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

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.