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
Write
Our assumptions:
Assumption 1 (Residual separation and offsets). The
data satisfy
To specify the full-width parameterization, write
Our result is algorithm-specific: we analyze the cyclic full-width
perceptron. The method chooses a fixed step size
After an allotted budget of
Results
Signed data in
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CyclicFullWidthPerceptronAcceleration (Ours) (review) | |||
| (2) Read then solve LP; derived bound (LongTails, n.d.-a) | (1): No established improvement. | (1): |
|
| (3) Rescaled linear Perceptron; derived bound (Novikoff 1963) | (1): Adaptivity: updates
and budget need no |
(1): |
|
| (4) Unrescaled linear Perceptron (Novikoff 1963; LongTails, n.d.-b) | Derived cyclic bound: |
(1): Rate gain if |
(1) requires the slab and
known |
| (5) Noisy quadratic Perceptron (Tyurin 2026), Thm. 5.1 | (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: