Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance

By Jonathan Weed, Francis R. Bach. 2017

514 citations recorded by the source corpus.

The Wasserstein distance between two probability measures on a metric space is a measure of closeness with applications in statistics, probability, and machine learning. In this work, we consider the fundamental question of how quickly the empirical measure obtained from $n$ independent samples from $\mu$ approaches $\mu$ in the Wasserstein distance of any order. We prove sharp asymptotic and finite-sample results for this rate of convergence for general measures on general compact metric spaces. Our finite-sample results show the existence of multi-scale behavior, where measures can exhibit radically different rates of convergence as $n$ grows.

Subfields: Applied Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

Citations in the corpus

Wasserstein Fair Classification (2019, background): “(4) and (6), and (5) and (7): Therefore the following inequality holds almost surely: Since W 1 ( p S a , ˆ p S a ) → 0 almost surely for all a (see Weed and Bach (2017)), and ˆ p a → p a almost surely (by the strong law of large numbers) and W 1 ( p S , p S a ) < ∞ for all a , the result follows:…”
Learning Generative Models with Sinkhorn Divergences (2017, background): “In contrast, the unreg-ularized OT loss suﬀers from a sample complexity of O (1 /n 1 /d ) , see [36] for a recent account on this point.”
Computational Optimal Transport (2018, background): “Computational Optimal Transport Gabriel Peyré ÉCOLE NORMALE S U P É R I E U R E RESEARCH UNIVERSITY PARIS Joint work with: Francis Bach François-Xavier Vialard Jean Feydy Thibault Séjourné Lénaic Chizat Aude Genevay Marco Cuturi Alain Trouvé Shun'ichi Amari https://optimaltransport.github.io Optimal”
Sample Complexity of Sinkhorn Divergences (2018, background): “Although it was recently proved that this result can be reﬁned to consider the implicit dimension of data (Weed and Bach, 2017), the sample complexity of OT appears now to be the major bottleneck for the use of OT in high-dimensional machine learning problems.”
Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning (2019, methodology): “Unfortunately, this curse of dimensionality is fundamental, and the decay rate of ε p,N ( η ) is essentially optimal; see [36, § 1.3] or [109].”
TrajectoryNet: A Dynamic Optimal Transport Network for Modeling Cellular Dynamics (2020, background): “However, recent work shows that in high dimensions a more careful treatment that the rate depends on the intrinsic dimension not the ambient dimension (Weed & Bach, 2019).”
Subspace Robust Wasserstein distances (2019, methodology): “This result can be mitigated when data lives on lower dimensional manifolds as shown in (Weed & Bach, 2017), but sample complexity bounds remain pessimistic even in that case.”
Plugin estimation of smooth optimal transport maps (2021, background): “…the empirical measure under the Wasserstein distance is a classical problem (Dudley, 1969; Boissard and Le Gouic, 2014; Fournier and Guillin, 2015; Weed and Bach, 2019; Lei, 2020) which immediately leads to upper bounds on the convergence rate of the empirical plugin estimator of the Wasserstein…”
Statistical Aspects of Wasserstein Distances (2018, methodology): “The version given here can be found in Weed & Bach (2017) and extends Boissard & Le Gouic (2014).”
Regularization via Mass Transportation (2017, background): “2 on the input dimension n cannot be improved for generic distributions P; see [40] or [18, Section 1.”
Point Cloud GAN (2018, background): “However, the estimator with finite samples are either biased or with high variance (Peyré et al., 2017; Wang et al., 2009; Póczos et al., 2012; Weed and Bach, 2017).”
Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces (2018, methodology): “Comparing to [41, 32], both of whom focus on bounded spaces, our result extends to the unbounded case using a moment condition.”