ICML 2019oral160 citations
On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
Tianyi Lin, Nhat Ho, Michael Jordan
Abstract
We provide theoretical analyses for two algorithms that solve the regularized optimal transport (OT) problem between two discrete probability measures with at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn algorithm, known as the
BibTeX
@InProceedings{pmlr-v97-lin19a,
title = {On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms},
author = {Lin, Tianyi and Ho, Nhat and Jordan, Michael},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {3982--3991},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/lin19a/lin19a.pdf},
url = {https://proceedings.mlr.press/v97/lin19a.html},
abstract = {We provide theoretical analyses for two algorithms that solve the regularized optimal transport (OT) problem between two discrete probability measures with at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn algorithm, known as the