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

• URL: http://arxiv.org/abs/2605.04175v1
• Date: Tue, 05 May 2026 18:12:39 GMT
• Title: A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport
• Abstract summary: We show that Gromov-Wasserstein optimal transport (GWOT) aligns measure spaces by matching their within-domain structures.<n>Under implementable condition, we prove subsequential convergence to stationary points and, with a tolerance-decay condition, convergence retains and sparsity projected-gradient schemes.
• Score: 6.6892406473287105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 papers

• Convex Distance Operator Transport: A Convex and Geometry-Preserving Formulation [9.94046521985351]
  We introduce Convex Distance Transport Operator (CDOT), the first convex optimal transport framework that aligns distributions across heterogeneous domains.<n>CDOT employs an operator-based regularization that aligns aggregated distance structures by introducing distance and conditional expectation operators.
  arXiv  Detail & Related papers  (2026-06-01T10:38:09Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method [21.498979629454286]
  We propose a trust-region interior-point sequential quadratic programming (TR-IP-SSQP) method for solving optimization problems with an objective and deterministic nonlinear equality and inequality constraints.<n>We implement the method on a subset of problems from theCutest test set, as well as on logistic regression problems, to demonstrate its practical performance.
  arXiv  Detail & Related papers  (2026-03-10T21:03:33Z)
• The Theory and Practice of MAP Inference over Non-Convex Constraints [11.058494098615576]
  In safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints.<n>This makes computing this constrained maximum a posteriori (MAP) prediction efficiently and reliably extremely challenging.<n>We devise a scalable message-passing algorithm for this tractable fragment.<n>Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions.
  arXiv  Detail & Related papers  (2026-02-09T14:05:58Z)
• Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods [7.061954653503474]
  Differentially rigorous gradient descent (DP-SGD) has become the standard algorithm for machine learning models with privacy guarantees.<n>We show that despite its widespread expectation of convergence, the algorithm remains in both convex nonwise regimes.
  arXiv  Detail & Related papers  (2025-11-20T17:42:40Z)
• Optimization Guarantees for Square-Root Natural-Gradient Variational Inference [16.89312441692349]
  This paper establishes convergence guarantees for variational-Gaussian inference and its continuous-time gradient flow.<n>Experiments demonstrate the effectiveness of natural gradient methods and highlight their advantages over algorithms that use Euclidean or Wasserstein geometries.
  arXiv  Detail & Related papers  (2025-07-10T15:33:28Z)
• SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid 3D Registration [77.13381026159111]
  We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration.<n>The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
  arXiv  Detail & Related papers  (2024-05-30T15:55:04Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP) This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
  arXiv  Detail & Related papers  (2020-06-12T20:40:22Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  We propose a new distribution alignment method based on a log-likelihood ratio statistic and normalizing flows. We experimentally verify that minimizing the resulting objective results in domain alignment that preserves the local structure of input domains.
  arXiv  Detail & Related papers  (2020-03-26T22:10:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.