Diffusion limits of the random walk Metropolis algorithm in high dimensions
arXiv:1003.4306 · doi:10.1214/10-AAP754
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.
Published in at http://dx.doi.org/10.1214/10-AAP754 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (4)
Cited by in corpus (30)
- Dimension-independent likelihood-informed MCMC
- Likelihood-informed dimension reduction for nonlinear inverse problems
- Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
- Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
- 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
- On the Stability of Sequential Monte Carlo Methods in High Dimensions
- Accelerated dimension-independent adaptive Metropolis
- Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions
- MCMC Methods for Functions: Modifying Old Algorithms to Make Them Faster
- Weak Convergence and Optimal Tuning of the Reversible Jump Algorithm
- Weak error estimates for trajectories of SPDEs for Spectral Galerkin discretization
- Optimal Scaling of Random-Walk Metropolis Algorithms on General Target Distributions
- An adaptive independence sampler MCMC algorithm for infinite dimensional Bayesian inferences
- Scalable optimization-based sampling on function space
- Non-local SPDE limits of spatially-correlated-noise driven spin systems derived to sample a canonical distribution
- Random Coordinate Underdamped Langevin Monte Carlo
- On an adaptive preconditioned Crank-Nicolson MCMC algorithm for infinite dimensional Bayesian inferences
- An Introduction to Hamiltonian Monte Carlo Method for Sampling
- Supplement to "Markov Chain Monte Carlo Based on Deterministic Transformations"
- Limiting Behaviors of High Dimensional Stochastic Spin Ensembles
- Non-stationary phase of the MALA algorithm
- Universality of the Langevin diffusion as scaling limit of a family of Metropolis-Hastings processes I: fixed dimension
- A patch that imparts unconditional stability to certain explicit integrators for SDEs
- Bayesian inference using intermediate distribution based on coarse multiscale model for time fractional diffusion equation
- Statistics of Projected Motion in one dimension of a d-dimensional Random Walker
- On Metropolis Integrators for Molecular Dynamics
- Optimal Scaling and Shaping of Random Walk Metropolis via Diffusion Limits of Block-I.I.D. Targets