Summary
This paper consider the Gromov-Wasserstien (GW) problem with quadratic cost, a (non-convex) quadratic optimization problem over the space of probability measures (in this work, restricted to uniform discrete measures supported on $n$ points) which takes the form (in discrete setting):
$$\min_{\Gamma} \sum_{1 \leq i,j \leq n} ||x_i - x_{i'}|^2 - |y_j - y_{j'}|^2|^2 \Gamma_{ij} \Gamma_{i'j'},$$
where $\Gamma$ is a doubly stochastic matrix of size $n \times n$.
This problem is known to be hard to solve globally. This paper proposes an approach to do so that is tractable when the point clouds $X= (x_1,\dots,x_n)$ and $Y = (y_1,\dots,y_n)$ are in low dimension---say $d$ [edit: fix rendering]. The core idea is that the GW problem can be reparametrized as
\begin{equation}\tag{1}
\min_{(W,w), \Gamma} - |W|^2 - w + c_0,
\end{equation}
where $\Gamma$ is still a bistochastic matrix, $W,w$ must satisfy the relation $W = 2 X \Gamma Y^T$ and $w = \braket{L,\Gamma}$, where $L$ and $c_0$ are constant term (wrt $w,W,\Gamma$). Note that $W$ can be understood as the correlation between $X$ and $Y$ wrt the joint law $\Gamma$, which is of size $d \times d$, so losely speaking, the quadratic part of the GW problem does not depend on $\Gamma$ (which is of size $n \times n$) but only on the correlation it induces (which is a much smaller object when $d$ is small).
From this reformulation, the idea of the paper to globally solve GW is the following:
- Let $\mathcal{F}$ denote the constraint polytope which links $W,w$ and $\Gamma$. This space is too complex to be represented explicitly (by linear constraints).
- Build a bounding box of $\mathcal{F}$. This is doable because we know that the correlation matrix between $X$ and $Y$ has (explicit) bounds on its entries---for instance when $d=1$ this is simply the cost of the increasing (resp. decreasing) matching.
- Build iteratively a sequence of "lower approximation" $(H_N)_N$ of $\mathcal{F}$ (made of supporting hyperplanes of $\mathcal{F}$), in sense that minimizing the functional in (1) over $H_N$ yields a lower bound $L_N$ for the GW problem. Note: this is a concave minimization problem, which is tractable in low dimension ($d \times d + 1$ here).
- Let $(W_N, w_N)$ be the solution on $H_N$. Typically $W_N,w_N \not\in \mathcal{F}$ (otherwise, we have found a global minimizer of GW), but from this we can build a new constraint $H_{N+1}$ through solving a standard OT problem, providing a doubly stochastic matrix $\Gamma_N$ which is by definition sub-optimal, hence giving an upper-bound $U_N$ for GW.
- Eventually, the authors prove that $U_N - L_N \to 0$ as $N \to \infty$, so the proposed approach yields a practical (in low-dimension) algorithm that converges to a **global** solution of the GW problem.
Strengths
The paper considers the difficult (and important, in my opinion) question of globally solving the GW problem.
The proposed approach is based on existing ideas (parametrization of GW by low-dimensional matrices) but pushes them further to get an original and interesting approach. Having globally converging algorithms for GW, even if restricted to low dimensional setups with "not-so-many points", can be useful to assess the quality of other algorithms that may only converge locally (maybe some of them still converge globally "most of the time", etc.).
The paper is clear and does not sacrifice mathematical technicality. Proofs of Prop 2 and Thm 1 have been checked and no major flaw was identified (aside from small details).
I also appreciate that the paper immediately acknowledges that its approach is limited to low-dimensional problems (which is not a major issue; using GW in low dimension is completely natural).
Weaknesses
# 1. On the convergence of the algorithm
From my understanding, the proof of global convergence of the algorithm (Theorem 1) is purely asymptotic: the gap $\epsilon_N = |U_N - L_N|$ is controled by $|\theta_N - \theta_{N+k}|,\ (\forall k)$ where $\theta_N = (W_N, w_N)$ is compactly supported, which implies by contradiction that $0$ must be the single accumulation point of $\epsilon_N$.
While this makes sense (up to few technical considerations, see below), this can be considered as a weakness (at least from a theoretical viewpoint): the convergence of $\epsilon_N \to 0$ is controlled by "how fast $\theta_N$ accumulates", and even in low dimension, without further investigation (i.e. thinking that $\theta_N$ moves arbitrarily in a compact set), it may take a lot of time to reach low gap $\epsilon$ (and this seems to be suggested by the experiments, where the criterion is set to $10^{-8}$ when $d=2$, but to $10^{-2}$ when $d=3$).
I am not saying that this is what happen in practice, nor that this invalidates the contribution of this theoretical result, but a discussion on this may be welcome.
# 2. On numerical experiments
While the proposed experiments are conducted in a reasonable way, they remain somewhat limited in my opinion. In particular,
- [related to the point above] I would have appreciated to have more illustrative experiments on the algorithm behavior, its convergence, etc.
- As far as I can tell, the paper only compares with the work "local search" [16] (Peyré et al., 2016). Why not comparing with more modern works, as [17] (Scetbon et al., 2022), [D] by Sejourné et al. (2021) or [E] (Li et al., 2023)? Note that [17] seems to handle larger instances ($n=10^5$ points), but may fail to globally converge as far as I can tell. Showcasing the strengths of the current work vs [17] (probably the closest work in its spirit), even in illustrative scenarios, would be of interest.
# Minor comments (rather suggestions than actual weaknesses)
1. In Algorithm 1, the upper bound is updated as $U_{N+1} \leftarrow \min(U_N, \text{OT cost} )$. From my understanding, this makes $U_N$ non-increasing, while $L_N$ is increasing (as a minimization problem with more and more constraints), so that $\epsilon_N$ is decreasing. This is never mentioned as far as I can tell; but it seems to be used in the proof when saying that "if $\epsilon_N \not\to 0$, then it must be lower bounded". Am I correct? Also, the proof says "assume that $\epsilon_N = \dots$" (which to me means "assume that $U_{N+1} = \text{OT cost}$ rather than $U_{N+1} = U_N$"), but never discusses the possibility that $U_{N+1} = U_N$. In any case, this does not invalidate the proof as, from my understanding, the $\min$ in the algorithm is not required to prove convergence (even if we cannot ensure that $\epsilon_N$ is decreasing). But in any ways, I think that this is worth some clarification.
2. The discussion related work and context can be improved. For instance, I do not think that [16] is a suited reference in the introduction with mentioning the GW problem for the first time. It would rather be credited to either Mémoli (2011), or Sturm (2012 - "The space of spaces"). What is new vs known (from [16], or for instance from [A, Sec 2.2.3] and related works) in sections 2 and 3 should also be highlighted. Similarly, using that the quadratic term in GW only depends on $X \Gamma Y^T$ is also used (among other) in [B, C] (note : [C] is a preprint put on arxiv after neurIPS submission, this is a suggestion for the revised version, not a criticism).
3. [typo] line 90 : "has" should be "have" I think?
4. [typo] line 114, I think that "maximum" should be "minimum" ?
5. I wonder how useful are the variables $Z_N, \alpha_N$, given that $Z_N$ is simply $2 W_N$ and $\alpha_N = 1$. I understand that this is a convenient way to write a "general" hyperplane equation $\braket{Z,W} + \alpha w \leq \beta$, but to me it turned out to hinder the reading a bit.
6. [typo] line 168, "that the that".
# References
- [A] A contribution to Optimal Transport on incomparable spaces, T. Vayer, 2020
- [B] On the existence of Monge maps for the Gromov-Wasserstien problem, Dumont et al., 2023.
- [C] The Gromov-Wasserstein distance between spheres, Arya et al., 2023.
- [D] The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation, Sejourné et al., 2021
- [E] A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data, Li et al., 2023
Questions
I think that the work may be improved by adding:
- A discussion / numerical illustration on the convergence (rate) of the algorithm (Section 1. in Weaknesses), or an explanation of why this is not relevant.
- A more precise comparison with concurrent works, in particular [17] (which is the closest to the current work as far as I can tell), from both a theoretical and numerical perspective ; where scalability but also quality of the result (which, I guess, may favor the proposed approach). If the comparison is not meaningful, please explain why.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The authors clearly state that the work is dedicated to low-dimensional point cloud, which is its main limitation.
Aside from that, I do not see any potential societal impact specific to this work.