← All setups

Two-Sample Quadratic Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Two-Sample Quadratic Perceptron

We study strict separation of two labeled vectors b+,b−∈Rd by a quadratic perceptron with score F(b;θ). The parameter θ belongs to Rd×R for the two-layer model or R2×Rd for the convolutional model. The data have norms at most R>0 and satisfy model-specific geometric and spectral bounds; a given initialization θ0 satisfies signed wedge, depth, and size conditions. The oracle returns both signed scores and their parameter-gradient directions exactly. A fixed positive-step perceptron updates the first misclassified sample, prioritizing b+. The goal is an output θ¯ with F(b+;θ¯)>0 and F(b−;θ¯)<0 for every realization.

Let d∈N0, with Euclidean inner product and norm on the feature space Rd. Write 1∈Rd for the all-ones vector and S for the cyclic shift, so that (Sb)i=bi−1modd when d>0; in dimension zero, S is the unique map. The two scores are F(b;(w,a))=a⟨w,b⟩(two-layer),F(b;((u,v),w))=u⟨b,w⟩+v⟨Sb,w⟩(convolutional). Their parameter-gradient directions, in the same coordinate order, are G(b;(w,a))=(ab,⟨w,b⟩),G(b;((u,v),w))=((⟨b,w⟩,⟨Sb,w⟩),ub+vSb). The algorithm receives only the model, d, R, and θ0. The remaining parameters introduced below may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Data geometry). Both samples satisfy ∥b+∥≤R and ∥b−∥≤R. For the two-layer model, define eA=b+∥b+∥,n=b−−⟨b−,eA⟩eA,eB=n∥n∥. We require ⟨b+,b−⟩>0 and n≠0. For the convolutional model, define the mean level and the centered directions by ℓ(b)=⟨b,1⟩d,b~−=b−−ℓ(b−)1,h+=b~−+Sb~−,h−=b~−−Sb~−. We require b+=ℓ(b+)1,ℓ(b+)>0,ℓ(b−)>0,h+≠0. The admissible data necessarily have d>0; all mean levels above are taken in this case.

Assumption 2 (Spectral bounds). Let g>0, 0<c−≤c+, and s−>0. Define the model-dependent quantities (λ1,λ2,c,s)={(∥b+∥,⟨b−,eA⟩,∥n∥,0),two-layer,(ℓ(b+)2d,ℓ(b−)2d,∥h+∥/2,∥h−∥/2),convolutional. They satisfy λ1≥g,λ2≥g,c−≤c≤c+. For the convolutional model, additionally s≥s−.

Assumption 3 (Initialization geometry). Let ρ≥1 and ω,δ,M>0. For the given starting point, define coordinates (p,q,z,r,y) as follows. In the two-layer model, with θ0=(w0,a0), set p=a0,q=⟨w0,eA⟩,z=⟨w0,eB⟩,r=y=0. In the convolutional model, with θ0=((u0,v0),w0), set p=u0+v02,q=⟨w0,1⟩d,z=⟨w0,h+⟩∥h+∥,r=u0−v02,y=⟨w0,h−⟩∥h−∥. Writing σ=−sgn(z), we require |r+y|≤ρ|r−y|,|z|≥δ,σ(p+q)≥ω,σ(p−q)≥0,2σp+2|z|≤M.

Our result is algorithm-specific: we analyze the two-sample quadratic perceptron with a constant step size γ>0. At any query point θ, one oracle call returns the tuple (F(b+;θ), G(b+;θ), −F(b−;θ), −G(b−;θ)). Starting at the supplied θ0, the method follows θk+1={θk+γG(b+;θk),F(b+;θk)≤0,θk−γG(b−;θk),F(b+;θk)>0, F(b−;θk)≥0,θk,F(b+;θk)>0, F(b−;θk)<0. The step size is fixed throughout the run and may depend only on the available inputs. After K∈N0 oracle calls, the output is the current iterate θ¯=θK. The required accuracy is strict separation, F(b+;θ¯)>0,F(b−;θ¯)<0, for every realization of any algorithm or oracle randomness.

Results

Two labeled samples b1,b2∈Rd, ∥bi∥≤R. The width-one model is m(b;(v,c))=c⟨v,b⟩, with ⟨b1,b2⟩>0 and b2∦b1; the kernel-two model is m(b;((c1,c2),v))=c1⟨b,v⟩+c2⟨Pb,v⟩, with b1=b¯11, b¯1,b¯2>0, and (I+P)(b2−b¯21)≠0. In the setup’s coordinates and spectrum, g≤λ1,λ2, β−≤β≤β+, and the kernel-two slow eigenvalue is at least μ. All bounds R,g,β−,β+,μ,a,z,S are positive and ρ≥1. The start satisfies |r0+y0|≤ρ|r0−y0|, |z0|≥z, σ(p0+q0)≥a, σ(p0−q0)≥0, and 2σp0+2|z0|≤S. One oracle call returns exact signed margins and gradients for the two samples. The setup requires constant-step, first-violated-sample updates and the current iterate as output; (1) uses γ=1/(2R). Target: deterministically m(b1;θT)>0>m(b2;θT), also at every later step.

Two-sample quadratic perceptron: TwoSampleQuadraticPerceptron.
Result Oracle complexity Novelty Limitations
(1) TwoSampleQuadraticPerceptronAcceleration (Ours) (⋆⋆) (review) O((1+Rlog⁡ρμ)(1+Rg)2⋅[1+β+log⁡ρμ+log⁡(Sa+SR3(β−)3z)])
(2) Noisy quadratic perceptron (Tyurin 2026, Thm. 5.1, v2). Special case: kernel two, b1=1, b2=1+μe1, 0<μ≤1/10. O(dμL1L2[1+log(dL1L2μ)]) calls; success probability 1−δ. Requires h>0, γ=1/(4d), and the theorem’s tuned Gaussian perturbations. (1): Deterministic, noise-free analysis; extends to general admissible convolutional data and width one. On this dataset, matches d/μ up to unordered initialization logarithms; if r0y0≤0, gives O(1+log⁡(S/a+Sd3/2/(μ3z))) instead. (1) needs a data-dependent cone of starts; (2) covers every start with h>0.
(3) Derived bound: direct reconstruction; linear representation (Tyurin 2026, sec. 1.1). Same data and oracle, unrestricted updates. O(1): one call recovers b1,b2; construct a linear separator and represent it in either model. (1): No established improvement in problem-class complexity. Its contribution concerns the prescribed perceptron dynamics. (1) has a larger bound and restricts starts. (3) lies outside the required update family.
(4) Batch linear perceptron (Tyurin 2026, Thm. 5.2, v2). Special case: b1=1, b2=1+μe1, 0<μ≤1/2. Lower bound Ω(d/μ) paired-sample calls; step ϕ>0, initial linear weight u0∈B(0,ϕμ/(8maxi∥bi∥)). (1) retains the inherited quadratic-versus-linear method contrast; (4) is a lower bound, not a competing upper bound. Different initializations preclude an identical-start comparison.

Abbr: P: cyclic coordinate shift; b¯=d−1⟨b,1⟩; (p0,q0,z0,r0,y0): the linked setup’s coordinates of θ0; σ=−sign(z0). g: lower bound on fast coefficients λ1,λ2; β−,β+: coupling bounds; μ: slow-eigenvalue lower bound (also the sample perturbation in (2), (4)); a,z,S: cone-margin, depth and size bounds; ρ: slow-coordinate ratio bound. Width one has r0=y0=0 and permits ρ=1. h=|⟨θ0,vμ,+⟩|, with vμ,+ the unit positive slow eigenvector of the signed second-sample quadratic form; δ∈(0,1): failure probability; L1=1+log⁡(∥θ0∥2/(δ3h2)), L2=1+log⁡(d∥θ0∥2/(μh2)). Costs count exact margin-and-gradient queries for the two samples; counting individual sample queries changes only a universal factor.

Tyurin, Alexander. 2026. Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration. https://doi.org/10.48550/arXiv.2512.11587.

Lean setup