Sinkhorn-Knopp gets tight convergence proof, 2x faster matrix scaling
First nonasymptotic local convergence analysis matches Jacobian-based rates exactly.
A new paper by Wenzhi Gao, Zhaonan Qu, Yinyu Ye, and Madeleine Odell tackles a long-standing gap in understanding the Sinkhorn-Knopp (SK) algorithm, the workhorse for matrix scaling and optimal transport. While SK's global convergence has been studied extensively, its local linear convergence rate was only known asymptotically through Jacobian arguments. The researchers provide the first nonasymptotic local analysis that exactly matches that asymptotic rate, closing a theoretical gap that has persisted for decades.
The team proves SK is a polynomial-time algorithm for doubly stochastic matrix scaling under certain connectivity conditions—a crucial guarantee for practical deployment. More importantly, they show the algorithm is locally suboptimal and introduce accelerated variants that improve on the original. For dense matrices, their analysis reduces the complexity of first-order matrix scaling from O(n^(7/3)/ε^(2/3)) to O(n^(9/4)/√ε), a significant improvement in both n and ε dependence. This tighter bound means faster practical implementation of optimal transport, which underpins many modern machine learning systems, from generative models to domain adaptation. The paper also opens new avenues for algorithm design, suggesting that tailored acceleration can push beyond SK's baseline performance.
- First nonasymptotic local convergence proof for Sinkhorn-Knopp that matches asymptotic Jacobian rates
- Complexity improved for dense matrix scaling: O(n^(7/3)/ε^(2/3)) → O(n^(9/4)/√ε)
- Proves SK is polynomial-time and locally suboptimal; introduces accelerated variants
Why It Matters
Tighter convergence guarantees and faster matrix scaling directly accelerate optimal transport and ML workloads that rely on Sinkhorn-Knopp.