- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
In this paper, the authors study the theoretical convergence of numerical solvers for Gromov–Wasserstein(GW) Optima Transport problems. They study the average mirror descent (AMD) algorithm, which is equivalent to a conditional gradient method, and the dual gradient method, with both exact and inexact inner solvers. They prove convergence of AMD for arbitrary costs and convergence of the dual gradient method with a fixed step size. Numerical experiments compare AMD, MD (alpha = 1), and dual gradient methods, showing that AMD and the dual solvers perform better for small values of the regularization parameter epsilon.
Critical strengths
-
The question of efficiently solving entropic GW is interesting and of importance since solving it for small regularization is notoriously difficult and computationally intensive.
-
The results for inexact inner solvers are also interesting especially since that is what is used in practice and was not always studied in the literature.
-
The authors make several connexions between recent solvers and results between Rioux 2024+2026 and Houry 2026 that are interesting and a rare contribution to the literature that tend to claim novelty without proper positioning wrt existing work.
-
The paper is well written and easy to follow.
Critical weaknesses
-
The theoretical results are interesting but their novelty is limited. It feels a little as if the authors found that the AMD result was too weak a contribution for an ML paper so they also studied the dual gradient to compensate, but this makes the main story of the paper a bit unclear and limit space for numerical experiments.
-
The numerical experiments are quite weak, with only three datasets and no detailed computational analysis. The objective is clearly to recover the theoretical convergence speed (which is always easy in optimization papers) but many other practical aspects are not studied. For instance, the impact of the number of iterations of the inner solver is not studied despite the fact that inexact solvers are studied in the paper. Also the authors discuss how the dual gradient computation is more expensive than AMD but they do not provide any details about the computational cost of the dual vs AMD.
-
GW is a non convex problem and the final solution is what matters in practice. While I understand focus on convergence, it would have been interesting to see and compare the quality of the final solution for each method. This would probably require more datasets and runs but it would have been a more practical and useful contribution to the ML community.
See questions fo authors for more details.
Questions for authors
-
Could you please provide more details on the computation cost of the dual vs AMD? What is the time to compute a gradient? What is the impact of the approximations in the inner problems? For instance trajectories in the final objective VS computational time as a function of number of iterations in the inner problem could be very interesting and show more clearly the impact of the approximation in the inner solver.
-
Could you please clarify the novel contributions of the paper in particular wrt Houry and Rioux? The extension to fixed step and generalization to arbitrary costs are claimed (and interesting) but the paper is not very clear on this point such as how the proof strategy had to be adapted. It would have been better to have a dedicated section discussion related work.
-
Which methods actually lead to the best solution in practice? How do you initialize the algorithms? What is the impact of the initialization on the final solution? you provide information about "convergence" in Table 1 but not about the quality of the final solution. This is a very important point since GW is non-convex and the final solution is what matters in practice. When the true solution is not known, one can use the one having the best final objective as a reference to compare the others.
-
Minor comment: The authors could also discuss the references [A] that introduced the exact variant of the Algorithm 1 and [B] its application for solving entropic regularized OT problems. I added this in the questions because it is not a strong weakness. The authors have a clear interest in making the connection between AMD and conditional gradient methods and these references might be of interest to them.
-
Do you think it would be interesting to do a decreasing (as in conditional gradient) or adaptive line serach for AMD? For instance one can approximate the function as quadratic which leads to step sizes that could speedup convergence.
[A] Bredies, K., Lorenz, D., & Maass, P. (2005). Equivalence of a generalized conditional gradient method and the method of surrogate functionals. Bremen, Germany: Zentrum für Technomathematik.
[B] Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). Generalized conditional gradient: analysis of convergence and applications. arXiv preprint arXiv:1510.06567.
6 comments
- Adding objective values and limited experiments: We agree that adding objective values and extending the experimental results will help to improve the paper. Due to the limited space we have included many new experiments in Section F, including new datasets, ablations on different parameters, and experiments with an adaptive line search for AMD. We also compile objective values for the different experiments in Section F. These results indicate that, for non-CNT costs, such as the new graph matching example, the dual gradient method generally gives better values at the cost of a more complicated iteration, but this advantage does not generally hold for CNT costs. We also include visualizations of the approximate couplings obtained for each method in Section F.8.
Initialization: For the experiments in the main text, we initialize the algorithms at the product coupling for AMD and for the dual gradient method. We choose this as a natural initialization since the product coupling requires no problem-specific knowledge. The impact of the initialization depends on the structure of the underlying problem. We illustrate this in Section F.9 where we use a debiased version of EGW to compare two weighted isomorphic graphs on vertices. For that problem, each of the 120 permutation of the vertices gives us a possible initialization. Running each initialization for each method, we obtain that the same initializations give us a debiased EGW value close to for each method (indicating that the optimal alignment has been found) whereas the remaining initializations give larger values. This behavior is expected for the complicated task of checking for graph isomorphisms.
-
Additional references: Thank you for pointing us towards these references, we have cited them at the start of Section 3.1 to provide some additional context for Algorithm 1 from Ghadimi's paper.
-
Alternative step sizes: As noted in the response to reviewer d5nK, we have added Section 3.3 on an adaptive step size from Ghadimi (2019) and a corresponding analysis in Section B.5. This provides a principled way to set a step size which appears to be less conservative in the experiments performed in Section F.7. We will incorporate these results into the main text for the final version. Notably, we compare the performance of AMD with fixed step sizes (including the theoretical step) against this adaptive step size and track the obtained step size sequences. In our experiments we see that, for non-CNT costs, the adaptive step sizes are small for initial iterations which helps to mitigate oscillations and, in later iterations, larger steps are generally accepted.
In addition, we show that this step size still yields a convergent algorithm even in the presence of inexactness in Theorem 6.
I want to thank the authors for their detailed response and also for the new experiments that are interesting. It does answer some of my concerns. A few remaining points below.
-
I am a bit disappointed that actual computational time were only provided in the form of tables. This introduces a bias through the convergence conditions and is hard to compare between different algorithms. I can understand it is too late now if you did not store time along epochs but I strongly suggest that you add a few Values VS actual time plots to the final version of the paper. Theoretical complexity for each step is usually far from what is obtained when implementing on modern CPU and GPU for many reasons and hard fact about convergence vs time is important in addition to vs iterations.
-
Thanks for clarifying the novelty, this is more clear in term of new results but I was also asking about what novel steps in the proofs have been necessary and proposed/updated beyond using results and proof steps from both related papers. This is the interesting parts: what breaks and needs to be done in a new way and how. It is OK if you can used steps form both papers to reach the results and no novel proof trick is proposed, making connections is a nice contribution in itself. But it is bit unfair to ask the reader to do the work of looking for this when the authors have the full grasps of the question.
-
Thanks for the new initialization and seed experiments. they clearly show that it is a sensitive questions (even maybe more than having faster algorithms). About comparison of the different methods, since you tried for different seeds a good way to compare method would be to perform statistical tests (Wilcoxon) on the final objectives across different seeds to see if one is statistically better?
I keep my positive opinion on the paper and will keep my current score.
Compute time for gradient: This is a good point, we have added the number of operations required to compute the gradients for AMD and the dual gradient method in the fourth paragraph of p.9. Notably, AMD requires O(Sk+r1k+r0k), where S denotes the number of Sinkhorn iterations required to solve the EOT problem, whereas the dual gradient requires O(J′(Sk+r1k)+r0k) assuming, additionally, that J′ iterations of the inner gradient method used to solve the regularization quadratic program are performed assuming that each EOT problem requires S Sinkhorn iterations. These complexity results assume that the decomposition M=B1⊺B1−B0⊺B0 is available. Rioux et al. (2026) establish that when p=2, this decomposition can be obtained in O(max{N03,N13}) operations; this is a one-time cost.
Impact of Approximations in the Inner Problems: This is an interesting idea, we have added this experiment in Section F.3.2. Interestingly, the results from that section appear to indicate that the relationship between final EGW value and the number of steps in the inner problem is more complicated than one would assume (i.e., more steps should always be better). Indeed, the objective values do not vary much as the number of steps in the inner problem is varied and the largest number of steps does not always yield the best solution. We attribute this to the complicated landscape of the EGW objective; by changing the method slightly, we vary the optimization path and can arrive at a better stationary point.
Novelty: We thank the reviewer for pointing out that the discussion of the related works of Houry et al. and Rioux et al. is a bit unclear as it pertains to the contributions of our paper relative to theirs. As mentioned in the discussion of related literature, the work of Houry et al. established that mirror descent may fail to converge for non-CNT costs and demonstrate why this is not the case for CNT costs by using the connection between mirror descent and the dual gradient method with a fixed step size. Essentially, they prove convergence of the dual gradient method via a majorization-minorization argument.
On the other hand, the paper of Rioux et al. show that for general GW problems the gradient in the dual method requires solving a regularized convex quadratic program whereas the corresponding step in the mirror descent method solves an EOT problem. Thus, the mirror descent appears to use a coarse approximation of the gradient which may explain why it can fail. Moreover, the effects of inexact solutions to EOT problems are studied in that work.
Therefore, our paper attempts to bridge the gap between these two papers by answering the following questions (1) Is the failure of mirror descent for the non-CNT example a fundamental issue of the linearization scheme? (2) Can the majorization-minorization argument for CNT costs improve the analysis of the dual gradient method by enabling a fixed step size? (3) Can we account for inexact solutions in the mirror descent scheme?
For (1), we show that by damping successive steps we can retain convergence whilst using the conceptually and computationally simple linearization procedure. For (2), we show that the same idea can be applied to the ''outer'' optimization problem thereby enabling the step size for the outer loop to be set to 1 independently of ε, but does not appear to help with the ''inner'' problem which is solved when computing the gradient whose stepsize depends on ε in current methods. For (3), we show that inexactness can be accounted for in both algorithms. Crucially, the analysis in the case of averaged mirror descent is completely distinct from that for the dual methods and requires substantially new ideas to account for the fact that the iterates are not guaranteed to be couplings.
In sum, the aim of the paper is to show that, for general costs, the nice connection between mirror descent and the dual gradient method does not hold, but we can adapt these two algorithms in different ways to regain some of the desirable properties. Moreover, we also show that almost stationary points for the dual problem are also almost stationary for the primal problem. To our knowledge this relationship was not known previously.
We will clarify this point in the literature review.