TL;DR
This paper provides the first theoretical convergence guarantees for the popular RMSProp and ADAM optimizers in smooth, non-convex settings. Beyond the math, the authors demonstrate through extensive experiments that ADAM’s perceived "generalization gap" compared to Nesterov acceleration can often be closed simply by tuning the momentum parameter ($\beta_1$) to much higher values than the industry standard.
What Problem Does This Paper Address?
In the deep learning world, adaptive gradient methods like RMSProp and ADAM are favorites because they require less manual learning-rate tuning. However, they’ve long been plagued by two issues:
- Theoretical Mystery: While they work in practice, we lacked rigorous proofs that they actually converge to critical points (local minima or saddle points) when optimizing non-convex functions.
- The Generalization Gap: Empirical studies often suggested that while ADAM trains faster, it results in models that perform worse on new, unseen data compared to Nesterov’s Accelerated Gradient (NAG).
The authors set out to provide the missing theory and investigate if ADAM’s generalization issues are a fundamental flaw or just a hyperparameter tuning problem.
Methods
The paper takes a two-pronged approach:
- Theoretical Analysis: The authors provide runtime bounds for deterministic (full-batch) versions of RMSProp and ADAM, proving they reach approximate criticality on smooth non-convex objectives.
- Empirical Comparison: They conduct a head-to-head battle between RMSProp, ADAM, and NAG, tracking not just loss and accuracy, but also the gradient norms and the minimum eigenvalue of the Hessian ($\lambda_{min}$). The latter helps determine if an optimizer is successfully escaping "bad" saddle points.
Key Insights and Ideas
- The $\beta_1$ Sweet Spot: ADAM is extremely sensitive to its momentum parameter, $\beta_1$. While the default is usually $0.9$, the authors found that pushing $\beta_1$ to $0.99$ allowed ADAM to match or even outperform a carefully tuned NAG in both training and test loss.
- The Importance of $\xi$: The "perturbation" parameter $\xi$ acts as a crucial pre-conditioner; increasing it can help lower gradient norms and improve test performance, even if it slightly slows down training.
- Saddle Point Navigation: By tracking the Hessian's minimum eigenvalue, the authors found that NAG has a distinct, consistent ability to move toward regions with more positive curvature (better local minima).
Key Results
- Closing the Gap: On VGG-9 with CIFAR-10, ADAM with $\beta_1=0.99$ achieved generalization performance as good as or better than NAG, whereas the standard $\beta_1=0.9$ lagged behind.
- Convergence Rates: The paper establishes that deterministic RMSProp and ADAM reach an $\epsilon$-critical point in $O(1/\epsilon^2)$ and $O(1/\epsilon^6)$ steps, respectively.
- Gradient Reduction: NAG consistently proved superior at reducing the norm of the gradient compared to adaptive methods, suggesting it finds "flatter" or more stable minima.
Limitations and Future Work
The biggest limitation is the gap between theory and practice for ADAM. The current convergence proof only holds for the "small $\beta_1$" regime, yet experiments show the "large $\beta_1$" regime is where the best performance happens. Future work is needed to tighten theoretical bounds for ADAM to reflect the faster convergence seen in practice and to relax the "sign condition" required for the stochastic RMSProp proof.
Summary updated