Simple Bounds for the Convergence of Empirical and Occupation Measures in 1-Wasserstein Distance

Emmanuel Boissard (Université de Toulouse)

Abstract


We study the problem of non-asymptotic deviations between a reference measure and its empirical version, in the 1-Wasserstein metric, under the standing assumption that the reference measure satisfies a transport-entropy inequality. We extend some results of F. Bolley, A. Guillin and C. Villani with simple proofs. Our methods are based on concentration inequalities and extend to the general setting of measures on a Polish space. Deviation bounds for the occupation measure of a contracting Markov chain in 1-Wasserstein distance are also given. Throughout the text, several examples are worked out, including the cases of Gaussian measures on separable Banach spaces, and laws of diffusion processes.

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

Pages: 2296-2333

Publication Date: November 15, 2011

DOI: 10.1214/EJP.v16-958

References

  1. Ajtai, M.; KomlÛs, J.; Tusn·dy, G. On optimal matchings. Combinatorica 4 (1984), no. 4, 259--264. 0779885
  2. Baldi, P.; Ben Arous, G.; Kerkyacharian, G. Large deviations and the Strassen theorem in H?lder norm. Stochastic Process. Appl. 42 (1992), no. 1, 171--180. 1172514
  3. Barthe, F.; Bordenave, C. Combinatorial optimization over two random point sets. Arxiv preprint arXiv:1103.2734, 2011.
  4. Bobkov, S.; Ledoux, M. PoincarÈ's inequalities and Talagrand's concentration phenomenon for the exponential distribution. Probab. Theory Related Fields 107 (1997), no. 3, 383--400. 1440138
  5. Bobkov, S. G.; G?tze, F. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 (1999), no. 1, 1--28. 1682772
  6. Boissard, E.; Le Gouic, T. On the mean speed of convergence of empirical and occupation measures in Wasserstein distance. Arxiv preprint arXiv:1105.5263, 2011.
  7. Bolley, F. Quantitative concentration inequalities on sample path space for mean field interaction. ESAIM Probab. Stat. 14 (2010), 192--209. 2741965
  8. Bolley, F.; Guillin, A.; Villani, C. Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Related Fields 137 (2007), no. 3-4, 541--593. 2280433
  9. Bolley, F.; Villani, C. Weighted Csisz·r-Kullback-Pinsker inequalities and applications to transportation inequalities. Ann. Fac. Sci. Toulouse Math. (6) 14 (2005), no. 3, 331--352. 2172583
  10. del Barrio, E.; GinÈ, E.; Matr·n, C. Central limit theorems for the Wasserstein distance between the empirical and the true distributions. Ann. Probab. 27 (1999), no. 2, 1009--1071. 1698999
  11. Dembo, A.; Zeitouni, O. Large deviations techniques and applications. Jones and Bartlett Publishers, Boston, MA, 1993. 1202429
  12. Dereich, S.; Fehringer, F.; Matoussi, A.; Scheutzow, M. On the link between small ball probabilities and the quantization problem for Gaussian measures on Banach spaces. J. Theoret. Probab. 16 (2003), no. 1, 249--265. 1956830
  13. Dobric, V.; Yukich, J. E. Asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1995), no. 1, 97--118. 1308672
  14. Dudley, R. M. The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40 1968 40--50. 0236977
  15. Fehringer, F. Kodierung von Gaussmassen. Ph.D. thesis, 2001.
  16. Gozlan, N.; LÈonard, C. A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields 139 (2007), no. 1-2, 235--283. 2322697
  17. Gozlan, N.; LÈonard, C. Transport inequalities. A survey. Markov Processes and Related Fields 16 (2010) 635-736, 2010.
  18. Graf, S.; Luschgy, H.; PagËs, G. Functional quantization and small ball probabilities for Gaussian processes. J. Theoret. Probab. 16 (2003), no. 4, 1047--1062 (2004). 2033197
  19. 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. 2078555
  20. Joulin, A.; Ollivier, Y. Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 (2010), no. 6, 2418--2442.2683634
  21. Kuelbs, J.; Li, W. V. Metric entropy and the small ball problem for Gaussian measures. J. Funct. Anal. 116 (1993), no. 1, 133--157. 1237989
  22. Ledoux, M. Isoperimetry and Gaussian analysis. Lectures on probability theory and statistics (Saint-Flour, 1994) , 165--294, Lecture Notes in Math., 1648, Springer, Berlin, 1996. 1600888
  23. Ledoux, M. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. 1849347
  24. Li, W. V.; Linde, W. Approximation, metric entropy and small ball estimates for Gaussian measures. Ann. Probab. 27 (1999), no. 3, 1556--1578. 1733160
  25. Marton, K. Bounding bar-d-distance by informational divergence: a method to prove measure concentration. Ann. Probab. 24 (1996), no. 2, 857--866. 1404531
  26. Massart, P. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Probab. 18 (1990), no. 3, 1269--1283. 1062069
  27. Massart, P. Concentration inequalities and model selection. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, 2003. Lecture Notes in Mathematics, 1896. Springer, Berlin, 2007. 2319879
  28. Ollivier, Y. Ricci curvature of Markov chains on metric spaces. J. Funct. Anal. 256 (2009), no. 3, 810--864. 2484937
  29. Rao, M. M.; Ren, Z. D. Theory of Orlicz spaces. Monographs and Textbooks in Pure and Applied Mathematics, 146. Marcel Dekker, Inc., New York, 1991. 1113700
  30. Revuz, D.; Yor, M. Continuous martingales and Brownian motion. Third edition. Grundlehren der Mathematischen Wissenschaften, 293. Springer-Verlag, Berlin, 1999. 1725357
  31. Talagrand, M. Matching random samples in many dimensions. Ann. Appl. Probab. 2 (1992), no. 4, 846--856. 1189420
  32. van der Vaart, A. W.; Wellner, J. A. Weak convergence and empirical processes. With applications to statistics. Springer Series in Statistics. Springer-Verlag, New York, 1996. 1385671
  33. Varadarajan, V. S. On the convergence of sample probability distributions. Sankhya 19 1958 23--26. 0094839
  34. Villani, C. Optimal transport. Old and new. Grundlehren der Mathematischen Wissenschaften, 338. Springer-Verlag, Berlin, 2009. 2459454
  35. Wang, R.; Wang, X.; Wu, L. Sanov's theorem in the Wasserstein distance: a necessary and sufficient condition. Statist. Probab. Lett. 80 (2010), no. 5-6, 505--512. 2593592
Bookmark and Share


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