Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

Lénaïc Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, Gabriel Peyré

Estimating the distance between two probability distributions is a fundamental task in machine learning, essential for everything from training generative models to performing two-sample tests. The Wasserstein distance (or Optimal Transport distance) is widely considered the gold standard for this task because it accounts for the underlying geometry of the space. However, it suffers from two major Achilles' heels: it is computationally expensive to calculate and falls victim to the "curse of dimensionality" in high-dimensional spaces.

In this paper, Lénaïc Chizat and colleagues demonstrate that by using the Sinkhorn divergence—a "debiased" version of entropic optimal transport—we can estimate Wasserstein distances significantly faster and more accurately than previously thought possible. By leveraging this divergence, the authors show that one can use much higher regularization levels, leading to massive computational speedups and improved statistical efficiency for smooth probability densities.

The Computational and Statistical Bottleneck

When we only have samples from two distributions, $\mu$ and $\nu$, we typically estimate the Wasserstein distance using a "plug-in" estimator: we solve the optimal transport problem directly between the empirical samples. Unfortunately, this estimator's error scales poorly, specifically as $n^{-2/d}$, where $n$ is the number of samples and $d$ is the dimension. In high dimensions, this means an astronomical number of samples is required to achieve a reliable estimate.

Absolute error of the standard plug-in estimator on the squared Wasserstein distance, demonstrating the $n^{-2/d}$ scaling.

To solve the transport problem numerically, researchers often introduce entropic regularization, which makes the problem solvable via the highly efficient Sinkhorn algorithm. But there is a catch: the regularization parameter $\lambda$ introduces a bias. To get an accurate estimate of the true Wasserstein distance, $\lambda$ must be kept very small. However, as $\lambda$ approaches zero, the Sinkhorn algorithm becomes extremely slow, converging in $O(1/\lambda)$ or worse.

Debiasing with the Sinkhorn Divergence

To break this trade-off between speed and accuracy, the authors propose using the Sinkhorn divergence ($S_\lambda$) as an estimator for the squared Wasserstein distance ($W_2^2$). The Sinkhorn divergence is defined as:

$$S_\lambda(\mu, \nu) = T_\lambda(\mu, \nu) - \frac{1}{2} [T_\lambda(\mu, \mu) + T_\lambda(\nu, \nu)]$$

where $T_\lambda$ is the standard entropy-regularized transport cost.

Previously, the self-correction terms in the Sinkhorn divergence were primarily viewed as a mathematical trick to ensure the distance is non-negative and that $S_\lambda(\mu, \mu) = 0$. This paper reveals their true power: they actively cancel out the first-order bias of the regularization.

The key methodological contributions include:

  1. Refined Approximation Bounds: Using a dynamical formulation of optimal transport, the authors prove that $S_\lambda$ approximates $W_2^2$ with an error of $O(\lambda^2)$. This is a massive improvement over the uncorrected $T_\lambda$, which suffers from a much larger bias of $O(\lambda \log(1/\lambda))$.
  2. Richardson Extrapolation: They introduce an even more refined estimator ($R_\lambda$) by combining $S_\lambda$ at two different scales ($\lambda$ and $\sqrt{2}\lambda$). This cancels out the leading error term, potentially reaching an impressive $O(\lambda^4)$ accuracy.

The "Speedup Loophole" and Key Results

Because $S_\lambda$ is significantly more accurate for a given $\lambda$, practitioners can afford to use a much larger $\lambda$ than they would with the standard plug-in estimator. Since the Sinkhorn algorithm's computational complexity is inversely proportional to $\lambda$, this translates directly into a massive computational speedup without sacrificing accuracy.

Theoretical and empirical results highlight this efficiency:

  • Computational Complexity: To reach a target accuracy of $\epsilon$, the proposed $S_\lambda$ estimator requires significantly fewer operations. For example, on a grid, $S_\lambda$ achieves $\epsilon$-accuracy in $O(\epsilon^{-(3d/2 + 1.5)})$ time, compared to a sluggish $O(\epsilon^{-(2d+2)})$ for the standard regularized cost.
  • Numerical Validation: In 5D synthetic experiments (using smooth elliptically contoured distributions and Gaussians), both $S_\lambda$ and $R_\lambda$ reached target accuracy levels with far fewer samples and much larger regularization parameters than the biased $T_\lambda$ estimator.
  • Grid Stability: The authors proved that entropic regularization increases stability under discretization. They showed an error of $O(h^2)$ (where $h$ is grid size) for the regularized problem, which is strictly better than the $O(h)$ typically expected for the unregularized case.

Limitations and Future Directions

While the Sinkhorn divergence offers a robust way to mitigate the curse of dimensionality, it does not entirely break it. Furthermore, the theoretical benefits rely heavily on the distributions having smooth densities (specifically, finite Fisher information). If the distributions are truly discrete or have sharp boundaries, the $O(\lambda^2)$ error bound may not hold.

Additionally, while the paper proves that $\lambda$ can be larger, choosing the optimal $\lambda$ for a specific, real-world dataset still requires tuning or cross-validation. Finally, the current analysis is specific to the squared $L_2$ cost; extending these refined bounds to other costs or different types of divergences remains an exciting open question for future research.

Summary updated

Abstract

The squared Wasserstein distance is a natural quantity to compare probability distributions in a non-parametric setting. This quantity is usually estimated with the plug-in estimator, defined via a discrete optimal transport problem which can be solved to $\epsilon$-accuracy by adding an entropic regularization of order $\epsilon$ and using for instance Sinkhorn's algorithm. In this work, we propose instead to estimate it with the Sinkhorn divergence, which is also built on entropic regularization but includes debiasing terms. We show that, for smooth densities, this estimator has a comparable sample complexity but allows higher regularization levels, of order $\epsilon^{1/2}$, which leads to improved computational complexity bounds and a strong speedup in practice. Our theoretical analysis covers the case of both randomly sampled densities and deterministic discretizations on uniform grids. We also propose and analyze an estimator based on Richardson extrapolation of the Sinkhorn divergence which enjoys improved statistical and computational efficiency guarantees, under a condition on the regularity of the approximation error, which is in particular satisfied for Gaussian densities. We finally demonstrate the efficiency of the proposed estimators with numerical experiments.
BibTeX
@inproceedings{chizat2020faster,
  author = {Lénaïc Chizat and Pierre Roussillon and Flavien Léger and François-Xavier Vialard and Gabriel Peyré},
  title = {{Faster Wasserstein Distance Estimation with the Sinkhorn Divergence}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=W1LtU4RgakF},
}
Figure