# Improved Rate of First Order Algorithms for Entropic Optimal Transport

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 23 Jan 2023.

## Builds on (most cited first, 18 of 18)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)
- [Towards Optimal Running Times for Optimal Transport](https://mlsanity.com/paper/1810.07717/) (2018)
- [Approximating optimal transport with linear programs](https://mlsanity.com/paper/1810.05957/) (2018)
- [Greedy stochastic algorithms for entropy-regularized optimal transport problems](https://mlsanity.com/paper/1803.01347/) (2018)
- [A Graph Theoretic Additive Approximation of Optimal Transport](https://mlsanity.com/paper/1905.11830/) (2019)
- [Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent](https://mlsanity.com/paper/1909.06918/) (2019)
- [Accelerated Bregman Primal-Dual methods applied to Optimal Transport and Wasserstein Barycenter problems](https://mlsanity.com/paper/2203.00802/) (2022)

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

- [Novel Class Discovery for Long-tailed Recognition](https://mlsanity.com/paper/2308.02989/) (2023)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [A Truncated Newton Method for Optimal Transport](https://mlsanity.com/paper/2504.02067/) (2025)
- [Diffusion differentiable resampling](https://mlsanity.com/paper/2512.10401/) (2025)
- [Sinkhorn Algorithm for Sequentially Composed Optimal Transports](https://mlsanity.com/paper/2412.03120/) (2024)
- [Estimation of Stochastic Optimal Transport Maps](https://mlsanity.com/paper/2512.09499/) (2025)
- [Optimal Transport for Network Comparison: A Unified Review with New Spectral Bounds and Machine Learning Applications](https://mlsanity.com/paper/2608.27500/) (2026)

## Abstract (arXiv)

This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from widetildeO(n2.5/ε) to widetildeO(n2/ε), where n is the problem size and ε is the accuracy level. In particular, we propose an accelerated primal-dual stochastic mirror descent algorithm with variance reduction. Such special design helps us improve the rate compared to other accelerated primal-dual algorithms. We further propose a batch version of our stochastic algorithm, which improves the computational performance through parallel computing. To compare, we prove that the computational complexity of the Stochastic Sinkhorn algorithm is widetildeO(n2/ε2), which is slower than our accelerated primal-dual stochastic mirror algorithm. Experiments are done using synthetic and real data, and the results match our theoretical rates. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate widetildeO(n2/ε) for solving OT.