Concentration inequalities for Gibbs sampling under $d_{l_{2}}$-metric

Neng-Yi Wang (Huazhong University of Science and Technology)

Abstract


The aim of this paper is to investigate the Gibbs sampling that's used for computing the mean of observables with respect to some function $f$ depending on a very small number of variables. For this type of observable, by using the $d_{l_{2}}$-metric one obtains the sharp concentration estimate for the empirical mean, which in particular yields the correct speed in the concentration for $f$ depending on a single observable.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-11

Publication Date: September 18, 2014

DOI: 10.1214/ECP.v19-3502

References

  • Bobkov, S. G.; Goetze, F. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 (1999), no. 1, 1--28. MR1682772
  • Cattiaux, Patrick; Guillin, Arnaud; Wu, Li-Ming. A note on Talagrand's transportation inequality and logarithmic Sobolev inequality. Probab. Theory Related Fields 148 (2010), no. 1-2, 285--304. MR2653230
  • Djellout, H.; Guillin, A.; Wu, L. Transportation cost-information inequalities and applications to random dynamical systems and diffusions. Ann. Probab. 32 (2004), no. 3B, 2702--2732. MR2078555
  • Dobrushin, R. L. Description of a random field by means of conditional probabilities and conditions for its regularity. (Russian) Teor. Verojatnost. i Primenen 13 1968 201--229. MR0231434
  • Dobrushin, R. L.: Prescribing a system of random variables by conditional distributions. ph Theory Probab. Appl., 15(3): 458-486, 1970.
  • Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark. Dobrushin conditions and systematic scan. Combin. Probab. Comput. 17 (2008), no. 6, 761--779. MR2463409
  • Gozlan, Nathael; Leonard, Christian. A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields 139 (2007), no. 1-2, 235--283. MR2322697
  • Gozlan, N.; Leonard, C. Transport inequalities. A survey. Markov Process. Related Fields 16 (2010), no. 4, 635--736. MR2895086
  • Ledoux, Michel. Concentration of measure and logarithmic Sobolev inequalities. Seminaire de Probabilites, XXXIII, 120--216, Lecture Notes in Math., 1709, Springer, Berlin, 1999. MR1767995
  • Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347
  • Marton, K. Bounding $\overline d$-distance by informational divergence: a method to prove measure concentration. Ann. Probab. 24 (1996), no. 2, 857--866. MR1404531
  • Marton, K. A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996), no. 3, 556--571. MR1392329
  • Marton, Katalin. Measure concentration for Euclidean distance in the case of dependent random variables. Ann. Probab. 32 (2004), no. 3B, 2526--2544. MR2078549
  • Otto, F.; Villani, C. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. J. Funct. Anal. 173 (2000), no. 2, 361--400. MR1760620
  • Talagrand, M. Transportation cost for Gaussian and other product measures. Geom. Funct. Anal. 6 (1996), no. 3, 587--600. MR1392331
  • Villani, C. Topics in optimal transportation. Graduate Studies in Mathematics, 58. American Mathematical Society, Providence, RI, 2003. xvi+370 pp. ISBN: 0-8218-3312-X MR1964483
  • Wang, N.-Y. and Wu, L.: Convergence rate and concentration inequalities for Gibbs sampling in high dimension. To appear in Bernoulli.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.