On the Convergence Rate of Sinkhorn's Algorithm

Optimal transport (OT) has evolved from a classical mathematical problem to a versatile tool in machine learning, statistics, and image processing. Early methods like Kantorovich’s linear programming provided foundational solutions but faced computational challenges in high dimensions. The introduction of entropy regularization by Cuturi (2013) revolutionized the field, enabling efficient algorithms like Sinkhorn’s iterative proportional fitting procedure (IPFP). Despite practical success, theoretical understanding of convergence rates, especially for unbounded costs and marginals, remained limited. Prior works established linear convergence under bounded cost assumptions, but real-world applications often involve unbounded scenarios such as quadratic costs with Gaussian or subgaussian marginals. This gap motivated recent efforts to analyze the convergence behavior under broader conditions, with partial results indicating sublinear or qualitative convergence without explicit rates.

The core challenge addressed in this work is establishing explicit, non-asymptotic convergence rates for Sinkhorn’s algorithm when applied to unbounded cost functions and marginals. Existing theories primarily rely on boundedness assumptions, which are restrictive and do not reflect many practical problems involving quadratic or more complex costs. Moreover, understanding how the algorithm’s error diminishes over iterations, especially in high-dimensional settings with unbounded distributions, remains unresolved. The difficulty lies in controlling the growth of dual potentials and the relative entropy of couplings without the simplifying assumption of bounded costs, which is essential for guaranteeing polynomial convergence rates and stability.

The paper’s key innovations include: 1) employing exponential moment bounds of dual potentials to control their growth; 2) integrating Bolley–Villani’s weighted KL inequality to relate the relative entropy of couplings to marginal divergences; 3) deriving explicit non-asymptotic bounds that do not deteriorate exponentially with the regularization parameter, thus ensuring polynomial convergence rates in broad settings. Additionally, the authors develop a quantitative stability analysis of the optimal coupling with respect to marginal perturbations, measured via relative entropy, which enhances robustness. These approaches collectively extend the theoretical understanding of Sinkhorn’s convergence beyond classical bounded-cost regimes, addressing a critical gap in the literature.

• �� Establish exponential moment bounds for dual potentials (ϕ_t, ψ_t) to control their growth, assuming integrability conditions on marginals.
• �� Use the weighted Csiszár–Kullback–Pinsker inequality to relate the relative entropy of couplings to the symmetric relative entropy of marginals.
• �� Derive non-asymptotic bounds on H(π_t|π_*), leveraging the monotonicity of the relative entropy sequence and potential function estimates.
• �� Prove that the convergence rate is at least polynomial (O(t^{-1})) for the relative entropy, and O(t^{-2}) for marginal entropies, independent of exponential dependence on the regularization parameter.
• �� Analyze the stability of the optimal coupling with respect to marginal perturbations, providing explicit bounds in relative entropy.

作者在高维欧几里得空间中测试二次成本和亚高斯边缘分布，使用合成数据和图像数据集，比较Sinkhorn迭代的相对熵误差与传统界限。通过调节正则化参数验证多项式收敛速率的有效性。还进行了不同边缘分布的敏感性分析和稳定性验证，结果显示新界限在实际应用中具有优越性能，验证了理论的实用性和鲁棒性。

实验证明，H(π_t|π_*)以O(t^{-1})速率收敛，显著优于以往仅在有界成本条件下的线性收敛。边缘熵的收敛速率达到O(t^{-2})，且估计在不同正则化参数下保持稳定。边缘分布的稳定性分析显示，最优耦合对边缘变化的敏感性被有效量化，为算法的鲁棒性提供了理论支撑。这些结果在高维场景中表现出优异的收敛性能，验证了新界限的实用性。

该研究为高维数据分析、图像匹配、统计推断等提供了坚实的理论基础。算法适用于大规模数据集的快速匹配与迁移，特别是在无界边缘分布和复杂成本函数场景中。未来可结合深度学习模型，优化非线性大规模OT问题的收敛速度，推动自动驾驶、医疗影像等行业的发展。

当前分析依赖边缘分布的指数矩有限性，极端分布可能导致界限失效。算法参数调优仍需经验，正则化参数影响较大。未考虑多边多耦合和非连续成本场景，未来需拓展模型复杂度和鲁棒性。