A Variational Analysis of Stochastic Gradient Algorithms

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

180 citations recorded by the source corpus.

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. This analysis rests on interpreting SGD as a continuous-time stochastic process and then minimizing the Kullback-Leibler divergence between its stationary distribution and the target posterior. (This is in the spirit of variational inference.) In more detail, we model SGD as a multivariate Ornstein-Uhlenbeck process and then use properties of this process to derive the optimal parameters. This theoretical framework also connects SGD to modern scalable inference algorithms; we analyze the recently proposed stochastic gradient Fisher scoring under this perspective. We demonstrate that SGD with properly chosen constant rates gives a new way to optimize hyperparameters in probabilistic models.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training, Statistical Learning Theory

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

In Statistical Learning Theory

Citations in the corpus

Entropy-SGD: biasing gradient descent into wide valleys (2016, neutral): “…as follows: Secondly, Langevin dynamics in (11) is the discrete-time approximation of a continuous-time stochastic differential equation (Mandt et al., 2016) thereby necessitating a Metropolis-Hastings (MH) rejection step (Roberts & Stramer, 2002) which again requires computing p ( ξ k…”
Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples (2017, background): “Then, the parameters estimated in each iteration can be viewed, approximately, as samples drawn from the posterior distribution of the parameters Pr(W = w|Y,X) [31].”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, methodology): “We evaluate the diagonal-SGFS and constant-SGD algorithms from [18] in this work.”
Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, methodology): “…and implicit regularization: The idea that SGD is related to variational inference has been seen in machine learning before (Duvenaud et al., 2016; Mandt et al., 2016) under assumptions such as quadratic steady-states; for instance, see Mandt et al. (2017) for methods to approximate steady-states…”
Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms (2015, methodology): “Related work in SDE approximations of the SGD are Mandt et al. (2015, 2016), where the authors derived the ﬁrst order SME heuristically.”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, methodology): “Finally, it is worth mentioning [35, 36] which are interested in showing that the invariant measure of constant step-size SGD for an appropriate choice of the step-size γ, can be used as a proxy to approximate the target distribution π with density with respect to the Lebesgue measure e−f .”
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (2019, methodology): “A popular approach for investigating the behavior SGD is based on considering SGD as a discretization of a continuous-time process (Mandt et al., 2016; Jastrzebski et al., 2017; Li et al., 2017a; Hu et al., 2017; Zhu et al., 2018; Chaudhari & Soatto, 2018).”
Sample-then-optimize posterior sampling for Bayesian linear models (2017, background): “There is therefore a growing literature attempting to understand how Bayesian posterior inference could emerge from the complexity of modern practice [2, 3], even without having such a procedure as the stated goal.”
Efficient Gaussian Process Classification Using Polya-Gamma Data Augmentation (2018, methodology): “We compare our proposed method, efficient Gaussian process classification (x-gpc), with the state-of-the-art methods svgpc Salimbeni, Eleftheriadis, and Hensman (2018), provided in the package GPflow3 Matthews et al. (2017), which builds on TensorFlow and the EP approach epgpc by Hernández-Lobato an”
Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning (2020, methodology): “In this sense, the SDE of S GD in [25–27, 34, 37] is actually a special case of the Lévy-driven SDE in this work.”
Advances in Variational Inference (2017, methodology): “Some of these approaches are generally applicable in SGD.”
Two Methods for Wild Variational Inference (2016, methodology): “…work: one based on “amortizing SVGD” (Wang & Liu, 2016) which trains the inference network f(η, ξ) so that its output mimic the SVGD dynamics in order to decrease the KL divergence; another based on minimizing the KSD objective (9) which does not require to evaluate q(z) thanks to its special form.”
Multi-Class Gaussian Process Classification Made Conjugate: Efficient Inference via Data Augmentation (2019, methodology): “We follow an approximate approach and optimize the fitted variational lower bound L(h) as a function of h by alternating between optimization steps w.r.t. the variational parameters and the hyperparameters (Mandt et al., 2016).”
On Learning Rates and Schrödinger Operators (2020, methodology): “In the stochastic setting, this approach has been recently pursued by various authors [COO + 18, CS18, MHB16, LSJR16, CH19, LTE17] to establish various properties of stochastic optimization.”
Wild Variational Approximations (2016, background): “(Stochastic gradient descent (SGD) with constant/adaptive learning rates) It has been shown in [23, 24] that the trajectory of SGD with constant/adaptive learning rates near a local optimum can be viewed as a variational approximation to the exact posterior.”