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) 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.

DOI : 10.1214/12-AIHP517
Classification : 60B10, 65C50, 60J05
Mots-clés : 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 = {https://www.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  - https://www.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 https://www.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, Tome 50 (2014) no. 2, pp. 539-563. doi : 10.1214/12-AIHP517. https://www.numdam.org/articles/10.1214/12-AIHP517/

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

  • Lin, Judy Yangjun Statistical Wasserstein distance with rank regularization and spiked structure, Communications in Statistics - Theory and Methods (2025), p. 1 | DOI:10.1080/03610926.2025.2455943
  • Hundrieser, Shayan; Staudt, Thomas; Munk, Axel Empirical optimal transport between different measures adapts to lower complexity, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 60 (2024) no. 2 | DOI:10.1214/23-aihp1369
  • Hundrieser, Shayan; Klatt, Marcel; Munk, Axel; Staudt, Thomas A unifying approach to distributional limits for empirical optimal transport, Bernoulli, Volume 30 (2024) no. 4 | DOI:10.3150/23-bej1697
  • Stromme, Austin J. Minimum Intrinsic Dimension Scaling for Entropic Optimal Transport, Combining, Modelling and Analyzing Imprecision, Randomness and Dependence, Volume 1458 (2024), p. 491 | DOI:10.1007/978-3-031-65993-5_60
  • Lara Benitez, Jose Antonio; Furuya, Takashi; Faucher, Florian; Kratsios, Anastasis; Tricoche, Xavier; de Hoop, Maarten V. Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation, Journal of Computational Physics, Volume 513 (2024), p. 113168 | DOI:10.1016/j.jcp.2024.113168
  • Manole, Tudor; Niles-Weed, Jonathan Sharp convergence rates for empirical optimal transport with smooth costs, The Annals of Applied Probability, Volume 34 (2024) no. 1B | DOI:10.1214/23-aap1986
  • Goldfeld, Ziv; Kato, Kengo; Nietert, Sloan; Rioux, Gabriel Limit distribution theory for smooth p-Wasserstein distances, The Annals of Applied Probability, Volume 34 (2024) no. 2 | DOI:10.1214/23-aap2028
  • Acciaio, Beatrice; Hou, Songyan Convergence of adapted empirical measures on Rd, The Annals of Applied Probability, Volume 34 (2024) no. 5 | DOI:10.1214/24-aap2082
  • Manole, Tudor; Balakrishnan, Sivaraman; Niles-Weed, Jonathan; Wasserman, Larry Plugin estimation of smooth optimal transport maps, The Annals of Statistics, Volume 52 (2024) no. 3 | DOI:10.1214/24-aos2379
  • Zhang, Zhengxin; Goldfeld, Ziv; Mroueh, Youssef; Sriperumbudur, Bharath K. Gromov–Wasserstein distances: Entropic regularization, duality and sample complexity, The Annals of Statistics, Volume 52 (2024) no. 4 | DOI:10.1214/24-aos2406
  • Wang, Feng-Yu; Zhu, Jie-Xiang Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 59 (2023) no. 1 | DOI:10.1214/22-aihp1251
  • Yu, Lei Asymptotics for Strassen’s optimal transport problem, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 59 (2023) no. 4 | DOI:10.1214/22-aihp1258
  • Borda, Bence Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 59 (2023) no. 4 | DOI:10.1214/22-aihp1322
  • Du, Kai; Jiang, Yifan; Li, Jinfeng Empirical approximation to invariant measures for McKean–Vlasov processes: Mean-field interaction vs self-interaction, Bernoulli, Volume 29 (2023) no. 3 | DOI:10.3150/22-bej1550
  • Fournier, Nicolas Convergence of the empirical measure in expected wasserstein distance: non-asymptotic explicit bounds in ℝd, ESAIM: Probability and Statistics, Volume 27 (2023), p. 749 | DOI:10.1051/ps/2023011
  • Motte, Médéric; Pham, Huyên Quantitative propagation of chaos for mean field Markov decision process with common noise, Electronic Journal of Probability, Volume 28 (2023) no. none | DOI:10.1214/23-ejp978
  • Han, Fang; Miao, Zhen; Shen, Yandi Nonparametric Mixture MLEs Under Gaussian-Smoothed Optimal Transport Distance, IEEE Transactions on Information Theory, Volume 69 (2023) no. 12, p. 7823 | DOI:10.1109/tit.2023.3296380
  • Ledoux, Michel Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures, Mathematics Going Forward, Volume 2313 (2023), p. 615 | DOI:10.1007/978-3-031-12244-6_43
  • Wang, Feng-Yu; Wu, Bingyao Wasserstein Convergence for Empirical Measures of Subordinated Diffusions on Riemannian Manifolds, Potential Analysis, Volume 59 (2023) no. 3, p. 933 | DOI:10.1007/s11118-022-09989-6
  • Niles-Weed, Jonathan; Rigollet, Philippe Estimation of Wasserstein distances in the Spiked Transport Model, Bernoulli, Volume 28 (2022) no. 4 | DOI:10.3150/21-bej1433
  • Manole, Tudor; Balakrishnan, Sivaraman; Wasserman, Larry Minimax confidence intervals for the Sliced Wasserstein distance, Electronic Journal of Statistics, Volume 16 (2022) no. 1 | DOI:10.1214/22-ejs2001
  • Salkeld, William Small ball probabilities, metric entropy and Gaussian rough paths, Journal of Mathematical Analysis and Applications, Volume 506 (2022) no. 2, p. 125697 | DOI:10.1016/j.jmaa.2021.125697
  • Heinemann, Florian; Munk, Axel; Zemel, Yoav Randomized Wasserstein Barycenter Computation: Resampling with Statistical Guarantees, SIAM Journal on Mathematics of Data Science, Volume 4 (2022) no. 1, p. 229 | DOI:10.1137/20m1385263
  • Motte, Médéric; Pham, Huyên Mean-field Markov decision processes with common noise and open-loop controls, The Annals of Applied Probability, Volume 32 (2022) no. 2 | DOI:10.1214/21-aap1713
  • Niles-Weed, Jonathan; Berthet, Quentin Minimax estimation of smooth densities in Wasserstein distance, The Annals of Statistics, Volume 50 (2022) no. 3 | DOI:10.1214/21-aos2161
  • Borda, Bence Berry–Esseen Smoothing Inequality for the Wasserstein Metric on Compact Lie Groups, Journal of Fourier Analysis and Applications, Volume 27 (2021) no. 2 | DOI:10.1007/s00041-020-09803-0
  • Panaretos, Victor M.; Zemel, Yoav Phase Variation and Fréchet Means, An Invitation to Statistics in Wasserstein Space (2020), p. 75 | DOI:10.1007/978-3-030-38438-8_4
  • Lei, Jing Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces, Bernoulli, Volume 26 (2020) no. 1 | DOI:10.3150/19-bej1151
  • Kloeckner, Benoît R. Empirical measures: regularity is a counter-curse to dimensionality, ESAIM: Probability and Statistics, Volume 24 (2020), p. 408 | DOI:10.1051/ps/2019025
  • Goldfeld, Ziv; Greenewald, Kristjan; Niles-Weed, Jonathan; Polyanskiy, Yury Convergence of Smoothed Empirical Measures With Applications to Entropy Estimation, IEEE Transactions on Information Theory, Volume 66 (2020) no. 7, p. 4368 | DOI:10.1109/tit.2020.2975480
  • Honoré, Igor Sharp non-asymptotic concentration inequalities for the approximation of the invariant distribution of a diffusion, Stochastic Processes and their Applications, Volume 130 (2020) no. 4, p. 2127 | DOI:10.1016/j.spa.2019.06.012
  • Panaretos, Victor M.; Zemel, Yoav Statistical Aspects of Wasserstein Distances, Annual Review of Statistics and Its Application, Volume 6 (2019) no. 1, p. 405 | DOI:10.1146/annurev-statistics-030718-104938
  • Dolera, Emanuele; Regazzini, Eugenio Uniform rates of the Glivenko–Cantelli convergence and their use in approximating Bayesian inferences, Bernoulli, Volume 25 (2019) no. 4A | DOI:10.3150/18-bej1077
  • Weed, Jonathan; Bach, Francis Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance, Bernoulli, Volume 25 (2019) no. 4A | DOI:10.3150/18-bej1065
  • Dedecker, Jérôme; Merlevède, Florence Behavior of the empirical Wasserstein distance in Rd under moment conditions, Electronic Journal of Probability, Volume 24 (2019) no. none | DOI:10.1214/19-ejp266
  • Ambrosio, Luigi; Glaudo, Federico Finer estimates on the 2-dimensional matching problem, Journal de l’École polytechnique — Mathématiques, Volume 6 (2019), p. 737 | DOI:10.5802/jep.105
  • Tameling, Carla; Sommerfeld, Max; Munk, Axel Empirical optimal transport on countable metric spaces: Distributional limits and statistical applications, The Annals of Applied Probability, Volume 29 (2019) no. 5 | DOI:10.1214/19-aap1463
  • Chevallier, Julien Uniform decomposition of probability measures: quantization, clustering and rate of convergence, Journal of Applied Probability, Volume 55 (2018) no. 4, p. 1037 | DOI:10.1017/jpr.2018.69
  • Andreis, Luisa; Dai Pra, Paolo; Fischer, Markus McKean–Vlasov limit for interacting systems with simultaneous jumps, Stochastic Analysis and Applications, Volume 36 (2018) no. 6, p. 960 | DOI:10.1080/07362994.2018.1486202
  • Blanchet, Jose; He, Fei; Lam, Henry, 2017 Winter Simulation Conference (WSC) (2017), p. 2315 | DOI:10.1109/wsc.2017.8247962
  • Fournier, Nicolas; Mischler, Stéphane Rate of convergence of the Nanbu particle system for hard potentials and Maxwell molecules, The Annals of Probability, Volume 44 (2016) no. 1 | DOI:10.1214/14-aop983
  • Dereich, Steffen; Scheutzow, Michael; Schottstedt, Reik Constructive quantization: Approximation by empirical measures, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 49 (2013) no. 4, pp. 1183-1203 | DOI:10.1214/12-aihp489
  • Fournier, Nicolas; Guillin, Arnaud On the rate of convergence in Wasserstein distance of the empirical measure, arXiv (2013) | DOI:10.48550/arxiv.1312.2128 | arXiv:1312.2128
  • Mischler, Stéphane Kac's chaos and Kac's program, arXiv (2013) | DOI:10.48550/arxiv.1311.7544 | arXiv:1311.7544
  • Hauray, Maxime; Mischler, Stéphane On Kac's Chaos And Related Problems, arXiv (2012) | DOI:10.48550/arxiv.1205.4518 | arXiv:1205.4518
  • Maïda, Mylène; Maurel-Segala, Édouard Free transport-entropy inequalities for non-convex potentials and application to concentration for random matrices, arXiv (2012) | DOI:10.48550/arxiv.1204.3208 | arXiv:1204.3208

Cité par 46 documents. Sources : Crossref, NASA ADS