← All setups

Noisy Batch Quadratic Perceptron Global — Noisy Batch Quadratic Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Noisy Batch Quadratic Perceptron · Lean proof

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.

Proved result

⌈100000⋅count⋅((count+1)2⋅(radiusmargin)2+‖start‖2noiseScale2⋅(dimension+1))⋅(2failure)5⋅exp⁡(25000⋅(dimension+1)2⋅((count+1)2⋅(radiusmargin)2)2)failure⌉+

OracleTemplate.Convergence LongTails.Setups.NoisyBatchQuadraticPerceptron.spec
  OracleTemplate.NoisyBatchQuadraticPerceptronGlobal.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.