Empirical measures: regularity is a counter-curse to dimensionality
ESAIM: Probability and Statistics, Tome 24 (2020), pp. 408-434.

We propose a “decomposition method” to prove non-asymptotic bound for the convergence of empirical measures in various dual norms. The main point is to show that if one measures convergence in duality with sufficiently regular observables, the convergence is much faster than for, say, merely Lipschitz observables. Actually, assuming s derivatives with s > d∕2 (d the dimension) ensures an optimal rate of convergence of $$ (n the number of samples). The method is flexible enough to apply to Markov chains which satisfy a geometric contraction hypothesis, assuming neither stationarity nor reversibility, with the same convergence speed up to a power of logarithm factor. Our results are stated as controls of the expected distance between the empirical measure and its limit, but we explain briefly how the classical method of bounded difference can be used to deduce concentration estimates.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ps/2019025
Classification : 60B10, 60J05, 62E17, 49Q20
Mots-clés : Concentration, dual norms, empirical measure, Markov chains, non-asymptotic bounds, Wasserstein metric 
@article{PS_2020__24_1_408_0,
     author = {Kloeckner, Beno{\^\i}t R.},
     title = {Empirical measures: regularity is a counter-curse to dimensionality},
     journal = {ESAIM: Probability and Statistics},
     pages = {408--434},
     publisher = {EDP-Sciences},
     volume = {24},
     year = {2020},
     doi = {10.1051/ps/2019025},
     mrnumber = {4153634},
     zbl = {1452.60007},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ps/2019025/}
}
TY  - JOUR
AU  - Kloeckner, Benoît R.
TI  - Empirical measures: regularity is a counter-curse to dimensionality
JO  - ESAIM: Probability and Statistics
PY  - 2020
SP  - 408
EP  - 434
VL  - 24
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ps/2019025/
DO  - 10.1051/ps/2019025
LA  - en
ID  - PS_2020__24_1_408_0
ER  - 
%0 Journal Article
%A Kloeckner, Benoît R.
%T Empirical measures: regularity is a counter-curse to dimensionality
%J ESAIM: Probability and Statistics
%D 2020
%P 408-434
%V 24
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ps/2019025/
%R 10.1051/ps/2019025
%G en
%F PS_2020__24_1_408_0
Kloeckner, Benoît R. Empirical measures: regularity is a counter-curse to dimensionality. ESAIM: Probability and Statistics, Tome 24 (2020), pp. 408-434. doi : 10.1051/ps/2019025. http://archive.numdam.org/articles/10.1051/ps/2019025/

[1] M. Ajtai, J. Komlós and G. Tusnády, On optimal matchings. Combinatorica 4 (1984) 259–264. | DOI | MR | Zbl

[2] L. Ambrosio, F. Stra and D. Trevisan, A PDE approach to a 2-dimensional matching problem. Probab. Theory Related Fields 173 (2019) 433–477. | DOI | MR | Zbl

[3] E. Boissard and T. Le Gouic, On the mean speed of convergence of empirical and occupation measures in Wasserstein distance. Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014) 539–563. | DOI | Numdam | MR | Zbl

[4] J.-R. Chazottes and F. Redig, Concentration inequalities for Markov processes via coupling. Electron. J. Probab. 14 (2009) 1162–1180. | MR | Zbl

[5] J.-R. Chazottes and S. Gouëzel, Optimal concentration inequalities for dynamical systems. Commun. Math. Phys. 316 (2012) 843–889. | DOI | MR | Zbl

[6] I. Daubechies, Orthonormal bases of compactly supported wavelets. Commun. Pure Appl. Math. 41 (1988) 909–996. | DOI | MR | Zbl

[7] J. Dedecker and X. Fan, Deviation inequalities for separately Lipschitz functionals of iterated random functions. Stochastic Process. Appl. 125 (2015) 60–90. | DOI | MR | Zbl

[8] J. Dedecker and F. Merlevède, Behavior of the empirical Wasserstein distance in R$$ under moment conditions. Electron. J. Probab. 24 (2019). | DOI | MR | Zbl

[9] S. Dereich, M. Scheutzow and R. Schottstedt, Constructive quantization: approximation by empirical measures. Ann. Inst. Henri Poincaré Probab. Stat. 49 (2013) 1183–1203. | DOI | Numdam | MR | Zbl

[10] R.M. Dudley, Real analysis and probability. Vol. 74 of Cambridge Studies in Advanced Mathematics. Revised reprint ofthe 1989 original. MR 1932358. Cambridge University Press, Cambridge (2002). | MR | Zbl

[11] A. Eberle, Reflection couplings and contraction rates for diffusions. Probab. Theory Related Fields 166 (2016) 851–886. | DOI | MR | Zbl

[12] N. Fournier and A. Guillin, On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Related Fields 162 (2015) 707–738. | DOI | MR | Zbl

[13] J.E. Hutchinson, Fractals and self-similarity. Indiana Univ. Math. J. 30 (1981) 713–747. | DOI | MR | Zbl

[14] A. Joulin, A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature. Bernoulli 15 (2009) 532–549. | DOI | MR | Zbl

[15] A. Joulin and Y. Ollivier, Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 (2010) 2418–2442. | DOI | MR | Zbl

[16] B.R. Kloeckner, An optimal transportation approach to the decay of correlations for non-uniformly expanding maps. Ergodic Theory Dyn. Syst. 40 (2020) 714–750. | DOI | MR | Zbl

[17] B. Kloeckner, Effective Berry-Esseen and concentration bounds for Markov chains with a spectral gap. Ann. Appl. Probab. 29 (2019) 1778–1807. | DOI | MR | Zbl

[18] B.R. Kloeckner, A.O. Lopes and M. Stadlbauer, Contraction in the Wasserstein metric for some Markov chains, and applications to the dynamics of expanding maps. Nonlinearity 28 (2015) 4117–4137. | DOI | MR | Zbl

[19] A. Kontorovich, Obtaining measure concentration from Markov contraction. Markov Process. Related Fields 18 (2012) 613–638. | MR | Zbl

[20] J.C. Mason, Near-best multivariate approximation by Fourier series, Chebyshev series and Chebyshev interpolation. J. Approx. Theory 28 (1980) 349–358. | DOI | MR | Zbl

[21] Y. Meyer, Wavelets and operators. Vol. 1. Cambridge University Press (1992). | MR | Zbl

[22] P. Monmarché, On H1 and entropic convergence for contractive PDMP. Electron. J. Probab. 20 (2015). | DOI | MR | Zbl

[23] Y. Ollivier, Ricci curvature of Markov chains on metric spaces. J. Funct. Anal. 256 (2009) 810–864. | DOI | MR | Zbl

[24] D. Paulin, Mixing and concentration by Ricci curvature. J. Funct. Anal. 270 (2016) 1623–1662. | DOI | MR | Zbl

[25] M.H. Schultz, Linf-multivariate approximation theory. SIAM J. Numer. Anal. 6 (1969) 161–183. | DOI | MR | Zbl

[26] M. Talagrand, Matching random samples in many dimensions. Ann. Appl. Probab. 2 (1992) 846–856. | DOI | MR | Zbl

[27] M. Talagrand, Sharper bounds for Gaussian and empirical processes. Ann. Probab. 22 (1994) 28–76. | DOI | MR | Zbl

[28] A.W. Van Der Vaart and J.A. Wellner, Weak convergence and empirical processes. With applications to statistics. MR 1385671. Springer Series in Statistics. Springer-Verlag, New York (1996). | MR | Zbl

[29] R. Van Handel, Probability in high dimension, APC 550 Lecture Notes. Princeton University (1996). Available from: http://www.princeton.edu/~rvan/APC550.pdf.

[30] J. Weed and F. Bach, Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli 25 (2019) 2620–2648. | DOI | MR | Zbl

[31] J. Weed and Q. Berthet, Estimation of smooth densities in wasserstein distance. Preprint (2019). | arXiv | MR

Cité par Sources :