A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport
For practitioners using GWOT, this work provides rigorous convergence guarantees for a simple and scalable projected-gradient method, bridging theory and practice.
The paper addresses the convergence gap between practical projected-gradient implementations and theory for Gromov--Wasserstein optimal transport (GWOT). It proposes an inexact projected-gradient framework with a verifiable condition that ensures subsequential convergence to stationary points and, under mild conditions, full sequence convergence.
Gromov--Wasserstein optimal transport (GWOT) aligns metric measure spaces by matching their within-domain relational structures, but large-scale GWOT remains challenging because its objective is nonconvex and projection onto the transport polytope is often solved only approximately in practice. This leads to a gap between practical projected-gradient implementations and convergence theory, which typically assumes exact projections. For squared-loss GWOT, we propose an inexact projected-gradient framework with a verifiable feasibility-residual-based inexact condition for the projection subproblem. This condition is directly computable and avoids unknown quantities such as the exact projection point. Under this implementable condition, we prove subsequential convergence to stationary points and, with a mild tolerance-decay condition, convergence of the whole sequence. The resulting method retains the simplicity and sparsity of projected-gradient schemes while providing rigorous convergence guarantees, turning projected-gradient methods into a principled and scalable approach for GWOT with provable reliability.