Timezone: »
This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We reveal which problems in unbalanced optimal transport can/cannot be solved efficiently. Specifically, we prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time under the strong exponential time hypothesis. Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric. The proposed algorithm processes a tree with one million nodes in less than one second. Our analysis forms a foundation for the theoretical study of unbalanced optimal transport algorithms and opens the door to the applications of unbalanced optimal transport to million-scale datasets.
Author Information
Ryoma Sato (Kyoto University)
I am a first year student in master's program at Kashima-Yamada Lab, Kyoto University Interests: Machine Learning on Graphs, Discrete Algorithms
Makoto Yamada (Kyoto University/RIKEN AIP)
Hisashi Kashima (Kyoto University/RIKEN Center for AIP)
More from the Same Authors
-
2021 Poster: Adversarial Regression with Doubly Non-negative Weighting Matrices »
Tam Le · Truyen Nguyen · Makoto Yamada · Jose Blanchet · Viet Anh Nguyen -
2021 Poster: Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares »
Hiroaki Yamada · Makoto Yamada -
2020 Poster: Neural Methods for Point-wise Dependency Estimation »
Yao-Hung Hubert Tsai · Han Zhao · Makoto Yamada · Louis-Philippe Morency · Russ Salakhutdinov -
2020 Spotlight: Neural Methods for Point-wise Dependency Estimation »
Yao-Hung Hubert Tsai · Han Zhao · Makoto Yamada · Louis-Philippe Morency · Russ Salakhutdinov -
2019 Poster: Fast Sparse Group Lasso »
Yasutoshi Ida · Yasuhiro Fujiwara · Hisashi Kashima -
2019 Poster: Theoretical evidence for adversarial robustness through randomization »
Rafael Pinot · Laurent Meunier · Alexandre Araujo · Hisashi Kashima · Florian Yger · Cedric Gouy-Pailler · Jamal Atif -
2019 Poster: Kernel Stein Tests for Multiple Model Comparison »
Jen Ning Lim · Makoto Yamada · Bernhard Schölkopf · Wittawat Jitkrittum -
2019 Poster: Approximation Ratios of Graph Neural Networks for Combinatorial Problems »
Ryoma Sato · Makoto Yamada · Hisashi Kashima -
2019 Poster: Tree-Sliced Variants of Wasserstein Distances »
Tam Le · Makoto Yamada · Kenji Fukumizu · Marco Cuturi -
2018 Poster: Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams »
Tam Le · Makoto Yamada