← All setups

Noisy Batch Quadratic Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Noisy Batch Quadratic Perceptron

We consider strict separation of vectors a1,…,an∈Rd, where n≥1 and d≥0 are integers, by quadratic weights x=(v,s)∈Rd×R. The vectors are bounded and share a unit separating direction with positive margin. At a query (i,x), the oracle returns the margin s⟨ai,v⟩ and direction (sai,⟨ai,v⟩). We analyze the noisy batch quadratic perceptron, initialized at a given point, with independent standard Gaussian perturbations scaled by σ>0. For δ∈(0,1), the goal is an output x¯=(v¯,s¯) satisfying s¯⟨ai,v¯⟩>0 for every i with probability at least 1−δ.

Equip the weight space E=Rd×R with the Euclidean product norm ∥(v,s)∥2=∥v∥22+s2. For each data vector, define its quadratic margin and update direction by mi(v,s)=s⟨ai,v⟩,gi(v,s)=(sai,⟨ai,v⟩). The task is to find x∈E such that mi(x)>0 for all i∈{1,…,n}. The algorithm receives d, n, a radius R, a margin γ, the noise scale σ, the starting point x0∈E, and the prescribed noise source; only the oracle-call budget may additionally depend on δ.

Our assumptions:

Assumption 1 (Bounded separable data). The parameters satisfy 0<γ≤R. There exists u∈Rd such that ∥u∥2=1,∥ai∥2≤R,⟨u,ai⟩≥γ,i=1,…,n.

Assumption 2 (Gaussian perturbations). The prescribed noise source consists of a probability space (Ω,F,ν) and measurable maps Zk:Ω→E, k≥0. Under ν, these maps are mutually independent and satisfy Zk∼N(0,Id+1),k≥0, where Id+1 is the identity on E. The perturbation scale satisfies σ>0.

Queries may use any index i∈{1,…,n} and any weight x∈E. The oracle returns the exact pair (mi(x),gi(x)); 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 η>0 from its available inputs and starts at the given x0. During batch k, it queries indices 1,…,n in order at the unchanged weight xk. Define Vk={i∈{1,…,n}:mi(xk)≤0}. The accumulator starts at zero and adds gi(xk) exactly when i∈Vk. After a complete scan with Vk≠∅, the method updates xk+1=xk+ηn∑i∈Vkgi(xk)+σZk. It then resets the accumulator and begins the next scan at index 1. If a complete scan has Vk=∅, the method freezes at xk: subsequent calls repeat the last query (n,xk) and leave the weight unchanged. No perturbation is applied on such a scan.

Each complete scan uses n oracle calls. For a prescribed total budget N∈N, the output x¯ is the current weight after those calls. An incomplete final scan does not change the weight, and calls made after freezing still count toward N. The output must satisfy P(∃i∈{1,…,n}:mi(x¯)≤0)≤δ, where P is the law of the algorithm’s randomness, realizing the prescribed noise source.

Results

Signed data a1,…,an∈Rd, n≥1, satisfy ∥ai∥≤R and ⟨u,ai⟩≥δ for some ∥u∥=1, with 0<δ≤R. The setup requires averaged full-batch quadratic perceptron updates for w=(c,v), arbitrary w0, and IID N(0,Id+1) perturbations scaled by fixed σ>0, freezing after a successful scan. Result (1) uses η=δ/[8(n+1)R2]. Target: P{∃i: v⟨ai,c⟩≤0}≤ρ, 0<ρ<1. One call returns v⟨ai,c⟩ and (vai,⟨ai,c⟩).

Comparison for NoisyBatchQuadraticPerceptron.
Result Oracle complexity Novelty Limitations
(1) NoisyBatchQuadraticPerceptronGlobal (Ours) (review) O(nρ[n2R2δ2+∥w0∥2(d+1)σ2]⋅(2ρ)H)
(2) Data recovery + linear feasibility; derived bound (LongTails, n.d.) O(n) calls; deterministic. Query (c,v)=(0,1) to recover every ai; solve offline. (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 ρ; (2) assumes unrestricted offline computation.
(3) Cyclic perceptron (Novikoff 1962); derived scan cost O(n[1+R2/δ2]) calls; deterministic, initialized at zero. Queries (x,1) use the same oracle. (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) O(tL[1+log⁡(tL)]) per-example convolutional calls, success probability 1−ρ; n=2, dataset (5), kernel k=2. (1): Method-specific global convergence for arbitrary n, separable data, w0 and fixed σ>0 in the width-one model; frozen output eventually constant almost surely. Rates not comparable: different models. (4) requires 0<μ≤1/10, nonzero initial projection and theorem-tuned noise; its acceleration is not established for (1).

Abbr: QPA: quadratic perceptron algorithm; H=5exp(25000(d+1)2(n+1)4R4/δ4). For (4), a1=1, a2=−(1+μe1), t=d/μ, q=∥θ0∥2/|⟨θ0,vμ,+⟩|2, and L=[1+log⁡(q/ρ3)][1+log⁡(tq)]; vμ,+ is the unit eigenvector of the second sample’s convolutional matrix with eigenvalue μ, and θ0 its initial weight. log denotes the natural logarithm. Costs count all per-example calls, including full scans; offline arithmetic is not counted.

LongTails: NoisyBatchQuadraticPerceptron. n.d. Repository setup and oracle definition. https://github.com/k3nfalt/longtails/blob/main/LongTails/Setups/NoisyBatchQuadraticPerceptron.lean.
Novikoff, Albert B. J. 1962. “On Convergence Proofs for Perceptrons.” Proceedings of the Symposium on the Mathematical Theory of Automata 12: 615–22. https://cs.uwaterloo.ca/~y328yu/classics/novikoff.pdf.
Tyurin, Alexander. 2026. Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration. https://doi.org/10.48550/arXiv.2512.11587.

Lean setup