Noisy Batch Quadratic Perceptron
Descriptions may be stale. Consult the linked Lean sources.
Noisy Batch Quadratic Perceptron
We consider strict separation of vectors
Equip the weight space
Our assumptions:
Assumption 1 (Bounded separable data). The
parameters satisfy
Assumption 2 (Gaussian perturbations). The
prescribed noise source consists of a probability space
Queries may use any index
Our formulation is algorithm-specific: we analyze the noisy batch
quadratic perceptron. The method chooses a fixed step size
Each complete scan uses
Results
Signed data
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) NoisyBatchQuadraticPerceptronGlobal (Ours) (review) | |||
| (2) Data recovery + linear feasibility; derived bound (LongTails, n.d.) | (1): No established improvement in classification cost, data scope, or output. (2) uses the same oracle but falls outside the prescribed family. | (1) has larger cost
throughout the domain and allows failure probability |
|
| (3) Cyclic perceptron (Novikoff 1962); derived scan cost | (1): No established improvement in classification cost or scope. (3) uses linear updates outside the prescribed family; arbitrary initialization also converges. | (1) adds dimension, noise, initialization and confidence dependence; its displayed cost is worse. The arbitrary-start bound for (3) adds initialization dependence. | |
| (4) Two-sample noisy QPA (Tyurin 2026, Theorem 5.1, v2) | (1): Method-specific
global convergence for arbitrary |
Rates not comparable: different models.
(4) requires |
Abbr: QPA: quadratic perceptron algorithm;