Diffusion limits of the random walk metropolis algorithm in high dimensions

By Jonathan C. Mattingly, Natesh S. Pillai, Andrew M. Stuart. 2010

118 citations recorded by the source corpus.

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.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/cba5e11ff65565b510b8cfd67fb42e5053fcfa25

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The Bayesian Approach to Inverse Problems (2013, methodology): “The SPDE limit theorem is built on these ideas and may be found in [MPS11], and on the arxiv at [MPS10].”
On the stability of sequential Monte Carlo methods in high dimensions (2011, methodology): “As in [38, 42] we consider a target distribution on an infinite-dimensional separable Hilbert space H determined via the change of measure {d /d 0}(x) ∝ exp{− (x)}, x ∈ H,”
Spectral gaps for a Metropolis–Hastings algorithm in infinite dimensions (2011, background): “In a similar setup it was recently shown [35] that there is a μ-reversible SPDE limit if the product law is a truncated Karhunen-Loeve expansion.”
MCMC Methods for Functions: ModifyingOld Algorithms to Make Them Faster (2012, methodology): “Furthermore, the papers [37, 45] identify diffusion limits of the standard random walk and of the pCN method; the scalings required for the proposal variance β reflect the dimension-dependence of the standard random walk, and the dimension-independent properties of the pCN method.”
Optimal Scaling and Diffusion Limits for the Langevin Algorithm in High Dimensions (2011, methodology): “In [19] the RWM algorithm is studied when applied to a sequence of finite dimensional approximations of π as in (1.”