Preprint

Sample Complexity for the 2-Gromov-Wasserstein Distance

Pui-Kuen Leung Riku Okada Samuel Lok-Hei Wong

Jul 2026 · 0 citations · 32 references

Mathematics

Abstract

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}\left|D_2^2(\widehat\mu_n,\widehat\nu_n)-D_2^2(\mu,\nu)\right| \lesssim n^{-2/((d_x\wedge d_y)\vee 4)} (\log n)^{\mathbf 1_{\{d_x\wedge d_y=4\}}}. \] 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.

arXiv Semantic Scholar

View source

Similar papers

Jul 2026

Level-set entropy and sparse randomized embeddings

This work develops an approach to the spectral norm of the matrix product $\Pi U_V$, based on entropy estimates for level sets of vectors $x\in V$, and shows that matching results hold for other random models with negatively associated entries.

K. Tikhomirov · arXiv.org · 0 citations

Preprint Jul 2026

A uniform bound in the dimensional Brunn--Minkowski inequality for even log-concave measures

For every $n\ge 2$, we prove that there exists an exponent $p_n$ such that, for every even log-concave probability measure $\mu$ on $\mathbb R^n$, all nonempty symmetric convex sets $K,L\subseteq\mathbb R^n$, and all $\lambda\in[0,1]$, $$ \mu(\lambda K+(1-\lambda)L)^{p_n} \ge \lambda\mu(K)^{p_n}+(1-\lambda)\mu(L)^{p_n}...

Kai-Wen Yang · 0 citations

Preprint Jul 2026

Dimension-free cotype for isotropic log-concave random polytope spaces

Let $X_1,\ldots,X_N$ be independent random vectors in $\mathbb{R}^n$ with common isotropic log-concave distribution $\mu$ and set $P_{N,n}^{\mu}:=\operatorname{conv}\{\pm X_i:1\leqslant i\leqslant N\}$. Assume that $N/n=\gamma\geqslant \gamma_0$ where $\gamma_0>1$ is an absolute constant. We prove that with probability...

Antonios Hmadi · 0 citations

Preprint Aug 2026

Sharp Convex Concentration for Symmetric Random Tensors with Subgaussian Coordinates

Let $X=(X_1,\ldots,X_n)$ have independent coordinates with mean zero, variance one, and $\|X_i\|_{\psi_2}\le K$, and let $H_d=(\mathbb R^n)^{\otimes_2 d}$. Let $L>0$ and let $f:H_d\to\mathbb R$ be convex and $L$-Lipschitz. We prove that, for $0\le t\le c_KLn^{d/2}$, \[ \textsf{P}\left\{ \left\lvert f(X^{\otimes d})-\te...

Xuan-Ang Hu · 0 citations

Preprint Aug 2026

Sharp $\ell^p$-Improving Estimates for Fixed-Radius Discrete Spherical Averages

Let $d\geq 4$ and let $R>0$. When $d=4$, assume that $R^2\in\mathbb{N}\setminus 4\mathbb{N}$; when $d\geq 5$, let $R^2\in\mathbb{N}$ be arbitrary. We prove the fixed-radius estimate $$\|A_R f\|_{\ell^{p'}(\mathbb{Z}^d)}\leq C_{d,p,\varepsilon}R^{-d(2/p-1)+\varepsilon}\|f\|_{\ell^p(\mathbb{Z}^d)}$$ for $(d+2)/d\leq p\le...

Rui Han, Fan Yang · 0 citations

Preprint Jul 2026

Well-invertible column subsets of sparse matrices are rare

A random $n\times k$ matrix $S$ is an \emph{$(r,\alpha)$-oblivious subspace injection} (OSI) if $\mathbb{E}\|S^\top x\|_2^2=\|x\|_2^2$ for every $x\in\mathbb{R}^n$, and for every fixed $r$-dimensional subspace $V\subset\mathbb{R}^n$, with probability close to one, one has $\alpha\|x\|_2^2\le\|S^\top x\|_2^2$ for all $x...

Han Huang, M. Rudelson, Konstantin E. Tikhomirov · 1 citation · ⚡1