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 \textit{Greenkhorn},
from $\widetilde{O}(n^2\varepsilon^{-3})$ to
$\widetilde{O}(n^2\varepsilon^{-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~\citet{Altschuler-2017-Near}. Second, we propose a new
algorithm, which we refer to as \textit{APDAMD} and which generalizes an
adaptive primal-dual accelerated gradient descent (APDAGD)
algorithm~\citep{Dvurechensky-2018-Computational} with a prespecified mirror
mapping $\phi$. We prove that APDAMD achieves the complexity bound of
$\widetilde{O}(n^2\sqrt{\delta}\varepsilon^{-1})$ in which $\delta>0$ stands
for the regularity of $\phi$. In addition, we show by a counterexample that the
complexity bound of $\widetilde{O}(\min\{n^{9/4}\varepsilon^{-1},
n^2\varepsilon^{-2}\})$ proved for APDAGD before is invalid and give a refined
complexity bound of $\widetilde{O}(n^{5/2}\varepsilon^{-1})$. Further, we
develop a \textit{deterministic} accelerated variant of Sinkhorn via appeal to
estimated sequence and prove the complexity bound of
$\widetilde{O}(n^{7/3}\varepsilon^{-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)~\citep{Guminov-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.
