{"id":"arxiv/2608.11760","url":"https://arxiv.org/abs/2608.11760","tags":["math.OC","cs.LG","stat.ML"],"score":0,"title":"Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp","domain":"math.OC","source":"arxiv","authors":["Wenzhi Gao","Zhaonan Qu","Yinyu Ye","Madeleine Udell"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}