# Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

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

## 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 (most cited first, 25 of 25)

- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [mHC: Manifold-Constrained Hyper-Connections](https://mlsanity.com/paper/2512.24880/) (2025)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Semi-dual Regularized Optimal Transport](https://mlsanity.com/paper/1811.05527/) (2018)
- [Softmax is 1/2-Lipschitz: A tight bound across all ℓp norms](https://mlsanity.com/paper/2510.23012/) (2025)
- [Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1711.01851/) (2017)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [Towards Optimal Running Times for Optimal Transport](https://mlsanity.com/paper/1810.07717/) (2018)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Much Faster Algorithms for Matrix Scaling](https://mlsanity.com/paper/1704.02315/) (2017)
- [Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods](https://mlsanity.com/paper/1704.02310/) (2017)
- [Quantum Optimal Transport for Tensor Field Processing](https://mlsanity.com/paper/1612.08731/) (2016)
- [On Sinkhorn's Algorithm and Choice Modeling](https://mlsanity.com/paper/2310.00260/) (2023)
- [Exact worst-case convergence rates of the proximal gradient method for composite convex minimization](https://mlsanity.com/paper/1705.04398/) (2017)
- [Parameter Selection and Pre-Conditioning for a Graph Form Solver](https://mlsanity.com/paper/1503.08366/) (2015)
- [A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast](https://mlsanity.com/paper/2106.10439/) (2021)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [Stochastic Matrix-Free Equilibration](https://mlsanity.com/paper/1602.06621/) (2016)
- [Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods](https://mlsanity.com/paper/2602.10697/) (2026)
- [Phase transition of the Sinkhorn-Knopp algorithm](https://mlsanity.com/paper/2507.09711/) (2025)
- [On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport](https://mlsanity.com/paper/2604.03787/) (2026)
- [Accelerating Sinkhorn for Entropy-Regularized Optimal Transport](https://mlsanity.com/paper/2605.30267/) (2026)

## 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).