×

Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions. (English) Zbl 1307.65002

It is well known that the most widely used method for general target measures are Markov chain Monte Carlo (MCMC) algorithms. The main aim of this article is to study the complexity of certain sampling algorithms in high dimensions, more precisely, the Metropolis-Hastings algorithm in infinite dimensions. The computational cost of such an algorithm is the number of necessary steps \(\times\) cost of a step.
While for most algorithms the cost of one step grows with the dimension, a major result of this paper is an lgorithm which, when applied to measures, defines via a finite-dimensional approximation of a measure defined by a density with respect to a Gaussian random field, requires a number of steps independent of the dimension in order to achieve a given level of accuracy.
The authors consider Metropolis-Hastings MCMC methods and focus on cases when the proposal is either a Gaussian random walk (RWM) for which the covariance equals to that of a reference measure or an Orstain-Uhlenbeck proposal (pCN) for which the reference measure is invariant. Among the main results belong:
\(\bullet\)
Description of \(RWM\) and \(pCN\) algorithms and study of their properties, both positive and negative ones.
\(\bullet\)
Statement of the weak Harris theorem and a discussion of the relationship between exponential convergence in a Wasserstein distance and \(L^{2}_{\mu}\)-spectral gaps.
\(\bullet\)
Formal confirmation of a conjecture that \(pCN\) has a convergence rate that is independent of the dimension while \(RWM\) has undesirable dimension dependent properties.
The results are presented for separable Hilbert spaces, but in fact they do also hold on an arbitrary Banach space.

MSC:

65C05 Monte Carlo methods
65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
60G50 Sums of independent random variables; random walks
60G60 Random fields
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Adler, R. J. (1990). An Introduction to Continuity , Extrema , and Related Topics for General Gaussian Processes. Institute of Mathematical Statistics Lecture Notes-Monograph Series 12 . IMS, Hayward, CA. · Zbl 0747.60039
[2] Athreya, K. B. and Ney, P. (1978). A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245 493-501. · Zbl 0397.60053 · doi:10.2307/1998882
[3] Bakry, D. and Émery, M. (1985). Diffusions hypercontractives. In Séminaire de Probabilités , XIX , 1983 / 84. Lecture Notes in Math. 1123 177-206. Springer, Berlin. · Zbl 0561.60080 · doi:10.1007/BFb0075847
[4] Beskos, A., Kalogeropoulos, K. and Pazos, E. (2013). Advanced MCMC methods for sampling on diffusion pathspace. Stochastic Process. Appl. 123 1415-1453. · Zbl 1276.60078 · doi:10.1016/j.spa.2012.12.001
[5] 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. · Zbl 1172.60328 · doi:10.1214/08-AAP563
[6] Beskos, A., Roberts, G., Stuart, A. and Voss, J. (2008). MCMC methods for diffusion bridges. Stoch. Dyn. 8 319-350. · Zbl 1159.65007 · doi:10.1142/S0219493708002378
[7] Beskos, A., Pinski, F., Sanz-Serna, J. M. and Stuart, A. M. (2011). Hybrid Monte-Carlo on Hilbert spaces. Stochastic Process. Appl. 121 2201-2230. · Zbl 1235.60091 · doi:10.1016/j.spa.2011.06.003
[8] Bogachev, V. I. (1998). Gaussian Measures. Mathematical Surveys and Monographs 62 . Amer. Math. Soc., Providence, RI. · Zbl 0938.28010
[9] Bogachev, V. I. (2007). Measure Theory. Vol. I , II . Springer, Berlin. · Zbl 1120.28001
[10] Chan, K. S. and Geyer, C. J. (1994). Discussion: Markov chains for exploring posterior distributions. Ann. Statist. 22 1747-1758. · Zbl 0829.62080 · doi:10.1214/aos/1176325750
[11] Cheeger, J. (1970). A lower bound for the smallest eigenvalue of the Laplacian. In Problems in Analysis ( Papers Dedicated to Salomon Bochner , 1969) 195-199. Princeton Univ. Press, Princeton, NJ. · Zbl 0212.44903
[12] Cotter, S. L., Roberts, G. O., Stuart, A. M. and White, D. (2013). MCMC methods for functions: Modifying old algorithms to make them faster. Statist. Sci. 28 424-446. · Zbl 1331.62132 · doi:10.1214/13-STS421
[13] Cuny, C. and Lin, M. (2009). Pointwise ergodic theorems with rate and application to the CLT for Markov chains. Ann. Inst. Henri Poincaré Probab. Stat. 45 710-733. · Zbl 1186.37013 · doi:10.1214/08-AIHP180
[14] Dashti, M., Harris, S. and Stuart, A. (2012). Besov priors for Bayesian inverse problems. Inverse Probl. Imaging 6 183-200. · Zbl 1243.62032 · doi:10.3934/ipi.2012.6.183
[15] Dashti, M. and Stuart, A. M. (2011). Uncertainty quantification and weak approximation of an elliptic inverse problem. SIAM J. Numer. Anal. 49 2524-2542. · Zbl 1234.35309 · doi:10.1137/100814664
[16] Da Prato, G. and Zabczyk, J. (1992). Stochastic Equations in Infinite Dimensions. Encyclopedia of Mathematics and Its Applications 44 . Cambridge Univ. Press, Cambridge. · Zbl 0761.60052 · doi:10.1017/CBO9780511666223
[17] Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36-61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[18] Eberle, A. (2014). Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions. Ann. Appl. Probab. 24 337-377. · Zbl 1296.60195 · doi:10.1214/13-AAP926
[19] Frigessi, A., di Stefano, P., Hwang, C.-R. and Sheu, S. J. (1993). Convergence rates of the Gibbs sampler, the Metropolis algorithm and other single-site updating dynamics. J. Roy. Statist. Soc. Ser. B 55 205-219. · Zbl 0781.60039
[20] Geyer, C. J. (1992). Practical Markov chain Monte Carlo. Statist. Sci. 7 473-483.
[21] Geyer, C. J. and Thompson, E. A. (1995). Annealing Markov chain Monte Carlo with applications to ancestral inference. J. Amer. Statist. Assoc. 90 909-920. · Zbl 0850.62834 · doi:10.2307/2291325
[22] Hairer, M. (2010). An introduction to stochastic PDEs. Lecture notes, University of Warwick.
[23] Hairer, M. and Majda, A. J. (2010). A simple framework to justify linear response theory. Nonlinearity 23 909-922. · Zbl 1186.82006 · doi:10.1088/0951-7715/23/4/008
[24] Hairer, M., Mattingly, J. C. and Scheutzow, M. (2011). Asymptotic coupling and a general form of Harris’ Theorem with applications to stochastic delay equations. Probab. Theory Related Fields 149 223-259. · Zbl 1238.60082 · doi:10.1007/s00440-009-0250-6
[25] 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. · Zbl 1140.60329 · doi:10.1214/07-AAP441
[26] Hastings, W. K. (1970). Monte-Carlo sampling methods using Markov chains and their applications. Biometrika 57 97. · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97
[27] Hjort, N. L., Holmes, C., Müller, P. and Walker, S. G., eds. (2010). Bayesian Nonparametrics. Cambridge Series in Statistical and Probabilistic Mathematics 28 . Cambridge Univ. Press, Cambridge. · Zbl 1192.62080
[28] Joulin, A. and Ollivier, Y. (2010). Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 2418-2442. · Zbl 1207.65006 · doi:10.1214/10-AOP541
[29] Kipnis, C. and Varadhan, S. R. S. (1986). Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions. Comm. Math. Phys. 104 1-19. · Zbl 0588.60058 · doi:10.1007/BF01210789
[30] Komorowski, T. and Walczuk, A. (2012). Central limit theorem for Markov processes with spectral gap in the Wasserstein metric. Stochastic Process. Appl. 122 2155-2184. · Zbl 1244.60024 · doi:10.1016/j.spa.2012.03.006
[31] Lassas, M., Saksman, E. and Siltanen, S. (2009). Discretization-invariant Bayesian inversion and Besov space priors. Inverse Probl. Imaging 3 87-122. · Zbl 1191.62046 · doi:10.3934/ipi.2009.3.87
[32] Łatuszyński, K. and Niemiro, W. (2011). Rigorous confidence bounds for MCMC under a geometric drift condition. J. Complexity 27 23-38. · Zbl 1210.65004 · doi:10.1016/j.jco.2010.07.003
[33] Łatuszyński, K. and Roberts, G. O. (2013). CLTs and asymptotic variance of time-sampled Markov chains. Methodol. Comput. Appl. Probab. 15 237-247. · Zbl 1262.60068 · doi:10.1007/s11009-011-9237-8
[34] Lawler, G. F. and Sokal, A. D. (1988). Bounds on the \(L^{2}\) spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality. Trans. Amer. Math. Soc. 309 557-580. · Zbl 0716.60073 · doi:10.2307/2000925
[35] Lee, P. M. (2004). Bayesian Statistics : An Introduction , 3rd ed. Arnold, London. · Zbl 1056.62035
[36] Liu, J. S. (2008). Monte Carlo Strategies in Scientific Computing . Springer, New York. · Zbl 1132.65003
[37] Lovász, L. and Simonovits, M. (1993). Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms 4 359-412. · Zbl 0788.60087 · doi:10.1002/rsa.3240040402
[38] Mattingly, J. C., Pillai, N. S. and Stuart, A. M. (2012). Diffusion limits of the random walk Metropolis algorithm in high dimensions. Ann. Appl. Probab. 22 881-930. · Zbl 1254.60081 · doi:10.1214/10-AAP754
[39] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., Teller, E. et al. (1953). Equation of state calculations by fast computing machines. J. Chem. Phys. 21 1087.
[40] Meyn, S. and Tweedie, R. L. (2009). Markov Chains and Stochastic Stability , 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 0925.60001
[41] Nummelin, E. (1978). A splitting technique for Harris recurrent Markov chains. Probab. Theory Related Fields 43 309-318. · Zbl 0364.60104 · doi:10.1007/BF00534764
[42] Pillai, N. S., Stuart, A. M. and Thiéry, A. H. (2011). Optimal proposal design for random walk type Metropolis algorithms with Gaussian random field priors. ArXiv E-prints.
[43] Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods , 2nd ed. Springer, New York. · Zbl 1096.62003
[44] Roberts, G. O. and Tweedie, R. L. (1996). Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83 95-110. · Zbl 0888.60064 · doi:10.1093/biomet/83.1.95
[45] Röckner, M. and Wang, F.-Y. (2001). Weak Poincaré inequalities and \(L^{2}\)-convergence rates of Markov semigroups. J. Funct. Anal. 185 564-603. · Zbl 1009.47028 · doi:10.1006/jfan.2001.3776
[46] Rudolf, D. (2012). Explicit error bounds for Markov chain Monte Carlo. Dissertationes Math. ( Rozprawy Mat. ) 485 1-93. · Zbl 1273.60090 · doi:10.4064/dm485-0-1
[47] Schwab, C. and Stuart, A. M. (2012). Sparse deterministic approximation of Bayesian inverse problems. Inverse Problems 28 045003, 32. · Zbl 1236.62014 · doi:10.1088/0266-5611/28/4/045003
[48] Sinclair, A. and Jerrum, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput. 82 93-133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9
[49] Stuart, A. M. (2010). Inverse problems: A Bayesian perspective. Acta Numer. 19 451-559. · Zbl 1242.65142 · doi:10.1017/S0962492910000061
[50] Tierney, L. (1998). A note on Metropolis-Hastings kernels for general state spaces. Ann. Appl. Probab. 8 1-9. · Zbl 0935.60053 · doi:10.1214/aoap/1027961031
[51] Vollmer, S. J. (2013). Dimension-independent MCMC sampling for inverse problems with non-Gaussian priors. Available at . 1302.2213
[52] Wang, F.-Y. (2003). Functional inequalities for the decay of sub-Markov semigroups. Potential Anal. 18 1-23. · Zbl 1022.47029 · doi:10.1023/A:1020535718522
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.