Source-linked AI summary
On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
Dongruo Zhou, Jinghui Chen, Yuan Cao, Ziyan Yang, Quanquan Gu
TL;DR
Adaptive gradient methods lacked thorough convergence guarantees for smooth nonconvex optimization despite their practical use. The paper develops a fine-grained analysis of AMSGrad, corrected RMSProp, and AdaGrad, proving convergence in expectation and high-probability bounds. Its results improve dimension dependence and establish previously unavailable high-probability guarantees for these methods.
Problem
Convergence guarantees for adaptive gradient methods were mostly restricted to online convex optimization, leaving their nonconvex behavior insufficiently characterized.
Method
The paper analyzes AMSGrad, corrected RMSProp, and AdaGrad for smooth nonconvex optimization under bounded-gradient and cumulative-gradient assumptions.
Results
The methods converge to stationary points in expectation, with AMSGrad achieving O(d1/2/T 3/4−s/2), while AMSGrad, RMSProp, and AdaGrad also receive high-probability convergence bounds.
Takeaways & Limitations
The analysis provides finer convergence guarantees for adaptive methods in smooth nonconvex optimization, including improved dimension dependence and new high-probability results.
Takeaways & Limitations
The analysis assumes bounded stochastic gradients, with the coordinatewise bound related to an ℓ2 bound through dimension-dependent factors.
Abstract
from arXiv · showhide
Adaptive gradient methods are workhorses in deep learning. However, the convergence guarantees of adaptive gradient methods for nonconvex optimization have not been thoroughly studied. In this paper, we provide a fine-grained convergence analysis for a general class of adaptive gradient methods including AMSGrad, RMSProp and AdaGrad. For smooth nonconvex functions, we prove that adaptive gradient methods in expectation converge to a first-order stationary point. Our convergence rate is better than existing results for adaptive gradient methods in terms of dimension. In addition, we also prove high probability bounds on the convergence rates of AMSGrad, RMSProp as well as AdaGrad, which have not been established before. Our analyses shed light on better understanding the mechanism behind adaptive gradient methods in optimizing nonconvex objectives.
1 Introduction
Adaptive gradient methods have strong empirical motivation but limited nonconvex convergence guarantees. The paper analyzes their convergence rates and establishes improved dimension dependence and new high-probability results.
- Adaptive gradient methods scale each coordinate using past gradients, adjusting feature-specific learning rates and often helping when gradients are sparse.
- Existing convergence guarantees are mostly restricted to online convex optimization, leaving a gap with empirical success in nonconvex optimization.
- The paper proves convergence rates for AMSGrad in stochastic nonconvex optimization under a cumulative-gradient growth condition parameterized by s.
- In the worst case s = 1/2, the AMSGrad rate has better dependence on dimension d and iterations T than a previous result.
- The paper establishes high-probability convergence bounds for AMSGrad, RMSProp, and AdaGrad, including first such guarantees for AMSGrad and RMSProp in nonconvex stochastic optimization.
2 Related Work
Related work covers nonconvex stochastic optimization, adaptive-gradient convergence, and high-probability guarantees. Prior studies use varied assumptions and convergence settings, motivating the paper’s comparison of rates and guarantees.
- Adaptive-gradient studies addressed strongly convex, convex, delayed, and denominator-specific settings, while several results used deterministic rather than stochastic gradients.
- Prior nonconvex stochastic-optimization work established stationary-point convergence rates for randomized, accelerated, and variance-reduced gradient methods.
- Table 1 compares prior AMSGrad and AdaGrad convergence rates by convergence type and assumptions in smooth nonconvex optimization.
- High-probability convergence results had been developed for several other algorithms, but adaptive-gradient guarantees remained an open area addressed by this paper.
3 Algorithms
The paper studies AMSGrad, corrected RMSProp, and AdaGrad as adaptive methods that construct effective learning rates from gradient history. Their update mechanisms differ in how past squared stochastic gradients are aggregated and controlled.
- The paper focuses on AMSGrad, a corrected RMSProp variant, and AdaGrad.
- AMSGrad: AMSGrad uses exponential moving averages of gradients and squared gradients, with an element-wise maximum controlling the adaptive denominator.
- AMSGrad: AMSGrad’s non-increasing effective learning rate is designed to address Adam’s possible convergence issue.
- RMSProp: The corrected RMSProp variant also uses the maximum step and sets its effective learning rate through the corresponding adaptive denominator.
- AdaGrad: AdaGrad computes the effective learning rate from the summation of past stochastic gradient squares rather than a running average.
4 Convergence Results in Expectation
The paper analyzes AMSGrad, RMSProp, and AdaGrad for smooth stochastic nonconvex optimization under bounded-gradient and smoothness assumptions. In expectation, all three methods obtain convergence rates that match nonconvex SGD in the worst case, while improving dimension dependence over prior adaptive-method bounds.
- Problem setting: The analysis studies stochastic optimization of L-smooth nonconvex functions with unbiased stochastic gradients and coordinate-wise bounded gradients.The bounded-gradient assumption is expressed in the ℓ∞ norm and is weaker than a corresponding ℓ2-boundedness assumption.
- Assumptions: The convergence guarantees assume cumulative coordinate-wise stochastic gradients grow no faster than G∞T^s, where 0 ≤ s ≤ 1/2.The parameter s captures gradient sparsity: s = 1/2 in the worst case and s < 1/2 when gradients are sparse.
- AMSGrad: In the worst case s = 1/2, AMSGrad matches the convergence rate of nonconvex SGD.The comparison is made under the paper’s stochastic-gradient assumptions and concerns the convergence rate to a stationary point.
- AMSGrad: AMSGrad’s bound has linear rather than quadratic dimension dependence in the relevant convergence term and converges to zero without Adam’s constant error term.The paper reports a rate O(d^1/2/T^(3/4−s/2)) and states that this addresses the convergence issue identified for Adam.
- RMSProp and AdaGrad: RMSProp and AdaGrad achieve the same convergence rate as AMSGrad under the corresponding expectation assumptions.When s = 1/2, both methods match the convergence rate of nonconvex SGD.
- RMSProp and AdaGrad: The AdaGrad result improves the dimension dependence over a prior AdaGrad bound.The paper specifically states that its result gives a faster rate in the dependence on dimension d.
5 Convergence Results with High Probability
The paper extends convergence guarantees for adaptive gradient methods to high-probability settings in smooth nonconvex optimization. Under sub-Gaussian stochastic-gradient assumptions, it gives high-probability bounds for AMSGrad, RMSProp, and AdaGrad.
- Motivation: Single-run training motivates high-probability guarantees because expectation bounds cannot rule out extremely bad solutions.The paper highlights this concern for applications where training is performed only once because training time can be substantial.
- Assumptions: Sub-Gaussian stochastic gradients are assumed for the high-probability analysis.The paper notes that this assumption is commonly used and weaker than a cited alternative in a Gaussian case.
- AMSGrad: With probability at least 1 −δ, AMSGrad satisfies the theorem’s convergence bound under its stated step-size, gradient-growth, and regularity conditions.The supplied passage states the probability guarantee and conditions but omits the displayed bound itself.
- Scope: The paper also explicitly provides high-probability corollaries for RMSProp and AdaGrad.These results extend the high-probability analysis beyond AMSGrad.
- RMSProp: With probability at least 1 −δ, RMSProp satisfies its corresponding convergence bound under the same class of conditions.The RMSProp corollary imposes αt = α ≤σ−2ǫ/2 and ∥g1:T,i∥2 ≤G∞T s with 0 ≤s ≤1/2.
- AdaGrad: With probability at least 1 −δ, AdaGrad likewise satisfies a high-probability convergence bound under the theorem’s conditions.The corollary uses αt = α ≤σ−2ǫ/2 and the same gradient-growth condition with 0 ≤s ≤1/2.
6 Proof Sketch of the Main Results
The proof handles stochastic momentum and adaptive scaling through an auxiliary sequence, then bounds its increments and gradient discrepancies before telescoping smoothness inequalities. A joint treatment of momentum and stochastic gradients yields a tighter dimension dependence than separately bounding them.
- Proof strategy: The main technical difficulty is analyzing stochastic momentum and adaptive stochastic gradients together, unlike standard stochastic-gradient analysis.The proof sketch identifies these adaptive components as the source of additional difficulty.
- Auxiliary sequence: An auxiliary sequence zt is introduced to analyze algorithms containing stochastic momentum, including AMSGrad.Its increments can be represented using momentum, stochastic gradients, and adaptive scaling.
- Auxiliary sequence: Bounds on ∥zt+1 −zt∥2 and ∥∇f(zt) −∇f(xt)∥2 support the proof of the main convergence theorem.The proof then applies smoothness, separately bounds terms, and telescopes the resulting inequalities.
- Bounding terms: The analysis bounds ∥∇f(x)∥∞, ∥bvt∥∞, and ∥mt∥∞ using the assumptions and auxiliary lemmas.These bounds control the gradient, adaptive second-moment estimate, and stochastic momentum.
- Bounding terms: The proof combines one-step inequalities by taking expectations, telescoping over t = 2 to T, and applying the lemma controlling adaptive-gradient terms.The same proof structure is adapted for the high-probability result using filtration and martingale concentration.
- Dimension dependence: Jointly bounding momentum and stochastic gradients produces an α1d term, whereas the compared analysis incurs an α2d + d = O(d) dependency.Optimizing α therefore yields a tighter dimension dependence in the paper’s final bound.
- High-probability proof: The high-probability proof reuses the expectation proof through the initial inequalities, then invokes a martingale concentration argument under the filtration Ft.The step size is chosen as αt = α ≤σ−2ǫ/2 before rearranging the resulting bound.
7 Conclusion
The paper presents a fine-grained convergence analysis for a general class of adaptive gradient methods in smooth nonconvex optimization. It reports faster rates than previous work and new high-probability guarantees for AMSGrad, corrected RMSProp, and AdaGrad.
- Conclusion: The paper proves convergence rates for a general class of adaptive gradient methods in smooth nonconvex optimization.The conclusion characterizes the analysis as fine-grained.
- Conclusion: The reported rates for AMSGrad, corrected RMSProp, and AdaGrad are faster than those in previous work.The comparison is stated for smooth nonconvex optimization.
- Conclusion: The paper proves high-probability convergence bounds for AMSGrad, RMSProp, and AdaGrad.The conclusion states that these guarantees had not previously been established in the considered setting.
A.1 Proof of Theorem 4.3
The proof of Theorem 4.3 combines boundedness assumptions, an auxiliary sequence, and lemmas controlling its increments and gradient differences. Conditional unbiasedness, telescoping, and step-size conditions then yield the theorem’s bound.
- Assumptions: The proof assumes bounded gradients and adaptive estimates, including ∥∇f(x)∥∞≤G∞ and ∥bvt∥∞≤G2.These bounds are supplied by Lemma A.1 under Assumption 4.1.
- Assumptions: The analysis uses constant step sizes αt = α and requires γ ≤1 under Assumption 4.1.Here γ is defined from the momentum weight parameters.
- Algorithmic cases: Different choices of β′1 and β′2 recover the paper’s algorithmic cases, including Algorithms 1, 2, and 3.The lemma is presented as general and applicable to various algorithms.
- Auxiliary sequence: An auxiliary sequence zt is introduced to handle stochastic momentum and stochastic adaptive scaling.The proof connects zt+1 −zt with xt+1 −xt and the adaptive-gradient update.
- Technical lemmas: Two lemmas bound ∥zt+1 −zt∥2 and ∥∇f(zt) −∇f(xt)∥2, providing the technical controls needed for the proof.A further lemma bounds the one-step function difference f(zt+1) −f(zt).
- Proof completion: The proof concludes after applying the stated theorem quantities and completing the telescoping argument.The supplied proof passages explicitly mark completion after the final rearrangement.
- Proof completion: Conditional unbiasedness gives E[gt] = ∇f(xt), after which the proof telescopes inequalities and substitutes auxiliary bounds.The proof rearranges the resulting inequalities and applies the theorem’s gradient-growth condition.
A.2 Proof of Corollary 4.5
The corollary follows the proof strategy established for Theorem 4.3 by specializing parameters in Lemma A.2.
- The conclusion is obtained by setting β′ 1 = β1 = 0 and β′ 2 = β2 = β in Lemma A.2.
- The proof follows the approach used for Theorem 4.3.
A.3 Proof of Corollary 4.6
The proof of Corollary 4.6 specializes the preceding theorem’s argument and combines conditional tail bounds, smoothness estimates, and telescoping inequalities.
- The proof follows Theorem 4.3 and obtains the corollary through parameter choices in Lemma A.2.
- Telescoping the main inequality from t = 2 to T and adding the initial-step bound completes the aggregate estimate.
- The analysis conditions on the filtration generated by past stochastic-gradient samples.The proof notes that xt and bV−1/2 t−1 depend only on ξ1, . . . , ξt−1.
- The proof uses a tail bound to invoke a high-probability result and concludes with absolute-constant bounds.The cited passages identify the tail-bound step and constants C and C′ as absolute.
- The argument bounds separate terms, applies smoothness and standard inequalities, and combines the resulting inequalities.The proof explicitly bounds I1, I2, and I3 separately before combining bounds.
B.7 Experimental Verification of the Growth Rate Condition
The paper experimentally estimates the cumulative-gradient growth-rate parameter s for a 3-layer LSTM on PennTreeBank and compares adaptive methods with SGDM.
- The experiment estimates s for a 3-layer LSTM model trained on the PennTreeBank dataset.Table 2 reports the empirical growth-rate parameter s for this setting.
- AdaGrad, RMSProp, and AMSGrad have smaller estimated s values than SGDM for the 3-layer LSTM experiment.