Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems

Joanna Marks; Gabriel Rioux; Riccardo Passeggeri

cs.LGSep 25, 2026

Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems

Authors: Joanna Marks, Gabriel Rioux, Riccardo Passeggeri

Organizations: ⋆Denotes equal contribution to this work.

Abstract

The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.

Figures & tables

Figure 1. Convergence of AMD ( Algorithm 1 ) for $\alpha\in\{0.1,0.5,0.9,1\}$ ( $\alpha=1$ recovering classical MD ), and the dual gradient method ( Algorithm 2 ) across three datasets, which are visualized in the left-most panel. Primal stationarity records $\|x_{j}-\tilde{x}_{j}\|_{1}^{2}$ for AMD . Dual stationarity records $\|u_{j}-u_{j+1}\|^{2}$ for simple variational methods: Variational (1) and Variational ( $L$ ), and $\|u_{j}-z_{j}\|^{2}$ for Accelerated ( $L$ ) where $z_{j}$ is a second sequence used for momentum (see Algorithm 2 in [ 27 ] ). The right-most plot shows the corresponding EGW value. In both stationarity panels, solid lines show the per-iteration value and dotted lines its running minimum, with the $O(1/j)$ rate overlaid in black. Solid lines report the geometric mean for stationarity and the arithmetic mean for the objective over $10$ seeds; shaded regions indicate one standard deviation in log and non-log space respectively.

	Gaussian mixture		Sphere		Gaussian-ring
Method	Runtime (s)	Conv.	Runtime (s)	Conv.	Runtime (s)	Conv.
AMD ( $\alpha=0.1$ )	$38.2\pm 13.1$	$10/10$	$0.62\pm 0.49$	$10/10$	$9.42\pm 3.39$	$8/10$
AMD ( $\alpha=0.5$ )	$7.69\pm 2.74$	$10/10$	$0.117\pm 0.090$	$10/10$	$4.66\pm 3.76$	$9/10$
AMD ( $\alpha=0.9$ )	$4.19\pm 1.55$	$10/10$	$0.061\pm 0.048$	$10/10$	$7.85\pm 6.18$	$6/10$
AMD ( $\alpha=1$ )	$3.66\pm 1.41$	$10/10$	$0.054\pm 0.042$	$10/10$	$15.10\pm 3.19$	$0/10$
Variational (1)	$9.06\pm 2.94$	$10/10$	$0.128\pm 0.113$	$10/10$	$106.1\pm 57.8$	$10/10$

Table 1. Mean solver wall-clock runtime in seconds (

\pm

one standard deviation) over 10 seeds as well as the number of runs that reached the prescribed tolerance before reaching the maximum number of iterations. The measured runtime does not include the set up needed for the methods and in particular does not take into account the cost decompositions needed for both methods (for details see Section C.2 ).

Figure 2. Results for the non-CNT example adapted from [ 15 ] . The plots track primal stationarity (

\|x_{j}-\tilde{x}_{j}\|_{1}^{2}

) for AMD for

\alpha\in\{0.1,0.5,0.9,1\}

, dual stationarity (

\|u_{j}-u_{j+1}\|^{2}

) for Variational (1) and Variational (L), the EGW value and the lag-two difference between couplings at each iteration i.e.

\|x_{j}-x_{j+2}\|

for all methods. The dotted line denotes the

O(1/j)

reference curve. The top block shows the results for

\varepsilon=0.01

and the bottom for

\varepsilon=0.1

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Data	$\varepsilon$	$J_{\text{outer}}$	$J_{\text{inner}}$	Inner stepsize	Sinkhorn method
Gaussian mixture	$0.1$	$10\,000$	$100$	$0.5$	sinkhorn_knopp
Sphere	$0.01$	$10\,000$	$100$	$0.5$	sinkhorn_knopp
Gaussian-ring	$1$	$300$	$200$	$0.05$	sinkhorn_epsilon_scaling

Appendix

Table 2. Settings for the experiments.

J_{\mathrm{outer}}

is the total number of iterations used for AMD ( Algorithm 1 ) and the dual gradient method ( Algorithm 2 ).

J_{\mathrm{inner}}

is the maximum number of gradient ascent iterations used to solve each convex quadratic subproblem in Algorithm 2 and inner stepsize refers to the stepsize used for this gradient ascent algorithm. Sinkhorn method refers to what method was used to solve the EOT problems.

Figure 3. The interaction term from the EGW objective plotted for increasing number of iterations computed using the outputs of AMD for

\alpha\in\{0.1,0.5,0.9,1\}

and the Variational (1) method.

Method	Quantity	Gaussian mixture	Sphere
AMD	$\alpha$	$(3.30\pm 0.53)\times 10^{-4}$	$(1.53\pm 0.42)\times 10^{-3}$
Variational ( $L$ )	$L_{\mathrm{var}}$	$706\pm 66$	$15355\pm 10740$
Accelerated variational ( $L$ )	$L_{\mathrm{acc}}$	$704\pm 66$	$15353\pm 10740$

Appendix

Table 3. Theoretical step sizes, mean

\pm

one standard deviation over 10 seeds.

Figure 4. The primal stationarity and objective plots for AMD for $\alpha\in\{0.1,0.5,0.9,1,\text{theoretical}\}$ for the Gaussian mixture and sphere examples. The theoretical step sizes per experiment are reported in Table 3 .

Figure 5. Couplings at the final iterations for different algorithms applied to the example adapted from [ 15 ] when the intra-domain cost is set to $\|\cdot\|^{6}$ . The support points of $\mu_{0}$ are in green and those from $\mu_{1}$ are in yellow. On the left, the regularization is set to $\varepsilon=0.01$ and $\varepsilon=0.1$ on the right.

Figure 6. Couplings at the final iterations for different algorithms applied to the example adapted from [ 15 ] when the intra-domain cost is set to $\|\cdot\|^{2}$ . The support points of $\mu_{0}$ are in green and those from $\mu_{1}$ are in yellow. On the left, the regularization is set to $\varepsilon=0.01$ and $\varepsilon=0.1$ on the right

Method	Gaussian mixture	Sphere	Gaussian-ring
AMD ( $\alpha=0.1$ )	$149\pm 49$	$118\pm 9$	$200\pm 72$
AMD ( $\alpha=0.5$ )	$30.8\pm 10.0$	$23.4\pm 2.1$	$99.1\pm 77.6$
AMD ( $\alpha=0.9$ )	$17.0\pm 5.4$	$12.5\pm 1.4$	$158\pm 118$
AMD ( $\alpha=1$ )	$15.0\pm 5.0$	$11.1\pm 1.1$	$300\pm 0$
Variational (1)	$68.6\pm 21.0$	$32.2\pm 2.4$	$2458\pm 1350$
Variational ( $L$ )	$14517\pm 3407$	$20006\pm 0.5$	—

Appendix

Table 4. Mean number of Sinkhorn calls (

\pm

one standard deviation) over 10 seeds.

Explore similar work

May 14, 2026cs.LG

Distance-Matrix Wasserstein Statistics for Scalable Gromov--Wasserstein Learning

Gromov--Wasserstein (GW) distances compare graphs, shapes, and point clouds through internal distances, without requiring a common coordinate system. This invariance is powerful, but discrete GW is a nonconvex quadratic optimal transport problem and is difficult to estimate at scale. We propose \emph{Distance-Matrix Wasserstein} (DMW), a hierarchy of Wasserstein statistics comparing laws of random finite distance matrices. Rather than optimizing a global point-level alignment, DMW samples

n

points from each space, records their pairwise distances, and transports the resulting matrix laws. We prove that DMW is a relaxation and lower bound of GW, and establish a reverse approximation inequality: the GW--DMW gap is controlled by the Wasserstein error of approximating each original measure with

n

samples. Hence population DMW converges to GW as sampled subspaces become dense. We further give finite-sample bounds, including intrinsic-dimensional rates that depend on the data manifold rather than the ambient matrix dimension

\binom n2

. For scalable computation, we introduce sliced and multi-scale DMW; for

p=1

, the sliced multi-scale dissimilarity yields positive-definite exponential kernels. Experiments on synthetic metric spaces, scalability benchmarks, graph classification, and two-sample testing validate the theory and demonstrate an interpretable GW-style proxy for structural comparison.

Ao Xu, Tieru Wu

School of Artificial Intelligence Jilin University No. 2699, Qianjin Street, Chaoyang District Changchun 130012, China · Zhongguancun Academy Daniufang 2nd Ring Road, Haidian District2026 Beijing 100094, China · School of Artificial IntelligenceMay Jilin University No. 2699, Qianjin Street, Chaoyang District14 Changchun 130012, China

Gromov--Wasserstein Wasserstein Distance Metric Spaces Intrinsic Dimensionality Feature Alignment

Ask PDF

May 5, 2026cs.LG

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

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.

Ling Liang, Lei Yang

Department of Mathematics The University of Tennessee Knoxville, TN 37916, USA · School of Computer Science and Engineering Guangdong Province Key Laboratory of Computational Science Sun Yat-sen University Guangzhou, Guangdong 510275, China

Gromov--Wasserstein Convergence Nonconvex

Ask PDF

Jun 26, 2026cs.LG

Difference of Convex Programming in the Wasserstein Space with Applications to MMD Optimization

Optimizing functionals over the space of probability measures is now ubiquitous in machine learning. A widely used approach is to perform the optimization directly over the Wasserstein space, but many objective functionals of practical interest are non-convex along Wasserstein geodesics, making the analysis of standard first-order methods challenging. In this work, we study a class of objectives over the Wasserstein space that admit a difference-of-convex (DC) decomposition and we lift the classical convex-concave procedure (CCCP) to this setting. Under smoothness and strong convexity assumptions on the convex components of the decomposition, we prove almost stationarity along the iterates of the resulting algorithm. Our main focus is on the Maximum Mean Discrepancy (MMD) and the Energy Distance (ED) functionals, for which we develop explicit Wasserstein DC decompositions, and establish local convergence of the scheme under mild assumptions. Empirically, we show that well-chosen DC decompositions yield faster and more stable convergence than Wasserstein gradient descent on these MMD objectives.

Clément Bonet, Pierre-Cyril Aubin-Frankowski, Youssef Mroueh

CMAP, CNRS, Ecole Polytechnique, IP Paris · CERMICS, CNRS, ENPC, IP Paris · IBM Research

Wasserstein Distance Maximum Mean Discrepancy Convex Optimization Nonconvex Gradient Descent

Ask PDF