Kernel Convolutional Perceptron
Descriptions may be stale. Consult the linked Lean sources.
Kernel Convolutional Perceptron
We study strict separation of
Write the data as
Our assumptions:
Assumption 1 (Parameter regime). The integer
parameters satisfy
Assumption 2 (Background and defect geometry).
Define the high-pass operator on
At a query
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
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) KernelConvolutionalPerceptronAcceleration (Ours) (review) | |||
| (2) Fixed high-pass perceptron, derived bound (Kernel-Size-k Convolutional QPA on Many-Sample Data, n.d.) | (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.) | (1): No established improvement in oracle complexity. | (1) pays the extra factor
|
|
| (4) Clustered QPA (LongTails, n.d.) | (1): Removes the residual
cap and |
(1): Worse |
|
| (5) Noisy QPA (Tyurin 2026, Theorem 5.1) | (1): Method-specific
guarantee for |
(1) excludes
(5)’s pure-reference sample ( |
Abbr: