Descriptions may be stale. Consult the linked Lean sources.
Kernel
Convolutional Perceptron
We study strict separation of vectors in by a kernel convolutional
perceptron with parameters ,
where , , and are integers. Each vector consists
of a nonzero constant background and a small centered defect; normalized
high-pass defects share a unit separator with positive margin. The
parameters satisfy a quantitative small-contrast condition. The oracle
returns a sample’s bilinear convolutional margin and its update
direction. Starting from the identity filter and zero readout, the
method cycles through samples with a fixed positive step size. The goal
is strictly positive margins on every sample, for every realization.
Write the data as . Inner
products and norms on each factor are Euclidean. Let be the cyclic shift defined by for , and set . For , , define the response
and margin by The task is to find parameters for which all
these margins are strictly positive. The algorithm receives and the scalars specified below; the data
are accessed through the oracle.
Our assumptions:
Assumption 1 (Parameter regime). The integer
parameters satisfy , , and . The real parameters satisfy and
Assumption 2 (Background and defect geometry).
Define the high-pass operator on by There exist
background coefficients ,
defects , and a
separator with
such that, for every ,
At a query ,
the oracle returns exactly , where
Our formulation is algorithm-specific: we analyze the kernel
convolutional perceptron with cyclic sample selection and simultaneous
updates of the filter and readout. The algorithm chooses a fixed step
size from its inputs and
initializes
where . At
each iteration it queries and applies The sample cursor advances after every query,
including queries that leave the parameters unchanged. After oracle calls, the output is the current
pair . Its required accuracy is exact strict separation:
for every
realization of any algorithmic randomness.