Semidefinite Relaxations of the Gromov-Wasserstein Distance
- URL: http://arxiv.org/abs/2312.14572v2
- Date: Wed, 27 Dec 2023 03:48:44 GMT
- Title: Semidefinite Relaxations of the Gromov-Wasserstein Distance
- Authors: Junyu Chen, Binh T. Nguyen, Yong Sheng Soh
- Abstract summary: The Gromov-Wasser (GW) distance is a variant of the optimal transport problem that allows one to match objects between spaces.
In this work, we propose a semi-definite relaxation of the GW distance.
Our relaxation provides a manner to compute the ratio of any transport to the global optimal solution.
- Score: 11.014678654943234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Gromov-Wasserstein (GW) distance is a variant of the optimal transport
problem that allows one to match objects between incomparable spaces. At its
core, the GW distance is specified as the solution of a non-convex quadratic
program and is not known to be tractable to solve. In particular, existing
solvers for the GW distance are only able to find locally optimal solutions. In
this work, we propose a semi-definite programming (SDP) relaxation of the GW
distance. The relaxation can be viewed as the dual of the GW distance augmented
with constraints that relate the linear and quadratic terms of transportation
maps. Our relaxation provides a principled manner to compute the approximation
ratio of any transport map to the global optimal solution. Finally, our
numerical experiments suggest that the proposed relaxation is strong in that it
frequently computes the global optimal solution, together with a proof of
global optimality.
Related papers
- Normalizing flows as approximations of optimal transport maps via
linear-control neural ODEs [55.2480439325792]
"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 $W$-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) - A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein
in Graph Data [37.89640056739607]
We present the Bregman Alternating Projected Gradient (BAPG) method, a single-loop algorithm that offers an approximate solution to the Gromov-Wasserstein (GW) distance.
We introduce a novel relaxation technique that balances accuracy and computational efficiency, albeit with some compromises in the feasibility of the coupling map.
arXiv Detail & Related papers (2023-03-12T07:23:16Z) - Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds [53.110934987571355]
We propose Geodesic Sinkhorn -- based on a heat kernel on a manifold graph.
We apply our method to the computation of barycenters of several distributions of high dimensional single cell data from patient samples undergoing chemotherapy.
arXiv Detail & Related papers (2022-11-02T00:51:35Z) - Efficient Approximation of Gromov-Wasserstein Distance using Importance
Sparsification [34.865115235547286]
We propose a novel importance sparsification method, called Spar-GW, to approximate Gromov-Wasserstein distance efficiently.
We demonstrate that the proposed Spar-GW method is applicable to the GW distance with arbitrary ground cost.
In addition, this method can be extended to approximate the variants of GW distance, including the entropic GW distance, the fused GW distance, and the unbalanced GW distance.
arXiv Detail & Related papers (2022-05-26T18:30:40Z) - 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) - Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal
Transport [0.483420384410068]
We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport.
Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.
arXiv Detail & Related papers (2021-10-25T06:52:45Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space.
We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
arXiv Detail & Related papers (2020-12-09T20:19:32Z) - 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) - On Projection Robust Optimal Transport: Sample Complexity and Model
Misspecification [101.0377583883137]
Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected.
Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances.
Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
arXiv Detail & Related papers (2020-06-22T14:35:33Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations.
Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic.
We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
arXiv Detail & Related papers (2020-02-05T03:09:23Z)
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.