Timezone: »
Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iterations, which also directly suggests a new greedy coordinate descent algorithm Greenkhorn with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice.
Author Information
Jason Altschuler (MIT)
Jonathan Niles-Weed (MIT)
Philippe Rigollet (MIT)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Spotlight: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration »
Tue. Dec 5th 07:30 -- 07:35 PM Room Hall C
More from the Same Authors
-
2021 Spotlight: Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent »
Jason Altschuler · Sinho Chewi · Patrik R Gerber · Austin Stromme -
2022 Poster: Variational inference via Wasserstein gradient flows »
Marc Lambert · Sinho Chewi · Francis Bach · Silvère Bonnabel · Philippe Rigollet -
2022 Poster: GULP: a prediction-based metric between representations »
Enric Boix-Adsera · Hannah Lawrence · George Stepaniants · Philippe Rigollet -
2021 : Entropic estimation of optimal transport maps »
Aram-Alexandre Pooladian · Jonathan Niles-Weed -
2021 Workshop: Optimal Transport and Machine Learning »
Jason Altschuler · Charlotte Bunne · Laetitia Chapel · Marco Cuturi · Rémi Flamary · Gabriel Peyré · Alexandra Suvorikova -
2021 Poster: Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent »
Jason Altschuler · Sinho Chewi · Patrik R Gerber · Austin Stromme -
2020 Poster: Exponential ergodicity of mirror-Langevin diffusions »
Sinho Chewi · Thibaut Le Gouic · Chen Lu · Tyler Maunu · Philippe Rigollet · Austin Stromme -
2020 Poster: SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence »
Sinho Chewi · Thibaut Le Gouic · Chen Lu · Tyler Maunu · Philippe Rigollet -
2019 : Jon Weed »
Jonathan Niles-Weed -
2019 Poster: Power analysis of knockoff filters for correlated designs »
Jingbo Liu · Philippe Rigollet -
2019 Poster: Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem »
Gonzalo Mena · Jonathan Niles-Weed -
2019 Spotlight: Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem »
Gonzalo Mena · Jonathan Niles-Weed -
2019 Poster: Massively scalable Sinkhorn distances via the Nyström method »
Jason Altschuler · Francis Bach · Alessandro Rudi · Jonathan Niles-Weed