Mattingly, Jonathan C., Pillai, Natesh S., 1981- and Stuart, A. M.. (2012) Diffusion limits of the random walk Metropolis algorithm in high dimensions. The Annals of Applied Probability, Vol.22 (No.3). pp. 881-930. ISSN 1050-5164

Preview

Text WRAP_Stuart_euclid.aoap.1337347534.pdf - Published Version Download (616Kb) | Preview

Abstract

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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Diffusion processes, Monte Carlo method, Random walks (Mathematics), Hilbert space
Journal or Publication Title:	The Annals of Applied Probability
Publisher:	Institute of Mathematical Statistics
ISSN:	1050-5164
Date:	June 2012
Volume:	Vol.22
Number:	No.3
Number of Pages:	50
Page Range:	pp. 881-930
Identification Number:	10.1214/10-AAP754
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	National Science Foundation (U.S.) (NSF), Engineering and Physical Sciences Research Council (EPSRC), European Research Council (ERC)
Grant number:	DMS-04-49910 (NSF), DMS-08-54879 (NSF)
References:	[1] BÉDARD, M. (2007).Weak convergence of Metropolis algorithms for non-i.i.d. target distributions. Ann. Appl. Probab. 17 1222–1244. MR2344305 [2] BÉDARD, M. (2009). On the optimal scaling problem of Metropolis algorithms for hierarchical target distributions. Preprint. [3] BERGER, E. (1986). Asymptotic behaviour of a class of stochastic approximation procedures. Probab. Theory Related Fields 71 517–552. MR0833268 [4] BESKOS, A., ROBERTS, G. and STUART, A. (2009). Optimal scalings for local Metropolis– Hastings chains on nonproduct targets in high dimensions. Ann. Appl. Probab. 19 863– 898. MR2537193 [5] BESKOS, A., ROBERTS, G., STUART, A. and VOSS, J. (2008). MCMC methods for diffusion bridges. Stoch. Dyn. 8 319–350. MR2444507 [6] BESKOS, A. and STUART, A. M. (2008). MCMC methods for sampling function space. In ICIAM Invited Lecture 2007 (R. Jeltsch and G. Wanner, eds.). European Mathematical Society, Zürich. [7] BOU-RABEE, N. and VANDEN-EIJNDEN, E. (2010). Pathwise accuracy and ergodicity of Metropolized integrators for SDEs. Comm. Pure Appl. Math. 63 655–696. MR2583309 [8] BREYER, L. A., PICCIONI, M. and SCARLATTI, S. (2004). Optimal scaling of MALA for nonlinear regression. Ann. Appl. Probab. 14 1479–1505. MR2071431 [9] BREYER, L. A. and ROBERTS, G. O. (2000). From Metropolis to diffusions: Gibbs states and optimal scaling. Stochastic Process. Appl. 90 181–206. MR1794535 [10] CHATTERJEE, S. (2007). Stein’s method. Lecture notes. Available at http://www.stat.berkeley. edu/~sourav/stat206Afall07.html. [11] CHEN, X. and WHITE, H. (1998). Central limit and functional central limit theorems for Hilbert-valued dependent heterogeneous arrays with applications. Econometric Theory 14 260–284. MR1629340 [12] COTTER, S. L., DASHTI, M. and STUART, A. M. (2010). Approximation of Bayesian inverse problems. SIAM Journal of Numerical Analysis 48 322–345. [13] DA PRATO, G. and ZABCZYK, J. (1992). Stochastic Equations in Infinite Dimensions. Encyclopedia of Mathematics and Its Applications 44. Cambridge Univ. Press, Cambridge. MR1207136 [14] ETHIER, S. N. and KURTZ, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. MR0838085 [15] HAIRER, M., STUART, A. M. and VOSS, J. (2007). Analysis of SPDEs arising in path sampling. II. The nonlinear case. Ann. Appl. Probab. 17 1657–1706. MR2358638 [16] HAIRER, M., STUART, A. M. and VOSS, J. (2011). Signal processing problems on function space: Bayesian formulation, stochastic PDEs and effective MCMC methods. In The Oxford Handbook of Nonlinear Filtering (D. Crisan and B. Rozovsky, eds.). Oxford Univ. Press, Oxford. [17] HAIRER, M., STUART, A. M., VOSS, J. andWIBERG, P. (2005). Analysis of SPDEs arising in path sampling. I. The Gaussian case. Commun. Math. Sci. 3 587–603. MR2188686 [18] HASTINGS, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 97–109. [19] LIU, J. S. (2008). Monte Carlo Strategies in Scientific Computing. Springer, New York. MR2401592 [20] MA, Z. M. and RÖCKNER, M. (1992). Introduction to the Theory of (nonsymmetric) Dirichlet Forms. Springer, Berlin. MR1214375 [21] METROPOLIS, N., ROSENBLUTH, A.W., TELLER, M. N. and TELLER, E. (1953). Equations of state calculations by fast computing machines. J. Chem. Phys. 21 1087–1092. [22] ROBERT, C. P. and CASELLA, G. (2004). Monte Carlo Statistical Methods, 2nd ed. Springer, New York. MR2080278 [23] ROBERTS, G. O., GELMAN, A. and GILKS, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Probab. 7 110–120. MR1428751 [24] ROBERTS, G. O. and ROSENTHAL, J. S. (1998). Optimal scaling of discrete approximations to Langevin diffusions. J. R. Stat. Soc. Ser. B Stat. Methodol. 60 255–268. MR1625691 [25] ROBERTS, G. O. and ROSENTHAL, J. S. (2001). Optimal scaling for various Metropolis– Hastings algorithms. Statist. Sci. 16 351–367. MR1888450 [26] STROOCK, D. W. (1993). Probability Theory, an Analytic View. Cambridge Univ. Press, Cambridge. MR1267569 [27] STUART, A. M. (2010). Inverse problems: A Bayesian perspective. Acta Numer. 19 451–559. MR2652785
URI:	http://wrap.warwick.ac.uk/id/eprint/48174

Request changes to a record

Actions (login required)

View Item