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

2023/02/17 by Amit Attia, Attia, Amit, Tomer Koren +1 · 7 citations
Computer Science · Economics, Econometrics and Finance · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Stochastic processes and financial applications

paper · pdf · doi:10.48550/arxiv.2302.08783

openalex publication_date 2023/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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
• On the O(\frac√(d)K^1/4) Convergence Rate of AdamW Measured by ℓ₁ Norm
• Fast Stochastic Second-Order Adagrad for Nonconvex Bound-Constrained Optimization

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