Elamur Research⌕
☰
home / papers / 2019 / On the Convergence of Adam and Beyond

On the Convergence of Adam and Beyond

Paper · 2019 · Sashank J. Reddi, Satyen Kale and Sanjiv Kumar

Summary

Adaptive optimizers such as RMSProp, Adam, AdaDelta and NAdam scale each gradient coordinate by the root of an exponential moving average of past squared gradients. In some settings, for example learning with large output spaces, they fail to reach an optimum. The authors place these methods in a generic adaptive framework and trace the failure to that moving average. Because it effectively forgets old gradients, rare but large and informative gradients fade quickly. As a result, the effective learning rate can grow over time, while in SGD and AdaGrad it only shrinks. They build a simple one-dimensional convex problem where Adam provably converges to the worst point, and they locate the flaw in the original convergence proof by Kingma & Ba (2015). As a fix, they propose Adam variants with "long-term memory" of past gradients, most notably AMSGrad, which tracks a running maximum of the second-moment estimate. These variants keep Adam's time and memory cost and come with a convex regret bound. Preliminary experiments show they match or beat Adam. The work matters because Adam is a default optimizer in deep learning.

Key points

  • The analysis centres on Γ_t, the change in the inverse learning rate between steps. It is positive semidefinite for SGD and AdaGrad but can be indefinite for Adam and RMSProp, and this is what breaks convergence.
  • In the counterexample, the feasible set is F = [−1, 1]. The loss is f_t(x) = Cx when t mod 3 = 1 and −x otherwise, with C > 2, β1 = 0 and β2 = 1/(1+C²). The optimum is x = −1, yet Adam settles at x = +1.
  • Adding the usual ε term to the denominator does not help (Theorem 6). Average regret still stays non-zero, with R_T ≥ (2C−4)T/3.
  • The proposed variants run at Adam's cost and achieve a data-dependent regret bound similar to AdaGrad's. Typical Adam defaults are β1 = 0.9 and β2 = 0.999.
  • The arguments also cover AdaDelta, NAdam, the debiased version of Adam, and any method that averages squared gradients over an essentially fixed window.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksMathematics · 189 worksNumerical Analysis · 4 works

Cite

Cite as Sashank J. Reddi, Satyen Kale and Sanjiv Kumar. 2019. On the Convergence of Adam and Beyond. arXiv:1904.09237.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1904.09237 · arXiv 1904.09237

@misc{reddi2019convergence,
  title = {{On the Convergence of Adam and Beyond}},
  author = {Sashank J. Reddi, Satyen Kale and Sanjiv Kumar},
  year = {2019},
  doi = {10.48550/arxiv.1904.09237},
  eprint = {1904.09237},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1904.09237}
}

References

11 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Peter Auer and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. In Proceedings of the 13th Annual Conference on Learning Theory, pp. 107–117, 2000. find
  2. Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50:2050–2057, 2004. find
  3. Timothy Dozat. Incorporating Nesterov Momentum into Adam. In Proceedings of 4th International Conference on Learning Representations, Workshop Track, 2016. find
  4. John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, 2011. find
  5. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of 3rd International Conference on Learning Representations, 2015.
  6. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems 25, pp. 1097– 1105, 2012.
  7. H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Annual Conference On Learning Theory, pp. 244–256, 2010. find
  8. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15:1929–1958, 2014.
  9. T. Tieleman and G. Hinton. RmsProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012. find
  10. Matthew D. Zeiler. ADADELTA: An Adaptive Learning Rate Method. CoRR, abs/1212.5701, 2012.
  11. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pp. 928–936, 2003. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/reddi-2019-convergence-adam/