Research map / Learning theory and algorithms / Optimal transport
A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an inexact projected-gradient method (iPG) for squared-loss Gromov–Wasserstein OT whose projection subproblems are stopped using a computable primal feasibility residual, proving subsequential and whole-sequence convergence to stationary points.
Problem
Projected-gradient methods for nonconvex Gromov–Wasserstein optimal transport are used in practice with approximate projections onto the transport polytope, but convergence theory assumes exact projections.
Approach
Replace the exact projection requirement with a verifiable inexact condition based on the primal feasibility residual of the dual iterate, scaled by 1+||y||, and prove convergence under summable tolerances (plus a tolerance-decay condition for whole-sequence convergence) via a Hoffman error bound and KL property.
Key results
- iPG attains among the smallest GW losses across graph alignment sizes while keeping feasibility residuals extremely small.
- iPG returns couplings with sparsity essentially equal to one, much sparser than entropic baselines EPGD and PPA.
- BAPG fails for small regularization and is the least robust method in the experiments.
Surprising findings
- CG yields very sparse exactly feasible couplings but worse loss and alignment accuracy than other methods.
Limitations
- Experiments limited to synthetic graph alignment with squared loss; no real-world GWOT tasks.
- Convergence guarantees are for stationary points only, not global optimality.
- Whole-sequence convergence requires an additional summability/tolerance-decay condition.
Experimental setup
Datasets: synthetic Erdős–Rényi graphs with permuted and edge-flipped copies
Benchmarks: synthetic graph alignment instances (n=100 to 500)
Metrics: GW loss constraint violation sparsity alignment accuracy (Hungarian matching) runtime
Baselines: CG PPA EPGD BAPG
Builds on: projected gradient descent Kurdyka-Lojasiewicz framework entropic projected gradient (EPGD) Bregman alternating projected gradient (BAPG)
Closest papers by meaning
- Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem (NeurIPS 2026 · similarity 0.90)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.89)
- Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows (ICML 2025 · similarity 0.88)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.88)
- Generalized Wasserstein Flow Matching: Transport Plans, Everywhere, All at Once (NeurIPS 2026 · similarity 0.87)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.