mlsanityData to 14 Oct 2026

Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness

arXiv 2609.30276 ↗First posted 12 Aug 2026cs.LG cs.SY eess.SYcited by 0

Not on the map. Why?

Abstract (arXiv)

We analyze the original same-step coordinate-wise AdaGrad under generalized smoothness and heavy-tailed noise with bounded variance. In this setting, local curvature may grow sub-quadratically with the gradient norm, and stochastic gradients are assumed to have only bounded conditional second moments. We show that unclipped AdaGrad can become anisotropically miscalibrated: under heavy-tailed noise, the adaptive denominator can learn the geometry of rare noise shocks rather than the local curvature of the objective, leading to a persistent directional distortion that blocks finite-horizon Euclidean progress. We then prove that clipping repairs this failure mode. Our main result is a finite-horizon high-probability guarantee for the original non-lagged AdaGrad update, yielding frac1Tsumt=0T-1|nabla f(xt)|2=Oleft(fracdbig(√log T + log frac1δbig)√Tright), and hence widetildemathcal O(varepsilon-2) complexity. This shows that, for AdaGrad under heavy-tailed noise, clipping is a structural stabilizer of the adaptive geometry rather than merely a robustness heuristic.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 50 of its 61 references that are in the map. First posted on arXiv 12 Aug 2026.

Builds on

50 of 61 references.

References · 50

  1. 2017Attention Is All You Needcited by 60,361
  2. 2019On the Convergence of Adam and Beyondcited by 841
  3. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 674
  4. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  6. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 183
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2020A Simple Convergence Proof of Adam and Adagradcited by 171
  9. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  10. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  11. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 126
  12. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
38 more
  1. 2023Convergence of Adam Under Relaxed Assumptionscited by 99
  2. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  3. 2018Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networkscited by 90
  4. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
  5. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  6. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  7. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  8. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  9. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  10. 2023High Probability Convergence of Stochastic Gradient Methodscited by 49
  11. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  12. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  13. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  14. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  15. 2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
  16. 2023Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimizationcited by 35
  17. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  18. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  19. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  20. 2023MoMo: Momentum Models for Adaptive Learning Ratescited by 24
  21. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  22. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  23. 2024Optimizing (L0, L1)-Smooth Functions by Gradient Methodscited by 19
  24. 2024Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailedcited by 18
  25. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  26. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  27. 2021AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methodscited by 15
  28. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 15
  29. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 14
  30. 2019Domain-independent Dominance of Adaptive Methodscited by 13
  31. 2022SP2: A Second Order Stochastic Polyak Methodcited by 13
  32. 2013Mini-Batch Primal and Dual Methods for SVMscited by 12
  33. 2023Stochastic Gradient Descent with Preconditioned Polyak Step-sizecited by 7
  34. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  35. 2025Mirror Descent Under Generalized Smoothnesscited by 5
  36. 2025Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothnesscited by 4
  37. 2024Enhancing Policy Gradient with the Polyak Step-Size Adaptioncited by 2
  38. 2024A Methodology Establishing Linear Convergence of Adaptive Gradient Methods under PL Inequalitycited by 2

Built on by

Not cited yet.