Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits. (21st June 2016) - Roberts, Gareth O.; Rosenthal, Jeffrey S.
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 weak 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 algorithm in d dimensions takes O ( d ) iterations to converge to stationarity, while the Metropolis-adjusted Langevin algorithm takes O ( d 1/3 ) iterations to converge to stationarity.