608. Sum-of-squares for Optimal Transport: The Gromov Wasserstein Problem
Invited abstract in session MC-10: Optimization, Learning, and Games II, stream Optimization, Learning, and Games.
Monday, 14:00-16:00Room: B100/8011
Authors (first author is the speaker)
| 1. | Yong Sheng Soh
|
| National University of Singapore |
Abstract
The Gromov-Wasserstein (GW) problem is an extension of the classical optimal transport problem to settings where the source and target distributions reside in incomparable spaces, and for which a cost function that attributes the price of moving resources is not available. The sum-of-squares (SOS) hierarchy is a principled method for deriving tractable semidefinite relaxations to generic polynomial optimization problems. The GW problem, as it is stated, is a non-convex quadratic program and is intractable to solve in general.
In this talk, we describe a moment-SOS hierarchy for solving the GW problem. We also describe extensions that remain valid for continuous measures. We establish convergence rates of the proposed SOS hierarchy, as well as sample complexity rates that arise from sampling the source and target distributions. We show that these hierarchies define pseudo-metrics over the space of (metric measure-) spaces. Finally, we discuss future directions that hint at applying SOS for general optimization problems over distributions that depend on the decision variable in a polynomial way.
Keywords
- Applications of continuous optimization
Status: accepted
Back to the list of papers