In high-dimensional Bayesian inference, we often need to sample from a target distribution $\pi(x) \propto \exp(-U(x))$. While the Langevin diffusion process provides a continuous-time path toward this distribution, implementing it on a computer requires discretization. This transition from continuous flow to discrete steps introduces a fundamental challenge: discretization bias.
The Speed-Accuracy Tradeoff
The most direct way to sample using gradients is the Unadjusted Langevin Algorithm (ULA). As explored by Alain Durmus and Eric Moulines in Nonasymptotic convergence analysis for the unadjusted Langevin algorithm, ULA omits the Metropolis-Hastings "rejection step" to maximize computational speed.
However, this speed comes at a cost. Without an adjustment step, the algorithm does not converge to the true target distribution $\pi$, but rather to a biased stationary distribution $\pi_\gamma$ that depends on the step size $\gamma$. This creates a persistent tension:
- Large step sizes allow the chain to explore the space rapidly and converge quickly to a stationary distribution.
- Small step sizes reduce the distance between the biased distribution $\pi_\gamma$ and the true target $\pi$, but significantly slow down the rate of convergence.
Quantifying the Bias
Recent theoretical work has shifted from asymptotic "limit" results to non-asymptotic bounds. In Sampling from a strongly log-concave distribution with the Unadjusted Langevin Algorithm, Durmus and Moulines provide explicit bounds on how this error scales with the dimension of the problem. They show that for log-concave targets, ULA can be remarkably efficient, provided one carefully manages the step size to balance the remaining bias against the time spent sampling.
This framework has been extended to more complex scenarios, such as Stochastic Gradient MCMC Methods for Hidden Markov Models by Yi-An Ma and Emily Fox. In these large-scale settings, the bias arises not just from discretization, but also from the noise in the stochastic gradient estimates.
Mitigating Bias Without Rejection
Because the Metropolis-Hastings adjustment can be computationally prohibitive in high dimensions, researchers have developed alternative ways to "correct" the bias:
- Extrapolation: Alain Durmus and Umut Simsekli introduced Stochastic Gradient Richardson-Romberg Markov Chain Monte Carlo. This method runs multiple chains with different step sizes and combines them to cancel out the first-order bias terms, achieving higher accuracy without the cost of a rejection step.
- Taming: In The tamed unadjusted Langevin algorithm, Nicolas Brosse and colleagues address stability. When the gradient of the potential grows too quickly, standard ULA can diverge; "taming" the updates ensures the algorithm remains stable even in steep landscapes.
- Score Matching: Newer approaches like Score-Based Metropolis-Hastings Algorithms by Ahmed Aloui and Ali Hasan attempt to re-introduce the adjustment step efficiently by learning the score function, bridging the gap between unadjusted speed and adjusted exactness.
By understanding ULA as a biased approximation, researchers can now deploy it as a powerful tool for optimization and inference, as seen in the SOUL framework by Valentin De Bortoli and Marcelo Pereyra, where "inexact" sampling is used to solve otherwise intractable high-dimensional optimization problems.