RMSProp and ADAM continue to be extremely popular algorithms for training neural nets but their theoretical convergence properties have remained unclear. Further, recent work has seemed to suggest that these algorithms have worse generalization properties when compared to carefully tuned stochastic gradient descent or its momentum variants. In this work, we make progress towards a deeper understanding of ADAM and RMSProp in two ways. First, we provide proofs that these adaptive gradient algorithms are guaranteed to reach criticality for smooth non-convex objectives, and we give bounds on the running time.

 Next we design experiments to empirically study the convergence and generalization properties of RMSProp and ADAM against Nesterov's Accelerated Gradient method on a variety of common autoencoder setups and on VGG-9 with CIFAR-10. Through these experiments we demonstrate the interesting sensitivity that ADAM has to its momentum parameter \beta_1. We show that at very high values of the momentum parameter (\beta_1 = 0.99) ADAM outperforms a carefully tuned NAG on most of our experiments, in terms of getting lower training and test losses. On the other hand, NAG can sometimes do better when ADAM's \beta_1 is set to the most commonly used value: \beta_1 = 0.9, indicating the importance of tuning the hyperparameters of ADAM to get better generalization performance.

 We also report experiments on different autoencoders to demonstrate that NAG has better abilities in terms of reducing the gradient norms, and it also produces iterates which exhibit an increasing trend for the minimum eigenvalue of the Hessian of the loss function at the iterates. Many optimization questions arising in machine learning can be cast as a finite sum optimization problem of the form: min x f (x) where f (x) = 1 k k i=1 f i (x). Most neural network problems also fall under a similar structure where each function f i is typically non-convex. A well-studied algorithm to solve such problems is Stochastic Gradient Descent (SGD), which uses updates of the form: x t+1 := x t − α∇f it (x t ), where α is a step size, andf it is a function chosen randomly from {f 1 , f 2 , . . . , f k } at time t. Often in neural networks, "momentum" is added to the SGD update to yield a two-step update process given as: v t+1 = µv t − α∇f it (x t ) followed by x t+1 = x t + v t+1 . This algorithm is typically called the Heavy-Ball (HB) method (or sometimes classical momentum), with µ > 0 called the momentum parameter (Polyak, 1987) . In the context of neural nets, another variant of SGD that is popular is Nesterov's Accelerated Gradient (NAG), which can also be thought of as a momentum method (Sutskever et al., 2013) , and has updates of the form v t+1 = µv t − α∇f it (x t + µv t ) followed by x t+1 = x t + v t+1 (see Algorithm 1 for more details).Momentum methods like HB and NAG have been shown to have superior convergence properties compared to gradient descent in the deterministic setting both for convex and non-convex functions (Nesterov, 1983; Polyak, 1987; Zavriev & Kostyuk, 1993; Ochs, 2016; O'Neill & Wright, 2017; Jin et al., 2017) . While (to the best of our knowledge) there is no clear theoretical justification in the stochastic case of the benefits of NAG and HB over regular SGD in general (Yuan et al., 2016; Kidambi et al., 2018; Wiegerinck et al., 1994; Orr & Leen, 1994; Yang et al., 2016; Gadat et al., 2018) , unless considering specialized function classes (Loizou & Richtárik, 2017) ; in practice, these momentum methods, and in particular NAG, have been repeatedly shown to have good convergence and generalization on a range of neural net problems (Sutskever et al., 2013; Lucas et al., 2018; Kidambi et al., 2018) .The performance of NAG (as well as HB and SGD), however, are typically quite sensitive to the selection of its hyper-parameters: step size, momentum and batch size (Sutskever et al., 2013) . Thus, "adaptive gradient" algorithms such as RMSProp (Algorithm 2) (Tieleman & Hinton, 2012) and ADAM (Algorithm 3) (Kingma & Ba, 2014) have become very popular for optimizing deep neural networks (Melis et al., 2017; Xu et al., 2015; Denkowski & Neubig, 2017; Gregor et al., 2015; Radford et al., 2015; Bahar et al., 2017; Kiros et al., 2015) . The reason for their widespread popularity seems to be the fact that they are believed to be easier to tune than SGD, NAG or HB. Adaptive gradient methods use as their update direction a vector which is the image under a linear transformation (often called the "diagonal pre-conditioner") constructed out of the history of the gradients, of a linear combination of all the gradients seen till now. It is generally believed that this "pre-conditioning" makes these algorithms much less sensitive to the selection of its hyperparameters. A precursor to these RMSProp and ADAM was outlined in Duchi et al. (2011) .Despite their widespread use in neural net problems, adaptive gradients methods like RMSProp and ADAM lack theoretical justifications in the non-convex setting -even with exact/deterministic gradients (Bernstein et al., 2018) . Further, there are also important motivations to study the behavior of these algorithms in the deterministic setting because of usecases where the amount of noise is controlled during optimization, either by using larger batches (Martens & Grosse, 2015; De et al., 2017; Babanezhad et al., 2015) or by employing variance-reducing techniques (Johnson & Zhang, 2013; Defazio et al., 2014) .Further, works like Wilson et al. (2017) and Keskar & Socher (2017) have shown cases where SGD (no momentum) and HB (classical momentum) generalize much better than RMSProp and ADAM with stochastic gradients. Wilson et al. (2017) also show that ADAM generalizes poorly for large enough nets and that RMSProp generalizes better than ADAM on a couple of neural network tasks (most notably in the character-level language modeling task). But in general it's not clear and no heuristics are known to the best of our knowledge to decide whether these insights about relative performances (generalization or training) between algorithms hold for other models or carry over to the full-batch setting.A summary of our contributions In this work we try to shed some light on the above described open questions about adaptive gradient methods in the following two ways.• To the best of our knowledge, this work gives the first convergence guarantees for adaptive gradient based standard neural-net training heuristics. Specifically we show run-time bounds for deterministic RMSProp and ADAM to reach approximate criticality on smooth non-convex functions, as well as for stochastic RMSProp under an additional assumption. Recently, Reddi et al. (2018) have shown in the setting of online convex optimization that there are certain sequences of convex functions where ADAM and RMSprop fail to converge to asymptotically zero average regret. We contrast our findings with Theorem 3 in Reddi et al. (2018) . Their counterexample for ADAM is constructed in the stochastic optimization framework and is incomparable to our result about deterministic ADAM. Our proof of convergence to approximate critical points establishes a key conceptual point that for adaptive gradient algorithms one cannot transfer intuitions about convergence from online setups to their more common use case in offline setups.• Our second contribution is empirical investigation into adaptive gradient methods, where our goals are different from what our theoretical results are probing. We test the convergence and generalization properties of RMSProp and ADAM and we compare their performance against NAG on a variety of autoencoder experiments on MNIST data, in both full and mini-batch settings. In the full-batch setting, we demonstrate that ADAM with very high values of the momentum parameter (β 1 = 0.99) matches or outperforms carefully tuned NAG and RMSProp, in terms of getting lower training and test losses. We show that as the autoencoder size keeps increasing, RMSProp fails to generalize pretty soon. In the mini-batch experiments we see exactly the same behaviour for large enough nets. We further validate this behavior on an image classification task on CIFAR-10 using a VGG-9 convolutional neural network, the results to which we present in the Appendix E. We note that recently it has been shown by Lucas et al. (2018) , that there are problems where NAG generalizes better than ADAM even after tuning β 1 . In contrast our experiments reveal controlled setups where tuning ADAM's β 1 closer to 1 than usual practice helps close the generalization gap with NAG and HB which exists at standard values of β 1 .Remark. Much after this work was completed we came to know of a related paper ( Li & Orabona, 2018 ) which analyzes convergence rates of a modification of AdaGrad (not RMSPRop or ADAM).After the initial version of our work was made public, a few other analysis of adaptive gradient methods have also appeared like Chen et al. (2018) , Zhou et al. (2018) and Zaheer et al. (2018) . To the best of our knowledge, we present the first theoretical guarantees of convergence to criticality for the immensely popular algorithms RMSProp and ADAM in their most commonly used setting of optimizing a non-convex objective.By our experiments, we have sought to shed light on the important topic of the interplay between adaptivity and momentum in training nets. By choosing to study textbook autoencoder architectures where various parameters of the net can be changed controllably we highlight the following two aspects that (a) the value of the gradient shifting hyperparameter ξ has a significant influence on the performance of ADAM and RMSProp and (b) ADAM seems to perform particularly well (often supersedes Nesterov accelerated gradient method) when its momentum parameter β 1 is very close to 1. On VGG-9 with CIFAR-10 and for the task of training autoencoders on MNIST we have verified these conclusions across different widths and depths of nets as well as in the full-batch and the mini-batch setting (with large nets) and under compression of the input/out image size. Curiously enough, this regime of β 1 being close to 1 is currently not within the reach of our proof techniques of showing convergence for ADAM. Our experiments give strong reasons to try to advance theory in this direction in future work.Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. Now we give the proof of Theorem 3.1.Proof. We define σ t := max k=1,.. ,t ∇f i k (x k ) and we solve the recursion for v t as, DISPLAYFORM0 . This lets us write the following bounds, DISPLAYFORM1 i and this lets us get the following bounds, DISPLAYFORM2 Now we invoke the bounded gradient assumption about the f i functions and replace in the above equation the eigenvalue bounds of the pre-conditioner by worst-case estimates µ max and µ min defined as, DISPLAYFORM3 Using the L-smoothness of f between consecutive iterates x t and x t+1 we have, DISPLAYFORM4 We note that the update step of stochastic RMSProp is x t+1 = x t − α(V t ) − 1 2 g t where g t is the stochastic gradient at iterate x t . Let H t = {x 1 , x 2 , .., x t } be the set of random variables corresponding to the first t iterates. The assumptions we have about the stochastic oracle give us the following relations, DISPLAYFORM5 f . Now we can invoke these stochastic oracle's properties and take a conditional (on H t ) expectation over g t of the L−smoothness in equation to get, DISPLAYFORM6 We now separately analyze the middle term in the RHS above in Lemma A.1 below and we get, DISPLAYFORM7 We substitute the above into equation 1 and take expectations over H t to get, DISPLAYFORM8 Doing the above replacements to upperbound the RHS of equation 2 and summing the inequation over t = 1 to t = T and taking the average and replacing the LHS by a lowerbound of it, we get, DISPLAYFORM9 Replacing into the RHS above the optimal choice of, DISPLAYFORM10 Thus stochastic RMSProp with the above step-length is guaranteed is reach −criticality in number of iterations given by, T ≤ DISPLAYFORM11 Lemma A.1. At any time t, the following holds, DISPLAYFORM12 Proof. DISPLAYFORM13 Now we introduce some new variables to make the analysis easier to present. Let a pi := [∇f p (x t )] i where p indexes the training data set, p ∈ {1, . . . , k}. (conditioned on H t , a pi s are constants) This implies, DISPLAYFORM14 where the expectation is taken over the oracle call at the t th update step. Further our instantiation of the oracle is equivalent to doing the uniformly at random sampling, (g t ) i ∼ {a pi } p=1,...,k .Given that we have, DISPLAYFORM15 i +di where we have defined DISPLAYFORM16 This leads to an explicit form of the needed expectation over the t th −oracle call as, DISPLAYFORM17 Substituting the above (and the definition of the constants a pi ) back into equation 3 we have, DISPLAYFORM18 Substituting this, the above expression can be written as, DISPLAYFORM19 Note that with this substitution, the RHS of the claimed lemma becomes, DISPLAYFORM20 Therefore our claim is proved if we show that for all i, DISPLAYFORM21 To further simplify, we define DISPLAYFORM22 −µ min . We therefore need to show, DISPLAYFORM23 We first bound d i by recalling the definition of σ f (from which it follows that a 2 pi ≤ σ 2 f ), DISPLAYFORM24 The inequality follows since β 2 ∈ (0, 1]Putting this all together, we get, DISPLAYFORM25 Now our assumption that for all x, sign(∇f p (x)) = sign(∇f q (x)) for all p, q ∈ {1, . . . , k} leads to the conclusion that the term a pi a qi ≥ 0. And we had already shown in equation 5 that DISPLAYFORM26 Thus we have shown that (a i 1 k )(q i a i ) ≥ 0 and this finishes the proof.
In this paper we prove convergence to criticality of (stochastic and deterministic) RMSProp and deterministic ADAM for smooth non-convex objectives and we demonstrate an interesting beta_1 sensitivity for ADAM on autoencoders.  This paper presents a convergence analysis of RMSProp and ADAM in the case of smooth non-convex functions