# On the Efficiency of Entropic Regularized Algorithms for Optimal Transport

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2019.

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

- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning](https://mlsanity.com/paper/2204.06645/) (2022)
- [Integrating Efficient Optimal Transport and Functional Maps For Unsupervised Shape Correspondence Learning](https://mlsanity.com/paper/2403.01781/) (2024)
- [Markovian Sliced Wasserstein Distances: Beyond Independent Projections](https://mlsanity.com/paper/2301.03749/) (2023)
- [Progressive Entropic Optimal Transport Solvers](https://mlsanity.com/paper/2406.05061/) (2024)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (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)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [Applications of No-Collision Transportation Maps in Manifold Learning](https://mlsanity.com/paper/2304.00199/) (2023)
- [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)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [A Survey on Algorithmic Developments in Optimal Transport Problem with Applications](https://mlsanity.com/paper/2501.06247/) (2025)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Improving Generative Flow Networks with Path Regularization](https://mlsanity.com/paper/2209.15092/) (2022)
- [On Rank Energy Statistics via Optimal Transport: Continuity, Convergence, and Change Point Detection](https://mlsanity.com/paper/2302.07964/) (2023)
- [Estimation of entropy-regularized optimal transport maps between non-compactly supported measures](https://mlsanity.com/paper/2311.11934/) (2023)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Fitted value iteration methods for bicausal optimal transport](https://mlsanity.com/paper/2306.12658/) (2023)
- [Fast Approximation of the Generalized Sliced-Wasserstein Distance](https://mlsanity.com/paper/2210.10268/) (2022)
- [Keypoint-Guided Optimal Transport: Models, Algorithms, and Applications](https://mlsanity.com/paper/2303.13102/) (2023)
- [Sinkhorn Algorithm for Sequentially Composed Optimal Transports](https://mlsanity.com/paper/2412.03120/) (2024)
- [Distributionally Robust Deep Q-Learning](https://mlsanity.com/paper/2505.19058/) (2025)
- [Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes](https://mlsanity.com/paper/2506.14780/) (2025)
- [DPOT: A DeepParticle method for Computation of Optimal Transport with convergence guarantee](https://mlsanity.com/paper/2506.23429/) (2025)
- [Sparse Partial Optimal Transport via Quadratic Regularization](https://mlsanity.com/paper/2508.08476/) (2025)
- [cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport](https://mlsanity.com/paper/2605.08793/) (2026)
- [Decentralized and Equitable Optimal Transport](https://mlsanity.com/paper/2403.04259/) (2024)

## Abstract (arXiv)

We present several new complexity results for the entropic regularized algorithms that approximately solve the optimal transport (OT) problem between two discrete probability measures with at most n atoms. First, we improve the complexity bound of a greedy variant of Sinkhorn, known as textitGreenkhorn, from widetildeO(n2varepsilon-3) to widetildeO(n2varepsilon-2). Notably, our result can match the best known complexity bound of Sinkhorn and help clarify why Greenkhorn significantly outperforms Sinkhorn in practice in terms of row/column updates as observed by~citetAltschuler-2017-Near. Second, we propose a new algorithm, which we refer to as textitAPDAMD and which generalizes an adaptive primal-dual accelerated gradient descent (APDAGD) algorithm~citepDvurechensky-2018-Computational with a prespecified mirror mapping φ. We prove that APDAMD achieves the complexity bound of widetildeO(n2√δvarepsilon-1) in which δ>0 stands for the regularity of φ. In addition, we show by a counterexample that the complexity bound of widetildeO(minn9/4varepsilon-1, n2varepsilon-2) proved for APDAGD before is invalid and give a refined complexity bound of widetildeO(n5/2varepsilon-1). Further, we develop a textitdeterministic accelerated variant of Sinkhorn via appeal to estimated sequence and prove the complexity bound of widetildeO(n7/3varepsilon-4/3). As such, we see that accelerated variant of Sinkhorn outperforms Sinkhorn and Greenkhorn in terms of 1/varepsilon and APDAGD and accelerated alternating minimization (AAM)~citepGuminov-2021-Combination in terms of n. Finally, we conduct the experiments on synthetic and real data and the numerical results show the efficiency of Greenkhorn, APDAMD and accelerated Sinkhorn in practice.