Constant Momentum Last Iterate — Momentum SGD for Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Momentum SGD for Convex Minimization · Lean proof
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
Proved result
OracleTemplate.Convergence LongTails.Setups.MomentumLipschitzConvex.spec OracleTemplate.MomentumConvex.budgetRelevant previous results
- A. S. Nemirovskii and D. B. Yudin. Cesari
Convergence of the Gradient Method of Approximating Saddle Points of
Convex-Concave Functions. 1978. Complexity:
fixed stochastic subgradient calls for expected objective gap , using averaged projected iterates on a radius- ball. - Daniela Angela Parletta, Andrea Paudice, and Saverio Salzo. An Improved Analysis of the
Clipped Stochastic subGradient Method under Heavy-Tailed Noise. 2024
preprint; version used: April 2025, v2. Complexity:
fixed stochastic subgradient calls for expected last-iterate objective gap , with moment order , batch size one, base stepsize , and base clipping parameter , for . - Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the Last Iterate of SGD
Information Theoretically Optimal. 2019, COLT; full analysis: May
2019 preprint, v2. Complexity:
fixed stochastic subgradient calls for expected last-iterate objective gap , using projected SGD with epochwise decreasing stepsizes; is the feasible-set diameter.