Gromov-Wasserstein Distances: Entropic Regularization, Duality, and Sample Complexity

Zhengxin Zhang, Ziv Goldfeld, Youssef Mroueh, Bharath SriperumbudurThe Annals of Statistics 2022 · DOI · OpenReview

TL;DR

This paper introduces a novel duality framework for Gromov-Wasserstein (GW) distances, bridging the gap between theoretical properties and practical statistical analysis. This breakthrough enables the derivation of the first sharp convergence rates for GW distances, matching those of simpler optimal transport problems and providing crucial insights into their behavior.

What Problem Does This Paper Address?

The Gromov-Wasserstein (GW) distance is a powerful tool for measuring the dissimilarity between metric measure spaces, finding applications in areas like aligning heterogeneous datasets. While its computational aspects have been explored, fundamental statistical questions, particularly regarding how well GW distances estimated from data converge to their true values (sample complexity), remained largely unanswered. This was primarily due to the complex, quadratic nature of the GW functional, which prevented the direct application of well-established statistical techniques from optimal transport (OT). This paper aims to fill this gap by developing a duality theory for GW distances, which then allows for the application of these powerful statistical tools.

Methods

The core of this work lies in deriving dual formulations for both the standard and entropically regularized Gromov-Wasserstein (GW) distances. This is achieved by introducing an auxiliary matrix-valued variable that linearizes the quadratic terms in the GW functional. This linearization cleverly transforms the GW problem into a form that can be related to the well-understood duals of standard Optimal Transport (OT) and Entropic Optimal Transport (EOT) problems.

Leveraging these dual forms, the authors employ techniques from statistical OT, specifically empirical process theory. This involves analyzing the behavior of optimal dual potentials and using their regularity properties to bound estimation errors. For the entropically regularized GW (EGW) distance, they establish parametric convergence rates ($n^{-1/2}$), which are shown to be optimal. For the standard GW distance, they derive upper bounds and, importantly, matching lower bounds, demonstrating the sharpness of their results. The paper also investigates the stability of EGW with respect to its regularization parameter and sheds light on the one-dimensional GW distance problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and derives convergence rates for probability distributions in Euclidean spaces, rather than empirical datasets.

Key Insights and Ideas

  • Duality Unlocks Statistical Analysis: The most significant insight is that by reformulating GW distances through duality, we can finally apply the powerful statistical tools developed for OT. This is a major step towards a comprehensive statistical theory for GW.
  • GW Rates Match Simpler OT: The derived convergence rates for GW distances ($n^{-2/\max\{\min\{d_x,d_y\},4\}}$ for standard GW and $n^{-1/2}$ for EGW) are surprisingly similar to those for standard OT and EOT. This suggests that the added complexity of GW doesn't fundamentally hinder statistical estimation in the same way as computational complexity.
  • Sharpness of Rates: The paper not only provides upper bounds for GW convergence rates but also establishes matching lower bounds, proving that these rates are indeed the best possible.
  • One-Dimensional GW Mystery Solved (Partially): The duality framework provides new insights into the long-standing problem of the one-dimensional GW distance, explaining why identity and anti-identity permutations might not always be optimal.

Key Results

  • First GW Empirical Convergence Rates: The paper establishes the first theoretical guarantees for the statistical convergence of GW distances.
  • Optimal Rates for EGW: The entropically regularized GW (EGW) distance achieves a parametric rate of $n^{-1/2}$ for two-sample estimation, matching the optimal rates for EOT.
  • Sharp Rates for Standard GW: The standard GW distance achieves a rate of $n^{-2/\max\{\min\{d_x,d_y\},4\}}$ (with a log factor for specific dimensions), and matching lower bounds are provided.
  • Stability and Continuity: The paper analyzes the stability of EGW with respect to its regularization parameter $\varepsilon$, showing an $O(\varepsilon \log(1/\varepsilon))$ approximation gap.

Limitations and Future Work

  • General (p,q)-GW Duality: While the paper focuses on the (2,2)-GW distance, extending the duality theory to general (p,q)-GW distances remains an open challenge.
  • Non-Euclidean Spaces: The current framework is for Euclidean spaces. Extending the duality and statistical analysis to non-Euclidean metric measure spaces (e.g., graphs, manifolds) is a significant future direction.
  • Unbounded Domains: While EGW analysis extends to some unbounded domains under specific conditions (4-sub-Weibull), a more general treatment for standard GW on unbounded domains would be valuable.
  • Algorithmic Advancements: The authors suggest that their duality framework can be used to develop new and efficient algorithms for computing GW and EGW distances.
  • Refining Rates: For standard GW, while the rates are sharp, there might be possibilities to improve constants or remove log factors in specific cases.

Summary updated

Abstract

The Gromov-Wasserstein (GW) distance, rooted in optimal transport (OT) theory, quantifies dissimilarity between metric measure spaces and provides a framework for aligning heterogeneous datasets. While computational aspects of the GW problem have been widely studied, a duality theory and fundamental statistical questions concerning empirical convergence rates remained obscure. This work closes these gaps for the quadratic GW distance over Euclidean spaces of different dimensions $d_x$ and $d_y$. We treat both the standard and the entropically regularized GW distance, and derive dual forms that represent them in terms of the well-understood OT and entropic OT (EOT) problems, respectively. This enables employing proof techniques from statistical OT based on regularity analysis of dual potentials and empirical process theory, using which we establish the first GW empirical convergence rates. The derived two-sample rates are $n^{-2/\max\{\min\{d_x,d_y\},4\}}$ (up to a log factor when $\min\{d_x,d_y\}=4$) for standard GW and $n^{-1/2}$ for entropic GW (EGW), which matches the corresponding rates for standard and entropic OT. The parametric rate for EGW is evidently optimal, while for standard GW we provide matching lower bounds, which establish sharpness of the derived rates. We also study stability of EGW in the entropic regularization parameter and prove approximation and continuity results for the cost and optimal couplings. Lastly, the duality is leveraged to shed new light on the open problem of the one-dimensional GW distance between uniform distributions on $n$ points, illuminating why the identity and anti-identity permutations may not be optimal. Our results serve as a first step towards a comprehensive statistical theory as well as computational advancements for GW distances, based on the discovered dual formulations.
BibTeX
@article{zhang2022gromov,
  author = {Zhengxin Zhang and Ziv Goldfeld and Youssef Mroueh and Bharath Sriperumbudur},
  title = {{Gromov-Wasserstein Distances: Entropic Regularization, Duality, and Sample Complexity}},
  journal = {The Annals of Statistics},
  year = {2022},
  doi = {10.48550/arxiv.2212.12848},
}

Loading related content...

Figure