Diffusion limits of the random walk Metropolis algorithm in high dimensions

DOI10.1214/10-AAP754MaRDI QIDQ433896zbMATH OpenOpenAlexFDO

Authors Natesh S. Pillai, A. M. Stuart, Jonathan C. Mattingly

Publication date 8 July 2012

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.4306, https://projecteuclid.org/euclid.aoap/1337347534

zbMATH Keywords

convergence timedifffusion limitMarkov chain Monte Carlooptimal convergencerandom walk Metropolis-Hastingsscaling limitsstochastic partial differential equations

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Discrete-time Markov processes on general state spaces (60J05) Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: Diffusion limits of MCMC methods in high dimensions provide a useful theoretical tool for studying computational complexity. In particular, they lead directly to precise estimates of the number of steps required to explore the target measure, in stationarity, as a function of the dimension of the state space. However, to date such results have mainly been proved for target measures with a product structure, severely limiting their applicability. The purpose of this paper is to study diffusion limits for a class of naturally occurring high-dimensional measures found from the approximation of measures on a Hilbert space which are absolutely continuous with respect to a Gaussian reference measure. The diffusion limit of a random walk Metropolis algorithm to an infinite-dimensional Hilbert space valued SDE (or SPDE) is proved, facilitating understanding of the computational complexity of the algorithm.

Review text

The authors establish a diffusion limit for a random walk Metropolis-Hastings (RWM) algorithm approximating samples from a measure on an infinite-dimensional space, more precisely, for the RWM algorithm applied to distribution families obtained as finite-dimensional approximations to a measure on an separable Hilbert space. In general, diffusion limits are used as a tool to measure the complexity of MCMC methods which have been applied to high-dimensional target measures with product structure. In that case, the individual components of the Markov chain satisfy an invariance principle with respect to a scalar stochastic differential equation. The present paper extends this approach to more general high-dimensional target measures naturally arising in applications. The established invariance principle is such that the entire Markov chain converges to an infinite-dimensional continuous-time stochastic process given by a Hilbert-valued stochastic differential equation, i.e., a stochastic partial differential equations (SPDE).NEWLINENEWLINEIn more detail, the authors consider target measures \(\pi\) on a real separable Hilbert space \(H\) which possess a Radon-Nikodym derivative with respect to a Gaussian measure \(\pi_0\) on \(H\) of the form NEWLINE\[NEWLINE\frac{d\pi}{d\pi_0}=M_\Psi\exp(-\Psi(x))NEWLINE\]NEWLINE for some real, measurable functional \(\Psi\). Then, a realisable implementation (necessarily in finite dimensions) of the RWM algorithm for \(\pi\) is obtained by applying an RWM algorithm for a projection \(\pi^N\) of \(\pi\) on an \(N\)-dimensional subspace of \(H\). The main result of the paper is that started in stationarity the piecewise constant linear interpolants of the Markov chains in the \(N\)-dimensional subspaces converge for \(N\to\infty\) weakly to the solution of an SPDE in a suitable subspace of \(H\) started at \(\pi\) which is the invariant measure for this SPDE. This is proved under a list of assumptions on the function \(\Psi\) and the trace class covariance operator of the Gaussian measure \(\pi_0\) which according to the authors are satisfied in many applications. The practical implications of this result are that at stationarity the work to explore that state space scales as \(\mathcal{O}(N)\) and the speed at which the invariant measure is explored can be maximized by tuning the acceptance rate probability to \(0.234\) analogous to the known case for measures of product structure.

Recommendations

• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• Weak convergence and optimal scaling of random walk Metropolis algorithms
• Diffusion limit for the random walk Metropolis algorithm out of stationarity
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
• Random walk Metropolis algorithm in high dimension with non-Gaussian target distributions

Cites work

• Analysis of SPDEs arising in path sampling. I: The Gaussian case
• Analysis of SPDEs arising in path sampling. II: The nonlinear case
• Approximation of Bayesian Inverse Problems for PDEs
• Asymptotic behaviour of a class of stochastic approximation procedures
• From Metropolis to diffusions: Gibbs states and optimal scaling.
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 520220 (Why is no real title available?)
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• Inverse problems: a Bayesian perspective
• MCMC METHODS FOR DIFFUSION BRIDGES
• MCMC methods for sampling function space
• Monte Carlo sampling methods using Markov chains and their applications
• Monte Carlo strategies in scientific computing.
• Optimal scaling for various Metropolis-Hastings algorithms.
• Optimal Scaling of Discrete Approximations to Langevin Diffusions
• Optimal scaling of MaLa for nonlinear regression.
• Optimal scalings for local Metropolis-Hastings chains on nonproduct targets in high dimensions
• Pathwise accuracy and ergodicity of metropolized integrators for SDEs
• Signal processing problems on function space: Bayesian formulation, stochastic PDEs and effective MCMC methods
• Stein's method for concentration inequalities
• Stochastic Equations in Infinite Dimensions
• Weak convergence and optimal scaling of random walk Metropolis algorithms
• Weak convergence of Metropolis algorithms for non-I.I.D. target distributions

Cited in

(61)

• Asymptotic analysis of the random walk metropolis algorithm on ridged densities
• Hierarchical models: local proposal variances for RWM-within-Gibbs and MALA-within-Gibbs
• Fast Langevin based algorithm for MCMC in high dimensions
• A Dirichlet form approach to MCMC optimal scaling
• Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions
• Multimodal, high-dimensional, model-based, Bayesian inverse problems with applications in biomechanics
• From Metropolis to diffusions: Gibbs states and optimal scaling.
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
• Weak convergence and optimal tuning of the reversible jump algorithm
• Efficiency of delayed-acceptance random walk metropolis algorithms
• Limiting behaviors of high dimensional stochastic spin ensembles
• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• Optimal scaling of the MALA algorithm with irreversible proposals for Gaussian targets
• Optimal scaling of random-walk Metropolis algorithms on general target distributions
• Hierarchical models and tuning of random walk Metropolis algorithms
• Random walk Metropolis algorithm in high dimension with non-Gaussian target distributions
• Non-stationary phase of the MALA algorithm
• Diffusion limit for the random walk Metropolis algorithm out of stationarity
• Optimal scaling for the transient phase of the random walk Metropolis algorithm: the mean-field limit
• Dimension-independent likelihood-informed MCMC
• Scalable posterior approximations for large-scale Bayesian inverse problems via likelihood-informed parameter and state reduction
• On the computational complexity of MCMC-based estimators in large samples
• Optimal tuning of the hybrid Monte Carlo algorithm
• Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions
• On the stability of sequential Monte Carlo methods in high dimensions
• Scaling analysis of delayed rejection MCMC methods
• Langevin type limiting processes for adaptive MCMC
• Accelerated dimension-independent adaptive metropolis
• On the empirical efficiency of local MCMC algorithms with pools of proposals
• Dimension-Independent MCMC Sampling for Inverse Problems with Non-Gaussian Priors
• Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits
• Computational complexity of Metropolis-Hastings methods in high dimensions
• A hybrid adaptive MCMC algorithm in function spaces
• An Adaptive Independence Sampler MCMC Algorithm for Bayesian Inferences of Functions
• Bayesian inference using intermediate distribution based on coarse multiscale model for time fractional diffusion equations
• Optimal scaling for the transient phase of Metropolis Hastings algorithms: the longtime behavior
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• Noisy gradient flow from a random walk in Hilbert space
• Interacting Langevin diffusions: gradient structure and ensemble Kalman sampler
• Scalable Optimization-Based Sampling on Function Space
• A Bayesian Approach to Estimating Background Flows from a Passive Scalar
• Asymptotic variance for random walk Metropolis chains in high dimensions: logarithmic growth via the Poisson equation
• Bayesian computational methods for estimation of two-parameters Weibull distribution in presence of right-censored data
• Bayesian inverse problems with l₁ priors: a randomize-then-optimize approach
• High dimensional simulation
• A function space HMC algorithm with second order Langevin diffusion limit
• MCMC methods for functions: modifying old algorithms to make them faster
• Spectral gaps and error estimates for infinite-dimensional Metropolis-Hastings with non-Gaussian priors
• Certified Dimension Reduction for Bayesian Updating with the Cross-Entropy Method
• A hierarchical Bayesian approach for modeling the evolution of the 7-day moving average of the number of deaths by COVID-19
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• Asymptotic bias of inexact Markov chain Monte Carlo methods in high dimension
• Noise-free sampling algorithms via regularized Wasserstein proximals
• Weak neural variational inference for solving Bayesian inverse problems \textit{without} forward models: applications in elastography
• On an adaptive preconditioned Crank-Nicolson MCMC algorithm for infinite dimensional Bayesian inference
• An extended sampling-Bayesian approach for inverse elastic scattering problems with limited aperture data
• High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance
• Convergence of Dirichlet forms for MCMC optimal scaling with dependent target distributions on large graphs
• Optimal scaling for the proximal Langevin algorithm in high dimensions
• A replica exchange preconditioned Crank-Nicolson Langevin dynamic MCMC method with multi-variance strategy for Bayesian inverse problems
• Large deviations for independent Metropolis Hastings and Metropolis-adjusted Langevin algorithm

This page was built for publication: Diffusion limits of the random walk Metropolis algorithm in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433896)