Spectral gaps for a Metropolis–Hastings algorithm in infinite dimensions

By Martin Hairer, Andrew M. Stuart, Sandra Jeanne Vollmer. 2011

206 citations recorded by the source corpus.

We study the problem of sampling high and infinite dimensional target measures arising in applications such as conditioned diffusions and inverse problems. We focus on those that arise from approximating measures on Hilbert spaces defined via a density with respect to a Gaussian reference measure. We consider the Metropolis–Hastings algorithm that adds an accept–reject mechanism to a Markov chain proposal in order to make the chain reversible with respect to the target measure. We focus on cases where the proposal is either a Gaussian random walk (RWM) with covariance equal to that of the reference measure or an Ornstein–Uhlenbeck proposal (pCN) for which the reference measure is invariant. Previous results in terms of scaling and diffusion limits suggested that the pCN has a convergence rate that is independent of the dimension while the RWM method has undesirable dimension-dependent behaviour. We confirm this claim by exhibiting a dimension-independent Wasserstein spectral gap for pCN algorithm for a large class of target measures. In our setting this Wasserstein spectral gap implies an L^2-spectral gap. We use both spectral gaps to show that the ergodic average satisfies a strong law of large numbers, the central limit theorem and nonasymptotic bounds on the mean square error, all dimension independent. In contrast we show that the spectral gap of the RWM algorithm applied to the reference measures degenerates as the dimension tends to infinity.

Subfields: Applied Mathematics, Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/78f117e2dfee1e8da869938dac5beae25d1cecc8

How researchers see this paper

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

In Applied Mathematics

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Exponential Stability of Slowly Decaying Solutions to the Kinetic-Fokker-Planck Equation (2014, background): “However we note that it had not been proved yet in the probability literature, even in the spatially homogeneous case, that the Poincaré inequality implies the convergence inW1 distance (whereas the converse is known, see for instance [12]).”
Statistical guarantees for Bayesian uncertainty quantification in nonlinear inverse problems with Gaussian process priors (2020, background): “Computational guarantees for convergence of such algorithms are also available in the high-dimensional and non-log-concave setting relevant here, see [27, 45] and references therein.”
Quantitative Harris-type theorems for diffusions and McKean–Vlasov processes (2016, background): “, [8]) and to quantify the dimension dependence in high-dimensional problems [31].”
Statistical Aspects of Wasserstein Distances (2018, background): “Hairer et al. (2014) explore its behaviour in inﬁnite-dimensional state spaces, when taking ﬁnite-dimensional projections of P .”
Quantitative contraction rates for Markov chains on general state spaces (2018, background): “Meanwhile there have been numerous extensions and applications of their result [25, 6, 3, 11].”
Measuring Sample Quality with Diffusions (2016, methodology): “The Stein factor bounds of Theorem 5 can also be used, in the manner of [62, 45, 38], to characterize the error of numerical discretizations of diffusions.”
MCMC Methods for Functions: ModifyingOld Algorithms to Make Them Faster (2012, unknown): “The second approach, namely the use of spectral gaps, oﬀers the opportunity to further substantiate these ideas: in [28] it is shown that the pCN method has a dimension independent spectral gap, whilst a standard random walk which closely resembles it has spectral gap which shrinks with dimension.”