SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance

2023/02/17 by Attia, Amit, Koren, Tomer · 5 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2302.08783

Abstract

We study Stochastic Gradient Descent with AdaGrad stepsizes: a popular adaptive (self-tuning) method for first-order stochastic optimization. Despite being well studied, existing analyses of this method suffer from various shortcomings: they either assume some knowledge of the problem parameters, impose strong global Lipschitz conditions, or fail to give bounds that hold with high probability. We provide a comprehensive analysis of this basic method without any of these limitations, in both the convex and non-convex (smooth) cases, that additionally supports a general ``affine variance'' noise model and provides sharp rates of convergence in both the low-noise and high-noise~regimes.

Cited by

• Design Criteria for SGD Preconditioners: Local Conditioning, Noise Floors, and Basin Stability
• Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
• A regret minimization approach to fixed-point iterations
• Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
• Simple Convergence Proof of Adam From a Sign-like Descent Perspective

Related

• The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
• High Probability Convergence of Stochastic Gradient Methods
• Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution