Descriptions may be stale. Consult the linked Lean sources.
Finite-Scale
Convolutional SGD
We seek strict separation of vectors , where , using parameters
and margins , where is the cyclic coordinate shift. The
data have bounded, nonzero backgrounds and small centered defects with a
common positive derivative margin. The oracle returns and its parameter gradient.
We analyze SGD with independent uniform sample indices, exhaustive
separation scans, and periodic restarts from a scaled initialization.
For , the goal is an
output with , where is the law of the algorithm’s
randomness.
Index the data by and the coordinates
by . Write
and . Inner products
and norms on the feature space are Euclidean. The task is to find a
parameter vector satisfying The algorithm receives , background bounds , contrast , derivative margin , initial coefficients , an initial readout , and the sampling
source specified below. The failure tolerance may enter only the oracle-call
budget.
Our assumptions:
Assumption 1 (Data geometry). The parameters satisfy
, , and . There exist scalars
, defects , and a vector such that, for every
,
Assumption 2 (Finite-scale regime and
initialization). The given initial coefficients satisfy
Define the auxiliary quantities They satisfy
Assumption 3 (Uniform sampling). The given sampling
source consists of a probability law on a measurable space and measurable maps , . Under , the variables are mutually independent and
each is uniform on .
At any query , the
oracle returns the exact pair , where Thus is the coordinate gradient of the
margin. Each queried pair counts as one oracle call, including calls
used to scan the data or at restart steps.
Our formulation is algorithm-specific: we analyze convolutional SGD
with separation scans and periodic restarts. The algorithm chooses a
fixed step size , a scale
, and a restart period from its available
inputs. The auxiliary quantity
above does not prescribe .
Define The algorithm
starts at with training
counter and draws its sampling
source with law . Any additional
algorithm randomness must preserve this sampling law.
Before each training call, the algorithm queries all indices in order
at its current point
, without changing that
point during the scan. If every scanned margin is strictly positive, it
freezes the point permanently. Otherwise it queries and sets It then increments and begins a new complete scan. In
particular, a restart consumes the sampled oracle call even though its
reply is discarded. Each completed scan followed by a training call uses
calls. Once frozen, any
remaining calls repeat the query at index at the frozen point and leave the
point unchanged.
At exhaustion of the allotted oracle calls, including exhaustion
during a scan, the output is the current point. The
required accuracy is strict separation with failure probability at most
: