← All setups

Clustered Convolutional Separation

Descriptions may be stale. Consult the linked Lean sources.

Clustered Convolutional Separation

We seek a convolutional separator θ=((a,b),w)∈R2×Rd for samples z0,…,zn∈Rd, where d≥1 and n≥0 are integers. Each sample combines a constant background of bounded, nonzero magnitude with an orthogonal defect; the defects cluster near a small center with a nonzero cyclic difference, subject to a quantitative small-contrast condition. Writing S for the cyclic coordinate shift, the margin is mi(θ)=a⟨zi,w⟩+b⟨Szi,w⟩. At a queried sample and parameter, the oracle returns this margin and its exact parameter derivative. The goal is an output θ¯ satisfying mi(θ¯)>0 for every sample and every realization of the algorithm’s randomness.

Equip the feature space Rd with its Euclidean inner product and norm. For coordinates indexed by j=0,…,d−1, define (Sv)j=v(j−1)modd,u=1d(1,…,1). The task is the strict feasibility problem of finding θ∈R2×Rd with positive margins on all n+1 samples. The algorithm receives d,n,g,R,μ,κ; the samples and their geometric decomposition are accessed only through the oracle.

Our assumptions:

Assumption 1 (Parameter regime). The background bounds g,R, contrast μ, and derivative margin κ satisfy 0<g≤R,μ>0,0<κ≤14,(μ4R)2≤κ24096(g4R)8.

Assumption 2 (Clustered sample geometry). There exist background coefficients h0,…,hn∈R, defects v0,…,vn∈Rd, and a center c∈Rd such that, for every i=0,…,n, zi=hi2ν+μvi,g≤|hi|≤R,⟨ν,vi⟩=0,∥vi−c∥≤κ64. The center satisfies ∥c∥≤12,‖c−Sc2‖≥2κ.

A query consists of an index i∈{0,…,n} and any parameter θ=((a,b),w)∈R2×Rd. The exact oracle returns the scalar margin mi(θ) and the direction Gi(θ)=((⟨zi,w⟩,⟨Szi,w⟩),azi+bSzi). After the allotted oracle calls, the output θ¯∈R2×Rd must satisfy mi(θ¯)>0for every i∈{0,…,n}, for every realization of the algorithm’s randomness.

Results

Signed examples Di∈Rd, d>0, satisfy Di=(αi/2)e+μui, 0<g≤|αi|≤R, ⟨e,ui⟩=0, ∥ui−u⋆∥≤κ/64, ∥u⋆∥≤1/2, and ∥(u⋆−Pu⋆)/2∥≥2κ, with 0<κ≤1/4 and 0<μ≤κg4/(4096R3). An exact query returns one example’s margin and its parameter gradient. The target is a deterministic strict separator: w1⟨Di,v⟩+w2⟨PDi,v⟩>0 for every i. The setup imposes no algorithm restriction.

Clustered convolutional separation: ClusteredConvolutionalPerceptron.
Result Oracle complexity Novelty Limitations
(1) ClusteredConvolutionalPerceptronAcceleration (Ours) (review) O(N(R/g)2log⁡(R/μ)) exact margin-and-gradient calls
(2) One-query projection, derived bound (LongTails, n.d.-a) O(1): query ((1,0),0) on D0; return ((1,0),D0−⟨D0,e⟩e). Applies to the same cluster geometry without the small-contrast restriction. (1): No established improvement. (1): larger budget than one call; needs g,R,μ,κ and the small-contrast restriction.
(3) Reference-sample construction (LongTails, n.d.-c) O((R/g)4ℓ2κ2[N+(R/g)ℓ]). Pure reference and derivative-separable defects, under its small-contrast hypotheses. No common instance class; rates not comparable. (1): method-specific analysis removes the reference and directed kick; handles clustered residuals through unmodified cyclic updates. (1): adds a cluster cap; the data classes are not nested.
(4) Two-sample quadratic perceptron (Tyurin 2026), Section 5 Not applicable: dataset (5) contains a pure-background example, excluded by the cluster cap. Rates are not comparable. (1): method-specific scope extends to N interacting clustered residuals; deterministic, noiseless analysis from one fixed start. (1): a κ-dependent start and small contrast; (4) covers almost every start with random perturbations.
(5) Raw or frozen-filter linear perceptron (LongTails, n.d.-b) Ω(1/μ) calls on an explicit growing-rank clustered family (method lower bound). (1): O(Nlog⁡(1/μ)) for fixed R,g,κ contrasts with inverse-contrast linear-perceptron lower bounds; a method-specific comparison, retaining N.

Abbr: N=samples+1; d=dimension; g=lower; R=upper; μ=contrast; κ=derivativeMargin; e=d−1/2(1,…,1); P is the cyclic coordinate shift; u⋆ is the unknown cluster center. ℓ=log⁡(R/μ); log is natural.

LongTails: ClusteredConvolutionalPerceptron. n.d.-a. Repository setup and exact oracle definition. https://github.com/k3nfalt/longtails/blob/main/LongTails/Setups/ClusteredConvolutionalPerceptron.lean.
LongTails: ClusteredPerceptronLowerBound. n.d.-b. Repository method-specific lower-bound statements. https://github.com/k3nfalt/longtails/blob/main/LongTails/Proofs/ClusteredPerceptronLowerBound.lean.
LongTails: ManySampleConvolutionalPerceptronAcceleration. n.d.-c. Repository convergence theorem. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/ManySampleConvolutionalPerceptronAcceleration.lean.
Tyurin, Alexander. 2026. Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration. https://doi.org/10.48550/arXiv.2512.11587.

Lean setup