Convergence rate and concentration inequalities for Gibbs sampling in high dimension. (English) Zbl 1385.60042
Summary: The objective of this paper is to study the Gibbs sampling for computing the mean of observable in very high dimension – a powerful Markov chain Monte Carlo method. Under the R. L. Dobrushin’s uniqueness condition [Teor. Veroyatn. Primen. 13, 201–229 (1968; Zbl 0177.45202); Theory Probab. Appl. 15, 458–486 (1970; Zbl 0264.60037); translation from Teor. Veroyatn. Primen. 15, 469–497 (1970)], we establish some explicit and sharp estimate of the exponential convergence rate and prove some Gaussian concentration inequalities for the empirical mean.
MSC:
| 60E15 | Inequalities; stochastic orderings |
| 60J22 | Computational methods in Markov chains |
| 65C05 | Monte Carlo methods |
Keywords:
concentration inequality; coupling method; Dobrushin’s uniqueness condition; Gibbs measure; Markov chain Monte CarloReferences:
| [1] | Bobkov, S.G. and Götze, F. (1999). Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 1-28. · Zbl 0924.46027 · doi:10.1006/jfan.1998.3326 |
| [2] | Diaconis, P., Khare, K. and Saloff-Coste, L. (2008). Gibbs sampling, exponential families and orthogonal polynomials. Statist. Sci. 23 151-178. · Zbl 1327.62058 · doi:10.1214/07-STS252 |
| [3] | Diaconis, P., Khare, K. and Saloff-Coste, L. (2010). Gibbs sampling, conjugate priors and coupling. Sankhya A 72 136-169. · Zbl 1209.60042 · doi:10.1007/s13171-010-0004-7 |
| [4] | Djellout, H., Guillin, A. and Wu, L. (2004). Transportation cost-information inequalities and applications to random dynamical systems and diffusions. Ann. Probab. 32 2702-2732. · Zbl 1061.60011 · doi:10.1214/009117904000000531 |
| [5] | Dobrushin, R.L. (1968). The description of a random field by means of conditional probabilities and condition of its regularity. Theory Probab. Appl. 13 197-224. · Zbl 0184.40403 |
| [6] | Dobrushin, R.L. (1970). Prescribing a system of random variables by conditional distributions. Theory Probab. Appl. 15 458-486. · Zbl 0264.60037 |
| [7] | Dobrushin, R.L. and Shlosman, S.B. (1985). Completely analytical Gibbs fields. In Statistical Physics and Dynamical Systems ( Köszeg , 1984). Progress in Probability 10 371-403. Boston, MA: Birkhäuser. · Zbl 0569.46043 |
| [8] | Doucet, A., de Freitas, N. and Gordon, N. (2001). Sequential Monte Carlo Methods in Practice. Statistics for Engineering and Information Science . New York: Springer. · Zbl 0967.00022 |
| [9] | Gozlan, N. and Léonard, C. (2007). A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields 139 235-283. · Zbl 1126.60022 · doi:10.1007/s00440-006-0045-y |
| [10] | Gozlan, N. and Léonard, C. (2010). Transport inequalities. A survey. Markov Process. Related Fields 16 635-736. · Zbl 1229.26029 |
| [11] | Hairer, M. and Mattingly, J.C. (2011). Yet another look at Harris’ ergodic theorem for Markov chains. In Seminar on Stochastic Analysis , Random Fields and Applications VI. Progress in Probability 63 109-117. Basel: Birkhäuser. · Zbl 1248.60082 · doi:10.1007/978-3-0348-0021-1_7 |
| [12] | 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 |
| [13] | Ledoux, M. (1999). Concentration of measure and logarithmic Sobolev inequalities. In Séminaire de Probabilités , XXXIII. Lecture Notes in Math. 1709 120-216. Berlin: Springer. · Zbl 0957.60016 |
| [14] | Ledoux, M. (2001). The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89 . Providence, RI: Amer. Math. Soc. · Zbl 0995.60002 |
| [15] | Martinelli, F. (1999). Lectures on Glauber dynamics for discrete spin models. In Lectures on Probability Theory and Statistics ( Saint-Flour , 1997). Lecture Notes in Math. 1717 93-191. Berlin: Springer. · Zbl 1051.82514 · doi:10.1007/978-3-540-48115-7_2 |
| [16] | Martinelli, F. and Olivieri, E. (1994). Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys. 161 447-486. · Zbl 0793.60110 · doi:10.1007/BF02101929 |
| [17] | Marton, K. (1996). Bounding \(\overline{d}\)-distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24 857-866. · Zbl 0865.60017 · doi:10.1214/aop/1039639365 |
| [18] | Marton, K. (1996). A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 556-571. · Zbl 0856.60072 · doi:10.1007/BF02249263 |
| [19] | Marton, K. (2003). Measure concentration and strong mixing. Studia Sci. Math. Hungar. 40 95-113. · Zbl 1027.60011 · doi:10.1556/SScMath.40.2003.1-2.8 |
| [20] | Marton, K. (2004). Measure concentration for Euclidean distance in the case of dependent random variables. Ann. Probab. 32 2526-2544. · Zbl 1071.60012 · doi:10.1214/009117904000000702 |
| [21] | Meyn, S.P. and Tweedie, R.L. (1993). Markov Chains and Stochastic Stability. Communications and Control Engineering Series . London: Springer. · Zbl 0925.60001 |
| [22] | Paulin, D. (2012). Concentration inequalities for Markov chains by Marton coupling. |
| [23] | Rio, E. (2000). Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes. C. R. Acad. Sci. Paris Sér. I Math. 330 905-908. · Zbl 0961.60032 · doi:10.1016/S0764-4442(00)00290-1 |
| [24] | Roberts, G.O. and Rosenthal, J.S. (2004). General state space Markov chains and MCMC algorithms. Probab. Surv. 1 20-71. · Zbl 1189.60131 · doi:10.1214/154957804100000024 |
| [25] | Rosenthal, J.S. (1995). Minorization conditions and convergence rates for Markov chain Monte Carlo. J. Amer. Statist. Assoc. 90 558-566. · Zbl 0824.60077 · doi:10.2307/2291067 |
| [26] | Rosenthal, J.S. (1996). Analysis of the Gibbs sampler for a model related to James-Stein estimations. Statist. Comput. 6 269-275. |
| [27] | Rosenthal, J.S. (2002). Quantitative convergence rates of Markov chains: A simple account. Electron. Commun. Probab. 7 123-128 (electronic). · Zbl 1013.60053 · doi:10.1214/ECP.v7-1054 |
| [28] | Samson, P.M. (2000). Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes. Ann. Probab. 28 416-461. · Zbl 1044.60061 · doi:10.1214/aop/1019160125 |
| [29] | Talagrand, M. (1996). Transportation cost for Gaussian and other product measures. Geom. Funct. Anal. 6 587-600. · Zbl 0859.46030 · doi:10.1007/BF02249265 |
| [30] | Villani, C. (2003). Topics in Optimal Transportation. Graduate Studies in Mathematics 58 . Providence, RI: Amer. Math. Soc. · Zbl 1106.90001 |
| [31] | Winkler, G. (1995). Image Analysis , Random Fields and Dynamic Monte Carlo Methods : A Mathematical Introduction. Applications of Mathematics ( New York ) 27 . Berlin: Springer. · Zbl 0821.68125 |
| [32] | Wintenberger, O. (2012). Weak transport inequalities and applications to exponential inequalities and oracle inequalities. · Zbl 1328.60057 |
| [33] | Wu, L. (2006). Poincaré and transportation inequalities for Gibbs measures under the Dobrushin uniqueness condition. Ann. Probab. 34 1960-1989. · Zbl 1111.60079 · doi:10.1214/009117906000000368 |
| [34] | Zegarliński, B. (1992). Dobrushin uniqueness theorem and logarithmic Sobolev inequalities. J. Funct. Anal. 105 77-111. · Zbl 0761.46020 · doi:10.1016/0022-1236(92)90073-R |
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.
