Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm

By Pavel E. Dvurechensky, Alexander V. Gasnikov, Alexey Kroshnin. International Conference on Machine Learning, 2018

326 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/2f9717c462f9a9f0e7598173f636291d6985c000

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics (2018, background): “…of these algorithmic successes and the behavior of some statistical procedures in general (we refer to Bhattacharya and Patrangenaru, 2003; Kendall and Le, 2011; Le Gouic and Loubes, 2017; Altschuler et al., 2017; Dvurechensky et al., 2018; Bigot et al., 2018, for works in this direction).”
Computational Optimal Transport (2018, methodology): “This field remains active, as shown by the recent improvement on the result above by Dvurechensky et al. [2018]. Remark 4.”
Distribution Matching for Crowd Counting (2020, background): “The time complexity is O ( n 2 log n/ 2 ) [9], where (cid:15) is the desired optimality gap, i.e., the upper bound for the difference between the returned objective and the optimal objective.”
Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters (2018, methodology): “Recently, an alternative accelerated-gradient-based approach was shown to give better results than the Sinkhorn’s algorithm for Wasserstein distance [18, 19].”
A Gradient Descent Perspective on Sinkhorn (2020, background): “More recently, a series of work [ANWR17, CK18, DGK18] have derived sublinear estimates for the relative entropy H ( ν | ρ n ) in the same spirit as our convergence rate.”