Exact Langevin Dynamics with Stochastic Gradients

Adrià Garriga-Alonso, Vincent Fortuin

Abstract

Popular stochastic gradient MCMC methods, such as SGHMC, are fundamentally biased because their mathematical structure—specifically the Euler-Maruyama integrator—makes Metropolis-Hastings (MH) correction impossible. In these frameworks, the backward transition probability is zero, leading to a zero acceptance rate. This paper demonstrates that by adopting "backward-realizable" integrators from molecular dynamics, specifically Gradient-Guided Monte Carlo (GGMC), researchers can calculate valid acceptance probabilities. This enables exact Bayesian inference even when using noisy, stochastic gradients through a deferred correction mechanism.

Introduction

In Bayesian deep learning, the goal is to sample from the posterior distribution of model parameters. While Hamiltonian Monte Carlo (HMC) is the standard for high-quality sampling, its requirement for full-dataset gradients makes it prohibitively slow for large-scale models. Stochastic Gradient MCMC (SG-MCMC) methods like SGLD and SGHMC address this by using minibatches. However, the noise introduced by minibatches creates a bias that is typically ignored. Standard statistical practice uses a Metropolis-Hastings (MH) step to correct such biases, but as this paper reveals, popular SG-MCMC methods are mathematically incompatible with MH correction.

The Irreversibility Trap

The authors provide a formal proof (Theorem 1) showing that for any step size $h > 0$, the backward transition density of SGHMC is zero. This "unrealizability" stems from the Euler-Maruyama discretization. If an algorithm cannot theoretically "return" to its starting state, the MH ratio becomes zero, and the bias cannot be corrected. This means the bias in SGHMC is not just a practical nuisance but is fundamentally baked into the integrator choice.

Gradient-Guided Monte Carlo (GGMC)

To overcome this, the paper proposes using the Gradient-Guided Monte Carlo (GGMC) framework, employing a "backward-realizable" integration scheme known as OBABO (or BAOAB). This scheme decomposes the dynamics into three distinct operations:

  1. O (Ornstein-Uhlenbeck): Partial momentum refreshment.
  2. B (Burnside/Kick): Update momentum based on the gradient of potential energy.
  3. A (Action/Drift): Update position based on current momentum.

By ensuring the integrator is reversible, the authors can implement a deferred correction scheme. Instead of an expensive MH step at every minibatch, they run the sampler for several epochs using stochastic gradients and perform a single MH correction using the exact likelihood (calculated over the full dataset) at the end of the cycle.

Experimental Results

The authors evaluated GGMC against HMC using a ResNet-20 architecture on the CIFAR-10 dataset. This represents a high-dimensional, non-convex challenge for Bayesian sampling.

Comparison of GGMC and HMC stability. GGMC (top row) maintains stable kinetic and potential energy across various learning rates, whereas HMC (bottom row) exhibits significant instability and energy spikes at higher learning rates.

As shown in the figure above, GGMC demonstrates superior stability compared to HMC. While HMC's kinetic energy spikes dramatically as the learning rate increases (bottom-right), GGMC remains remarkably flat (top-right). Furthermore, while the log-acceptance probabilities for such a high-dimensional model are naturally low (around $-10^4$), they are non-zero and mathematically valid in GGMC, allowing for the first time a way to monitor the "health" of the stochastic sampler.

Conclusion and Future Work

GGMC provides a unified bridge between SGLD (infinite friction) and HMC (zero friction), offering a path toward exact inference with stochastic gradients. However, challenges remain. The acceptance probability, while non-zero, is still very low in high dimensions, which may lead to high rejection rates in practice. Additionally, the requirement for time-symmetry means that common optimization tricks, such as cosine learning rate schedules, cannot be directly applied without breaking the mathematical guarantees. Future research is needed to adapt these dynamic schedules while maintaining the reversibility required for exact Langevin dynamics.

Summary updated

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},
}
Figure