AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization

By Rachel A. Ward, Xiaoxia Wu, L. Eon Bottou. 2018

451 citations recorded by the source corpus.

Adaptive gradient methods such as AdaGrad and its variants update the stepsize in stochastic gradient descent on the fly according to the gradients received along the way; such methods have gained widespread use in large-scale optimization for their ability to converge robustly, without the need to fine-tune the stepsize schedule. Yet, the theoretical guarantees to date for AdaGrad are for online and convex optimization. We bridge this gap by providing theoretical guarantees for the convergence of AdaGrad for smooth, nonconvex functions. We show that the norm version of AdaGrad (AdaGrad-Norm) converges to a stationary point at the $\mathcal{O}(\log(N)/\sqrt{N})$ rate in the stochastic setting, and at the optimal $\mathcal{O}(1/N)$ rate in the batch (non-stochastic) setting -- in this sense, our convergence guarantees are 'sharp'. In particular, the convergence of AdaGrad-Norm is robust to the choice of all hyper-parameters of the algorithm, in contrast to stochastic gradient descent whose convergence depends crucially on tuning the step-size to the (generally unknown) Lipschitz smoothness constant and level of stochastic noise on the gradient. Extensive numerical experiments are provided to corroborate our theory; moreover, the experiments suggest that the robustness of AdaGrad-Norm extends to state-of-the-art models in deep learning, without sacrificing generalization.

Subfields: Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “1 as recommended in [32] (see their Figure 3), tuning ⌘ cannot quite match the performance of DecSPS.”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “More recently, adaptive methods (Duchi et al., 2011; Liu et al., 2019; Kingma and Ba, 2015; Bengio, 2015; Vaswani et al., 2019b; Li and Orabona, 2019; Ward et al., 2019) that adjust the step-size on the fly have become wide-spread and are particularly beneficial when training deep neural networks.”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, neutral): “Along similar lines, recent research has shown that AdaGrad can converge without explicitly decreasing the learning rate (Ward et al., 2019; Zou et al., 2019) .”
Learning explanations that are hard to vary (2020, methodology): “2Similar results hold for SGD [Daneshmand et al., 2018, Kushner and Yin, 2003], momentum [Jin et al., 2017], and adaptive methods including Adam [Barakat and Bianchi, 2019] and Adagrad [Ward et al., 2019].”
Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks (2018, background): “[Ward et al., 2018] also proved the convergence rate of AdaGrad under both convex and nonconvex settings without considering the effect of stochastic momentum.”
Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network (2019, methodology): “In the general non-convex and smooth setting, Ward et al. [2018] and Li and Orabona [2018] prove that the same “norm” version of AdaGrad converges to a stationary point at rate O 1 /ε 2 for stochastic gradient descent and at rate O (1 /ε ) for batch gradient descent.”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “Ward et al. (2018); Li and Orabona (2018) prove that Adagrad converges to stationary point for nonconvex stochastic problems.”
Adaptive Gradient Methods at the Edge of Stability (2022, background): “Understanding adaptive gradient methods There have been a number of convergence analyses of adaptive gradient methods [7, 48, 26, 41, 44, 11], none of which model the behavior that we observe here.”
Sequential convergence of AdaGrad algorithm for smooth convex optimization (2020, background): “In a more general nonconvex optimization context, there has been several recent attempts to develop a convergence theory for adaptive methods, with the application to deep network training in mind [16, 17, 3, 20, 22, 11, 4].”
A Simple Convergence Proof of Adam and Adagrad (2020, unknown): “Ward et al. (2019) proved that Adagrad also converges to a critical point for non convex objectives with a rate O (ln( N ) / √ N ) when using a scalar adaptive step-size, instead of diagonal.”
Online Meta-Learning on Non-convex Setting (2019, methodology): “We thus propose to use the AdaGrad-Norm [11] algorithm (Algorithm 2) as the online learning algorithm A in Algorithm 1 instead.”
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization (2018, background): “Reference [28] provided convergence rate of original Adam and RMSprop under full-batch (deterministic) setting, and [29] proved convergence rate of a modified version of AdaGrad where coordinate-wise weighting is removed.”
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds (2020, background): “Algorithms such as output-perturbation that perturbs the output of a non-DP algorithm, objective function perturbation that perturbs the objective function [7] and gradient perturbation that adds noise to the gradient in gradient descent algorithms [4, 28] have been proposed to solve DP-ERM.”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, background): “Recently, convergence guarantees for such methods are starting to appear [74, 49].”
On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks (2018, background): “We cite the proof form [39].”
Escaping Saddle Points with Adaptive Gradient Methods (2019, background): “Ward et al. [2018] give a nonconvex convergence result for a variant of Adagrad which employs an adaptively decreasing single learning rate (not per-parameter).”
Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability (2021, unknown): “L-smoothness may be inappropriate when analyzing other optimization algorithms too It is common for optimization papers seemingly motivated by deep learning to analyze algorithms under the “non-convex but L-smooth”’ setting (Reddi et al., 2016; Agarwal et al., 2017; Zaheer et al., 2018; Zhou et al.,”
Why are Adaptive Methods Good for Attention Models? (2020, background): “Since then, many works studied different interesting aspects of adaptive methods, see [1, 6, 13, 16–18, 27, 30, 32–36].”
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization (2019, background): “For instance, for AdaGrad-like algorithms, several works cover the nonconvex setting (Wu et al., 2018; Ward et al., 2019; Xie et al., 2019; Li and Orabona, 2019).”