← All setups

Cyclic Full-Width Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Cyclic Full-Width Perceptron

We consider strict separation by a two-layer linear model with parameters W∈R(d+1)×(d+1) and v∈Rd+1, where d is the feature dimension. Its margin on an input q∈Rd+1 is mq(W,v)=v⊤Wq. The inputs comprise an anchor and perturbed opposite inputs whose residual features have bounded norms and a common positive separating projection. The perturbation scales obey explicit smallness conditions. The oracle returns the exact margin and its parameter gradient. We analyze the cyclic full-width perceptron, initialized at the identity matrix and zero head. The goal is an output with strictly positive margins on every input, for every realization.

Write n≥1 for the number of non-anchor inputs and take d∈Z≥0. The algorithm receives d,n,κ,μ,ν, with 0<κ≤1,0<μ≤κ4220,0≤ν≤κ12μ2256. The instance consists of residual vectors ri∈Rd and offsets δi∈R, for i=1,…,n, accessed through the oracle. They define the inputs q0=(10),qi=(−(1+δi)−μri),i=1,…,n. All vector inner products and norms are Euclidean.

Our assumptions:

Assumption 1 (Residual separation and offsets). The data satisfy 0≤δi≤ν,∥ri∥≤1,i=1,…,n. There exists w∈Rd such that ∥w∥=1,⟨w,ri⟩≥κ,i=1,…,n.

To specify the full-width parameterization, write W=(au⊤cM),v=(bh), where a,b∈R, u,c,h∈Rd, and M:Rd→Rd is linear. For q=(s,z)∈R×Rd, the margin is mq(W,v)=b(as+⟨u,z⟩)+⟨h,sc+Mz⟩. A query specifies an index i∈{0,…,n} and parameters (W,v). The oracle returns (mqi(W,v),(vqi⊤,Wqi)). The second component is the parameter gradient, using the Frobenius inner product for matrices and the Euclidean inner product for the head.

Our result is algorithm-specific: we analyze the cyclic full-width perceptron. The method chooses a fixed step size η>0 from the available inputs and initializes W0=Id+1,v0=0,i0=0. At call t≥0, it queries (it,Wt,vt) and sets γt=mqit(Wt,vt),(Wt+1,vt+1)={(Wt+ηvtqit⊤,vt+ηWtqit),γt≤0,(Wt,vt),γt>0,it+1=(it+1)mod(n+1). Both parameter updates use the parameters before the update. The index advances after every query, including queries with positive margin.

After an allotted budget of T∈Z≥0 oracle calls, the output is the last parameter pair (W¯,v¯)=(WT,vT). The required accuracy is strict separation: mqi(W¯,v¯)>0,i=0,…,n, for every realization of any algorithm randomness.

Results

Signed data in Rd+1 are q0=(1,0) and qi=(−(1+νi),−μui), 1≤i≤N, with N≥1, ∥ui∥≤1, and a unit w satisfying ⟨w,ui⟩≥κ. Parameters obey 0<κ≤1, 0<μ≤κ4/220, and 0≤νi≤ν≤κ12μ2/256. The exact per-example oracle returns v⊤Wqi and its parameter gradient. The setup requires cyclic, constant-positive-step mistake updates from W=I,v=0, with the current parameters as output; (1) uses η=κ6/228. The target is deterministic strict separation, v⊤Wqi>0 for every i.

Cyclic full-width Perceptron: comparison for CyclicFullWidthPerceptron.
Result Oracle complexity Novelty Limitations
(1) CyclicFullWidthPerceptronAcceleration (Ours) (review) O((N+1)/κ4)
(2) Read then solve LP; derived bound (LongTails, n.d.-a) O(N+1) calls; recover each qi at W=I,v=0, then solve an offline LP. Applies to all separable data, outside the required update family. (1): No established improvement. (1): κ−4 worse call bound; needs κ and the slab. Uses O(d2) arithmetic per update; (2) incurs offline LP arithmetic.
(3) Rescaled linear Perceptron; derived bound (Novikoff 1963) O((N+1)/κ2) calls on (qi,0,qi′/μ), including a certifying pass. Same oracle; outside the required update family. (1): Adaptivity: updates and budget need no μ; (3) needs μ for rescaling. (1): κ−2 worse call bound; needs κ and the slab. (3) certifies separation without κ and converges on arbitrary separable data.
(4) Unrescaled linear Perceptron (Novikoff 1963; LongTails, n.d.-b) Derived cyclic bound: O((N+1)/(μ2κ2)). Any constant step from zero, any order: >1/(2μ2) calls on the target data. (1): Rate gain if (N+1)⌈256/κ4⌉<1/(2μ2). Fixed κ, μ=κ4/[220(N+1)]: O(N) versus Ω(N2) calls. Gain is confined to unrescaled updates. (1) requires the slab and known κ; (4) converges on arbitrary separable data.
(5) Noisy quadratic Perceptron (Tyurin 2026), Thm. 5.1 O(DmL1L2[1+log(DmL1L2)]) calls, success probability ≥1−ρ. Two-sample dataset (5), 0<m≤1/10, nonzero initial alignment; prescribed step and noise tuning. (1): Method-specific analysis for many conflicting residual directions, noiseless and deterministic. (5) uses tuned noise on two samples outside the slab; rates are not comparable. (1) analyzes full width, not the size-2 convolution of (5); its slab theorem does not cover (5)’s dataset.

Abbr: N: negative-example count; d: residual dimension; κ: latent margin; μ: residual scale; ν: offset bound; W,v: layer matrix and head; LP: linear program. Costs count individual example queries, including scans. In (5), D,m are that paper’s dimension and margin parameter (distinct from d,μ here), 0<ρ<1 is failure probability, r=∥θ0∥2/|⟨θ0,vm,+⟩|2, vm,+ is its unit eigenvector of eigenvalue m, L1=1+log⁡(r/ρ), and L2=1+log⁡(Dr/m).

LongTails: CyclicFullWidthPerceptron. n.d.-a. Repository setup, oracle definition. https://github.com/k3nfalt/longtails/blob/main/LongTails/Setups/CyclicFullWidthPerceptron.lean.
LongTails: CyclicPerceptronLinearComparison. n.d.-b. Repository comparison result. https://github.com/k3nfalt/longtails/blob/main/LongTails/Proofs/CyclicPerceptronLinearComparison.lean.
Novikoff, Albert B. J. 1963. “On Convergence Proofs for Perceptrons.” Proceedings of the Symposium on the Mathematical Theory of Automata (Brooklyn, New York), Microwave research institute symposia series, vol. 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