← All setups

Many-Sample Convolutional Separation

Descriptions may be stale. Consult the linked Lean sources.

Many-Sample Convolutional Separation

We consider strict separation of one positive reference vector and n≥1 negative sample vectors in Rd, where d≥1, using parameters θ=((a,b),w)∈R2×Rd. The score is hθ(x)=a⟨x,w⟩+b⟨Sx,w⟩, where S is the cyclic coordinate shift and ⟨⋅,⋅⟩ is the Euclidean inner product. The reference is constant across coordinates; samples have bounded positive constant backgrounds and small centered defects whose cyclic differences share a separating direction. The oracle returns a selected example’s signed score and parameter direction. The goal is an output with strictly positive reference score and strictly negative scores on all samples, for every realization of algorithm randomness.

Write the data as a reference x0∈Rd and samples x1,…,xn∈Rd. Coordinates are indexed by j=0,…,d−1, with (Sx)j=xj−1modd,u=1d(1,…,1). All inner products and norms on Rd are Euclidean. The algorithm receives d,n,g,R,μ,κ, where g,R bound the background amplitudes, μ scales the defects, and κ is a directional margin. The data and their geometric witnesses are accessed only through the oracle.

Our assumptions:

Assumption 1 (Parameter regime). The dimensions satisfy d,n∈N≥1, and 0<g≤R,μ>0,0<κ≤1. Define ρ=g4R,δ=(μ4R)2,B=⌈8ρ2log⁡1δ⌉++2, where ⌈t⌉+ is the smallest nonnegative integer at least t. These quantities satisfy δ≤e−1,δ(B+1)3≤κ316777216,δ(B+1)2≤κ2ρ416777216.

Assumption 2 (Background and defect geometry). There exist amplitudes c0,c1,…,cn∈R, defects z1,…,zn∈Rd, and a vector v∈Rd such that x0=c02u,g≤c0≤R,xi=ci2u+μzi,g≤ci≤R(1≤i≤n). The defects and common direction satisfy ⟨u,zi⟩=0,∥zi∥≤12(1≤i≤n),∥v∥=1,−⟨zi−Szi2,v⟩≥κ(1≤i≤n).

For oracle access, define signed examples q0=x0 and qi=−xi for 1≤i≤n. A query consists of any index i∈{0,…,n} and any parameter θ=((a,b),w)∈R2×Rd. The oracle returns the exact pair (mi(θ),Gi(θ)), where mi(θ)=a⟨qi,w⟩+b⟨Sqi,w⟩,Gi(θ)=((⟨qi,w⟩,⟨Sqi,w⟩),aqi+bSqi). Initialization is chosen by the algorithm. After the allotted oracle calls, its output θ¯∈R2×Rd must satisfy hθ¯(x0)>0,hθ¯(xi)<0(1≤i≤n), for every realization of the algorithm’s randomness.

Results

In Rd, d,n≥1, the positive reference is b0=α0e/2 and the n negative samples are bi=αie/2+μui, with 0<g≤αi≤R, μ>0, ui⊥e, and ∥ui∥≤1/2. There exists ∥w∥=1 with −⟨(ui−Pui)/2,w⟩≥κ, 0<κ≤1. Validity requires δ≤e−1, δ(B+1)3≤κ3/224, and δ(B+1)2≤κ2ρ4/224. Each call returns one sample’s exact signed margin and gradient. The target is deterministic strict separation: m(b0;θ)>0 and m(bi;θ)<0 for all i≥1. The setup imposes no algorithm-family restriction.

Many-sample convolutional separation under the ManySampleConvolutionalPerceptron setup.
Result Oracle complexity Novelty Limitations
(1) ManySampleConvolutionalPerceptronAcceleration (Ours) (review) O((R/g)4ℓ2κ2[n+(R/g)ℓ])
(2) Derived bound: reconstruction + LP; convolutional model (Tyurin 2026, sec. 2) O(n+1) calls; offline linear separation after recovering each signed sample at θ=((1,0),0). (1): O(d) state instead of O(nd) cached data. No established oracle-complexity improvement; the setup imposes no memory constraint. (1): cost larger by (R/g)4ℓ2[1+(R/g)ℓ/n]/κ2; ℓ2 when R/g,κ are constant and n≳ℓ. Needs small contrast, R,μ for updates, g,κ for stopping; (2) needs none.
(3) Noisy quadratic perceptron (Tyurin 2026, Thm. 5.1, v2) O(dνH[1+log(dHν)]). Special case: n=1, b0=1, b1=1+νE0, 0<ν≤1/10; success probability ≥1−β, nonzero initial alignment, tuned Gaussian perturbations. (1): Method-specific O(log3⁡(d/ν)) versus (3) when ν≲2−22d/log3/2⁡(d/ν) and setup validity holds. Scope: many derivative-separable defects. Deterministic guarantee. No problem-class speedup over (2). (1) requires small contrast and one fixed initialization; changes the method to a directed deterministic kick and restarting scan. Its analysis does not establish GD equivalence.

Abbr: e=1/d; P is the cyclic shift; E0 is a coordinate unit vector; θ=((a1,a2),v); m(b;θ)=a1⟨b,v⟩+a2⟨Pb,v⟩; ρ=g/(4R), δ=μ2/(16R2), B=⌈8ρ−2log⁡(1/δ)⌉+2; ℓ=1+max{0,log⁡(R/μ)}. In (3), ν is the coordinate defect, 0<β<1 is the failure probability, Q=∥θ0∥2/|⟨θ0,vν,+⟩|2, and H=[1+log⁡(Q/β3)][1+log⁡(dQ/ν)]; vν,+ is the unit eigenvector of the negative signed-margin Hessian with eigenvalue ν. Oracle costs count individual sample queries; offline arithmetic is excluded.

Tyurin, Alexander. 2026. “Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration.” Proceedings of the 43rd International Conference on Machine Learning, Proceedings of machine learning research, vol. 306: 122808–75. https://proceedings.mlr.press/v306/tyurin26a.html.

Lean setup