Bayesian inference provides a rigorous framework for uncertainty quantification by computing a full posterior distribution over model parameters. However, traditional Markov Chain Monte Carlo (MCMC) algorithms—the gold standard for generating samples from these posteriors—suffer from a severe scalability bottleneck.
To evaluate a single parameter update or decide whether to accept a proposed state transition, standard MCMC samplers must compute the likelihood of the entire dataset. This means the computational cost per step scales linearly ($O(N)$) with the number of data points. For modern datasets containing millions or billions of observations, this full-batch requirement makes exact Bayesian inference computationally intractable.
The Problem with Naive Subsampling
In optimization, we routinely bypass full-batch bottlenecks by using mini-batches. Stochastic Gradient Descent (SGD) computes gradients on small, random subsets of data. While this introduces stochastic noise, the noise averages out over many iterations, allowing the parameters to drift reliably toward a local minimum.
Why can't we do the same for MCMC sampling?
In optimization, we only care about finding a single point: the mode. In sampling, we want to map the geometry of the entire distribution. When we substitute a mini-batch gradient for a full-batch gradient in a standard sampler, the mini-batch subsampling introduces an uncontrolled source of variance. This variance acts as an artificial, fluctuating "temperature" that distorts the target distribution. Instead of exploring the true posterior, the sampler explores a smeared-out distribution, introducing severe and irreducible simulation biases.
As Betancourt demonstrated in The Fundamental Incompatibility of Scalable Hamiltonian Monte Carlo and Naive Data Subsampling, this stochastic noise fundamentally destroys the geometric conservation laws that allow advanced samplers like Hamiltonian Monte Carlo (HMC) to explore high-dimensional spaces efficiently. Without a full-dataset evaluation to perform a Metropolis-Hastings correction step, naive subsampling causes the simulation to fall apart.
Overwhelming the Noise: Stochastic Gradient Langevin Dynamics
The breakthrough that unlocked large-scale sampling was Stochastic Gradient Langevin Dynamics (SGLD), introduced by Max Welling and Yee Whye Teh in Bayesian Learning via Stochastic Gradient Langevin Dynamics.
SGLD builds on Langevin dynamics, a mathematical model of a particle moving through a fluid under the influence of a potential field (the gradient of our posterior) and thermal fluctuations (injected Gaussian noise). The standard continuous-time Langevin update is:
$$\Delta \theta_t = \frac{\epsilon_t}{2} \nabla \log p(\theta_t | X) + \eta_t, \quad \eta_t \sim \mathcal{N}(0, \epsilon_t)$$
If we replace the full gradient $\nabla \log p(\theta_t | X)$ with a mini-batch estimate, we introduce an additional noise term $\mathcal{V}_t$ due to subsampling variance. The actual update becomes:
$$\Delta \theta_t = \frac{\epsilon_t}{2} \left[ \nabla \log p(\theta_t | X_{batch}) \right] + \eta_t = \frac{\epsilon_t}{2} \nabla \log p(\theta_t | X) + \frac{\epsilon_t}{2} \mathcal{V}_t + \eta_t$$
Here lies the core intuition of SGLD: look at how the two noise terms scale with the step size $\epsilon_t$.
- The variance of the injected tracking noise $\eta_t$ scales linearly with $\epsilon_t$.
- The variance of the mini-batch gradient noise term $\frac{\epsilon_t}{2} \mathcal{V}_t$ scales quadratically with $\epsilon_t^2$.
By systematically annealing (decaying) the step size $\epsilon_t$ toward zero over time, the $\epsilon_t^2$ term shrinks much faster than the $\epsilon_t$ term. Eventually, the injected Gaussian noise completely overwhelms the mini-batch noise. As a result, the system undergoes a phase transition: early on (large $\epsilon_t$), it behaves like standard SGD optimization, rapidly finding the high-probability regions of the model. Later on (small $\epsilon_t$), it transitions into a valid posterior sampler, bypassing the need for expensive full-dataset Metropolis-Hastings rejection checks.
Adding Friction: Thermostats for Momentum Samplers
While SGLD scales gracefully to large datasets, it shares a fundamental limitation with standard Langevin dynamics: it explores the parameter space via a slow, diffusive random walk. To sample efficiently from complex, high-dimensional distributions, we need momentum-based methods like Hamiltonian Monte Carlo (HMC), which glide smoothly across the posterior landscape.
However, when we introduce mini-batch gradients to HMC, the stochastic noise acts as a continuous injection of kinetic energy. In a physical system, pumping in energy without a cooling mechanism causes the temperature to rise uncontrollably. In a simulation, this causes the sampler to fly off target.
To counteract this destabilization, Tianqi Chen et al. proposed Stochastic Gradient Hamiltonian Monte Carlo (SGHMC). They introduced a friction term into the system's dynamics to dissipate the excess energy injected by the mini-batches. By balancing the injected stochastic noise with a corresponding friction coefficient, the system maintains a stable kinetic energy profile, allowing the sampler to preserve its momentum without blowing up.
Mini-batch Subsampling ──> Injects Uncontrolled Heat (Variance) ──┐
├──> Destabilizes Sampler
Friction / Thermostat ──> Dissipates Excess Energy ──┘
In practice, calculating the exact amount of friction needed requires knowing the precise covariance of the mini-batch noise, which changes depending on where you are in the parameter space. To automate this, Nan Ding et al. developed Bayesian Sampling Using Stochastic Gradient Thermostats. They adapted the Nosé-Hoover thermostat from statistical physics, introducing a dynamic variable that automatically increases friction when the system gets too hot and decreases it when the system cools down. This ensures the simulation remains at the correct thermodynamic temperature for accurate posterior sampling.
Eliminating Noise: Variance-Reduced MCMC
Rather than designing clever physical mechanisms like friction to fight mini-batch noise, an alternative paradigm seeks to eliminate the noise at its source using variance reduction techniques borrowed from stochastic optimization (such as SVRG and SAGA).
Difan Zou et al. introduced this concept to momentum samplers in Stochastic Variance-Reduced Hamilton Monte Carlo Methods (SVR-HMC). The core mechanic relies on an anchor point $\tilde{\theta}$, where a full-batch gradient is computed occasionally. For subsequent mini-batch steps, the gradient estimate is adjusted by tracking how much the mini-batch gradient shifts relative to that anchor point:
$$\nabla \log p(\theta | X_{batch}) - \nabla \log p(\tilde{\theta} | X_{batch}) + \nabla \log p(\tilde{\theta} | X)$$
As the sampler converges toward a high-probability region, the current parameter $\theta$ stays close to the anchor $\tilde{\theta}$. Consequently, the difference between their mini-batch gradients shrinks, and the variance of the estimator drops dramatically toward zero.
Expanding on this, Zhize Li 0001 et al. demonstrated in Stochastic gradient Hamiltonian Monte Carlo with variance reduction for Bayesian inference that combining variance-reduced estimators with high-order numerical splitting schemes yields faster convergence and tighter error bounds. Because the gradient noise vanishes asymptotically, these samplers can maintain large step sizes and high momentum without suffering from the chaotic thermal destabilization typical of standard stochastic updates.