Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization

Abstract

Although ADAM is a very popular algorithm for optimizing the weights of neural networks, it has been recently shown that it can diverge even in simple convex optimization examples. Several variants of ADAM have been proposed to circumvent this convergence issue. In this work, we study the ADAM algorithm for smooth nonconvex optimization under a boundedness assumption on the adaptive learning rate. The bound on the adaptive step size depends on the Lipschitz constant of the gradient of the objective function and provides safe theoretical adaptive step sizes. Under this boundedness assumption, we show a novel first order convergence rate result in both deterministic and stochastic contexts. Furthermore, we establish convergence rates of the function value sequence using the Kurdyka-Lojasiewicz property.

arXiv comment28 pages, 1 figure, published in ACML2020

References in corpus (20)

• On the difficulty of training Recurrent Neural Networks
• On the Convergence of Adam and Beyond
• On the Variance of the Adaptive Learning Rate and Beyond
• Adaptive Gradient Methods with Dynamic Bound of Learning Rate
• Splitting methods with variable metric for KL functions
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Adaptive Bound Optimization for Online Convex Optimization
• Quasi-hyperbolic momentum and Adam for deep learning
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• 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
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• WNGrad: Learn the Learning Rate in Gradient Descent
• Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization
• Global Convergence of Block Coordinate Descent in Deep Learning
• Escaping Saddle Points with Adaptive Gradient Methods
• On the Convergence of AdaBound and its Connection to SGD
• Efficient Full-Matrix Adaptive Regularization
• A Unified Approach to Adaptive Regularization in Online and Stochastic Optimization
• Linear Convergence of Adaptive Stochastic Gradient Descent

Cited by in corpus (3)

• Optimization for deep learning: theory and algorithms
• Long term dynamics of the subgradient method for Lipschitz path differentiable functions
• Convergence of adaptive algorithms for weakly convex constrained optimization