Momentum SGD for Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Momentum SGD for Convex Minimization
We consider minimizing a convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Stochastic subgradient oracle). The
map
Assumption 3 (Initial distance). There exists
Our result is algorithm-specific: we analyze constant-momentum SGD
with a linearly decreasing step-size schedule. The algorithm chooses
Let
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ConstantMomentumLastIterate (Ours) (review) | |||
| (2) Linear-decay SGD (Liu and Zhou 2026, Thm. 3.4) | Finite-dimensional Euclidean specialization: |
(1): Matches known accuracy dependence with log-free constant-EMA last-iterate analysis; no improved problem-class complexity. | (1): Adds |
| (3) FTRL-SGDM (Li et al. 2022, Cor. 1) | On |
(1): Matches known accuracy dependence with constant EMA momentum instead of increasing momentum and shrinking updates; no total-cost improvement. | (1): Needs the horizon; adds momentum-dependent cost and has a worse leading constant. |
| (4) Schedule-Free SGD (Defazio et al. 2024, Thm. 1) | Special case on |
(1): Scope extends to second-moment-bounded oracles without Lipschitz sample losses. Returns the EMA last iterate; (4) certifies its averaged sequence, not its query sequence. | (1): On the shared sample-loss setup, adds momentum-dependent cost and has a worse leading constant. |
Abbr: