Fast Langevin based algorithm for MCMC in high dimensions

Alain Durmus, Gareth O. Roberts, Gilles Vilmart, Konstantinos C. Zygalakis

Abstract

Sampling from high-dimensional target distributions is a fundamental challenge in Bayesian inference and statistical physics. While the standard Metropolis-Adjusted Langevin Algorithm (MALA) achieves a computational complexity of $O(d^{1/3})$, we present a new class of Gaussian proposals—the fast Metropolis-Adjusted Langevin Algorithm (fMALA)—that improves this scaling to $O(d^{1/5})$. By incorporating higher-order information from the Jacobian and Hessian of the target distribution, fMALA minimizes the variance of the log-acceptance ratio. We demonstrate through asymptotic diffusion limit theorems that the optimal acceptance rate for this algorithm is 0.704, and numerical experiments confirm its superior efficiency in high dimensions.

Introduction

Markov Chain Monte Carlo (MCMC) methods are essential for generating samples from complex probability distributions $\pi$. However, as the dimensionality $d$ of the target space increases, traditional algorithms suffer from the "curse of dimensionality." The Random Walk Metropolis (RWM) algorithm, for instance, requires $O(d)$ steps to explore the target distribution effectively. The Metropolis-Adjusted Langevin Algorithm (MALA) utilizes the gradient of the log-density to guide the walker, improving the scaling to $O(d^{1/3})$.

Despite this improvement, $O(d^{1/3})$ remains computationally expensive for modern large-scale models. Furthermore, MALA can exhibit instability and lack geometric ergodicity for certain distribution types. This paper introduces fMALA, which leverages higher-order discretizations of Langevin diffusion to achieve a complexity of $O(d^{1/5})$, alongside robust variants designed for stability.

The fMALA Proposal

The core innovation of fMALA lies in its proposal mechanism. Standard MALA relies on a first-order Euler-Maruyama discretization. In contrast, fMALA utilizes a more sophisticated proposal that integrates:

  1. The Gradient: Directs the walker toward regions of higher probability.
  2. The Jacobian ($Df$): Accounts for the rate of change in the gradient.
  3. The Hessian ($D^2f$): Captures local curvature.

By balancing these terms within the Gaussian proposal’s mean and covariance, fMALA effectively cancels out higher-order error terms in the Taylor expansion of the Metropolis-Hastings acceptance probability. This allows the algorithm to take larger steps without the acceptance rate crashing, leading to faster exploration of the state space.

Theoretical Results and Optimal Tuning

A key contribution of this work is the derivation of the asymptotic diffusion limit. Similar to how RWM and MALA have optimal acceptance rates of 0.234 and 0.574 respectively, we prove that for fMALA, the "sweet spot" for efficiency is an acceptance rate of 0.704. This value is independent of the specific target distribution, providing a practical heuristic for tuning the algorithm in high-dimensional settings.

Furthermore, we show that simply increasing the order of a "weak" integrator is insufficient for improving complexity. The proposal must be specifically engineered to minimize the variance of the log-acceptance ratio, a criterion that fMALA satisfies to achieve its $O(d^{1/5})$ scaling.

Stability and Robustness

High-order methods often risk instability, particularly when the target distribution has heavy tails or when the chain starts in a region of low probability (the "transient phase"). To address this, we introduce two variants:

  • mOMA (modified Ozaki-Metropolis): Tailored for better handling of heavy-tailed distributions.
  • gbOMA (generalized boosted Ozaki-Metropolis): A robust version designed to ensure geometric ergodicity across a broader range of target densities.

These variants ensure that the speed gains of fMALA do not come at the cost of convergence reliability, providing a blueprint for algorithms that are both high-order and theoretically stable.

Numerical Validation

The theoretical gains were validated across several synthetic test-beds:

  • Product Measures: Rigorous confirmation of the $d^{1/5}$ scaling.
  • Double-Well Potential: Demonstrated the algorithm's ability to navigate non-Gaussian, multi-modal landscapes.
  • AR(1) Process with Cauchy Increments: Showed that the efficiency gains persist in correlated, non-Gaussian settings where the variables are not independent.

In these experiments, fMALA exhibited significantly higher first-order efficiency and faster-decaying autocorrelation compared to standard MALA and RWM, particularly as $d$ approached 1000. This confirms that the algorithm produces independent samples much more quickly than its predecessors.

Conclusion and Limitations

fMALA represents a significant step forward in high-dimensional sampling, offering a "pure" win in complexity for models where the Jacobian and Hessian can be computed efficiently (e.g., $O(d)$ for tridiagonal structures). However, the $O(d^2)$ or $O(d^3)$ cost of computing these derivatives in general cases remains a practical constraint. Future work will focus on extending formal proofs of $O(d^{1/5})$ scaling to non-product measures and further refining hybrid strategies to mitigate sensitivity during the transient phase.

Summary updated

Abstract

We introduce new Gaussian proposals to improve the efficiency of the standard Hastings-Metropolis algorithm in Markov chain Monte Carlo (MCMC) methods, used for the sampling from a target distribution in large dimension $d$. The improved complexity is $\mathcal{O}(d^{1/5})$ compared to the complexity $\mathcal{O}(d^{1/3})$ of the standard approach. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterised by its overall acceptance rate (with asymptotical value 0.704), independently of the target distribution. Numerical experiments confirm our theoretical findings.
BibTeX
@article{durmus2015fast,
  author = {Alain Durmus and Gareth O. Roberts and Gilles Vilmart and Konstantinos C. Zygalakis},
  title = {{Fast Langevin based algorithm for MCMC in high dimensions}},
  journal = {The Annals of Applied Probability},
  year = {2015},
}
Figure