Source-linked AI summary
Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
Jonathan Weed, Francis Bach
TL;DR
The paper asks how quickly empirical measures converge to their target distributions in Wasserstein distance, a question relevant to statistical use of empirical distributions. It develops sharp asymptotic and finite-sample bounds for general measures on compact metric spaces, showing that intrinsic dimension and multi-scale structure govern convergence behavior. The finite-sample results reveal that rates can differ radically across sample-size regimes.
Problem
The paper addresses the need to quantify empirical-measure convergence rates in Wasserstein distance, including faster-rate conditions and sharper finite-sample behavior.
Method
The paper proves upper and lower bounds for Wp(μ, ˆμn) on bounded metric spaces and combines expectation estimates with concentration to obtain high-probability bounds.
Results
The convergence rate depends on the measure’s intrinsic dimension, while multi-scale measures can have much faster small-n convergence than their large-n limiting rate.
Takeaways & Limitations
Measures that are intrinsically or approximately low dimensional can converge reasonably quickly even when embedded in high-dimensional metric spaces.
Takeaways & Limitations
The results are developed for compact metric spaces, and the paper leaves open whether entropically regularized Wasserstein variants achieve better high-dimensional rates.
Abstract
from arXiv · showhide
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 $μ$ approaches $μ$ 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.
1. INTRODUCTION
The paper studies how quickly empirical measures converge to their underlying distributions in Wasserstein distance, addressing dimensionality, finite-sample, and practical convergence questions. It develops general asymptotic and finite-sample results for compact metric spaces.
- Motivation: Wasserstein distance measures closeness between probability distributions through couplings evaluated using the underlying metric.It remains generally finite for empirical distributions even when measures are not mutually absolutely continuous.
- Motivation: Empirical measures from i.i.d. samples converge almost surely to the target distribution in Wasserstein distance on compact separable spaces.This follows from Wasserstein distances metrizing weak convergence and almost-sure weak convergence of empirical measures.
- Open questions: n^-1/d is the exact W1 convergence rate for d-dimensional measures, making slow convergence a necessary challenge in high-dimensional settings.The introduction asks when faster rates and sharper finite-sample bounds are possible.
- Contributions: The paper proves essentially tight asymptotic bounds for Wp on bounded metric spaces, with rates governed by the measure’s intrinsic dimension rather than the ambient metric-space dimension.The intrinsic dimension can be significantly smaller than the dimension of the space supporting the measure.
- Contributions: Finite-sample convergence can display multi-scale behavior, including much faster rates for small n than in the large-n limit.The paper illustrates this phenomenon using examples inspired by measures arising in practice.
- Contributions: Expectation bounds combined with concentration of Wasserstein distance yield sharp high-probability bounds.The paper also gives applications to machine learning and statistics.
2. PRELIMINARIES
The preliminaries set the compact Polish-space framework, define Wasserstein transport formulations, and position the paper relative to prior convergence-rate results. They emphasize both the geometric meaning of transport and the generality of the paper’s sharper bounds.
- Setting: The analysis assumes a compact metric space that is Polish, with all measures Borel and diam(X) ≤1 after rescaling.Compactness ensures finite diameter, while the normalization is made without loss of generality.
- Wasserstein distance: Wp is defined through the infimum transport cost over couplings whose marginals are the two input measures.This formulation gives Wasserstein distance its interpretation as the cost of moving mass between measures.
- Wasserstein distance: The Monge formulation instead minimizes over transport maps, but its infimum need not be attained in general.The map formulation provides a direct geometric interpretation of transporting mass.
- Wasserstein distance: W1 has a simpler dual representation over 1-Lipschitz functions, making it significantly easier to bound than general Wp.More general dual formulations exist for p ≠ 1 but are less convenient to manipulate.
- Prior work: Earlier work obtained rates based on covering numbers or Euclidean couplings, but those rates were not generally tight or easily extendable to arbitrary metric spaces.The paper follows related coupling ideas while tightening the analysis.
- Prior work: The paper separates expectation estimates from concentration bounds to derive tail guarantees for Wp(μ, ˆμn).This two-step strategy simplifies the development of high-probability bounds.
3. DYADIC TRANSPORT
The dyadic-transport framework bounds Wasserstein distance by comparing mass across recursively refined partitions. This yields sharper convergence rates, extending covering-based results to all Wasserstein orders in general metric spaces.
- Dyadic partitions: A dyadic partition recursively refines a set into cells whose diameters decrease geometrically with the partition level.The cells partition the set, and every finer cell is either contained in or disjoint from each coarser cell.
- Dyadic transport: Proposition 1 bounds Wp(μ, ν) using the masses that the two measures assign to cells in a dyadic partition.The bound applies to Borel probability measures supported on a common set.
- Dyadic transport: The upper bound is obtained by explicitly constructing a coupling between the two measures.The proposition is related to earlier partition-based and Euclidean transport arguments.
- Dyadic transport: The partition argument can be adapted to general transport costs by replacing cell-diameter control with a bound on the cost within each cell.This extends the framework beyond the metric cost formulation.
- Relation to prior work: Sharper analysis improves prior covering-number bounds and extends Dudley-type rates from p = 1 to every p ∈ [1, ∞).The paper identifies the earlier results as non-sharp in general and obtains bounds based on a smaller quantity.
4. ASYMPTOTIC UPPER AND LOWER BOUNDS
The section develops asymptotic upper and lower Wasserstein convergence bounds for all p, using measure dimensions defined through covering numbers and showing when these bounds are sharp.
- Main asymptotic bounds: For all p ∈ [1, ∞), the main theorem gives asymptotic upper and lower bounds governed by the Wasserstein dimensions.The lower bound applies even to any measure supported on at most n points, not only to the empirical measure.
- Dimension definitions: The authors define upper and lower Wasserstein dimensions using covering numbers that may ignore a small fraction of the measure’s mass.The framework uses ε-covering numbers and (ε, τ)-covering numbers, with τ controlling the ignored mass.
- Dimension definitions: The upper Wasserstein dimension is new, while the lower Wasserstein dimension extends an earlier notion and is justified by the main convergence theorem.The paper identifies the lower dimension with prior work and introduces the term “Wasserstein dimension” for these quantities.
- Dimension comparisons: The measure’s Minkowski and Hausdorff dimensions bound the Wasserstein dimensions, but these dimensions need not coincide in general.The inequalities can be strict; discrete measures provide simple examples where the dimensions differ.
- Sharpness and examples: The bounds are asymptotically sharp for broad classes of sufficiently regular measures whose relevant dimensions agree.Examples include measures absolutely continuous with respect to d-dimensional Hausdorff measure on regular sets.
5. FINITE-SAMPLE BOUNDS AND MULTISCALE BEHAVIOR
The section develops finite-sample Wasserstein bounds and shows that convergence can vary sharply across scales and sample sizes. Measures that are approximately discrete or low-dimensional can converge quickly initially, despite eventually exhibiting slower dimension-dependent rates.
- 5.1 Finite-sample behavior: The finite-sample analysis strengthens asymptotic bounds by controlling covering behavior beyond sufficiently small scales.The resulting bound removes the n^-1/2 term under stronger control over d_ε(µ, τ).
- 5.1 Finite-sample behavior: A measure can realize essentially any prescribed decreasing convergence rate, subject to mild regularity conditions on the rate sequence.The construction gives E[W_p(µ, µ̂_n)] ≥ Cn^-1/d_n while n^-1/d_n approximately follows the desired sequence δ_n.
- 5.2 Clusterable distributions: For mixtures of Gaussians, the fast finite-sample rate persists until n is large enough for the eventual dimension-dependent regime to dominate.Although the mixture is absolutely continuous, its mass is concentrated near finitely many mixture centers.
- 5.3 Approximately low-dimensional sets: Measures concentrated near low-dimensional sets can converge at n^-p/d until n is exponentially large in d, even when their ambient dimension is much larger.For an absolutely continuous measure on R^s with s ≫ d, the initial rate n^-p/d is faster than the limiting rate n^-p/s.
6. CONCENTRATION
The concentration analysis complements expectation bounds by showing that Wasserstein distance concentrates around its expectation on bounded metric spaces. This yields high-probability guarantees without dimension-dependent concentration deterioration.
- 6. CONCENTRATION: The analysis first bounds E[W_p(µ, µ̂_n)] and then uses concentration around that expectation to obtain sharp high-probability bounds.The expectation bounds come from earlier sections, while the concentration argument is standard and dimension-independent on bounded spaces.
- 6. CONCENTRATION: On bounded metric spaces, W_p(µ, µ̂_n) concentrates around its expectation independently of the dimension.The paper obtains this through a bounded-difference argument based on a dual formulation of Wasserstein distance.
- 6. CONCENTRATION: Kantorovich duality represents the Wasserstein quantity through bounded continuous test functions and permits the required bounded-difference analysis.When diam(X) ≤ 1, the dual functions can be chosen between 0 and 1.
7. APPLICATIONS
The applications connect Wasserstein convergence to numerical integration and clustering. The results show that empirical sampling is optimal for Lipschitz-function approximation and for k-means-type clustering in the stated regimes.
- 7.1 Numerical integration: The Lipschitz-function approximation problem is equivalent to controlling W_1 between the target measure and its empirical approximation.Lower bounds for measures supported on regular d-dimensional sets establish the corresponding optimality statement.
- 7.1 Numerical integration: For approximating all 1-Lipschitz functions, uniform-weight Monte Carlo sampling is asymptotically optimal for a wide class of measures.This contrasts with its asymptotic suboptimality when only a single function is integrated.
- 7.2 k-means clustering: For k-means, minimizing the clustering objective is equivalent to finding a measure supported on at most k points with small W_2 distance.A Voronoi partition of the support based on those points gives the resulting clustering.
- 7.2 k-means clustering: When d ≥ 4, clustering from k i.i.d. samples is asymptotically optimal and has concentration properties stronger than prior results imply.The empirical measure supplies the k-point approximation used for clustering.
8. CONCLUSION AND FUTURE WORK
The paper sharpens convergence-rate results for empirical measures and explains why approximately low-dimensional measures can converge faster despite high-dimensional worst cases. It leaves open whether alternative Wasserstein variants or sampling schemes can improve general rates.
- The results provide sharper asymptotic and finite-sample rates for empirical-measure convergence in Wasserstein distance.
- Measures that are intrinsically low dimensional, at least approximately, can have reasonably fast convergence rates even when the ambient metric space is high dimensional.
- Whether modified Wasserstein distances can converge faster in general remains open, including the possibility of better high-dimensional rates for entropically penalized versions.
- The work does not analyze empirical measures beyond the simple empirical measure ˆµn, although the authors conjecture reasonable sampling techniques may be asymptotically no worse.
A.1 Proof of Proposition 1
The proof bounds Wasserstein transport by moving mass between partition cells and then within cells. Recursively refining the partition improves the basic single-scale estimate.
- The transport plan first corrects mass discrepancies between partition cells, moving |µ(Qi) − ν(Qi)| into or out of each cell.
- After cell masses match, rearranging mass inside Qi costs at most diam(Qi), yielding a single-scale total-cost bound.
- Recursive partitioning replaces each cell-diameter estimate with finer-scale transport estimates and produces a refined bound after k∗ iterations.
- The formal proof represents residual measures across scales and combines couplings between scale-specific components with a final coupling of the remaining measures.
- The argument uses measure inequalities and auxiliary lemmas to obtain the final bound from the constructed transport decomposition.
A.2 Proof of Proposition 2
This proof establishes lower bounds by relating covering numbers and local mass estimates to the measure’s dimensional properties. The resulting inequalities identify the relevant dimension threshold.
- For d < dH(µ), a positive-mass compact set has sufficiently small local ball masses to constrain coverings at radius ε.
- The covering constraint implies d∗(µ) ≥ d, and since d < dH(µ) is arbitrary, dH(µ) ≤ d∗(µ).
- The proof constructs finite covers and nested partitions whose elements have controlled diameters and refinement structure.
- Each partition element has diameter at most 3^-k, and the finer partition Qk+1 refines Qk.
- The remaining inequality follows from absolute continuity: high-mass sets retain positive d-dimensional Hausdorff content and therefore require at least σε^-d covering balls.
- Taking limits in the covering estimate yields d∗(µ) ≥ d for the relevant dimension range.
A.5 Proof of Proposition 11
The proof constructs a multiscale measure on dyadic cubes whose covering numbers follow a prescribed sequence, then derives a lower bound for every n-point approximation. Auxiliary arguments establish the needed regularity and scale relations.
- The sequence Nk records the first power-of-two sample size at which the approximation scale δn reaches 2^-k, and consecutive Nk values have bounded ratios.
- A dyadic construction on [0,1]^m builds µ as a weak limit of measures supported uniformly on Nk−2 live cubes.
- Each live cube is refined into 2^m subcubes, retaining mass uniformly on the first Nk+1/Nk subcubes.
- The proof also establishes auxiliary coupling, partition, proportionality, and Gaussian-decomposition properties used in the multiscale argument.
- For Nk ≤ n < Nk+1, any measure supported on at most n points leaves more than half the mass farther than 2^-k−5 from its support.
- Every coupling therefore incurs a Wasserstein lower bound of at least 2^-6 n^-1/dn.
- The constructed measure and estimates satisfy the stated bounds for all c ≥ 5.
- The later partition arguments verify mass relations and coupling feasibility across dyadic scales.
B.4 Proof of Lemma A.4
The proof establishes a multiscale mass bound for small ℓ∞-balls and uses it to derive covering-number estimates and bounds involving the sequence δ_n.
- For balls aligned with the construction’s cubes, each live cube has mass exactly 1/N_{ℓ−2}, yielding the local mass bound.The same bound extends to arbitrary centers by partitioning the ball into translated pieces across intersecting cubes.
- A set with µ(S) ≥ 1/2 requires at least N_{ℓ−2}/2 balls of diameter 2^−ℓ to cover.
- If N_k ≤ n < N_{k+1}, monotonicity of δ_n gives bounds relating δ_n to powers of 2 indexed by k.The proof uses these inequalities to control the relevant covering scales.
- The covering estimates are combined across dyadic scales to prove the lemma’s stated claims.The proof separately derives bounds on n^−1/d_n and related quantities before combining them.