Gap-Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Gap-Smooth Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and initialization). The
function
Assumption 2 (Gap-dependent upper model). For every
Assumption 3 (Strong-growth stochastic oracle).
There exist a probability measure
After the allotted oracle calls, the algorithm must return a
measurable output
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GapSmoothStrongGrowthHighProbability
(Ours) |
|||
| (2) RCSAG (Lobanov et al. 2026, Thm. 9, v1) |
|
(1): at fixed |
(1) excludes additive/gap
noise, moments below two, and martingale sampling. Near |
| (3) (Dvinskikh et al. 2026, App. I, Thm. 7, v1) |
|
(1): |
|
| (4) Accelerated SGD (Vaswani et al. 2019, Thm. 2) | (1): scope extends to
|
(1) uses batches |
|
| (5) Derived bound: Markov conversion of (Vaswani et al. 2019, Thm. 2) | (1): if |
(1) uses batches |
|
| (6) Derived bound: AGNES + proxBoost (Gupta and Wojtowytsch 2025, Thm. 15, v3)(Davis and Drusvyatskiy 2020, Thm. 7) | (1): for |
(1) uses batches |
Abbr: Costs count individual stochastic-gradient
samples, including batches and trials.