On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization

Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, Quanquan Gu

Introduction

Adaptive gradient methods, such as Adam, AMSGrad, and AdaGrad, have become the standard for training large-scale neural networks. Despite their empirical dominance, a significant gap remains between their practical performance and theoretical understanding in nonconvex optimization. This paper addresses two critical shortcomings in existing literature: the poor scaling of convergence rates with problem dimensionality ($d$) and the reliance on "in-expectation" guarantees rather than high-probability bounds.

The Dimensionality and Probability Gap

Previous theoretical analyses of adaptive methods often suggested that convergence speed slows down quadratically with the number of parameters ($O(d^2)$). In the era of models with billions of parameters, such a dependency is overly pessimistic. Furthermore, most existing proofs only guarantee performance "on average" (in expectation). For practitioners who typically run an optimizer once, "high-probability" guarantees are essential to ensure that a single training run will reliably converge to a stationary point.

Methodology: A Unified Fine-Grained Analysis

The authors propose a unified framework for analyzing a general class of adaptive methods, including AMSGrad, RMSProp, and AdaGrad. Their approach introduces several key technical innovations:

  • The Gradient Growth Parameter ($s$): A parameter $s \in [0, 1/2]$ is introduced to characterize the growth rate of cumulative stochastic gradients. This allows the analysis to distinguish between "sparse" gradients (where adaptive methods are most effective) and "dense" gradients.
  • Auxiliary "Shadow" Sequences: To manage the complexity of momentum and adaptive scaling, the authors analyze a shadow sequence ($z_t$) that tracks the algorithm's progress more cleanly than the raw iterates.
  • Concentration Inequalities: By assuming sub-Gaussian noise in stochastic gradients, the authors employ martingale concentration arguments to derive the first high-probability convergence bounds for these algorithms.

Key Results and Improved Rates

The most significant contribution of this work is the reduction of the dimension dependency from $O(d^2)$ to $O(\sqrt{d})$. In the worst-case scenario ($s=1/2$), the authors establish a convergence rate of $O(\sqrt{d/T} + d/T)$, where $T$ is the number of iterations.

Comparison of convergence rates for AMSGrad and AdaGrad against prior state-of-the-art results.

As shown in the table above, this result significantly improves upon previous benchmarks. For instance, the rate for AMSGrad is improved from $O(d^2/\sqrt{T})$ (Chen et al., 2018a) to a much more favorable scaling with $d$. Additionally, the high-probability bounds show that the gradient norm decreases at essentially the same rate as the expected case, with only a logarithmic dependency on the failure probability ($\log(1/\delta)$).

Empirical Validation

While primarily theoretical, the paper validates its assumptions through experiments on PennTreeBank (training a 3-layer LSTM) and ResNet-18. These experiments empirically estimate the $s$ parameter, confirming that the "fine-grained" assumptions hold in practical deep learning scenarios.

Limitations and Future Directions

While this work marks a significant step forward, some limitations remain:

  1. Bounded Gradient Assumption: The analysis assumes stochastic gradients are bounded in the $L_\infty$ norm, a standard but sometimes restrictive assumption in deep learning.
  2. First-Order Stationarity: The results guarantee convergence to a first-order stationary point (where the gradient is zero) but do not explicitly address the avoidance of saddle points or local minima.
  3. Algorithm Scope: The analysis focuses on AMSGrad and its variants. Extending these fine-grained techniques to the "vanilla" Adam optimizer remains a promising area for future research.

Summary updated

Abstract

Adaptive gradient methods are workhorses in deep learning. However, the convergence guarantees of adaptive gradient methods for nonconvex optimization have not been thoroughly studied. In this paper, we provide a fine-grained convergence analysis for a general class of adaptive gradient methods including AMSGrad, RMSProp and AdaGrad. For smooth nonconvex functions, we prove that adaptive gradient methods in expectation converge to a first-order stationary point. Our convergence rate is better than existing results for adaptive gradient methods in terms of dimension, and is strictly faster than stochastic gradient decent (SGD) when the stochastic gradients are sparse. To the best of our knowledge, this is the first result showing the advantage of adaptive gradient methods over SGD in nonconvex setting. In addition, we also prove high probability bounds on the convergence rates of AMSGrad, RMSProp as well as AdaGrad, which have not been established before. Our analyses shed light on better understanding the mechanism behind adaptive gradient methods in optimizing nonconvex objectives.
BibTeX
@misc{zhou2018convergence,
  author = {Dongruo Zhou and Yiqi Tang and Ziyan Yang and Yuan Cao and Quanquan Gu},
  title = {{On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization}},
  year = {2018},
  eprint = {1808.05671},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.05671},
}
Figure