Abstract
Adaptive optimizers like Adam and RMSProp are the backbone of modern deep learning, yet their theoretical convergence properties under realistic conditions have remained elusive. This paper bridges the gap by providing the first tight convergence analysis for these algorithms under generalized smoothness and affine noise variance. We prove that both optimizers achieve an optimal iteration complexity of $O(\epsilon^{-4})$ for reaching an $\epsilon$-stationary point, matching the theoretical lower bound for first-order stochastic optimizers.
Introduction
In the landscape of deep learning, Adam and RMSProp are ubiquitous. From Large Language Models (LLMs) to complex computer vision architectures, these adaptive methods are preferred for their ability to handle sparse gradients and varying scales. However, a significant disconnect has persisted between their empirical dominance and our mathematical understanding. Most existing proofs rely on idealized assumptions—such as constant smoothness and bounded noise—that are frequently violated in real-world neural network training.
A recent study published in Transactions on Machine Learning Research addresses this discrepancy. By analyzing these optimizers under "generalized" conditions, the authors provide a theoretical foundation that finally aligns with practical observations.
The Challenge of Realistic Optimization
Classical optimization theory typically rests on two pillars:
- $L$-smoothness: The assumption that the objective function's gradient changes at a bounded, constant rate.
- Bounded Noise: The assumption that the variance of stochastic gradient estimates is constant and independent of the gradient's magnitude.
In practice, particularly with LSTMs and Transformers, these pillars crumble. These models exhibit generalized smoothness, where the "curviness" of the loss landscape increases as the gradient grows. Furthermore, noise is often affine, meaning it scales with the signal (the gradient magnitude). Previous attempts to analyze Adam under these conditions often failed to prove convergence or required artificial constraints like gradient clipping.
Methodology: Taming the Gradient
The authors' approach centers on a per-coordinate analysis of Adam and RMSProp. Their primary innovation involves a novel application of the descent lemma—the mathematical tool used to guarantee that function values decrease over time.
- Coordinate-wise Generalized Smoothness (CWGS): Instead of a global smoothness constant, they assume the Lipschitz constant for each parameter increases linearly with its respective gradient norm.
- Recursive Bounding: To handle potentially unbounded gradients, the researchers developed a recursive technique to bound the first-order terms in their proofs. They demonstrate that the adaptive denominator in Adam and RMSProp naturally "tames" large gradient estimates, preventing the algorithm from diverging in steep regions.
- Potential Functions for Momentum: To account for the bias introduced by Adam's momentum (the moving average of past gradients), the authors utilized a specific "potential function" to track progress accurately.
Theoretical Breakthrough and Comparison
The most significant result is the proof that Adam and RMSProp converge to an $\epsilon$-stationary point with an iteration complexity of $O(\epsilon^{-4})$. This is the "theoretical speed limit" for all first-order stochastic optimizers, meaning these algorithms are theoretically optimal under the given assumptions.
As shown in the table above, this work is the first to simultaneously address Adam/RMSProp, coordinate-wise generalized smoothness, and affine noise while maintaining the optimal $O(\epsilon^{-4})$ complexity with a standard $O(1)$ batch size.
Empirical Validation
The authors validated their theoretical framework through experiments on standard benchmarks:
- Language Modeling: Training a 3-layer LSTM on the Penn Treebank (PTB) dataset confirmed that "generalized smoothness" is a realistic model, showing a clear linear relationship between smoothness and gradient values.
- Image Classification: Experiments on CIFAR-10 demonstrated that the minor modifications to the Adam step-size formula used in the proof do not negatively impact actual training performance.
Conclusion
This research provides a long-awaited theoretical justification for the success of Adam and RMSProp. By proving that these optimizers are self-correcting and optimal even in "messy" non-convex landscapes, the authors have narrowed the gap between optimization theory and deep learning practice. While challenges remain—such as proving convergence for the exact original Adam formulation and exploring global minima—this work sets a new standard for analyzing adaptive methods in realistic settings.
Summary updated