Faster Wasserstein Distance Estimation with the Sinkhorn Divergence - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (1.02 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02867271 , version 1 (13-06-2020)
hal-02867271 , version 2 (28-10-2020)

Identifiants

Citer

Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, Gabriel Peyré. Faster Wasserstein Distance Estimation with the Sinkhorn Divergence. NeurIPS 2020, Dec 2020, Vancouver, Canada. pp.2257-2269. ⟨hal-02867271v2⟩
713 Consultations
993 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More