We propose and analyze a novel approach to accelerate the Sinkhorn and Greenkhorn algorithms for solving the entropic regularized optimal transport (OT) problems. Focusing on the discrete setting where the probability distributions have at most $n$ atoms, and letting $\varepsilon \in \left(0, 1\right)$ denote the tolerance, we introduce accelerated algorithms that have complexity bounds of $\widetilde{\mathcal{O}} \left(\frac{n^{5/2}}{\varepsilon^{3/2}}\right)$. This improves on the known complexity bound of $\widetilde{\mathcal{O}} \left(\frac{n^{2}}{\varepsilon^2}\right)$ for the Sinkhorn and Greenkhorn algorithms. We also present two hybrid algorithms that use the new accelerated algorithms to initialize the Sinkhorn and Greenkhorn algorithms, and we establish complexity bounds of $\widetilde{\mathcal{O}} \left(\frac{n^{7/3}}{\varepsilon}\right)$ for these hybrid algorithms. This is better than the best known complexity $\widetilde{\mathcal{O}} \left(\frac{n^{5/2}}{\varepsilon}\right)$ for accelerated gradient-type algorithms for entropic regularized OT in the literature. We provide an extensive experimental comparison on both synthetic and real datasets to explore the relative advantages of the new algorithms.

我们提出了一种新的算法APDAMD来解决原子最优输运问题，并证明了算法的复杂度界限与加速变种的Sinkhorn算法和Greenkhorn算法，在实践中均具有较高的效率。

熵正则算法在最优输运中的效率