Abstract

We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size n, up to accuracy. For the first algorithm, which is based on the celebrated Sinkhorn’s algorithm, we pro  2 n the complexity bound arithmetic operatie 1 ons . For the second one, which is based on our novel Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) algorithm, n 9/4 we prove o n n2 complexity bound ari tic operations. Both bounds have better dependenceon   than the state-of-the-art result give n2 by . Our second algorithm not only has e better dependence on in the complexity bound, but also is not specific to entropic regularizatio and can solve the OT problem with different regularizers.2