← All setups

Derivative Convolutional Perceptron Acceleration — Derivative Convolutional Perceptron Separation

Descriptions may be stale. Consult the linked Lean sources.

Derivative Convolutional Perceptron Separation · Lean proof

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.

Proved result

(samples+1)⋅(⌈2140⋅upper10derivativeMargin8⋅lower10⋅(1+log⁡(uppercontrast))⌉++1)

OracleTemplate.Convergence LongTails.Setups.DerivativeConvolutionalPerceptron.spec
  OracleTemplate.DerivativeConvolutionalPerceptron.budget

Relevant previous results

  • A. Novikoff. On Convergence Proofs for Perceptrons. 1963 proceedings; presented 1962. Complexity: O((samples+1)(1+derivativeMargin−2)) exact sample margin-and-gradient oracle calls for strict separation by cyclic perceptron, including a final verification pass, applied to features (Di−shiftDi)/(2contrast); the proved perceptron update bound is O(r2/γ2) for feature radius r and separating margin γ.