Empirical measures: regularity is a counter-curse to dimensionality

2018/02/12 by Benoît Kloeckner, Kloeckner, Benoît · 2 citations
Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1802.04038

openalex publication_date 2018/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 1/√(n) (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.

Citations

• Ricci curvature of Markov chains on metric spaces
• Effective limit theorems for Markov chains with a spectral gap
• Contraction in the Wasserstein metric for some Markov chains, and\n applications to the dynamics of expanding maps

Cited by

• On the Design of One-step Diffusion via Shortcutting Flow Paths
• Learning from one graph: transductive learning guarantees via the geometry of small random worlds

Related

• Convergence of the empirical measure in expected Wasserstein distance: non asymptotic explicit bounds in ℝ^d
• On the rate of convergence in Wasserstein distance of the empirical\n measure
• Convergence of Empirical Measures for i.i.d. samples in W^{-α, p}
• Convergence of Adapted Empirical Measures on ℝ^d
• A Class of Dimension-free Metrics for the Convergence of Empirical Measures