| 1. |
- Fan, Jiaojiao, et al.
(författare)
-
On the complexity of the optimal transport problem with graph-structured cost
- 2022
-
Ingår i: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. - : PMLR. ; , s. 9147-9165
-
Konferensbidrag (refereegranskat)abstract
- Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. In particular, with $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal\tilde O(d(\mathcalT)m n^w(G)+1ε^-2)$ bound for a ε-accuracy when the problem is associated with a graph that can be factored as a junction tree with diameter $d(\mathcalT)$ and tree-width $w(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.
|
|
| 2. |
- Singh, Rahul, et al.
(författare)
-
Inference With Aggregate Data in Probabilistic Graphical Models : An Optimal Transport Approach
- 2022
-
Ingår i: IEEE Transactions on Automatic Control. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9286 .- 1558-2523. ; 67:9, s. 4483-4497
-
Tidskriftsartikel (refereegranskat)abstract
- We consider inference (filtering) problems over probabilistic graphical models with aggregate data generated by a large population of individuals. We propose a new efficient belief propagation type algorithm over tree graphs with polynomial computational complexity as well as a global convergence guarantee. This is in contrast to previous methods that either exhibit prohibitive complexity as the population grows or do not guarantee convergence. Our method is based on optimal transport, or more specifically, multimarginal optimal transport theory. In particular, we consider an inference problem with aggregate observations, that can be seen as a structured multimarginal optimal transport problem where the cost function decomposes according to the underlying graph. Consequently, the celebrated Sinkhorn/iterative scaling algorithm for multi-marginal optimal transport can be leveraged together with the standard belief propagation algorithm to establish an efficient inference scheme which we call Sinkhorn belief propagation (SBP). We further specialize the SBP algorithm to cases associated with hidden Markov models due to their significance in control and estimation. We demonstrate the performance of our algorithm on applications such as inferring population flow from aggregate observations. We also show that in the special case where the aggregate observations are in Dirac form, our algorithm naturally reduces to the standard belief propagation algorithm.
|
|
