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 ∈ (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=Oleft(Delta ρ1/2(G+σ)^frac5p3p-4ε^-left(frac5p3p-4+frac32right)right) for p∈(frac43,2], which simplifies to T=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=Oleft(Delta ρ1/2(G+σ)^fracpp-1ε^-left(fracpp-1+frac32right)right) for p∈(1,2], which simplifies to T=O(ε-7/2) when p=2. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.