Abstract
Although adaptive gradient methods have been extensively used in deep learning, their convergence rates proved in the literature are all slower than that of SGD, particularly with respect to their dependence on the dimension. This paper considers the classical RMSProp and its momentum extension and establishes the convergence rate of $\frac{1}{T}\sum_{k=1}^T E\left[\|\nabla f(x^k)\|_1\right]\leq O(\frac{\sqrt{d}C}{T^{1/4}})$ measured by $\ell_1$ norm without the bounded gradient assumption, where $d$ is the dimension of the optimization variable, $T$ is the iteration number, and $C$ is a constant identical to that appeared in the optimal convergence rate of SGD. Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$. Since $\|x\|_2\ll\|x\|_1\leq\sqrt{d}\|x\|_2$ for problems with extremely large $d$, our convergence rate can be considered to be analogous to the $\frac{1}{T}\sum_{k=1}^T E\left[\|\nabla f(x^k)\|_2\right]\leq O(\frac{C}{T^{1/4}})$ rate of SGD in the ideal case of $\|\nabla f(x)\|_1=\varTheta(\sqrt{d}\|\nabla f(x)\|_2)$.
Introduction
Adaptive gradient methods, such as RMSProp and Adam, have become the standard for training large-scale deep learning models. Despite their empirical success, a significant theoretical gap has persisted: existing analyses often suggest these methods converge slower than standard Stochastic Gradient Descent (SGD), especially as the parameter dimension $d$ increases. For high-dimensional models like GPT-3, a linear dependence on $d$ in the convergence rate would imply impractical training times. This work by Li et al. addresses this discrepancy by establishing a tighter convergence bound for RMSProp and its momentum extension.
Theoretical Framework: Shifting the Metric
The core innovation of this research is the shift from the standard Euclidean ($\ell_2$) norm to the Manhattan ($\ell_1$) norm for measuring convergence. Traditional optimization theory evaluates the expected norm of the gradient, $E[\|\nabla f(x)\|_2]$. However, adaptive methods scale updates coordinate-wise, making them inherently linked to the geometry of the $\ell_1$ norm.
By analyzing RMSProp in the $\ell_1$ space, the authors derive a convergence rate of $O(\frac{\sqrt{d}}{T^{1/4}})$. Crucially, this analysis avoids the restrictive "bounded gradient" assumption often found in prior literature, instead relying on the more realistic assumption of coordinate-wise bounded noise variance. This result matches the lower bound for stochastic optimization in terms of iteration count ($T$), smoothness, and noise, with the dimension $d$ being the only remaining factor for potential refinement.
Empirical Validation
To bridge the theoretical $\ell_1$ rate with practical $\ell_2$ performance, the authors investigate the relationship between these norms in real-world training scenarios. In high-dimensional spaces, it is known that $\|x\|_2 \leq \|x\|_1 \leq \sqrt{d}\|x\|_2$. If the gradient components are roughly equal in magnitude, the ratio $\|\nabla f\|_1 / \|\nabla f\|_2$ approaches $\sqrt{d}$.
The researchers conducted experiments using ResNet-50 on CIFAR-100 and ImageNet, as well as GPT-2 on OpenWebText. As shown in Figure 1, the "gradient norm ratio" remains remarkably stable and close to the theoretical $\sqrt{d}$ value throughout the training process.
This empirical evidence suggests that the $O(\sqrt{d}/T^{1/4})$ rate in $\ell_1$ is functionally equivalent to SGD's $O(1/T^{1/4})$ rate in $\ell_2$ for practical deep learning tasks.
Conclusion
This work provides a theoretical foundation that aligns with the observed efficiency of adaptive methods in high-dimensional optimization. By choosing a norm that respects the coordinate-wise nature of these algorithms, the authors demonstrate that RMSProp is not inherently slower than SGD. Future work may focus on formally proving lower bounds in the $\ell_1$ norm and further relaxing noise assumptions to generalize these findings to a broader class of adaptive optimizers.
Summary updated