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.
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:
- 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))$.
- 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