Sample Complexity for the 2-Gromov-Wasserstein Distance

In this paper, we study the sample complexity of the empirical plug-in estimator for the $2$-Gromov-Wasserstein distance $D_2$ between compactly supported probability measures on Euclidean spaces. Let $\mu$ and $\nu$ be supported on compact subsets of ${\mathbb{R}}^{d_x}$ and ${\mathbb{R}}^{d_y}$, respectively, and let ${\widehat{\mu }}_n$ and ${\widehat{\nu }}_n$ be their empirical measures based on independent samples of size $n$. We prove that $$\mathbb{E}\mid D_2^2({\widehat{\mu }}_n,{\widehat{\nu }}_n)-D_2^2(\mu ,\nu )\mid \lesssim n^{-2\mathrm{/}((d_x\wedge d_y)\vee 4)}(\log n{)}^{{\mathbf{1}}_{\{d_x\wedge d_y=4\}}}\mathrm{.}$$ This rate is sharp up to the logarithmic factor in the critical dimension. The proof is based on a geometric representation of the Euclidean distance as a squared $L^2$-distance between half-space feature maps. This yields a variational dual formulation of the Gromov-Wasserstein functional in terms of a family of classical optimal transport problems indexed by an infinite-dimensional auxiliary parameter. Although the resulting cost functions need not be semiconcave in either argument, we introduce a marginal recentering of the costs that restores the concavity structure needed for sharp metric-entropy bounds. Combining this representation with empirical-process estimates gives a rate governed by the smaller of the two ambient dimensions.