Metraipolis › archive › dc_490ff1906a10
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp — arXiv:2608.11760
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.11760
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T05:40:19.318Z
- SHA-256 of the archived text
25c0021031db60f04f5e8a1f3bc4336172bf0272a35f807876faa2381f8b3836- Stable URL of this page
https://metraipolis.com/documento/dc_490ff1906a10
How to cite
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp — arXiv:2608.11760 — arXiv (en), https://arxiv.org/abs/2608.11760 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_490ff1906a10 (Metraipolis archive dc_490ff1906a10, sha256 25c0021031db60f04f5e8a1f3bc4336172bf0272a35f807876faa2381f8b3836)
BibTeX
@misc{dc490ff1906a10,
title = {Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp — arXiv:2608.11760},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.11760},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_490ff1906a10; sha256 25c0021031db60f04f5e8a1f3bc4336172bf0272a35f807876faa2381f8b3836},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11760. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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(\tfrac{n^{7/3}}{\varepsilon^{2/3}})$ to $O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})$.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-13 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2608.11760 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:18:32.545Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).