A High Probability Analysis of Adaptive SGD with Momentum
arXiv:2007.14294
Abstract
Stochastic Gradient Descent (SGD) and its variants are the most used algorithms in machine learning applications. In particular, SGD with adaptive learning rates and momentum is the industry standard to train deep networks. Despite the enormous success of these methods, our theoretical understanding of these variants in the nonconvex setting is not complete, with most of the results only proving convergence in expectation and with strong assumptions on the stochastic gradients. In this paper, we present a high probability analysis for adaptive and momentum algorithms, under weak assumptions on the function, stochastic gradients, and learning rates. We use it to prove for the first time the convergence of the gradients to zero in high probability in the smooth nonconvex setting for Delayed AdaGrad with momentum.
References in corpus (7)
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- On the Convergence of Adam and Beyond
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
- On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
- A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
- Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent
Cited by in corpus (5)
- A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
- High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails
- Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Łojasiewicz Condition
- Dynamic Regret Analysis for Online Meta-Learning
- A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization