The Library

Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions

Tools

Pillai, Natesh S., Stuart, A. M. and Thiéry, Alexandre H. (2011) Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions. Working Paper. Coventry: University of Warwick. Centre for Research in Statistical Methodology. Working papers, Vol.2011 (No.8).

Preview

PDF
WRAP_Pillai_11-08w.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (831Kb)

Official URL: http://www2.warwick.ac.uk/fac/sci/statistics/crism...

Abstract

The Metropolis-adjusted Langevin (MALA) algorithm is a sampling algorithm which
makes local moves by incorporating information about the gradient 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 at 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 O(N1/3) steps to explore the invariant measure. As a by-product
of the diffusion limit it also follows that the MALA algorithm is optimized at an average acceptance
probability of 0.574. Until now such results were proved only for targets which are products of one
dimensional distributions, or for variants of this situation. Our result is the first derivation of scaling
limits for the MALA algorithm to target measures which are not of the product form. As a consequence the rescaled MALA algorithm converges weakly to an infinite dimensional Hilbert space valued
diffusion, and not to a scalar diffusion. The diffusion limit is proved by showing that a drift-martingale
decomposition of the Markov chain, suitably scaled, closely resembles an Euler-Maruyama discretization of the putative limit. An invariance principle is proved for the Martingale and a continuous
mapping argument is used to complete the proof.

Item Type:

Working or Discussion Paper (Working Paper)

Subjects:

Q Science > QA Mathematics

Divisions:

Faculty of Science > Mathematics
Faculty of Science > Statistics

Library of Congress Subject Headings (LCSH):

Langevin equations, Hilbert space, Diffusion processes

Series Name:

Working papers

Publisher:

University of Warwick. Centre for Research in Statistical Methodology

Place of Publication:

Coventry

Official Date:

2011

Dates:

Date	Event
2011	Published

Volume:

Vol.2011

Number:

No.8

Number of Pages:

Status:

Not Peer Reviewed

Access rights to Published version:

Open Access

Funder:

Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Research in Statistical Methodology, European Research Council (ERC)

References:

[Bed07] M. Bedard. Weak convergence of Metropolis algorithms for non-i.i.d. target distributions. Ann.
Appl. Probab., 17(4):1222{1244, 2007.
[Bed09] M. Bedard. On the optimal scaling problem of metropolis algorithms for hierarchical target
distributions. 2009. preprint.
[Ber86] E. Berger. Asymptotic behaviour of a class of stochastic approximation procedures. Probab.
Theory Relat. Fields, 71(4):517{552, 1986.
[BPR+11] A. Beskos, N. Pillai, G.O. Roberts, J.-M. Sanz-Serna, and A.M. Stuart. Optimal tuning of hybrid
monte-carlo. Submitted, 2011.
[BPS04] Laird Arnault Breyer, Mauro Piccioni, and Sergio Scarlatti. Optimal scaling of MaLa for non-
linear regression. Ann. Appl. Probab., 14(3):1479{1505, 2004.
[BPSSA] A. Beskos, F. Pinski, J.M. Sanz-Serna, and A.M.Stuart. Hybrid Monte-Carlo on hilbert spaces.
Stoch. Proc. Applics.
[BR00] L. A. Breyer and G. O. Roberts. From Metropolis to diffusions: Gibbs states and optimal scaling.
Stochastic Process. Appl., 90(2):181{206, 2000.
[BRS09] A. Beskos, G.O. Roberts, and A.M. Stuart. Optimal scalings for local Metropolis-Hastings chains
on non-product targets in high dimensions. Ann. Appl. Probab., 19(3):863{898, 2009.
[BRSV08] A. Beskos, G.O. Roberts, A.M. Stuart, and J. Voss. An MCMC method for diffusion bridges.
Stochastics and Dynamics, 8(3):319{350, 2008.
[BS09] A. Beskos and A.M. Stuart. MCMC methods for sampling function space. In Invited Lectures,
Sixth International Congress on Industrial and Applied Mathematics, ICIAM07, Editors Rolf
Jeltsch and Gerhard Wanner, pages 337{364. European Mathematical Society, 2009.
[CRR05] O.F. Christensen, G.O. Roberts, and J.S. Rosenthal. Scaling limits for the transient phase of local
Metropolis{Hastings algorithms. Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 67(2):253{268, 2005.
[DPZ92] G. Da Prato and J. Zabczyk. Stochastic equations in infinite dimensions, volume 44 of Encyclo-
pedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1992.
[Dur96] Richard Durrett. Stochastic Calculus: A Practical Introduction. CRC Press; Subsequent edition
(21 Jun 1996), 1996.
[EK86] S. N. Ethier and T. G. Kurtz. Markov processes. Wiley Series in Probability and Mathematical
Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, 1986.
Characterization and convergence.
[HAVW05] M. Hairer, A.M.Stuart, J. Voss, and P. Wiberg. Analysis of SPDEs arising in path sampling.
Part i: the gaussian case. Comm. Math. Sci., 3:587{603, 2005.
[HSV07] M. Hairer, A. M. Stuart, and J. Voss. Analysis of SPDEs arising in path sampling. PartII: the
nonlinear case. Ann. Appl. Probab., 17(5-6):1657{1706, 2007.
[HSV10] M. Hairer, A. M. Stuart, and J. Voss. Signal processing problems on function space: Bayesian
formulation, stochastic pdes and effective mcmc methods. The Oxford Handbook of Nonlinear
Filtering, Editors D. Crisan and B. Rozovsky, 2010. To Appear.
[MPS09] J.C. Mattingly, N.S. Pillai, and A.M. Stuart. SPDE Limits of the Random Walk Metropolis
Algorithm in High Dimensions. 2009.
[MRTT53] N. Metropolis, A.W. Rosenbluth, M.N. Teller, and E. Teller. Equations of state calculations by
fast computing machines. J. Chem. Phys., 21:1087{1092, 1953.
[RC04] C. P. Robert and G. Casella. Monte Carlo statistical methods. Springer Texts in Statistics.
Springer-Verlag, New York, second edition, 2004.
[RGG97] G. O. Roberts, A. Gelman, and W. R. Gilks. Weak convergence and optimal scaling of random
walk Metropolis algorithms. Ann. Appl. Probab., 7(1):110{120, 1997.
[RR98] G. O. Roberts and J. S. Rosenthal. Optimal scaling of discrete approximations to Langevin
diffusions. J. R. Stat. Soc. Ser. B Stat. Methodol., 60(1):255{268, 1998.
[RR01] G. O. Roberts and J. S. Rosenthal. Optimal scaling for various Metropolis-Hastings algorithms.
Statist. Sci., 16(4):351{367, 2001.
[SFR10] Chris Sherlock, Paul Fearnhead, and Gareth O. Roberts. The random walk metropolis : linking
theory and practice through a case study. Statistical Science, 25(2):172{190, 2010.
[Stu10] A.M. Stuart. Inverse problems: a Bayesian perspective. Acta Numerica, To appear, 2010.