A Complete Recipe for Stochastic Gradient MCMC

By Yian Ma, Yi-An Ma, Tianqi Chen, Emily B. Fox. 2015

537 citations recorded by the source corpus.

Many recent Markov chain Monte Carlo (MCMC) samplers leverage continuous dynamics to define a transition kernel that efficiently explores a target distribution. In tandem, a focus has been on devising scalable variants that subsample the data and use stochastic gradients in place of full-data gradients in the dynamic simulations. However, such stochastic gradient MCMC samplers have lagged behind their full-data counterparts in terms of the complexity of dynamics considered since proving convergence in the presence of the stochastic gradient noise is non-trivial. Even with simple dynamics, significant physical intuition is often required to modify the dynamical system to account for the stochastic gradient noise. In this paper, we provide a general recipe for constructing MCMC samplers--including stochastic gradient versions--based on continuous Markov processes specified via two matrices. We constructively prove that the framework is complete. That is, any continuous Markov process that provides samples from the target distribution can be written in our framework. We show how previous continuous-dynamic samplers can be trivially "reinvented" in our framework, avoiding the complicated sampler-specific proofs. We likewise use our recipe to straightforwardly propose a new state-adaptive sampler: stochastic gradient Riemann Hamiltonian Monte Carlo (SGRHMC). Our experiments on simulated data and a streaming Wikipedia analysis demonstrate that the proposed SGRHMC sampler inherits the benefits of Riemann HMC, with the scalability of stochastic gradient methods.

Subfields: Computational Mechanics, Spectroscopy, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Spectroscopy

In Statistics and Probability

Citations in the corpus

Improving Task-free Continual Learning by Distributionally Robust Memory Evolution (2022, methodology): “We then introduce three speciﬁc memory evolution methods to solve the Dynamic DRO, including Langevin Dynamics (Welling & Teh, 2011), Stein Variational Gradient Descent (Liu & Wang, 2016), and Hamiltonian ﬂow (Ma et al., 2015; Liu et al., 2019).”
Stochastic Gradient Descent as Approximate Bayesian Inference (2017, methodology): “Ma et al. (2015) give a complete classiﬁcation of possible stochastic gradient-based MCMC schemes.”
Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, methodology): “Markov Chain Monte Carlo MCMC methods that sample from a negative log-likelihood Φ(x) have employed the idea of designing a force j = ∇Φ−∇ f to accelerate convergence, see [51] for a thorough survey, or [52, 53] for a rigorous treatment.”
A Variational Analysis of Stochastic Gradient Algorithms (2016, methodology): “If we approximate the posterior p ( θ | x , y , λ ) with some distribution q ( θ ), then VEM tries to ﬁnd a value for λ that maximizes the expected log-joint probability E q [log p ( θ, y | x , λ )].”
Learning Weight Uncertainty with Stochastic Gradient MCMC for Shape Classification (2016, background): “It has been shown that with appropriate functions F and δ, the stationary marginal distribution ρ(θ), of an Itô diffusion (4) has a marginal distribution equal to the posterior distribution [14, 50].”
Magnetic Hamiltonian Monte Carlo (2016, result): “Similar arbitrary, antisymmetric terms have also appeared in the study of MCMC algorithms based on diffusion processes; such samplers often do not enforce detailed balance with respect to the target density and are often implemented as discretizations of stochastic differential equations (Rey-Bellet”
Bayesian Inference for Large Scale Image Classification (2019, background): “The general form of SDEs converging to p ( z ) for which only the gradient of p ( z ) is required is as follows [12]: where D ( z ) is a positive-deﬁnite matrix that determines the amount of noise, Q ( z ) is a skew-symmetric matrix that mixes energy between variables, and Γ( z ) is a correction…”
Deterministic Variational Inference for Robust Bayesian Neural Networks (2018, methodology): “A complete characterization of SG-MCMC methods is given by (Ma et al., 2015; Gong et al., 2018).”
Bayesian Meta Sampling for Fast Uncertainty Adaptation (2020, methodology): “One idea is to use a nonparametric model to generate meta samples such as standard stochastic gradient MCMC (SG-MCMC) (Welling & Teh, 2011; Ma et al., 2015) and the Stein variational gradient descent (SVGD) (Liu & Wang, 2016a), where no parameters are consider in the model.”
Understanding MCMC Dynamics as Flows on the Wasserstein Space (2019, methodology): “In fact, a general MCMC dynamics is only guaranteed to keep the target distribution invariant (Ma et al., 2015), but unnecessarily drives a distribution towards the target steepestly.”
Robust generalised Bayesian inference for intractable likelihoods (2021, unknown): “This enables a variety of exact and approximate algorithms for posterior approximation to be exploited (e.g. Ma et al., 2015).”
Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server (2015, methodology): “…function, stochastic gradient MCMC (Welling and Teh, 2011, Patterson and Teh, 2013, Ding et al., 2014, Teh et al., 2015, Leimkuhler and Shang, 2015, Ma et al., 2015, Li et al., 2016a) which uses minibatch stochastic gradients within MCMC, austerity MCMC (Korattikara et al., 2014, Bardenet et al.,…”
Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning (2019, methodology): “We recommend (Ma et al., 2015) for a general review of SG-MCMC algorithms.”
Action and Perception as Divergence Minimization (2020, background): “Moreover, the dynamics of any stochastic system maximize only its log stationary distribution (Ao et al., 2013; Friston, 2013; Ma et al., 2015).”
Stochastic Normalizing Flows (2020, background): “Because these diﬀusions are frequently used in MCMC algorithms, in a sense, conducting VI with respect to targeted diﬀusions is analogous to optimizing the convergence rate of stochastic MCMC algorithms.”
Stochastic Gradient Markov Chain Monte Carlo (2019, methodology): “Algorithm ζ H(ζ ) D(ζ ) Q(ζ ) SGLD θ U(θ) I 0 SGRLD θ U(θ) G(θ)−1 0 SGHMC (θ , ρ) U(θ) + 12 ρ ρ ( 0 0 0 C ) ( 0 −I I 0 ) SGRHMC (θ , ρ) U(θ) + 12 ρ ρ ( 0 0 0 G(θ)−1 ) ( 0 −G(θ)−1/2 G(θ)−1/2 0 ) SGNHT (θ , ρ, η) U(θ) + 12 ρ ρ + 12d (η − A)2 ⎛ ⎝0 0 00 A · I 0 0 0 0 ⎞ ⎠ ⎛ ⎝0 −I 0I 0 ρ /d 0 −ρ /d 0 ⎞ ⎠ ”
A Unified and General Framework for Continual Learning (2024, background): “Then, D Φ ( p , q ) is equivalent to the cross-entropy loss H ( p , q ) according to Eq.”
Learning Neural Random Fields with Inclusive Auxiliary Generators (2018, methodology): “δt = ( a · ( 1 + t b ))−c like in [21] with (a = 10, b = 1000, c = 2) for all methods, and β = 0.”
Deep convolutional Gaussian processes (2018, background): “ts. due to the multiple channel mappings and the convolution structure. „ere are several avenues for improved e†ciency and modelling capacity. „e Stochastic Gradient Hamiltonian Monte Carlo approach (Ma et al., 2015) has proven e†cient in deep GPs (Havasi et al., 2018) and in GANs (Saatci and Wilson”