Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
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.
Dedicated to the memory of Michael B. Cohen
In this paper the authors discuss entropic regularized optimal transport with a focus on the computational complexity of its resolution. Their main contribution is a result giving relation between accuracy (in term of error wrt the constraint) and number of iterations for Sinkhorn (and their) algorithm. It show that a given accuracy can be obtained with a complexity near linear to the size of the problem which is impressive.
Using the in-depth computational study the authors propose a new algorithm with the same theoretical property of Sinkhorn but more efficient in practice. very small numerical experiment suggest that the propose GreenKhorn method works in practice better than Sinkhorn.
This paper is very interesting and propose a theoretical computational study that can be of huge help to the community. It also explain why the recent entropic regularization works so well in practice and when it shouldn't be used.  The new Greedy Sinkhorn algorithm is very interesting and seem to work very well in practice. I still have a few comment that I would like to be addressed in the rebuttal before giving a definite rating.
Comments:
- The whole paper seem a bit of a mess with theorems given between definitions and proofs scattered everywhere except below the theorem. I understand the the authors wanted to tell a story but in practice it makes the paper more difficult to read. Beginning with theorem 1 is ok and finishing with its proof is also OK. But the remaining should be done in classical math stuff theorem 2 followed by proof then theorem 3 that uses theorem 2 and so on.
- One of the take home message from theorem 1 is actually not that good: if you want to decrease the l1 error on the constraint by 10, you will need to perform 10^3=1000 times more iterations. this also explain why sinkhorn is known to converge rather quickly to a good enough solution but might take forever to actually converge to numerical precision. It should have been discussed a bit more. Actually I would really like to see numerical experiments that illustrate the O(1/k^{1/3}) convergence of the error.
- The propose Greenkhron is very interesting but it has strong similarity with the stochastic sinkhorn of [GCPB16]. My opinion is that the proposed method is better because it basically update only the variable that violate the most the constraints whereas stochastic will spend time updating already valid constraints since all variables are updated. Still good scientific experiments require the authors to provide these comparison and the fact that the code for [GCPB16] is available online gives the authors no excuse.