Barzilai-Borwein Step Size for Stochastic Gradient Descent

By Conghui Tan, Shiqian Ma, Yuhong Dai, Yuqiu Qian. 2016

203 citations recorded by the source corpus.

One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step size by hand, which can be time consuming in practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to automatically compute step sizes for SGD and its variant: stochastic variance reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective functions. As a by-product, we prove the linear convergence result of SVRG with Option I proposed in [10], whose convergence result is missing in the literature. Numerical experiments on standard data sets show that the performance of SGD-BB and SVRG-BB is comparable to and sometimes even better than SGD and SVRG with best-tuned step sizes, and is superior to some advanced SGD variants.

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

In Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “A similar smoothing procedure has been used to control the magnitude of the step-sizes when using the Barzilai-Borwein step-size selection procedure for SGD (Tan et al., 2016) and is related to the “reset“ option for using larger step-sizes in Vaswani et al.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Moreover, VR makes setting the learning rate easier and there has been work exploring the use of line-search techniques for automatically setting the step-size for these methods [74, 73, 83, 78].”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, neutral): “Many modifications of AdaGrad with or without momentum have been proposed, namely, RMSprop (Srivastava and Swersky, 2012), AdaDelta (Zeiler, 2012), Adam (Kingma and Ba, 2015), AdaFTRL(Orabona and Pal, 2015), SGD-BB(Tan et al., 2016), AdaBatch (Defossez and Bach, 2017), SC-Adagrad (Mukkamala and Hein”
Automated Inference with Adaptive Batches (2017, methodology): “While there has been some work on adaptive stepsize methods for stochastic optimization (Mahsereci and Hennig, 2015; Schaul et al., 2013; Tan et al., 2016; Kingma and Ba, 2014; Zeiler, 2012), the methods are largely heuristic without any kind of theoretical guarantees or convergence rates.”
Training Neural Networks for and by Interpolation (2019, methodology): “Less closely related methods, included second-order ones, adaptively compute the learning-rate without using the minimum (Schaul et al., 2013; Martens & Grosse, 2015; Tan et al., 2016; Zhang et al., 2017; Baydin et al., 2018; Wu et al., 2018; Li & Orabona, 2019; Henriques et al., 2019), but do not d”
Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network (2019, unknown): “…been proposed, namely, RMSprop [Hinton et al., 2012], AdaDelta [Zeiler, 2012], Adam [Kingma and Ba, 2014], AdaFTRL[Orabona and P´al, 2015], SGD-BB[Tan et al., 2016], AdaBatch [D´efossez and Bach, 2017], signSGD [Bernstein et al., 2018], SC-Adagrad [Mukkamala and Hein, 2017, Shah et al., 2018],…”
L ] 1 0 A pr 2 01 9 AdaGrad-Norm convergence over nonconvex landscapes AdaGrad stepsizes : sharp convergence over nonconvex landscapes , from any initialization (2019, unknown): “Many modifications of AdaGrad with or without momentum have been proposed, namely, RMSprop (Srivastava and Swersky, 2012), AdaDelta (Zeiler, 2012), Adam (Kingma and Ba, 2015), AdaFTRL(Orabona and Pal, 2015), SGD-BB(Tan et al., 2016), AdaBatch (Defossez and Bach, 2017), SC-Adagrad (Mukkamala and Hein”
Big Batch SGD: Automated Inference using Adaptive Batch Sizes (2016, methodology): “While there has been some work on adaptive stepsize methods for stochastic optimization (Mahsereci and Hennig, 2015; Schaul et al., 2013; Tan et al., 2016; Kingma and Ba, 2014; Zeiler, 2012), the methods are largely heuristic without any kind of theoretical guarantees or convergence rates.”