Tree-Based Diffusion Schr\"odinger Bridge with Applications to Wasserstein Barycenters

• URL: http://arxiv.org/abs/2305.16557v2
• Date: Sat, 28 Oct 2023 15:01:39 GMT
• Title: Tree-Based Diffusion Schr\"odinger Bridge with Applications to Wasserstein Barycenters
• Authors: Maxence Noble, Valentin De Bortoli, Arnaud Doucet, Alain Durmus
• Abstract summary: We develop Tree-based Diffusion Schr"odinger Bridge (TreeDSB), an extension of the Diffusion Schr"odinger Bridge (DSB) algorithm. A notable use case of our methodology is to compute Wasserstein barycenters which can be recast as the solution of a mOT problem on a star-shaped tree.
• Score: 44.75675404104031
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-marginal Optimal Transport (mOT), a generalization of OT, aims at minimizing the integral of a cost function with respect to a distribution with some prescribed marginals. In this paper, we consider an entropic version of mOT with a tree-structured quadratic cost, i.e., a function that can be written as a sum of pairwise cost functions between the nodes of a tree. To address this problem, we develop Tree-based Diffusion Schr\"odinger Bridge (TreeDSB), an extension of the Diffusion Schr\"odinger Bridge (DSB) algorithm. TreeDSB corresponds to a dynamic and continuous state-space counterpart of the multimarginal Sinkhorn algorithm. A notable use case of our methodology is to compute Wasserstein barycenters which can be recast as the solution of a mOT problem on a star-shaped tree. We demonstrate that our methodology can be applied in high-dimensional settings such as image interpolation and Bayesian fusion.

Related papers

• Conditional Density Estimation with Histogram Trees [3.5297361401370044]
  Conditional density estimation (CDE) goes beyond regression by modeling the full conditional distribution. Current methods typically employ kernel-based approaches, using kernel functions directly for kernel density estimation or as basis functions in linear models. We propose the Conditional Density Tree (CDTree), a fully non-parametric model consisting of a decision tree in which each leaf is formed by a histogram model.
  arXiv  Detail & Related papers  (2024-10-15T09:53:24Z)
• Optimal Transport for Measures with Noisy Tree Metric [29.950797721275574]
  We study optimal transport problem for probability measures supported on a tree metric space. In general, this approach is hard to compute, even for measures supported in one space. We show that the robust OT satisfies the metric property and is negative definite.
  arXiv  Detail & Related papers  (2023-10-20T16:56:08Z)
• Light Schrödinger Bridge [72.88707358656869]
  We develop a lightweight, simulation-free and theoretically justified Schr"odinger Bridges solver. Our light solver resembles the Gaussian mixture model which is widely used for density estimation. Inspired by this similarity, we also prove an important theoretical result showing that our light solver is a universal approximator of SBs.
  arXiv  Detail & Related papers  (2023-10-02T13:06:45Z)
• Building the Bridge of Schr\"odinger: A Continuous Entropic Optimal Transport Benchmark [96.06787302688595]
  We propose a novel way to create pairs of probability distributions for which the ground truth OT solution is known by the construction. We use these benchmark pairs to test how well existing neural EOT/SB solvers actually compute the EOT solution.
  arXiv  Detail & Related papers  (2023-06-16T20:03:36Z)
• I$^2$SB: Image-to-Image Schr\"odinger Bridge [87.43524087956457]
  Image-to-Image Schr"odinger Bridge (I$2$SB) is a new class of conditional diffusion models. I$2$SB directly learns the nonlinear diffusion processes between two given distributions. We show that I$2$SB surpasses standard conditional diffusion models with more interpretable generative processes.
  arXiv  Detail & Related papers  (2023-02-12T08:35:39Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Fixed Support Tree-Sliced Wasserstein Barycenter [40.087553363884396]
  We propose a barycenter under the tree-Wasserstein distance, called the fixed support tree-Wasserstein barycenter (FS-TWB) and its extension, called the fixed support tree-sliced Wasserstein barycenter (FS-TSWB) We show that the FS-TWB and FS-TSWB can be solved two orders of magnitude faster than the original Wasserstein barycenter.
  arXiv  Detail & Related papers  (2021-09-08T04:50:33Z)
• Wasserstein Distances, Geodesics and Barycenters of Merge Trees [9.149293243237778]
  This paper presents a unified computational framework for the estimation of distances, geodesics and barycenters of merge trees. We introduce a new metric, called the Wasserstein distance between merge trees, which is purposely designed to enable efficient computations of geodesics and barycenters.
  arXiv  Detail & Related papers  (2021-07-16T09:27:49Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks [15.171726731041055]
  Wasserstein Barycenter is a principled approach to represent the weighted mean of a given set of probability distributions. We present a novel scalable algorithm to approximate the Wasserstein Barycenters aiming at high-dimensional applications in machine learning.
  arXiv  Detail & Related papers  (2020-07-08T22:41:18Z)

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.