On the mean speed of convergence of empirical and occupation measures in Wasserstein distance
Boissard, Emmanuel ; Le Gouic, Thibaut
Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014), p. 539-563 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Dans ce travail, on exhibe des bornes non asymptotiques pour la vitesse de convergence en moyenne de la mesure empirique dans la loi des grands nombres, en distance de Wasserstein. On considère également la mesure d'occupation d'une chaîne de Markov ergodique. L'une des motivations est l'approximation d'une mesure de probabilité par des mesures à support fini (le problème de la quantification). On détermine que les taux de convergence des mesures empiriques ou des mesures d'occupation correspondent dans plusieurs cas aux taux de quantification optimale déjà établis par ailleurs. Ce fait est notamment établi pour des mesures gaussiennes dans des espaces de dimension infinie.

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.

Publié le : 2014-01-01
DOI : https://doi.org/10.1214/12-AIHP517
Classification:  60B10,  65C50,  60J05 
@article{AIHPB_2014__50_2_539_0,
     author = {Boissard, Emmanuel and Le Gouic, Thibaut},
     title = {On the mean speed of convergence of empirical and occupation measures in Wasserstein distance},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {50},
     year = {2014},
     pages = {539-563},
     doi = {10.1214/12-AIHP517},
     mrnumber = {3189084},
     zbl = {1294.60005},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2014__50_2_539_0}
}

Boissard, Emmanuel; 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, Tome 50 (2014) pp. 539-563. doi : 10.1214/12-AIHP517. http://gdmltest.u-ga.fr/item/AIHPB_2014__50_2_539_0/

[1] M. Ajtai, J. Komlos and G. Tusnády. On optimal matchings. Combinatorica 4 (1984) 259-264. | MR 779885 | Zbl 0562.60012

[2] F. Barthe and C. Bordenave. Combinatorial optimization over two random point sets. Preprint, 2011. Available at arXiv:1103.2734v1. | MR 3185927 | Zbl pre06234286

[3] S. G. Bobkov, I. Gentil and M. Ledoux. Hypercontractivity of Hamilton-Jacobi equations. J. Math. Pures Appl. 80 (2001) 669-696. | MR 1846020 | Zbl 1038.35020

[4] E. Boissard. Simple bounds for the convergence of empirical and occupation measures in 1-Wasserstein distance. Electron J. Probab 16 (2011) 2296-2333. | MR 2861675 | Zbl 1254.60014

[5] F. Bolley, A. Guillin and C. Villani. Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Related Fields 137 (2007) 541-593. | MR 2280433 | Zbl 1113.60093

[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. | Numdam | MR 2172583 | Zbl 1087.60008

[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. | MR 3069369 | Zbl 1277.60047

[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. | MR 1698999 | Zbl 0958.60012

[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. | MR 1956830 | Zbl 1017.60012

[10] H. Djellout, A. Guillin and L. Wu. Transportation cost-information inequalities for random dynamical systems and diffusions. Ann. Probab. 32 (2004) 2702-2732. | MR 2078555 | Zbl 1061.60011

[11] V. Dobric and J. E. Yukich. Exact asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1995) 97-118. | MR 1308672 | Zbl 0811.60022

[12] R. M. Dudley. The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40 (1969) 40-50. | MR 236977 | Zbl 0184.41401

[13] F. Fehringer. Kodierung von Gaußmaßen. Ph.D. manuscript, 2001, available at http://d-nb.info/962880116.

[14] N. Gozlan and C. Léonard. A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields 139 (2007) 235-283. | MR 2322697 | Zbl 1126.60022

[15] N. Gozlan and C. Léonard. Transport inequalities. A survey. Markov Process. Related Fields 16 (2010) 635-736. | MR 2895086 | Zbl 1229.26029

[16] S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730. Springer, Berlin, 2000. | MR 1764176 | Zbl 0951.60003

[17] S. Graf and H. Luschgy. Rates of convergence for the empirical quantization error. Ann. Probab. 30 (2002) 874-897. | MR 1905859 | Zbl 1018.60032

[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. | MR 2033197 | Zbl 1038.60032

[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. | MR 1329874 | Zbl 0819.60031

[20] A. Joulin and Y. Ollivier. Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 (2010) 2418-2442. | MR 2683634 | Zbl 1207.65006

[21] J. Kuelbs and W. V. Li. Metric entropy and the small ball problem for Gaussian measures. J. Funct. Anal. 116 (1993) 133-157. | MR 1237989 | Zbl 0799.46053

[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. | MR 1600888 | Zbl 0874.60005

[23] M. Ledoux. The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89. Am. Math. Soc., Providence, RI, 2001. | MR 1849347 | Zbl 0995.60002

[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. | MR 1102015 | Zbl 0748.60004

[25] W. V. Li and W. Linde. Approximation, metric entropy and small ball estimates for Gaussian measures. Ann. Probab. 27 (1999) 1556-1578. | MR 1733160 | Zbl 0983.60026

[26] H. Luschgy and G. Pagès. Sharp asymptotics of the functional quantization problem for Gaussian processes. Ann. Probab. 32 (2004) 1574-1599. | MR 2060310 | Zbl 1049.60029

[27] H. Luschgy and G. Pagès. Sharp asymptotics of the Kolmogorov entropy for Gaussian measures. J. Funct. Anal. 212 (2004) 89-120. | MR 2065239 | Zbl 1060.60037

[28] K. Marton. Bounding d ¯-distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24 (1996) 857-866. | MR 1404531 | Zbl 0865.60017

[29] M. Talagrand. Matching random samples in many dimensions. Ann. Appl. Probab. 2 (1992) 846-856. | MR 1189420 | Zbl 0761.60007

[30] A. W. Van Der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer, New York, 1996. | MR 1385671 | Zbl 0862.60002

[31] V. S. Varadarajan. On the convergence of sample probability distributions. Sankhyā 19 (1958) 23-26. | MR 94839 | Zbl 0082.34201

[32] C. Villani. Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften 338. Springer, Berlin, 2009. | MR 2459454 | Zbl 1156.53003