PaperlayerView exact revision on arXiv

Source-linked AI summary

A Simple Convergence Proof of Adam and Adagrad

Alexandre Défossez, Léon Bottou, Francis Bach, Nicolas Usunier

arXiv:2003.02395v3stat.MLcs.LG

TL;DR

The paper addresses convergence of Adam and Adagrad for smooth stochastic non-convex optimization under bounded-gradient assumptions. It develops a unified proof and shows that suitable hyper-parameters give Adam the same O(d ln(N)/√N) rate as Adagrad, while improving momentum dependence to O((1−β1)^−1).

  • Problem

    Convergence guarantees for Adam in non-convex optimization remained uncertain, while prior bounds for Adam and Adagrad had worse dependence on β1.

  • Method

    The paper uses a simplified, unified convergence proof for coordinate-wise Adagrad and Adam under smoothness, lower-boundedness, and almost-surely bounded stochastic gradients.

  • Results

    With appropriate step sizes and decay parameters, Adam converges at the same O(d ln(N)/√N) rate as Adagrad, while the β1 dependence improves to O((1−β1)^−1).

  • Takeaways & Limitations

    Adam can converge without the AMSGrad variant when its hyper-parameters are chosen appropriately, and its analysis links its convergence to Adagrad’s.

  • Takeaways & Limitations

    The analysis assumes a strong uniform almost-sure ℓ∞ bound on stochastic gradients and has a dimension dependence inherited from coordinate-wise adaptive methods.

Abstract

from arXiv · show

We provide a simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied to smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer, the dimension $d$, and the total number of iterations $N$. This bound can be made arbitrarily small, and with the right hyper-parameters, Adam can be shown to converge with the same rate of convergence $O(d\ln(N)/\sqrt{N})$. When used with the default parameters, Adam doesn't converge, however, and just like constant step-size SGD, it moves away from the initialization point faster than Adagrad, which might explain its practical success. Finally, we obtain the tightest dependency on the heavy ball momentum decay rate $β_1$ among all previous convergence bounds for non-convex Adam and Adagrad, improving from $O((1-β_1)^{-3})$ to $O((1-β_1)^{-1})$.

1 Introduction

The paper presents a simplified, unified convergence proof for Adagrad and Adam in stochastic non-convex smooth optimization. It establishes convergence rates and improves the dependence on momentum parameters relative to prior work.

  • Adaptive step sizes have been applied to sparse optimization, tensor factorization, and deep learning, with Adagrad effective for sparse optimization but under-performing in deep learning.
  • Adagrad achieves optimal regret in online convex optimization, while prior convergence analyses for Adam and non-convex Adagrad used progressively specialized settings.
  • The paper gives a simplified, unified convergence proof for Adagrad and Adam in stochastic non-convex smooth optimization.
  • Under the stated assumptions, the analysis recovers an O(ln(N)/√N) convergence rate for Adagrad and for Adam with appropriate step sizes and decay parameters.
  • The paper compares its convergence bounds with experimental results on toy and real-life problems.

2 Setup

The setup formulates Adagrad and Adam within one coordinate-wise adaptive framework, with momentum, squared-gradient averaging, corrective terms, and explicit smoothness and gradient assumptions. A simplified Adam variant drops the momentum corrective term while retaining the variance correction.

  • The optimization goal is to find a critical point of F using unbiased stochastic gradients from i.i.d. samples of a random function f.
  • The unified formulation iteratively defines momentum, squared-gradient-average, and parameter vectors from an initial point x0.
  • β1 controls heavy-ball momentum, β2 controls per-coordinate squared-gradient averaging, and β1 = 0 with β2 = 1 recovers Adagrad.
  • Adam and its corrective terms: Adam uses weighted averages and corrective terms that compensate for early bias of the momentum and squared-gradient estimates.
  • Adam and its corrective terms: The analyzed Adam variation drops the corrective term for mn, keeps the one for vn, and uses the resulting step size because monotonic step sizes simplify the proof.
  • Adam and its corrective terms: Dropping the mn correction has no observable training effect, whereas dropping the vn correction produces observable perturbations and can increase early step sizes.
  • Assumptions: The assumptions include a lower-bounded objective, uniformly almost-surely bounded stochastic gradients, and an L-smooth objective gradient.

3 Related work

Related work established convergence results for adaptive methods in convex and selected non-convex settings, but Adam’s convergence remained disputed and coordinate-wise, momentum-supported guarantees were limited. This paper extends the analysis and improves the dependence on β1.

  • Adagrad has established convergence results in convex optimization and, later, for non-convex objectives under increasingly less restrictive conditions.
  • Adam’s original convergence proof contained an error, and AMSGrad was proposed after examples showed Adam failing to converge to an optimal solution on some convex problems.
  • The paper extends prior scalar-Adagrad analysis to coordinate-wise Adagrad and Adam while supporting heavy-ball momentum.
  • For Adagrad with heavy-ball momentum, the β1 dependence improves from O((1−β1)^−3) to O((1−β1)^−1) while retaining the same dependence on N.
  • For Adam, the β1 dependence improves from O((1−β1)^−5) in prior work to O((1−β1)^−1).
  • Momentum SGD previously had an O((1−β1)^−2) bound, which the paper improves to O((1−β1)^−1).

4 Main results

The paper gives convergence bounds for Adagrad and Adam under smooth non-convex stochastic optimization, including momentum, and analyzes their finite-horizon behavior and dimensional dependence. It shows that suitable Adam parameters match Adagrad’s rate, while momentum worsens bounds and the coordinate-wise analysis can scale poorly with dimension.

  • Convergence results: The expected squared gradient norm at a randomly sampled trajectory iterate is bounded for both Adagrad and Adam under the stated stochastic optimization assumptions.The sampling distribution is uniform when β1 = 0 and downweights the latest iterations when β1 > 0.
  • Dimensional dependence: The coordinate-wise bound can grow as d because the proof applies its key ratio lemma once per dimension; this is worse than scalar Adagrad or SGD when many dimensions contribute little gradient norm.The dR² term is reasonable when gradient scales are similar across dimensions, but not when many coordinates are negligible.
  • Assumptions: An almost-sure uniform ℓ∞ gradient bound is assumed, although a uniform bound on the expected gradient is also discussed as an alternative.The paper characterizes the almost-sure assumption as strong and notes that replacing it changes the resulting bound.
  • Momentum: O((1 −β1)^−1) is the momentum dependency obtained for both algorithms, improving previous Adagrad and Adam dependencies of O((1 −β1)^−3) and O((1 −β1)^−5).The bounds nevertheless deteriorate as β1 increases.
  • Finite-horizon Adam: α(N) ∝ N^−1/2 and β2 = 1 −1/N yield Adam’s best finite-horizon rate, O(ln(N)/√N).With these parameters, Adam’s exponential averaging window is of order N, resembling Adagrad’s averaging over past terms.
  • Convergence results: O(ln(N)/√N) is achieved by Adagrad for all step sizes and by Adam with appropriate step sizes and decay parameters.Adam can therefore converge without using AMSGrad under those parameter choices.
  • Finite-horizon Adam: Adam with default parameters does not converge, whereas suitable α and β2 can make its critical-point error arbitrarily small and match Adagrad’s finite-horizon bound.The analysis also relates Adam’s behavior to constant-step-size SGD and Adagrad’s behavior to decaying-step-size SGD.

5 Proofs for β1 = 0 (no momentum)

For the no-momentum case, the proof controls adaptive updates through approximate descent and bounds the accumulated deviations using a logarithmic ratio lemma. Applying that lemma coordinate-wise completes the Adagrad and Adam convergence proofs.

  • Setup: The no-momentum analysis sets β1 = 0 and uses the unified recursions that recover Adagrad when β2 = 1 and Adam when 0 < β2 < 1.The proof first treats this simpler setting before the momentum results.
  • Technical lemmas: Correlation between the stochastic-gradient numerator and adaptive denominator prevents direct conditional-expectation analysis of the update.The expected update direction can therefore have a positive dot product with the objective gradient.
  • Technical lemmas: Lemma 5.1 bounds the adaptive update’s deviation from a descent direction for each coordinate.This provides the local control needed before summing over iterations.
  • Technical lemmas: Lemma 5.2 shows that the sum of these deviations grows at most logarithmically, despite deviations at individual iterations.Its proof uses a telescoping series and a logarithmic bound involving β2.
  • Completing the proofs: Applying Lemma 5.2 once per dimension and rearranging terms completes the convergence proofs for Adagrad and Adam.The Adagrad and Adam derivations sum the smoothness-based inequalities over iterations before taking expectations.

6 Experiments

Experiments compare Adam's parameter dependencies on a crafted toy problem and CIFAR-10, then test the practical effect of Adam's corrective terms. The toy results match theoretical dependencies more closely than the CIFAR-10 behavior.

  • Setup: Figure 1 varies one of α, 1 −β1, and 1 −β2 while measuring the average squared gradient norm on a toy task and CIFAR-10.The toy task uses 10^6 iterations; CIFAR-10 uses 600 epochs with batch size 128, averaging curves over three runs.
  • Toy problem: The toy problem uses six coordinates with increasingly rare, increasingly weighted gradient events, giving every coordinate equal gradient variance.Different event probabilities are necessary to obtain the continuous improvement observed as β2 changes.
  • Toy problem: 0.56: the toy-task log-log slope versus 1 −β2 is compatible with the predicted O(1/√1 −β2) dependency.The experiment observes continual improvement as β2 increases.
  • Toy problem: 0.87: the toy-task log-log slope versus α is compatible with the predicted O(α) dependency, while β1 has limited impact except when 1 −β1 is small.The fitted β1 slope is -0.16, compared with the bound's predicted slope of -1.
  • CIFAR-10: On CIFAR-10, large α performs best from random initialization but has high variance at the largest values, indicating instability absent from the theory.The authors attribute this likely mismatch to the bounded-gradient assumption not holding for deep neural networks.
  • Impact of the Adam corrective terms: Dropping Adam's corrective term on m_n has limited impact, whereas dropping the term on v_n substantially changes training trajectories.The comparison reports both training loss and expected-gradient norm across combinations of α, β1, and β2.

7 Conclusion

The paper concludes that a simple convergence proof links Adam and Adagrad and substantially improves momentum dependence. Experiments support the predicted α and β2 dependencies, while the practical role of momentum remains unexplained.

  • Conclusion: The proof establishes convergence for Adam and Adagrad without heavy-ball momentum and links Adam's convergence behavior to Adagrad under suitable hyper-parameters.The analysis also extends to heavy-ball momentum and improves its parameter dependence for Adam, Adagrad, and SGD.
  • Conclusion: The toy experiment matches the predicted dependencies on α and β2, but the analysis does not predict momentum's practical interest.The authors identify improvements to the proof as future work.
  • Conclusion: The theoretical results concern stochastic optimization of non-convex losses and are intended to improve understanding of deep-neural-network training dynamics.The paper states no direct possible negative societal impact.

Overview

The paper develops a dynamic-system analysis of adaptive methods, with parameterizations that encompass Adam and Adagrad and simplify the treatment of corrective terms. Its proof also uses an iteration-sampling scheme adapted to momentum.

  • Overview: The analysis defines momentum and squared-gradient moving-average updates together with coordinate-wise iterates starting from x_0, m_0 = 0, and v_0 = 0.The updates use β1 for momentum and β2 for the squared-gradient average.
  • Overview: The proof omits Adam's original corrective factor on m_n by incorporating 1 −β1 into the step size, while retaining the relevant asymptotic denominator choice.The denominator replacement avoids non-monotonic step sizes and differs from the original rule mainly during early iterations.
  • Overview: The analysis introduces updates with and without heavy-ball momentum and auxiliary moving-average quantities to support the convergence proof.These objects organize the comparison between momentum and non-momentum dynamics.

A.2 Results

The results bound the expected squared gradient norm at a momentum-aware random iteration for Adagrad and Adam under the paper's assumptions. The momentum dependence is O((1 −β1)^-1), improving substantially over earlier bounds.

  • Sampling: τ is sampled uniformly when β1 = 0, but recent iterations are sampled less often when β1 > 0 because momentum delays the influence of recent gradients.The analysis bounds the expected squared norm of the total gradient at iteration τ, a standard non-convex stochastic-optimization target.
  • Momentum dependence: O((1 −β1)^-1): the convergence bound worsens as β1 increases but improves over O((1 −β1)^-3) for Adagrad and O((1 −β1)^-5) for Adam.The comparison is stated for heavy-ball momentum convergence bounds.
  • Adagrad: Theorem 3 gives convergence for Adagrad with β2 = 1, constant α > 0, 0 ≤β1 < 1, and sufficiently large N.The random index τ follows the paper's momentum-aware sampling rule.
  • Adam: Theorem 4 gives convergence for Adam when 0 < β2 < 1, 0 ≤β1 < β2, with the stated step-size condition and sufficiently large N.The theorem uses the same τ construction as the momentum analysis.
  • Adam: The displayed Adam result makes the bound explicit in α, d, R, L, β1, β2, and the iteration-dependent terms.Its terms include factors involving (1 −β1/β2), (1 −β2), and square-root dependence on 1 −β1 and 1 −β2.

A.3 Analysis of the results with momentum

The momentum analysis extends the convergence proof to Adam, Adagrad, and SGD, using recentered past gradients and non-uniform iterate sampling to control momentum effects. It obtains an O((1 −β1)^−1) dependence and recovers an ln(N)/√N rate under suitable scaling, while leaving variance reduction from momentum unresolved.

  • Finite-horizon behavior: With suitable hyper-parameters, Adam recovers the ln(N)/√N convergence rate associated with Adagrad.The finite-horizon scaling compensates the (1 −β2)^3/2 denominator term through α^2.
  • Proof strategy: Adam and Adagrad require updated descent and ratio lemmas because momentum correlates decayed gradient sums with adaptive denominators.The proof separately handles momentum contributions through decaying past gradients and technical summation lemmas.
  • Proof strategy: Re-centering past gradients using smoothness creates extra terms involving earlier expected gradients and improves the β1 dependence.The added smoothness cost is compensated by additional terms in the analysis.
  • Momentum convergence bounds: O((1 −β1)^−1) dependence is obtained for Adam, Adagrad, and SGD, improving the previous momentum dependence for adaptive methods.The proof combines tight summation control with non-uniform sampling of iterates.
  • Limitations: The proof does not establish that heavy-ball momentum reduces update variance, limiting the demonstrated benefits of momentum.Stronger probabilistic results or additional regularity assumptions might be needed for such an improvement.

B.3 Analysis

The analysis derives an SGD-with-momentum convergence theorem by bounding momentum iterates, establishing descent, and averaging gradients using a geometrically weighted random iterate. Its resulting β1 dependence improves earlier bounds from O((1 −β1)^−2) to O((1 −β1)^−1).

  • Main result: O((1 −β1)^−1) dependence replaces the O((1 −β1)^−2) dependence obtained in earlier non-convex SGD momentum analysis.The comparison is made under the paper’s bounded-gradient setting, while related work achieves similar dependence with weaker assumptions.
  • Parameter scaling: Choosing the step size proportional to (1 −β1) compensates for the increase in the typical momentum update as β1 grows.This scaling keeps the first term in the convergence bound independent of β1.
  • Proof components: The proof bounds the momentum sequence and establishes a descent lemma before summing expected inequalities over all iterations.Smoothness and a lower bound on the objective are used in the summation step.
  • Proof mechanism: Replacing the current gradient with an old gradient yields additional terms ∥G_n−k∥^2 that enable the improved momentum dependence.The trade-off is an extra smoothness-controlled term on the right-hand side.
  • Random iterate: A random iterate τ is sampled with geometrically shaped weights, reflecting the accumulated contribution of momentum across past gradients.The normalization of these weights appears when converting the summed gradient terms into an expectation at τ.
Loading 2003.02395v3…