cs.LGNov 2, 2026

On the Convergence of Vanilla Adam under Heavy-Tailed Noise and Index Sampling

Authors: Kanata Oowada, Hideaki Iiduka

Organizations: Meiji University

Abstract

Understanding how stochastic gradient noise affects the convergence of Adaptive Moment Estimation (Adam) is an important problem in stochastic optimization, particularly when the noise exhibits heavy-tailed behavior. In this paper, we investigate the convergence of vanilla Adam in both the expected risk and the empirical risk minimization, focusing on the effects of heavy-tailed noise and its relationship to index sampling. For the expected risk minimization, we establish convergence guarantees under Hölder smoothness and bounded p\mathfrak{p}-th moment assumptions, allowing stochastic gradient noise with infinite variance. Our analysis provides explicit upper bounds on the expected squared gradient norm and shows that the iteration-dependent convergence term decays more slowly as p\mathfrak{p} decreases. For the empirical risk minimization, we establish asymptotic and non-asymptotic convergence guarantees and demonstrate that heavy-tailed population noise can deteriorate convergence bounds through dataset-dependent constants as the dataset size increases. Numerical experiments support our theoretical findings on the effects of heavy-tailed noise.

Figures & tables

Explore similar work

Jul 29, 2026

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 pp-th central moment for some p∈(1,2]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 pp-dependent convergence, a suboptimality that persists even in the bounded-variance case (p=2p=2). Specifically, the εε-dominant term in the iteration complexity for reaching in-expectation stationarity is T=O(Δρ1/2(G+σ)5p3p−4ε−(5p3p−4+32))T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{5p}{3p-4}}ε^{-\left(\frac{5p}{3p-4}+\frac{3}{2}\right)}\right) for p∈(43,2]p\in(\frac{4}{3},2], which simplifies to T=O(ε−13/2)T=\mathrm{O}(ε^{-13/2}) when p=2p=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=O(Δρ1/2(G+σ)pp−1ε−(pp−1+32))T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{p}{p-1}}ε^{-\left(\frac{p}{p-1}+\frac{3}{2}\right)}\right) for p∈(1,2]p\in(1,2], which simplifies to T=O(ε−7/2)T=\mathrm{O}(ε^{-7/2}) when p=2p=2. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.
Nov 6, 2026

Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

Adam estimates second moments coordinatewise, but typically adds the same scalar ε\varepsilon to every denominator. We study how this shared ε\varepsilon affects convergence when noise and curvature vary across coordinates. Under coordinatewise finite-pp noise moments, p∈(1,2]p\in(1,2], choosing εi\varepsilon_i from the noise and curvature bounds for each coordinate attains the heavy-tailed ℓ1\ell_1-stationarity benchmark O(T−p−13p−2)O(T^{-\frac{p-1}{3p-2}}), matching the known optimal time exponent for smooth nonconvex stochastic optimization. For 1<p<21<p<2, Adam with a shared εt\varepsilon_t admits a lower bound of order Ω(T−p−12p)Ω(T^{-\frac{p-1}{2p}}). This lower bound holds for every predictable scalar choice of ηtη_t, β1,tβ_{1,t}, β2,tβ_{2,t}, and εt\varepsilon_t, precluding a dimension-uniform benchmark rate for this class.
May 18, 2026

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

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 Adam\mathtt{Adam} and AdamW\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, AdaGrad\mathtt{AdaGrad}, the origin of adaptive gradient methods. We provide the first provable convergence rate for AdaGrad\mathtt{AdaGrad} in non-convex optimization when the tail index pp satisfies 4/3<p≤24/3<p\leq2. Notably, this result is achieved without requiring any prior knowledge of pp 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 AdaGrad\mathtt{AdaGrad}. Lastly, we consider AdaGrad-Norm\mathtt{AdaGrad}\text{-}\mathtt{Norm}, a popular variant of AdaGrad\mathtt{AdaGrad} in theoretical studies, and show an improved rate that holds for any 1<p≤21<p\leq2 under an extra mild assumption.