Sum-of-Squares Hierarchy for the Gromov Wasserstein Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908937628942336 |
|---|---|
| author | Tran, Hoang Anh Nguyen, Binh Tuan Soh, Yong Sheng |
| author_facet | Tran, Hoang Anh Nguyen, Binh Tuan Soh, Yong Sheng |
| contents | 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 non-convex 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09102 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sum-of-Squares Hierarchy for the Gromov Wasserstein Problem Tran, Hoang Anh Nguyen, Binh Tuan Soh, Yong Sheng Optimization and Control 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 non-convex 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. |
| title | Sum-of-Squares Hierarchy for the Gromov Wasserstein Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2502.09102 |