提出可证明收敛的近似投影梯度法，解决大规模图-沃尔瑟斯坦匹配难题。
A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport
- 设计基于可行性残差的可验证近似投影条件，实现可计算的近似解。
- 在温和容差衰减条件下，保证整个迭代序列收敛到驻点。
- 保持算法简洁稀疏性，适合大规模图结构对齐任务。
图-沃尔瑟斯坦最优传输（GWOT）通过匹配域内关系结构来对齐度量测空间，但大规模GWOT仍具挑战性，因其目标函数非凸，且运输多面体上的投影通常仅近似求解，导致实际投影梯度方法与收敛理论之间存在差距，后者通常假设精确投影。针对平方损失下的GWOT，本文提出一种不精确投影梯度框架，采用基于可行性残差的可验证不精确条件处理投影子问题。该条件可直接计算，避免依赖未知量如精确投影点。在此可实施条件下，我们证明了子序列收敛至驻点；在温和容差衰减条件下，全序列也收敛。所提方法保持了投影梯度方案的简洁性与稀疏性，同时提供严格收敛保证，使投影梯度法成为具有可证明可靠性的可扩展GWOT求解方案。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。