Quantitative Stability and Sample Complexity for Regularized Gromov-Wasserstein Distance
Abstract
The Gromov-Wasserstein (GW) distance provides a principled framework for comparing two probability distributions supported on different metric spaces by matching their individual intrinsic geometric structures. In practice, the GW distance is estimated from finite samples and often incorporates regularization for statistical and computational tractability. This motivates a quantitative understanding of the stability and estimation error of regularized GW distances. In this work, we study a general family of divergence regularized GW distances, including entropy and Tsallis regularizations over the full range of powers, from a nonasymptotic perspective. Specifically, we establish Lipschitz continuity of the value of regularized GW and H{ö}lder continuity of its optimal coupling under Wasserstein perturbations of the input probability measures. Moreover, we derive the parametric rate of convergence for the empirical regularized (2,2)-GW distance on compactly supported Euclidean spaces.
Related
- Quantitative QSD convergence in 1-Wasserstein distance via the Föllmer drift
- Quantitative stability of classical, entropic, and doubly entropic Wasserstein barycenters
- Continuous Dual Maximizers for Fixed-Reference Entropy-Regularized Wasserstein Barycenters
- On Over-Conservatism Under Low-Probability Extreme Events: A KL-Regularized Wasserstein Distributionally Robust Planning Method
- The p-Bures-Wasserstein distance via 3×3 block matrices (with application to p-Bures-Wasserstein barycenters)
BibTeX
@misc{li2026quantitative,
title = {{Quantitative Stability and Sample Complexity for Regularized Gromov-Wasserstein Distance}},
author = {Pengtao Li and Xiaohui Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14562},
eprint = {2610.14562},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14562},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantitative Stability and Sample Complexity for Regularized Gromov-Wasserstein Distance
AU - Pengtao Li
AU - Xiaohui Chen
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14562
UR - https://arxiv.org/abs/2610.14562
AB - The Gromov-Wasserstein (GW) distance provides a principled framework for comparing two probability distributions supported on different metric spaces by matching their individual intrinsic geometric structures. In practice, the GW distance is estimated from finite samples and often incorporates regularization for statistical and computational tractability. This motivates a quantitative understanding of the stability and estimation error of regularized GW distances. In this work, we study a general family of divergence regularized GW distances, including entropy and Tsallis regularizations over the full range of powers, from a nonasymptotic perspective. Specifically, we establish Lipschitz continuity of the value of regularized GW and H{ö}lder continuity of its optimal coupling under Wasserstein perturbations of the input probability measures. Moreover, we derive the parametric rate of convergence for the empirical regularized (2,2)-GW distance on compactly supported Euclidean spaces.
ER -