Abstract
The Adaptive Momentum Estimation (Adam) algorithm is highly effective in training various deep learning tasks. Despite this, there's limited theoretical understanding for Adam, especially when focusing on its vanilla form in non-convex smooth scenarios with potential unbounded gradients and affine variance noise. In this paper, we study vanilla Adam under these challenging conditions. We introduce a comprehensive noise model which governs affine variance noise, bounded noise and sub-Gaussian noise. We show that Adam can find a stationary point with a $\mathcal{O}(\text{poly}(\log T)/\sqrt{T})$ rate in high probability under this general noise model where $T$ denotes total number iterations, matching the lower rate of stochastic first-order algorithms up to logarithm factors. More importantly, we reveal that Adam is free of tuning step-sizes with any problem-parameters, yielding a better adaptation property than the Stochastic Gradient Descent under the same conditions. We also provide a probabilistic convergence result for Adam under a generalized smooth condition which allows unbounded smoothness parameters and has been illustrated empirically to more accurately capture the smooth property of many practical objective functions.
Introduction
Despite its massive empirical success, Adam—the "workhorse" optimizer of deep learning—has historically been a theoretical challenge. Most mathematical proofs for optimization algorithms rely on two restrictive assumptions: Bounded Gradients, where gradients never exceed a certain magnitude, and Simple Noise, where stochastic gradient noise is uniform. In practice, gradients in deep learning often explode, and noise frequently scales with the size of the gradient itself (affine variance).
This paper provides a rigorous theoretical guarantee for why vanilla Adam works so well even when these assumptions are removed. By proving convergence under a "generalized smoothness" condition, the authors align theoretical analysis with the complex landscapes of modern models like Transformers.
Theoretical Framework
To bridge the gap between theory and practice, the authors introduce several sophisticated mathematical techniques:
- Proxy Iterative Sequences: The authors introduce an auxiliary sequence ($y_s$) to handle momentum and adaptive step-sizes, allowing for a more effective application of the "descent lemma" than raw iterates ($x_s$) alone.
- Proxy Step-Sizes: To address the correlation between adaptive step-sizes and current gradients, a "proxy" step-size is constructed to decouple this relationship, making the analysis tractable without altering the algorithm.
- Inductive Bounding: In the absence of bounded gradient assumptions, an inductive argument is used to prove that gradients remain controlled throughout the optimization process.
- Generalized Smoothness $(L_0, L_1)$: Instead of standard $L$-smoothness, the authors use a flexible model where smoothness can grow with the gradient. This model has been shown empirically to describe Large Language Models (LLMs) more accurately.
Key Results and Convergence Analysis
The paper establishes that Adam achieves a near-optimal convergence rate of $\tilde{O}(1/\sqrt{T})$ under highly relaxed conditions, including affine noise and generalized smoothness.
- Near-Optimal Rate: Under standard smoothness, Adam finds a stationary point at a rate of $\tilde{O}(1/\sqrt{T})$. This matches the theoretical lower bound for first-order stochastic optimizers, up to logarithmic factors.
- Generalized Smoothness Success: Even under the $(L_0, L_1)$ condition, Adam maintains a convergence rate of $O(\text{poly}(\log T)/\sqrt{T})$, provided hyper-parameters (like the learning rate and $\beta_2$) are tuned relative to the total iterations $T$.
- Robustness and Adaptivity: The analysis confirms that Adam’s coordinate-wise normalization allows it to handle regions of rapid gradient growth. Furthermore, for the RMSProp variant, the convergence rate is shown to be "noise-adaptive," effectively ignoring noise that scales with the gradient.
- High Probability Guarantees: Unlike many studies that prove results in expectation (on average), this paper provides results "with high probability" (w.h.p.), offering a stronger guarantee for individual training runs.
Limitations and Future Work
While providing a significant step forward in Adam's theoretical foundation, the authors note several areas for improvement:
- Experimental Validation: The theoretical hyper-parameter settings suggested (e.g., $\beta_2 = 1 - c/T$) require empirical testing to see if they align with current best practices in large-scale training.
- Tightness of the Bound: A small gap remains between these results and the absolute theoretical lower bound due to the $\text{poly}(\log T)$ factors.
- Hyper-parameter Knowledge: Some results for generalized smoothness require knowing problem-specific parameters (like $L_0$ and $L_1$) to tune the step-size, which may not always be feasible in practice.
Summary updated