Descriptions may be stale. Consult the linked Lean sources.
Many-Sample Convolutional
Separation
We consider strict separation of one positive reference vector and
negative sample vectors in
, where , using parameters .
The score is , where is the cyclic coordinate shift and
is the
Euclidean inner product. The reference is constant across coordinates;
samples have bounded positive constant backgrounds and small centered
defects whose cyclic differences share a separating direction. The
oracle returns a selected example’s signed score and parameter
direction. The goal is an output with strictly positive reference score
and strictly negative scores on all samples, for every realization of
algorithm randomness.
Write the data as a reference and samples .
Coordinates are indexed by , with All inner products and norms
on are Euclidean. The
algorithm receives , where bound the background amplitudes,
scales the defects, and is a directional margin. The data
and their geometric witnesses are accessed only through the oracle.
Our assumptions:
Assumption 1 (Parameter regime). The dimensions
satisfy ,
and Define
where is the
smallest nonnegative integer at least . These quantities satisfy
Assumption 2 (Background and defect geometry). There
exist amplitudes , defects
, and
a vector such that
The defects and common direction satisfy
For oracle access, define signed examples and for . A query consists of any
index and any
parameter .
The oracle returns the exact pair
where Initialization is chosen by the algorithm. After
the allotted oracle calls, its output
must satisfy for every realization of the algorithm’s
randomness.