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

Alokendu Mazumder; Ayaan Mohd; Harshit Rawat; Arnab Roy; Mayank Baranwal; Punit Rathore

cs.LGAug 12, 2026

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

Authors: Alokendu Mazumder, Ayaan Mohd, Harshit Rawat, Arnab Roy, Mayank Baranwal, Punit Rathore

Organizations: Robert Bosch Center for Cyber Physical Systems, IISc Bengaluru · Undergraduate Program, IISc Bengaluru · Department of Computational Data Sciences, IISc Bengaluru · Department of Computer Science and Automation, IISc Bengaluru ·

Abstract

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 $\frac1T\sum_{t=0}^{T-1}\|\nabla f(x_t)\|^2=\mathcal{O}\left(\frac{d\big(\sqrt{\log T} + \log \frac{1}δ\big)}{\sqrt{T}}\right),$ and hence $\widetilde{\mathcal 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.

Figures & tables

	Allow unbounded gradient	Smooth	Noise	Rate	Conv.	Comments
Ward et al. [2020] [ 55 ]	$\times$	$L$	bounded variance	$O(\frac{\log T}{\delta^{3/2}\sqrt{T}}+\frac{\log^{2}T}{\delta^{2}T})$	best iterate	AdaGrad Norm
Li et al. [2020] 30	$\checkmark$	$L$	sub-Gaussian	$O\Big(\frac{d\log^{3/2}(T/\delta)}{\sqrt{T}}+\frac{d^{2}\log^{2}(T/\delta)}{T}\Big)$	best iterate	Delayed AdaGrad with momentum
Kavis et al. [2022] 23	$\times$	$L$	bounded variance	$O(\frac{\log T+\log(1/\delta)+\sqrt{\log(1/\delta)}}{\sqrt{T}})$	average stationarity	AdaGrad-Norm
Attia et al. [2023] 3	$\checkmark$	$L$	affine noise	$O\left(\frac{\log^{2}(T/\delta)}{\sqrt{T}}+\frac{\log^{4}(T/\delta)\log(1/\delta)}{T}\right)$	average stationarity	SGD with AdaGrad stepsize
Liu et al. [2023] 33	$\checkmark$	$L$	sub-Gaussian	$\mathcal{O}\left(\frac{d^{3}\log^{3/2}(dT/\delta)}{\sqrt{T}}+\frac{d^{3}\log^{3/2}(dT/\delta)\log(d/\delta)}{T}\right)$	average stationarity (1)	AdaGrad
Li et al. [2023] 27	$\checkmark^{(2)}$	$L$	bounded non-central $\alpha$ moment of stoc. grad.	$\mathcal{O}\Big(\frac{\log(1/\delta)}{\sqrt{T}}\Big)^{\$ }$	average stationarity	Clipped AdaGrad-Norm

Table 1: Summary of existing high probability convergence results for AdaGrad. None of these works show

\frac{1}{T}\sum_{t=1}^{T}\|\nabla f(x_{t})\|^{2}=\tilde{\mathcal{O}}(T^{-1/2})

for clipped AdaGrad under generalized smoothness. (1) Uses

L_{1}

average gradient norm stationarity. (2) They assume the objective function is uniformly upper-bounded.

\$$ denotes that the rates are given for

\alpha=2$ .

Stochastic Optimization Convergence

Stochastic optimization convergence studies how noisy, sampled, or delayed updates approach solutions and how fast they do so.

See all 212 papers

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
Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
Sep 26, 2026Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5Polyak-Ruppert Averaging Stochastic Optimization
Independent Researcher · HSE University · MBZUAI +3
Weak- $L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails
Oct 20, 2026Alyona Nekrasova, Makar Sidorov, Savelii Chezhegov +4Gradient Clipping Heavy-Tailed Stochastic Optimization
Independent researcher · Yaroslavl State University · Moscow Independent Research Institute of Artificial Intelligence +2

May 18, 2026J/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

Stochastic Optimization Convergence

Explore similar work

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

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise

Weak-LαL^αLα Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

Weak- $L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails