# On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 36 references that are in the map.
- First posted on arXiv 4 Apr 2026.

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

- [Improved Complexity Analysis of the Sinkhorn and Greenkhorn Algorithms for Optimal Transport](https://mlsanity.com/paper/2305.14939/) (2023)

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

- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

The Sinkhorn--Knopp (SK) algorithm is a cornerstone method for matrix scaling and entropically regularized optimal transport (EOT). Despite its empirical efficiency, existing theoretical guarantees to achieve a target marginal accuracy varepsilon deteriorate severely in the presence of outliers, bottlenecked either by the global maximum regularized cost η|C|_∞ (where η is the regularization parameter and C the cost matrix) or the matrix's minimum-to-maximum entry ratio nu. This creates a fundamental disconnect between theory and practice. In this paper, we resolve this discrepancy. For EOT, we introduce the novel concept of well-boundedness, a local bulk mass property that rigorously isolates the well-behaved portion of the data from extreme outliers. We prove that governed by this fundamental notion, SK recovers the target transport plan for a problem of dimension n in O(log n - log varepsilon) iterations, completely independent of the regularized cost η|C|_∞. Furthermore, we show that a virtually cost-free pre-scaling step eliminates the dimensional dependence entirely, accelerating convergence to a strictly dimension-free O(log(1/varepsilon)) iterations. Beyond EOT, we establish a sharp phase transition for general (boldsymbolu,boldsymbolv)-scaling governed by a critical matrix density threshold. We prove that when a matrix's density exceeds this threshold, the iteration complexity is strictly independent of nu. Conversely, when the density falls below this threshold, the dependence on nu becomes unavoidable; in this sub-critical regime, we construct instances where SK requires Omega(n/varepsilon) iterations.