The Convergence Behavior of Adam under Heavy-Tailed Noise

Research Question and Approach

This paper investigates the theoretical behavior of the Adam optimizer in environments where stochastic gradients exhibit heavy-tailed noise. Unlike classical analyses that assume bounded variance (the p=2 case), this work considers the more realistic setting where gradients only possess a bounded p-th central moment for p in (1, 2]. The author generalizes the online-to-nonconvex conversion framework to accommodate this heavy-tailed martingale-difference noise, allowing for a rigorous discounted regret analysis of the exact vector-form Adam update without requiring restrictive parameter coupling.

The study establishes that the standard Adam optimizer converges to (rho, epsilon)-stationary points under heavy-tailed noise. A key technical contribution is the derivation of a discounted regret bound that accounts for the heavy-tailed nature of the noise through a p-dependent factor. The analysis reveals that in its plain form, Adam exhibits suboptimal iteration complexity that persists even in the bounded-variance case. However, when the domain radius is known and utilized to clip the online learner's output, the convergence rate improves to match the optimal complexity for non-smooth stochastic optimization.

Adaptive gradient methods like Adam are the standard for training deep neural networks, yet their theoretical foundations have historically lagged behind their empirical success, particularly in non-ideal stochastic environments. By providing the first convergence guarantees for the exact Adam algorithm under heavy-tailed noise, this work bridges a significant gap between theory and practice. It offers practitioners a clearer understanding of when Adam is robust and how algorithmic modifications—such as domain-based output control—can restore optimal performance in challenging training regimes.