# Greedy stochastic algorithms for entropy-regularized optimal transport problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2018.

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

- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [A Survey of Geometric Optimization for Deep Learning: From Euclidean Space to Riemannian Manifold](https://mlsanity.com/paper/2302.08210/) (2023)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples](https://mlsanity.com/paper/2103.00394/) (2021)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes](https://mlsanity.com/paper/2506.14780/) (2025)
- [Efficient Optimal Transport Algorithm by Accelerated Gradient descent](https://mlsanity.com/paper/2104.05802/) (2021)

## Abstract (arXiv)

Optimal transport (OT) distances are finding evermore applications in machine learning and computer vision, but their wide spread use in larger-scale problems is impeded by their high computational cost. In this work we develop a family of fast and practical stochastic algorithms for solving the optimal transport problem with an entropic penalization. This work extends the recently developed Greenkhorn algorithm, in the sense that, the Greenkhorn algorithm is a limiting case of this family. We also provide a simple and general convergence theorem for all algorithms in the class, with rates that match the best known rates of Greenkorn and the Sinkhorn algorithm, and conclude with numerical experiments that show under what regime of penalization the new stochastic methods are faster than the aforementioned methods.