Joint Metric Space Embedding by Unbalanced OT with Gromov-Wasserstein Marginal Penalization

• URL: http://arxiv.org/abs/2502.07510v2
• Date: Tue, 13 May 2025 14:24:45 GMT
• Title: Joint Metric Space Embedding by Unbalanced OT with Gromov-Wasserstein Marginal Penalization
• Abstract summary: We propose a new approach for unsupervised alignment of heterogeneous datasets.<n>Our method is based on an unbalanced optimal transport problem with Gromov-Wasserstein marginalization.
• Score: 3.7498611358320733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a new approach for unsupervised alignment of heterogeneous datasets, which maps data from two different domains without any known correspondences to a common metric space. Our method is based on an unbalanced optimal transport problem with Gromov-Wasserstein marginal penalization. It can be seen as a counterpart to the recently introduced joint multidimensional scaling method. We prove that there exists a minimizer of our functional and that for penalization parameters going to infinity, the corresponding sequence of minimizers converges to a minimizer of the so-called embedded Wasserstein distance. Our model can be reformulated as a quadratic, multi-marginal, unbalanced optimal transport problem, for which a bi-convex relaxation admits a numerical solver via block-coordinate descent. We provide numerical examples for joint embeddings in Euclidean as well as non-Euclidean spaces.

Related papers

• Riemannian ascent--descent for nonconvex nonconcave minimax landscapes: convergence to basin saddle points and applications to distributionally robust optimization [1.0195618602298684]
  We study minimax problems over a gradient of a geodesicean space and a Buresian manifold.<n>Because no globally convergent order first method is known to be available, we instead introduce the notion of a emphbasin saddle point.
  arXiv  Detail & Related papers  (2026-09-12T20:42:11Z)
• A Riemannian Approach to Low-Rank Optimal Transport [10.296598409953278]
  Low-rank optimal transport (OT) mitigates the quadratic scaling of classical solvers, yet existing approaches rely heavily on first-order mirror-descent updates.<n>We propose a unified Riemannian geometric framework for low-rank OT, modeling balanced and unbalanced rank-$r$ positive factored couplings.<n>Our regularization-free first- and second-order solvers achieve faster convergence and superior performance over existing state-of-the-art low-rank OT solvers.
  arXiv  Detail & Related papers  (2026-06-10T14:17:08Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• From Saddle Points Toward Global Minima: A Newton-Type Method on Wasserstein Space [51.56484100374058]
  We propose a second-order method that preconditions Wasserstein minimization by a regularized square root of the squared Wasserstein Hessian.<n>This construction preserves attraction toward directions toward directions toward positive curvature while inducing repulsion directions along negative curvature.<n>We show that WSFN converges linearly in $L2$-Wasserstein to a non-de global distance.
  arXiv  Detail & Related papers  (2026-05-18T07:18:22Z)
• 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)
• A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints [4.917399520581689]
  We propose a space-decoupling framework for optimization on bounded-rank matrices.<n>We show that the tangent cone of coupled constraints is the intersection of tangent cones of each constraint.<n>We unveil the equivalence between the reformulated problem and the original problem.
  arXiv  Detail & Related papers  (2025-01-23T16:54:03Z)
• Total Uncertainty Quantification in Inverse PDE Solutions Obtained with Reduced-Order Deep Learning Surrogate Models [50.90868087591973]
  We propose an approximate Bayesian method for quantifying the total uncertainty in inverse PDE solutions obtained with machine learning surrogate models. We test the proposed framework by comparing it with the iterative ensemble smoother and deep ensembling methods for a non-linear diffusion equation.
  arXiv  Detail & Related papers  (2024-08-20T19:06:02Z)
• Scalable unsupervised alignment of general metric and non-metric structures [21.29255788365408]
  Aligning data from different domains is a fundamental problem in machine learning with broad applications across very different areas. We learn a related well-scalable linear assignment problem (LAP) whose solution is also a minimizer of the quadratic assignment problem (QAP) We evaluate our approach on synthetic and real datasets from single-cell multiomics and neural latent spaces.
  arXiv  Detail & Related papers  (2024-06-19T12:54:03Z)
• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein [27.2585517709102]
  We show that the celebrated Gromov-Wasserstein algorithm from optimal transport is also minimax optimal. These results give the first statistical justification for the deployment of the Gromov-Wasserstein algorithm in practice.
  arXiv  Detail & Related papers  (2023-11-22T18:55:27Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Non-asymptotic convergence bounds for Wasserstein approximation using point clouds [0.0]
  We show how to generate discrete data as if sampled from a model probability distribution. We provide explicit upper bounds for the convergence-type algorithm.
  arXiv  Detail & Related papers  (2021-06-15T06:53:08Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport. We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
  arXiv  Detail & Related papers  (2021-02-02T21:01:13Z)
• Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization [8.386501595252]
  Block majorization-minimativeization (BMM) is a simple iterative algorithm for constrained nonnegative surrogates.<n>We show that BMM produces a novel first-order optimality measure for various algorithms.<n>We also demonstrate that the additional use of diminishing radius can improve the convergence rate of BMM in many instances.
  arXiv  Detail & Related papers  (2020-12-07T07:53:09Z)
• The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation [0.0]
  Comparing metric measure spaces (i.e. a metric space endowed with aprobability distribution) is at the heart of many machine learning problems. The most popular distance between such metric spaces is the metric measureGro-Wasserstein (GW) distance of which is a quadratic. The GW formulation alleviates the comparison of metric spaces equipped with arbitrary positive measures up to isometries.
  arXiv  Detail & Related papers  (2020-09-09T12:38:14Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Continuous Regularized Wasserstein Barycenters [51.620781112674024]
  We introduce a new dual formulation for the regularized Wasserstein barycenter problem. We establish strong duality and use the corresponding primal-dual relationship to parametrize the barycenter implicitly using the dual potentials of regularized transport problems.
  arXiv  Detail & Related papers  (2020-08-28T08:28:06Z)

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.