# Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 60 references that are in the map.
- First posted on arXiv 25 Oct 2021.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests](https://mlsanity.com/paper/1509.02237/) (2015)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Entropic Optimal Transport: Convergence of Potentials](https://mlsanity.com/paper/2104.11720/) (2021)
- [Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm](https://mlsanity.com/paper/1905.13194/) (2019)
- [Wasserstein Discriminant Analysis](https://mlsanity.com/paper/1608.08063/) (2016)
- [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018)
- [Entropic Optimal Transport: Geometry and Large Deviations](https://mlsanity.com/paper/2102.04397/) (2021)
- [Unsupervised Hyperalignment for Multilingual Word Embeddings](https://mlsanity.com/paper/1811.01124/) (2018)
- [Asymptotics for semi-discrete entropic optimal transport](https://mlsanity.com/paper/2106.11862/) (2021)
- [Log-PCA versus Geodesic PCA of histograms in the Wasserstein space](https://mlsanity.com/paper/1708.08143/) (2017)

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

- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization](https://mlsanity.com/paper/2405.14459/) (2024)
- [Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate](https://mlsanity.com/paper/2510.25287/) (2025)
- [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025)

## Abstract (arXiv)

We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. These bounds quantify the stability of the dual solutions of the regularized problem (sometimes called Sinkhorn potentials) w.r.t. the regularization parameter, for which we ensure a better than Lipschitz dependence. Such facts may be a first step towards a mathematical justification of annealing or varepsilon-scaling heuristics for the numerical resolution of regularized semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.