Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits. (21st June 2016)

• Record Type: Journal Article
• Authors: Roberts, Gareth O.; Rosenthal, Jeffrey S.
• Is Part Of: Journal of applied probability. Volume 53:Number 2(2016)
• Page Start: 410
• Page End: 420
• Publication Date: 2016-06-21
• Subjects: MCMC, -- convergence, -- complexity, -- diffusion limit, -- random-walk Metropolis algorithm, -- Metropolis-adjusted Langevin algorithm; Primary 60J05, -- 60J25, -- Secondary 62F10, -- 62F15; 519.2
• DOI: 10.1017/jpr.2016.9
• Languages: English
• ISSNs: 0021-9002

Abstract

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.