# Improved Complexity Analysis of the Sinkhorn and Greenkhorn Algorithms for Optimal Transport

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2023.

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

- [Learning diffusion at lightspeed](https://mlsanity.com/paper/2406.12616/) (2024)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [A Universal Metric of Dataset Similarity for Cross-silo Federated Learning](https://mlsanity.com/paper/2404.18773/) (2024)
- [Probabilistic Token Alignment for Large Language Model Fusion](https://mlsanity.com/paper/2509.17276/) (2025)
- [On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport](https://mlsanity.com/paper/2604.03787/) (2026)
- [Bias as a Virtue: Rethinking Generalization under Distribution Shifts](https://mlsanity.com/paper/2506.00407/) (2025)
- [Optimal Transport Meets Reinforcement Learning: A Survey](https://mlsanity.com/paper/2610.01413/) (2026)

## Abstract (arXiv)

The Sinkhorn algorithm is a widely used method for solving the optimal transport problem, and the Greenkhorn algorithm is one of its variants. While there are modified versions of these two algorithms whose computational complexities are O(n2|C|_∞2log n/varepsilon2) to achieve an varepsilon-accuracy, to the best of our knowledge, the existing complexities for the vanilla versions are O(n2|C|_∞3log n/varepsilon3). In this paper we fill this gap and show that the complexities of the vanilla Sinkhorn and Greenkhorn algorithms are indeed O(n2|C|_∞2log n/varepsilon2). The analysis relies on the equicontinuity of the dual variables for the discrete entropic regularized optimal transport problem, which is of independent interest.