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{\"o}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.