← All setups

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 f:E→R on a separable real Hilbert space E. A given point x0∈E lies within distance R≥0 of a global minimizer x⋆. At x, the oracle returns g(ξ,x)∈E using a fresh independent sample ξ from a probability law ν on a measurable space Ξ. The map g is jointly measurable, its mean is a subgradient of f, and Eξ∼ν∥g(ξ,x)∥2≤G2, where G>0. For ε>0, constant-momentum SGD must return a last iterate x¯ with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε under the sampling law.

The optimization problem is minx∈Ef(x). The norm is induced by the inner product on E. The algorithm receives E, the measurable sample space Ξ, G, R, a momentum parameter β∈[0,1), ε, and x0; the objective, oracle map, and sampling law are accessed through oracle replies.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Stochastic subgradient oracle). The map g:Ξ×E→E is jointly measurable. For every x∈E, the random variable ∥g(ξ,x)∥2 is integrable under ν, and Eξ∼ν[∥g(ξ,x)∥2]≤G2. Writing h(x)=Eξ∼ν[g(ξ,x)] for the Bochner mean, we require f(x)+⟨h(x),y−x⟩≤f(y),x,y∈E. Successive calls use independent samples ξ0,ξ1,… with common law ν, and queries may be made anywhere in E.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Our result is algorithm-specific: we analyze constant-momentum SGD with a linearly decreasing step-size schedule. The algorithm chooses γ∈R and N∈{0,1,2,…} from its inputs and initializes m0=0. At iteration k≥0, it queries the oracle at xk and updates gk=g(ξk,xk),mk+1=βmk+(1−β)gk,ηk=γ(N+1−k+β1−β),xk+1=xk−ηkmk+1. After T∈{0,1,2,…} oracle calls, the output is the last iterate x¯=xT. The schedule parameter N and the call budget T are separate quantities.

Let P=ν⊗N be the joint law of the samples. The required objective gap is integrable under P and satisfies EP[f(x¯)−f(x⋆)]≤ε.

Results

Convex f:E→R on a separable real Hilbert space with its Borel measurable structure; a minimizer x⋆ satisfies ∥x0−x⋆∥≤R. The jointly measurable oracle g(ξ,x) has ∫g(ξ,x)dp(ξ)∈∂f(x) and integrable squared norm with ∫∥g(ξ,x)∥2dp(ξ)≤G2 for every x. Samples are IID from the probability law p. Here G>0, R≥0, 0≤β<1, and ε>0. The setup restricts algorithms to constant-β EMA momentum SGD. Result (1) uses zero initial momentum and horizon-dependent affine step decay, tuned with G,R,β,ε, and returns xN with ∫[f(xN)−f(x⋆)]dP≤ε, where P=p⊗N.

Constant-momentum last-iterate guarantees for MomentumLipschitzConvex.
Result Oracle complexity Novelty Limitations
(1) ConstantMomentumLastIterate (Ours) (review) O(1+G2R2ε2+κ2log⁡e1−β)
(2) Linear-decay SGD (Liu and Zhou 2026, Thm. 3.4)

O(1+G2R2ε2)

Finite-dimensional Euclidean specialization: L=0, M=2G, σ≤G, no composite term or constraints.

(1): Matches known accuracy dependence with log-free constant-EMA last-iterate analysis; no improved problem-class complexity. (1): Adds κ2loge1−β cost. Covers only unconstrained objectives; (2) also permits composite terms, constraints, and general norms.
(3) FTRL-SGDM (Li et al. 2022, Cor. 1)

O(1+G2R2ε2)

On Rd, second-moment assumption H3; c=R, anytime choice γt−1=R/(Gt).

(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)

O(1+G2R2ε2)

Special case on Rd: convex G-Lipschitz sample losses; constant interpolation parameter in [0,1]; horizon-tuned step.

(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: κ=β/(1−β); N is the number of oracle calls; all costs count individual stochastic subgradient calls for expected objective gap ε. EMA: exponential moving average; FTRL: follow the regularized leader; SGD(M): stochastic gradient descent (with momentum). In (2), L,M are smoothness/Lipschitz parameters and σ bounds noise standard deviation; in (3), c,γt−1 are tuning parameters and t is the iteration index.

Defazio, Aaron, Xingyu Alice Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, and Ashok Cutkosky. 2024. The Road Less Scheduled. https://doi.org/10.48550/arXiv.2405.15682.
Li, Xiaoyu, Mingrui Liu, and Francesco Orabona. 2022. “On the Last Iterate Convergence of Momentum Methods.” In Proceedings of the 33rd International Conference on Algorithmic Learning Theory, edited by Sanjoy Dasgupta and Nika Haghtalab, vol. 167. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v167/li22a.html.
Liu, Zijian, and Zhengyuan Zhou. 2026. Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. https://arxiv.org/abs/2312.08531v4.

Lean setup