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) no. 2, pp. 539-563.

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.

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

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

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

[28] K. Marton. Bounding $\overline{d}$-distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24 (1996) 857-866. | MR | Zbl

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

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

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

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