Empirical Convergence of Even-Order Gromov-Wasserstein Functionals

Vasyl Paliy

arxiv: 2605.11108 · v2 · submitted 2026-05-11 · 🧮 math.PR · math.ST· stat.TH

Empirical Convergence of Even-Order Gromov-Wasserstein Functionals

Vasyl Paliy This is my paper

Pith reviewed 2026-05-14 20:56 UTC · model grok-4.3

classification 🧮 math.PR math.STstat.TH

keywords Gromov-Wasserstein distanceempirical convergencesample complexityoptimal transporteven-order functionalscompactly supported measuresEuclidean spaces

0 comments

The pith

The two-sample empirical error for powered even-order Gromov-Wasserstein functionals converges at rate n to the power of -2 over max of min dimensions and 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that for any fixed integers r and k at least 1, the error when estimating the powered even-order Gromov-Wasserstein distance from two samples of size n is bounded by n to the power of negative 2 over the maximum of the minimum of the two dimensions and 4, with a logarithmic factor only when that minimum dimension equals exactly 4. The result applies to any pair of probability measures with compact support in Euclidean spaces of dimensions d_x and d_y. A sympathetic reader would care because the bound shows how many samples are needed to approximate these distances reliably, extending the known quadratic case to the entire even-order family and thereby supporting statistical use of the functionals for comparing shapes or aligning data sets.

Core claim

For every fixed pair of integers r,k ≥ 1, the two-sample empirical error for the powered even-order Gromov-Wasserstein functional is bounded at the rate n^{-2/max{min{d_x,d_y},4}}, up to a logarithmic factor in the critical case min{d_x,d_y}=4. This extends the known quadratic Euclidean upper rate to the full powered even-order family.

What carries the argument

Polynomial decomposition of the even-order GW functional together with a generalized duality formula that reduces the coupling-dependent term to a compact family of ordinary optimal transport problems, supported by entropy estimates for semiconcave dual potentials.

Load-bearing premise

The probability measures must be compactly supported on Euclidean spaces so that entropy estimates for the dual potentials and the polynomial decomposition remain valid.

What would settle it

Draw two independent samples of increasing size n from compactly supported measures in dimension 3 and measure whether the observed empirical GW error decreases exactly like n to the power -1/2; a consistently slower observed rate would falsify the claimed bound.

read the original abstract

We study the sample complexity of empirical plug-in estimation for the powered even-order Gromov-Wasserstein functional between compactly supported probability measures on $\mathbb{R}^{d_x}$ and $\mathbb{R}^{d_y}$. For every fixed pair of integers $r,k\geq 1$, we prove that the two-sample empirical error is bounded at the rate $n^{-2/\max\{\min\{d_x,d_y\},4\}}$, up to a logarithmic factor in the critical case $\min\{d_x,d_y\}=4$. This extends the known quadratic Euclidean upper rate to the full powered even-order family. The proof uses a polynomial decomposition of the even-order GW functional, a generalized duality formula reducing the coupling-dependent term to a compact family of ordinary optimal transport problems, and entropy estimates for semiconcave dual potentials.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper extends the known quadratic empirical rate for Gromov-Wasserstein to the full even-powered family via polynomial decomposition and duality reduction, with the bound n^{-2/max{min(d_x,d_y),4}} (log at 4).

read the letter

The central result here is a clean extension of sample-complexity bounds from the quadratic Gromov-Wasserstein case to the broader family of even-order powered functionals. For fixed r and k the two-sample empirical error decays at the stated rate under compact support on Euclidean spaces. The proof strategy—decomposing the functional into polynomials, reducing the coupling term to a compact collection of ordinary optimal-transport problems via generalized duality, then applying entropy bounds on semiconcave potentials—looks internally consistent and directly builds on the quadratic literature without obvious circularity or dimension-dependent gaps. That reduction step is the part that feels genuinely new and useful; it keeps the argument modular rather than reinventing everything from scratch. The compact-support assumption is standard for these entropy estimates and is stated up front, so it does not come as a surprise. The logarithmic factor at the critical dimension min{d_x,d_y}=4 is also expected from the quadratic precedent and does not weaken the claim. No load-bearing gaps appear in the outline, though without the full derivations one cannot rule out minor technical conditions on the potentials or the precise handling of the polynomial coefficients. Overall the work is technically solid for what it sets out to do. It is aimed at researchers in mathematical statistics and optimal transport who already care about statistical rates for GW-type distances; a reader outside that niche will find the result narrow but the technique reusable. I would bring it to a reading group focused on OT statistics and would cite the rate in my own work if I needed the even-order extension. It deserves a serious referee rather than a desk reject.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that for every fixed pair of integers r, k ≥ 1, the two-sample empirical error for the powered even-order Gromov-Wasserstein functional between compactly supported probability measures on R^{d_x} and R^{d_y} is bounded by the rate n^{-2 / max{min{d_x, d_y}, 4}}, up to a logarithmic factor when min{d_x, d_y} = 4. The argument proceeds by polynomial decomposition of the even-order functional, a generalized duality that reduces the coupling term to a compact family of standard optimal transport problems, and entropy estimates on semiconcave dual potentials.

Significance. If the result holds, it extends the known quadratic Euclidean upper rate to the full powered even-order family without worsening the dimension dependence. This is a meaningful contribution to the statistical theory of Gromov-Wasserstein distances, as it shows that higher even powers incur no additional sample-complexity penalty under compact support. The use of standard optimal-transport tools (duality and entropy bounds) makes the extension technically natural and potentially useful for applications involving higher-moment or robust discrepancies.

major comments (2)

[Proof strategy (abstract and §3)] The generalized duality reduction (outlined in the abstract and presumably detailed in the main proof) must ensure that the family of reduced OT problems remains compact uniformly in the polynomial coefficients arising from the even-order decomposition; otherwise the entropy estimates may acquire hidden dependence on r and k that affects the claimed rate.
[Entropy estimates section] In the critical case min{d_x, d_y} = 4, the logarithmic factor is asserted to appear; the manuscript should explicitly track where the log arises in the entropy integral (e.g., via the covering number or the semiconcavity modulus) to confirm it does not propagate into the non-critical regimes.

minor comments (2)

[Introduction] The notation for the powered functional (presumably denoted GW^{r,k} or similar) should be introduced with its precise definition in the introduction rather than deferred to the preliminaries.
[Notation and constants] Explicit dependence of all constants on the fixed parameters r and k should be stated once, even if only to record that they are absorbed into the O(·) notation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive comments on the proof strategy and entropy estimates. We have revised the manuscript to clarify the uniformity of compactness in the duality reduction and to explicitly track the origin of the logarithmic factor, thereby strengthening the presentation without altering the main results.

read point-by-point responses

Referee: [Proof strategy (abstract and §3)] The generalized duality reduction (outlined in the abstract and presumably detailed in the main proof) must ensure that the family of reduced OT problems remains compact uniformly in the polynomial coefficients arising from the even-order decomposition; otherwise the entropy estimates may acquire hidden dependence on r and k that affects the claimed rate.

Authors: We agree that uniform compactness is essential to avoid hidden parameter dependence. In the revised manuscript we have inserted a new auxiliary result (Lemma 3.3) that verifies the family of reduced cost functions remains in a compact subset of C(X×Y) uniformly over the polynomial coefficients for any fixed r,k. The argument relies on the compact support of the measures, which yields uniform bounds on the dual potentials via semiconcavity, independent of the specific coefficients. Consequently the entropy estimates retain the stated rate with no additional dependence on r or k. revision: yes
Referee: [Entropy estimates section] In the critical case min{d_x, d_y} = 4, the logarithmic factor is asserted to appear; the manuscript should explicitly track where the log arises in the entropy integral (e.g., via the covering number or the semiconcavity modulus) to confirm it does not propagate into the non-critical regimes.

Authors: We appreciate the request for explicit tracking. In the revised Section 4 we have added a detailed computation of the entropy integral. The logarithmic factor originates from the covering-number bound N(ε) ≲ ε^{-4} for the class of semiconcave functions when the dimension equals 4, causing the integral ∫_0^1 log N(ε) dε to diverge logarithmically. For dimensions strictly larger than 4 the integral remains finite without a log term, while for dimensions smaller than 4 the resulting rate is absorbed into the leading polynomial term. A new remark confirms that the log does not appear or propagate outside the critical case. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via standard OT tools

full rationale

The paper's central result is a rate bound derived from polynomial decomposition of the even-order GW functional, reduction via generalized duality to a compact family of ordinary OT problems, and entropy estimates for semiconcave dual potentials under compact support. These steps use standard optimal-transport techniques and extend the known quadratic Euclidean case without any reduction to fitted parameters, self-definitional relations, or load-bearing self-citations that would make the claimed rate equivalent to the inputs by construction. The proof strategy is internally consistent and independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard domain assumptions in optimal transport theory with no free parameters or invented entities visible from the abstract.

axioms (2)

domain assumption Measures are compactly supported probability measures on Euclidean spaces
Stated in the abstract as the setting required for boundedness and entropy estimates.
standard math Existence and regularity of semiconcave dual potentials for optimal transport problems
Invoked for the entropy estimates in the duality formula.

pith-pipeline@v0.9.0 · 5431 in / 1333 out tokens · 72336 ms · 2026-05-14T20:56:11.427307+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean; IndisputableMonolith/Foundation/AlexanderDuality.lean washburn_uniqueness_aczel; alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

polynomial decomposition of the even-order GW functional, a generalized duality formula reducing the coupling-dependent term to a compact family of ordinary optimal transport problems, and entropy estimates for semiconcave dual potentials

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Zhang, Z

Z. Zhang, Z. Goldfeld, Y. Mroueh, and B. K. Sriperumbudur. Gromov–Wasserstein distances: entropic regular- ization, duality, and sample complexity.Annals of Statistics, 52(4):1616–1645, 2024

work page 2024
[2]

Villani.Optimal Transport: Old and New

C. Villani.Optimal Transport: Old and New. Springer, 2009

work page 2009
[3]

A. W. van der Vaart and J. A. Wellner.Weak Convergence and Empirical Processes. Springer, 1996

work page 1996
[4]

R. M. Dudley. The speed of mean Glivenko–Cantelli convergence.Annals of Mathematical Statistics, 40(1):40–50, 1969

work page 1969
[5]

E. M. Bronshtein.ε-entropy of convex sets and functions.Siberian Mathematical Journal, 17(3):393–398, 1976

work page 1976
[6]

Gao and J

F. Gao and J. A. Wellner. Entropy of convex functions onR d.Constructive Approximation, 46(3):565–592, 2017

work page 2017
[7]

Hundrieser, T

S. Hundrieser, T. Staudt, and A. Munk. Empirical optimal transport between different measures adapts to lower complexity.Annales de l’Institut Henri Poincar´ e Probabilit´ es et Statistiques, 60(2):824–846, 2024

work page 2024
[8]

Manole and J

T. Manole and J. Niles-Weed. Sharp convergence rates for empirical optimal transport with smooth costs.Annals of Applied Probability, 34(1B):1108–1135, 2024

work page 2024
[9]

M. Sion. On general minimax theorems.Pacific Journal of Mathematics, 8(1):171–176, 1958

work page 1958
[10]

M´ emoli

F. M´ emoli. Gromov–Wasserstein distances and the metric approach to object matching.Foundations of Com- putational Mathematics, 11(4):417–487, 2011

work page 2011
[11]

K.-T. Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv:1208.0434, 2012. AppendixA.Generalized duality for the case(2r,2k) This appendix proves Theorem 2.4. The proof below follows the generalized duality argument of Zhang, Goldfeld, Mroueh, and Sriperumbudur [1, Appendix G]. Their ...

work page arXiv 2012

[1] [1]

Zhang, Z

Z. Zhang, Z. Goldfeld, Y. Mroueh, and B. K. Sriperumbudur. Gromov–Wasserstein distances: entropic regular- ization, duality, and sample complexity.Annals of Statistics, 52(4):1616–1645, 2024

work page 2024

[2] [2]

Villani.Optimal Transport: Old and New

C. Villani.Optimal Transport: Old and New. Springer, 2009

work page 2009

[3] [3]

A. W. van der Vaart and J. A. Wellner.Weak Convergence and Empirical Processes. Springer, 1996

work page 1996

[4] [4]

R. M. Dudley. The speed of mean Glivenko–Cantelli convergence.Annals of Mathematical Statistics, 40(1):40–50, 1969

work page 1969

[5] [5]

E. M. Bronshtein.ε-entropy of convex sets and functions.Siberian Mathematical Journal, 17(3):393–398, 1976

work page 1976

[6] [6]

Gao and J

F. Gao and J. A. Wellner. Entropy of convex functions onR d.Constructive Approximation, 46(3):565–592, 2017

work page 2017

[7] [7]

Hundrieser, T

S. Hundrieser, T. Staudt, and A. Munk. Empirical optimal transport between different measures adapts to lower complexity.Annales de l’Institut Henri Poincar´ e Probabilit´ es et Statistiques, 60(2):824–846, 2024

work page 2024

[8] [8]

Manole and J

T. Manole and J. Niles-Weed. Sharp convergence rates for empirical optimal transport with smooth costs.Annals of Applied Probability, 34(1B):1108–1135, 2024

work page 2024

[9] [9]

M. Sion. On general minimax theorems.Pacific Journal of Mathematics, 8(1):171–176, 1958

work page 1958

[10] [10]

M´ emoli

F. M´ emoli. Gromov–Wasserstein distances and the metric approach to object matching.Foundations of Com- putational Mathematics, 11(4):417–487, 2011

work page 2011

[11] [11]

K.-T. Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv:1208.0434, 2012. AppendixA.Generalized duality for the case(2r,2k) This appendix proves Theorem 2.4. The proof below follows the generalized duality argument of Zhang, Goldfeld, Mroueh, and Sriperumbudur [1, Appendix G]. Their ...

work page arXiv 2012