Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem
SIAM Journal on Optimization · 30.06.2026 · 36 (2) · 729-759
DOI: 10.1137/25m1736876 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 27.04.2026. Verfasst von Hoang Anh Tran und 2 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben.
Abstract (Originalsprache)
The Gromov–Wasserstein (GW) problem is a variant of the classical optimal transport problem that allows one to compute meaningful transportation plans between incomparable spaces. At an intuitive level, it seeks plans that minimize the discrepancy between metric evaluations of pairs of points. The GW problem is typically cast as an instance of a nonconvex quadratic program that is, unfortunately, intractable to solve. In this paper, we describe tractable semidefinite relaxations of the GW problem based on the sum-of-squares (SOS) hierarchy. We describe how the Putinar-type and the Schmüdgen-type moment hierarchies can be simplified using marginal constraints, and we prove convergence rates for these hierarchies towards computing global optimal solutions to the GW problem. The proposed SOS hierarchies naturally induce a distance measure analogous to the distortion metrics, and we show that these are genuine distances in that they satisfy the triangle inequality. In particular, the proposed SOS hierarchies provide computationally tractable proxies of the GW distance and the associated distortion distances (over metric measure spaces) that are otherwise intractable to compute.
Zitieren
APA
Tran, H. A., Nguyen, B. T., & Soh, Y. S. (2026). Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem. SIAM Journal on Optimization, 36(2), 729-759. https://doi.org/10.1137/25m1736876
Vancouver
Tran HA, Nguyen BT, Soh YS. Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem. SIAM Journal on Optimization. 2026;36(2):729-759. doi:10.1137/25m1736876
BibTeX
@article{Tran2026,
author = {Tran, Hoang Anh and Nguyen, Binh Tuan and Soh, Yong Sheng},
title = {Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem},
journal = {SIAM Journal on Optimization},
year = {2026},
volume = {36},
number = {2},
pages = {729--759},
doi = {10.1137/25m1736876}
}
EUVIMED