On the Convergence of Adaptive Gradient Methods for Nonconvex
  Optimization
  Adaptive gradient methods are workhorses in deep learning. However, the
convergence guarantees of adaptive gradient methods for nonconvex optimization
have not been thoroughly studied. In this paper, we provide a fine-grained
convergence analysis for a general class of adaptive gradient methods including
AMSGrad, RMSProp and AdaGrad. For smooth nonconvex functions, we prove that
adaptive gradient methods in expectation converge to a first-order stationary
point. Our convergence rate is better than existing results for adaptive
gradient methods in terms of dimension, and is strictly faster than stochastic
gradient decent (SGD) when the stochastic gradients are sparse. To the best of
our knowledge, this is the first result showing the advantage of adaptive
gradient methods over SGD in nonconvex setting. In addition, we also prove high
probability bounds on the convergence rates of AMSGrad, RMSProp as well as
AdaGrad, which have not been established before. Our analyses shed light on
better understanding the mechanism behind adaptive gradient methods in
optimizing nonconvex objectives.
