Linear Convergence of Adaptive Stochastic Gradient Descent

By Yuege Xie, Xiaoxia Wu, Rachel A. Ward. 2019

53 citations recorded by the source corpus.

We prove that the norm version of the adaptive stochastic gradient method (AdaGrad-Norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-convex functions that satisfy the Polyak Lojasiewicz (PL) inequality. The paper introduces the notion of Restricted Uniform Inequality of Gradients (RUIG)---which is a measure of the balanced-ness of the stochastic gradient norms---to depict the landscape of a function. RUIG plays a key role in proving the robustness of AdaGrad-Norm to its hyper-parameter tuning in the stochastic setting. On top of RUIG, we develop a two-stage framework to prove the linear convergence of AdaGrad-Norm without knowing the parameters of the objective functions. This framework can likely be extended to other adaptive stepsize algorithms. The numerical experiments validate the theory and suggest future directions for improvement.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

1. Simon Lacoste-Julien
2. Nicolas Loizou
3. Peter Richtárik
4. Antonio Orvieto
5. Naman Agarwal
6. Justin Gilmer
7. Edouard Pauwels
8. Jeremy M. Cohen

In Computational Mechanics

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Naman Agarwal
5. Antonio Orvieto
6. Edouard Pauwels
7. Cheik Traoré
8. George E. Dahl

In Numerical Analysis

1. Simon Lacoste-Julien
2. Edouard Pauwels
3. Nicolas Loizou
4. Cheik Traoré
5. Naman Agarwal
6. Pascal Bianchi
7. Antonio Orvieto
8. Anas Barakat

In Optimization & Training

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Antonio Orvieto
5. Naman Agarwal
6. Edouard Pauwels
7. Cheik Traoré
8. Justin Gilmer

Citations in the corpus

• Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “Unfortunately, this is a common problem of all AdaGrad variants: with the exception of [33] (which works in a slightly different scenario), no rate can be provided in the stochastic setting without the bounded iterates/gradients [12] assumption — even after assuming strong convexity.”
• 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).”
• Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability (2021, unknown): “…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., 2020; Xie et al., 2020; Liu et al., 2020; Defazio, 2020).”
• Sequential convergence of AdaGrad algorithm for smooth convex optimization (2020, background): “This idea was extended to adaptivity to strong convexity [6] and its extensions [24], as well as adaptivity in the context of variational inequalities [2].”
• 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.”