Geodesic
On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
Canadian journal of mathematics, Tome 67 (2015) no. 6, pp. 1358-1383

Voir la notice de l'article provenant de la source Cambridge University Press

We consider random i.i.d. samples of absolutely continuous measures on bounded connected domains. We prove an upper bound on the $\infty $ -transportation distance between the measure and the empirical measure of the sample. The bound is optimal in terms of scaling with the number of sample points.
DOI : 10.4153/CJM-2014-044-6
Mots-clés : 60B10, 60D05, 05C70, optimal transportation, optimal matching, infinity transportation distance, min-maxdistance, empirical measure 
Trillos, Nicolás García; Slepčev, Dejan. On the Rate of Convergence of Empirical Measures in ∞-transportation Distance. Canadian journal of mathematics, Tome 67 (2015) no. 6, pp. 1358-1383. doi: 10.4153/CJM-2014-044-6
@article{10_4153_CJM_2014_044_6,
     author = {Trillos, Nicol\'as Garc{\'\i}a and Slep\v{c}ev, Dejan},
     title = {On the {Rate} of {Convergence} of {Empirical} {Measures} in \ensuremath{\infty}-transportation {Distance}},
     journal = {Canadian journal of mathematics},
     pages = {1358--1383},
     year = {2015},
     volume = {67},
     number = {6},
     doi = {10.4153/CJM-2014-044-6},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-044-6/}
}
TY  - JOUR
AU  - Trillos, Nicolás García
AU  - Slepčev, Dejan
TI  - On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
JO  - Canadian journal of mathematics
PY  - 2015
SP  - 1358
EP  - 1383
VL  - 67
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-044-6/
DO  - 10.4153/CJM-2014-044-6
ID  - 10_4153_CJM_2014_044_6
ER  - 
%0 Journal Article
%A Trillos, Nicolás García
%A Slepčev, Dejan
%T On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
%J Canadian journal of mathematics
%D 2015
%P 1358-1383
%V 67
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2014-044-6/
%R 10.4153/CJM-2014-044-6
%F 10_4153_CJM_2014_044_6

[1] [1] Ajtai, M., Komlos, J., and Tusnády, G., On optimal matchings. Combinatorica 4(1984), no. 4, 259–264. Google Scholar | DOI

[2] [2] Arora, S., Rao, S., and Vazirani, U., Expander flows, geometric embeddings anagraph partitioning. J. ACM (JACM) 56(2009), no. 2, Art. 5,1–37. Google Scholar

[3] [3] Ball, J. M. and Zarnescu, A., Partial regularity and smooth topology-preserving approximations of rough domains. arxiv:1312.5156 Google Scholar

[4] [4] Berstein, S., On a modification of Chebyshev's inequality and of the error formula of Laplace. Ann.Sci. Inst. Sav., Sect. Math. 1(1924), no. 4, 38–49. Google Scholar

[5] [5] Boissard, E., Simple bounds for convergence of empirical and occupation measures in 1-Wasserstein distance. Electron. J. Probab. 16(2011), no. 83, 2296–2333. Google Scholar | DOI

[6] [6] Bolley, F., Guillin, A., and Villani, C., Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Related Fields 137(2007), no. 3-4, 541–593. Google Scholar | DOI

[7] [7] Champion, T., Thierry, L., De Pascale, and Juutinen, P., The ∞-Wasserstein distance: local solutions and existence of optimal transport maps. SIAM J. Math. Anal. 40(2008), no. 1,1–20. Google Scholar | DOI

[8] [8] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics 23(1952), 493–507. Google Scholar | DOI

[9] [9] Dobriaac, V. and Yukich, J. E., Asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8(1995), no. 1, 97–118. Google Scholar | DOI

[10] [10] Dudley, R. M., The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40(1968), 40–50. Google Scholar | DOI

[11] [11] Leighton, T. and Shor, P., Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. Combinatorica 9(1989), no. 2,161–187. Google Scholar | DOI

[12] [12] Shor, P. W. and Yukich, J. E., Minimax grid matching and empirical measures. Ann. Probab. 19(1991), no. 3, 1338–1348. Google Scholar | DOI

[13] [13] Talagrand, M., The generic chaining. Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2005. Google Scholar

[14] [14] Talagrand, M., Upper and lower bounds of stochastic processes. A Series of Modern Surveys in Mathematics, 60, Springer-Verlag, Berlin Heidelberg, 2014 Google Scholar

[15] [15] Talagrand, M., The transportation cost from the uniform measure to the empirical measure in dimension ≥ 3. Ann. Probab. 22(1994), no. 2, 919–959. Google Scholar | DOI

[16] [16] Talagrand, M. and Yukich, J. E., The integrability of the square exponential transportation cost. Ann. Appl. Probab. 3(1993), no. 4, 1100–1111. Google Scholar | DOI

Cité par Sources :