Descriptions may be stale. Consult the linked Lean sources.
Noisy Batch
Quadratic Perceptron
We consider strict separation of vectors , where
and are integers, by quadratic weights
.
The vectors are bounded and share a unit separating direction with
positive margin. At a query ,
the oracle returns the margin and direction . We analyze the noisy batch quadratic
perceptron, initialized at a given point, with independent standard
Gaussian perturbations scaled by . For , the goal is an output
satisfying for every with probability at least .
Equip the weight space with the
Euclidean product norm For each data
vector, define its quadratic margin and update direction by The task is to find such that for all . The algorithm
receives , , a radius , a margin , the noise scale , the starting point , and the prescribed noise
source; only the oracle-call budget may additionally depend on .
Our assumptions:
Assumption 1 (Bounded separable data). The
parameters satisfy . There exists such that
Assumption 2 (Gaussian perturbations). The
prescribed noise source consists of a probability space and measurable
maps , . Under , these maps are mutually independent
and satisfy where is
the identity on . The perturbation
scale satisfies .
Queries may use any index and any weight . The oracle returns the exact pair
; the Gaussian noise
enters the weight updates.
Our formulation is algorithm-specific: we analyze the noisy batch
quadratic perceptron. The method chooses a fixed step size from its available inputs and
starts at the given . During
batch , it queries indices in order at the unchanged
weight . Define
The accumulator starts at zero and adds exactly when . After a complete scan with
, the method
updates It then resets the accumulator and
begins the next scan at index . If
a complete scan has , the method freezes at
: subsequent calls repeat the
last query and leave the
weight unchanged. No perturbation is applied on such a scan.
Each complete scan uses oracle
calls. For a prescribed total budget , the output is the current weight after those
calls. An incomplete final scan does not change the weight, and calls
made after freezing still count toward . The output must satisfy where is the
law of the algorithm’s randomness, realizing the prescribed noise
source.