Entropic Gromov-Wasserstein Distances: Stability and Algorithms
Preprint
Abstract
The Gromov-Wasserstein (GW) distance quantifies discrepancy between metric measure spaces and provides a natural framework for aligning heterogeneous datasets. Alas, as exact computation of GW alignment is NP hard, entropic regularization provides an avenue towards a computationally tractable proxy. Leveraging a recently derived variational representation for the quadratic entropic GW (EGW) distance, this work derives the first efficient algorithms for solving the EGW problem subject to formal, non-asymptotic convergence guarantees. To that end, we derive smoothness and convexity properties of the objective in this variational problem, which enables its resolution by the accelerated gradient method. Our algorithms employs Sinkhorn's fixed point iterations to compute an approximate gradient, which we model as an inexact oracle. We furnish convergence rates towards local and even global solutions (the latter holds under a precise quantitative condition on the regularization parameter), characterize the effects of gradient inexactness, and prove that stationary points of the EGW problem converge towards a stationary point of the unregularized GW problem, in the limit of vanishing regularization. We provide numerical experiments that validate our theory and empirically demonstrate the state-of-the-art empirical performance of our algorithm.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- The Space of Spaces: Curvature Bounds and Gradient Flows on the Space of Metric Measure SpacesMemoirs of the American Mathematical Society, 2023
- Gromov–Wasserstein distances between Gaussian distributionsJournal of Applied Probability, 2022
- SCOT: Single-Cell Multi-Omics Alignment with Optimal TransportJournal of Computational Biology, 2022
- Accelerated gradient methods for nonconvex nonlinear and stochastic programmingMathematical Programming, 2015
- Local Minimization, Variational Evolution and Γ-Convergence2014
- First-order methods of smooth convex optimization with inexact oracleMathematical Programming, 2013
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Templates for convex cone problems with applications to sparse signal recoveryMathematical Programming Computation, 2011
- Gromov–Wasserstein Distances and the Metric Approach to Object MatchingFoundations of Computational Mathematics, 2011
- Functional Analysis, Sobolev Spaces and Partial Differential Equations2011