Timezone: »

 
Poster
A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport
Arun Jambulapati · Aaron Sidford · Kevin Tian

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #74
in Algorithms -- Similarity and Distance Learning »
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 $\epsilon$ accuracy with $\tilde{O}(1/\epsilon)$ parallel depth and $\tilde{O}\left(n^2/\epsilon\right)$ 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 $\tilde{O}(\min(n^2 / \epsilon^2, n^{2.5} / \epsilon))$ \cite{DvurechenskyGK18, LinHJ19}. We obtain our results by a primal-dual extragradient method, motivated by recent theoretical improvements to maximum flow \cite{Sherman17}.
Keywords: Optimization · Algorithms; Algorithms -> Regression; Algorithms -> Similarity and Distance Learning; Optimization · Combinatorial Optimizatio
[ Paper]  [ Poster] 

Author Information

Arun Jambulapati (Stanford University)
Aaron Sidford (Stanford)
Kevin Tian (Stanford University)

More from the Same Authors