On the Efficiency of Entropic Regularized Algorithms for Optimal Transport

We present several new complexity results for the entropic regularized algorithms that approximately solve the optimal transport (OT) problem between two discrete probability measures with at most n atoms. First, we improve the complexity bound of a greedy variant of Sinkhorn, known as textitGreenkhorn, from widetildeO(n2varepsilon-3) to widetildeO(n2varepsilon-2). Notably, our result can match the best known complexity bound of Sinkhorn and help clarify why Greenkhorn significantly outperforms Sinkhorn in practice in terms of row/column updates as observed by~citetAltschuler-2017-Near. Second, we propose a new algorithm, which we refer to as textitAPDAMD and which generalizes an adaptive primal-dual accelerated gradient descent (APDAGD) algorithm~citepDvurechensky-2018-Computational with a prespecified mirror mapping φ. We prove that APDAMD achieves the complexity bound of widetildeO(n2√δvarepsilon-1) in which δ>0 stands for the regularity of φ. In addition, we show by a counterexample that the complexity bound of widetildeO(minn9/4varepsilon-1, n2varepsilon-2) proved for APDAGD before is invalid and give a refined complexity bound of widetildeO(n5/2varepsilon-1). Further, we develop a textitdeterministic accelerated variant of Sinkhorn via appeal to estimated sequence and prove the complexity bound of widetildeO(n7/3varepsilon-4/3). As such, we see that accelerated variant of Sinkhorn outperforms Sinkhorn and Greenkhorn in terms of 1/varepsilon and APDAGD and accelerated alternating minimization (AAM)~citepGuminov-2021-Combination in terms of n. Finally, we conduct the experiments on synthetic and real data and the numerical results show the efficiency of Greenkhorn, APDAMD and accelerated Sinkhorn in practice.