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

arXiv1802.04367MaRDI QIDQ6297660

Author name not available (Why is that?)

Publication date: 12 February 2018

Abstract: 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 $widetildeOleft(n^2/varepsilo{n}^{2}ight)$ 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 $widetildeOleft(minleft{n}^{9/4}/varepsilon,n^2/varepsilo{n}^{2}ightight)$ arithmetic operations. Both bounds have better dependence on $varepsilon$ than the state-of-the-art result given by $widetildeOleft(n^2/varepsilo{n}^{3}ight)$. 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.

Has companion code repository: https://github.com/kumarak93/numpy_ot

This page was built for publication: Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6297660)