Order Constraints in Optimal Transport

• URL: http://arxiv.org/abs/2110.07275v1
• Date: Thu, 14 Oct 2021 11:26:23 GMT
• Title: Order Constraints in Optimal Transport
• Authors: Fabian Lim, Laura Wynter, Shiau Hong Lim
• Abstract summary: We introduce novel order constraints into the optimal transport formulation to allow for the incorporation of structure. We derive computationally efficient lower bounds that allow for an explainable approach to adding structure to the optimal transport plan.
• Score: 6.677646909984405
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal transport is a framework for comparing measures whereby a cost is incurred for transporting one measure to another. Recent works have aimed to improve optimal transport plans through the introduction of various forms of structure. We introduce novel order constraints into the optimal transport formulation to allow for the incorporation of structure. While there will are now quadratically many constraints as before, we prove a $\delta-$approximate solution to the order-constrained optimal transport problem can be obtained in $\mathcal{O}(L^2\delta^{-2} \kappa(\delta(2cL_\infty (1+(mn)^{1/2}))^{-1}) \cdot mn\log mn)$ time. We derive computationally efficient lower bounds that allow for an explainable approach to adding structure to the optimal transport plan through order constraints. We demonstrate experimentally that order constraints improve explainability using the e-SNLI (Stanford Natural Language Inference) dataset that includes human-annotated rationales for each assignment.

Related papers

• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  Optimal transport theory provides a principled framework for constructing such mappings. We propose a novel optimal transport solver based on Wasserstein-1. Our experiments demonstrate that the proposed solver can mimic the $W$ OT solvers in finding a unique and monotonic" map on 2D datasets.
  arXiv  Detail & Related papers  (2024-11-01T14:23:19Z)
• Expected Sliced Transport Plans [9.33181953215826]
  We propose a "lifting" operation to extend one-dimensional optimal transport plans back to the original space of the measures. We prove that using the EST plan to weight the sum of the individual Euclidean costs for moving from one point to another results in a valid metric between the input discrete probability measures.
  arXiv  Detail & Related papers  (2024-10-16T02:44:36Z)
• Submodular Framework for Structured-Sparse Optimal Transport [7.030105924295838]
  Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling unnormalized measures and its robustness. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column. We propose novel sparsity-constrained UOT formulations building on the recently explored mean discrepancy based UOT.
  arXiv  Detail & Related papers  (2024-06-07T13:11:04Z)
• Conditional Optimal Transport on Function Spaces [53.9025059364831]
  We develop a theory of constrained optimal transport problems that describe block-triangular Monge maps. This generalizes the theory of optimal triangular transport to separable infinite-dimensional function spaces with general cost functions. We present numerical experiments that demonstrate the computational applicability of our theoretical results for amortized and likelihood-free inference of functional parameters.
  arXiv  Detail & Related papers  (2023-11-09T18:44:42Z)
• Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs [49.1574468325115]
  "Normalizing Flows" is related to the task of constructing invertible transport maps between probability measures by means of deep neural networks. We consider the problem of recovering the $Wamma$-optimal transport map $T$ between absolutely continuous measures $mu,nuinmathcalP(mathbbRn)$ as the flow of a linear-control neural ODE.
  arXiv  Detail & Related papers  (2023-11-02T17:17:03Z)
• InfoOT: Information Maximizing Optimal Transport [58.72713603244467]
  InfoOT is an information-theoretic extension of optimal transport. It maximizes the mutual information between domains while minimizing geometric distances. This formulation yields a new projection method that is robust to outliers and generalizes to unseen samples.
  arXiv  Detail & Related papers  (2022-10-06T18:55:41Z)
• Neural Optimal Transport with General Cost Functionals [66.41953045707172]
  We introduce a novel neural network-based algorithm to compute optimal transport plans for general cost functionals. As an application, we construct a cost functional to map data distributions while preserving the class-wise structure.
  arXiv  Detail & Related papers  (2022-05-30T20:00:19Z)
• 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)
• Approximating Optimal Transport via Low-rank and Sparse Factorization [19.808887459724893]
  Optimal transport (OT) naturally arises in a wide range of machine learning applications but may often become the computational bottleneck. A novel approximation for OT is proposed, in which the transport plan can be decomposed into the sum of a low-rank matrix and a sparse one.
  arXiv  Detail & Related papers  (2021-11-12T03:10:45Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  We study the multi-marginal partial optimal transport (POT) problem between $m$ discrete (unbalanced) measures with at most $n$ supports. We first prove that we can obtain two equivalence forms of the multimarginal POT problem in terms of the multimarginal optimal transport problem via novel extensions of cost tensor. We demonstrate that the ApproxMPOT algorithm can approximate the optimal value of multimarginal POT problem with a computational complexity upper bound of the order $tildemathcalO(m3(n+1)m/ var
  arXiv  Detail & Related papers  (2021-08-18T06:46:59Z)

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.