PreprintCC BY-NC-SA 4.0arXiv
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
Abstract
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(n7/3/ε2/3) to O(n9/4/√ε).
Related
- Robust Local Fréchet Regression: Nonasymptotic Theory and Minimax Optimality
- Exponential Convergence of the Sinkhorn Algorithm for the Schrödinger Bridge with Regime Switching
- Exponential convergence of Sinkhorn algorithm for entropy martingale optimal transport
- Convergence of the Sinkhorn Riemannian metric for finitely supported measures
- Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter
BibTeX
@misc{gao2026tight,
title = {{Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp}},
author = {Wenzhi Gao and Zhaonan Qu and Yinyu Ye and Madeleine Udell},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.11760},
eprint = {2608.11760},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.11760},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
AU - Wenzhi Gao
AU - Zhaonan Qu
AU - Yinyu Ye
AU - Madeleine Udell
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2608.11760
UR - https://arxiv.org/abs/2608.11760
AB - 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(n^7/3/ε^2/3) to O(n^9/4/√ε).
ER -