Descriptions may be stale. Consult the linked Lean sources.
Two-Sample
Quadratic Perceptron
We study strict separation of two labeled vectors by a quadratic
perceptron with score .
The parameter belongs to
for
the two-layer model or for the
convolutional model. The data have norms at most and satisfy model-specific
geometric and spectral bounds; a given initialization 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 . The goal is an output with and for every
realization.
Let , with
Euclidean inner product and norm on the feature space . Write for the
all-ones vector and for the
cyclic shift, so that when ; in
dimension zero, is the unique
map. The two scores are Their parameter-gradient directions, in the same
coordinate order, are The algorithm receives only the model, , , and . 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
and . For the two-layer model,
define We require and . For the convolutional model,
define the mean level and the centered directions by We require The
admissible data necessarily have ; all mean levels above are taken
in this case.
Assumption 2 (Spectral bounds). Let , , and . Define the model-dependent
quantities They satisfy For the convolutional model, additionally
.
Assumption 3 (Initialization geometry). Let and . For the given
starting point, define coordinates as follows. In the two-layer
model, with , set
In the convolutional
model, with , set Writing , we require
Our result is algorithm-specific: we analyze the two-sample quadratic
perceptron with a constant step size . At any query point , one oracle call returns the tuple
Starting at the supplied
, the method follows The step size is fixed throughout the run and may
depend only on the available inputs. After oracle calls, the output
is the current iterate . The required
accuracy is strict separation, for every realization of any
algorithm or oracle randomness.