On the rate of convergence of empirical measure in $\infty$-Wasserstein distance for unbounded density function
Authors:
Anning Liu, Jian-Guo Liu and Yulong Lu
Journal:
Quart. Appl. Math. 77 (2019), 811-829
MSC (2010):
Primary 60B10, 68R10
DOI:
https://doi.org/10.1090/qam/1541
Published electronically:
May 22, 2019
MathSciNet review:
4009333
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider a sequence of identical independently distributed random samples from an absolutely continuous probability measure in one dimension with unbounded density. We establish a new rate of convergence of the $\infty$-Wasserstein distance between the empirical measure of the samples and the true distribution, which extends the previous convergence result by Trillos and Slepčev to the case that the true distribution has an unbounded density.
References
- M. Ajtai, J. Komlós, and G. Tusnády, On optimal matchings, Combinatorica 4 (1984), no. 4, 259–264. MR 779885, DOI https://doi.org/10.1007/BF02579135
- Franck Barthe and Charles Bordenave, Combinatorial optimization over two random point sets, Séminaire de Probabilités XLV, Lecture Notes in Math., vol. 2078, Springer, Cham, 2013, pp. 483–535. MR 3185927, DOI https://doi.org/10.1007/978-3-319-00321-4_19
- S. N. Bernstein, The theory of probabilities, Gastehizdat Publishing House,Moscow, 1946.
- Emmanuel Boissard, Simple bounds for convergence of empirical and occupation measures in 1-Wasserstein distance, Electron. J. Probab. 16 (2011), no. 83, 2296–2333. MR 2861675, DOI https://doi.org/10.1214/EJP.v16-958
- Emmanuel Boissard and Thibaut Le Gouic, On the mean speed of convergence of empirical and occupation measures in Wasserstein distance, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 2, 539–563 (English, with English and French summaries). MR 3189084, DOI https://doi.org/10.1214/12-AIHP517
- François Bolley, Arnaud Guillin, and Cédric Villani, Quantitative concentration inequalities for empirical measures on non-compact spaces, Probab. Theory Related Fields 137 (2007), no. 3-4, 541–593. MR 2280433, DOI https://doi.org/10.1007/s00440-006-0004-7
- Thierry Champion, Luigi De Pascale, and Petri Juutinen, The $\infty $-Wasserstein distance: local solutions and existence of optimal transport maps, SIAM J. Math. Anal. 40 (2008), no. 1, 1–20. MR 2403310, DOI https://doi.org/10.1137/07069938X
- Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493–507. MR 57518, DOI https://doi.org/10.1214/aoms/1177729330
- M. d’Amico, P. Frosini, and C. Landi, Using matching distance in size theory: A survey, International Journal of Imaging Systems and Technology 16 (2006), no. 5, 154–161.
- Erik Davis and Sunder Sethuraman, Consistency of modularity clustering on random geometric graphs, Ann. Appl. Probab. 28 (2018), no. 4, 2003–2062. MR 3843822, DOI https://doi.org/10.1214/17-AAP1313
- R. M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist. 40 (1968), 40–50. MR 236977, DOI https://doi.org/10.1214/aoms/1177697802
- A. Dvoretzky, J. Kiefer, and J. Wolfowitz, Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, Ann. Math. Statist. 27 (1956), 642–669. MR 83864, DOI https://doi.org/10.1214/aoms/1177728174
- Nicolas Fournier and Arnaud Guillin, On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Related Fields 162 (2015), no. 3-4, 707–738. MR 3383341, DOI https://doi.org/10.1007/s00440-014-0583-7
- A. L. Gibbs and F. E. Su, On choosing and bounding probability metrics, International statistical review 70 (2002), no. 3, 419–435.
- T. Leighton and P. Shor, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica 9 (1989), no. 2, 161–187. MR 1030371, DOI https://doi.org/10.1007/BF02124678
- P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures, Ann. Probab. 19 (1991), no. 3, 1338–1348. MR 1112419
- P. Tchebichef, Des valeurs moyennes, Journal de mathématiques pures et appliquées 12 (1867), no. 2, 177–184.
- N. García Trillos and D. Slepčev, A variational approach to the consistency of spectral clustering, Applied and Computational Harmonic Analysis (2016).
- Nicolás García Trillos and Dejan Slepčev, On the rate of convergence of empirical measures in $\infty $-transportation distance, Canad. J. Math. 67 (2015), no. 6, 1358–1383. MR 3415656, DOI https://doi.org/10.4153/CJM-2014-044-6
- Aad W. van der Vaart and Jon A. Wellner, Weak convergence and empirical processes, Springer Series in Statistics, Springer-Verlag, New York, 1996. With applications to statistics. MR 1385671
- Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483
- Ulrike von Luxburg, A tutorial on spectral clustering, Stat. Comput. 17 (2007), no. 4, 395–416. MR 2409803, DOI https://doi.org/10.1007/s11222-007-9033-z
References
- M. Ajtai, J. Komlós, and G. Tusnády, On optimal matchings, Combinatorica 4 (1984), no. 4, 259–264. MR 779885, DOI https://doi.org/10.1007/BF02579135
- Franck Barthe and Charles Bordenave, Combinatorial optimization over two random point sets, Séminaire de Probabilités XLV, Lecture Notes in Math., vol. 2078, Springer, Cham, 2013, pp. 483–535. MR 3185927, DOI https://doi.org/10.1007/978-3-319-00321-4_19
- S. N. Bernstein, The theory of probabilities, Gastehizdat Publishing House,Moscow, 1946.
- Emmanuel Boissard, Simple bounds for convergence of empirical and occupation measures in 1-Wasserstein distance, Electron. J. Probab. 16 (2011), no. 83, 2296–2333. MR 2861675, DOI https://doi.org/10.1214/EJP.v16-958
- Emmanuel Boissard and Thibaut Le Gouic, On the mean speed of convergence of empirical and occupation measures in Wasserstein distance, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 2, 539–563 (English, with English and French summaries). MR 3189084, DOI https://doi.org/10.1214/12-AIHP517
- François Bolley, Arnaud Guillin, and Cédric Villani, Quantitative concentration inequalities for empirical measures on non-compact spaces, Probab. Theory Related Fields 137 (2007), no. 3-4, 541–593. MR 2280433, DOI https://doi.org/10.1007/s00440-006-0004-7
- Thierry Champion, Luigi De Pascale, and Petri Juutinen, The $\infty$-Wasserstein distance: local solutions and existence of optimal transport maps, SIAM J. Math. Anal. 40 (2008), no. 1, 1–20. MR 2403310, DOI https://doi.org/10.1137/07069938X
- Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493–507. MR 0057518, DOI https://doi.org/10.1214/aoms/1177729330
- M. d’Amico, P. Frosini, and C. Landi, Using matching distance in size theory: A survey, International Journal of Imaging Systems and Technology 16 (2006), no. 5, 154–161.
- Erik Davis and Sunder Sethuraman, Consistency of modularity clustering on random geometric graphs, Ann. Appl. Probab. 28 (2018), no. 4, 2003–2062. MR 3843822, DOI https://doi.org/10.1214/17-AAP1313
- R. M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist 40 (1968), 40–50. MR 0236977, DOI https://doi.org/10.1214/aoms/1177697802
- A. Dvoretzky, J. Kiefer, and J. Wolfowitz, Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, Ann. Math. Statist. 27 (1956), 642–669. MR 0083864, DOI https://doi.org/10.1214/aoms/1177728174
- Nicolas Fournier and Arnaud Guillin, On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Related Fields 162 (2015), no. 3-4, 707–738. MR 3383341, DOI https://doi.org/10.1007/s00440-014-0583-7
- A. L. Gibbs and F. E. Su, On choosing and bounding probability metrics, International statistical review 70 (2002), no. 3, 419–435.
- T. Leighton and P. Shor, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica 9 (1989), no. 2, 161–187. MR 1030371, DOI https://doi.org/10.1007/BF02124678
- P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures, Ann. Probab. 19 (1991), no. 3, 1338–1348. MR 1112419
- P. Tchebichef, Des valeurs moyennes, Journal de mathématiques pures et appliquées 12 (1867), no. 2, 177–184.
- N. García Trillos and D. Slepčev, A variational approach to the consistency of spectral clustering, Applied and Computational Harmonic Analysis (2016).
- Nicolás García Trillos and Dejan Slepčev, On the rate of convergence of empirical measures in $\infty$-transportation distance, Canad. J. Math. 67 (2015), no. 6, 1358–1383. MR 3415656, DOI https://doi.org/10.4153/CJM-2014-044-6
- Aad W. van der Vaart and Jon A. Wellner, Weak convergence and empirical processes, Springer Series in Statistics, Springer-Verlag, New York, 1996. With applications to statistics. MR 1385671
- Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483
- Ulrike von Luxburg, A tutorial on spectral clustering, Stat. Comput. 17 (2007), no. 4, 395–416. MR 2409803, DOI https://doi.org/10.1007/s11222-007-9033-z
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC (2010):
60B10,
68R10
Retrieve articles in all journals
with MSC (2010):
60B10,
68R10
Additional Information
Anning Liu
Affiliation:
Department of Mathematical Sciences, Tsinghua University, Beijing 100084, People’s Republic of China
Email:
lan15@mails.tsinghua.edu.cn
Jian-Guo Liu
Affiliation:
Department of Mathematics and Department of Physics, Duke University, Durham, North Carolina 27708
MR Author ID:
233036
ORCID:
0000-0002-9911-4045
Email:
jliu@phy.duke.edu
Yulong Lu
Affiliation:
Department of Mathematics, Duke University, Durham, North Carolina 27708
MR Author ID:
1039427
Email:
yulonglu@math.duke.edu
Received by editor(s):
August 1, 2018
Received by editor(s) in revised form:
March 30, 2019
Published electronically:
May 22, 2019
Additional Notes:
The research was partially supported by KI-Net NSF RNMS11-07444 and NSF DMS-1812573.
Article copyright:
© Copyright 2019
Brown University
