# Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm

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

## Key facts

- Cited by 112 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2018.

## Built on by (most cited first, 30 of 112)

- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Diffusion Bridge Mixture Transports, Schr"odinger Bridge Problems and Generative Modeling](https://mlsanity.com/paper/2304.00917/) (2023)
- [Optimal Flow Matching: Learning Straight Trajectories in Just One Step](https://mlsanity.com/paper/2403.13117/) (2024)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Training neural operators to preserve invariant measures of chaotic attractors](https://mlsanity.com/paper/2306.01187/) (2023)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [Optimal Transport for Treatment Effect Estimation](https://mlsanity.com/paper/2310.18286/) (2023)
- [Transformed Distribution Matching for Missing Value Imputation](https://mlsanity.com/paper/2302.10363/) (2023)
- [Trajectory Inference via Mean-field Langevin in Path Space](https://mlsanity.com/paper/2205.07146/) (2022)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Novel Class Discovery for Long-tailed Recognition](https://mlsanity.com/paper/2308.02989/) (2023)
- [Light Schr"odinger Bridge](https://mlsanity.com/paper/2310.01174/) (2023)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Unified Mask Embedding and Correspondence Learning for Self-Supervised Video Segmentation](https://mlsanity.com/paper/2303.10100/) (2023)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Adaptive Distribution Calibration for Few-Shot Learning with Hierarchical Optimal Transport](https://mlsanity.com/paper/2210.04144/) (2022)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Flow Matching with Semidiscrete Couplings](https://mlsanity.com/paper/2509.25519/) (2025)
- [Entropic Gromov-Wasserstein between Gaussian Distributions](https://mlsanity.com/paper/2108.10961/) (2021)
- [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022)
- [Discovering Conservation Laws using Optimal Transport and Manifold Learning](https://mlsanity.com/paper/2208.14995/) (2022)
- [A relaxed proximal gradient descent algorithm for convergent plug-and-play with proximal denoiser](https://mlsanity.com/paper/2301.13731/) (2023)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Entropy Regularized Optimal Transport Independence Criterion](https://mlsanity.com/paper/2112.15265/) (2021)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Fourier Sliced-Wasserstein Embedding for Multisets and Measures](https://mlsanity.com/paper/2504.02544/) (2025)

## Abstract (arXiv)

We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size n, up to accuracy varepsilon. For the first algorithm, which is based on the celebrated Sinkhorn's algorithm, we prove the complexity bound widetildeOleft(n2/varepsilon2right) arithmetic operations. For the second one, which is based on our novel Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) algorithm, we prove the complexity bound widetildeOleft(minleftn9/4/varepsilon, n2/varepsilon2 rightright) arithmetic operations. Both bounds have better dependence on varepsilon than the state-of-the-art result given by widetildeOleft(n2/varepsilon3right). Our second algorithm not only has better dependence on varepsilon in the complexity bound, but also is not specific to entropic regularization and can solve the OT problem with different regularizers.