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

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 prove the complexity bound O(n^2/ε^2) 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 O({n^9/4/ε, n^2/ε^2 }) arithmetic operations. Both bounds have better dependence on ε than the state-of-the-art result given by O(n^2/ε^3). Our second algorithm not only has better dependence on ε in the complexity bound, but also is not specific to entropic regularization and can solve the OT problem with different regularizers.

Authors

05/23/2019

Accelerated Primal-Dual Coordinate Descent for Computational Optimal Transport

We propose and analyze a novel accelerated primal-dual coordinate descen...
09/30/2019

On the Complexity of Approximating Multimarginal Optimal Transport

We study the complexity of approximating the multimarginal optimal trans...
04/12/2021

Efficient Optimal Transport Algorithm by Accelerated Gradient descent

Optimal transport (OT) plays an essential role in various areas like mac...
01/24/2019

On the Complexity of Approximating Wasserstein Barycenter

We study the complexity of approximating Wassertein barycenter of m disc...
01/19/2019

On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms

We provide theoretical analyses for two algorithms that solve the regula...
09/29/2021

On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

This paper studies the equitable and optimal transport (EOT) problem, wh...
09/18/2020

SISTA: learning optimal transport costs under sparsity constraints

In this paper, we describe a novel iterative procedure called SISTA to l...
This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9177688,"math_prob":0.91265583,"size":941,"snap":"2022-05-2022-21","text_gpt3_token_len":210,"char_repetition_ratio":0.12059765,"word_repetition_ratio":0.029850746,"special_character_ratio":0.20085016,"punctuation_ratio":0.08235294,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9867227,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-19T14:04:41Z\",\"WARC-Record-ID\":\"<urn:uuid:f5b84b08-c7d6-4613-84ba-84f832f3c0c3>\",\"Content-Length\":\"136518\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:19f0d0d5-8be9-4cda-b6a4-b5398d220ce7>\",\"WARC-Concurrent-To\":\"<urn:uuid:1cd44798-750b-4582-b6b6-65bf06acf183>\",\"WARC-IP-Address\":\"44.235.123.242\",\"WARC-Target-URI\":\"https://deepai.org/publication/computational-optimal-transport-complexity-by-accelerated-gradient-descent-is-better-than-by-sinkhorn-s-algorithm\",\"WARC-Payload-Digest\":\"sha1:MMA5P4JYNW3G3I4USWVZTYTIJX5TZFWL\",\"WARC-Block-Digest\":\"sha1:K5ROYVEX3SNYIQ5YDEWXA66E3KXBC4F7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320301341.12_warc_CC-MAIN-20220119125003-20220119155003-00419.warc.gz\"}"}