A Sufficient Condition for Convergences of Adam and RMSProp

By Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang. 2018

462 citations recorded by the source corpus.

Adam and RMSProp are two of the most influential adaptive stochastic algorithms for training deep neural networks, which have been pointed out to be divergent even in the convex setting via a few simple counterexamples. Many attempts, such as decreasing an adaptive learning rate, adopting a big batch size, incorporating a temporal decorrelation technique, seeking an analogous surrogate, etc., have been tried to promote Adam/RMSProp-type algorithms to converge. In contrast with existing approaches, we introduce an alternative easy-to-check sufficient condition, which merely depends on the parameters of the base learning rate and combinations of historical second-order moments, to guarantee the global convergence of generic Adam/RMSProp for solving large-scale non-convex stochastic optimization. Moreover, we show that the convergences of several variants of Adam, such as AdamNC, AdaEMA, etc., can be directly implied via the proposed sufficient condition in the non-convex setting. In addition, we illustrate that Adam is essentially a specifically weighted AdaGrad with exponential moving average momentum, which provides a novel perspective for understanding Adam and RMSProp. This observation coupled with this sufficient condition gives much deeper interpretations on their divergences. At last, we validate the sufficient condition by applying Adam and RMSProp to tackle a certain counterexample and train deep neural networks. Numerical results are exactly in accord with our theoretical analysis.

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): “…(cid:15) at the common default value of 10 − 8 for Adam and 10 − 10 for RMSProp (Tieleman and Hinton, 2012; Kingma and Ba, 2015; Dozat, 2016; Balles and Hennig, 2017; Loshchilov and Hutter, 2017; Zou and Shen, 2018; Ma and Yarats, 2018; Bernstein et al., 2018; Chen et al., 2019; Zou et al., 2019).”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “(Zou et al. (2019), Lemma 15) For any non-negative sequence a0, a1, . . . , aT , we have T∑ t=1 at a0 + ∑t s=1 as ≤ log ( a0 + T∑ t=1 at ) − log(a0).”
A Simple Convergence Proof of Adam and Adagrad (2020, unknown): “The coordinate-wise version of Adagrad was also tackled by Zou et al. (2019b), oﬀering a convergence result for Adagrad with either heavy-ball or Nesterov style momentum.”
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).”
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.”
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).”
Robust Federated Recommendation System (2020, background): “However, in learning FRS, SGD often leads to poor performance due to the problem of vanishing gradients, slow convergence, and its inability to handle sparse data [43; 42].”
Linear Convergence of Adaptive Stochastic Gradient Descent (2019, methodology): “Adaptive gradient methods introduced in [16, 17] update the stepsize on the ﬂy: They either adapt a vector of per-coefﬁcient stepsizes [18, 19, 20, 21, 22, 23] or a single stepsize depending on the norm of the gradient [24, 25, 26].”