2016

A Variational Analysis of Stochastic Gradient Algorithms

Mandt, Stephan, Hoffman, Matthew D., Blei, David M.

Understand

Stochastic Gradient Descent (SGD) is an important algorithm in machine learning.

With constant learning rates, it is a stochastic process that, after an initial phase of convergence, generates samples from a stationary distribution.
We show that SGD with constant rates can be effectively used as an approximate posterior inference algorithm for probabilistic modeling.
Specifically, we show how to adjust the tuning parameters of SGD such as to match the resulting stationary distribution to the posterior.

Built on

On the theory of the brownian motion
Uhlenbeck, G. E. and Ornstein, L. S. (1930) · 1930
Earlier work this paper cites.
Brownian motion in a field of force and the diffusion model of chemical reactions
Kramers, H. A. (1940) · 1940
Earlier work this paper cites.
A stochastic approximation method
Robbins, H. and Monro, S. (1951) · 1951
Earlier work this paper cites.
Efficient recursive estimation; application to estimating the parameters of a covariance function
Sakrison, D. J. (1965) · 1965
Earlier work this paper cites.
Handbook of stochastic methods
Gardiner, C. W. et al. (1985) · 1985
Earlier work this paper cites.
Adaptive signal processing
Widrow, B. and Stearns, S. D. (1985) · 1985
Earlier work this paper cites.
Solving large scale linear prediction problems using stochastic gradient descent algorithms
Zhang, T. (2004) · 1985
Earlier work this paper cites.
A fast scoring algorithm for maximum likelihood estimation in unbalanced mixed models with nested random effects
Longford, N. T. (1987) · 1987
Earlier work this paper cites.
Online learning and stochastic approximations
Bottou, L. (1998) · 1998
Earlier work this paper cites.

Similar

Stochastic approximation and recursive algorithms and applications
Kushner, H. J. and Yin, G. (2003) · 2003
Cited alongside, same era.
Pattern Recognition and Machine Learning
Bishop, C. (2006) · 2006
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
Duchi, J., Hazan, E., and Singer, Y. (2011) · 2011
Cited alongside, same era.
Bayesian learning via stochastic gradient langevin dynamics
Welling, M. and Teh, Y. W. (2011) · 2011
Cited alongside, same era.
Bayesian posterior sampling via stochastic gradient fisher scoring
Original
Ahn, S., Korattikara, A., and Welling, M. (2012) · 2012
Cited alongside, same era.
Stochastic approximation and optimization of random systems
Ljung, L., Pflug, G. C., and Walk, H. (2012) · 2012
Cited alongside, same era.
Lecture 6.5—RmsProp: Divide the Gradient by a Running Average of its Recent Magnitude
Tieleman, T. and Hinton, G. (2012) · 2012
Cited alongside, same era.
Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)
Bach, F. and Moulines, E. (2013) · 2013
Cited alongside, same era.
Stochastic gradient hamiltonian monte carlo
Original
Chen, T., Fox, E. B., and Guestrin, C. (2014) · 2014
Cited alongside, same era.
Bridging the gap between stochastic gradient mcmc and stochastic optimization
Original
Chen, C., Carlson, D., Gan, Z., Li, C., and Carin, L. (2015a)
Cited in the paper.
On the convergence of stochastic gradient mcmc algorithms with high-order integrators
Chen, C., Ding, N., and Carin, L. (2015b)
Cited in the paper.
Introduction to variational methods for graphical models
Jordan, M., Ghahramani, Z., Jaakkola, T., and Saul, L. (1999a)
Cited in the paper.

Then

Bayesian sampling using stochastic gradient thermostats
Ding, N., Fang, Y., Babbush, R., Chen, C., Skeel, R. D., and Neven, H. (2014) · 2014
Later among the works it cites.
Approximation analysis of stochastic gradient langevin dynamics by using fokker-planck equation and ito process
Sato, I. and Nakagawa, H. (2014) · 2014
Later among the works it cites.
Statistical analysis of stochastic gradient methods for generalized linear models
Toulis, P., Airoldi, E., and Rennie, J. (2014) · 2014
Later among the works it cites.
Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions
Défossez, A. and Bach, F. (2015) · 2015
Later among the works it cites.
From averaging to acceleration, there is only a step-size
Original
Flammarion, N. and Bach, F. (2015) · 2015
Later among the works it cites.
Automatic variational inference in stan
Kucukelbir, A., Ranganath, R., Gelman, A., and Blei, D. (2015) · 2015
Later among the works it cites.
Dynamics of stochastic gradient algorithms
Original
Li, Q., Tai, C., et al. (2015) · 2015
Later among the works it cites.
A complete recipe for stochastic gradient mcmc
Original
Ma, Y.-A., Chen, T., and Fox, E. B. (2015) · 2015
Later among the works it cites.
Early stopping is nonparametric variational inference
Original
Maclaurin, D., Duvenaud, D., and Adams, R. P. (2015) · 2015
Later among the works it cites.

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…