← All setups

Cyclic Full Width Perceptron Acceleration — Cyclic Full-Width Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Cyclic Full-Width Perceptron · Lean proof

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.

Proved result

(count+1)⋅⌈256κ4⌉+

OracleTemplate.Convergence LongTails.Setups.CyclicFullWidthPerceptron.spec
  OracleTemplate.CyclicFullWidthPerceptronAcceleration.budget

Relevant previous results

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