싱크혼-노프 알고리즘의 엄격하고 비점근적인 국소 수렴성

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

본 논문에서는 행렬 스케일링 문제에 대한 싱크혼-노프(SK) 알고리즘을 재검토합니다. SK 알고리즘과 그 변형들의 전역 수렴성에 대한 많은 연구가 진행되었지만, 그 국소적인 선형 수렴 특성은 아직 덜 이해되고 있습니다. 본 논문은 기존의 점근적 야코비안 기반 분석에서 얻을 수 있는 수렴 속도와 일치하는 SK 알고리즘에 대한 최초의 비점근적 국소 분석을 제공합니다. 특정 연결 조건 하에서, SK는 이중 확률 행렬 스케일링을 위한 다항 시간 알고리즘임을 보여줍니다. 개발된 도구를 활용하여, SK 알고리즘의 국소적인 최적성을 입증하고, 가속화된 변형들을 제시합니다. 마지막으로, 밀집 행렬에 대해 기존의 1차 행렬 스케일링 알고리즘의 복잡도를 $O( frac{n^{7/3}}{ ext{ε}^{2/3}})$에서 $O( frac{n^{9/4}}{ ext{√ε}})$로 개선합니다.

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}})$.