Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm

Pavel Dvurechensky, Alexander Gasnikov, Alexey Kroshnin

We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size $n$, up to accuracy $\epsilon$. For the first…