Debiased Sinkhorn barycenters

Abstract

Entropy regularization in optimal transport (OT) has been the driver of many recent interests for Wasserstein metrics and barycenters in machine learning. It allows to keep the appealing geometrical properties of the unregularized Wasserstein distance while having a significantly lower complexity thanks to Sinkhorn's algorithm. However, entropy brings some inherent smoothing bias, resulting for example in blurred barycenters. This side effect has prompted an increasing temptation in the community to settle for a slower algorithm such as log-domain stabilized Sinkhorn which breaks the parallel structure that can be leveraged on GPUs, or even go back to unregularized OT. Here we show how this bias is tightly linked to the reference measure that defines the entropy regularizer and propose debiased Wasserstein barycenters that preserve the best of both worlds: fast Sinkhorn-like iterations without entropy smoothing. Theoretically, we prove that the entropic OT barycenter of univariate Gaussians is a Gaussian and quantify its variance bias. This result is obtained by extending the differentiability and convexity of entropic OT to sub-Gaussian measures with unbounded supports. Empirically, we illustrate the reduced blurring and the computational advantage on various applications.

arXiv commentICML 2020

References in corpus (7)

• Scikit-learn: Machine Learning in Python
• Fast Computation of Wasserstein Barycenters
• Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
• Smooth and Sparse Optimal Transport
• Scaling Algorithms for Unbalanced Transport Problems
• Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance
• Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem

Cited by in corpus (11)

• Entropic Optimal Transport between Unbalanced Gaussian Measures has a Closed Form
• Wasserstein barycenters are NP-hard to compute
• Unbalanced Multi-Marginal Optimal Transport
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Entropic regularization of Wasserstein distance between infinite-dimensional Gaussian measures and Gaussian processes
• Wasserstein barycenters can be computed in polynomial time in fixed dimension
• Conditional Wasserstein Barycenters and Interpolation/Extrapolation of Distributions
• Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
• Landmarks Augmentation with Manifold-Barycentric Oversampling
• On the Existence of Optimal Transport Gradient for Learning Generative Models
• Topological Node2vec: Enhanced Graph Embedding via Persistent Homology