String Diagram of Optimal Transports

• URL: http://arxiv.org/abs/2408.08550v2
• Date: Sat, 25 Jan 2025 04:50:05 GMT
• Title: String Diagram of Optimal Transports
• Authors: Kazuki Watanabe, Noboru Isobe,
• Abstract summary: We present a novel hierarchical framework for optimal transport (OT) using string diagrams, namely string diagrams of optimal transports. This framework reduces complex hierarchical OT problems to standard OT problems, allowing efficient synthesis of optimal hierarchical transportation plans.
• Score: 0.0
• License:
• Abstract: We present a novel hierarchical framework for optimal transport (OT) using string diagrams, namely string diagrams of optimal transports. This framework reduces complex hierarchical OT problems to standard OT problems, allowing efficient synthesis of optimal hierarchical transportation plans. Our approach uses algebraic compositions of cost matrices to effectively model hierarchical structures. We also study an adversarial situation with multiple choices in the cost matrices, where we present a polynomial-time algorithm for a relaxation of the problem. Experimental results confirm the efficiency and performance advantages of our proposed algorithm over the naive method.

Related papers

• 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)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sys is a framework that harnesses optimal transport theory for data repair under Conditional Independence (CI) constraints. We develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data.
  arXiv  Detail & Related papers  (2024-03-04T18:23:55Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  Best subset selection is considered the gold standard for many learning problems. An efficient subset-dual algorithm is developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2024-02-04T02:26:40Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Multi-Task Off-Policy Learning from Bandit Feedback [54.96011624223482]
  We propose a hierarchical off-policy optimization algorithm (HierOPO), which estimates the parameters of the hierarchical model and then acts pessimistically with respect to them. We prove per-task bounds on the suboptimality of the learned policies, which show a clear improvement over not using the hierarchical model. Our theoretical and empirical results show a clear advantage of using the hierarchy over solving each task independently.
  arXiv  Detail & Related papers  (2022-12-09T08:26:27Z)
• Efficient Robust Optimal Transport with Application to Multi-Label Classification [12.521494095948068]
  We model the feature-feature relationship via a symmetric positive semi-definite Mahalanobis metric in the OT cost function. We view the resulting optimization problem as a non-linear OT problem, which we solve using the Frank-Wolfe algorithm. Empirical results on the discriminative learning setting, such as tag prediction and multi-class classification, illustrate the good performance of our approach.
  arXiv  Detail & Related papers  (2020-10-22T16:43:52Z)
• Feature Robust Optimal Transport for High-dimensional Data [125.04654605998618]
  We propose feature-robust optimal transport (FROT) for high-dimensional data, which solves high-dimensional OT problems using feature selection to avoid the curse of dimensionality. We show that the FROT algorithm achieves state-of-the-art performance in real-world semantic correspondence datasets.
  arXiv  Detail & Related papers  (2020-05-25T14:07:16Z)
• Tiering as a Stochastic Submodular Optimization Problem [5.659969270836789]
  Tiering is an essential technique for building large-scale information retrieval systems. We show that the optimal tiering as an optimization problem can be cast as a submodular minimization problem with a submodular knapsack constraint.
  arXiv  Detail & Related papers  (2020-05-16T07:39:29Z)
• Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework [21.037720934987483]
  We propose a convex OT program with a sum-of-norms regularization term, which provably recovers the underlying class structure under geometric assumptions. We provide a novel argument for the uniqueness of the optimum even in the absence of strong convexity. Our experiments show that the new regularizer not only results in a better preservation of the class structure in the data but also yields additional robustness to the data geometry.
  arXiv  Detail & Related papers  (2019-03-09T18:54:21Z)

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.