Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
Abstract
AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal \textbf{last-iterate} rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield \textbf{high-probability average-iterate} rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Ω(log T/√T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/√T).
Related
- SCMO: Stochastic Control for Optimization over Probability Measures on Infinite-Dimensional Spaces
- High-Probability Sampled-Data Stabilization of General Nonlinear Stochastic Systems
- Addendum to "Optimal Steering of a Linear Stochastic System to a Final Probability Distribution, Part II"
- (Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator
- Foundations of Stochastic Lexical Calculus: Semantic Descent and Random Dynamics on Probability Simplices
BibTeX
@misc{ou2026revisiting,
title = {{Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds}},
author = {Weiming Ou and Xiao Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32729},
eprint = {2609.32729},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32729},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
AU - Weiming Ou
AU - Xiao Wang
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32729
UR - https://arxiv.org/abs/2609.32729
AB - AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal \textbf{last-iterate} rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield \textbf{high-probability average-iterate} rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Ω(log T/√T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/√T).
ER -