mlsanityData to 14 Oct 2026

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

arXiv 2608.11760 ↗First posted 12 Aug 2026math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We show that under certain connectivity conditions, SK is a polynomial-time algorithm for doubly stochastic matrix scaling. With the developed tools, we showcase the local suboptimality of SK and provide accelerated variants. Finally, for dense matrices, we improve the complexity of existing first-order matrix scaling algorithms from O(tfracn7/3varepsilon2/3) to O(tfracn9/4√varepsilon).

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 25 of its 41 references that are in the map. First posted on arXiv 12 Aug 2026.

Builds on

25 of 41 references.

References · 25

  1. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 223
  2. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  3. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 112
  4. 2025mHC: Manifold-Constrained Hyper-Connectionscited by 88
  5. 2019On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithmscited by 62
  6. 2021Acceleration Methodscited by 48
  7. 2018Semi-dual Regularized Optimal Transportcited by 26
  8. 2025Softmax is 1/2-Lipschitz: A tight bound across all ℓp normscited by 22
  9. 2017Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transportcited by 18
  10. 2018Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scalingcited by 14
  11. 2018Towards Optimal Running Times for Optimal Transportcited by 11
  12. 2024Accelerating Sinkhorn Algorithm with Sparse Newton Iterationscited by 11
13 more
  1. 2017Much Faster Algorithms for Matrix Scalingcited by 10
  2. 2017Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methodscited by 9
  3. 2016Quantum Optimal Transport for Tensor Field Processingcited by 7
  4. 2023On Sinkhorn's Algorithm and Choice Modelingcited by 6
  5. 2017Exact worst-case convergence rates of the proximal gradient method for composite convex minimizationcited by 5
  6. 2015Parameter Selection and Pre-Conditioning for a Graph Form Solvercited by 4
  7. 2021A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fastcited by 4
  8. 2025Gradient Methods with Online Scaling Part I. Theoretical Foundationscited by 3
  9. 2016Stochastic Matrix-Free Equilibrationcited by 2
  10. 2026Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methodscited by 2
  11. 2025Phase transition of the Sinkhorn-Knopp algorithmcited by 1
  12. 2026On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transportcited by 1
  13. 2026Accelerating Sinkhorn for Entropy-Regularized Optimal Transportcited by 1

Built on by

Not cited yet.