Finite-Scale Convolutional SGD
Descriptions may be stale. Consult the linked Lean sources.
Finite-Scale Convolutional SGD
We seek strict separation of
Index the data by
Our assumptions:
Assumption 1 (Data geometry). The parameters satisfy
Assumption 2 (Finite-scale regime and
initialization). The given initial coefficients satisfy
Assumption 3 (Uniform sampling). The given sampling
source consists of a probability law
At any query
Our formulation is algorithm-specific: we analyze convolutional SGD
with separation scans and periodic restarts. The algorithm chooses a
fixed step size
Before each training call, the algorithm queries all indices in order
At exhaustion of the allotted oracle calls, including exhaustion
during a scan, the output
Results
Signed data
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) FiniteScaleConvolutionalSgd (Ours) (review) | |||
| (2) Fixed-filter perceptron, derived bound (Novikoff 1963) | (1): No established improvement in separation complexity. | (1): Worse polynomial
dependence on |
|
| (3) Cached feasibility, derived bound (Novikoff 1963) | (1): No established improvement in oracle complexity. | (1): More calls and only high-probability separation. (3) counts no offline computation and does not train by SGD. | |
| (4) Raw-input perceptron, derived bound (Novikoff 1963) | (1): Contrast dependence
|
(1): Loses deterministic separation; needs small contrast and tuned initialization. | |
| (5) (Tyurin 2026, Thm. 2.1) | No finite separation-call bound: full-batch GD tends to quadratic-perceptron dynamics as initialization norm tends to infinity. | (1): Finite-time, high-probability analysis of actual joint logistic SGD with finite initialization on the stated class. | (1): Requires derivative separability, nonzero backgrounds and severe small contrast. (5) is a dynamics correspondence, not a competing rate. |
| (6) (Tyurin 2026, Thm. 5.1) | (1): Handles arbitrary
|
(1) excludes (6)’s pure constant reference sample; the dataset classes are not nested. |
Abbr: