Descriptions may be stale. Consult the linked Lean sources.
Clustered
Convolutional Separation
We seek a convolutional separator
for samples , where
and are integers. Each sample combines
a constant background of bounded, nonzero magnitude with an orthogonal
defect; the defects cluster near a small center with a nonzero cyclic
difference, subject to a quantitative small-contrast condition. Writing
for the cyclic coordinate shift,
the margin is . At a queried sample and
parameter, the oracle returns this margin and its exact parameter
derivative. The goal is an output satisfying for every sample and
every realization of the algorithm’s randomness.
Equip the feature space with its Euclidean inner
product and norm. For coordinates indexed by , define The task is the strict
feasibility problem of finding
with positive margins on all
samples. The algorithm receives ; the samples and their
geometric decomposition are accessed only through the oracle.
Our assumptions:
Assumption 1 (Parameter regime). The background
bounds , contrast , and derivative margin satisfy
Assumption 2 (Clustered sample geometry). There
exist background coefficients , defects
, and
a center such
that, for every , The center satisfies
A query consists of an index and any parameter
.
The exact oracle returns the scalar margin and the direction After the allotted oracle calls, the
output
must satisfy for every
realization of the algorithm’s randomness.