On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

By Xiaoyun Li, Francesco Orabona. 2018

345 citations recorded by the source corpus.

Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in our theoretical understanding of these methods, especially in the non-convex setting. In this paper, we start closing this gap: we theoretically analyze in the convex and non-convex settings a generalized version of the AdaGrad stepsizes. We show sufficient conditions for these stepsizes to achieve almost sure asymptotic convergence of the gradients to zero, proving the first guarantee for generalized AdaGrad stepsizes in the non-convex setting. Moreover, we show that these stepsizes allow to automatically adapt to the level of noise of the stochastic gradients in both the convex and non-convex settings, interpolating between $O(1/T)$ and $O(1/\sqrt{T})$, up to logarithmic terms.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

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.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “A similar technique has recently been used to prove convergence of SGD with the AdaGrad step-size [45].”
Adaptive Federated Optimization (2020, background): “, 2011; Kingma and Ba, 2015) and nonconvex setting (Zaheer et al., 2018; Li and Orabona, 2018; Ward et al., 2018; Wu et al., 2019).”
Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks (2018, background): “[Li and Orabona, 2018] analyzed convergence rate of AdaGrad under both convex and nonconvex settings but did not consider more complicated Adam-type algorithms.”
A Sufficient Condition for Convergences of Adam and RMSProp (2018, background): “Besides, many other adaptive stochastic algorithms without combining momentums, such as AdaGrad [22, 18] and stagewise AdaGrad [7], have been guaranteed to be convergent and work well in the non-convex stochastic setting.”
On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks (2018, methodology): “In [26], convergence rates of an AdaGrad-like and its coordinate-wise version have been established with the following perturbed adaptive learning rate: P under slightly diﬀerent assumptions.”
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].”
Linear Convergence of Adaptive Stochastic Gradient Descent (2019, methodology): “4 Our analysis does not follow the standard analysis—which assumes the bounded variance [28, 24, 27, 29]—and avoids likely sub-linear convergence results.”
Stochastic Gradient Descent with Polyak’s Learning Rate (2019, methodology): “For example, [14] provides convergence guarantees for AdaGrad and [32] generalizes to class of adaptive gradient methods that includes AMSGrad, RMSProp and AdaGrad.”
A Simple Convergence Proof of Adam and Adagrad (2020, neutral): “The convergence of Adagrad for non-convex objectives was ﬁrst tackled by Li & Orabona (2019), who proved its convergence, but under restrictive conditions (e.g., α ≤ √ /L ).”
Better Theory for SGD in the Nonconvex World (2020, methodology): “Then for all x ∈ R d we have This lemma shows up in several recent works and is often used in conjunction with other assumptions such as bounded variance (Li & Orabona, 2019) and convexity (Stich & Karimireddy, 2019).”
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).”
Why ADAM Beats SGD for Attention Models (2019, background): “Since then, many works studied different interesting aspects of adaptive methods, see (Ward et al., 2018; Li & Orabona, 2018; Zhou et al., 2018a; Staib et al., 2019; Chen et al., 2018; Zou & Shen, 2018; Zhou et al., 2018b; Agarwal et al., 2018; Zou et al., 2019).”
Momentum Improves Normalized SGD (2020, background): “These learning rates enable SGD to converge faster when the objective under consideration is in some technical sense “easier” than a worst-case objective 1 , speciﬁcally when the variance of the loss from one example to another is small Li & Orabona (2019); Ward et al. (2019).”
Online Meta-Learning on Non-convex Setting (2019, background): “t), Assumption 1 gives us: (a) E t[G t;m(w t)] = rF t;m(w t) (b) E t p kG t;m(x t) r F t;m(x t)k 2 ˙2 m Lemma 3. Given Assumption 2(d), we have: P T t=1 E[F t;m(w t) F t;m(w t+1)] 4MT m . Lemma 4 ([13], Lemma 9). Let h : [0;+1) ![0;+1) be a nonincreasing function, and a i0 for i= 0; ;T. Then XT t=1”
Theoretical Analysis of Auto Rate-Tuning by Batch Normalization (2018, background): “Other works analyzing the convergence of adaptive methods are (Ward et al., 2018; Li & Orabona, 2018; Zou & Shen, 2018; Zhou et al., 2018).”
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.”
Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability (2021, background): “…under the “non-convex but L-smooth”’ setting (Reddi et al., 2016; Agarwal et al., 2017; Zaheer et al., 2018; Zhou et al., 2018; Chen et al., 2019; Li & Orabona, 2019; Ward et al., 2019; You et al., 2020; Vaswani et al., 2019; Sankararaman et al., 2019; Reddi et al., 2021; Défossez et al.,…”