On the Acceleration of the Sinkhorn and Greenkhorn Algorithms for Optimal Transport

Tianyi Lin, Nhat Ho, Michael I. Jordan

We propose and analyze a novel approach to accelerate the Sinkhorn and Greenkhorn algorithms for solving the entropic regularized optimal transport (OT) problems. Focusing on the discrete setting where the probability distributions have at most $n$ atoms, and letting $\varepsilon \in \left(0, 1\right)$ denote the tolerance, we introduce accelerated algorithms that have complexity bounds of $\widetilde{\mathcal{O}}\left(n^{7/3}\varepsilon^{-1}\right)$. This improves on the best known complexity bound of $\widetilde{\mathcal{O}} \left(n^2\varepsilon^{-2}\right)$ for the Sinkhorn and Greenkhorn algorithms in terms of $\varepsilon$ and that of $\widetilde{\mathcal{O}}\left(n^{5/2}\varepsilon^{-1}\right)$ for the practical accelerated first-order primal-dual algorithms in terms of $n$. We provide an extensive experimental comparison on both synthetic and real datasets to explore the relative advantages of the new algorithms.

Knowledge Graph



Sign up or login to leave a comment