← All setups

Two Sided Convolutional Perceptron Acceleration — Two-Sided Convolutional Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Two-Sided Convolutional Perceptron · Lean proof

Two-Sided Convolutional Perceptron

We study strict separation of vectors b0,…,bn∈Rd by a convolutional perceptron with parameters θ=((a,c),w)∈R2×Rd and margin mi(θ)=a⟨bi,w⟩+c⟨Sbi,w⟩, where S is the cyclic shift by one coordinate. Each vector has a constant background of either sign, bounded above and away from zero in magnitude, plus a bounded centered defect. The scaled differences between defects and their shifts share a unit separator with positive margin. The oracle returns the margin and its parameter derivative for a queried sample. Starting from ((1,0),0), cyclic perceptron updates must produce an output θ¯ with mi(θ¯)>0 for every sample and every realization.

Write d≥1 and n≥0 for integers, so there are n+1 samples. Inner products and norms on Rd are Euclidean. With coordinates indexed by j=0,…,d−1, define (Su)j=u(j−1)modd,e=1d(1,…,1),Tu=u−Su2. The task is to find parameters whose margins are strictly positive simultaneously. The algorithm receives d,n,g,R,μ,κ; the data vectors and their geometric decomposition are accessed only through the oracle.

Our assumptions:

Assumption 1 (Parameter regime). The background bounds g,R, contrast μ, and derivative margin κ satisfy 0<g≤R,μ>0,κ>0. They also obey κμ⌈224(Rg)21+log⁡(1+g/μ)κ3⌉≤3R2, where log is the natural logarithm and the ceiling denotes the least integer greater than or equal to its positive argument.

Assumption 2 (Two-sided background and defect separation). There exist scalars βi∈R, defects ui∈Rd, and a vector v∈Rd such that ∥v∥=1 and, for every i=0,…,n, bi=βie+μui,g≤|βi|≤R,⟨e,ui⟩=0,∥ui∥≤12,⟨Tui,v⟩≥κ.

For a query (i,θ)∈{0,…,n}×(R2×Rd), the oracle returns the exact pair (mi(θ),hi(θ)), where mi(((a,c),w))=a⟨bi,w⟩+c⟨Sbi,w⟩,hi(((a,c),w))=((⟨bi,w⟩,⟨Sbi,w⟩),abi+cSbi).

Our formulation is algorithm-specific: we analyze the two-sided convolutional perceptron with cyclic sample queries and a fixed step size η>0. The algorithm chooses η from its available inputs and initializes θ0=((1,0),0),i0=0. At each call t, it queries (it,θt) and applies θt+1={θt+ηhit(θt),mit(θt)≤0,θt,mit(θt)>0,it+1=(it+1)mod(n+1). Thus the sample index advances even when the parameters remain unchanged. After an allotted number K≥0 of oracle calls, the output is the last iterate θ¯=θK. The required accuracy is strict separation: mi(θ¯)>0for every i=0,…,n, for every realization of any algorithm randomness.

Proved result

(samples+1)⋅⌈224⋅(upperlower)2⋅(1+log⁡(1+lowercontrast))margin3⌉+

OracleTemplate.Convergence LongTails.Setups.TwoSidedConvolutionalPerceptron.spec
  OracleTemplate.TwoSidedConvolutionalPerceptron.budget

Relevant previous results

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