  We provide theoretical analyses for two algorithms that solve the regularized
optimal transport (OT) problem between two discrete probability measures with
at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn
algorithm, known as the \emph{Greenkhorn algorithm}, can be improved to
$\widetilde{\mathcal{O}}(n^2\varepsilon^{-2})$, improving on the best known
complexity bound of $\widetilde{\mathcal{O}}(n^2\varepsilon^{-3})$. Notably,
this matches the best known complexity bound for the Sinkhorn algorithm and
helps explain why the Greenkhorn algorithm can outperform the Sinkhorn
algorithm in practice. Our proof technique, which is based on a primal-dual
formulation and a novel upper bound for the dual solution, also leads to a new
class of algorithms that we refer to as \emph{adaptive primal-dual accelerated
mirror descent} (APDAMD) algorithms. We prove that the complexity of these
algorithms is $\widetilde{\mathcal{O}}(n^2\sqrt{\delta}\varepsilon^{-1})$,
where $\delta > 0$ refers to the inverse of the strong convexity module of
Bregman divergence with respect to $\|\cdot\|_\infty$. This implies that the
APDAMD algorithm is faster than the Sinkhorn and Greenkhorn algorithms in terms
of $\varepsilon$. Experimental results on synthetic and real datasets
demonstrate the favorable performance of the Greenkhorn and APDAMD algorithms
in practice.
