Descriptions may be stale. Consult the linked Lean sources.
Two-Sided
Convolutional Perceptron
We study strict separation of vectors by a
convolutional perceptron with parameters
and margin , where is the cyclic shift by one coordinate.
Each vector has a constant background of either sign, bounded above and
away from zero in magnitude, plus a bounded centered defect. The scaled
differences between defects and their shifts share a unit separator with
positive margin. The oracle returns the margin and its parameter
derivative for a queried sample. Starting from , cyclic perceptron updates must
produce an output with
for every
sample and every realization.
Write and for integers, so there are samples. Inner products and norms on
are Euclidean. With
coordinates indexed by , define The task is to find parameters whose
margins are strictly positive simultaneously. The algorithm receives
; the data
vectors and their geometric decomposition are accessed only through the
oracle.
Our assumptions:
Assumption 1 (Parameter regime). The background
bounds , contrast , and derivative margin satisfy They also obey where is the natural logarithm and the
ceiling denotes the least integer greater than or equal to its positive
argument.
Assumption 2 (Two-sided background and defect
separation). There exist scalars , defects , and a vector such that and, for every ,
For a query ,
the oracle returns the exact pair , where
Our formulation is algorithm-specific: we analyze the two-sided
convolutional perceptron with cyclic sample queries and a fixed step
size . The algorithm
chooses from its available
inputs and initializes At each
call , it queries and applies Thus the sample index advances even when the
parameters remain unchanged. After an allotted number of oracle calls, the output is the
last iterate .
The required accuracy is strict separation: for every realization of
any algorithm randomness.