Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

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.

References in corpus (11)

• Learning with a Wasserstein Loss
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Learning in Implicit Generative Models
• Sample Complexity of Sinkhorn divergences
• Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
• Entropic Optimal Transport between Unbalanced Gaussian Measures has a Closed Form
• Minimax Confidence Intervals for the Sliced Wasserstein Distance
• Minimax Distribution Estimation in Wasserstein Distance
• Benamou-Brenier and duality formulas for the entropic cost on $RC{D}^{\ast }(K,N)$ spaces
• A Graph Theoretic Additive Approximation of Optimal Transport
• On the Effectiveness of Richardson Extrapolation in Machine Learning

Cited by in corpus (9)

• Sinkhorn Divergences for Unbalanced Optimal Transport
• Solving Schrödinger Bridges via Maximum Likelihood
• Asymptotics for semi-discrete entropic optimal transport
• Sharp Convergence Rates for Empirical Optimal Transport with Smooth Costs
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Automatic Differentiation-based Full Waveform Inversion with Flexible Workflows
• Martingale Methods for Sequential Estimation of Convex Functionals and Divergences
• Entropic estimation of optimal transport maps
• Wasserstein Conditional Independence Testing