Source-linked AI summary
Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
Aymeric Dieuleveut, Alain Durmus, Francis Bach
TL;DR
The paper studies constant-step-size SGD, which is practical but generally does not converge to the global optimum. It uses Markov-chain tools to analyze its behavior and shows that Richardson-Romberg extrapolation produces estimates closer to the optimum, with a slight variance increase.
Problem
Constant-step-size SGD is practical and quickly forgets initial conditions, but generally does not converge to the global optimum.
Method
The analysis interprets constant-step-size SGD as a Markov chain and derives step-size expansions for averaged iterates using Markov-chain tools.
Results
Richardson-Romberg extrapolation improves convergence by a factor of γ, producing estimates closer to θ∗ at the expense of a slight increase in variance.
Takeaways & Limitations
Extrapolating averaged SGD iterates can mitigate the constant-step-size method’s distance from the optimum.
Takeaways & Limitations
The stated assumptions exclude some un-bounded observation settings, although Assumption A4 can be weakened; Gaussian inputs typically do not satisfy it.
Abstract
from arXiv · showhide
We consider the minimization of an objective function given access to unbiased estimates of its gradient through stochastic gradient descent (SGD) with constant step-size. While the detailed analysis was only performed for quadratic functions, we provide an explicit asymptotic expansion of the moments of the averaged SGD iterates that outlines the dependence on initial conditions, the effect of noise and the step-size, as well as the lack of convergence in the general (non-quadratic) case. For this analysis, we bring tools from Markov chain theory into the analysis of stochastic gradient. We then show that Richardson-Romberg extrapolation may be used to get closer to the global optimum and we show empirical improvements of the new extrapolation scheme.
1 Introduction
The paper analyzes constant-step-size SGD through Markov-chain tools, characterizing its stationary behavior, bias, variance, and lack of general convergence. It then uses Richardson-Romberg extrapolation to reduce the step-size bias and reports empirical improvements.
- Motivation: Constant-step-size SGD is often practical because it uses one parameter and forgets initial conditions exponentially fast on well-conditioned problems, despite not generally reaching the global optimum.Its practical performance may remain sufficient when small prediction errors do not matter.
- Markov-chain interpretation: The SGD iterates form a homogeneous Markov chain that converges exponentially to a unique stationary distribution, so iterates oscillate around its mean rather than converge to a point.The average magnitude of non-averaged oscillations is γ1/2.
- Bias and convergence: For quadratic objectives, the stationary mean equals the optimum, whereas for general objectives its deviation from the optimum is O(γ), preventing convergence with constant step-size.This separates the convergent quadratic case from the general non-quadratic setting.
- Main analysis: The paper derives an explicit step-size expansion and a quantitative central-limit bound that separate initial-condition bias from noise-driven variance.The bias is proportional to N(θ0−θ∗), while the variance increases with the covariance of the gradient noise and is independent of the starting point.
- Extrapolation: Richardson-Romberg extrapolation combines averages from step-sizes γ and 2γ to obtain an estimate closer to θ∗ by a factor γ.The method exploits the step-size expansion to cancel the leading bias, with a slight variance increase.
- Contributions: The paper adapts diffusion-discretization analysis tools to SGD and reports empirical improvements from the extrapolation schemes.The empirical study is presented as evidence that the new schemes improve performance.
2 Main results
The paper analyzes constant-step-size SGD through its Markov-chain structure under strongly convex, smooth objectives and explicit noise assumptions. It derives stationary-distribution and averaged-iterate results, then uses a step-size expansion to motivate Richardson-Romberg extrapolation.
- Assumptions and Markov-chain formulation: Under strongly convexity, smoothness, regularity, and unbiased i.i.d. noise assumptions, the SGD recursion defines a Markov chain with a stationary distribution.The analysis assumes a strongly convex objective with bounded derivatives and regular covariance structure, alongside measurable, conditionally unbiased i.i.d. noise.
- Assumptions and Markov-chain formulation: The Markov chain converges to a probability measure πγ with finite second moment, characterizing constant-step-size SGD's long-run behavior.The stationary distribution depends on the step size and replaces convergence to a single point in the general constant-step-size setting.
- Main asymptotic results: For sufficiently small γ, the stationary mean satisfies ¯θγ = θ∗ + γ∆ + O(γ2), providing an explicit step-size expansion of the optimization error.The expansion is established under suitable conditions on the objective and noise and is also summarized through a bound with a constant independent of γ.
- Richardson-Romberg extrapolation: Richardson-Romberg extrapolation combines averaged SGD runs with step sizes γ and 2γ to cancel the leading error and improve proximity to θ∗.The extrapolated estimate requires two parallel SGD recursions and incurs a slight variance increase while improving convergence by a factor of γ.
- Main asymptotic results: The averaged iterates satisfy a quantitative central-limit bound whose constants separate initialization-dependent bias from noise-dependent variance.The bias decreases as initial conditions are forgotten, while the variance increases with the covariance of the gradient noise.
3 Detailed analysis
The paper models constant-step-size SGD as a Markov chain, characterizes its stationary behavior and averaged-iterate moments, and explains how bias, variance, initialization, noise, and step size shape convergence.
- Markov-chain formulation: For γ ∈ (0, 2/L), SGD admits a unique stationary distribution πγ and converges to it in Wasserstein distance.
- Step-size expansion: The asymptotic expansion ¯θγ = θ∗ + γ∆ + O(γ2) makes the leading step-size bias explicit and motivates Richardson-Romberg extrapolation.The expansion is established under the paper’s regularity and moment assumptions.
- Stationary behavior: The stationary mean satisfies ¯θγ = θ∗ for quadratic objectives, but differs from θ∗ by O(γ) in the general case.For non-quadratic functions, the deviation is the source of constant-step-size non-convergence.
- Scope of analysis: For general objectives, only a first-order expansion in γ is obtained, whereas the quadratic case permits exact asymptotic bias and variance formulas.The general case cannot generally compute the relevant Poisson solutions exactly or prove the same small-γ development.
- Moment expansions: Averaged-iterate error separates into a variance term scaling as 1/k, a bias term scaling as 1/k2, and a non-positive residual term scaling as 1/k2.The variance depends on the stationary distribution rather than the initial point, while the bias depends on θ0.
4 Experiments
Synthetic logistic-regression experiments compare constant and decaying step sizes, averaging, Richardson-Romberg extrapolation, and online Newton methods across dimensions and step-size configurations.
- Experimental setup: The experiments evaluate averaged and non-averaged constant-step-size SGD at 1/R2, 1/2R2, and 1/4R2 alongside the extrapolated methods.
- Experimental comparison: Richardson-Romberg iterates saturate at a much lower level and perform better than decaying step-sizes proportional to 1/√n.The experiments use n = 10^7 observations with d = 12 and d = 4.
- Experimental comparison: The observed convergence-limit ratios are roughly 2 for un-averaged sequences and 4 for averaged sequences, confirming the predicted limits.
5 Conclusion
The paper uses Markov-chain tools to analyze constant-step-size SGD beyond least-squares, revealing how initialization, noise, and step size affect convergence and motivating Richardson-Romberg improvements.
- Conclusions: Markov-chain analysis extends results known for least-squares to all loss functions considered under the paper’s assumptions.
- Conclusions: Richardson-Romberg extrapolation provably improves the convergence behavior of averaged SGD iterates.
- Future work: Future work includes applying the Richardson-Romberg trick to decreasing step sizes and extending the results under self-concordance.
6 Postponed proofs
The proofs discuss alternative noise assumptions, emphasizing that weaker moment conditions cover important regression settings while semi-stochastic independence is substantially stronger.
- Assumption A4 can be weakened to accommodate unbounded observations, although Gaussian inputs typically do not satisfy the stated version.
- The analysis also considers semi-stochastic noise independent of θ or noise with a uniformly bounded fourth-order moment.
- Assumption A7(p), p ≥2, is the weakest condition and covers random design least squares and logistic regression with bounded fourth-moment inputs.
- The i.i.d. random-field assumption alone does not imply A8; semi-stochastic noise functions being i.i.d. vectors is a very strong assumption that implies A8.
6.2 Preliminary results
The preliminary results establish regularity, moment, and ergodic properties for the constant-step-size SGD Markov chain, including bounds and small-step-size conditions.
- For Lipschitz test functions, the Poisson-equation solution ψγ is well-defined and satisfies (Id − Rγ)ψγ = φ and πγ(ψγ) = 0.
- The preliminary lemmas control local Lipschitz observables and propagation from arbitrary initial points under suitable moment assumptions.
- Under A8, the maximal admissible step-size differs from the stochastic-noise case, highlighting a distinct behavior for semi-stochastic noise.
- Moment bounds hold under A1-A4(2p) when γ ∈(0, 1/(LCp)), with constants depending only on p.
- The stationary mean-squared distance satisfies ∫Rd ∥θ − θ∗∥2πγ(dθ) = O(γ), implying ∥¯θγ − θ∗∥2 = O(γ).
6.3 Proof of Proposition 3
The proof of Proposition 3 uses stationarity and independence to characterize the relevant second-moment operator and establish its invertibility for sufficiently small step-size.
- For γ < 2L^-1, the operator Σ ⊗ Id + Id ⊗ Σ − γΣ ⊗ Σ is symmetric positive definite and therefore invertible.
- The proposition is then specialized to least-squares regression, where f is quadratic and Σ = E[XX⊤].
6.4 Proof of Theorem 4
The proof of Theorem 4 obtains higher-order stationary expansions through Taylor expansions, moment bounds, and invertibility of tensorized Hessian operators.
- The gradient is expanded as f′(θ) = f′′(θ∗)(θ − θ∗) + (1/2)f′′′(θ∗)(θ − θ∗)⊗2 + R1(θ).
- Invertibility follows from positive definiteness of the tensorized Hessian operator when γ < 2L^-1.
- A fourth-order Taylor expansion around θ∗ is used to reduce the residual in the second-moment expansion to order O(γ2).
- The stationary second moment has the expansion ∫Rd(θ − θ∗)⊗2πγ(dθ) = □γ + △γ2 + o(γ2).
- The proof combines the expansions and moment estimates to establish the theorem's higher-order results.
6.5 Proof of Theorem 5
The proof establishes Theorem 5 through a general Lipschitz-function result using Poisson equations and geometric decay under a step-size restriction.
- Specialization: Theorem 5 follows by applying the general result with ϕ(θ) = θ − θ∗ and combining the resulting identity with equation (58).The proof concludes after the specialization and combination step.
- General result: Theorem 20 applies to Lipschitz functions under assumptions A1–A4(4) and γ ∈ (0, 1/(2L)).It defines ρ = (1 − 2µγ(1 − γL))^1/2 for controlling decay.
- Poisson-equation tools: Poisson solutions associated with ϕ, ψγ, and ψ⊗2 provide the auxiliary functions used in the analysis.The proof invokes their existence, regularity, and centering under the stationary distribution.
- Geometric decay: The transient contribution γψγ(θ0) decays geometrically as O(ρ^k), and the proof uses this decay to control averaged iterates.The construction introduces Φk as an average while bounding the initial-condition term.
6.6 Proof of Corollary 6
The proof of Corollary 6 specializes Theorem 5 to the quadratic LMS setting and evaluates the resulting moment expansion through linear recursions and matrix identities.
- Quadratic specialization: The quadratic specialization uses the LMS algorithm and represents the iterates in a form suitable for explicit calculation.The proof applies Theorem 5 to the linear function ϕ(θ) = θ − θ∗, for which Φk equals the averaged error.
- Moment evaluation: The stationary expectation of ϕ(θ)⊗2 is supplied by Proposition 3 and enters the bound obtained from Theorem 5.This provides the second-moment quantity needed for the corollary.
- Asymptotic terms: The expansion separates terms proportional to 1/k and 1/k2, with the latter requiring a Poisson equation for ϕ(θ)⊗2.The 1/k2 contribution is decomposed into three terms.
- Linear-algebra calculations: The proof simplifies the remaining calculations using an arithmetico-geometric recursion and explicit tensor-operator identities.The operator Σ ⊗ Id + Id ⊗ Σ − γT is shown positive and invertible on symmetric matrices under γ ≤ 1/r2.
- Conclusion: Combining equations (63), (64), and (65) completes the proof of Corollary 6.The preceding calculations supply the components of the stated expansion.
6.7 Proof of Theorem 7
The proof of Theorem 7 develops regularity and decay properties for the gradient-flow Poisson equation, then combines them with stochastic-gradient estimates and Taylor expansion.
- Derivative regularity: Higher-order flow derivatives satisfy ordinary differential equations, with explicit eigenbasis expressions available for third-order behavior.The eigenvectors and eigenvalues are those of f′′(θ∗).
- Gradient-flow estimates: The gradient flow contracts toward θ∗ according to ∥ϕt(θ) − θ∗∥2 ≤ e^−2µt∥θ − θ∗∥2.The flow and its derivatives are analyzed under assumptions A1 and A9(ℓ).
- Poisson solutions: Continuous Poisson solutions hg are well-defined and inherit smoothness under the stated regularity and growth assumptions.Theorem 23 establishes derivative bounds and hg ∈ Cℓ(Rd).
- Poisson-solution derivatives: For the identity function, the Poisson solution satisfies ∇hId(θ∗) = (f′′(θ∗))−1 when ℓ ≥ 2.This links the continuous Poisson equation to the inverse Hessian at the optimum.
- Stochastic-gradient analysis: The stochastic-gradient proof uses moment estimates, Taylor expansion, and assumptions on gradient and noise moments to establish Theorem 7.The Markov chain is generated by recursion (1), with γ restricted by a constant depending on the moment order.