We analyze two algorithms for approximating the general optimal transport
(OT) distance between two discrete distributions of size $n$, up to accuracy
$\varepsilon$. For the first algorithm, which is based on the celebrated
Sinkhorn's algorithm, we prove the complexity bound
$\widetilde{O}\left({n^2/\varepsilon^2}\right)$ arithmetic operations. For the
second one, which is based on our novel Adaptive Primal-Dual Accelerated
Gradient Descent (APDAGD) algorithm, we prove the complexity bound
$\widetilde{O}\left(\min\left\{n^{9/4}/\varepsilon, n^{2}/\varepsilon^2
\right\}\right)$ arithmetic operations. Both bounds have better dependence on
$\varepsilon$ than the state-of-the-art result given by
$\widetilde{O}\left({n^2/\varepsilon^3}\right)$. Our second algorithm not only
has better dependence on $\varepsilon$ in the complexity bound, but also is not
specific to entropic regularization and can solve the OT problem with different
regularizers.

本研究分析了逼近两个离散分布之间的一般最优运输（OT）距离的两种算法，并证明了复杂度界限，其中一种基于 Sinkhorn 算法，另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比，我们的算法具有更好的复杂度界限，更好地依赖于 ε，同时可用于各种正则项。