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 Adam, AMSGrad, AdaGrad. Despite their popularity in training deep neural networks (DNNs), the convergence of these algorithms for solving  non-convex problems remains an open question. In this paper, we develop an analysis framework and a set of mild sufficient conditions that guarantee the convergence of the Adam-type methods, with a convergence rate of order   $O(\log{T}/\sqrt{T})$ for non-convex stochastic optimization. Our convergence analysis applies to a new algorithm called AdaFom (AdaGrad with First Order Momentum). We show that the conditions are essential, by identifying concrete examples in which violating the conditions makes an algorithm diverge. Besides providing one of the first comprehensive analysis for Adam-type methods in the non-convex setting, our results can also help the practitioners to easily  monitor the progress of algorithms and determine their convergence behavior. First-order optimization has witnessed tremendous progress in the last decade, especially to solve machine learning problems BID3 . Almost every first-order method obeys the following generic form BID4 ), x t+1 = x t − α t ∆ t , where x t denotes the solution updated at the tth iteration for t = 1, 2, . . . , T , T is the number of iterations, ∆ t is a certain (approximate) descent direction, and α t > 0 is some learning rate. The most well-known first-order algorithms are gradient descent (GD) for deterministic optimization (Nesterov, 2013; BID5 and stochastic gradient descent (SGD) for stochastic optimization (Zinkevich, 2003; Ghadimi & Lan, 2013) , where the former determines ∆ t using the full (batch) gradient of an objective function, and the latter uses a simpler but more computationally-efficient stochastic (unbiased) gradient estimate.Recent works have proposed a variety of accelerated versions of GD and SGD (Nesterov, 2013) . These achievements fall into three categories: a) momentum methods (Nesterov, 1983; Polyak, 1964; BID10 which carefully design the descent direction ∆ t ; b) adaptive learning rate methods BID1 BID9 Zeiler, 2012; BID7 which determine good learning rates α t , and c) adaptive gradient methods that enjoy dual advantages of a) and b). In particular, Adam (Kingma & Ba, 2014) , belonging to the third type of methods, has become extremely popular to solve deep learning problems, e.g., to train deep neural networks. Despite its superior performance in practice, theoretical investigation of Adam-like methods for non-convex optimization is still missing.Very recently, the work (Reddi et al., 2018) pointed out the convergence issues of Adam even in the convex setting, and proposed AMSGrad, a corrected version of Adam. Although AMSGrad has made a positive step towards understanding the theoretical behavior of adaptive gradient methods, the convergence analysis of (Reddi et al., 2018) was still very restrictive because it only works for convex problems, despite the fact that the most successful applications are for non-convex problems. Apparently, there still exists a large gap between theory and practice. To the best of our knowledge,• (Practicality) The sufficient conditions we derive are simple and easy to check in practice. They can be used to either certify the convergence of a given algorithm for a class of problem instances, or to track the progress and behavior of a particular realization of an algorithm.• (Tightness and Insight) We show the conditions are essential and "tight", in the sense that violating them can make an algorithm diverge. Importantly , our conditions provide insights on how oscillation of a so-called "effective stepsize" (that we define later) can affect the convergence rate of the class of algorithms. We also provide interpretations of the convergence conditions to illustrate why under some circumstances, certain Adam-type algorithms can outperform SGD. Notations We use z = x/y to denote element-wise division if x and y are both vectors of size d; x y is element-wise product, x 2 is element-wise square if x is a vector, √ x is element-wise square root if x is a vector, (x) j denotes jth coordinate of x, x is x 2 if not otherwise specified. We use [N ] to denote the set {1, · · · , N }, and use O(·), o(·), Ω(·), ω(·) as standard asymptotic notations. We provided some mild conditions to ensure convergence of a class of Adam-type algorithms, which includes Adam, AMSGrad, AdaGrad, AdaFom, SGD, SGD with momentum as special cases. Apart from providing general convergence guarantees for algorithms, our conditions can also be checked in practice to monitor empirical convergence. To the best of our knowledge, the convergence of Adam-type algorithm for non-convex problems was unknown before. We also provide insights on how oscillation of effective stepsizes can affect convergence rate for the class of algorithms which could be beneficial for the design of future algorithms. This paper focuses on unconstrained non-convex optimization problems, and one future direction is to study a more general setting of constrained non-convex optimization.
We analyze convergence of Adam-type algorithms and provide mild sufficient conditions to guarantee their convergence, we also show  violating the conditions can makes an algorithm diverge. Presents a convergence analysis in the non-convex setting for a family of optimization algorithms. This paper investigates the convergence condition of Adam-type optimizers in the unconstrained non-convex optimization problems.