Central limit theorems for semi-discrete Wasserstein distances

Eustasio del Barrio, Alberto González-Sanz, Jean–Michel LoubesBernoulli 2023 · DOI

TL;DR

This paper introduces new theoretical tools to understand the behavior of optimal transport costs when one of the probability distributions is discrete and the other is continuous. They establish Central Limit Theorems (CLTs) for these "semi-discrete" settings, showing that the error in estimating the true transport cost converges to a Gaussian process. This work is significant because it provides a theoretical foundation for using optimal transport in machine learning and statistics, particularly in scenarios where exact computations are challenging, and it offers a way to avoid the "curse of dimensionality" for the discrete distribution.

What Problem Does This Paper Address?

Comparing probability distributions is a fundamental task in many fields, from statistics and machine learning to physics. Optimal transport (OT) provides a powerful framework for this comparison by finding the most efficient way to "move" mass from one distribution to another, minimizing a cost function. The Wasserstein distance, derived from OT, is a popular metric for this purpose. However, computing these distances exactly is often computationally intractable, especially in high dimensions.

A common approach is to use empirical distributions (samples) to approximate the true distributions. While CLTs exist for the empirical Wasserstein distance between two discrete distributions, the case where one distribution is discrete and the other is continuous (semi-discrete OT) has been less understood, particularly regarding the asymptotic behavior of the estimated transport cost. This paper aims to fill this gap by providing CLTs for semi-discrete optimal transport costs and their potentials, offering theoretical guarantees and insights into their statistical properties.

Methods

The authors leverage the dual formulation of the optimal transport problem, which involves maximizing a function over potentials. They extend existing results on CLTs for optimal transport by employing techniques related to the Hadamard differentiability of functionals. Specifically, they analyze the asymptotic distribution of the empirical optimal transport cost in three scenarios:

  1. One sample case for P: When the discrete distribution P is approximated by its empirical version $P_n$, and Q is a continuous distribution.
  2. One sample case for Q: When the continuous distribution Q is approximated by its empirical version $Q_m$, and P is a discrete distribution.
  3. Two sample case: When both distributions are approximated by their empirical versions.

A key technical contribution is the development of a new proof that handles the semi-discrete setting without strong assumptions on the continuous distribution Q. They also investigate the behavior of optimal transport potentials, providing the first CLT for these potentials in a general dimension. The proofs involve intricate analysis of Gaussian processes and their suprema, as well as the application of the delta-method.

Datasets

The paper does not introduce new datasets. Instead, it uses theoretical probability distributions for simulations to illustrate the findings. The simulations involve:

  • A discrete distribution P supported on a finite set of points in $\mathbb{R}^d$.
  • Continuous distributions Q, including a uniform distribution on the unit interval and a product of uniform and Gaussian distributions.

Key Insights and Ideas

  • CLT for Semi-Discrete OT: The paper establishes that the empirical optimal transport cost in the semi-discrete setting converges in distribution to the supremum of a Gaussian process. This is a significant theoretical result that provides statistical guarantees for estimation.
  • Avoiding the Curse of Dimensionality (for P): For a fixed number of points $N$ in the discrete distribution P, the "curse of dimensionality" is avoided. This means that the statistical error does not grow with the dimension of the space, which is a major advantage for applications.
  • CLT for Optimal Transport Potentials: For the first time, a CLT is derived for the optimal transport potentials in the semi-discrete setting. This is crucial for understanding the statistical properties of the dual solutions.
  • Trade-off in Estimation: The paper highlights a trade-off between the sample size ($m$) of the continuous distribution and the number of points ($N$) in the discrete distribution when estimating the Wasserstein distance.
  • Bootstrap Consistency: The authors discuss the conditions under which classical bootstrap procedures are consistent for approximating the variance of the estimated transport cost, particularly when the dual problem has a unique solution.

Key Results

  • Theorem 2.4: Provides the main CLT for the empirical semi-discrete optimal transport cost in three scenarios (one sample for P, one sample for Q, and two samples). The limit is shown to be the supremum of a Gaussian process.
  • Theorem 2.10: Derives an upper bound on the expected difference between the true 1-Wasserstein distance and its semi-discrete empirical estimate. This bound shows a dependence on $N$ and $m$, illustrating the trade-off mentioned above.
  • Theorem 3.2: Under specific regularity conditions on the cost function and the continuous distribution Q (e.g., Q is absolutely continuous with a connected support), the Gaussian process in the CLT simplifies to a centered Gaussian random variable.
  • Theorem 4.2: Establishes a CLT for the empirical optimal transport potentials in the semi-discrete setting, showing their convergence to a multivariate Gaussian distribution.

Limitations and Future Work

  • Assumptions on Q: While the paper aims to relax assumptions on Q, some results (like Theorem 3.2) still require Q to be absolutely continuous with respect to the Lebesgue measure and have a connected support. The authors mention that their results can be extended to cases where Q is not necessarily connected.
  • Curse of Dimensionality (for Q): The paper notes that for the continuous distribution Q, the "curse of dimensionality" can still be an issue if Q is approximated by a discrete distribution with a number of points $N$ that grows exponentially with the dimension.
  • Generalization to Manifolds: The paper briefly mentions extending the study to semi-discrete OT on manifolds, suggesting this as a direction for future work.
  • Bootstrap Consistency: While the paper discusses bootstrap consistency, its application is more straightforward when the optimal transport potential is unique. Further investigation into bootstrap for more general cases might be warranted.

Summary updated

Abstract

We prove a Central Limit Theorem for the empirical optimal transport cost, nmn+m{Tc(Pn,Qm)−Tc(P,Q)}, in the semi-discrete case, i.e when the distribution P is supported in N points, but without assumptions on Q. We show that the asymptotic distribution is the sup of a centered Gaussian process, which is Gaussian under some additional conditions on the probability Q and on the cost. Such results imply the central limit theorem for the p-Wassertein distance, for p≥1. This means that, for fixed N, the curse of dimensionality is avoided. To better understand the influence of such N, we provide bounds of E|Wpp(P,Qm)−Wpp(P,Q)| depending on m and N. Finally, the semi-discrete framework provides a control on the second derivative of the dual formulation, which yields the first central limit theorem for the optimal transport potentials and Laguerre cells. The results are supported by simulations that help to visualize the given limits and bounds. We analyse also the cases where classical bootstrap works.
BibTeX
@inproceedings{barrio2023central,
  author = {Eustasio del Barrio and Alberto González-Sanz and Jean–Michel Loubes},
  title = {{Central limit theorems for semi-discrete Wasserstein distances}},
  booktitle = {Bernoulli},
  year = {2023},
  doi = {10.3150/23-bej1608},
}
Figure