Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

By Sharan Vaswani, Aaron Mishkin, Issam Hadj Laradji, Mark W. Schmidt, Gauthier Gidel, Simon Lacoste-Julien. 2019

247 citations recorded by the source corpus.

Recent works have shown that stochastic gradient descent (SGD) achieves the fast convergence rates of full-batch gradient descent for over-parameterized models satisfying certain interpolation conditions. However, the step-size used in these works depends on unknown quantities and SGD's practical performance heavily relies on the choice of this step-size. We propose to use line-search techniques to automatically set the step-size when training models that can interpolate the data. In the interpolation setting, we prove that SGD with a stochastic variant of the classic Armijo line-search attains the deterministic convergence rates for both convex and strongly-convex functions. Under additional assumptions, SGD with Armijo line-search is shown to achieve fast convergence for non-convex functions. Furthermore, we show that stochastic extra-gradient with a Lipschitz line-search attains linear convergence for an important class of non-convex functions and saddle-point problems satisfying interpolation. To improve the proposed methods' practical performance, we give heuristics to use larger step-sizes and acceleration. We compare the proposed algorithms against numerous optimization methods on standard classification tasks using both kernel methods and deep networks. The proposed methods result in competitive performance across all models and datasets, while being robust to the precise choices of hyper-parameters. For multi-class classification using deep networks, SGD with Armijo line-search results in both faster convergence and better generalization.

Subfields: 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 Optimization & Training

Citations in the corpus

Adversarial Example Games (2020, methodology): “We train both the generator ( g ) and representative classiﬁer ( f c ) using stochastic gradient descent-ascent with the ExtraAdam optimizer [26] and held out target models, f t , are trained ofﬂine using SGD with Armijo line search [66].”
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.”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Furthermore, a modest batch-growth strategy and stochastic line-search (Vaswani et al., 2019b) scheme ensure that R-SSN is computationally eﬃcient and competitive with stochastic ﬁrst-order methods and L-BFGS variants in terms of both the number of iterations and wall-clock time required for…”
Training Neural Networks for and by Interpolation (2019, methodology): “We say that f satisﬁes the RSI if there exists α > 0 such that: The RSI is sometimes used to prove convergence of optimization algorithms without assuming convexity (Vaswani et al., 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).”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “We selected the kernel band-width 0.05 following Vaswani et al. (2019b).”
Stochastic Adaptive Line Search for Differentially Private Optimization (2020, background): “Recently, [9] introduced a stochastic version in which both objectives and gradients are approximated using a random subset of data.”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “This kind of condition has been popularized recently in the machine learning community under the name of interpolation [34].”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “There are several choices that one can use including constant step-size [33, 35, 11, 36, 41], decreasing step-size [47, 8, 11, 37, 17] and adaptive step-size [6, 26, 20, 3, 55, 56].”