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

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.

Published in at http://dx.doi.org/10.1214/11-AAP828 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Sparse Deterministic Approximation of Bayesian Inverse Problems
• Optimal scalings for local Metropolis--Hastings chains on nonproduct targets in high dimensions
• The Random Walk Metropolis: Linking Theory and Practice Through a Case Study
• Weak convergence of Metropolis algorithms for non-i.i.d. target distributions
• Optimal Scaling of Mala for Nonlinear Regression

Cited by in corpus (21)

• A Survey of Monte Carlo Methods for Parameter Estimation
• Dimension-independent likelihood-informed MCMC
• On the efficiency of pseudo-marginal random walk Metropolis algorithms
• Likelihood-informed dimension reduction for nonlinear inverse problems
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Scalable posterior approximations for large-scale Bayesian inverse problems via likelihood-informed parameter and state reduction
• Optimal scaling for the transient phase of Metropolis Hastings algorithms: The longtime behavior
• Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions
• Optimal scaling for the transient phase of the random walk Metropolis algorithm: The mean-field limit
• Accelerated dimension-independent adaptive Metropolis
• MCMC Methods for Functions: Modifying Old Algorithms to Make Them Faster
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
• Generalized Bayesian Likelihood-Free Inference
• Efficient constrained sampling via the mirror-Langevin algorithm
• Path integral Monte Carlo with importance sampling for excitons interacting with an arbitrary phonon bath
• An Introduction to Hamiltonian Monte Carlo Method for Sampling
• Random Coordinate Underdamped Langevin Monte Carlo
• Non-stationary phase of the MALA algorithm
• Optimal Scaling and Shaping of Random Walk Metropolis via Diffusion Limits of Block-I.I.D. Targets
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities