# A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport

arXiv: https://arxiv.org/abs/2605.04175 · HTML: https://mlsanity.com/paper/2605.04175/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 5 May 2026.

## Builds on (most cited first, 24 of 24)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Semidefinite Relaxations of the Gromov-Wasserstein Distance](https://mlsanity.com/paper/2312.14572/) (2023)
- [A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1809.04249/) (2018)
- [Bregman Proximal Point Algorithm Revisited: A New Inexact Version and its Inertial Variant](https://mlsanity.com/paper/2105.10370/) (2021)
- [An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming](https://mlsanity.com/paper/1903.09546/) (2019)
- [An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems](https://mlsanity.com/paper/2011.14312/) (2020)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-quadratic Regularized Optimal Transport Problems](https://mlsanity.com/paper/2311.01976/) (2023)
- [PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport](https://mlsanity.com/paper/2407.19689/) (2024)
- [An Inexact Augmented Lagrangian Method for Second-order Cone Programming with Applications](https://mlsanity.com/paper/2010.08772/) (2020)
- [A Sparse Smoothing Newton Method for Solving Discrete Optimal Transport Problems](https://mlsanity.com/paper/2311.06448/) (2023)
- [HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems](https://mlsanity.com/paper/2408.00598/) (2024)
- [Accelerating Multi-Block Constrained Optimization Through Learning to Optimize](https://mlsanity.com/paper/2409.17320/) (2024)
- [ripALM: A Relative-Type Inexact Proximal Augmented Lagrangian Method for Linearly Constrained Convex Optimization](https://mlsanity.com/paper/2411.13267/) (2024)

## Built on by (most cited first, 1 of 1)

- [Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning](https://mlsanity.com/paper/2610.04264/) (2026)

## Abstract (arXiv)

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.