The Gromov-Wasserstein (GW) distance quantifies dissimilarity between metric measure spaces and provides a meaningful figure of merit for applications involving heterogeneous data. While computational aspects of the GW distance have been widely studied, a strong duality theory and fundamental statistical questions concerning empirical convergence rates remained obscure. This work closes these gaps for the $(2,2)$-GW distance (namely, with quadratic cost) over Euclidean spaces of different dimensions $d_x$ and $d_y$. We consider both the standard GW and the entropic GW (EGW) distances, derive their dual forms, and use them to analyze expected empirical convergence rates. The resulting rates are $n^{-2/\max\{d_x,d_y,4\}}$ (up to a log factor when $\max\{d_x,d_y\}=4$) and $n^{-1/2}$ for the two-sample GW and EGW problems, respectively, which matches the corresponding rates for standard and entropic optimal transport distances. We also study stability of EGW in the entropic regularization parameter and establish approximation and continuity results for the cost and optimal couplings. Lastly, the duality is leveraged to shed new light on the open problem of the one-dimensional GW distance between uniform distributions on $n$ points, illuminating why the identity and anti-identity permutations may not be optimal. Our results serve as a first step towards a comprehensive statistical theory as well as computational advancements for GW distances, based on the discovered dual formulation.
翻译:Gromov-Wasserstein (GW) 距离量化度量测度空间的不相似性,适用于涉及异构数据的应用,并为此提供有意义的性能指标。虽然 GW 距离的计算方面已经广泛研究,但其强对偶理论和关于经验收敛速度的基本统计问题仍然模糊不清。本文针对不同维度 d_x 和 d_y 的欧几里得空间中的 $(2,2)$-GW 距离(即具有二次成本), 分别考虑标准 GW 和熵正则化 GW (EGW) 距离,导出它们的对偶形式,并使用它们分析预期的经验收敛速度。对于两个样本的 GW 和 EGW 问题,所得到的收敛速度为 $n^{-2/\max\{d_x,d_y,4\}}$ (当 $\max \{d_x,d_y\}=4$ 时带有对数因子) 和 $n^{-1/2}$,这与标准和熵正则化最优运输距离的相应速率相匹配。我们还研究了 EGW 距离在熵正则化参数中的稳定性,并为成本和最优匹配提供了逼近性和连续性结果。最后,对偶性被用来揭示一维均匀分布之间 GW 距离的开放问题,阐明了为什么恒等和反恒等排列可能不是最优的。我们的结果是迈向全面的统计理论和基于发现的对偶公式的计算进步的第一步。