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

Abstract

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 the Adam, AMSGrad and AdaGrad. Despite their popularity in training deep neural networks, the convergence of these algorithms for solving nonconvex problems remains an open question. This paper provides a set of mild sufficient conditions that guarantee the convergence for the Adam-type methods. We prove that under our derived conditions, these methods can achieve the convergence rate of order $O(\log T/\sqrt{T})$ for nonconvex stochastic optimization. We show the conditions are essential in the sense that violating them may make the algorithm diverge. Moreover, we propose and analyze a class of (deterministic) incremental adaptive gradient algorithms, which has the same $O(\log T/\sqrt{T})$ convergence rate. Our study could also be extended to a broader class of adaptive gradient methods in machine learning and optimization.

References in corpus (11)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• Equilibrated adaptive learning rates for non-convex optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Nostalgic Adam: Weighting more of the past gradients when designing the adaptive learning rate
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Cited by in corpus (28)

• On Empirical Comparisons of Optimizers for Deep Learning
• Optimization for deep learning: theory and algorithms
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• A Deep Learning Algorithm for High-Dimensional Exploratory Item Factor Analysis
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration
• LaProp: Separating Momentum and Adaptivity in Adam
• Puzzle-AE: Novelty Detection in Images through Solving Puzzles
• Last-iterate convergence analysis of stochastic momentum methods for neural networks
• Adam${}^{+}$: A Stochastic Method with Adaptive Variance Reduction
• Mutually exciting point process graphs for modelling dynamic networks
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• An Adaptive Gradient Method with Energy and Momentum
• A Control Theoretic Framework for Adaptive Gradient Optimizers in Machine Learning
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Block-Randomized Stochastic Proximal Gradient for Low-Rank Tensor Factorization
• Generalized Left-Localized Cayley Parametrization for Optimization with Orthogonality Constraints
• SAdam: A Variant of Adam for Strongly Convex Functions
• On the Trend-corrected Variant of Adaptive Stochastic Optimization Methods
• Data Augmentation for Text Generation Without Any Augmented Data
• CRAUM-Net: Contextual Recursive Attention with Uncertainty Modeling for Salient Object Detection
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study
• Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits
• ACMo: Angle-Calibrated Moment Methods for Stochastic Optimization
• Optimizing Convergence for Iterative Learning of ARIMA for Stationary Time Series
• Rapidly Adapting Moment Estimation