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 and
, where is the feature dimension. Its margin on
an input is
. 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 for the number of
non-anchor inputs and take . The algorithm
receives , with
The instance consists of residual vectors and offsets , for , accessed through the
oracle. They define the inputs All vector inner products and norms are
Euclidean.
Our assumptions:
Assumption 1 (Residual separation and offsets). The
data satisfy There exists such that
To specify the full-width parameterization, write where , , and is linear.
For ,
the margin is A query specifies an index and parameters . The oracle returns 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 from the available inputs and
initializes At call , it
queries and sets
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 oracle calls, the
output is the last parameter pair . The required accuracy is strict
separation: for every realization of any algorithm
randomness.