← All setups

Kernel Convolutional Perceptron

Descriptions may be stale. Consult the linked Lean sources.

Kernel Convolutional Perceptron

We study strict separation of n+1 vectors in Rd by a kernel convolutional perceptron with parameters (c,w)∈Rk×Rd, where d≥1, k≥2, and n≥0 are integers. Each vector consists of a nonzero constant background and a small centered defect; normalized high-pass defects share a unit separator with positive margin. The parameters satisfy a quantitative small-contrast condition. The oracle returns a sample’s bilinear convolutional margin and its update direction. Starting from the identity filter and zero readout, the method cycles through samples with a fixed positive step size. The goal is strictly positive margins on every sample, for every realization.

Write the data as b0,…,bn∈Rd. Inner products and norms on each factor are Euclidean. Let S be the cyclic shift defined by (Su)ℓ=u(ℓ−1)modd for 0≤ℓ<d, and set a=d−1/2(1,…,1). For c∈Rk, b,w∈Rd, define the response and margin by Ccb=∑j=0k−1cjSjb,mi(c,w)=⟨Ccbi,w⟩. The task is to find parameters for which all these margins are strictly positive. The algorithm receives d,k,n and the scalars g,R,μ,κ specified below; the data are accessed through the oracle.

Our assumptions:

Assumption 1 (Parameter regime). The integer parameters satisfy d≥1, k≥2, and n≥0. The real parameters satisfy 0<g≤R,0<μ≤R,0<κ≤1, and μ2(Rg)4[log⁡(128kR2(κμ)2)]2≤kκ6R21013.

Assumption 2 (Background and defect geometry). Define the high-pass operator on Rd by Hku=11−1/k(u−1k∑j=0k−1Sju). There exist background coefficients β0,…,βn∈R, defects u0,…,un∈Rd, and a separator v∈Rd with ∥v∥=1 such that, for every 0≤i≤n, bi=βi2a+μui,g≤|βi|≤R,⟨a,ui⟩=0,∥ui∥≤1k,⟨v,Hkui⟩≥κ.

At a query (i,(c,w))∈{0,…,n}×(Rk×Rd), the oracle returns exactly (mi(c,w),Gi(c,w)), where Gi(c,w)=((⟨Sjbi,w⟩)j=0k−1,Ccbi).

Our formulation is algorithm-specific: we analyze the kernel convolutional perceptron with cyclic sample selection and simultaneous updates of the filter and readout. The algorithm chooses a fixed step size η>0 from its inputs and initializes θ0=(c0,w0)=(e0,0),i0=0, where e0=(1,0,…,0)∈Rk. At each iteration it queries (it,θt) and applies θt+1={θt+ηGit(θt),mit(θt)≤0,θt,mit(θt)>0,it+1=(it+1)mod(n+1). The sample cursor advances after every query, including queries that leave the parameters unchanged. After T oracle calls, the output is the current pair θ¯=(c¯,w¯)=θT. Its required accuracy is exact strict separation: mi(c¯,w¯)>0for every i∈{0,…,n}, for every realization of any algorithmic randomness.

Results

N≥1 samples Di=(αi/2)e+μui∈Rd, d>0, k≥2, 0<g≤|αi|≤R, 0<μ≤R, ui⊥e, ∥ui∥≤k−1/2. A unit w satisfies ⟨w,Hkui⟩≥κ, 0<κ≤1. Require μ2(R/g)4log2⁡(128kR2/(κμ)2)≤kκ6R2/1013. The oracle gives one exact sample margin and gradient. The setup requires cyclic QPA, identity filter and zero readout initialization, positive constant step, and updates only at nonpositive margins. Target: deterministic strict separation ⟨∑j<kcjPjDi,v⟩>0 for every sample at the returned iterate.

Kernel convolutional perceptron: KernelConvolutionalPerceptron.
Result Oracle complexity Novelty Limitations
(1) KernelConvolutionalPerceptronAcceleration (Ours) (review) O(N(R/g)2κ−3log⁡kRκμ); η=κ/(16k/2R).
(2) Fixed high-pass perceptron, derived bound (Kernel-Size-k Convolutional QPA on Many-Sample Data, n.d.) O(N(1+(kκ2)−1)), same sample oracle; readout-only updates. (1): No established improvement in separation complexity. (1) costs more throughout its admissible regime; (2) has no contrast dependence or small-contrast restriction.
(3) Data recovery and offline LP, derived bound (Kernel-Size-k Convolutional QPA on Many-Sample Data, n.d.) O(N) sample calls; offline computation excluded. (1): No established improvement in oracle complexity. (1) pays the extra factor (R/g)2κ−3log⁡(kR/(κμ)).
(4) Clustered QPA (LongTails, n.d.) O(N(R/g)2[1+log⁡(R/μ)]); k=2, ∥ui−u⋆∥≤κ/64. (1): Removes the residual cap and κ-dependent initialization; covers arbitrary kernel sizes and unaligned, negatively correlated, growing-rank residuals. (1): Worse κ−3 dependence and leading constant on the overlap; stricter contrast condition; step still needs κ.
(5) Noisy QPA (Tyurin 2026, Theorem 5.1) O(dνA[1+log⁡(dA/ν)]); probability 1−ρ; k=N=2, dataset (5), 0<ν≤1/10. (1): Method-specific guarantee for k>2, arbitrary N, identity start without noise, deterministic separation. Classes are incomparable; no rate comparison. (1) excludes (5)’s pure-reference sample (κ=0); requires positive residual margin for every sample.

Abbr: e=d−1/21; P is the cyclic shift; Hk=(1−1/k)−1/2(I−k−1∑j<kPj); QPA: quadratic perceptron algorithm; LP: linear program. In (5), ν is the unnormalized defect amplitude, ρ∈(0,1), q=∥θ0∥2/|⟨θ0,vν,+⟩|2<∞, vν,+ is the positive defect eigenvector, and A=(1+log⁡(q/ρ3))(1+log⁡(dq/ν)); the step and injected noise are tuned as in Theorem 5.1.

Kernel-Size-k Convolutional QPA on Many-Sample Data: Novelty Assessment. n.d. LongTails repository, reduction check. https://github.com/k3nfalt/longtails/blob/main/scripts/reviews/KernelConvolutionalPerceptronAcceleration.md.
LongTails: ClusteredConvolutionalPerceptronAcceleration. n.d. Repository convergence theorem and budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/ClusteredConvolutionalPerceptronAcceleration.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