Abstract

Optimal transportation, or computing the Wasserstein or “earth mover’s” distance between two n-dimensional distributions, is a fundamental primitive which arises in many learning and statistical settings. We give an algorithm which solves
the problem to additive  accuracy with parallel depth and / work. [BJKS18, Qua19] obtained this runtime through reductions to positive linear programming and matrix scaling. However, these reduction-based algorithms use subroutines which may be impractical due to requiring solvers for second-order iterations (matrix scaling) or non-parallelizability (positive LP). Our methods match the previous-best work bounds by [BJKS18, Qua19] while either improving parallelization or removing the need for linear system solves, and improve upon the previous best first-order methods running in time [DGK18, LHJ19]. We obtain our results by a primal-dual extragradient method, motivated by recent theoretical improvements to maximum flow [She17].