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:
- 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.
- 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.
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.
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