A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport
Abstract
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.
Related
- A provably convergent MM-GKS variant for large-scale inverse problems
- Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
- Wasserstein mirror gradient flow as the limit of the Sinkhorn algorithm
- Dynamic Generalized Gromov-Wasserstein Optimal Transport
- A practical DIRECT-type algorithm for medium-scale black-box global optimization
BibTeX
@misc{liang2026provably,
title = {{A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport}},
author = {Ling Liang and Lei Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.04175},
eprint = {2605.04175},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.04175},
}
RIS
TY - UNPB
TI - A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport
AU - Ling Liang
AU - Lei Yang
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2605.04175
UR - https://arxiv.org/abs/2605.04175
AB - 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.
ER -