Structured Transforms Across Spaces with Cost-Regularized Optimal Transport

• URL: http://arxiv.org/abs/2311.05788v2
• Date: Thu, 23 Nov 2023 11:29:11 GMT
• Title: Structured Transforms Across Spaces with Cost-Regularized Optimal Transport
• Authors: Othmane Sebbouh and Marco Cuturi and Gabriel Peyr\'e
• Abstract summary: We exploit in this work a parallel between GW and cost-regularized OT, the regularized minimization of a linear OT objective parameterized by a ground cost. We show that several quadratic OT problems fall in this category, and consider enforcing structure in linear transform. We provide a proximal algorithm to extract such transforms from unaligned data, and demonstrate its applicability to single-cell spatial transcriptomics/multiomics matching tasks.
• Score: 25.684201757101263
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matching a source to a target probability measure is often solved by instantiating a linear optimal transport (OT) problem, parameterized by a ground cost function that quantifies discrepancy between points. When these measures live in the same metric space, the ground cost often defaults to its distance. When instantiated across two different spaces, however, choosing that cost in the absence of aligned data is a conundrum. As a result, practitioners often resort to solving instead a quadratic Gromow-Wasserstein (GW) problem. We exploit in this work a parallel between GW and cost-regularized OT, the regularized minimization of a linear OT objective parameterized by a ground cost. We use this cost-regularized formulation to match measures across two different Euclidean spaces, where the cost is evaluated between transformed source points and target points. We show that several quadratic OT problems fall in this category, and consider enforcing structure in linear transform (e.g. sparsity), by introducing structure-inducing regularizers. We provide a proximal algorithm to extract such transforms from unaligned data, and demonstrate its applicability to single-cell spatial transcriptomics/multiomics matching tasks.

Related papers

• Transport Clustering: Solving Low-Rank Optimal Transport via Clustering [0.9558392439655014]
  We introduce transport clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a full-text-type problem on correspondence rates.<n> Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.
  arXiv  Detail & Related papers  (2026-03-03T23:12:14Z)
• GIST: Targeted Data Selection for Instruction Tuning via Coupled Optimization Geometry [4.94446914034065]
  GIST (Gradient Isometric Subspace Transformation) replaces axis-aligned scaling with robust subspace alignment.<n>We show that GIST matches or outperforms the state-of-the-art baseline with only 0.29% of the storage and 25% of the computational time.
  arXiv  Detail & Related papers  (2026-02-20T19:44:24Z)
• Robust Sublinear Convergence Rates for Iterative Bregman Projections [21.689846521201588]
  We use entropic regularization to approximate linear programs whose constraints split into two (or more) tractable blocks.<n>We derive the flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs.
  arXiv  Detail & Related papers  (2026-02-01T18:20:19Z)
• Optimal Transportation and Alignment Between Gaussian Measures [80.4634530260329]
  Optimal transport (OT) and Gromov-Wasserstein (GW) alignment provide interpretable geometric frameworks for datasets.<n>Because these frameworks are computationally expensive, large-scale applications often rely on closed-form solutions for Gaussian distributions under quadratic cost.<n>This work provides a comprehensive treatment of Gaussian, quadratic cost OT and inner product GW (IGW) alignment, closing several gaps in the literature to broaden applicability.
  arXiv  Detail & Related papers  (2025-12-03T09:01:48Z)
• Structured Matching via Cost-Regularized Unbalanced Optimal Transport [0.8594140167290097]
  Unbalanced optimal transport (UOT) provides a flexible way to match or compare nonnegative finite Radon measures.<n>We introduce cost-regularized unbalanced optimal transport (CR-UOT), a framework that allows the ground cost to vary while allowing mass creation and removal.
  arXiv  Detail & Related papers  (2025-11-24T13:11:27Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  We prove an $mathcalO(t-1)$ lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation.<n>To nearly achieve the desired fast rate, we design an entropic regularization scheme decreasing with the number of samples.
  arXiv  Detail & Related papers  (2024-05-23T11:46:03Z)
• Nearest Neighbor Sampling for Covariate Shift Adaptation [7.940293148084844]
  We propose a new covariate shift adaptation method which avoids estimating the weights. The basic idea is to directly work on unlabeled target data, labeled according to the $k$-nearest neighbors in the source dataset. Our experiments show that it achieves drastic reduction in the running time with remarkable accuracy.
  arXiv  Detail & Related papers  (2023-12-15T17:28:09Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Learning representations that are closed-form Monge mapping optimal with application to domain adaptation [24.258758784011572]
  Optimal transport (OT) is a powerful tool used to compare and align probability measures following the least effort principle. Despite its widespread use in machine learning (ML), OT problem still bears its computational burden. We propose to tackle these challenges using representation learning.
  arXiv  Detail & Related papers  (2023-05-12T14:14:39Z)
• 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)
• Sparsity-Constrained Optimal Transport [27.76137474217754]
  Regularized optimal transport is now increasingly used as a loss or as a matching layer in neural networks. We propose a new approach for OT with explicit cardinality constraints on the transportation plan. Our method can be thought as a middle ground between unregularized OT (recovered in the case $k$) and quadratically-regularized OT (recovered when $k$ is large enough)
  arXiv  Detail & Related papers  (2022-09-30T13:39:47Z)
• 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)
• Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound [11.086440815804226]
  The Gromov-Wasserstein (GW) formulates a node graph between the structured data based on optimal transportation datasets. We take inspiration from the connection with the assignment problem, and propose the Gromov-Wasserstein discrepancy as a surrogate of GW.
  arXiv  Detail & Related papers  (2022-05-12T02:10:56Z)
• Unsupervised Ground Metric Learning using Wasserstein Eigenvectors [0.0]
  Key bottleneck is design of a "ground" cost which should be adapted to the task under study. In this paper, we propose for the first time a canonical answer by computing the ground cost as a positive eigenvector of the function mapping a cost to the pairwise OT distances between the inputs. We also introduce a scalable computational method using entropic regularization, which operates a principal component analysis dimensionality reduction.
  arXiv  Detail & Related papers  (2021-02-11T21:32:59Z)
• Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations [79.23797234241471]
  Discriminating between distributions is an important problem in a number of scientific fields. The Linear Optimal Transportation (LOT) embeds the space of distributions into an $L2$-space. We demonstrate the benefits of LOT on a number of distribution classification problems.
  arXiv  Detail & Related papers  (2020-08-20T19:09:33Z)
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization [101.5159744660701]
  In distributed second order optimization, a standard strategy is to average many local estimates, each of which is based on a small sketch or batch of the data. Here, we introduce a new technique for debiasing the local estimates, which leads to both theoretical and empirical improvements in the convergence rate of distributed second order methods.
  arXiv  Detail & Related papers  (2020-07-02T18:08:14Z)

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.