A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport
Authors: Arun Jambulapati, Aaron Sidford, Kevin Tian
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We give an algorithm which solves the problem to additive ϵ accuracy with O(1/ϵ) parallel depth and O n2/ϵ work. 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 O(min(n2/ϵ2, n2.5/ϵ)) [DGK18, LHJ19]. We obtain our results by a primal-dual extragradient method, motivated by recent theoretical improvements to maximum flow [She17]. We show experiments illustrating the potential of our algorithm to be useful in practice, by considering its performance on computing optimal transport distances on the MNIST dataset and comparing against algorithms in the literature including APDAMD [LHJ19] and Sinkhorn iteration. |
| Researcher Affiliation | Academia | Arun Jambulapati, Aaron Sidford, and Kevin Tian Stanford University {jmblpati,sidford,kjtian}@stanford.edu |
| Pseudocode | Yes | Algorithm 1 w = Dual-Extrapolation(κ, r, g, T): Dual extrapolation with area-convex r. Algorithm 2 ˆX = Rounding( X, r, c): Rounding to feasible polytope |
| Open Source Code | No | The paper does not provide a direct link or explicit statement regarding the public release of the source code for the described methodology. |
| Open Datasets | Yes | We show experiments illustrating the potential of our algorithm to be useful in practice, by considering its performance on computing optimal transport distances on the MNIST dataset |
| Dataset Splits | No | The paper mentions using the MNIST dataset and '20 randomly chosen MNIST digit pairs' for experiments, but it does not specify explicit training, validation, or test dataset splits or how the data was partitioned. |
| Hardware Specification | No | The paper does not provide specific details about the hardware (e.g., GPU/CPU models, memory) used to run the experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers (e.g., programming languages, libraries, or solvers with specific versions). |
| Experiment Setup | Yes | For the experiments shown in Section 5, we use a single regularizer value across all instances, which is 106. We use 1/t as the step size at iteration t. For the mirror prox experiments, we set the step size 0.5/L and the regularizer to 1. For Sinkhorn, we set regularizer 103 and use the standard iteration for 1000 iterations. |