Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions

Natesh S. Pillai, Andrew M. Stuart, Alexandre H. ThiéryThe Annals of Applied Probability 2012 · DOI

TL;DR

This paper proves that the Metropolis-Adjusted Langevin Algorithm (MALA) in high dimensions, when applied to complex, correlated probability distributions, converges to an infinite-dimensional diffusion process. This theoretical breakthrough shows MALA is significantly more efficient than Random Walk Metropolis, requiring only $\mathcal{O}(N^{1/3})$ steps to explore the target distribution, and is optimized at an acceptance probability of 0.574.

What Problem Does This Paper Address?

Sampling from complex probability distributions is a cornerstone of modern statistics and machine learning, particularly in areas like Bayesian inference and statistical physics. Markov Chain Monte Carlo (MCMC) methods, like the Metropolis-Adjusted Langevin Algorithm (MALA) and Random Walk Metropolis (RWM), are designed for this. A key challenge is understanding how the computational cost of these algorithms scales with the dimensionality of the problem. Previous work showed that for simple, independent distributions, MALA offered a significant speedup over RWM, scaling as $\mathcal{O}(N^{1/3})$ versus $\mathcal{O}(N)$. However, these results were limited to product distributions. This paper tackles the crucial problem of extending these efficiency gains to more realistic scenarios involving correlated target distributions, which are common in applications like Bayesian nonparametrics and the theory of conditioned diffusions. The authors aim to prove that MALA's efficiency advantage persists even in these more complex, infinite-dimensional settings.

Methods

The core of this paper lies in establishing a diffusion limit for the MALA algorithm. This involves:

  • Continuous Interpolation: The discrete-time MALA Markov chain is "smoothed" into a continuous-time process using a time-acceleration factor that scales with dimension ($N$).
  • Drift-Martingale Decomposition: The MALA algorithm's steps are decomposed into a "drift" term (related to the gradient of the target density) and a "martingale difference" term (representing random fluctuations).
  • Invariance Principle: A key technical result that shows the scaled martingale part of the process behaves like a standard Brownian motion.
  • Weak Convergence: The authors prove that the interpolated MALA process, under appropriate scaling, converges weakly to a solution of a stochastic partial differential equation (SPDE) in an infinite-dimensional Hilbert space. This SPDE represents the limiting diffusion process.
  • Optimal Scaling Analysis: By analyzing the diffusion limit, the paper derives the optimal "tuning" parameter for MALA, which maximizes the exploration speed of the target distribution. This is linked to the average acceptance probability.

The approach builds upon prior work on diffusion limits for MCMC but extends it to handle the complexities of infinite-dimensional Hilbert spaces and correlated target measures, which cannot be reduced to scalar diffusion analyses.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of algorithms applied to abstract probability measures, not specific empirical datasets.

Key Insights and Ideas

  • MALA's Efficiency Extends to Complex Distributions: The most significant insight is that MALA's $\mathcal{O}(N^{1/3})$ scaling advantage over RWM (which scales as $\mathcal{O}(N)$) is not limited to simple product distributions but holds even for complex, correlated distributions in infinite dimensions. This is a major theoretical validation for using MALA in a wider range of applications.
  • Infinite-Dimensional Diffusion Limit: The paper demonstrates that the limiting process for MALA in these complex settings is an infinite-dimensional diffusion, not just a collection of independent scalar diffusions. This highlights the importance of considering the correlation structure.
  • Optimal Acceptance Probability is Universal: The analysis confirms that an average acceptance probability of 0.574 optimizes MALA's performance, a result previously known for simpler targets. This provides a robust practical guideline for tuning MALA.
  • Bridging Theory and Practice: The work provides a strong theoretical foundation for why MALA is often preferred in practice for complex models, offering a rigorous explanation for its observed efficiency.

Key Results

  • Diffusion Limit: The paper proves that a scaled and interpolated version of the MALA Markov chain converges weakly to an infinite-dimensional diffusion process.
  • Computational Complexity: For an $N$-dimensional approximation of the target distribution, MALA requires $\mathcal{O}(N^{1/3})$ steps to explore the invariant measure, a significant improvement over RWM's $\mathcal{O}(N)$ steps.
  • Optimal Tuning: The MALA algorithm is shown to be optimized when the average acceptance probability is approximately 0.574.
  • Generalization: The results extend to a broad class of target measures on infinite-dimensional Hilbert spaces, including those arising in Bayesian nonparametrics and conditioned diffusions, which exhibit correlation.

Limitations and Future Work

  • Assumptions: The analysis relies on specific assumptions about the target distribution (e.g., its decay of eigenvalues, properties of the functional $\Psi$) and the covariance operator $C$. While these assumptions cover important cases, they might not apply to all possible target distributions.
  • Hybrid Monte Carlo (HMC): The paper mentions that HMC requires $\mathcal{O}(N^{1/4})$ steps for simpler targets but lacks a diffusion limit in that context. Extending the current diffusion limit framework to HMC would be a challenging but valuable avenue.
  • Fluid Limit: For chains started far from stationarity, a "fluid limit" (governed by ordinary differential equations) is observed for simpler targets. Investigating whether such limits exist for the more complex targets considered here is suggested.
  • Hierarchical Models: Combining the analysis with MCMC methods for hierarchical target measures is proposed as a source of challenging theoretical questions with direct applicability.
  • Non-Gaussian Priors: Exploring MCMC methods for targets with non-Gaussian product structures (e.g., Besov priors) is suggested as a natural extension.
  • New MCMC Variants: The paper notes the existence of new MCMC variants (RWM, MALA, HMC) for which acceptance probabilities don't degenerate with dimension. Comparing their efficiency with standard methods is an interesting area.

Summary updated

Abstract

The Metropolis-adjusted Langevin (MALA) algorithm is a sampling algorithm which makes local moves by incorporating information about the gradient of the logarithm of the target density. In this paper we study the efficiency of MALA on a natural class of target measures supported on an infinite dimensional Hilbert space. These natural measures have density with respect to a Gaussian random field measure and arise in many applications such as Bayesian nonparametric statistics and the theory of conditioned diffusions. We prove that, started in stationarity, a suitably interpolated and scaled version of the Markov chain corresponding to MALA converges to an infinite dimensional diffusion process. Our results imply that, in stationarity, the MALA algorithm applied to an $N$-dimensional approximation of the target will take $\mathcal{O}(N^{1/3})$ steps to explore the invariant measure, comparing favorably with the Random Walk Metropolis which was recently shown to require $\mathcal{O}(N)$ steps when applied to the same class of problems. As a by-product of the diffusion limit, it also follows that the MALA algorithm is optimized at an average acceptance probability of $0.574$. Previous results were proved only for targets which are products of one-dimensional distributions, or for variants of this situation, limiting their applicability. The correlation in our target means that the rescaled MALA algorithm converges weakly to an infinite dimensional Hilbert space valued diffusion, and the limit cannot be described through analysis of scalar diffusions. The limit theorem is proved by showing that a drift-martingale decomposition of the Markov chain, suitably scaled, closely resembles a weak Euler–Maruyama discretization of the putative limit. An invariance principle is proved for the martingale, and a continuous mapping argument is used to complete the proof.
BibTeX
@article{pillai2012optimal,
  author = {Natesh S. Pillai and Andrew M. Stuart and Alexandre H. Thiéry},
  title = {{Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions}},
  journal = {The Annals of Applied Probability},
  year = {2012},
  doi = {10.1214/11-aap828},
}
Figure