← All setups

Kernel Convolutional Perceptron Acceleration — Kernel Convolutional Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Kernel Convolutional Perceptron · Lean proof

Kernel Convolutional Perceptron

We study strict separation of n+1 vectors in Rd by a kernel convolutional perceptron with parameters (c,w)∈Rk×Rd, where d≥1, k≥2, and n≥0 are integers. Each vector consists of a nonzero constant background and a small centered defect; normalized high-pass defects share a unit separator with positive margin. The parameters satisfy a quantitative small-contrast condition. The oracle returns a sample’s bilinear convolutional margin and its update direction. Starting from the identity filter and zero readout, the method cycles through samples with a fixed positive step size. The goal is strictly positive margins on every sample, for every realization.

Write the data as b0,…,bn∈Rd. Inner products and norms on each factor are Euclidean. Let S be the cyclic shift defined by (Su)ℓ=u(ℓ−1)modd for 0≤ℓ<d, and set a=d−1/2(1,…,1). For c∈Rk, b,w∈Rd, define the response and margin by Ccb=∑j=0k−1cjSjb,mi(c,w)=⟨Ccbi,w⟩. The task is to find parameters for which all these margins are strictly positive. The algorithm receives d,k,n and the scalars g,R,μ,κ specified below; the data are accessed through the oracle.

Our assumptions:

Assumption 1 (Parameter regime). The integer parameters satisfy d≥1, k≥2, and n≥0. The real parameters satisfy 0<g≤R,0<μ≤R,0<κ≤1, and μ2(Rg)4[log⁡(128kR2(κμ)2)]2≤kκ6R21013.

Assumption 2 (Background and defect geometry). Define the high-pass operator on Rd by Hku=11−1/k(u−1k∑j=0k−1Sju). There exist background coefficients β0,…,βn∈R, defects u0,…,un∈Rd, and a separator v∈Rd with ∥v∥=1 such that, for every 0≤i≤n, bi=βi2a+μui,g≤|βi|≤R,⟨a,ui⟩=0,∥ui∥≤1k,⟨v,Hkui⟩≥κ.

At a query (i,(c,w))∈{0,…,n}×(Rk×Rd), the oracle returns exactly (mi(c,w),Gi(c,w)), where Gi(c,w)=((⟨Sjbi,w⟩)j=0k−1,Ccbi).

Our formulation is algorithm-specific: we analyze the kernel convolutional perceptron with cyclic sample selection and simultaneous updates of the filter and readout. The algorithm chooses a fixed step size η>0 from its inputs and initializes θ0=(c0,w0)=(e0,0),i0=0, where e0=(1,0,…,0)∈Rk. At each iteration it queries (it,θt) and applies θt+1={θt+ηGit(θt),mit(θt)≤0,θt,mit(θt)>0,it+1=(it+1)mod(n+1). The sample cursor advances after every query, including queries that leave the parameters unchanged. After T oracle calls, the output is the current pair θ¯=(c¯,w¯)=θT. Its required accuracy is exact strict separation: mi(c¯,w¯)>0for every i∈{0,…,n}, for every realization of any algorithmic randomness.

Proved result

(samples+1)⋅⌈200000⋅(upperlower)2derivativeMargin3⋅log⁡(128⋅kernel⋅upper2(derivativeMargin⋅contrast)2)⌉+

OracleTemplate.Convergence LongTails.Setups.KernelConvolutionalPerceptron.spec
  OracleTemplate.KernelConvolutionalPerceptronAcceleration.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.