← All setups

Finite-Scale Convolutional SGD

Descriptions may be stale. Consult the linked Lean sources.

Finite-Scale Convolutional SGD

We seek strict separation of n≥1 vectors bi∈Rd, where d≥1, using parameters θ=(a1,a2,w)∈R2×Rd and margins mi(θ)=a1⟨bi,w⟩+a2⟨Sbi,w⟩, where S is the cyclic coordinate shift. The data have bounded, nonzero backgrounds and small centered defects with a common positive derivative margin. The oracle returns mi(θ) and its parameter gradient. We analyze SGD with independent uniform sample indices, exhaustive separation scans, and periodic restarts from a scaled initialization. For β∈(0,1), the goal is an output θ¯ with P{minimi(θ¯)≤0}≤β, where P is the law of the algorithm’s randomness.

Index the data by i∈{0,…,n−1} and the coordinates by j∈{0,…,d−1}. Write (Sv)j=vj−1modd and e=d−1/2(1,…,1). Inner products and norms on the feature space are Euclidean. The task is to find a parameter vector satisfying min0≤i<nmi(θ)>0. The algorithm receives d,n, background bounds g,R, contrast μ, derivative margin κ, initial coefficients p0,q0, an initial readout w0∈Rd, and the sampling source specified below. The failure tolerance β may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Data geometry). The parameters satisfy 0<g≤R, μ>0, and 0<κ≤1/4. There exist scalars ci, defects vi∈Rd, and a vector u∈Rd such that, for every i, bi=ci2e+μvi,g≤|ci|≤R,⟨e,vi⟩=0,∥vi∥≤12,∥u∥=1,⟨u,vi−Svi2⟩≥κ.

Assumption 2 (Finite-scale regime and initialization). The given initial coefficients satisfy |p0|≤1,1≤q0≤32. Define the auxiliary quantities h=κ1000R,δ=(hμ)2,ρ=hg. They satisfy δ≤1,δ(log⁡24δ)2≤κ3ρ41022n3.

Assumption 3 (Uniform sampling). The given sampling source consists of a probability law Q on a measurable space Ω and measurable maps It:Ω→{0,…,n−1}, t≥0. Under ω∼Q, the variables It(ω) are mutually independent and each is uniform on {0,…,n−1}.

At any query (i,θ), the oracle returns the exact pair (mi(θ),Gi(θ)), where Gi(θ)=(⟨bi,w⟩,⟨Sbi,w⟩,a1bi+a2Sbi). Thus Gi is the coordinate gradient of the margin. Each queried pair counts as one oracle call, including calls used to scan the data or at restart steps.

Our formulation is algorithm-specific: we analyze convolutional SGD with separation scans and periodic restarts. The algorithm chooses a fixed step size η>0, a scale s>0, and a restart period T∈{1,2,…} from its available inputs. The auxiliary quantity h above does not prescribe η. Define θ0=(s(p0+q0)2,s(p0−q0)2,w0). The algorithm starts at θ0 with training counter t=0 and draws its sampling source with law Q. Any additional algorithm randomness must preserve this sampling law.

Before each training call, the algorithm queries all indices in order 0,…,n−1 at its current point θt, without changing that point during the scan. If every scanned margin is strictly positive, it freezes the point permanently. Otherwise it queries (It,θt) and sets θt+1={θ0,T∣(t+1),θt+η1+exp⁡(mIt(θt))GIt(θt),T∤(t+1). It then increments t and begins a new complete scan. In particular, a restart consumes the sampled oracle call even though its reply is discarded. Each completed scan followed by a training call uses n+1 calls. Once frozen, any remaining calls repeat the query at index n−1 at the frozen point and leave the point unchanged.

At exhaustion of the allotted oracle calls, including exhaustion during a scan, the output θ¯ is the current point. The required accuracy is strict separation with failure probability at most β: P{min0≤i<nmi(θ¯)≤0}≤β.

Results

Signed data bi=αie/2+μui∈Rd, N,d≥1, satisfy 0<g≤|αi|≤R, ui⊥e, ∥ui∥≤1/2, and ⟨s,(ui−Pui)/2⟩≥κ for a unit s, with 0<κ≤1/4, μ>0. Put η=κ/(1000R), δ=(ημ)2, ρ=ηg; require δ≤1 and δlog2⁡(24/δ)≤κ3ρ4/(1022N3). The prescribed family jointly trains a two-tap filter and readout by logistic SGD with IID uniform indices, full validation scans, periodic restarts and freezing upon separation. Initial filter coordinates are a positive scale times (a0+t0,a0−t0)/2, |a0|≤1, 1≤t0≤3/2; the initial readout is arbitrary. Target: all signed margins positive with probability at least 1−q, 0<q<1. One oracle call returns one sample’s exact margin and parameter gradient.

Finite-scale convolutional SGD: FiniteScaleConvolutionalSgd.
Result Oracle complexity Novelty Limitations
(1) FiniteScaleConvolutionalSgd (Ours) (review) O(N3(R/g)2κ−3ℓ(1+log⁡(1/q))), including scans and restarts.
(2) Fixed-filter perceptron, derived bound (Novikoff 1963) O(N(1+κ−2)); deterministic. Fix h=(1,−1)/2 and scan cyclically. (1): No established improvement in separation complexity. (1): Worse polynomial dependence on N,R/g,κ−1; probabilistic guarantee; requires small contrast, nonzero backgrounds and large tuned initialization.
(3) Cached feasibility, derived bound (Novikoff 1963) O(N) calls at h=(1,0),v=0 recover all data; solve difference-feature feasibility offline, deterministically. (1): No established improvement in oracle complexity. (1): More calls and only high-probability separation. (3) counts no offline computation and does not train by SGD.
(4) Raw-input perceptron, derived bound (Novikoff 1963) O(N(1+R2/(μ2κ2))); deterministic on the common class, using raw margin μκ/2 and norm bound R. (1): Contrast dependence ℓ instead of μ−2. At fixed N,R,g,κ,q, sufficiently small admissible μ improves this upper bound; no lower bound for linear methods. (1): Loses deterministic separation; needs small contrast and tuned initialization.
(5) (Tyurin 2026, Thm. 2.1) No finite separation-call bound: full-batch GD tends to quadratic-perceptron dynamics as initialization norm tends to infinity. (1): Finite-time, high-probability analysis of actual joint logistic SGD with finite initialization on the stated class. (1): Requires derivative separability, nonzero backgrounds and severe small contrast. (5) is a dynamics correspondence, not a competing rate.
(6) (Tyurin 2026, Thm. 5.1) O((d/ν)A[1+log⁡((d/ν)A)]) noisy quadratic-perceptron steps; two fixed samples, 0<ν≤0.1, tuned noise, nonzero initial signal. (1): Handles arbitrary N and conflicting derivative directions with actual logistic SGD, rather than a two-sample surrogate. Rates are not comparable. (1) excludes (6)’s pure constant reference sample; the dataset classes are not nested.

Abbr: e is the unit constant vector; P is cyclic shift; g,R bound background magnitudes; μ is contrast; κ is derivative-feature margin; q is failure probability; ℓ=1+log+⁡(R/(κμ)), log+⁡x=max{0,log⁡x}. In (6), signed samples are 1 and −(1+νe1); ν is that paper’s contrast, C=∥θ0∥2/|⟨θ0,vν,+⟩|2, and A=(1+log⁡(C/q3))(1+log⁡(dC/ν)); vν,+ is its positive signal eigenvector. Each step checks at most two sample margins/gradients.

Novikoff, Albert B. J. 1963. “On Convergence Proofs for Perceptrons.” Proceedings of the Symposium on the Mathematical Theory of Automata (Brooklyn, New York) 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