Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

Weiming Ou; Xiao Wang

math.OCSep 26, 2026

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

Authors: Weiming Ou, Xiao Wang

Organizations: Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics

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/\sqrt 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/\sqrt{T})$ .

Figures & tables

Theorem	Assumptions	Guarantee type	Result
3.1	Sub-Gaussian + bounded iterates	Last iterate	No universal vanishing rate a
3.5	Finite variance + bounded iterates	Average iterate, high probability	No polynomial rate b with $\operatorname{polylog}(1/\delta)$
3.8	Finite variance	Average iterate	Lower bound c $\Omega(1)$
3.10	Sub-Gaussian	Average iterate	Lower bound c $\Omega(\log T/\sqrt{T})$
3.14	ABC condition + bounded iterates	Average iterate	Upper bound $O(T^{-1}+\sqrt{C/T})$

Table 1: Results for standard unprojected AdaGrad-Norm and AdaGrad on smooth convex objectives with conditionally unbiased oracles. Errors are in expectation unless high probability is specified. a For each prescribed

r_{T}\to 0

, one fixed infinite-horizon instance satisfies

\mathbb{E}[\Delta_{T_{n}}]/r_{T_{n}}\to\infty

. b One fixed infinite-horizon instance, uniformly averaged output, and any prescribed radius

D>0

; the excluded bounds have polynomial decay in

T

and only polynomial dependence on

\log(1/\delta)

. c Horizon-dependent families with fixed algorithm parameters and no common trajectory radius. The upper bound is an explicit ABC extension of classical analysis.

Explore similar work

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad
May 18, 2026Zijian LiuStochastic Optimization Nonconvex Stochastic Optimization
Stern School of Business, New York University
New Bounds for the Last Iterate of the Stochastic subGradient Method
Jun 23, 2026Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1Stochastic Optimization Last-Iterate Convergence
Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom
Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
May 15, 2026Dmitry KovalevStochastic Optimization Gradient Clipping
Yandex Research

May 18, 2026, math.OCJ/K move · Enter open · S save

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Adaptive Gradient Methods+1

Open paper AskPDF arXiv

Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular

\mathtt{Adam}

and

\mathtt{AdamW}

, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case,

\mathtt{AdaGrad}

, the origin of adaptive gradient methods. We provide the first provable convergence rate for

\mathtt{AdaGrad}

in non-convex optimization when the tail index

p

satisfies

4/3<p\leq2

. Notably, this result is achieved without requiring any prior knowledge of

p

and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by

\mathtt{AdaGrad}

. Lastly, we consider

\mathtt{AdaGrad}\text{-}\mathtt{Norm}

, a popular variant of

\mathtt{AdaGrad}

in theoretical studies, and show an improved rate that holds for any

1<p\leq2

under an extra mild assumption.

Abstract

Explore similar work

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

New Bounds for the Last Iterate of the Stochastic subGradient Method

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients