# On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms

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

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jan 2019.

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

- [Density-aware Chamfer Distance as a Comprehensive Metric for Point Cloud Completion](https://mlsanity.com/paper/2111.12702/) (2021)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Point-set Distances for Learning Representations of 3D Point Clouds](https://mlsanity.com/paper/2102.04014/) (2021)
- [Understanding DDPM Latent Codes Through Optimal Transport](https://mlsanity.com/paper/2202.07477/) (2022)
- [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)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Revisiting Sliced Wasserstein on Images: From Vectorization to Convolution](https://mlsanity.com/paper/2204.01188/) (2022)
- [Hierarchical Sliced Wasserstein Distance](https://mlsanity.com/paper/2209.13570/) (2022)
- [Amortized Projection Optimization for Sliced Wasserstein Generative Models](https://mlsanity.com/paper/2203.13417/) (2022)
- [On Transportation of Mini-batches: A Hierarchical Approach](https://mlsanity.com/paper/2102.05912/) (2021)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (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)
- [Convergence Rates for Regularized Optimal Transport via Quantization](https://mlsanity.com/paper/2208.14391/) (2022)
- [Integrating Efficient Optimal Transport and Functional Maps For Unsupervised Shape Correspondence Learning](https://mlsanity.com/paper/2403.01781/) (2024)
- [Global-Local Regularization Via Distributional Robustness](https://mlsanity.com/paper/2203.00553/) (2022)
- [Markovian Sliced Wasserstein Distances: Beyond Independent Projections](https://mlsanity.com/paper/2301.03749/) (2023)
- [A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementation](https://mlsanity.com/paper/2110.11738/) (2021)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [A Truncated Newton Method for Optimal Transport](https://mlsanity.com/paper/2504.02067/) (2025)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)

## Abstract (arXiv)

We provide theoretical analyses for two algorithms that solve the regularized optimal transport (OT) problem between two discrete probability measures with at most n atoms. We show that a greedy variant of the classical Sinkhorn algorithm, known as the Greenkhorn algorithm, can be improved to widetildeO(n2varepsilon-2), improving on the best known complexity bound of widetildeO(n2varepsilon-3). Notably, this matches the best known complexity bound for the Sinkhorn algorithm and helps explain why the Greenkhorn algorithm can outperform the Sinkhorn algorithm in practice. Our proof technique, which is based on a primal-dual formulation and a novel upper bound for the dual solution, also leads to a new class of algorithms that we refer to as adaptive primal-dual accelerated mirror descent (APDAMD) algorithms. We prove that the complexity of these algorithms is widetildeO(n2√δvarepsilon-1), where δ > 0 refers to the inverse of the strong convexity module of Bregman divergence with respect to |·|_∞. This implies that the APDAMD algorithm is faster than the Sinkhorn and Greenkhorn algorithms in terms of varepsilon. Experimental results on synthetic and real datasets demonstrate the favorable performance of the Greenkhorn and APDAMD algorithms in practice.