Diffusion limits of the random walk Metropolis algorithm in high dimensions

DOI10.1214/10-AAP754zbMATH Open1254.60081arXiv1003.4306OpenAlexW2127836946MaRDI QIDQ433896FDOQ433896

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)

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.

Full work available at URL: https://arxiv.org/abs/1003.4306

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

zbMATH Keywords

Markov chain Monte Carlostochastic partial differential equationsoptimal convergencescaling limitsconvergence timedifffusion limitrandom walk Metropolis-Hastings

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (55)

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

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)