← All setups

Many Sample Convolutional Perceptron Acceleration — Many-Sample Convolutional Separation

Descriptions may be stale. Consult the linked Lean sources.

Many-Sample Convolutional Separation · Lean proof

Many-Sample Convolutional Separation

We consider strict separation of one positive reference vector and n≥1 negative sample vectors in Rd, where d≥1, using parameters θ=((a,b),w)∈R2×Rd. The score is hθ(x)=a⟨x,w⟩+b⟨Sx,w⟩, where S is the cyclic coordinate shift and ⟨⋅,⋅⟩ is the Euclidean inner product. The reference is constant across coordinates; samples have bounded positive constant backgrounds and small centered defects whose cyclic differences share a separating direction. The oracle returns a selected example’s signed score and parameter direction. The goal is an output with strictly positive reference score and strictly negative scores on all samples, for every realization of algorithm randomness.

Write the data as a reference x0∈Rd and samples x1,…,xn∈Rd. Coordinates are indexed by j=0,…,d−1, with (Sx)j=xj−1modd,u=1d(1,…,1). All inner products and norms on Rd are Euclidean. The algorithm receives d,n,g,R,μ,κ, where g,R bound the background amplitudes, μ scales the defects, and κ is a directional margin. The data and their geometric witnesses are accessed only through the oracle.

Our assumptions:

Assumption 1 (Parameter regime). The dimensions satisfy d,n∈N≥1, and 0<g≤R,μ>0,0<κ≤1. Define ρ=g4R,δ=(μ4R)2,B=⌈8ρ2log⁡1δ⌉++2, where ⌈t⌉+ is the smallest nonnegative integer at least t. These quantities satisfy δ≤e−1,δ(B+1)3≤κ316777216,δ(B+1)2≤κ2ρ416777216.

Assumption 2 (Background and defect geometry). There exist amplitudes c0,c1,…,cn∈R, defects z1,…,zn∈Rd, and a vector v∈Rd such that x0=c02u,g≤c0≤R,xi=ci2u+μzi,g≤ci≤R(1≤i≤n). The defects and common direction satisfy ⟨u,zi⟩=0,∥zi∥≤12(1≤i≤n),∥v∥=1,−⟨zi−Szi2,v⟩≥κ(1≤i≤n).

For oracle access, define signed examples q0=x0 and qi=−xi for 1≤i≤n. A query consists of any index i∈{0,…,n} and any parameter θ=((a,b),w)∈R2×Rd. The oracle returns the exact pair (mi(θ),Gi(θ)), where mi(θ)=a⟨qi,w⟩+b⟨Sqi,w⟩,Gi(θ)=((⟨qi,w⟩,⟨Sqi,w⟩),aqi+bSqi). Initialization is chosen by the algorithm. After the allotted oracle calls, its output θ¯∈R2×Rd must satisfy hθ¯(x0)>0,hθ¯(xi)<0(1≤i≤n), for every realization of the algorithm’s randomness.

Proved result

⌈34359738368⋅(upperlower)4⋅(log⁡(16⋅upper2contrast2))2⋅(samples+1+upperlower⋅log⁡(16⋅upper2contrast2))derivativeMargin2⌉+

OracleTemplate.Convergence LongTails.Setups.ManySampleConvolutionalPerceptron.spec
  OracleTemplate.ManySampleConvolutionalPerceptron.budget

Relevant previous results

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