← All setups

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 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⋆)]≤ε.

Proved result

⌈100⋅G2⋅R2ε2⌉++⌈4⋅(β1−β)2⋅(1+−log⁡(1−β))⌉+

OracleTemplate.Convergence LongTails.Setups.MomentumLipschitzConvex.spec OracleTemplate.MomentumConvex.budget

Relevant previous results