mlsanityData to 14 Oct 2026

Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

arXiv 2110.12678 ↗First posted 25 Oct 2021cs.AI cs.NA math.NAcited by 5

Not on the map. Why?

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.

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

17 of 60 references.

References · 17

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  2. 2018Computational Optimal Transportcited by 780
  3. 2017Learning Generative Models with Sinkhorn Divergencescited by 314
  4. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 223
  5. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 189
  6. 2015On Wasserstein Two Sample Testing and Related Families of Nonparametric Testscited by 166
  7. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 112
  8. 2019Statistical bounds for entropic optimal transport: sample complexity and the central limit theoremcited by 85
  9. 2016Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problemscited by 73
  10. 2021Entropic Optimal Transport: Convergence of Potentialscited by 31
  11. 2019Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithmcited by 27
  12. 2016Wasserstein Discriminant Analysiscited by 25
5 more
  1. 2018An explicit analysis of the entropic penalty in linear programmingcited by 24
  2. 2021Entropic Optimal Transport: Geometry and Large Deviationscited by 20
  3. 2018Unsupervised Hyperalignment for Multilingual Word Embeddingscited by 17
  4. 2021Asymptotics for semi-discrete entropic optimal transportcited by 14
  5. 2017Log-PCA versus Geodesic PCA of histograms in the Wasserstein spacecited by 5

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 2.

5 papers.

  1. 2023Minimax estimation of discontinuous optimal transport maps: The semi-discrete casecited by 20
  2. 2023Lower Complexity Adaptation for Empirical Entropic Optimal Transportcited by 12
  3. 2024Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularizationcited by 0
  4. 2025Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Ratecited by 0
  5. 2025Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transportcited by 0