  This paper improves the state-of-the-art rate of a first-order algorithm for
solving entropy regularized optimal transport. The resulting rate for
approximating the optimal transport (OT) has been improved from
$\widetilde{{O}}({n^{2.5}}/{\epsilon})$ to $\widetilde{{O}}({n^2}/{\epsilon})$,
where $n$ is the problem size and $\epsilon$ is the accuracy level. In
particular, we propose an accelerated primal-dual stochastic mirror descent
algorithm with variance reduction. Such special design helps us improve the
rate compared to other accelerated primal-dual algorithms. We further propose a
batch version of our stochastic algorithm, which improves the computational
performance through parallel computing. To compare, we prove that the
computational complexity of the Stochastic Sinkhorn algorithm is
$\widetilde{{O}}({n^2}/{\epsilon^2})$, which is slower than our accelerated
primal-dual stochastic mirror algorithm. Experiments are done using synthetic
and real data, and the results match our theoretical rates. Our algorithm may
inspire more research to develop accelerated primal-dual algorithms that have
rate $\widetilde{{O}}({n^2}/{\epsilon})$ for solving OT.
