← All setups

Derivative Convolutional Perceptron Separation

Descriptions may be stale. Consult the linked Lean sources.

Derivative Convolutional Perceptron Separation

We seek to separate samples b0,…,bn∈Rd, where d≥1 and n≥0 are integers, using parameters θ=((a1,a2),w)∈R2×Rd. With S denoting the cyclic coordinate shift, the margin is mi(θ)=a1⟨bi,w⟩+a2⟨Sbi,w⟩. Each sample comprises a bounded, nonzero constant background and a small centered defect; the normalized cyclic differences of the defects share a unit separator with positive margin. The defect scale satisfies a quantitative smallness condition relative to the background bounds and derivative margin. The oracle returns mi(θ) and its parameter derivative at a queried pair (i,θ). The goal is an output θ¯ with mi(θ¯)>0 for every sample and every realization of algorithm randomness.

Equip the feature space Rd with its Euclidean inner product and norm. Index coordinates by j=0,…,d−1, and write (Sv)j=v(j−1)modd,u=1d(1,…,1). The task is strict feasibility of all sample margins in the parameter space R2×Rd. The algorithm receives d,n,g,R,μ,κ, where 0<g≤R,μ>0,0<κ≤1; the samples and their geometric witnesses are accessible only through the oracle.

Our assumptions:

Assumption 1 (Background and derivative separation). There exist scalars c0,…,cn∈R, defects v0,…,vn∈Rd, and a common separator s∈Rd such that ∥s∥=1 and, for every i=0,…,n, bi=ci2u+μvi, g≤|ci|≤R, ⟨u,vi⟩=0,∥vi∥≤12, ⟨vi−Svi2,s⟩≥κ.

Assumption 2 (Contrast scale). The contrast and background scales satisfy μR≤κ202400(gR)24.

At any query (i,θ)∈{0,…,n}×(R2×Rd), the oracle returns the exact scalar margin and derivative direction mi(θ)=a1⟨bi,w⟩+a2⟨Sbi,w⟩, hi(θ)=((⟨bi,w⟩,⟨Sbi,w⟩),a1bi+a2Sbi). Here hi(θ) represents the parameter derivative under the Euclidean coordinate pairing. Initialization is chosen by the algorithm. After the allotted oracle calls, its output θ¯∈R2×Rd must satisfy mi(θ¯)>0for every i=0,…,n, for every realization of its randomness.

Results

Signed samples Di∈Rd, d≥1, satisfy Di=αie/2+μui, g≤|αi|≤R, ⟨e,ui⟩=0, ∥ui∥≤1/2. A unit w satisfies ⟨(ui−Pui)/2,w⟩≥κ for every sample. Assume 0<g≤R, 0<κ≤1, and 0<μ/R≤2−400κ20(g/R)24. One call returns an indexed sample’s exact margin and full parameter gradient. Target: fi(c,v)>0 for every i, deterministically. Algorithms are unrestricted; (1) constructs cyclic simultaneous updates from ((2,0),0).

Strict separation under the DerivativeConvolutionalPerceptron setup.
Result Oracle complexity Novelty Limitations
(1) DerivativeConvolutionalPerceptronAcceleration (Ours) (review) O(Nκ−8(R/g)10[1+log⁡(R/μ)])
(2) Reconstruction, derived bound (Ordinary-Start Convolutional Perceptron Acceleration on Many Samples, n.d.) O(N); recover Di from the head gradient, then separate offline. (1): avoids storing samples and offline separation; no established oracle-complexity improvement. (1): larger bound by κ−8(R/g)10[1+log⁡(R/μ)] throughout its domain.
(3) Fixed difference-filter perceptron, derived bound (Ordinary-Start Convolutional Perceptron Acceleration on Many Samples, n.d.) O(N/κ2), including scans; filter (1,−1)/2, features μ(ui−Pui)/2. (1): new ordinary-start learned-filter trajectory analysis; no established problem-class improvement over (3). (1): larger bound by κ−6(R/g)10[1+log⁡(R/μ)]; (3) needs no contrast threshold or background lower bound.
(4) Frozen raw-filter perceptron (Ordinary-Start Convolutional Perceptron Acceleration on Many Samples, n.d.) Lower bound Ω(1/μ) on the growing-rank family, for every positive constant step and zero head. (1): method-specific gain when Nκ−8(R/g)10[1+log⁡(R/μ)]=o(1/μ). For N=2m, fixed geometry and μ≍(m+1)−2: O(mlog⁡(2m)) versus Ω(m2).
(5) (Tyurin 2026), Theorem 5.1 O(dνA[1+log⁡(dA/ν)]) indexed calls; success probability 1−ρ. Only dataset (5), 0<ν≤1/10, nonzero initial correlation, prescribed perturbations. (1): deterministic ordinary start and arbitrary sample count on a different derivative-separable class. Rates are incomparable; (5) includes a pure-constant sample excluded by (1). (1) does not cover (5)’s dataset; requires nonzero backgrounds and the stated strong contrast condition.

Abbr: N=samples+1; g,R,μ,κ are the setup’s lower, upper, contrast and derivative-margin parameters; e=d−1/21; P is the cyclic shift; fi(c,v)=c0⟨Di,v⟩+c1⟨PDi,v⟩. In (5), ν is that paper’s contrast, ρ∈(0,1) is failure probability, q=∥θ0∥2/⟨θ0,vν,+⟩2, and A=[1+log⁡(q/ρ3)][1+log⁡(dq/ν)]; vν,+ is its unit positive contrast eigendirection. In (4), m indexes the companion note’s growing-rank family.

Ordinary-Start Convolutional Perceptron Acceleration on Many Samples. n.d. LongTails companion note. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/DerivativeConvolutionalPerceptronAcceleration.md.
Tyurin, Alexander. 2026. Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration. https://doi.org/10.48550/arXiv.2512.11587.

Lean setup