Fast Unbalanced Optimal Transport on a Tree
- URL: http://arxiv.org/abs/2006.02703v3
- Date: Fri, 8 Jan 2021 04:35:00 GMT
- Title: Fast Unbalanced Optimal Transport on a Tree
- Authors: Ryoma Sato, Makoto Yamada, Hisashi Kashima
- Abstract summary: This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time.
We prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time.
Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric.
- Score: 40.60905158071766
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Efficient and Accurate Optimal Transport with Mirror Descent and
Conjugate Gradients [15.128885770407132]
We design a novel algorithm for optimal transport by drawing from the entropic optimal transport, mirror descent and conjugate gradients literatures.
Our scalable and GPU parallelizable algorithm is able to compute the Wasserstein distance with extreme precision, reaching relative error rates of $10-8$ without numerical stability issues.
arXiv Detail & Related papers (2023-07-17T14:09:43Z) - Generative modeling of time-dependent densities via optimal transport
and projection pursuit [3.069335774032178]
We propose a cheap alternative to popular deep learning algorithms for temporal modeling.
Our method is highly competitive compared with state-of-the-art solvers.
arXiv Detail & Related papers (2023-04-19T13:50:13Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - Learning Ultrametric Trees for Optimal Transport Regression [10.524752369156337]
We find an optimal tree structure for a given discrete metric space.
One of our key ideas is to cast the problem in ultrametric spaces.
arXiv Detail & Related papers (2022-10-21T22:54:42Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds.
The object of interest for applications such as generative modeling is the underlying optimal transport map.
We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
arXiv Detail & Related papers (2021-12-03T13:45:36Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network.
We design two optimal algorithms that attain these lower bounds.
We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
arXiv Detail & Related papers (2021-06-08T15:54:44Z) - Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical
Solution [8.465228064780748]
We prove that computing the Wasserstein distance between a discrete probability measure supported on two points is already #P-hard.
We introduce a distributionally robust dual optimal transport problem whose objective function is smoothed with the most adverse disturbance distributions.
We show that smoothing the dual objective function is equivalent to regularizing the primal objective function.
arXiv Detail & Related papers (2021-03-10T18:53:59Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
arXiv Detail & Related papers (2020-12-11T08:28:51Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.