Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits

DOI10.1017/JPR.2016.9MaRDI QIDQ3188572zbMATH OpenOpenAlexFDO

Authors Gareth O. Roberts, Jeffrey S. Rosenthal

Publication date 11 August 2016

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

Full work available at URL https://arxiv.org/abs/1411.0712, https://projecteuclid.org/euclid.jap/1466172863, https://semanticscholar.org/paper/f7ad44a706a34be879f3d83496e8f41313dd89af

zbMATH Keywords

complexitydiffusion limitsMarkov chain Monte Carlo algorithmsmetropolis-adjusted Langevin algorithmrandom walk metropolis algorithm

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Sums of independent random variables; random walks (60G50) Discrete-time Markov processes on general state spaces (60J05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational methods in Markov chains (60J22) Continuous-time Markov processes on general state spaces (60J25) Diffusion processes (60J60) Point estimation (62F10) Bayesian inference (62F15) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: We connect known results about diffusion limits of Markov chain Monte Carlo (MCMC) algorithms to the Computer Science notion of algorithm complexity. Our main result states that any diffusion limit of a Markov process implies a corresponding complexity bound (in an appropriate metric). We then combine this result with previously-known MCMC diffusion limit results to prove that under appropriate assumptions, the Random-Walk Metropolis (RWM) algorithm in $d$ dimensions takes $O(d)$ iterations to converge to stationarity, while the Metropolis-Adjusted Langevin Algorithm (MALA) takes $O(d^{1/3})$ iterations to converge to stationarity.

Recommendations

• Diffusion limits of the random walk Metropolis algorithm in high dimensions
• Complexity results for MCMC derived from quantitative bounds
• Computational complexity of Metropolis-Hastings methods in high dimensions
• On the computational complexity of MCMC-based estimators in large samples
• Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields

Cites work

• A class of Wasserstein metrics for probability distributions
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• General state space Markov chains and MCMC algorithms
• Geometric ergodicity and hybrid Markov chains
• Handbook of Markov Chain Monte Carlo
• Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 1482788 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Inference from iterative simulation using multiple sequences
• Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
• Optimal acceptance rates for Metropolis algorithms: Moving beyond 0.234
• Optimal metropolis algorithms for product measures on the vertices of a hypercube
• Optimal scaling for partially updating MCMC algorithms
• Optimal scaling for random walk Metropolis on spherically constrained target densities
• Optimal scaling for the transient phase of Metropolis Hastings algorithms: the longtime behavior
• Optimal scaling for the transient phase of the random walk Metropolis algorithm: the mean-field limit
• Optimal scaling for various Metropolis-Hastings algorithms.
• Optimal Scaling of Discrete Approximations to Langevin Diffusions
• Optimal scaling of random walk Metropolis algorithms with discontinuous target densities
• Optimal scaling of random walk Metropolis algorithms with non-Gaussian proposals
• Optimal scaling of the random walk Metropolis on elliptically symmetric unimodal targets
• Quantitative convergence rates of Markov chains: A simple account
• Rates of convergence for Gibbs sampling for variance component models
• Rates of convergence of the Hastings and Metropolis algorithms
• Sufficient burn-in for Gibbs samplers for a hierarchical random effects model.
• Sufficient conditions for torpid mixing of parallel and simulated tempering
• Weak convergence and optimal scaling of random walk Metropolis algorithms
• Weak convergence of Metropolis algorithms for non-I.I.D. target distributions

Cited in

(17)

• Asymptotic analysis of the random walk metropolis algorithm on ridged densities
• A Dirichlet form approach to MCMC optimal scaling
• Efficiency of delayed-acceptance random walk metropolis algorithms
• Complexity of randomized algorithms for underdamped Langevin dynamics
• High-dimensional scaling limits of piecewise deterministic sampling algorithms
• Optimal scaling of random-walk Metropolis algorithms on general target distributions
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings
• The computational complexity of estimating MCMC convergence time
• Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields
• Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
• On the Power of Restricted Monte Carlo Algorithms
• Reflections on Bayesian inference and Markov chain Monte Carlo
• Complexity results for MCMC derived from quantitative bounds
• Multilevel linear models, Gibbs samplers and multigrid decompositions (with discussion)
• Finite-sample complexity of sequential Monte Carlo estimators
• Weak Poincaré inequalities for Markov chains: theory and applications

This page was built for publication: Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits

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