← All setups

Two-Sided Convolutional Perceptron

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Samples Di=αie+μui∈Rd, d,N≥1, 0<g≤|αi|≤R, μ,κ>0, ui⊥e, ∥ui∥≤1/2, and a unit w with ⟨(ui−Pui)/2,w⟩≥κ. The setup requires μκ⌈224(R/g)2[1+log⁡(1+g/μ)]/κ3⌉≤3R/2. Exact sample margin/gradient queries; the permitted family cyclically updates on nonpositive margins from ((1,0),0). Target: m(Di;θ)>0 for every sample, deterministically.

Comparison for TwoSidedConvolutionalPerceptron.
Result Oracle complexity Novelty Limitations
(1) TwoSidedConvolutionalPerceptronAcceleration (Ours) (review) O(NR2g2κ3[1+log⁡(1+g/μ)])
(2) Read-and-solve (elementary derived bound) O(N) queries; offline linear feasibility on (Di−PDi)/2. (1): No established improvement in problem-class complexity. Analyzes jointly learned filter dynamics; (2) lies outside the permitted family. (1): Higher query cost; needs κ,R for tuning and g,μ for stopping; requires small contrast. (2) is parameter-free.
(3) Fixed-filter perceptron, derived bound (Novikoff 1962) O(N/κ2), including cyclic scans; filter (1,−1)/2, features μri. (1): No established improvement in complexity. New analysis of coupled filter/weight dynamics; (3) freezes the filter outside the permitted family. (1): Extra (R/g)2κ−1[1+log⁡(1+g/μ)] factor in the bound; small-contrast restriction. Same oracle suffices for (3).
(4) Two-sample QPA (Tyurin 2026), Theorem 5.1 O(dνA[1+log⁡(dA/ν)]); probability 1−ρ; dataset (5), 0<ν≤1/10, h>0, theorem-tuned Gaussian noise. (1): Method-specific analysis for N samples and signed intensities, deterministic identity start. Disjoint classes: (4) has a zero derivative feature; rates not comparable. (1) does not cover (4)’s dataset or generic perturbed starts; uses margin-tuned step κ/(96R) and small contrast.

Abbr: N: sample count; P: circular shift; e=1/d; ri=(ui−Pui)/2; m(b;(c1,c2),v)=c1⟨b,v⟩+c2⟨Pb,v⟩. In (4), ν is its dataset perturbation, ρ∈(0,1) its failure probability, h=|⟨θ0,vν,+⟩|, vν,+ its unit positive-eigenvalue direction, q=∥θ0∥2/h2, and A=[1+log⁡(q/ρ3)][1+log⁡(dq/ν)].

Novikoff, Albert B. J. 1962. “On Convergence Proofs for Perceptrons.” Proceedings of the Symposium on the Mathematical Theory of Automata 12: 615–22. https://cs.uwaterloo.ca/~y328yu/classics/novikoff.pdf.
Tyurin, Alexander. 2026. Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration. https://doi.org/10.48550/arXiv.2512.11587.

Lean setup