mlsanityData to 13 Oct 2026

Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes

arXiv 2506.14780 ↗First posted 23 May 2025math.NA cs.NA math.OCcited by 1

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose an accelerated version for the Sinkhorn algorithm, which is the reference method for computing the solution to Entropic Optimal Transport. Its main draw-back is the exponential slow-down of convergence as the regularization weakens varepsilon rightarrow 0. Thanks to spectral insights on the behavior of the Hessian, we propose to mitigate the problem via an original spectral warm-start strategy. This leads to faster convergence compared to the reference method, as also demonstrated in our numerical experiments.

Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). Builds on 18 of its 26 references that are in the map. First posted on arXiv 23 May 2025.

Builds on

18 of 26 references.

References · 18

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,295
  2. 2017Learning Generative Models with Sinkhorn Divergencescited by 311
  3. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 222
  4. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 188
  5. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 112
  6. 2020Faster Wasserstein Distance Estimation with the Sinkhorn Divergencecited by 73
  7. 2016Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problemscited by 72
  8. 2018Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distancecited by 56
  9. 2018Massively scalable Sinkhorn distances via the Nystr"om methodcited by 41
  10. 2019On the Efficiency of Entropic Regularized Algorithms for Optimal Transportcited by 35
  11. 2018Semi-dual Regularized Optimal Transportcited by 26
  12. 2019Screening Sinkhorn Algorithm for Regularized Optimal Transportcited by 20
6 more
  1. 2017Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transportcited by 17
  2. 2022Rethinking Initialization of the Sinkhorn Algorithmcited by 14
  3. 2024Accelerating Sinkhorn Algorithm with Sparse Newton Iterationscited by 11
  4. 2018Greedy stochastic algorithms for entropy-regularized optimal transport problemscited by 9
  5. 2022The derivatives of Sinkhorn-Knopp convergecited by 9
  6. 2024Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasingcited by 7

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Accelerating Birkhoff Projection for Manifold-Constrained Hyper-Connectionscited by 3