betaFeedback

WorksMathematics

The Rate of Convergence of Empirical (p,q)(p,q)-Gromov-Wasserstein Distances

Abstract

We study empirical convergence rates for (p,q)(p,q)-Gromov-Wasserstein (GW) distances Dp,qD_{p,q} for arbitrary real exponents p>0p>0 and q≥1q\ge1. Let μμ and νν be probability measures on compact metric spaces X\mathcal{X} and Y\mathcal{Y}, and let μ^n\widehatμ_n and ν^m\widehatν_m be their empirical measures, constructed from independent i.i.d. samples of sizes nn and mm. If the spaces X, Y\mathcal{X},\,\mathcal{Y} are compact subsets of the Euclidean spaces Rdx\mathbb{R}^{d_x} and Rdy\mathbb{R}^{d_y}, respectively, we obtain an upper bound of order (n∧m)−(p∧2)/((dx∧dy)∨2(p∧2))(n\wedge m)^{-(p\wedge2)/((d_x\wedge d_y)\vee 2(p\wedge2))} on the plug-in error of Dp,qp(μ^n,ν^m)D_{p,q}^p(\widehatμ_n,\widehatν_m) in expectation, up to a logarithmic factor at the critical dimension dx∧dy=2(p∧2)d_x\wedge d_y=2(p\wedge2). On Euclidean balls, this rate is sharp up to the logarithmic factor. More generally, we show that the same upper bound holds when one space is a compact subset of a complete, connected dd-dimensional Riemannian manifold and the other has polynomial covering numbers, with dx∧dyd_x\wedge d_y replaced by dd. Earlier works on (2,2)(2,2)-GW, (2,1)(2,1)-GW and other even-order cases rely on variational representations of GW distances that are specific to their exponents. We instead reduce the plug-in error to an analysis of empirical processes through local duality, which may be of independent interest.

Introduction

Let (X,dX,μ)(\mathcal{X}, d_{\mathcal{X}}, \mu) and (Y,dY,ν)(\mathcal{Y}, d_{\mathcal{Y}}, \nu) be compact metric measure spaces. Given p,q>0p, q > 0, the (p,q)(p,q)-Gromov–Wasserstein (GW) distance Dp,q(μ,ν)D_{p,q}(\mu,\nu), also called the Lp,qL^{p,q}-distortion distance [20], is defined as

Dp,q(μ,ν)=(inf⁡π∈Π(μ,ν)∬(X×Y)2∣dX(x,x′)q−dY(y,y′)q∣p dπ(x,y) dπ(x′,y′))1/p,(1)D_{p,q}(\mu,\nu) = \left(\inf_{\pi\in\Pi(\mu,\nu)} \iint_{(\mathcal{X}\times\mathcal{Y})^2} \left|d_{\mathcal{X}}(x,x')^q-d_{\mathcal{Y}}(y,y')^q\right|^p \,d\pi(x,y)\,d\pi(x',y')\right)^{1/p}, \tag*{(1)}

where Π(μ,ν)\Pi(\mu,\nu) is the set of couplings of μ\mu and ν\nu. The (p,q)(p,q)-GW distance extends the pp-GW distance [Mém11], introduced by Mémoli as an LpL^p relaxation of the Gromov–Hausdorff distance, by raising the pairwise distances in the integrand to a power qq. As is known for the pp-GW distance [Mém11, Theorem 5.1(a)], (p,q)(p,q)-GW defines a metric on the collection of isomorphism classes of compact metric measure spaces when p≥1p \ge1.

The authors are listed in alphabetical order.

*Department of Statistics, University of Chicago. Email: [email protected].

†Committee on Computational and Applied Mathematics, University of Chicago. Email: [email protected].

‡Committee on Computational and Applied Mathematics, University of Chicago. Email: [email protected].

Given the empirical measures

μ^n=1n∑i=1nδXi,ν^m=1m∑j=1mδYj(2)\widehat{\mu}_n=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_i},\qquad\widehat{\nu}_m=\frac{1}{m}\sum_{j=1}^{m}\delta_{Y_j} \tag*{(2)}

constructed from independent i.i.d. samples X1,…,Xn∼μX_1,\ldots,X_n \sim\mu and Y1,…,Ym∼νY_1,\ldots,Y_m \sim\nu, a slight modification of the proof of Mémoli [Mém11, Theorem 5.1(e)] shows that Dp,q(μ^n,ν^m)→Dp,q(μ,ν)D_{p,q}(\widehat{\mu}_n,\widehat{\nu}_m) \to D_{p,q}(\mu,\nu) almost surely as n,m→∞n,m \to\infty, for all p,q>0p,q > 0. The aim of this paper is to quantify the rate of this convergence. We are interested in nonasymptotic bounds of the form

E∣Dp,qp(μ^n,ν^m)−Dp,qp(μ,ν)∣≤Cr(n∧m),(3)\mathbb{E}\left|D_{p,q}^{p}(\widehat{\mu}_n,\widehat{\nu}_m)-D_{p,q}^{p}(\mu,\nu)\right|\leq C r(n\wedge m), \tag*{(3)}

where CC depends only on pp, qq and the two spaces, and r(n∧m)→0r(n\wedge m) \to0 as n∧m→∞n\wedge m \to\infty.

When X\mathcal{X} and Y\mathcal{Y} are finite, Rioux et al. [18] recently established a variational representation for general (p,q)(p,q)-GW and obtained bounds of the form (3) for equal sample sizes n=mn=m, with r(n)=n−1/2r(n)=n^{-1/2}.

For Euclidean compact subsets X⊂Rdx\mathcal{X}\subset\mathbb{R}^{d_x} and Y⊂Rdy\mathcal{Y}\subset\mathbb{R}^{d_y}, with p,q≥1p,q\geq1, one can obtain a bound of the form (3) by comparing (p,q)(p,q)-GW with pp-Wasserstein distances [KW25, Lemma 2.1(i)], [ZGMS24, Lemma 4.4] and applying classical rates for empirical measures in Wasserstein distance [9]. However, such an argument only yields bounds of the form (3) with r(n∧m)=(n∧m)−1/((dx∨dy)∨2p)r(n\wedge m)=(n\wedge m)^{-1/((d_x\vee d_y)\vee2p)}, up to a logarithmic factor when dx∨dy=2pd_x\vee d_y=2p. Here the exponent depends on the larger dimension dx∨dyd_x\vee d_y.

Sharper bounds, in which the exponent depends on the dimensions only through their minimum d⋆=dx∧dyd_\star=d_x\wedge d_y, have been obtained for (p,q)=(2,1)(p,q)=(2,1) [13], for (2,2)(2,2) [25], and for (2r,2k)(2r,2k) with r,kr,k positive integers [16].1 To obtain this dependence on d⋆d_\star, these works use arguments based on the lower complexity adaptation principle from optimal transport [11], where the reduction to optimal transport relies on variational representations of Dp,qpD_{p,q}^{p} specific to these exponents ([ZGMS24, Corollary 4.1]; [LOW26, Theorem 4.1 and Corollary 4.2]; [Pal26, Theorem 2.4]).

In this paper, we extend these d⋆d_\star-dependent bounds to all real p>0p>0 and q≥1q\geq1. We also go beyond the Euclidean setting by proving an upper bound when one space is a compact subset of a Riemannian manifold and the other has polynomial covering numbers. We reduce the problem to optimal transport using local duality, without a variational representation of Dp,qpD_{p,q}^{p}. We also establish a lower bound for Euclidean balls, which shows that the upper bound we obtain is sharp up to a logarithmic factor.

Setting and main results

We now state upper and lower bounds in the Euclidean setting, followed by a Riemannian extension of the upper bound. Throughout, we write a∧b=min⁡(a,b)a\wedge b=\min(a,b) and a∨b=max⁡(a,b)a\vee b=\max(a,b). For a metric space SS, let P(S)\mathcal{P}(S) denote the set of Borel probability measures on SS.

For s>0s>0, d≥1d\geq1 and n≥2n\geq2, set

ψd,s(n)={n−1/2,d<2s,n−1/2log⁡n,d=2s,n−s/d,d>2s.(4)\psi_{d,s}(n)= \begin{cases} n^{-1/2}, & d<2s,\\ n^{-1/2}\log n, & d=2s,\\ n^{-s/d}, & d>2s. \end{cases} \tag*{(4)}

Thus ψd,s(n)\psi_{d,s}(n) is of polynomial order n−s/(d∨2s)n^{-s/(d\vee2s)}, up to a logarithmic factor when d=2sd=2s.

Euclidean setting. We first consider the case where both spaces are compact subsets of Euclidean spaces. The following theorem gives an upper bound for p>0p > 0, q≥1q \ge1, where the rate exponent depends on the smaller of the ambient Euclidean dimensions, together with a lower bound on Euclidean balls. The latter applies to all p,q>0p,q > 0, including the case q<1q < 1 omitted for the upper bound, and shows that the upper bound cannot in general be improved, apart from the logarithmic factor at the critical dimension.

Theorem 1.1 (Euclidean bounds).

(a) Let p>0p > 0, q≥1q \ge1. Let X⊂Rdx\mathcal{X} \subset\mathbb{R}^{d_x} and Y⊂Rdy\mathcal{Y} \subset\mathbb{R}^{d_y} be compact, with dx,dy≥1d_x,d_y \ge1, and set d⋆:=dx∧dyd_\star:= d_x \wedge d_y. Then, for all μ∈P(X)\mu\in\mathcal{P}(\mathcal{X}), ν∈P(Y)\nu\in\mathcal{P}(\mathcal{Y}) and n,m≥2n,m \ge2,

E∣Dp,qp(μ^n,ν^m)−Dp,qp(μ,ν)∣≤C[ψd⋆,p∧2(n)+ψd⋆,p∧2(m)],(5)\mathbb{E}\left|D_{p,q}^{p}(\widehat{\mu}_n,\widehat{\nu}_m)-D_{p,q}^{p}(\mu,\nu)\right| \le C\left[\psi_{d_\star,p\wedge2}(n)+\psi_{d_\star,p\wedge2}(m)\right], \tag*{(5)}

where CC depends only on pp, qq, dxd_x, dyd_y, X\mathcal{X} and Y\mathcal{Y}. In particular, the bound is of order (n∧m)−(p∧2)/(d⋆∨2(p∧2))(n\wedge m)^{-(p\wedge2)/(d_\star\vee2(p\wedge2))}, with an additional factor log⁡(n∧m)\log(n\wedge m) when d⋆=2(p∧2)d_\star=2(p\wedge2).

(b) Let p,q>0p,q > 0 and dx,dy≥1d_x,d_y \ge1, and set d⋆:=dx∧dyd_\star:= d_x\wedge d_y. For the closed unit balls B1dx(0)B_1^{d_x}(0) and B1dy(0)B_1^{d_y}(0), there are constants c>0c > 0 and n0n_0, depending only on pp, qq and d⋆d_\star, such that, for all n,m≥n0n,m \ge n_0,

sup⁡μ∈P(B1dx(0))ν∈P(B1dy(0))E∣Dp,qp(μ^n,ν^m)−Dp,qp(μ,ν)∣≥c(n−(p∧2)/(d⋆∨2(p∧2))+m−(p∧2)/(d⋆∨2(p∧2))).(6)\sup_{\substack{\mu\in\mathcal{P}(B_1^{d_x}(0))\\ \nu\in\mathcal{P}(B_1^{d_y}(0))}}\mathbb{E}\left|D_{p,q}^{p}(\widehat{\mu}_n,\widehat{\nu}_m)-D_{p,q}^{p}(\mu,\nu)\right| \ge c\left(n^{-(p\wedge2)/(d_\star\vee2(p\wedge2))}+m^{-(p\wedge2)/(d_\star\vee2(p\wedge2))}\right). \tag*{(6)}

References

  1. [1]Daniel Berend and Aryeh Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics & Probability Letters, 83(4):1254–1259, 2013.DOI
  2. [2]E. M. Bronshtein. ε-entropy of convex sets and functions. Siberian Mathematical Journal, 17(3):393–398, 1976.DOI
  3. [3]Bernd Carl, Ioanna Kyrezi, and Alain Pajor. Metric entropy of convex hulls in Banach spaces. Journal of the London Mathematical Society, 60(3):871–896, 1999.DOI
  4. [4]P. Cannarsa and C. Sinestrari. Semiconcave Functions, Hamilton–Jacobi Equations, and Optimal Control, volume 58 of Progress in Nonlinear Differential Equations and Their Applications. Birkhäuser, Boston, 2004.DOI
  5. [5]T. Dumont, T. Lacombe, and F.-X. Vialard. On the existence of Monge maps for the Gromov–Wasserstein problem. Foundations of Computational Mathematics, 25:463–510, 2025.DOI
  6. [7]Sanjit Dandapanthula, Aleksandr Podkopaev, Shiva Prasad Kasiviswanathan, Aaditya Ramdas, and Ziv Goldfeld. Optimal transportation and alignment between Gaussian measures, 2025. arXiv:2512.03579.arxiv.org/abs/2512.03579
  7. [8]Richard M. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290–330, 1967.
  8. [9]N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162:707–738, 2015.arxiv.org/abs/1312.2128
  9. [10]Adityanand Guntuboyina and Bodhisattva Sen. Covering numbers for convex functions. IEEE Transactions on Information Theory, 59(4):1957–1965, 2013.arxiv.org/abs/1204.0147
  10. [11]S. Hundrieser, T. Staudt, and A. Munk. Empirical optimal transport between different measures adapts to lower complexity. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 60(2):824–846, 2024.arxiv.org/abs/2202.10434
  11. [12]Kengo Kato and Boyu Wang. Convergence of empirical Gromov–Wasserstein distance, 2025. arXiv:2508.03985.arxiv.org/abs/2508.03985
  12. [13]Pui Kuen Leung, Riku Okada, and Samuel Lok-Hei Wong. Sample complexity for the 2-Gromov–Wasserstein distance, 2026. arXiv:2607.27514.arxiv.org/abs/2607.27514
  13. [15]Carlo Mantegazza and Andrea Carlo Mennucci. Hamilton–Jacobi equations and distance functions on Riemannian manifolds. Applied Mathematics & Optimization, 47(1):1–25, 2003.DOI
  14. [16]Vasyl Paliy. Empirical convergence of even-order Gromov–Wasserstein functionals, 2026. arXiv:2605.11108.arxiv.org/abs/2605.11108
  15. [17]Peter Petersen. Riemannian Geometry, volume 171 of Graduate Texts in Mathematics. Springer, Cham, third edition, 2016.
  16. [18]Gabriel Rioux, Joanna Marks, Riccardo Passeggeri, and Ziv Goldfeld. Discrete Gromov–Wasserstein duality: Algorithms and isomorphism testing, 2026. arXiv:2609.03094.arxiv.org/abs/2609.03094
  17. [19]Filippo Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling, volume 87 of Progress in Nonlinear Differential Equations and Their Applications. Birkhäuser, Cham, 2015.DOI
  18. [20]Karl-Theodor Sturm. The Space of Spaces: Curvature Bounds and Gradient Flows on the Space of Metric Measure Spaces, volume 290, no. 1443 of Memoirs of the American Mathematical Society. American Mathematical Society, Providence, RI, 2023.arxiv.org/abs/1208.0434
  19. [21]Shuguang Song and Jon A. Wellner. An upper bound for uniform entropy numbers. Technical Report 406, Department of Statistics, University of Washington, 2002.
  20. [22]A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Series in Statistics. Springer, New York, 1996.
  21. [23][Vil09] Cédric Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 2009.
  22. [24][vLB04] U. von Luxburg and O. Bousquet. Distance-based classification with Lipschitz functions. Journal of Machine Learning Research, 5:669–695, 2004.
  23. [25][ZGMS24] Z. Zhang, Z. Goldfeld, Y. Mroueh, and B. K. Sriperumbudur. Gromov–Wasserstein distances: Entropic regularization, duality and sample complexity. The Annals of Statistics, 52(4):1616–1645, 2024.arxiv.org/abs/2212.12848

Paper details

vlnc:W_snfzk4he
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents