acceptodds
Under review as a conference paper at ICLR 2027

MAEG: Moving-Anchor Adaptive-Adaptive Accelerated Extra Gradient Method

Abstract

We propose the moving-anchor adaptive-adaptive accelerated extragradient method (MAEG) for smooth convex-concave minimax problems, which combines extragradient updates with a moving anchor to achieve accelerated convergence while adapting to both the smoothness constant and the strong convexity-concavity parameter. MAEG uses no line search and no restarts, and its step size and anchor coefficient are adaptively updated. For a smooth convex-concave objective function, MAEG achieves an accelerated last-iterate convergence rate, similar to the extra anchored gradient (EAG) method. When the objective function is additionally -strongly convex-concave, MAEG has a linear last-iterate convergence rate. Numerical experiments in several diverse settings show that MAEG matches or beats prior methods, and significantly outperforms the baselines when the local smoothness constant and strong convexity-concavity parameter are more favorable than their global counterparts.

Primary area:
optimization
Keywords:
adaptive gradient methods, minimax optimization, convex-concave optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_ARseOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes MA${}^4$EG, an adaptive method for finding zeros of monotone Lipschitz operators, using the operator residual norm as an optimality measure. The method has two adaptative mechanisms: First, it adopts the adaptive anchoring principle of Suh et al. (2023), originally developed for implicit methods, to adapt the anchor coefficient βk\beta_k and achieve linear convergence under strong monotonicity without knowing the strong monotonicity parameter μ\mu. Second, it adapts step size hkh_k based on local Lipschitz estimates and uses a moving anchor to compensate for potentially overly aggresive steps. This allows the method take larger steps when the global Lipschitz constant is substantially larger than the local Lipschitz constant, while maintaining the O(1/k2)O(1/k^2) accelerated last-iterate rate in squared residual for general monotone problems. The benefits of these adaptive mechanisms are demonstrated through several experiments. The appendix also proposes a variant called MA${}^4$EG-AP, which incorporates previous operator evaluations into the predictor step.

Critical strengths

The main strength of the proposed method lies in its adaptivity to both the strong monotonicity parameter and the Lipschitz constant. Not only can this adaptivity lead to faster convergence, but it also eliminates the need for prior knowledge of either constant, making the method more attractive in practice. In particular, the method achieves the accelerated O(1/k2)O(1/k^2) rate under monotonicity and linear convergence under strong monotonicity.

Another technically interesting aspect is the use of a moving anchor, which allows the method to accept potentially overly aggressive steps without backtracking while maintaining the accelerated convergence guarantee.

Critical weaknesses

None

Questions for authors
  1. Adaptivity to decreasing local smoothness.

The method tracks the maximum local Lipschitz estimate over all previous iterations, which imposes a nonincreasing upper bound on the adaptive step size hkh_k. This may limit the benefit of adaptivity when the local Lipschitz constant is initially large but decreases as the iterations progress. Could the authors clarify whether maintaining the running maximum is essential for the convergence guarantees, or whether the step-size rule could instead adapt to recent local Lipschitz estimates?

  1. Moving anchor versus backtracking.

Could the authors further clarify the advantages of the proposed moving-anchor mechanism over backtracking line search? While the moving-anchor mechanism allows the method to accept potentially overly aggressive steps without backtracking, it is unclear when this approach would be preferable to simply reducing the step size through backtracking.

  1. Motivation for MA${}^4$EG-AP.

Could the authors clarify the advantage of MA${}^4$EG-AP over the original MA${}^4$EG? Unlike classical Popov methods, MA${}^4$EG-AP does not reduce the number of new operator evaluations per iteration, and both methods achieve the same asymptotic convergence rates. Therefore, the benefit of incorporating previous operator evaluations into the predictor remains unclear.

4 comments

Common Response (Repeated in all responses)

We thank the reviewers for their constructive feedback. We were happy to see the reviewers recognize MA$^4$EG’s contributions: simultaneous adaptivity to the smoothness constant LL and strong convexity–concavity parameter μ\mu, an accelerated O(1/k2)O(1/k^2) last-iterate rate in squared gradient norm, and linear convergence under strong convexity–concavity. These guarantees are achieved without prior knowledge of either parameter, line searches, or restarts.

Reviewer ARse identifies no critical weaknesses. Reviewers 67pc and 2Jn5 propose further generalizations, including convergence bounds that reflect local smoothness, extension to constrained setting, and separate primal and dual curvatures μx,μy\mu_x,\mu_y. While these extensions are certainly valuable directions for future work, each of these have the scope of a full research paper, and they are not really weaknesses of the present algorithm or analysis. Nevertheless, in response to Reviewer 2Jn5, we prepared Appendix E (pp. 29–37) which extends MA$^4$EG to constrained minimax problems.

We believe that the contributions of MA$^4$EG constitute a substantial advance that warrants publication. We hope that the suggested generalizations do not overshadow the the volume of contributions that the paper already achieves, and we respectfully ask the AC and reviewers to give these contributions full weight in their final assessment.

Response to Reviewer ARse

We thank the reviewer for the positive and encouraging review, and we are happy that the reviewer found no critical weaknesses in our work. We respond to the questions below.

Adaptivity to decreasing local smoothness (Q1). The reviewer is correct that the running maximum R^k+1=max⁡{R^k,ℓk}\hat R_{k+1}=\max\{\hat R_k,\ell_k\} in Line 9 of Algorithm 1 can limit the benefit of adaptivity when the local smoothness decreases along the trajectory. This choice is what allows us to bound the number of unsafe iterations (equation 25 in Appendix B). Every unsafe iteration multiplies R^k\hat R_k by more than γ\gamma, and since R^k\hat R_k never decreases and never exceeds LL, there are at most JJ unsafe iterations. If the step size instead followed only the most recent local estimates, it would grow again in flat regions. Whenever the iterates re-entered a region of high curvature, the larger step would then trigger new unsafe iterations, each requiring another anchor correction, and this could happen repeatedly if the iterates move back and forth between flat and curved regions. The nondecreasing R^k\hat R_k is therefore what keeps the number of anchor corrections bounded in Theorems 1 and 2. Designing a safeguard that lets the estimate decrease while keeping this bound is an interesting direction for future work.

Moving anchor versus backtracking (Q2). We added a paragraph on the role of the moving anchor to Section 2 and a numerical example to Appendix C. The moving anchor is what makes the adaptive anchor coefficient βk=hk/(τk+hk)\beta_k=h_k/(\tau_k+h_k) work with adaptive step sizes. If the anchor is frozen at ak≡z0a_k\equiv z_0 (Lines 11–12 removed, a variant we call A$^3$EG), an overly aggressive step can make ⟨F(zk),z0−zk⟩≤0\langle F(z_k),z_0-z_k\rangle\le0. Then τk=0\tau_k=0 and βk=1\beta_k=1, and the next iterate jumps back to z0−hkF(z0)z_0-h_kF(z_0), however close zkz_k already was to z⋆z^\star. The correction in Line 12 removes these resets. It keeps the step that was taken and moves the anchor by the smallest amount that guarantees τk+1≥τk+hk\tau_{k+1}\ge\tau_k+h_k, and hence βk<1\beta_k<1. In the example of Appendix C, A$^3$EG is reset six times and stalls, while MA$^4$EG is never reset and converges faster.

Regarding backtracking, both the step size and the anchor coefficient have to be chosen carefully, and backtracking in the literature adapts only the step size. FEG-A (Lee & Kim, 2021), the backtracking variant of FEG, searches for its step sizes but keeps the fixed schedule βk=1/(k+1)\beta_k=1/(k+1). We added FEG-A to all experiments, counting every gradient evaluation, including those rejected by the line search. MA$^4$EG performs better than or comparably to FEG-A in every experiment, and FEG-A converges only sublinearly on the strongly convex-concave Experiments 4 and 5 because its anchor coefficient does not adapt to μ\mu.

The affine-Popov extension (Q3). The reviewer is correct that MA$^4$EG-AP still uses two new operator evaluations per iteration, as MA$^4$EG does, so it does not halve the cost per iteration in the way Popov's method does relative to EG. We included Appendix D mainly out of intellectual curiosity, to show that the adaptive step size, the adaptive anchor coefficient, and the moving anchor also accommodate a predictor that reuses a past operator evaluation, while both convergence guarantees are preserved. It is not a main contribution of the paper, which is why it appears only in the appendix.

We thank the reviewer again for the encouraging comments and the helpful questions.

References

  • S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. In Advances in Neural Information Processing Systems, volume 34, pages 22588–22600, 2021.

I appreciate the authors' detailed responses and additional experiments.

Regarding Q1, I believe that MA${}^4$EG's inability to increase its step size when the local Lipschitz constant decreases is a meaningful limitation that may affect its practical performance. While the authors explain that allowing such increases could lead to repeated unsafe iterations and complicate the convergence analysis, this difficulty does not indicate a fundamental impossibility of adapting to decreasing local smoothness.

Regarding Q2, I think the authors' response does not fully address my original question. The moving-anchor mechanism allows MA${}^4$EG to accept potentially unsafe steps by adjusting the anchor. Alternatively, one could use backtracking line search within the same adaptive anchored extragradient framework, reducing the step size until an appropriate local Lipschitz condition is satisfied. This could avoid the resets observed for A${}^3$EG while retaining the adaptive anchor coefficient. Further clarification of the relative advantages of moving anchors and backtracking would better address my question.

I think the comparison would be more informative if it also included other adaptive methods, such as aGRAAL (Alacaoglu et al., 2023) or adaptive variants of EG. This is because FEG and EG have different strengths across problem settings. In particular, FEG achieves an accelerated convergence rate under general monotonicity, whereas EG enjoys linear convergence under strong monotonicity. These differences are also relevant when comparing their adaptive variants. Including methods with these complementary strengths would provide a more comprehensive comparison and better demonstrate the strengths of MA${}^4$EG across different problem settings.

I consider these to be weaknesses of the paper, but not critical ones. I still find the moving-anchor mechanism technically interesting and the development of an explicit method based on the adaptive anchoring principle of Suh et al. (2023) a worthwhile contribution. My positive assessment of the paper remains unchanged.

We thank the reviewer with thoughtful feedback and discussion throughout the review process.

Decreasing local smoothness (Q1). We agree that exploiting decreases in local smoothness could improve practical performance. Designing a step-size rule that allows the smoothness estimate to decrease while preserving both convergence guarantees is an interesting direction for future work.

Moving anchor versus backtracking (Q2). We agree that incorporating backtracking into the same adaptive anchored extragradient framework as MA$^4$EG is a meaningful alternative. We do not claim that moving anchors always outperform backtracking. The use of moving anchors follows the line of work on adaptive methods without line search; see Malitsky and Mishchenko (2020) and Suh and Ma (2025). Understanding the conditions under which adaptive methods without line search outperform backtracking is a broader research question in adaptive optimization. We therefore leave characterizing the trade-off between moving anchors and backtracking within our framework as an interesting direction for future work.

References

  • Y. Malitsky and K. Mishchenko. Adaptive gradient descent without descent. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of PMLR, pages 6702–6712, 2020.
  • J. J. Suh and S. Ma. An adaptive and parameter-free Nesterov's accelerated gradient method for convex optimization. arXiv preprint arXiv:2505.11670, 2025.
Reviewer_2Jn5OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MA4EGMA^4EG, an adaptive accelerated extragradient method for smooth convex–concave minimax problems. By combining adaptive step sizes, adaptive anchor coefficients, and moving-anchor techniques, the method achieves an optimal O(1/k2)O(1/k^2) last-iterate squared gradient norm rate and automatically attains linear convergence under strong convexity–concavity, without prior knowledge of the smoothness or strong convexity parameters, line searches, or restarts. The theoretical guarantees are established through an adaptive Lyapunov analysis, and numerical experiments on five benchmark problems demonstrate competitive performance against existing extragradient-type methods.

Critical strengths

Acceleration and adaptivity without parameter knowledge. The proposed method achieves the optimal O(1/k2)O(1/k^2) last-iterate squared gradient norm rate for smooth convex–concave problems and automatically attains linear convergence under strong convexity–concavity, without prior knowledge of the smoothness constant LL or strong convexity–concavity parameter μ\mu. Notably, these guarantees are achieved using explicit first-order updates, without line searches or restarts.

Critical weaknesses
  1. Limited applicability to constrained minimax problems. The proposed method and its convergence analysis are restricted to unconstrained problems, whereas many practical minimax applications involve nontrivial constraints. In particular, the analysis relies on F(z⋆)=0F(z^\star)=0 and unconstrained extragradient updates, making an extension to constrained settings nontrivial. This restriction limits the applicability of the proposed framework.

  2. Optimality of the adaptive linear convergence rate. Although Theorem 2 establishes automatic linear convergence under strong convexity–concavity without knowing LL or μ\mu, it is unclear whether the resulting convergence rate achieves optimal condition-number dependence in general. In particular, the analysis uses a single strong convexity–concavity parameter μ\mu, without distinguishing the primal and dual curvature parameters (μx\mu_{x} and μy\mu_{y}). A more explicit comparison with the best known SC–SC convergence rates would help clarify the strength of the proposed adaptivity.

Questions for authors

Could the authors clarify whether the moving-anchor mechanism can be extended to constrained convex–concave problems while retaining its accelerated convergence and adaptivity properties, or whether there are fundamental obstacles to such an extension? This would help assess the broader applicability of the proposed framework.

4 comments

Common Response (Repeated in all responses)

We thank the reviewers for their constructive feedback. We were happy to see the reviewers recognize MA$^4$EG’s contributions: simultaneous adaptivity to the smoothness constant LL and strong convexity–concavity parameter μ\mu, an accelerated O(1/k2)O(1/k^2) last-iterate rate in squared gradient norm, and linear convergence under strong convexity–concavity. These guarantees are achieved without prior knowledge of either parameter, line searches, or restarts.

Reviewer ARse identifies no critical weaknesses. Reviewers 67pc and 2Jn5 propose further generalizations, including convergence bounds that reflect local smoothness, extension to constrained setting, and separate primal and dual curvatures μx,μy\mu_x,\mu_y. While these extensions are certainly valuable directions for future work, each of these have the scope of a full research paper, and they are not really weaknesses of the present algorithm or analysis. Nevertheless, in response to Reviewer 2Jn5, we prepared Appendix E (pp. 29–37) which extends MA$^4$EG to constrained minimax problems.

We believe that the contributions of MA$^4$EG constitute a substantial advance that warrants publication. We hope that the suggested generalizations do not overshadow the the volume of contributions that the paper already achieves, and we respectfully ask the AC and reviewers to give these contributions full weight in their final assessment.

Response to Reviewer 2Jn5

We thank the reviewer for the time and the constructive feedback. We would first like to point out that the present work already overcomes several limitations of prior accelerated minimax methods.

(i) MA$^4$EG adapts to the smoothness constant LL without line search or restarts, whereas existing accelerated methods either set their step sizes from LL (Yoon & Ryu, 2021, Lee & Kim, 2021) or rely on backtracking (Lee & Kim, 2021).

(ii) MA$^4$EG also adapts to the strong convexity-concavity parameter μ\mu. The same algorithm attains the optimal O(1/k2)O(1/k^2) last-iterate rate for convex-concave problems and linear convergence for strongly convex-concave problems. To our knowledge, this is the first time both rates are achieved simultaneously by a single algorithm that adapts to both LL and μ\mu, without line search, implicit updates, or restarts.

(iii) The moving-anchor correction is a new mechanism that makes adaptive step sizes compatible with anchoring-based acceleration.

We kindly ask the reviewer to assess our work in light of these contributions. The two directions raised by the reviewer, the extension to constrained problems and the use of separate primal and dual curvatures μx\mu_x and μy\mu_y, are both valuable, and each could be the subject of a separate paper. We view them as natural future directions rather than weaknesses of the present results. Nevertheless, we were able to carry out the first of them in the revision, as described below.

Constrained minimax problems (W1, Q1). We thank the reviewer for raising this point. The reviewer is correct that our analysis uses F(z⋆)=0F(z^\star)=0, which no longer holds at a constrained saddle point. Nevertheless, the standard treatment of constraints through the normal cone carries over to our ideas. Appendix E of the revision (pp. 29–37) extends MA$^4$EG to min⁡x∈Xmax⁡y∈YL(x,y)\min_{x\in\mathcal X}\max_{y\in\mathcal Y}\mathbf L(x,y) with closed convex sets X\mathcal X and Y\mathcal Y. The extension, MA$^4$EG-C (Algorithm 3), adds one projection per iteration and replaces F(zk)F(z_k) by F(zk)+ckF(z_k)+c_k, where ckc_k is a normal-cone element obtained from the projection at no extra cost. It keeps the key properties of MA$^4$EG: no knowledge of LL or μ\mu, no line search or restarts, two operator evaluations per iteration, the accelerated O(1/k2)O(1/k^2) last-iterate rate for convex-concave problems (Theorem 5), and linear convergence under strong convexity-concavity (Theorem 6). When the problem is unconstrained, MA$^4$EG-C reduces to MA$^4$EG. With a fixed step size, a fixed anchor, and βk=1/(k+1)\beta_k=1/(k+1), it reduces to the composite FEG of Cai et al. (2024).

Separate primal and dual curvatures (W2). We thank the reviewer for this insightful question. Like the standard analyses of extragradient-type methods under strong monotonicity, such as SM-EAG+\text{SM-EAG}^{+} (Yoon & Ryu, 2025), our analysis uses a single parameter μ\mu, the strong monotonicity modulus of the saddle operator. To our knowledge, the methods that exploit μx≠μy\mu_x\neq\mu_y to attain the optimal complexity (Zhang et al., 2022, Kovalev & Gasnikov, 2022) set their parameters from LxL_x, LyL_y, LxyL_{xy}, μx\mu_x, and μy\mu_y. We are optimistic that the adaptive step size, adaptive anchor coefficient, and moving anchor of MA$^4$EG can be extended in this direction, but attaining the optimal dependence on μx\mu_x and μy\mu_y without knowing LxL_x, LyL_y, LxyL_{xy}, μx\mu_x, or μy\mu_y goes beyond the scope of the present paper, and we view it as an interesting direction for future research.

We hope that the constrained extension addresses the reviewer's main concern. If so, we kindly ask the reviewer to adjust the score.

References

  • Y. Cai, A. Oikonomou, and W. Zheng. Accelerated algorithms for constrained nonconvex-nonconcave min-max optimization and comonotone inclusion. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of PMLR, pages 5312–5347, 2024.
  • D. Kovalev and A. Gasnikov. The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization. In Advances in Neural Information Processing Systems, volume 35, 2022.
  • S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. In Advances in Neural Information Processing Systems, volume 34, pages 22588–22600, 2021.
  • T. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k2)O(1/k^2) rate on squared gradient norm. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of PMLR, pages 12098–12109, 2021.
  • T. Yoon and E. K. Ryu. Accelerated minimax algorithms flock together. SIAM Journal on Optimization, 35(1):180–209, 2025.
  • J. Zhang, M. Hong, and S. Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194:901–935, 2022.

Thank you for the substantial revision. I appreciate the addition of Appendix E, which addresses my original concern regarding the applicability to constrained minimax problems.

My remaining concern is the characterization of the linear convergence rate under strong convexity-concavity. The analysis still relies on a single strong convexity-concavity parameter μ\mu, without clarifying how the complexity depends on potentially different primal and dual curvature parameters.

I acknowledge that this is a potentially separate research direction, but it leaves the theoretical strength of the linear convergence guarantee insufficiently characterized. I appreciate the authors' additional efforts; however, this concern still affects my overall assessment, and I therefore maintain my original score.

We thank the reviewer for the response.

We agree with the reviewer that exploring different primal and dual curvature parameters is a separate research direction that warrants a follow-up publication.

Reviewer_67pcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work proposes MA$^4$EG that combines extragradient updates with adaptive step size, an adaptive anchoring coefficient with a moving anchor. For LL-smooth convex-concave problems, it achieves an O(k−2)O(k^{-2}) last-iterate rate in squared gradient norm. Furthermore, if the function is μ\mu-strongly convex-concave, the method has linear convergence rate. The method requires no prior knowledge of LL or μ\mu and uses neither line searches nor restarts.

Critical strengths
  • The method adapts simultaneously to the problem-dependent parameters LL and μ\mu without prior knowledge of either, while retaining the accelerated O(1/k2)O(1/k^2) rate in squared gradient norm.

  • The moving-anchor correction compensates for overly large adaptive step size, attaining the accelerated convergence guarantee.

  • The presentation is easy to follow, and the main contribution of the method is clearly stated and compared with the prior works.

  • The provided experiments compare the proposed method with various baseline methods across a range of convex-concave and strongly convex-concave problems.

Critical weaknesses
  • The prefactor CancJC_{\mathrm{anc}}^J in Theorem~1 can be large when the initial estimate R^0\widehat R_0 underestimates LL.

  • The convergence bounds depend on the (global) smoothness parameter LL and do not quantify the empirical gains from adapting to local smoothness.

  • The experiments do not include adaptive accelerated baselines such as FEG-A or an ablation that removes the moving-anchor correction, which appears to be one of the main contributions of this work.

Questions for authors
  • Could the authors compare the explicit constant in the O(1/k2)O(1/k^{2}) bound in Theorem 1 with that of FEG under the same assumptions? It seems that the bound does not establish a (much) smaller constant than FEG's, but the reported experiments show comparable or even faster convergence. Therefore, I think there may exist an example in which the proposed method is much slower than FEG (or other methods). Otherwise, can a theoretical bound explain the comparable or faster convergence observed empirically?

  • Section~2.1 explains the moving-anchor correction through the condition τk+1≥τk+hk\tau_{k+1}\geq\tau_k+h_k. Could the authors provide a 'geometric interpretation' of this correction, especially the +F(zk+1)+F(z_{k+1}) direction? A simple example with and without the correction would help clarify more why it is needed with adaptive step sizes.

  • Can the authors provide a bound that quantifies when adapting to local curvature leads to faster convergence?

  • Can the authors compare against FEG-A [Lee and Kim, 2021] and include a fixed-anchor variant using the same adaptive stepsize, to show the effects of moving-anchor correction more explicitly?

  • (Minor) At the end of the proof outline of Theorem 1, the bound on ∣∣ak−z⋆∣∣||a_k-z^\star|| appears to require equation (8), not (9).

4 comments

Common Response (Repeated in all responses)

We thank the reviewers for their constructive feedback. We were happy to see the reviewers recognize MA$^4$EG’s contributions: simultaneous adaptivity to the smoothness constant LL and strong convexity–concavity parameter μ\mu, an accelerated O(1/k2)O(1/k^2) last-iterate rate in squared gradient norm, and linear convergence under strong convexity–concavity. These guarantees are achieved without prior knowledge of either parameter, line searches, or restarts.

Reviewer ARse identifies no critical weaknesses. Reviewers 67pc and 2Jn5 propose further generalizations, including convergence bounds that reflect local smoothness, extension to constrained setting, and separate primal and dual curvatures μx,μy\mu_x,\mu_y. While these extensions are certainly valuable directions for future work, each of these have the scope of a full research paper, and they are not really weaknesses of the present algorithm or analysis. Nevertheless, in response to Reviewer 2Jn5, we prepared Appendix E (pp. 29–37) which extends MA$^4$EG to constrained minimax problems.

We believe that the contributions of MA$^4$EG constitute a substantial advance that warrants publication. We hope that the suggested generalizations do not overshadow the the volume of contributions that the paper already achieves, and we respectfully ask the AC and reviewers to give these contributions full weight in their final assessment.

Response to Reviewer 67pc

We thank the reviewer for the positive and detailed review. We are happy to hear that the reviewer found the simultaneous adaptivity to LL and μ\mu and the moving-anchor correction to be clear contributions, and the presentation easy to follow. Changes in the revised PDF are marked in blue.

Constants and local smoothness (W1, W2, Q1, Q3). The reviewer is indeed correct that Theorems 1–2 are stated with the global LL, that the prefactor CancJC_{\rm anc}^J can be large when R^0\hat R_0 underestimates LL, and that the bounds alone do not quantify the empirical gains. In our view, however, this is a limitation shared by the literature on adaptive methods rather than a weakness specific to our work. Adaptive methods are motivated by the intuition that convergence should eventually depend only on the local curvature, and not on a poor initial estimate, but to our knowledge, prior analyses, such as those of Malitsky & Mishchenko (2020, 2024), Latafat et al. (2024), and Alacaoglu et al. (2023), also state their guarantees with a worst-case smoothness constant rather than the local curvature eventually encountered. Establishing this property is an important open problem for adaptive optimization as a whole. What our theorems do establish is that a single algorithm, MA$^4$EG, attains both the optimal O(1/k2)O(1/k^2) last-iterate rate for convex-concave problems and linear convergence for strongly convex-concave problems, without knowing LL or μ\mu and without line search or restarts. To our knowledge, MA$^4$EG is the first explicit method to achieve both guarantees with adaptivity. When adaptivity helps is shown empirically: Figures 2(b), 4(b) and 5(b) plot the local estimate ℓk\ell_k against LL, and the improvement appears when ℓk≪L\ell_k\ll L.

FEG-A and the fixed-anchor variant (W3, Q4). We thank the reviewer for these suggestions and added both to the revised version.

(i) FEG-A (Lee & Kim, 2021) is now a baseline in all experiments (Section 3, with the update rule in Appendix A), and every gradient evaluation is counted, including those rejected by backtracking. FEG-A adapts its step size through backtracking but keeps the fixed anchor coefficient βk=1/(k+1)\beta_k=1/(k+1). As a result, it is slower than MA$^4$EG in Experiments 2 and 3 and converges only sublinearly on the strongly convex-concave Experiments 4 and 5, where MA$^4$EG adapts βk\beta_k and converges linearly.

(ii) For the variant with the anchor frozen at z0z_0 (Algorithm 1 without Lines 11–12, which we call A$^3$EG), Section 2 now explains what goes wrong, and Appendix C gives an example. Whenever ⟨F(zk),z0−zk⟩≤0\langle F(z_k),z_0-z_k\rangle\le0, A$^3$EG has τk=0\tau_k=0 and βk=1\beta_k=1, so its next iterate is z0−hkF(z0)z_0-h_kF(z_0): it is sent back to one step from the starting point, however close zkz_k already was to z⋆z^\star. In the example of Appendix C (Figure 6), this happens six times and A$^3$EG stalls at a gradient norm of about 10−510^{-5}, while MA$^4$EG is never reset and converges faster.

Geometric interpretation (Q2). We added this explanation to Section 2. The correction enforces τk+1≥τk+hk\tau_{k+1}\ge\tau_k+h_k, so τk≥h0>0\tau_k\ge h_0>0 and βk<1\beta_k<1 for every k≥1k\ge1, and the reset above cannot occur. If wk=0w_k=0 in Line 11, then ak+1=aka_{k+1}=a_k and the definition of τk+1\tau_{k+1} already gives τk+1≥τk+hk\tau_{k+1}\ge\tau_k+h_k. Otherwise, we need

τk+1=2[⟨F(zk+1),ak+1−zk+1⟩]+∥F(zk+1)∥2≥τk+hk.\tau_{k+1}=\frac{2[\langle F(z_{k+1}),a_{k+1}-z_{k+1}\rangle]_+}{\lVert F(z_{k+1})\rVert^2}\ge\tau_k+h_k.

The anchor enters this condition only through ⟨F(zk+1),ak+1⟩\langle F(z_{k+1}),a_{k+1}\rangle, so the shortest correction moves aka_k along F(zk+1)F(z_{k+1}), by exactly the amount that makes the inequality tight. This yields Line 12 and gives τk+1=τk+hk\tau_{k+1}=\tau_k+h_k.

Minor (Q5). Thank you. The reviewer is correct, and we fixed the reference to (8).

We thank the reviewer again for the encouraging comments and thoughtful questions, which helped us improve the paper.

References

  • A. Alacaoglu, A. Böhm, and Y. Malitsky. Beyond the golden ratio for variational inequality algorithms. Journal of Machine Learning Research, 24(172):1–33, 2023.
  • P. Latafat, A. Themelis, L. Stella, and P. Patrinos. Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient. Mathematical Programming, 2024. doi:10.1007/s10107-024-02143-7.
  • S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. In Advances in Neural Information Processing Systems, volume 34, pages 22588–22600, 2021.
  • Y. Malitsky and K. Mishchenko. Adaptive gradient descent without descent. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of PMLR, pages 6702–6712, 2020.
  • Y. Malitsky and K. Mishchenko. Adaptive proximal gradient method for convex optimization. In Advances in Neural Information Processing Systems, volume 37, 2024.

Thank you for the detailed response. The given explanations and the revisions to the manuscript have addressed most of my questions and provided a better understanding of the contributions. Therefore, I maintain my positive assessment.

We thank the reviewer for the response and constructive feedback, which have helped improve our paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.