Loading [MathJax]/jax/output/CommonHTML/jax.js
Skip to yearly menu bar Skip to main content


Poster

A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport

Arun Jambulapati · Aaron Sidford · Kevin Tian

East Exhibition Hall B, C #74

Keywords: [ Optimization ] [ Algorithms; Algorithms -> Regression; Algorithms -> Similarity and Distance Learning; Optimization ] [ Combinatorial Optimizatio ]


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 ˜O(1/ϵ) parallel depth and ˜O(n2/ϵ) work. \cite{BlanchetJKS18, Quanrud19} 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 \cite{BlanchetJKS18, Quanrud19} while either improving parallelization or removing the need for linear system solves, and improve upon the previous best first-order methods running in time ˜O(min(n2/ϵ2,n2.5/ϵ)) \cite{DvurechenskyGK18, LinHJ19}. We obtain our results by a primal-dual extragradient method, motivated by recent theoretical improvements to maximum flow \cite{Sherman17}.

Live content is unavailable. Log in and register to view live content