Sample complexity of optimal transport barycenters with discrete support

Léo Portales, Edouard Pauwels, Elsa CazellesarXiv 2025 · DOI · arXiv

TL;DR

This paper establishes new statistical guarantees for "sparse" optimal transport barycenters—essentially the geometric mean of several data distributions. The authors prove that the error in calculating these barycenters from samples scales at a rate of $O(\sqrt{N/n})$, where $N$ is the number of points in the barycenter and $n$ is the number of samples, providing a dimension-independent convergence rate that covers Wasserstein, Sinkhorn, and Sliced-Wasserstein distances.

What Problem Does This Paper Address?

Optimal Transport (OT) barycenters are a powerful way to find the "average" of multiple probability distributions, preserving their geometric structure (unlike a simple pixel-wise average of images, which just gets blurry). However, computing these is hard. In practice, we use empirical approximations: we take $n$ samples from our target distributions and restrict our resulting barycenter to a "sparse" support of $N$ points to keep it computationally tractable.

The big question is: How many samples ($n$) do we need to ensure our empirical sparse barycenter is close to the true population barycenter?

Standard OT results often suffer from the "curse of dimensionality," where the number of samples needed grows exponentially with the dimension $d$. This paper investigates whether restricting the barycenter to a discrete, sparse support ($N$ points) allows us to bypass this curse and achieve faster, more reliable convergence.

Methods

The authors employ tools from empirical risk minimization and empirical process theory. Their approach relies on the dual formulation of optimal transport.

  1. Dual Analysis: Instead of looking at the complex primal problem of moving mass, they look at the dual variables (potentials). They prove that these dual variables remain bounded even as the support of the measures changes.
  2. Covering Numbers: They calculate "covering numbers"—a measure of the complexity of the space of functions associated with the OT dual problem.
  3. Uniform Convergence: By bounding these covering numbers, they derive uniform generalization bounds. This means the error bound holds simultaneously for all possible sparse barycenters you might pick, which is a much stronger guarantee than point-wise convergence.

The analysis is comprehensive, covering several popular OT flavors:

  • Standard Wasserstein ($W_p$): The classic "earth mover's" distance.
  • Sinkhorn Divergences ($W_{\epsilon,p}$): An entropically regularized version that is much faster to compute.
  • Sliced-Wasserstein ($SW_p$): A version that projects high-dimensional data onto 1D lines to simplify calculations.

Datasets

As a theoretical paper, it does not introduce a new large-scale benchmark. Instead, the authors use synthetic Gaussian distributions to validate their theoretical bounds:

  • Target Measures: $L=3$ Gaussian distributions in 2D and 6D.
  • Parameters: They varied the sample size $n$ (from 1,000 to 10,000) and the sparsity $N$ (from 10 to 500).
  • Tools: Experiments were implemented in Python using the POT (Python Optimal Transport) library.

Key Insights and Ideas

  • Bypassing the Curse of Dimensionality: The most significant "aha moment" is that the statistical rate $O(1/\sqrt{n})$ is independent of the ambient dimension $d$. While the constants in the formula might still depend on $d$, the way the error shrinks as you add more samples does not get worse in high dimensions.
  • Sparsity as a Regularizer: The constraint that the barycenter must have only $N$ points acts as a form of regularization. The "curse of dimensionality" is essentially "hidden" within this sparsity level $N$.
  • Unified Framework: The paper shows that K-means clustering is actually just a special case of this framework (where you have only one target measure and use the $W_2^2$ distance). Their results actually improve upon some existing K-means bounds by a factor of $\sqrt{\log N}$.
  • Uniformity over $L$: The bounds are uniform with respect to the number of target measures ($L$), meaning the "average" doesn't get statistically harder to estimate just because you are averaging more distributions.

Key Results

  • Generalization Bound: The main theorem (Theorem 3.1) proves that the expected difference between the empirical barycenter cost and the true population cost is at most $C \sqrt{N/n}$.
  • Numerical Confirmation: The experiments (Figure 1) perfectly match the $1/\sqrt{n}$ theoretical slope in log-log plots, confirming that the theory holds in practice for both standard and Sinkhorn barycenters.
  • Optimality: For the specific case of the 2-Wasserstein distance, the authors provide a lower bound, showing that their $O(1/\sqrt{n})$ rate is essentially the best one can hope for without further assumptions.

Limitations and Future Work

  • Tightness of $N$: While the $1/\sqrt{n}$ rate is optimal, there is still a gap in the dependency on the sparsity $N$. The upper bound suggests a linear dependency on $N$, while lower bounds suggest it might be slightly better ($N^{1-4/d}$).
  • Sinkhorn Constants: For Sinkhorn divergences, while the rate is dimension-independent, the constants still have an exponential dependence on dimension. Finding ways to mitigate this remains an open challenge.
  • Sliced OT Optimality: The authors note that investigating the absolute optimality of the bounds for Sliced-Wasserstein and max-Sliced Wasserstein distances is a task for future research.

Summary updated

Abstract

Computational implementation of optimal transport barycenters for a set of target probability measures requires a form of approximation, a widespread solution being empirical approximation of measures. We provide an $O(\sqrt{N/n})$ statistical generalization bounds for the empirical sparse optimal transport barycenters problem, where $N$ is the maximum cardinality of the barycenter (sparse support) and $n$ is the sample size of the target measures empirical approximation. Our analysis includes various optimal transport divergences including Wasserstein, Sinkhorn and Sliced-Wasserstein. We discuss the application of our result to specific settings including K-means, constrained K-means, free and fixed support Wasserstein barycenters.
BibTeX
@misc{portales2025sample,
  author = {Léo Portales and Edouard Pauwels and Elsa Cazelles},
  title = {{Sample complexity of optimal transport barycenters with discrete support}},
  year = {2025},
  eprint = {2505.21274},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.21274},
  howpublished = {arXiv},
}
Figure