×

On the mean speed of convergence of empirical and occupation measures in Wasserstein distance. (English. French summary) Zbl 1294.60005

Authors’ abstract: We provide non-asymptotic bounds for the average speed of convergence in 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.

MSC:

60B10 Convergence of probability measures
65C50 Other computational problems in probability (MSC2010)
60J05 Discrete-time Markov processes on general state spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] M. Ajtai, J. Komlos and G. Tusnády. On optimal matchings. Combinatorica 4 (1984) 259-264. · Zbl 0562.60012 · doi:10.1007/BF02579135
[2] F. Barthe and C. Bordenave. Combinatorial optimization over two random point sets. Preprint, 2011. Available at . 1103.2734v1 · Zbl 1401.90180
[3] S. G. Bobkov, I. Gentil and M. Ledoux. Hypercontractivity of Hamilton-Jacobi equations. J. Math. Pures Appl. 80 (2001) 669-696. · Zbl 1038.35020 · doi:10.1016/S0021-7824(01)01208-9
[4] E. Boissard. Simple bounds for the convergence of empirical and occupation measures in 1-Wasserstein distance. Electron J. Probab 16 (2011) 2296-2333. · Zbl 1254.60014 · doi:10.1214/EJP.v16-958
[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. · Zbl 1113.60093 · doi:10.1007/s00440-006-0004-7
[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. · Zbl 1087.60008 · doi:10.5802/afst.1095
[7] P. Cattiaux, D. Chafai and A. Guillin. Central limit theorems for additive functionals of ergodic Markov diffusion processes. Preprint, 2011. Available at . 1104.2198
[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. · Zbl 0958.60012 · doi:10.1214/aop/1022677394
[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. · Zbl 1017.60012 · doi:10.1023/A:1022242924198
[10] H. Djellout, A. Guillin and L. Wu. Transportation cost-information inequalities for random dynamical systems and diffusions. Ann. Probab. 32 (2004) 2702-2732. · Zbl 1061.60011 · doi:10.1214/009117904000000531
[11] V. Dobric and J. E. Yukich. Exact asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1995) 97-118. · Zbl 0811.60022 · doi:10.1007/BF02213456
[12] R. M. Dudley. The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40 (1969) 40-50. · Zbl 0184.41401 · doi:10.1214/aoms/1177697802
[13] F. Fehringer. Kodierung von Gaußmaßen . Ph.D. manuscript, 2001, available at .
[14] N. Gozlan and C. Léonard. A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields 139 (2007) 235-283. · Zbl 1126.60022 · doi:10.1007/s00440-006-0045-y
[15] N. Gozlan and C. Léonard. Transport inequalities. A survey. Markov Process. Related Fields 16 (2010) 635-736. · Zbl 1229.26029
[16] S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730 . Springer, Berlin, 2000. · Zbl 0951.60003
[17] S. Graf and H. Luschgy. Rates of convergence for the empirical quantization error. Ann. Probab. 30 (2002) 874-897. · Zbl 1018.60032 · doi:10.1214/aop/1023481010
[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. · Zbl 1038.60032 · doi:10.1023/B:JOTP.0000012005.32667.9d
[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. · Zbl 0819.60031 · doi:10.1016/0377-0427(94)90033-7
[20] A. Joulin and Y. Ollivier. Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 (2010) 2418-2442. · Zbl 1207.65006 · doi:10.1214/10-AOP541
[21] J. Kuelbs and W. V. Li. Metric entropy and the small ball problem for Gaussian measures. J. Funct. Anal. 116 (1993) 133-157. · Zbl 0799.46053 · doi:10.1006/jfan.1993.1107
[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. · Zbl 0874.60005 · doi:10.1007/BFb0095676
[23] M. Ledoux. The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89 . Am. Math. Soc. , Providence, RI, 2001. · 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. · 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. · Zbl 0983.60026 · doi:10.1214/aop/1022677459
[26] H. Luschgy and G. Pagès. Sharp asymptotics of the functional quantization problem for Gaussian processes. Ann. Probab. 32 (2004) 1574-1599. · Zbl 1049.60029 · doi:10.1214/009117904000000324
[27] H. Luschgy and G. Pagès. Sharp asymptotics of the Kolmogorov entropy for Gaussian measures. J. Funct. Anal. 212 (2004) 89-120. · Zbl 1060.60037 · doi:10.1016/j.jfa.2003.09.004
[28] K. Marton. Bounding \(\bar{d}\)-distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24 (1996) 857-866. · Zbl 0865.60017 · doi:10.1214/aop/1039639365
[29] M. Talagrand. Matching random samples in many dimensions. Ann. Appl. Probab. 2 (1992) 846-856. · Zbl 0761.60007 · doi:10.1214/aoap/1177005578
[30] A. W. Van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes . Springer, New York, 1996. · Zbl 0862.60002
[31] V. S. Varadarajan. On the convergence of sample probability distributions. Sankhyā 19 (1958) 23-26. · Zbl 0082.34201
[32] C. Villani. Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften 338 . Springer, Berlin, 2009.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.