Source-linked AI summary
Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
Joanna Marks, Gabriel Rioux, Riccardo Passeggeri
TL;DR
Entropic GW is widely solved by Mirror Descent, but convergence guarantees are limited to restricted cost classes, while a general-cost dual method has required regularization-dependent step sizes. This paper proves convergence for arbitrary costs using averaged Mirror Descent and a fixed-step dual gradient method, accounting for inexact subproblems; empirically, AMD is comparable to Mirror Descent and the dual method is often slower.
Problem
Method
The paper introduces Averaged Mirror Descent and proves convergence for it and a fixed-step dual gradient method on arbitrary costs, accounting for inexact EOT solutions.
Source: §1 · p. 2, §7 · p. 16Results
AMD attains performance comparable to classical Mirror Descent, while the dual method takes a similar number of steps but is often slower because each iteration solves a regularized convex quadratic program instead of an EOT problem.
Source: §7 · p. 16Takeaways & Limitations
Both proposed methods converge in the Gaussian-ring example where classical Mirror Descent fails, and the dual method converges across the reported experiments.
Source: §5 · p. 10Sinkhorn does not return exact EOT solutions in finitely many steps, so AMD's practical analysis must account for inexact subproblems.
Source: §3 · p. 4
Abstract
from arXiv · showhide
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.
1. Introduction
Gromov–Wasserstein distance compares metric measure spaces through their internal structure, addressing the difficulty of choosing cross-domain transport costs. The paper introduces two convergence-guaranteed approaches for entropic GW problems with arbitrary costs, including analysis of inexact EOT solutions.
1. Introduction
- For heterogeneous datasets, a chosen transport cost may ignore relationships among objects within each domain.This motivates comparing spaces through their intrinsic structure.Source: §1 · pp. 1–2
- GW compares metric measure spaces through their intra-domain distortions and vanishes exactly when the spaces are isomorphic.Its optimal coupling can be viewed as a fuzzy alignment.Source: §1 · p. 2
- Entropic regularization makes GW practical, but its widely used Mirror Descent solver has limited convergence analysis and unaccounted-for EOT inexactness.Each Mirror Descent iteration solves an EOT problem after linearizing the objective.Source: §1 · p. 2
- Averaged Mirror Descent (AMD) averages each standard Mirror Descent step with the previous iterate, yielding a convergent arbitrary-cost variant with non-asymptotic bounds.The paper connects AMD to conditional gradient methods and includes inexact subproblem analysis.Source: §1 · p. 2
- A dual gradient method also converges for arbitrary costs with a fixed regularization-independent step size, although its iterates differ from Mirror Descent for indefinite GW costs.The paper accounts for inexact EOT resolution in both methods; the distinction between updates is linked to Mirror Descent's failures in some examples.Source: §1 · pp. 2–3
2. Optimal transport and Gromov–Wasserstein problems
The section sets up optimal transport and its entropic regularization, then formulates entropic Gromov–Wasserstein as a regularized quadratic program. Its regularization can make the problem strictly convex in EOT, while EGW is generally non-convex at the small regularization values used in applications.
2. Optimal transport and Gromov–Wasserstein problems
- Entropic regularization adds a KL-divergence penalty to OT, making the resulting EOT problem strictly convex.The penalty is defined relative to the product measure of the two marginals.Source: §2 · p. 3
- GW compares two finite metric-measure spaces using their within-space kernels, and its entropic version penalizes the GW objective with KL divergence.The section introduces this regularization as following prior EGW work.Source: §2 · p. 3
- EGW is generally non-convex unless the regularization parameter is sufficiently large, while applications use small values to approximate GW solutions.The cited convergence rate of regularized solutions to original solutions depends on whether the quadratic form is concave [16].Source: §2 · p. 3
- For finite supports, EGW can be represented as a regularized quadratic program in k = N0N1 variables subject to coupling constraints.The formulation uses a vectorized coupling and a cost matrix.Source: §2 · pp. 3–4
3. Averaged Mirror Descent
Averaged Mirror Descent (AMD) solves a linearized EOT subproblem and averages its solution with the current iterate, moderating the step relative to classical Mirror Descent. The section establishes convergence under exact and inexact EOT solutions, with the inexact error separated from the iteration-rate term.
3. Averaged Mirror Descent
- AMD averages the EOT solution of a linearized problem with the current iterate, introducing a step size that prevents excessively large steps.Classical Mirror Descent uses the same iterations with α_j = 1.Source: §3 · p. 4
- Sinkhorn iterations solve AMD's EOT subproblems in practice but do not return exact solutions in finitely many steps.The analysis therefore treats both exact and inexact subproblem solutions.Source: §3 · p. 4
3.1. Convergence under exact solutions.
- With exact EOT subproblems, AMD is analyzed as a conditional-gradient algorithm and has non-asymptotic convergence guarantees.The connection uses a smooth objective and a strongly convex regularizer.Source: §3.1 · pp. 4–5
3.2. Convergence under inexact solutions.
- A fixed number of Sinkhorn iterations can meet a desired 1-norm accuracy across AMD subproblems because their cost vectors are bounded by ∥M∥max.Sinkhorn's required iteration count depends on the accuracy, regularization, cost bound, and marginals.Source: §3.2 · p. 5
- With inexact EOT solutions, the convergence bound separates an O(1/J) optimization term from an approximation-error term.The approximation error can be made arbitrarily small as the EOT accuracy parameter decreases.Source: §3.2 · p. 5
- The inexact convergence metric is less directly interpretable than the exact-solution metric, but the analysis relates it to approximate stationarity.The stationarity tolerance depends on the iterate gap and EOT approximation error.Source: §3.2 · pp. 5–6
4. Dual gradient method
The dual gradient method reformulates the GW problem to optimize over variables that depend linearly on the coupling, and its new inexact variant avoids choosing a step size. Its convergence analysis covers arbitrary costs and inexact solutions, with a more complicated gradient call and solver-dependent approximation error.
4. Dual gradient method
- The dual reformulation trades the quadratic program over couplings for nested optimization in which the coupling enters linearly.The method uses a factorization of M, and the paper relates the framework for conditionally negative type costs to the special case B1 = 0.Source: §4 · pp. 6–7
- The proposed inexact gradient method for minimizing ℓε requires no step-size choice, but each iteration solves a strongly convex problem.Earlier projected-gradient methods use step sizes tied to ε, which can lead to small step sizes.Source: §4 · p. 6
4.1. Convergence under exact solutions.
- The dual method has convergence bounds for arbitrary costs when its inner problems are solved exactly, and its rate does not deteriorate as ε becomes small.The convergence metric is straightforward, but the method requires a more complicated gradient call.Source: §4.1 · p. 7
4.2. Convergence under inexact solutions.
- With inexact solutions, the convergence rate separates into an O(1/J) term and an approximation error depending on τ, while overall runtime depends on the gradient solver.The method extends the dual convergence analysis to an inexact gradient oracle.Source: §4.2 · pp. 7–8
5. Experiments
The experiments test AMD and dual-gradient convergence across CNT and non-CNT settings, including a reconstruction where classical mirror descent can oscillate. AMD converges more slowly than classical MD on the CNT examples, but smaller AMD step sizes can converge where classical MD fails on the non-CNT example; the dual method converges broadly but is often slower in runtime.
5. Experiments
- The dual-gradient implementations compare Variational (1) with Variational (L) and Accelerated variational (L), which use theoretically chosen stepsizes based on a Lipschitz constant.The regularized convex quadratic subproblems used for gradient approximations can be solved by other methods if they satisfy the stated approximation condition.Source: §5 · p. 8
- The evaluation covers a squared-Euclidean Gaussian mixture and geodesic sphere example with CNT costs, plus a sixth-power Euclidean Gaussian-to-ring example with a non-CNT cost.Regularization was ε = 0.1, 0.01, and 1 respectively; fixed α values were used because theorem step sizes scale as ε/∥M∥max and were prohibitively small in these settings.Source: §5 · p. 8
- On the non-CNT Gaussian-ring example, classical MD failed to converge in 300 iterations for all 10 seeds, while smaller AMD step sizes converged on at least some runs.Variational (1) converged in all experiments, but more slowly than AMD; methods with theoretical 1/L stepsizes could be too slow to converge within 10,000 iterations on some CNT examples.Source: §5 · p. 10
- All methods attained similar objective values, but dual methods had consistently higher total runtime because each iteration required a more complex inner solve.Although dual methods used a similar number of iterations to AMD with α ∈{0.9, 1} on CNT examples and fewer iterations than every AMD variant on the non-CNT example, iteration counts are not directly comparable because primal and dual methods use different stopping quantities.Source: §5 · p. 10
- At ε = 0.01 with the sixth-power non-CNT cost, α ∈{0.9, 1} produced objective oscillations, while α ∈{0.1, 0.5} and both dual methods decreased monotonically.The oscillating runs' stationarity proxy stayed above zero while the lag-2 coupling difference became negligible, indicating a two-cycle; all runs at ε = 0.1 met the stopping criterion, making oscillation a joint effect of non-CNT cost and small regularization.Source: §5 · p. 11
6. Proofs of main results
The proofs use strong convexity of negative entropy and conditional-gradient results to establish convergence guarantees, then extend the analysis to inexact EOT updates and connect dual and primal stationarity. The supplied proof passages give detailed arguments for Theorems 1, 4, and 9, with only a fragment of the Theorem 6 proof.
6.1. Proof of Theorem 1.
- Negative entropy is 1-strongly convex on the probability simplex in the 1-norm, so the scaled regularizer −εH is ε-strongly convex.Theorem 1's proof applies conditional-gradient results with f(x) = 1/2 x^T Mx and h(x) = −εH(x); the gradient of f is Lipschitz with constant ∥M∥max.Source: §6 · p. 11, §6.1 · p. 11
6.2. Proof of Theorem 4.
- Theorem 4's proof bounds inexact-update error by comparing Sinkhorn's approximate minimizer with the exact minimizer of the update objective.It uses a modulus of continuity for that objective on the simplex and controls iterate discrepancy through convex combinations of exact and approximate updates.Source: §6.2 · pp. 12–14
6.3. Proof of Theorem 6.
- Theorem 6's proof relates a dual stationarity residual to the difference between successive dual iterates.The displayed relation is summed over the iterates.Source: §6.3 · p. 14
6.5. Proof of theorem 9.
- An η-stationary point of the dual objective yields a primal point that is 2∥B0∥1,2η-stationary.The proof uses the variational condition for the primal minimizer and bounds the residual using the dual stationarity error and the fact that probability vectors are at most distance 2 apart in the 1-norm.Source: §6.5 · p. 15
7. Conclusion
The conclusion summarizes convergence guarantees for AMD and the fixed-stepsize dual gradient method, while noting the dual method's practical inner-solve cost. The appendix describes Sinkhorn iterations as the EOT solver used in the algorithmic pipeline.
7. Conclusion
- AMD has non-asymptotic convergence guarantees for exact updates, and its analysis accounts for inexact EOT solutions from Sinkhorn; the dual gradient method converges with a fixed stepsize independent of regularization.The conclusion also explains that for non-CNT costs, MD does not take true gradient steps, which helps explain its failure to converge in some examples.Source: §7 · p. 16
- AMD performs comparably to classical MD, while the dual method uses a similar number of steps but is often slower because each iteration solves a regularized convex quadratic program instead of an EOT problem.The conclusion identifies speeding up dual-gradient computation as a research direction; theoretically justified stepsizes in prior methods become small as ε decreases, potentially slowing convergence in practice.Source: §7 · p. 16
Appendix A. Sinkhorn’s algorithm
- Sinkhorn iteratively fixes the marginals of a positive matrix whose entries sum to one, and its output can be treated as a probability matrix on the product space.The output is not necessarily guaranteed to satisfy both marginal constraints simultaneously.Source: Appendix A · pp. 19–20
A.1. Proof of Lemma 3.
The proof uses Sinkhorn's convergence in a pseudometric to bound the 1-norm distance between its approximate output and the exact solution.
A.1. Proof of Lemma 3.
- A Sinkhorn output within pseudometric distance δ of the exact solution has 1-norm error at most e^δ − 1.The number of Sinkhorn steps needed for that pseudometric accuracy depends on δ, ε, the cost bound, and both marginals.Source: §A.1 · p. 20
Appendix B. Additional details on the convergence metrics
Appendix B develops the stationarity criteria for exact and inexact iterates. Exact minimizers must be strictly positive, while inexact EOT solves yield a nearby approximately stationary point under stated accuracy conditions.
B.1. Exact iterates.
- Every local or global minimizer of f + h over K has strictly positive entries, enabling the entropy gradient and stationarity condition to be defined there.At a global minimizer, ∇h has components ε(1 + log(x_i)), and optimality requires ⟨∇f(x) + ∇h(x), y − x⟩ ≥ 0 for every y ∈ K.Source: §B.1 · pp. 20–21
- A point is γ-approximately stationary when its first-order optimality inequality is violated by at most γ for every feasible comparison point.The condition is defined for points in K with strictly positive entries, so the entropy derivative is well-defined.Source: §B.1 · p. 21
B.2. Inexact iterates.
- If each EOT subproblem is solved within e^(δ−1) in 1-norm and the iterate error is at most τ, the resulting point is approximately stationary and within e^(δ−1) of the exact subproblem solution.The stated stationarity tolerance scales with sup_{x,y∈K} ∥x−y∥_1 ∥M∥_max (τ + e^(δ−1)).Source: §B.2 · pp. 21–22
C.1. Dataset generation.
The experiments use four generated examples, including a non-CNT Gaussian-to-ring case and a reconstruction of an example from. Implementation details describe low-rank AMD and variational solvers and their computational costs.
C.1. Dataset generation.
- The four examples are Gaussian mixtures in R^10 and R^15, rotated spherical clouds, a Gaussian-to-ring pair with sixth-power Euclidean cost, and a reconstructed example from.The mixture uses 1,000 points per cloud; the sphere and Gaussian-to-ring examples use 100 points per cloud, while the reconstruction uses two fixed 15-point clouds.Source: §C.1 · p. 22
C.2. Implementation details and computational complexity.
- AMD uses low-rank cost factorizations and has complexity O(N0N1SJ), up to log factors, where J is the iterations to approximate stationarity and S is the maximum Sinkhorn iterations.The averaging step can make J either larger or smaller than for classical MD depending on the experiment.Source: §C.2.1 · p. 23
- The variational implementation factorizes M using positive and negative eigenvalues, discards eigenvalues with absolute value at most 10^-10, and uses a memory-efficient Kronecker-product implementation.Its reported complexity for the simple gradient method scales as O(J_outer J_inner (S + max{r0,r1})N0N1), assuming B0 and B1 are available.Source: §C.2.2 · pp. 23–24
C.3. Experimental details.
This section specifies solver settings and stopping rules for the experiments. It also describes how runs are aggregated and when curves are omitted.
C.3. Experimental details.
- EOT subproblems use POT Sinkhorn methods with a 10^-9 threshold; Sinkhorn epsilon scaling is used for Gaussian-ring because Sinkhorn-Knopp encounters division-by-zero errors.Sinkhorn-Knopp is capped at 1,000 iterations, while epsilon scaling allows 20,000 continuation iterations with 100 inner scaling iterations per continuation step.Source: §C.3 · p. 24
- For α = 0.5, 9/10 runs and for α = 0.9, 6/10 runs reach the prescribed tolerance; none of the classical mirror descent (α = 1) runs do.Dual gradient methods terminate when the requisite metric is below 10^-6 or the maximum number of iterations is met. The outer tolerance is always met first for Variational (1), but not always for Variational (L) or Accelerated variational (L).Source: §C.3 · p. 25
- Objective curves aggregate arithmetic mean EGW values and stationarity curves aggregate geometric means of iterate differences, each with one standard deviation in base-10 log space.Aggregate curves are plotted only when at least half the seeds converge; Gaussian-ring inner gradient ascent misses its prescribed tolerance on the first iterate.Source: §C.3 · p. 25
- For the reconstructed example from, all methods use at most 300 iterations, with early stopping at a 10^-6 iterate-change threshold.The dual-gradient regularized quadratic subproblems use gradient ascent with step size 0.5 and at most 100 iterations.Source: §C.3 · p. 25
Appendix D. Additional results
Appendix D clarifies the Gaussian-ring objective plots, reports the behavior of theoretical AMD step sizes, and describes coupling visualizations and Sinkhorn-call reporting.
D.1. Gaussian-ring interaction objective.
- For the sixth-power Gaussian-ring cost, classical MD’s interaction-term progress stalls and appears to oscillate.The interaction term is plotted because large coupling-independent constants obscure changes in the full EGW objective.Source: §D.1 · p. 26, Figure 3 · p. 26
D.2. Theoretical stepsizes.
- The theoretical AMD step size is slower than the tested alternatives but reaches approximate stationarity within the prescribed iterations for the sphere example.The section reports theoretical AMD and variational step-size choices for the Gaussian mixture and sphere examples; Figure 4 plots primal stationarity and objective for several α values.Source: §D.2 · p. 26, Table 3 · p. 26, Figure 4 · p. 27
D.3. Coupling visualizations.
- With the non-CNT sixth-power cost and ε = 0.01, AMD at α = 0.9 and α = 1 alternates between two coupling configurations; this does not occur at ε = 0.1.For the CNT squared-distance cost, all methods converge as expected.Source: §D.3 · p. 27, Figure 5 · p. 28
D.4. Complexity in terms of average Sinkhorn calls.
- Table 4 reports the mean number of Sinkhorn calls and one standard deviation for each algorithm over 10 seeds.The supplied table description gives the reported measure but no call-count values.Source: §D.4 · p. 28, Table 4 · p. 28