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

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