← All setups

Two Sample Quadratic Perceptron Acceleration — Two-Sample Quadratic Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Two-Sample Quadratic Perceptron · Lean proof

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.

Proved result

⌈24⋅(radius⋅log⁡(ratio)slowLower+1)⋅(radiusgain+1)2⋅(3+2⋅couplingUpper⋅log⁡(ratio)slowLower+log⁡(size⋅(1wedgeLower+8⋅radius3couplingLower3⋅depthLower)))⌉+

OracleTemplate.Convergence LongTails.Setups.TwoSampleQuadraticPerceptron.spec
  OracleTemplate.TwoSampleQuadraticPerceptron.budget

Relevant previous results

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