Source-linked AI summary
An Improved Analysis of Stochastic Gradient Descent with Momentum
Yanli Liu, Yuan Gao, Wotao Yin
TL;DR
The paper studies why SGDM performs competitively despite limited theory for practical smooth objectives and dynamic schedules. It develops convergence analyses for fixed and multistage SGDM, showing SGD-matching rates and a benefit from stagewise training, while leaving faster special-case rates and better parameter choices open.
Problem
Existing SGDM analyses either give weaker convergence bounds than SGD, use restrictive objectives or assumptions, or do not address dynamic stagewise parameters.
Method
The paper analyzes SGDM with a Lyapunov function and auxiliary sequence that control momentum deviation and exploit reduced variance, then extends them to stagewise parameters.
Results
SGDM achieves the same convergence bound as SGD for smooth nonconvex and strongly convex objectives, while Multistage SGDM has a convergence guarantee and faster initial stages.
Takeaways & Limitations
Stagewise SGDM can combine larger early stepsizes for initial performance with smaller final stepsizes that reduce stationary-distribution size.
Takeaways & Limitations
Open questions include whether SGDM can be shown faster than SGD for special objectives and whether more efficient parameter choices exist.
Abstract
from arXiv · showhide
SGD with momentum (SGDM) has been widely applied in many machine learning tasks, and it is often applied with dynamic stepsizes and momentum weights tuned in a stagewise manner. Despite of its empirical advantage over SGD, the role of momentum is still unclear in general since previous analyses on SGDM either provide worse convergence bounds than those of SGD, or assume Lipschitz or quadratic objectives, which fail to hold in practice. Furthermore, the role of dynamic parameters has not been addressed. In this work, we show that SGDM converges as fast as SGD for smooth objectives under both strongly convex and nonconvex settings. We also establish \textit{the first} convergence guarantee for the multistage setting, and show that the multistage strategy is beneficial for SGDM compared to using fixed parameters. Finally, we verify these theoretical claims by numerical experiments.
1 Introduction
The paper addresses limited theoretical understanding of SGDM, especially under practical smooth objectives and stagewise parameter schedules, by analyzing fixed and multistage momentum methods.
- Motivation: Prior SGDM analyses mainly assume restrictive objectives or settings, provide weaker bounds than SGD, or omit dynamic parameter schedules.Examples include least-square objectives, local convergence, uniformly bounded gradients, and asymptotic results requiring momentum weights to approach 0 or 1.
- Motivation: SGDM is widely used for neural-network training, often with constant-and-drop stepsizes and fixed or increasing momentum weights.This stagewise strategy is called Multistage SGDM.
- Contributions: The paper shows that SGDM has the same convergence bound as SGD for both strongly convex and nonconvex objectives.The analysis applies beyond least squares and does not require uniformly bounded gradients.
- Contributions: The analysis attributes this result to SGDM’s update direction having controllable deviation from the full gradient and smaller variance, handled through a new Lyapunov function and auxiliary sequence.These constructions are designed to exploit the reduced variance while controlling the momentum-induced deviation.
- Contributions: Multistage SGDM receives the first convergence guarantee for stagewise parameters and is theoretically faster at initial stages than fixed-parameter training.Larger early stepsizes boost initial performance, while smaller final stepsizes reduce the stationary-distribution size.
- Scope: The work restricts its momentum analysis to heavy-ball momentum, the form described as most popular in current deep-learning practice.Other momentum variants are discussed but not analyzed here.
2 Notation and Preliminaries
This section establishes notation and the standard smoothness and stochastic-gradient assumptions used throughout the convergence analysis.
- Notation: The paper uses the vector ℓ2-norm and dot product, and defines gk as the full gradient ∇f(xk) and f∗ as the minimum objective value.These definitions provide the basic notation for subsequent convergence statements.
- Assumptions: The objective is assumed to be L-smooth, while strong convexity with parameter µ is introduced as an additional structural condition.Smoothness is part of the standing assumption; strong convexity is treated separately when required.
- Presentation: The paper states that its assumptions are standard in stochastic optimization and defers proofs to the appendix unless otherwise noted.This describes the presentation convention rather than a mathematical assumption.
- Assumptions: The stochastic gradient has bounded variance: Varζk(˜gk) = Eζk[∥˜gk − gk∥2] ≤ σ2 for some σ2 > 0.The variance is measured relative to the full gradient at the current iterate.
3 Key Ingredients of Convergence Theory
The analysis treats momentum as a moving-average update with reduced variance but a controllable deviation from the current gradient. A Lyapunov function incorporating this deviation and an auxiliary sequence supports convergence for fixed and multistage SGDM.
- Momentum observation: Momentum reduces the variance of the update vector by a factor involving (1 − β), while introducing a controllable deviation from the full gradient.
- Momentum observation: SGDM’s update vector is a moving average of past stochastic gradients, assigning smaller weights to older gradients.
- Momentum observation: The deviation from the current gradient is controlled through weighted past iterate differences whose coefficients decay linearly for older terms.
- Lyapunov construction: The analysis constructs a Lyapunov function with an auxiliary sequence to handle momentum’s deviation and exploit its reduced variance.
- Lyapunov construction: The auxiliary sequence z_k is analyzed because it behaves more like an SGD iterate than the original momentum iterate.
- Lyapunov construction: The resulting Lyapunov function yields SGDM convergence as fast as SGD under strongly convex and nonconvex settings.
- Multistage extension: For multistage SGDM, stagewise parameters use larger initial stepsizes and smaller final stepsizes, with momentum weights constrained by the schedule.
4 Convergence of SGDM
The paper establishes convergence results for SGDM under nonconvex and strongly convex assumptions using a Lyapunov analysis. The bounds recover the corresponding SGD behavior, including under a suitable stepsize scaling with momentum.
- Convergence analysis: A Lyapunov function is used to establish convergence of SGDM under the stated stepsize conditions.
- Nonconvex setting: The nonconvex result follows by telescoping the Lyapunov inequality to obtain stationary convergence.
- Strongly convex setting: Under strong convexity, Theorem 2 and Corollary 1 provide convergence bounds after the mild burn-in index k0.
- Nonconvex setting: SGDM achieves the same nonconvex convergence bound as SGD when α = O(1−β / L).
- Comparison with prior analyses: Earlier stationary-distribution analyses yielded a radius O(ασ2/(1−β)) and, in one case, additionally assumed uniformly bounded gradients.
- Strongly convex setting: Setting β = 0 recovers the corresponding SGD convergence bound under strong convexity.
5 Convergence of Multistage SGDM
The multistage analysis extends the Lyapunov framework to stagewise stepsizes, momentum weights, and stage lengths. It explains how larger early stepsizes and smaller later stepsizes trade initial speed against stationary-distribution size, while overall complexity remains unresolved.
- Proof framework: The multistage convergence proof extends the Lyapunov construction by choosing positive coefficients and an auxiliary sequence for stagewise parameters.
- Convergence guarantee: The multistage theorem bounds the average of the averaged squared gradient norms across n stages.
- Parameter schedule: The schedule uses larger stepsizes initially to accelerate convergence and smaller stepsizes later to reduce the final stationary distribution.
- Interpretation: Unlike static SGDM, the multistage strategy can combine fast initial progress with a small final stationary distribution.
- Limitation: The overall iteration complexity of Multistage SGDM versus SGDM remains unclear, although numerical experiments observe faster multistage performance.
6 Experiments
Experiments compare fixed and multistage SGDM across MNIST logistic regression and CIFAR-10 ResNet18 training. The results show a trade-off between rapid early loss reduction and lower final loss, with multistage SGDM performing best in the ResNet18 experiment.
- Experimental protocol: Three random seeds are used for each algorithm-task combination, with losses generally averaged over the preceding full-dataset batch window.The experiments use the mean of losses over the past m batches unless otherwise stated.
- 6.1 Logistic regression: Larger fixed stepsizes decrease loss faster initially, but the smallest tested stepsize achieves the lowest later loss.For example, α = 1.0 and α = 0.5 decrease losses more rapidly than α = 0.1, while α = 0.1 has lower final loss.
- 6.1 Logistic regression: Multistage SGDM combines the faster initial behavior of (α, β) = (0.66, 0.9) with the lower-final-loss behavior of (α, β) = (0.095, 0.9).The MNIST multistage schedule uses three stages with T1 = 3, T2 = 6, T3 = 21 and stage-dependent parameters.
- 6.2 Image classification: Multistage SGDM performs best among the tested ResNet18 training algorithms, while baseline SGDM is slightly worse.The comparison includes Multistage SGDM, baseline SGDM, and YellowFin on CIFAR-10, using training losses and end-of-epoch validation accuracy.
7 Summary and Future Directions
The paper concludes that SGDM matches plain SGD’s speed in nonconvex and strongly convex settings and establishes convergence and stagewise advantages for multistage SGDM. It identifies faster convergence for special objectives and more efficient parameter choices as open problems.
- Summary: SGDM is shown to be as fast as plain SGD in both nonconvex and strongly convex settings.The conclusion presents this as a theoretical insight into SGDM convergence behavior.
- Summary: The paper establishes convergence for widely adopted multistage SGDM and shows an advantage for stagewise training.This extends the convergence analysis beyond the momentum-free case discussed in the paper.
- Future Directions: Whether SGDM can converge faster than SGD for special objectives such as quadratic ones remains open.The paper also asks whether parameter choices more efficient than (7) can guarantee faster convergence.
- Future Directions: More efficient parameter choices than (7) that guarantee even faster convergence are identified as another open problem.This question concerns the design of multistage parameters.
A Proof of Preliminary Lemmas
The preliminary-lemma proofs control stochastic momentum terms using independence, unbiased gradients, smoothness, and auxiliary-sequence arguments. They then choose coefficients and stepsize conditions to establish the required inequalities.
- Expectation control: The proofs expand expectations over independent random variables and use unbiased stochastic gradients to handle stochastic inner-product terms.They also invoke the relevant assumption on gradient noise and independence from prior iterates.
- Analytic bounds: Cauchy-Schwarz, triangle inequality, and smoothness are used to bound gradient and iterate-difference terms.These inequalities form intermediate bounds used in the propositions.
- Auxiliary sequence: The auxiliary sequence z_k is related to x_k and x_{k-1}, allowing the proof to treat the initial and later iterations separately.For k = 1, z_k equals x_k; for k ≥ 2, it combines consecutive iterates using β.
- Coefficient selection: Coefficient choices make the remaining terms non-positive and yield the desired proposition inequalities.The arguments define constants such as c_i and impose stepsize restrictions involving L and β.
- Residual bounds: The proof bounds residual quantities R1 and R2 under explicit choices of ρ0 and sufficiently small α.The resulting bounds use smoothness, noise variance, and momentum-dependent factors.
B.4 Proof of Proposition 2
The Proposition 2 proof selects auxiliary constants and bounds terms using strong convexity and prior lemmas. It derives conditions ensuring coefficient positivity and the desired inequality under restrictions on stepsize, momentum, and problem parameters.
- Proof setup: The proof begins by setting auxiliary quantities for Proposition 2 and combining earlier inequalities to control the main expression.Several steps substitute bounds from prior results before deriving the desired relation.
- Strong-convexity bound: Strong convexity supplies a lower bound for the objective-gap term used in the proof.The argument relates f(x) to its minimum f⋆ through strong convexity.
- Conclusion: Combining the bounds produces the desired result for Proposition 2.The proof’s final substitutions connect the auxiliary estimates to the target inequality.
- Parameter conditions: The argument uses relationships among β, √β, μ, and L to verify the coefficient inequalities.These comparisons are invoked under conditions such as μ ≤ L and a stepsize restriction.
B.5 Proof of Theorem 2
The proof develops the multistage SGDM convergence theory by controlling momentum updates and auxiliary sequences under stagewise parameters. It concludes the desired result using convexity and Theorem 2.
- The auxiliary sequence z_k is related to the iterates through a convex-combination representation.
- The desired result follows from the convexity of f and Theorem 2.
- The update vector m_k is analyzed through past stochastic gradients, whose weights are shown to sum appropriately.
- Nondecreasing stage momentum weights, β_1 ≤ β_2 ≤ ... ≤ β_n, support the bound d_{k,i} ≤ a_{k,i}.
- The section proves the main convergence theory for Multistage SGDM.
D.1 Proof of Proposition 3
The proof of Proposition 3 extends earlier convergence arguments to the multistage setting. It controls stochastic-update terms using smoothness, independence, and parameter choices that make residual terms non-positive.
- Proposition 3 generalizes Propositions 4 and 1 to the multistage case.
- The remaining bounds combine Lemmas 4 and 5 with smoothness-based estimates.
- The stepsize α(k) is explicitly identified as the parameter applied at iteration k.
- The proof uses independence between z_k and the current sample ζ_k to handle the inner-product term.
- The parameter choices are designed so the last three terms in the main inequality are non-positive.