On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization

Abstract

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. 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.

25 pages, 2 tables. Published in Transactions on Machine Learning Research (TMLR)

References in corpus (14)

• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• The Marginal Value of Adaptive Gradient Methods in Machine Learning
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent

Cited by in corpus (43)

• Optimization for deep learning: theory and algorithms
• AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• A Simple Convergence Proof of Adam and Adagrad
• A Sufficient Condition for Convergences of Adam and RMSProp
• AdaX: Adaptive Gradient Descent with Exponential Long Term Memory
• Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability
• Robust Federated Recommendation System
• Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration
• A High Probability Analysis of Adaptive SGD with Momentum
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• A Qualitative Study of the Dynamic Behavior for Adaptive Gradient Algorithms
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Gradient descent with momentum --- to accelerate or to super-accelerate?
• On the Convergence of Decentralized Adaptive Gradient Methods
• AdaSGD: Bridging the gap between SGD and Adam
• A new regret analysis for Adam-type algorithms
• Recursive Estimation for Sparse Gaussian Process Regression
• MixML: A Unified Analysis of Weakly Consistent Parallel Learning
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• On the Trend-corrected Variant of Adaptive Stochastic Optimization Methods
• Adaptive Gradient Methods Can Be Provably Faster than SGD after Finite Epochs
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• On Higher-order Moments in Adam
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits
• Understanding the Role of Adversarial Regularization in Supervised Learning
• Binary Search and First Order Gradient Based Method for Stochastic Optimization
• A Comprehensive Study on Optimization Strategies for Gradient Descent In Deep Learning
• Toward Communication Efficient Adaptive Gradient Method
• Rapidly Adapting Moment Estimation
• A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization