acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
optimization
Keywords:
Gromov--Wasserstein, Mirror Descent, Non-convex optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_5rXhOpenReview ↗
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
  1. 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)O(Sk+r_1k+r_0k), where SS denotes the number of Sinkhorn iterations required to solve the EOT problem, whereas the dual gradient requires O(J′(Sk+r1k)+r0k)O(J'(Sk+r_1k)+r_0k) assuming, additionally, that J′J' iterations of the inner gradient method used to solve the regularization quadratic program are performed assuming that each EOT problem requires SS Sinkhorn iterations. These complexity results assume that the decomposition M=B1⊺B1−B0⊺B0\mathrm M=\mathrm B_1^{\intercal}\mathrm B_1-\mathrm B_0^{\intercal}\mathrm B_0 is available. Rioux et al. (2026) establish that when p=2p=2, this decomposition can be obtained in O(max⁡{N03,N13})O(\max\{N_0^3,N_1^3\}) 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.

  2. 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 11 independently of ε\varepsilon, but does not appear to help with the ''inner'' problem which is solved when computing the gradient whose stepsize depends on ε\varepsilon 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.

  1. 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 x∏=μ0⊗μ1x_{\prod}=\mu_0\otimes \mu_1 for AMD and u0=B0x∏u_0=\mathrm B_0 x_{\prod} 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 55 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 22 initializations give us a debiased EGW value close to 00 for each method (indicating that the optimal alignment has been found) whereas the remaining 118118 initializations give larger values. This behavior is expected for the complicated task of checking for graph isomorphisms.

  1. 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.

  2. 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.

Reviewer_TmhcOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies convergent algorithms for entropic Gromov-Wasserstein (EGW) problems with general costs. It introduces averaged mirror descent (AMD), which averages the current iterate with a mirror descent (MD) update, and establishes its convergence by viewing AMD as a conditional gradient method (Ghadimi, 2019). It also proves convergence of the existing dual gradient method with a unit step size independent of the entropic regularization parameter ε\varepsilon.

Critical strengths

The paper addresses computationally important problems in EGW: MD may fail to converge for non-CNT costs, and existing analyses of the dual method require very small step sizes when ε\varepsilon is small. The proposed AMD with α=0.1\alpha = 0.1 or 0.50.5 makes clear progress on the non-CNT examples where MD stalls or oscillates, and the dual method converges much faster with a unit step size than with conservative step sizes.

Both modifications are straightforward to incorporate into existing solvers. AMD retains the entropic OT subproblem used in MD and adds an averaging step, so existing MD solvers need only a small change. For the dual gradient method, the paper simply sets the step size to 1, yielding meaningful performance gains with minimal changes to existing solvers.

Critical weaknesses

Both non-CNT examples (Gaussian-ring and the reconstruction of Houry et al.) use the sixth power of the Euclidean distance, so it is unclear whether the empirical results carry over to other non-CNT costs (Q1).

The step sizes prescribed by the AMD convergence analysis are much smaller than those that work well in the experiments, and convergence also appears slow when the theoretical values are used. The choice of a suitable step size appears to depend on the problem, but practical guidance on making this choice remains limited (Q2).

Questions for authors

Q1. Could the authors add a small comparison of MD, AMD, and the dual method under a non-CNT cost that is not a power of the Euclidean distance? This would help assess whether the empirical results extend to a broader range of costs.

Q2. A heuristic rule for choosing a step size that works well in practice for a given cost would be helpful. Such a rule would be particularly useful when applying AMD to problems with non-CNT costs.

Minor comments

  1. Algorithm 3 initializes u0u_0 but starts at k=0k = 0 while referring to uk−1u_{k-1}, so the first iteration uses an undefined value. Please check the indexing.
3 comments

We thank the reviewer for their careful reading of the work and for identifying some points in the paper which deserve further clarification. We respond to the questions point by point below. Some of the responses include experiments which are ongoing due to the limited response period. We have posted our response early before all of these experiments are complete in order to promote discussion. We will update the paper once these experiments are complete.

  1. Non-CNT Examples: We agree that using only the sixth power of the Euclidean distance as an example of a non-CNT cost is not ideal. We have therefore added an experiment on graph matching in Section F.1 where it can be shown that one of the cost matrices is not CNT. Interestingly, we see in Figure 4 the sense that if α\alpha is too large, AMD can oscillate for this example as well, but that AMD with a sufficiently small α\alpha and the dual gradient method are convergent.

  2. Heuristic step size rule: 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.

  3. Typo in indexing: Thank you for identifying this typo, we have corrected it.

Thank you for the response and the additional experiments.

The graph matching example in Section F.1 addresses my first question, and the adaptive step size in Section 3.3 with Theorem 6 addresses my second. Since the corresponding experiments are currently only in the appendix, I would encourage the authors to bring them into the main text as planned.

We thank the reviewer for their response and for their time and effort in assessing our submission. We have uploaded an updated version of the paper which incorporates the additional experiments and discussion of the results into the main text. Notably, the results for the adaptive step size and graph matching example have been added to Figure 1. We are still performing some additional runs to finalize the experiments which we will incorporate into the final version of the paper. We will also continue working on optimizing the presentation of the paper so that as much detail as possible can be provided in the main text.

Reviewer_d5nKOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies a practical difficulty in solving entropic Gromov–Wasserstein problems: for some cost functions, the commonly used mirror descent method can oscillate instead of converging. The authors investigate two ways to address this. AMD takes a more cautious update by averaging the standard mirror descent step with the current coupling. The second approach uses a dual gradient method with a fixed outer stepsize of one, but requires solving a more demanding convex subproblem at each iteration. The paper provides guarantees for finding approximately stationary solutions under general costs, accounting for errors in the inner optimization. Experiments on synthetic datasets illustrate when these methods avoid the oscillations of classical MD and show the computational trade-offs between them.

Critical strengths

1, The paper extends convergence guarantees beyond CNT costs, where classical MD theory is currently limited.

2, Theorems 4 and 10 explicitly account for approximate Sinkhorn and inner-QP solutions, making the analysis more relevant to implementation.

3, The decomposition M=B1⊤B1−B0⊤B0M=B_1^\top B_1-B_0^\top B_0 explains why MD coincides with a true gradient method for CNT costs but may fail for general costs.

Critical weaknesses

1, Theorems 4 and 10 assume bounds on inner solution errors, but the experiments do not quantify how their residual thresholds and iteration limits satisfy these assumptions. As Remark 12 shows, a small computed dual gradient does not by itself certify true stationarity without controlling the inner error. AMD and the dual methods also stop on different quantities, so Table 1 does not establish which method reaches the same primal accuracy faster.

2, The practically successful stepsizes are much larger than the theoretically justified values, while stability remains sensitive to tuning; for example, α=0.9\alpha=0.9 still cycles in Figure 2. Appendix E.2 evaluates the theoretical stepsizes only in CNT settings, leaving their practical cost on the key non-CNT examples unclear.

Questions for authors
  1. Can you quantify inner solution errors or recompute final subproblems more accurately to validate termination? Does tightening inner tolerances change Gaussian-ring success counts?

  2. At matched primal stationarity and marginal-feasibility accuracy, how do end-to-end runtimes compare, including decomposition and preprocessing? Please explain how the native stopping metrics and inner errors relate to the common primal criterion. Does the runtime ranking persist when the variational baselines receive a comparable stepsize-tuning budget?

  3. On Gaussian-ring and Figure 2's sixth-power example, how does the Theorem 4 stepsize compare with empirical stepsizes and Ghadimi's line search (2019, Algorithm 2) in accuracy and runtime, using matched inner accuracy?

  4. With exact inner solves and corresponding initialization, does the dual update coincide with DCA/CCCP applied to the primal objective? What do Theorems 6 and 10 add, especially for stationarity bounds and inexact, potentially infeasible inner outputs?

3 comments

We thank the reviewer for their constructive comments on the paper. We believe that the questions brought up will help to improve the quality of the submission; we have made some additions to the paper in terms of theory and experiments to address these different points. We now address each question point by point. We note that some of the responses include some experiments which are still ongoing due to the short response period. We opt to post our response early before all of these experiments are complete in order to promote discussion and will update our paper once they are complete.

  1. Quantifying inner solution errors or recomputing final subproblems more accurately to validate termination: We have added additional discussion on the practical stopping conditions used for Sinkhorn and the gradient method used to solve the auxiliary regularized convex quadratic programs figuring in the dual gradient method (see after Lemma 3, after Remark 12, and Sections A.2 and D). In effect, both of these methods are generally run until a maximum number of steps is met or an early stopping criterion is reached. For Sinkhorn's method, this is based on how much the marginal condition is violated (see Algorithm 3) whereas for the gradient method the criteria is generally that the norm of the (approximate) gradient at a point is small. Sections A.2 and D show the influence these practical stopping conditions play in the approximation constants δ\delta and τ\tau. We are working on using the bounds provided in those sections to provide a sense for the practical values of δ\delta and τ\tau in the experiments and will include these details in the final version. Obtaining the exact error for practical problems is nontrivial except in very simple circumstances since the exact EOT solution and exact solution of the regularized convex quadratic programs are not generally available.

It is indeed reasonable to recompute the last iteration with higher accuracy in order to obtain better guarantees. We present the results with a uniform error since the presentation is simpler in that case, but one could accommodate for different error tolerances at each iteration using the same argument.

Success counts and inner tolerance: Regarding tightening the inner tolerances for the Gaussian-ring experiment, since the dual method converges for all seeds in the Gaussian–ring experiment, we interpret this question as regarding the stopping tolerance used for Sinkhorn in AMD. Please correct us if our interpretation is incorrect.

To investigate this, we reran all AMD variants on the Gaussian–ring example with different stopping tolerances for Sinkhorn's algorithm, namely α∈{10−9,10−12,10−15}\alpha\in\{10^{-9},10^{-12},10^{-15}\}. The table below reports the number of seeds reaching the prescribed outer convergence tolerance.

α\alpha10−910^{-9}10−1210^{-12}10−1510^{-15}
0.18/108/108/10
0.59/109/109/10
0.96/106/106/10
10/100/100/10

The results show that tightening the Sinkhorn tolerance does not change the success counts. To further investigate this behavior, we have added additional plots to Appendix F.2.1 of the revised manuscript. These show that the failures appear to be due to oscillations in the objective values, which persist even when the Sinkhorn tolerance is tightened. Thus, the observed instability does not appear to be a consequence of the accuracy of the inner Sinkhorn solves.

  1. Comparison of end-to-end runtimes: Note that the same marginal accuracy is the same for each experiment since we use Sinkhorn iterations. As it pertains to achieving a matched primal stationarity and, more generally, a clearer comparison between the primal and dual methods, we have rerun the experiments on 5 seeds and terminated the dual method when successive couplings have squared distance less than 10−610^{-6} in the squared 11-norm to make the comparison with the termination condition in AMD (∥xj−x~j∥12<10−6\|x_j-\tilde x_j\|_1^2<10^{-6}) more fair. A table of adjusted (mean) runtimes (including the time needed for the decomposition and preprocessing) and success rates is provided below.
MethodGaussian mixture Runtime (s); conv.Sphere Runtime (s); conv.Gaussian-ring Runtime (s); conv.
AMD (α=0.1\alpha=0.1)27.67±10.1827.67 \pm 10.18; 5/50.438±0.3560.438 \pm 0.356; 5end/59.06±3.409.06 \pm 3.40; 5/5
AMD (α=0.5\alpha=0.5)7.75±2.067.75 \pm 2.06; 5/50.116±0.0890.116 \pm 0.089; 5/55.39±2.275.39 \pm 2.27; 5/5
AMD (α=0.9\alpha=0.9)4.41±1.214.41 \pm 1.21; 5/50.068±0.0510.068 \pm 0.051; 5/511.03±8.5811.03 \pm 8.58; 3/5
MD (α=1\alpha=1)4.18±1.344.18 \pm 1.34; 5/50.060±0.0430.060 \pm 0.043; 5/521.83±10.1721.83 \pm 10.17; 0/5
Dual variational10.59±1.7010.59 \pm 1.70; 5/50.161±0.1320.161 \pm 0.132; 5/5176.12±85.32176.12 \pm 85.32; 5/5

As before, the dual variational solver is generally slower than AMD.

In the revised manuscript, we also provide a graph matching example in Section E.1. With the same matched accuracy in terms of subsequent couplings, we obtain the following results.

Method10 Vertices Runtime (s); conv.100 Vertices Runtime (s); conv.200 Vertices Runtime (s); conv.
AMD (α=0.1\alpha=0.1)4.28±1.264.28 \pm 1.26; 5/50.254±0.1850.254 \pm 0.185; 5/57.89±0.117.89 \pm 0.11; 0/5
AMD (α=0.5\alpha=0.5)1.05±0.651.05 \pm 0.65; 5/5246±342246 \pm 342; 0/5121±79121 \pm 79; 0/5
AMD (α=0.9\alpha=0.9)0.453±0.2240.453 \pm 0.224; 5/5389±421389 \pm 421; 0/5220±165220 \pm 165; 0/5
MD (α=1\alpha=1)0.513±0.2700.513 \pm 0.270; 5/5307±236307 \pm 236; 0/5247±187247 \pm 187; 0/5
AMD (theoretical)141±33141 \pm 33; 2/53.60±1.873.60 \pm 1.87; 1/51.72±0.481.72 \pm 0.48; 5/5
Dual variational48.4±24.148.4 \pm 24.1; 5/50.500±0.2790.500 \pm 0.279; 5/50.106±0.0240.106 \pm 0.024; 5/5

If, by primal stationarity, the reviewer means the expression max⁡x∈K⟨−(pˉ+∇f(xˉ)),x−xˉ⟩\max_{x\in\mathcal K}\langle -(\bar p+\nabla f(\bar x)),x-\bar x\rangle in Remark 2, we are working on implementing this and will include details in the final version.

Variational baselines with step-size tuning: We have conducted an ablation study of the dual method on the sphere example, varying both the inner and outer stepsizes and reporting the average runtime over five seeds for each combination. This experiment can be found in Section F.3.1. This experiment indicates that the fastest runtimes are comparable to the runtime of the original stepsize combination; inner stepsize equal to 0.50.5 and outer stepsize equal to 11.

Stopping metrics and inner errors: We have added Remark 14 which describes how the different sources of error in the dual gradient method effect the conclusion of Theorem 10 (that we can recover near stationary points for the primal from near stationary points of the dual). The conclusion is that near stationarity for the primal is preserved for the true solution of the regularized convex quadratic program at a near stationary point for the dual with a slightly different constant. We account for the fact that the true solution cannot generally be obtained by noting that an approximate solution (e.g., from Sinkhorn's algorithm) has an objective value close to that of this near stationary point and that the approximate solution can be processed into a true coupling using Algorithm 2 in Altschuler et al. (2017) which may not be near stationary, but is close (in value and distance) to a near stationary point. Remark 5 address the case of inexactness for AMD.

  1. Line search: We thank the reviewer for this excellent suggestion. We have added Section 3.3 to the text which illustrates that Ghadimi's line search not only applies to AMD with accompanying rates, but can also be shown to be robust to inexactness in the iterations with appropriate modifications to the rates. Section B.5 contains the proof of those results.

We have added the values of the theoretical step sizes for all experiments to Table 12 in Section F.6. In Figures 10 and 11, we show how the theoretical step size compares to the fixed choices used in the experiments except for the Gaussian–ring experiment, as the theoretical stepsize is prohibitively small, leading to extremely slow convergence.

We have also added a dedicated section on experiments with the adaptive step size AMD (using the line search); 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.

  1. Comparison with DCA/CCCCP: Defining f:K→12x⊺B1⊺B1x−12x⊺B0⊺B0x−εH(x)f:\mathcal K \to \frac 12 x^{\intercal}\mathrm{B}_1^{\intercal}\mathrm{B}_1 x -\frac 12 x^{\intercal}\mathrm{B}_0^{\intercal}\mathrm{B}_0 x-\varepsilon \mathsf{H}(x), the natural DCA iterations read x^{(k+1)}\gets \text{argmin}_{x\in\mathcal K}\left\\{\frac 12 x^{\intercal}\mathrm{B}_1^{\intercal}\mathrm{B}_1 x-\varepsilon \mathsf{H}(x) - x^{\intercal}\mathrm{B}_0^{\intercal}\mathrm{B}_0 x^{(k)} \right\\}. A connection to the dual gradient method can be seen by noting that, under exact iterations,
x_{u_j}\in \text{argmin}_{x\in\mathcal K}\left\\{\frac 12 x^{\intercal}\mathrm{B}_1^{\intercal}\mathrm{B}_1x -u_{j}^{\intercal}\mathrm{B}_0x -\varepsilon \mathsf{H}(x)\right\\}.$$ Therefore, if $u_0=\mathrm{B}_0x_0$ for some $x_0\in\mathcal K$ it holds that $u_j=\mathrm B_0 x_j$ for $x_j=x_{u_{j-1}}$ as the subproblems are strongly convex. Inserting this identity into the above display shows that the iterates coincide, i.e., $x_j=x^{(k)}$ for $j=k$ provided that $x_0=x^{(0)}$. Note, moreover, that this connection still holds under inexact iterates provided that the same solver is used for the quadratic subproblems. In the exact setting, an analogue of Theorem 6 could thus be obtained using the elegant theory for DC programming to the primal problem. For instance, Corollary 3.2 in Yurtsever and Sra (2022) establishes the same rate of convergence up to a factor of $2$ for a slightly different convergence criterion. Nevertheless, the case for inexact iterations considered within our work does not appear to follow directly from the literature. In effect, other papers in the DC literature focus on iterations which are inexact (in the sense that the update is not solved exactly), but are all feasible whereas Sinkhorn's algorithm is known to output solutions which are infeasible, but very close to the true solution. Therefore, our analysis in the inexact case differs from that of the standard DCA literature. We will add this connection to the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.