cs.LGNov 6, 2026

Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

Authors: Jeonseong Kim, Chenglin Fan

Organizations: Yonsei University Seoul, Korea · Seoul National University Seoul, Korea

Abstract

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.

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.
May 5, 2026

Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization

We provide a theoretical analysis of Adam under non-stationary stochastic objectives, separating two regimes: Euclidean tracking under adaptive strong monotonicity of the Adam-preconditioned mean-gradient operator, and high-probability projected stationarity guarantees under general LL-smooth objectives. In the tracking regime, we derive finite-time expected and high-probability bounds that decompose sharply into four components: initialization, objective drift, a first-moment tracking error governed by β1\beta_1, and a preconditioner perturbation governed by β2\beta_2. We characterize the burn-in time required for the transient terms to decay to the asymptotic tracking bound under constant and step-decay schedules. We also prove a high-probability bound on the average projected stationarity gap for Adam under distribution shift. Across both analyses, our bounds reveal a noise--drift tradeoff: in noise-dominated regimes, first-moment averaging and adaptive preconditioning can yield favorable upper guarantees, whereas in drift-dominated regimes, stale first-moment information and preconditioner perturbations can enlarge Adam's tracking guarantee, potentially allowing vanilla SGD to attain a smaller tracking error. Our explicit (β1,β2,ϵ)(\beta_1,\beta_2,\epsilon)-dependent bounds identify mechanisms through which adaptive step-sizing can help or hurt under nonstationarity and provide theoretical explanations consistent with Adam's empirical instability and stabilization under distribution shift.
Nov 2, 2026

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

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.