Gromov–Wasserstein Alignment: Statistical and Computational Advancements via Duality
Open access
Author
Date
2024-03-06Type
- Other Conference Item
ETH Bibliography
no
Altmetrics
Abstract
The Gromov-Wasserstein (GW) distance quantifies dissimilarity between metric measure (mm) spaces and provides a natural correspondence between them. As such, it serves as a figure of merit for applications involving alignment of heterogeneous datasets, including object matching, single-cell genomics, and language models translation. While various heuristic methods for approximately evaluating the GW distance from data have been developed, formal guarantees for such approaches—both statistical and computational—remained elusive. This work closes these gaps for the quadratic GW distance between Euclidean mm spaces of different dimensions. At the core of our proofs is a novel dual representation of the GW problem as an infimum of a certain class of optimal transportation problems. The dual form enables deriving, for the first time, sharp empirical convergence rates for the GW distance by providing matching upper and lower bounds. For computational tractability, we consider the entropically regularized GW distance. We derive bounds on the entropic approximation gap, establish sufficient conditions for smoothness and convexity of the objective in the dual problem, and devise efficient algorithms with local and, under convexity, even global convergence guarantees. These advancements facilitate principled estimation and inference methods for GW alignment problems, that are efficiently computable via the said algorithms. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000664604Publication status
publishedBook title
International Zurich Seminar on Information and Communication (IZS 2024). ProceedingsPages / Article No.
Publisher
ETH ZurichEvent
Organisational unit
02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.
Related publications and datasets
Is part of: https://doi.org/10.3929/ethz-b-000664209
Notes
Extended abstractMore
Show all metadata
ETH Bibliography
no
Altmetrics