# Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

arXiv: https://arxiv.org/abs/2006.08172 · HTML: https://mlsanity.com/paper/2006.08172/

## Key facts

- Cited by 73 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 73)

- [Solving Schr"odinger Bridges via Maximum Likelihood](https://mlsanity.com/paper/2106.02081/) (2021)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Learning Diffusion Priors from Observations by Expectation Maximization](https://mlsanity.com/paper/2405.13712/) (2024)
- [The Monge Gap: A Regularizer to Learn All Transport Maps](https://mlsanity.com/paper/2302.04953/) (2023)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [PTaRL: Prototype-based Tabular Representation Learning via Space Calibration](https://mlsanity.com/paper/2407.05364/) (2024)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Bending Graphs: Hierarchical Shape Matching using Gated Optimal Transport](https://mlsanity.com/paper/2202.01537/) (2022)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [An improved central limit theorem and fast convergence rates for entropic transportation costs](https://mlsanity.com/paper/2204.09105/) (2022)
- [Rethinking Initialization of the Sinkhorn Algorithm](https://mlsanity.com/paper/2206.07630/) (2022)
- [Transferability-Guided Cross-Domain Cross-Task Transfer Learning](https://mlsanity.com/paper/2207.05510/) (2022)
- [Adaptive Distribution Calibration for Few-Shot Learning with Hierarchical Optimal Transport](https://mlsanity.com/paper/2210.04144/) (2022)
- [Near-optimal estimation of smooth transport maps with kernel sums-of-squares](https://mlsanity.com/paper/2112.01907/) (2021)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Flow Factorized Representation Learning](https://mlsanity.com/paper/2309.13167/) (2023)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Measure Estimation in the Barycentric Coding Model](https://mlsanity.com/paper/2201.12195/) (2022)
- [Linear Optimal Partial Transport Embedding](https://mlsanity.com/paper/2302.03232/) (2023)
- [Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2311.04041/) (2023)
- [Structured Transforms Across Spaces with Cost-Regularized Optimal Transport](https://mlsanity.com/paper/2311.05788/) (2023)
- [Plug-in estimation of Schr"odinger bridges](https://mlsanity.com/paper/2408.11686/) (2024)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Proximity Matters: Local Proximity Enhanced Balancing for Treatment Effect Estimation](https://mlsanity.com/paper/2407.01111/) (2024)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Unsupervised Ground Metric Learning using Wasserstein Singular Vectors](https://mlsanity.com/paper/2102.06278/) (2021)
- [Differentially Private Post-Processing for Fair Regression](https://mlsanity.com/paper/2405.04034/) (2024)
- [Consistency of Neural Causal Partial Identification](https://mlsanity.com/paper/2405.15673/) (2024)

## Abstract (arXiv)

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.