# A Direct tildeO(1/ε) Iteration Parallel Algorithm for Optimal Transport

arXiv: https://arxiv.org/abs/1906.00618 · HTML: https://mlsanity.com/paper/1906.00618/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 4 of 4)

- [Optimal Transport for Treatment Effect Estimation](https://mlsanity.com/paper/2310.18286/) (2023)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [Efficient Optimal Transport Algorithm by Accelerated Gradient descent](https://mlsanity.com/paper/2104.05802/) (2021)

## Abstract (arXiv)

Optimal transportation, or computing the Wasserstein or ``earth mover's'' distance between two distributions, is a fundamental primitive which arises in many learning and statistical settings. We give an algorithm which solves this problem to additive ε with tildeO(1/ε) parallel depth, and tildeOleft(n2/εright) work. Barring a breakthrough on a long-standing algorithmic open problem, this is optimal for first-order methods. Blanchet et. al. '18, Quanrud '19 obtained similar runtimes through reductions to positive linear programming and matrix scaling. However, these reduction-based algorithms use complicated subroutines which may be deemed impractical due to requiring solvers for second-order iterations (matrix scaling) or non-parallelizability (positive LP). The fastest practical algorithms run in time tildeO(min(n2 / ε2, n2.5 / ε)) (Dvurechensky et. al. '18, Lin et. al. '19). We bridge this gap by providing a parallel, first-order, tildeO(1/ε) iteration algorithm without worse dependence on dimension, and provide preliminary experimental evidence that our algorithm may enjoy improved practical performance. We obtain this runtime via a primal-dual extragradient method, motivated by recent theoretical improvements to maximum flow (Sherman '17).