2019

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

Vaswani, Sharan, Mishkin, Aaron, Laradji, Issam et al.

Understand

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.

Built on

Gradient methods for minimizing functionals
Boris Teodorovich Polyak · 1963
Earlier work this paper cites.
Some methods of speeding up the convergence of iteration methods
Boris T Polyak · 1964
Earlier work this paper cites.
Minimization of functions having Lipschitz continuous first partial derivatives
Larry Armijo · 1966
Earlier work this paper cites.
The extragradient method for finding saddle points and other problems
GM Korpelevich · 1976
Earlier work this paper cites.
Modification of the extra-gradient method for solving variational inequalities and certain optimization problems
Evgenii Nikolaevich Khobotov · 1987
Earlier work this paper cites.
Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications
Patrick T Harker and Jong-Shi Pang · 1990
Earlier work this paper cites.
Accelerated stochastic approximation
Bernard Delyon and Anatoli Juditsky · 1993
Earlier work this paper cites.
Stochastic approximation with averaging and feedback: Rapidly convergent" on-line" algorithms
Harold J Kushner and Jichuan Yang · 1995
Earlier work this paper cites.
A variant of korpelevich’s method for variational inequalities with a new search strategy
AN Iusem and BF Svaiter · 1997
Earlier work this paper cites.
Parameter adaptation in stochastic optimization
Luís Almeida · 1998
Earlier work this paper cites.
Boosting the margin: A new explanation for the effectiveness of voting methods
Robert E Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee, et al · 1998
Earlier work this paper cites.
An incremental gradient (-projection) method with momentum term and adaptive stepsize rule
Paul Tseng · 1998
Earlier work this paper cites.
Local gain adaptation in stochastic gradient descent
Nicol Schraudolph · 1999
Earlier work this paper cites.
Rates of convergence of adaptive step-size of stochastic approximation algorithms
S Shao and Percy Yip · 2000
Earlier work this paper cites.
Learning rate adaptation in stochastic gradient descent
VP Plagianakos, GD Magoulas, and MN Vrahatis · 2001
Earlier work this paper cites.
Prox-method with rate of convergence O ⁡ ( 1 / t ) {O}(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems
Arkadi Nemirovski · 2004
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course
Yurii Nesterov · 2004
Earlier work this paper cites.
A support vector method for multivariate performance measures
Thorsten Joachims · 2005
Earlier work this paper cites.
Numerical optimization
Jorge Nocedal and Stephen Wright · 2006
Earlier work this paper cites.
Fast online policy gradient learning with smd gain vector adaptation
Jin Yu, Douglas Aberdeen, and Nicol Schraudolph · 2006
Earlier work this paper cites.
Robust optimization
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski · 2009
Earlier work this paper cites.
Robust stochastic approximation approach to stochastic programming
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro · 2009
Earlier work this paper cites.
LIBSVM: A library for support vector machines
Chih-Chung Chang and Chih-Jen Lin · 2011
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer · 2011
Earlier work this paper cites.
Solving variational inequalities with stochastic mirror-prox algorithm
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel · 2011
Earlier work this paper cites.
Optimization with sparsity-inducing penalties
Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et al · 2012
Earlier work this paper cites.
Practical recommendations for gradient-based training of deep architectures
Yoshua Bengio · 2012
Earlier work this paper cites.
Sample size selection in optimization methods for machine learning
Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu · 2012
Earlier work this paper cites.
Hybrid deterministic-stochastic methods for data fitting
Michael P Friedlander and Mark Schmidt · 2012
Earlier work this paper cites.
Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude
Tijmen Tieleman and Geoffrey Hinton · 2012
Earlier work this paper cites.
ADADELTA: an adaptive learning rate method
Original
Matthew Zeiler · 2012
Earlier work this paper cites.

Similar

Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Cited alongside, same era.
Line search methods with variable sample size for unconstrained optimization
Nataša Krejić and Nataša Krklec · 2013
Cited alongside, same era.
Gradient methods for minimizing composite functions
Yu Nesterov · 2013
Cited alongside, same era.
No more pesky learning rates
Tom Schaul, Sixin Zhang, and Yann LeCun · 2013
Cited alongside, same era.
Fast convergence of stochastic gradient descent under a strong growth condition
Original
Mark Schmidt and Nicolas Le Roux · 2013
Cited alongside, same era.
On the importance of initialization and momentum in deep learning
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton · 2013
Cited alongside, same era.
Saga: A fast incremental gradient method with support for non-strongly convex composite objectives
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien · 2014
Cited alongside, same era.
Robust learning under uncertain test distributions: Relating covariate shift to model misspecification
Junfeng Wen, Chun-Nam Yu, and Russell Greiner · 2014
Cited alongside, same era.
Solving random quadratic systems of equations is nearly as easy as solving linear systems
Yuxin Chen and Emmanuel Candes · 2015
Cited alongside, same era.
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford · 2015
Cited alongside, same era.
Adam: A method for stochastic optimization
Diederik Kingma and Jimmy Ba · 2015
Cited alongside, same era.
A universal catalyst for first-order optimization
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui · 2015
Cited alongside, same era.

Then

Training deep networks without learning rates through coin betting
Francesco Orabona and Tatiana Tommasi · 2017
Later among the works it cites.
Reflections on random kitchen sinks, 2017
Ali Rahimi and Ben Recht · 2017
Later among the works it cites.
Minimizing finite sums with the stochastic average gradient
Mark Schmidt, Nicolas Le Roux, and Francis Bach · 2017
Later among the works it cites.
Stochastic gradient descent: Going as fast as possible but not faster
Original
Alice Schoenauer-Sebag, Marc Schoenauer, and Michèle Sebag · 2017
Later among the works it cites.
Stabilizing adversarial nets with prediction methods
Original
Abhay Yadav, Sohil Shah, Zheng Xu, David Jacobs, and Tom Goldstein · 2017
Later among the works it cites.
Understanding deep learning requires rethinking generalization
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals · 2017
Later among the works it cites.
Yellowfin and the art of momentum tuning
Original
Jian Zhang and Ioannis Mitliagkas · 2017
Later among the works it cites.
On exponential convergence of SGD in non-convex over-parametrized learning
Original
Raef Bassily, Mikhail Belkin, and Siyuan Ma · 2018
Later among the works it cites.
A progressive batching l-bfgs method for machine learning
Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang · 2018
Later among the works it cites.
On the linear convergence of the stochastic gradient method with constant step-size
Volkan Cevher and Bang Công Vũ · 2018
Later among the works it cites.
Accelerating stochastic gradient descent for least squares regression
Prateek Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford · 2018
Later among the works it cites.
An alternative view: When does SGD escape local minima?
Robert Kleinberg, Yuanzhi Li, and Yang Yuan · 2018
Later among the works it cites.
Just interpolate: Kernel" ridgeless" regression can generalize
Original
Tengyuan Liang and Alexander Rakhlin · 2018
Later among the works it cites.
The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning
Siyuan Ma, Raef Bassily, and Mikhail Belkin · 2018
Later among the works it cites.
A stochastic line search method with convergence rate analysis
Original
Courtney Paquette and Katya Scheinberg · 2018
Later among the works it cites.
L4: practical loss-based stepsize adaptation for deep learning
Michal Rolinek and Georg Martius · 2018
Later among the works it cites.
Guaranteed sufficient decrease for stochastic variance reduced gradient optimization
Fanhua Shang, Yuanyuan Liu, Kaiwen Zhou, James Cheng, Kelvin Ng, and Yuichi Yoshida · 2018
Later among the works it cites.
Theoretical insights into the optimization landscape of over-parameterized shallow neural networks
Mahdi Soltanolkotabi, Adel Javanmard, and Jason Lee · 2018
Later among the works it cites.
Backtracking gradient descent method for general C 1
Original
Tuyen Trung Truong and Tuan Hang Nguyen · 2018
Later among the works it cites.
Does data interpolation contradict statistical optimality?
Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov · 2019
Closest in time.
Training neural networks for and by interpolation
Original
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar · 2019
Closest in time.
Convergence rate analysis of a stochastic trust region method via supermartingales
Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg · 2019
Closest in time.
Reducing noise in GAN training with variance reduced extragradient
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien · 2019
Closest in time.
On the ineffectiveness of variance reduced optimization for deep learning
Aaron Defazio and Léon Bottou · 2019
Closest in time.
A variational inequality perspective on generative adversarial networks
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien · 2019
Closest in time.
Variance-based extragradient methods with line search for stochastic variational inequalities
Alfredo N Iusem, Alejandro Jofré, Roberto I Oliveira, and Philip Thompson · 2019
Closest in time.
On the convergence of stochastic gradient descent with adaptive stepsizes
Xiaoyu Li and Francesco Orabona · 2019
Closest in time.
Accelerating stochastic training for over-parametrized learning
Original
Chaoyue Liu and Mikhail Belkin · 2019
Closest in time.
Adaptive gradient methods with dynamic bound of learning rate
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun · 2019
Closest in time.
On the convergence of Adam and beyond
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar · 2019
Closest in time.
Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron
Sharan Vaswani, Francis Bach, and Mark Schmidt · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…