The following question came up when trying to numerically solve some variants of the Gromov-Wasserstein distance.
Setting:
- Let $(X_1, d_1), (X_2, d_2)$ be two compact, separable and complete metric spaces.
- Let $\mu$ be a Borel probability measure on $X_1$ and $\nu$ a Borel probability measure on $X_2$.
- Denote by $\Pi(\mu, \nu)$ the set of probability measure on $X_1 \times X_2$ that have $\mu$ as first and $\nu$ as second marginal.
Question:
Does the following equality hold? \begin{align*} &\inf_{\pi \in \Pi(\mu, \nu)} \int \int |d_1(x_1, x_2) - d_2(y_1, y_2)| \,\pi(dx_2, dy_2) \,\pi(dx_1, dy_1) \\ = & \inf_{\pi_1, \pi_2 \in \Pi(\mu, \nu)} \int \int |d_1(x_1, x_2) - d_2(y_1, y_2)| \,\pi_2(dx_2, dy_2) \,\pi_1(dx_1, dy_1) \end{align*} Notably, the first line defines the 1-Gromov-Wasserstein distance between $\mu$ and $\nu$.
Comments:
More abstractly and simplified, the optimization problems occurring in Question 1 can be seen as bilinear optimization problems. Say $Q \subset \mathbb{R}^d$ is compact and convex and let $C \in \mathbb{R}^{d \times d}$. Basically, the above question asks whether the equality $$ \inf_{w \in Q} w^\top C w = \inf_{w_1, w_2 \in Q} w_1^\top C w_2 $$ can hold for particular $Q$ and $C$.
A bit more concretely, the bilinear problem above would correspond to the setting of the question if $X_1 = \{x_1, ..., x_{d_1}\}$ and $X_2 = \{\hat{x}_1, ..., \hat{x}_{d_2}\}$ are discrete sets. Setting $d=d_1 \cdot d_2$, then $Q \subset [0, 1]^d_+$ would be the weights of the probability mass at each point in the finite space $X \times Y$ with the condition that the marginals fit with the given $\mu$ and $\nu$. Similarly, $C$ would be given by the costs $|d_1(x, \hat{x}) - d_2(y, \hat{y})|$.
