Exact Langevin Dynamics with Stochastic Gradients

Adrià Garriga-Alonso, Vincent Fortuin

TL;DR

Widely used stochastic gradient MCMC algorithms like SGHMC rely on an Euler-Maruyama discretization that makes backward transitions mathematically impossible, forcing their Metropolis-Hastings (MH) acceptance probability to zero. The authors show that switching to a time-reversible integrator—Gradient-Guided Monte Carlo (GGMC)—yields non-zero acceptance probabilities, allowing researchers to perform exact posterior sampling with mini-batch gradients by amortizing the MH correction step over multiple iterations.

What Problem Does This Paper Address?

Bayesian deep learning often requires sampling from intractable, high-dimensional posteriors. Standard Hamiltonian Monte Carlo (HMC) is considered the gold standard for continuous state spaces, but it requires computing gradients over the entire dataset at every step—an intractable cost for modern deep learning.

To scale up, practitioners turn to Stochastic Gradient MCMC (SG-MCMC) methods such as Stochastic Gradient Langevin Dynamics (SGLD) and Stochastic Gradient HMC (SGHMC). However, using stochastic mini-batch gradients and numerical discretizations introduces asymptotic bias. In traditional MCMC, this error is corrected via Metropolis-Hastings (MH) rejection steps to ensure the sampler draws from the true posterior.

This paper highlights a fundamental roadblock in existing SG-MCMC literature: the standard symplectic Euler-Maruyama integrator used in SGHMC has a backward transition probability of exactly zero. As a result, it is mathematically impossible to apply an MH correction to SGHMC, leaving its discretization error permanently uncorrected.

Methods

  1. Proof of Zero Acceptance Probability (Theorem 1): The authors demonstrate that in the standard Euler-Maruyama discretization of second-order Langevin dynamics, the position update is deterministically tied to the forward momentum update ($\theta_{n+1} = \theta_n + h M^{-1} m_{n+1}$). For the reverse step to be valid, the forward and backward momentum must be identical ($m_n = m_{n+1}$), an event that occurs with probability zero under Gaussian noise.
  2. Revisiting Gradient-Guided Monte Carlo (GGMC): The authors replace Euler-Maruyama with the time-reversible OBABO operator-splitting scheme (first introduced by Horowitz in 1991). GGMC splits Langevin dynamics into:
  3. Partial momentum refreshment (O)
  4. Leapfrog updates consisting of half-step momentum kicks (B) and full-step coordinate drifts (A)
  5. Multi-Step Deferred MH Corrections: To avoid evaluating the entire dataset's likelihood at every step, the authors leverage an augmented multi-step framework. By treating the intermediate noise draws as auxiliary variables in a time-symmetric schedule, one can execute $N$ stochastic gradient steps and compute a single telescoping MH correction on the exact likelihood at the end of the trajectory.

Datasets

Not discussed in the paper. (The paper is purely theoretical and methodological, providing mathematical proofs and algorithmic formulations without empirical benchmark experiments.)

Key Insights and Ideas

  • Euler-Maruyama irrevocably breaks detailed balance: Because the backward path is unrealizable, the discretization error of standard SGHMC cannot be monitored or corrected via acceptance rates, regardless of how small the step size $h$ is.
  • GGMC unifies HMC and SGLD:
  • When friction $\gamma \to 0$ (no momentum decay, $a = 1$), GGMC reduces to leapfrog steps with occasional momentum refreshment (standard HMC).
  • When $\gamma \to \infty$ (complete momentum refreshment, $a \to 0$), incoming momentum is discarded at each step, recovering SGLD/MALA.
  • Invariance to momentum decay: The single-step MH acceptance probability of GGMC depends solely on the potential energy change and the kinetic energy across the inner leapfrog step; it is completely independent of the momentum refreshment parameter $a = e^{-\gamma h}$.
  • Schedules must be time-symmetric: Popular optimization tricks like cyclical cosine learning rate schedules violate time-reversibility ($f_i \neq f_{N-i+1}$), automatically driving the multi-step acceptance probability to zero unless redesigned to be symmetric.

Key Results

  • Theorem 1: For any step size $h > 0$ and any starting point $(\theta_n, m_n)$, the backward transition density $g(\theta_n, -m_n \mid \theta_{n+1}, -m_{n+1})$ under Euler-Maruyama is zero with probability 1.
  • Closed-Form Acceptance Ratio: The authors derive the exact log-acceptance ratio for GGMC: $$\log \text{MH} = -\frac{1}{T} \left[ U(\theta_{n+1}) - U(\theta_n) + K(m_{n+3/4}) - K(m_{n+1/4}) \right]$$ demonstrating that GGMC maintains a non-zero, well-behaved acceptance probability under stochastic dynamics.

Limitations and Future Work

  • Full-batch evaluation overhead: While deferred MH corrections avoid per-step full-dataset evaluations, an exact posterior still requires periodically calculating the full likelihood (e.g., once every epoch or multi-step cycle).
  • High-variance rejections: In deep neural networks with noisy stochastic gradients, the discrepancy between the accumulated stochastic trajectory and the true potential could lead to low acceptance rates over long multi-step intervals.
  • Lack of empirical validation: The paper does not provide empirical tests on large neural networks to measure practical acceptance rates, effective sample sizes, or wall-clock training times compared to biased SG-MCMC.

Summary updated

Abstract

Stochastic gradient Markov Chain Monte Carlo algorithms are popular samplers for approximate inference, but they are generally biased. We show that many recent versions of these methods (e.g. Chen et al. (2014)) cannot be corrected using Metropolis-Hastings rejection sampling, because their acceptance probability is always zero. We can fix this by employing a sampler with realizable backwards trajectories, such as Gradient-Guided Monte Carlo (Horowitz, 1991), which generalizes stochastic gradient Langevin dynamics (Welling and Teh, 2011) and Hamiltonian Monte Carlo. We show that this sampler can be used with stochastic gradients, yielding nonzero acceptance probabilities which can be computed even across multiple steps.
BibTeX
@inproceedings{garrigaalonso2020exact,
  author = {Adrià Garriga-Alonso and Vincent Fortuin},
  title = {{Exact Langevin Dynamics with Stochastic Gradients}},
  booktitle = {AABI},
  year = {2020},
  url = {https://openreview.net/forum?id=Rprd8aVUYkE},
}

Loading related content...

Figure