B1938
Title: Gromov-Wasserstein alignment: Statistical and computational advancements via duality
Authors: Ziv Goldfeld - Cornell University (United States) [presenting]
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 the alignment of heterogeneous datasets, including object matching, single-cell genomics, and matching language models. 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. These gaps are closed for the quadratic GW distance between Euclidean mm spaces of different dimensions. At the core of the proofs is a novel dual representation of the GW problem as an infimum of certain 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, the entropically regularized GW distance is considered. Bounds are provided on the entropic approximation gap, establish sufficient conditions for convexity of the objective, and devise the first efficient algorithms with global convergence guarantees. These advancements facilitate principled estimation and inference methods for GW alignment problems, that are efficiently computable via the said algorithms.
