Sharper exponential convergence rates for Sinkhorn's algorithm in continuous settings

• 成果类型: Article; Early Access
• 署名作者: Chizat, Lenaic; Delalande, Alex; Vaskevicius, Tomas
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02242-z
• 发表日期: 2025
• 关键词: entropy minimization

摘要

We study the convergence rate of Sinkhorn's algorithm for solving entropy-regularized optimal transport problems when at least one of the probability measures, mu, admits a density over R-d. For a semi-concave cost function bounded by cand a regularization parameter lambda > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rates that are polynomial in lambda/c(infinity). This represents an exponential improvement over the known contraction rate 1-Theta(exp(-c(infinity)/lambda)) achievable via Hilbert's projective metric. Specifically, we prove a contraction rate value of 1-Theta(lambda(2)/c(infinity)(2)) when mu has a bounded log-density. In some cases, such as when mu is log-concave and the cost function is c(x, y) _-(x, y), this rate improves to 1-Theta (lambda/c(infinity)). The latter rate matches the one that we derive for the transport between isotropic Gaussian measures, indicating tightness in the dependency in lambda/c(infinity). Our results are fully non-asymptotic and explicit in all the parameters of the problem.