← All setups

Clustered Convolutional Perceptron Acceleration — Clustered Convolutional Separation

Descriptions may be stale. Consult the linked Lean sources.

Clustered Convolutional Separation · Lean proof

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.

Proved result

(samples+1)⋅(⌈128⋅upper2lower2⋅log⁡(16⋅upper2contrast2)⌉++3)

OracleTemplate.Convergence LongTails.Setups.ClusteredConvolutionalPerceptron.spec
  OracleTemplate.ClusteredConvolutionalPerceptron.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.