A High Probability Analysis of Adaptive SGD with Momentum

2020/07/28 by Xiaoyu Li, Francesco Orabona, Li, Xiaoyu +1 · 8 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2007.14294

arxiv created 2020/07/28 · openalex publication_date 2020/07/28 · arxiv updated 2020/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.

Citations

• A Stochastic Approximation Method
• 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
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• PyTorch: An Imperative Style, High-Performance Deep Learning Library

Cited by

• High-Probability Convergence Guarantees of Decentralized SGD
• Stochastic Bilevel Optimization with Heavy-Tailed Noise
• Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds
• Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises
• Online Learning-guided Learning Rate Adaptation via Gradient Alignment
• Breaking a Logarithmic Barrier in the Stopping Time Convergence Rate of Stochastic First-order Methods
• Convergence of Clipped-SGD for Convex (L₀,L₁)-Smooth Optimization with Heavy-Tailed Noise
• A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance

Related

• A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Acceleration
• An Improved Analysis of Stochastic Gradient Descent with Momentum
• Learning-rate-free Momentum SGD with Reshuffling Converges in Nonsmooth Nonconvex Optimization
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• On the Generalization of Stochastic Gradient Descent with Momentum