On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization

By Xiangyi Chen, Sijia Liu, Ruoyu Sun, Mingyi Hong. 2018

381 citations recorded by the source corpus.

This paper studies a class of adaptive gradient based momentum algorithms that update the search directions and learning rates simultaneously using past gradients. This class, which we refer to as the "Adam-type", includes the popular algorithms such as the Adam, AMSGrad and AdaGrad. Despite their popularity in training deep neural networks, the convergence of these algorithms for solving nonconvex problems remains an open question. This paper provides a set of mild sufficient conditions that guarantee the convergence for the Adam-type methods. We prove that under our derived conditions, these methods can achieve the convergence rate of order $O(\log{T}/\sqrt{T})$ for nonconvex stochastic optimization. We show the conditions are essential in the sense that violating them may make the algorithm diverge. Moreover, we propose and analyze a class of (deterministic) incremental adaptive gradient algorithms, which has the same $O(\log{T}/\sqrt{T})$ convergence rate. Our study could also be extended to a broader class of adaptive gradient methods in machine learning and optimization.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

On Empirical Comparisons of Optimizers for Deep Learning (2019, background): “Others do not even report the value of (cid:15) used (Balles and Hennig, 2017; Zhang and Mitliagkas, 2017; Keskar and Socher, 2017; Chen et al., 2018; Zhou et al., 2018; Aitchison, 2018; Reddi et al., 2019; Luo et al., 2019).”
Adaptive Gradient Methods with Dynamic Bound of Learning Rate (2019, methodology): “Reddi et al. (2018) proposed AMSG RAD to solve this problem but recent work has pointed out AMSG RAD does not show evident improvement over A DAM (Keskar & Socher, 2017; Chen et al., 2018).”
Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks (2018, methodology): “1 is slightly weaker than the `2-boundedness assumption ‖∇f(x; ξ)‖2 ≤ G2 used in [Reddi et al., 2016; Chen et al., 2018].”
A Sufficient Condition for Convergences of Adam and RMSProp (2018, methodology): “When r = 1, Generic Adam reduces to the AdaEMA [6] with β = 0.”
Why ADAM Beats SGD for Attention Models (2019, background): “Since then, many works studied different interesting aspects of adaptive methods, see (Ward et al., 2018; Li & Orabona, 2018; Zhou et al., 2018a; Staib et al., 2019; Chen et al., 2018; Zou & Shen, 2018; Zhou et al., 2018b; Agarwal et al., 2018; Zou et al., 2019).”
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization (2019, background): “We also mention that most of the theoretical bounds depend on the dimension of the parameter (Reddi et al., 2018; Zhou et al., 2018; Chen et al., 2018; Zou et al., 2019; Chen et al., 2019; Luo et al., 2019).”
A Theory on Adam Instability in Large-Scale Machine Learning (2023, positive): “Chen et al. [2018] conducted an analysis that involved comparing the direction of the gradient and the direction of the update at each step of Adam dynamics, which is an idea we exploit as well.”
Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability (2021, methodology): “L-smoothness may be inappropriate when analyzing other optimization algorithms too It is common for optimization papers seemingly motivated by deep learning to analyze algorithms under the “non-convex but L-smooth”’ setting (Reddi et al., 2016; Agarwal et al., 2017; Zaheer et al., 2018; Zhou et al.,”
Why are Adaptive Methods Good for Attention Models? (2020, background): “Since then, many works studied different interesting aspects of adaptive methods, see [1, 6, 13, 16–18, 27, 30, 32–36].”
AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients (2020, methodology): “Similar to [13, 12, 27], for simplicity, we omit the de-biasing step (analysis applicable to de-biased version).”
Escaping Saddle Points with Adaptive Gradient Methods (2019, methodology): “(Chen et al., 2018; Reddi et al., 2018b; Zou et al., 2018) to understand and give theoretical guarantees for adaptive methods such as Adam and RMSProp.”
On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks (2018, methodology): “In general, gradient 1 A day earlier Chen et al. [7] release the O ( log ) convergence rate of AMSGrad in the non-convex stochastic setting online.”
A Simple Convergence Proof of Adam and Adagrad (2020, positive): “Chen et al. (2019) also provided a bound for Adagrad and Adam, but without convergence guarantees for Adam for any hyper-parameter choice, and with a worse dependency on β1. Finally, a convergence bound for Adam was introduced by Zou et al. (2019a). We recover the same scaling of the bound with resp”
Adaptive Gradient Methods at the Edge of Stability (2022, background): “Understanding adaptive gradient methods There have been a number of convergence analyses of adaptive gradient methods [7, 48, 26, 41, 44, 11], none of which model the behavior that we observe here.”
Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, neutral): “After the initial version of our work was made public, a few other analysis of adaptive gradient methods have also appeared like [7], [49] and [47].”
Domain-Independent Dominance of Adaptive Methods (2019, background): “Moreover, while most of the recently proposed variants do not provide formal guarantees for nonconvex problems, the few current convergence rate analyses in the literature (Zaheer et al., 2018; Chen et al., 2019) do not match SGD’s.”
A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, background): “However, it requires tuning extra algorithmic hyperparameters in addition to the learning rate and smoothing parameters [45], [48].”