On the mean speed of convergence of empirical and occupation measures in Wasserstein distance

Emmanuel Boissard; Thibaut Le Gouic

Annales de l'I.H.P. Probabilités et statistiques (2014)

  • Volume: 50, Issue: 2, page 539-563
  • ISSN: 0246-0203

Abstract

top
In this work, we provide non-asymptotic bounds for the average speed of convergence of the empirical measure in the law of large numbers, in Wasserstein distance. We also consider occupation measures of ergodic Markov chains. One motivation is the approximation of a probability measure by finitely supported measures (the quantization problem). It is found that rates for empirical or occupation measures match or are close to previously known optimal quantization rates in several cases. This is notably highlighted in the example of infinite-dimensional Gaussian measures.

How to cite

top

Boissard, Emmanuel, and Le Gouic, Thibaut. "On the mean speed of convergence of empirical and occupation measures in Wasserstein distance." Annales de l'I.H.P. Probabilités et statistiques 50.2 (2014): 539-563. <http://eudml.org/doc/271944>.

@article{Boissard2014,
abstract = {In this work, we provide non-asymptotic bounds for the average speed of convergence of the empirical measure in the law of large numbers, in Wasserstein distance. We also consider occupation measures of ergodic Markov chains. One motivation is the approximation of a probability measure by finitely supported measures (the quantization problem). It is found that rates for empirical or occupation measures match or are close to previously known optimal quantization rates in several cases. This is notably highlighted in the example of infinite-dimensional Gaussian measures.},
author = {Boissard, Emmanuel, Le Gouic, Thibaut},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {Wasserstein metrics; optimal transportation; functional quantization; transportation inequalities; Markov chains; measure theory},
language = {eng},
number = {2},
pages = {539-563},
publisher = {Gauthier-Villars},
title = {On the mean speed of convergence of empirical and occupation measures in Wasserstein distance},
url = {http://eudml.org/doc/271944},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Boissard, Emmanuel
AU - Le Gouic, Thibaut
TI - On the mean speed of convergence of empirical and occupation measures in Wasserstein distance
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2014
PB - Gauthier-Villars
VL - 50
IS - 2
SP - 539
EP - 563
AB - In this work, we provide non-asymptotic bounds for the average speed of convergence of the empirical measure in the law of large numbers, in Wasserstein distance. We also consider occupation measures of ergodic Markov chains. One motivation is the approximation of a probability measure by finitely supported measures (the quantization problem). It is found that rates for empirical or occupation measures match or are close to previously known optimal quantization rates in several cases. This is notably highlighted in the example of infinite-dimensional Gaussian measures.
LA - eng
KW - Wasserstein metrics; optimal transportation; functional quantization; transportation inequalities; Markov chains; measure theory
UR - http://eudml.org/doc/271944
ER -

References

top
  1. [1] M. Ajtai, J. Komlos and G. Tusnády. On optimal matchings. Combinatorica4 (1984) 259–264. Zbl0562.60012MR779885
  2. [2] F. Barthe and C. Bordenave. Combinatorial optimization over two random point sets. Preprint, 2011. Available at arXiv:1103.2734v1. Zbl06234286MR3185927
  3. [3] S. G. Bobkov, I. Gentil and M. Ledoux. Hypercontractivity of Hamilton-Jacobi equations. J. Math. Pures Appl.80 (2001) 669–696. Zbl1038.35020MR1846020
  4. [4] E. Boissard. Simple bounds for the convergence of empirical and occupation measures in 1-Wasserstein distance. Electron J. Probab16 (2011) 2296–2333. Zbl1254.60014MR2861675
  5. [5] F. Bolley, A. Guillin and C. Villani. Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Related Fields137 (2007) 541–593. Zbl1113.60093MR2280433
  6. [6] F. Bolley and C. Villani. Weighted Csiszár–Kullback–Pinsker inequalities and applications to transportation inequalities. Ann. Fac. Sci. Toulouse Math.14 (2005) 331–351. Zbl1087.60008MR2172583
  7. [7] P. Cattiaux, D. Chafai and A. Guillin. Central limit theorems for additive functionals of ergodic Markov diffusion processes. Preprint, 2011. Available at arXiv:1104.2198. Zbl1277.60047MR3069369
  8. [8] E. Del Barrio, E. Giné and C. Matrán. Central limit theorems for the Wasserstein distance between the empirical and the true distributions. Ann. Probab.27 (1999) 1009–1071. Zbl0958.60012MR1698999
  9. [9] S. Dereich, F. Fehringer, A. Matoussi and M. Scheutzow. On the link between small ball probabilities and the quantization problem for Gaussian measures on Banach spaces. J. Theoret. Probab.16 (2003) 249–265. Zbl1017.60012MR1956830
  10. [10] H. Djellout, A. Guillin and L. Wu. Transportation cost-information inequalities for random dynamical systems and diffusions. Ann. Probab.32 (2004) 2702–2732. Zbl1061.60011MR2078555
  11. [11] V. Dobric and J. E. Yukich. Exact asymptotics for transportation cost in high dimensions. J. Theoret. Probab.8 (1995) 97–118. Zbl0811.60022MR1308672
  12. [12] R. M. Dudley. The speed of mean Glivenko–Cantelli convergence. Ann. Math. Statist.40 (1969) 40–50. Zbl0184.41401MR236977
  13. [13] F. Fehringer. Kodierung von Gaußmaßen. Ph.D. manuscript, 2001, available at http://d-nb.info/962880116. 
  14. [14] N. Gozlan and C. Léonard. A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields139 (2007) 235–283. Zbl1126.60022MR2322697
  15. [15] N. Gozlan and C. Léonard. Transport inequalities. A survey. Markov Process. Related Fields 16 (2010) 635–736. Zbl1229.26029MR2895086
  16. [16] S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730. Springer, Berlin, 2000. Zbl0951.60003MR1764176
  17. [17] S. Graf and H. Luschgy. Rates of convergence for the empirical quantization error. Ann. Probab.30 (2002) 874–897. Zbl1018.60032MR1905859
  18. [18] S. Graf, H. Luschgy and G. Pagès. Functional quantization and small ball probabilities for Gaussian processes. J. Theoret. Probab.16 (2003) 1047–1062. Zbl1038.60032MR2033197
  19. [19] J. Horowitz and R. L. Karandikar. Mean rates of convergence of empirical measures in the Wasserstein metric. J. Comput. Appl. Math.55 (1994) 261–273. Zbl0819.60031MR1329874
  20. [20] A. Joulin and Y. Ollivier. Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab.38 (2010) 2418–2442. Zbl1207.65006MR2683634
  21. [21] J. Kuelbs and W. V. Li. Metric entropy and the small ball problem for Gaussian measures. J. Funct. Anal.116 (1993) 133–157. Zbl0799.46053MR1237989
  22. [22] M. Ledoux. Isoperimetry and Gaussian analysis. In Lectures on Probability Theory and Statistics (Saint-Flour, 1994) 165–294. Lecture Notes in Math. 1648. Springer, Berlin, 1996. Zbl0874.60005MR1600888
  23. [23] M. Ledoux. The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89. Am. Math. Soc., Providence, RI, 2001. Zbl0995.60002MR1849347
  24. [24] M. Ledoux and M. Talagrand. Probability in Banach Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)] 23. Springer, Berlin, 1991. Zbl0748.60004MR1102015
  25. [25] W. V. Li and W. Linde. Approximation, metric entropy and small ball estimates for Gaussian measures. Ann. Probab.27 (1999) 1556–1578. Zbl0983.60026MR1733160
  26. [26] H. Luschgy and G. Pagès. Sharp asymptotics of the functional quantization problem for Gaussian processes. Ann. Probab.32 (2004) 1574–1599. Zbl1049.60029MR2060310
  27. [27] H. Luschgy and G. Pagès. Sharp asymptotics of the Kolmogorov entropy for Gaussian measures. J. Funct. Anal.212 (2004) 89–120. Zbl1060.60037MR2065239
  28. [28] K. Marton. Bounding -distance by informational divergence: A method to prove measure concentration. Ann. Probab.24 (1996) 857–866. Zbl0865.60017MR1404531
  29. [29] M. Talagrand. Matching random samples in many dimensions. Ann. Appl. Probab.2 (1992) 846–856. Zbl0761.60007MR1189420
  30. [30] A. W. Van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer, New York, 1996. Zbl0862.60002MR1385671
  31. [31] V. S. Varadarajan. On the convergence of sample probability distributions. Sankhyā19 (1958) 23–26. Zbl0082.34201MR94839
  32. [32] C. Villani. Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften 338. Springer, Berlin, 2009. Zbl1156.53003MR2459454

NotesEmbed ?

top

You must be logged in to post comments.