On the Convergence Rate of Sinkhorn's Algorithm

• 成果类型: Article; Early Access
• 署名作者: Ghosal, Promit; Nutz, Marcel
• 署名单位: University of Chicago; Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0427
• 发表日期: 2025
• 关键词: optimal transport; matrices; geometry

摘要

We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate pi t is shown to satisfy H(pi t|pi*) + H(pi*|pi t) = O(t(-1)), where H denotes relative entropy and pi* denotes the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with sub-Gaussian marginals. We also obtain the rate O(t(-1)) for the dual suboptimality and O(t(-2)) for the marginal entropies. More precisely, we derive nonasymptotic bounds, and in contrast to previous results on linear convergence that are limited to bounded costs, our estimates do not deteriorate exponentially with the regularization parameter. We also obtain a stability result for pi* as a function of the marginals quantified in relative entropy.