RMSprop converges with proper hyper-parameter

Naichen Shi, Dawei Li, Mingyi Hong, Ruoyu Sun

Introduction

In the world of deep learning, RMSprop is a workhorse optimizer, especially favored for GANs and reinforcement learning. However, a famous 2018 paper by Reddi et al. revealed a theoretical rift: RMSprop can diverge even on simple convex functions. While practitioners continued to use it successfully, theorists scrambled to design "fixed" variants like AMSGrad.

The core issue with previous theoretical analyses is that they often relied on a "bounded gradient" assumption—the unrealistic idea that gradients never exceed a certain size. Furthermore, theory failed to explain why simply tuning the hyper-parameter $\beta_2$ (the second-order momentum coefficient) seemed to resolve divergence issues in practice. This paper bridges the gap between theory and practice, proving that vanilla RMSprop (and Adam with small momentum) is guaranteed to converge without unrealistic assumptions, provided $\beta_2$ is chosen correctly.

Theoretical Approach

The authors provide a rigorous convergence analysis for both full-batch and stochastic (randomly shuffled) versions of RMSprop. Their approach is novel in two key ways:

  1. Removing the Bounded Gradient Assumption: They prove convergence without assuming gradients are globally bounded, which is crucial for understanding why algorithms might diverge to infinity.
  2. Hyper-parameter Dependency: They treat $\beta_2$ as a problem-dependent hyper-parameter rather than a universal constant.

The paper categorizes optimization problems into two types:

  • Realizable (Interpolation regime): Problems where the model is powerful enough to fit all data points perfectly (common in overparameterized deep learning). Here, RMSprop converges to actual critical points.
  • Non-realizable: Problems where a perfect fit isn't possible. In these cases, RMSprop converges to a small bounded region around the minimum.

The Phase Transition of $\beta_2$

A central insight of the paper is the existence of a "phase transition" for $\beta_2$. If $\beta_2$ is below a critical threshold, the algorithm can diverge; above it, the algorithm is guaranteed to behave.

Phase transition between divergent and convergent regimes based on beta_2

The authors explain why RMSprop diverges with small $\beta_2$ values: the adaptive scaling factor fluctuates wildly based on noisy mini-batches. This "distorts" the update direction so much that it can point away from the solution. A large $\beta_2$ acts as a stabilizer, smoothing out these fluctuations. On synthetic counter-examples, they found a sharp transition: for instance, diverging if $\beta_2 < 0.955$ but converging if $\beta_2 > 0.956$.

Empirical Validation on CIFAR-10

The required $\beta_2$ for convergence is also linked to the batch size. As the number of batches increases (or batch size decreases), a larger $\beta_2$ is generally needed to maintain stability.

CIFAR-10 performance with varying batch sizes and beta_2 values

The authors validated these findings using a ResNet-18 architecture on the CIFAR-10 dataset. As shown in the results, with a small batch size of 8, training accuracy was a mere 10% (indicating divergence) when $\beta_2 = 0.9$. However, performance jumped to 99.74% when $\beta_2$ was increased to $0.99$, perfectly mirroring the theoretical predictions.

Limitations and Future Work

While this paper makes significant strides, some open challenges remain:

  • Conservative Bounds: The theoretical bound required for $\beta_2$ in the proofs is much stricter than what is observed in practice. Closing this gap between "pessimistic" theory and "optimistic" reality is an ongoing challenge.
  • Adam's Momentum: The analysis for Adam is currently restricted to cases with "small" $\beta_1$ (first-order momentum). A more general proof for standard Adam settings is left for future research.
  • Efficiency vs. Convergence: The paper focuses on whether the algorithm converges, not necessarily how fast it converges compared to SGD. The theoretical "advantage" of adaptive methods remains a long-standing open question.

Summary updated

Abstract

Despite the existence of divergence examples, RMSprop remains one of the most popular algorithms in machine learning. Towards closing the gap between theory and practice, we prove that RMSprop converges with proper choice of hyper-parameters under certain conditions. More specifically, we prove that when the hyper-parameter $\beta_2$ is close enough to $1$, RMSprop and its random shuffling version converge to a bounded region in general, and to critical points in the interpolation regime. It is worth mentioning that our results do not depend on ``bounded gradient" assumption, which is often the key assumption utilized by existing theoretical work for Adam-type adaptive gradient method. Removing this assumption allows us to establish a phase transition from divergence to non-divergence for RMSprop. Finally, based on our theory, we conjecture that in practice there is a critical threshold $\sf{\beta_2^*}$, such that RMSprop generates reasonably good results only if $1>\beta_2\ge \sf{\beta_2^*}$. We provide empirical evidence for such a phase transition in our numerical experiments.
BibTeX
@inproceedings{shi2021rmsprop,
  author = {Naichen Shi and Dawei Li and Mingyi Hong and Ruoyu Sun},
  title = {{RMSprop converges with proper hyper-parameter}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=H9UZeB9bPg9},
}
Figure