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.
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.
Keywords: Wasserstein metrics, optimal transportation, functional quantization, transportation inequalities, Markov chains, measure theory
@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}, pages = {539--563}, publisher = {Gauthier-Villars}, volume = {50}, number = {2}, year = {2014}, doi = {10.1214/12-AIHP517}, mrnumber = {3189084}, zbl = {1294.60005}, language = {en}, url = {http://archive.numdam.org/articles/10.1214/12-AIHP517/} }
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 SP - 539 EP - 563 VL - 50 IS - 2 PB - Gauthier-Villars UR - http://archive.numdam.org/articles/10.1214/12-AIHP517/ DO - 10.1214/12-AIHP517 LA - en ID - AIHPB_2014__50_2_539_0 ER -
%0 Journal Article %A Boissard, Emmanuel %A Le Gouic, Thibaut %T On the mean speed of convergence of empirical and occupation measures in Wasserstein distance %J Annales de l'I.H.P. Probabilités et statistiques %D 2014 %P 539-563 %V 50 %N 2 %I Gauthier-Villars %U http://archive.numdam.org/articles/10.1214/12-AIHP517/ %R 10.1214/12-AIHP517 %G en %F 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, Volume 50 (2014) no. 2, pp. 539-563. doi : 10.1214/12-AIHP517. http://archive.numdam.org/articles/10.1214/12-AIHP517/
[1] On optimal matchings. Combinatorica 4 (1984) 259-264. | MR | Zbl
, and .[2] Combinatorial optimization over two random point sets. Preprint, 2011. Available at arXiv:1103.2734v1. | MR
and .[3] Hypercontractivity of Hamilton-Jacobi equations. J. Math. Pures Appl. 80 (2001) 669-696. | MR | Zbl
, and .[4] Simple bounds for the convergence of empirical and occupation measures in 1-Wasserstein distance. Electron J. Probab 16 (2011) 2296-2333. | MR | Zbl
.[5] Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Related Fields 137 (2007) 541-593. | MR | Zbl
, and .[6] Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities. Ann. Fac. Sci. Toulouse Math. 14 (2005) 331-351. | EuDML | Numdam | MR | Zbl
and .[7] Central limit theorems for additive functionals of ergodic Markov diffusion processes. Preprint, 2011. Available at arXiv:1104.2198. | MR | Zbl
, and .[8] Central limit theorems for the Wasserstein distance between the empirical and the true distributions. Ann. Probab. 27 (1999) 1009-1071. | MR | Zbl
, and .[9] 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
, , and .[10] Transportation cost-information inequalities for random dynamical systems and diffusions. Ann. Probab. 32 (2004) 2702-2732. | MR | Zbl
, and .[11] Exact asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1995) 97-118. | MR | Zbl
and .[12] The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40 (1969) 40-50. | MR | Zbl
.[13] Kodierung von Gaußmaßen. Ph.D. manuscript, 2001, available at http://d-nb.info/962880116.
.[14] A large deviation approach to some transportation cost inequalities. Probab. Theory Related Fields 139 (2007) 235-283. | MR | Zbl
and .[15] Transport inequalities. A survey. Markov Process. Related Fields 16 (2010) 635-736. | MR | Zbl
and .[16] Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730. Springer, Berlin, 2000. | MR | Zbl
and .[17] Rates of convergence for the empirical quantization error. Ann. Probab. 30 (2002) 874-897. | MR | Zbl
and .[18] Functional quantization and small ball probabilities for Gaussian processes. J. Theoret. Probab. 16 (2003) 1047-1062. | MR | Zbl
, and .[19] Mean rates of convergence of empirical measures in the Wasserstein metric. J. Comput. Appl. Math. 55 (1994) 261-273. | MR | Zbl
and .[20] Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 (2010) 2418-2442. | MR | Zbl
and .[21] Metric entropy and the small ball problem for Gaussian measures. J. Funct. Anal. 116 (1993) 133-157. | MR | Zbl
and .[22] 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] The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89. Am. Math. Soc., Providence, RI, 2001. | MR | Zbl
.[24] Probability in Banach Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)] 23. Springer, Berlin, 1991. | MR | Zbl
and .[25] Approximation, metric entropy and small ball estimates for Gaussian measures. Ann. Probab. 27 (1999) 1556-1578. | MR | Zbl
and .[26] Sharp asymptotics of the functional quantization problem for Gaussian processes. Ann. Probab. 32 (2004) 1574-1599. | MR | Zbl
and .[27] Sharp asymptotics of the Kolmogorov entropy for Gaussian measures. J. Funct. Anal. 212 (2004) 89-120. | MR | Zbl
and .[28] Bounding -distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24 (1996) 857-866. | MR | Zbl
.[29] Matching random samples in many dimensions. Ann. Appl. Probab. 2 (1992) 846-856. | MR | Zbl
.[30] Weak Convergence and Empirical Processes. Springer, New York, 1996. | MR | Zbl
and .[31] On the convergence of sample probability distributions. Sankhyā 19 (1958) 23-26. | MR | Zbl
.[32] Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften 338. Springer, Berlin, 2009. | MR | Zbl
.Cited by Sources: