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

Zijian Liu

math.OCMay 18, 2026

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

Authors: Zijian Liu

Organizations: Stern School of Business, New York University

Abstract

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.

Explore similar work

Jul 29, 2026cs.LG

The Convergence Behavior of Adam under Heavy-Tailed Noise

We establish the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise. While several Adam variants are known to achieve optimal iteration complexity in bounded-variance nonsmooth nonconvex optimization, little is understood about their behavior when stochastic gradients admit only a bounded

p

-th central moment for some

p \in (1,2]

, a setting increasingly observed in modern deep learning. To address this gap, we generalize the recent online-to-nonconvex conversion framework to accommodate heavy-tailed martingale-difference noise. Building on this generalized framework, we develop a discounted regret analysis for Adam, without restrictive parameter coupling. Our results show that Adam converges to

(ρ,ε)

-stationary points under heavy-tailed noise. However, it exhibits a suboptimal iteration complexity and

p

-dependent convergence, a suboptimality that persists even in the bounded-variance case (

p=2

). Specifically, the

ε

-dominant term in the iteration complexity for reaching in-expectation stationarity is

T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{5p}{3p-4}}ε^{-\left(\frac{5p}{3p-4}+\frac{3}{2}\right)}\right)

for

p\in(\frac{4}{3},2]

, which simplifies to

T=\mathrm{O}(ε^{-13/2})

when

p=2

. When the domain radius is known and used to control the online-learner output, a standard setup in related literature, the convergence rate improves to match the optimal complexity. In this case, the

ε

-dominant iteration complexity is

T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{p}{p-1}}ε^{-\left(\frac{p}{p-1}+\frac{3}{2}\right)}\right)

for

p\in(1,2]

, which simplifies to

T=\mathrm{O}(ε^{-7/2})

when

p=2

. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.

Yijiang Pang

Adam Convergence Analysis Convex Optimization Long-Tailed Distribution

Ask PDF

May 30, 2026math.OC

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite

p

-th moment for

p\in\left(1,2\right)

, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent (

\textsf{SGD}

), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent (

\textsf{SMD}

) and Accelerated Stochastic Mirror Descent (

\textsf{ASMD}

) in convex optimization, and for

\textsf{SGD}

and Stochastic Gradient Descent with Momentum (

\textsf{SGDM}

) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.

Zijian Liu

Stochastic Smooth Convex Optimization Stochastic Gradient Descent Convex Optimization Stochastic

Ask PDF

Jul 9, 2026cs.LG

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

Stochastic gradient descent (SGD) is a cornerstone of modern optimization. While its performance under heavy-tailed noise is often addressed through specialized modifications such as gradient clipping or normalization, we investigate a more fundamental question: how does vanilla SGD, particularly with momentum, perform in the presence of heavy-tailed noise? In this paper, we refine existing convergence results for vanilla SGD and, more importantly, provide the first comprehensive convergence analysis of vanilla SGD with momentum for strongly convex, convex, and nonconvex objectives, without employing any gradient control mechanisms. Our results demonstrate that the obtained convergence rates are inferior to the optimal rates achieved by clipped or normalized variants of SGD, thereby revealing inherent limitations of vanilla methods under heavy-tailed noise. The theoretical findings are supported by experiments on synthetic functions.

Ryusei Yamada, Naoki Sato, Hideaki Iiduka

Stochastic Gradient Descent Convergence Analysis Long-Tailed Distribution Gradient Clipping

Ask PDF