Convergence guarantees for RMSProp and ADAM in non-convex optimization and their comparison to Nesterov acceleration on autoencoders

Amitabh Basu, Soham De, Anirbit Mukherjee, Enayat UllaharXiv 2018 · arXiv · OpenReview

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:

  1. 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.
  2. 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).
Minimum eigenvalue of the Hessian over iterations. NAG shows a consistent trend toward regions with more positive curvature compared to adaptive methods.

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.
Comparison of gradient norm reduction. NAG is significantly more effective at minimizing the gradient norm than ADAM or RMSProp.

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

Abstract

RMSProp and ADAM continue to be extremely popular algorithms for training neural nets but their theoretical convergence properties have remained unclear. Further, recent work has seemed to suggest that these algorithms have worse generalization properties when compared to carefully tuned stochastic gradient descent or its momentum variants. In this work, we make progress towards a deeper understanding of ADAM and RMSProp in two ways. First, we provide proofs that these adaptive gradient algorithms are guaranteed to reach criticality for smooth non-convex objectives, and we give bounds on the running time. Next we design experiments to empirically study the convergence and generalization properties of RMSProp and ADAM against Nesterov's Accelerated Gradient method on a variety of common autoencoder setups and on VGG-9 with CIFAR-10. Through these experiments we demonstrate the interesting sensitivity that ADAM has to its momentum parameter $\beta_1$. We show that at very high values of the momentum parameter ($\beta_1 = 0.99$) ADAM outperforms a carefully tuned NAG on most of our experiments, in terms of getting lower training and test losses. On the other hand, NAG can sometimes do better when ADAM's $\beta_1$ is set to the most commonly used value: $\beta_1 = 0.9$, indicating the importance of tuning the hyperparameters of ADAM to get better generalization performance. We also report experiments on different autoencoders to demonstrate that NAG has better abilities in terms of reducing the gradient norms, and it also produces iterates which exhibit an increasing trend for the minimum eigenvalue of the Hessian of the loss function at the iterates.
BibTeX
@misc{basu2018convergence,
  author = {Amitabh Basu and Soham De and Anirbit Mukherjee and Enayat Ullah},
  title = {{Convergence guarantees for RMSProp and ADAM in non-convex optimization and their comparison to Nesterov acceleration on autoencoders}},
  year = {2018},
  eprint = {1807.06766},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.06766},
}
Figure