[edit]
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1367-1376, 2018.
Abstract
We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size n, up to accuracy ε. For the first algorithm, which is based on the celebrated Sinkhorn’s algorithm, we prove the complexity bound ˜O(n2ε2) arithmetic operations (˜O hides polylogarithmic factors (lnn)c, c>0). For the second one, which is based on our novel Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) algorithm, we prove the complexity bound ˜O(min arithmetic operations. Both bounds have better dependence on \varepsilon than the state-of-the-art result given by \widetilde{O}\left(\frac{n^2}{\varepsilon^3}\right). Our second algorithm not only has better dependence on \varepsilon in the complexity bound, but also is not specific to entropic regularization and can solve the OT problem with different regularizers.