2015

Stochastic modified equations and adaptive stochastic gradient algorithms

Li, Qianxiao, Tai, Cheng, E, Weinan

Understand

We develop the method of stochastic modified equations (SME), in which stochastic gradient algorithms are approximated in the weak sense by continuous-time stochastic differential equations.

We exploit the continuous formulation together with optimal control theory to derive novel adaptive hyper-parameter adjustment policies.
Our algorithms have competitive performance with the added benefit of being robust to varying models and datasets.
This provides a general methodology for the analysis and design of stochastic gradient algorithms.

Built on

On the theory of the Brownian motion
Uhlenbeck, George E and Ornstein, Leonard S · 1930
Earlier work this paper cites.
A stochastic approximation method
Robbins, Herbert and Monro, Sutton · 1951
Earlier work this paper cites.
On the solution of nonlinear hyperbolic differential equations by finite differences
Courant, Richard, Isaacson, Eugene, and Rees, Mina · 1952
Earlier work this paper cites.
Dynamic programming and Lagrange multipliers
Bellman, Richard · 1956
Earlier work this paper cites.
Systems of conservation laws
Lax, Peter and Wendroff, Burton · 1960
Earlier work this paper cites.
Difference methods and the equations of hydrodynamics
Noh, WF and Protter, MH · 1960
Earlier work this paper cites.
The stability properties of a coupled pair of non-linear partial difference equations
Daly, Bart J · 1963
Earlier work this paper cites.
Some methods of speeding up the convergence of iteration methods
Polyak, Boris T · 1964
Earlier work this paper cites.
Heuristic stability theory for finite-difference equations
Hirt, CW · 1968
Earlier work this paper cites.
The modified equation approach to the stability and accuracy analysis of finite-difference methods
Warming, RF and Hyett, BJ · 1974
Earlier work this paper cites.
Approximate integration of stochastic differential equations
Milstein, GN · 1975
Earlier work this paper cites.
A method of second-order accuracy integration of stochastic differential equations
Milstein, GN · 1979
Earlier work this paper cites.
A method of solving a convex programming problem with convergence rate O(1/k 2 )
Nesterov, Yurii · 1983
Earlier work this paper cites.
Weak approximation of solutions of systems of stochastic differential equations
Milstein, GN · 1986
Earlier work this paper cites.
Mathematical theory of optimal processes
Pontryagin, Lev Semenovich · 1987
Earlier work this paper cites.
Expansion of the global error for numerical schemes solving stochastic differential equations
Talay, Denis and Tubaro, Luciano · 1990
Earlier work this paper cites.
Acceleration of stochastic approximation by averaging
Polyak, Boris T and Juditsky, Anatoli B · 1992
Earlier work this paper cites.
Numerical integration of stochastic differential equations , volume 313
Milstein, GN · 1995
Earlier work this paper cites.
Functional analysis and semi-groups , volume 31
Hille, Einar and Phillips, Ralph Saul · 1996
Earlier work this paper cites.

Similar

The mnist dataset of handwritten digits
LeCun, Yann, Cortes, Corinna, and Burges, Christopher JC · 1998
Cited alongside, same era.
On the momentum term in gradient descent learning algorithms
Qian, Ning · 1999
Cited alongside, same era.
Finite volume methods for hyperbolic problems , volume 31
LeVeque, Randall J · 2002
Cited alongside, same era.
Stochastic approximation and recursive algorithms and applications , volume 35
Kushner, Harold and Yin, G George · 2003
Cited alongside, same era.
Learning multiple layers of features from tiny images
Krizhevsky, Alex and Hinton, Geoffrey · 2009
Cited alongside, same era.
Optimization and Control of Bilinear Systems: Theory, Algorithms, and Applications , volume 11
Pardalos, Panos M and Yatsenko, Vitaliy A · 2010
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, John, Hazan, Elad, and Singer, Yoram · 2011
Cited alongside, same era.
Numerical Solution of Stochastic Differential Equations
Kloeden, P. E. and Platen, E · 2011
Cited alongside, same era.
Non-asymptotic analysis of stochastic approximation algorithms for machine learning
Moulines, Eric and, Francis R · 2011
Cited alongside, same era.
Towards optimal one pass large scale learning with averaged stochastic gradient descent
Original
Xu, Wei · 2011
Cited alongside, same era.
On the existence and the applications of modified equations for stochastic differential equations
Zygalakis, KC · 2011
Cited alongside, same era.
Random perturbations of dynamical systems , volume 260
Freidlin, Mark I, Szücs, Joseph, and Wentzell, Alexander D · 2012
Cited alongside, same era.

Then

Introductory lectures on convex optimization: A basic course , volume 87
Nesterov, Yurii · 2013
Later among the works it cites.
Stochastic differential equations: an introduction with applications
Oksendal, Bernt · 2013
Later among the works it cites.
Adaptive learning rates and parallelization for stochastic, sparse, non-smooth gradients
Original
Schaul, Tom and LeCun, Yann · 2013
Later among the works it cites.
No more pesky learning rates
Schaul, Tom, Zhang, Sixin, and LeCun, Yann · 2013
Later among the works it cites.
Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes
Shamir, Ohad and Zhang, Tong · 2013
Later among the works it cites.
On the importance of initialization and momentum in deep learning
Sutskever, Ilya, Martens, James, Dahl, George, and Hinton, Geoffrey · 2013
Later among the works it cites.
Stochastic gradient descent, weighted sampling, and the randomized algorithm
Needell, Deanna, Ward, Rachel, and Srebro, Nati · 2014
Later among the works it cites.
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
Shalev-Shwartz, Shai and Zhang, Tong · 2014
Later among the works it cites.
A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights
Su, Weijie, Boyd, Stephen, and Candes, Emmanuel · 2014
Later among the works it cites.
A proximal stochastic gradient method with progressive variance reduction
Xiao, Lin and Zhang, Tong · 2014
Later among the works it cites.
Probability measures for numerical solutions of differential equations
Original
Conrad, Patrick R, Girolami, Mark, Särkkä, Simo, Stuart, Andrew, and Zygalakis, Konstantinos · 2015
Closest in time.
Adam: A method for stochastic optimization
Kingma, Diederik and Ba, Jimmy · 2015
Closest in time.
Accelerated mirror descent in continuous and discrete time
Krichene, Walid, Bayen, Alexandre, and Bartlett, Peter L · 2015
Closest in time.
Continuous-time limit of stochastic gradient descent revisited
Mandt, Stephan, Hoffman, Matthew D, and Blei, David M · 2015
Closest in time.
Deep learning with elastic averaging SGD
Zhang, Sixin, Choromanska, Anna E, and LeCun, Yann · 2015
Closest in time.
Learning to learn by gradient descent by gradient descent
Andrychowicz, Marcin, Denil, Misha, Gomez, Sergio, Hoffman, Matthew W, Pfau, David, Schaul, Tom, and de Freitas, Nando · 2016
Closest in time.
A variational analysis of stochastic gradient algorithms
Original
Mandt, Stephan, Hoffman, Matthew D, and Blei, David M · 2016
Closest in time.
A variational perspective on accelerated methods in optimization
Wibisono, Andre, Wilson, Ashia C., and Jordan, Michael I · 2016
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…