- 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 and achieve linear convergence under strong monotonicity without knowing the strong monotonicity parameter . Second, it adapts step size 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 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 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
- 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 . 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?
- 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.
- 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
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 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 by more than , and since never decreases and never exceeds , there are at most 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 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 work with adaptive step sizes. If the anchor is frozen at (Lines 11–12 removed, a variant we call A$^3$EG), an overly aggressive step can make . Then and , and the next iterate jumps back to , however close already was to . 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 , and hence . 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 . 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 .
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.
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 L and strong convexity–concavity parameter μ, an accelerated O(1/k2) 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. 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.