On the Convergence Rate of Sinkhorn’s Algorithm
研究了Sinkhorn算法求解熵正则化最优传输问题的收敛速度，给出了迭代误差、对偶次优性和边际熵的显式非渐近界，且估计不随正则化参数指数恶化。
We study Sinkhorn’s algorithm for solving the entropically regularized optimal transport problem. Its iterate [Formula: see text] is shown to satisfy [Formula: see text], where H denotes relative entropy and [Formula: see text] 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 [Formula: see text] for the dual suboptimality and [Formula: see text] 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 [Formula: see text] as a function of the marginals quantified in relative entropy. Funding: P. Ghosal was supported by the National Science Foundation [Grant DMS-2153661]. M. Nutz was supported by the National Science Foundation [Grants DMS-1812661, DMS-2106056, and DMS-2407074].