Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

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

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 $ε$-accuracy by adding an entropic regularization of order $ε$ 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 $ε^{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.

Introduction

Estimating the Wasserstein distance ($W_2$) between high-dimensional distributions is a fundamental challenge in machine learning, particularly for generative modeling and imaging. Despite its power, $W_2$ estimation suffers from the "curse of dimensionality," where error scales as $n^{-1/d}$, and high computational costs. While entropic regularization (Sinkhorn’s algorithm) offers a speedup, it introduces bias. Reducing this bias requires a very small regularization parameter $\lambda$, which in turn slows down convergence.

This paper proposes using the Sinkhorn divergence—a debiased version of entropic optimal transport—to break this trade-off. By allowing for much larger regularization parameters, the Sinkhorn divergence achieves significant computational speedups and improved accuracy for smooth densities.

Methods

The core approach replaces the standard regularized optimal transport (OT) cost $T_\lambda$ with the Sinkhorn divergence $S_\lambda$: $$S_\lambda(\mu, \nu) = T_\lambda(\mu, \nu) - \frac{1}{2} \left( T_\lambda(\mu, \mu) + T_\lambda(\nu, \nu) \right)$$ Subtracting the "self-OT" terms debiases the estimator. The authors analyze $S_\lambda$ using the dynamical formulation of OT (Benamou-Brenier formula) to show how it approximates the squared Wasserstein distance $W_2^2$.

Additionally, they introduce a Richardson extrapolation estimator ($R_\lambda$): $$R_\lambda = 2S_\lambda - S_{\sqrt{2}\lambda}$$ This technique combines estimates at different scales to cancel higher-order error terms, further improving precision.

Key Insights and Results

Improved Approximation and Speed

A key finding is that debiasing is not just for ensuring $S_\lambda(\mu, \mu) = 0$; it improves the approximation error from $O(\lambda \log(1/\lambda))$ to $O(\lambda^2)$. This allows setting $\lambda \approx \epsilon^{1/2}$ for a target accuracy $\epsilon$, whereas biased versions require $\lambda \approx \epsilon$. Since Sinkhorn complexity scales with $1/\lambda$, this yields a massive practical speedup, reducing operations from $O(\epsilon^{-2})$ to $O(\epsilon^{-1.5})$.

Refined Statistical Rates

The authors provide a tighter analysis of sample complexity. For $d > 4$, the error for the squared Wasserstein distance $W_2^2$ scales as $n^{-2/d}$.

Absolute error on $W_2$ showing different convergence rates for $\mu = \nu$ and $\mu \neq \nu$.
Absolute error on $W_2^2$ demonstrating the $n^{-2/d}$ convergence rate for both cases.

Numerical experiments on smooth elliptically contoured distributions and Gaussian densities confirm these rates. $S_\lambda$ and $R_\lambda$ consistently outperform the standard plug-in estimator, requiring fewer samples and less computation to achieve high precision in dual potentials.

Limitations and Future Work

The theoretical gains rely on the smoothness of the underlying densities. For discrete or non-smooth measures, the $O(\lambda^2)$ error rate may not hold. Furthermore, while Richardson extrapolation is powerful, its full justification requires high regularity (e.g., Gaussian cases). Future work includes extending this analysis to transport map estimation, which is vital for applications like domain adaptation.

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 $ε$-accuracy by adding an entropic regularization of order $ε$ 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 $ε^{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