Skip to yearly menu bar Skip to main content

Workshop: Optimal Transport and Machine Learning

Semidefinite Relaxations of the Gromov-Wasserstein Distance

Junyu Chen · Binh T. Nguyen · Yong Sheng Soh


The Gromov-Wasserstein distance (GW) is an extension of the optimal transport problem that allows one to match objects between incomparable spaces. At its core, GW-distance is specified as the solution of a non-convex quadractically constrained quadratic program, which is not known to be tractable to solve. In particular, existing solvers are only able to find local optimizers. In this work, we propose a semi-definite programming (SDP) relaxation of the GW distance. Our approach provides the ability to compute the optimality gap of any transport map from the global optimal solution. Our initial numerical experiments suggest that our proposed relaxation is strong in that it frequently computes the global optimal solution, together with a proof of global optimality.

Chat is not available.