Optimal Scaling and Diffusion Limits for the Langevin Algorithm in High Dimensions

By Natesh S. Pillai, Andrew M. Stuart, Alexandre Hoang Thiery. 2011

106 citations recorded by the source corpus.

The Metropolis-adjusted Langevin (MALA) algorithm is a sampling algorithm which makes local moves by incorporating information about the gradient of the logarithm of the target density. In this paper we study the efficiency of MALA on a natural class of target measures supported on an infinite dimensional Hilbert space. These natural measures have density with respect to a Gaussian random field measure and arise in many applications such as Bayesian nonparametric statistics and the theory of conditioned diffusions. We prove that, started in stationarity, a suitably interpolated and scaled version of the Markov chain corresponding to MALA converges to an infinite dimensional diffusion process. Our results imply that, in stationarity, the MALA algorithm applied to an N-dimensional approximation of the target will take $\mathcal{O}(N^{1/3})$ steps to explore the invariant measure, comparing favorably with the Random Walk Metropolis which was recently shown to require $\mathcal{O}(N)$ steps when applied to the same class of problems.

Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/4deed2c354c042791aa3a75af25dfcc020997e1f

How researchers see this paper

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

In Artificial Intelligence

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, methodology): “For MALA algorithms an optimal acceptance rate of 0.574 has been established in Roberts and Rosenthal (1998) and con-ﬁrmed in inﬁnite-dimensional settings in Pillai et al. (2012) ) .”
Proximal Markov chain Monte Carlo algorithms (2013, background): “Theoretical and experimental studies of MALA show that for many high-dimensional target densities the value of δ should be set to achieve an acceptance rate of approximately 40–70% (Pillai et al. 2012).”
The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions (2019, background): “Even for p moderately large, the ⇥(p2 + dim(⌧)) number of parameters might require many MCMC iterations to properly explore such a large space (Beskos et al., 2013; MacKay, 1998; Pillai et al., 2012); see also Fig.”
MCMC Methods for Functions: ModifyingOld Algorithms to Make Them Faster (2012, background): “1) which are central to this paper; see [37, 44].”
Log-concave sampling: Metropolis-Hastings algorithms are fast! (2018, background): “1 Metropolized random walk Roberts and Tweedie (1996b) established sufficient conditions on the proposal function p and the target distribution Π for the geometric convergence of several random walk MetropolisHastings algorithms.”
Stochastic Gradient Markov Chain Monte Carlo (2019, background): “Under mild regularity conditions (Roberts and Tweedie, 1996; Pillai et al. , 2012), the Langevin diffusion, deﬁned by the stochastic differential equation where ∇ U ( θ ( t )) is the drift term and B t denotes d -dimensional Brownian motion, has π as its stationary distribution.”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, methodology): “2.4), combinations with proximal operators (Pereyra 2015; Schreck et al. 2013), and applications and algorithm development for the inﬁnite-dimensional context (Pillai et al. 2012; Cotter et al. 2013).”
The Bayesian Approach to Inverse Problems (2013, background): “Related SPDE limit theorems may be found in [MPS11], and [PST11b]; however these latter two papers concern algorithms which are not defined on Hilbert space, and only approach an SPDE through finite dimensional approximation, and with a “Courant-like” restriction on the time-step to achieve converge”
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,”
Theoretical guarantees for approximate sampling from smooth and log‐concave densities (2014, methodology): “…essentially on the Metropolis-adjusted version of the LMC algorithm, known as the Metropolis-adjusted Langevin algorithm, and its modifications (Roberts and Rosenthal, 1998; Stramer and Tweedie, 1999a,b; Jarner and Hansen, 2000; Roberts and Stramer, 2002; Pillai et al., 2012; Xifara et al., 2014).”