acceptodds
Under review as a conference paper at ICLR 2027

Exact Parameter Regions for Generalized Optimistic Gradient Methods

Abstract

The generalized optimistic gradient method (GOGD) is a one-call method for operator equations that includes the optimistic gradient method as the special case of equal step and correction parameters, yet its full admissible parameter region has remained unknown. For -Lipschitz operators satisfying a weak-Minty condition with parameter and , we characterize exactly the parameter pairs that guarantee bounded iterates with square-summable increments and residuals, and show by a two-dimensional linear counterexample that no other pair does. In particular, equal step and correction parameters are admissible only for small . For monotone operators, the region is exactly the set of parameters yielding weak convergence to a zero from every initialization; for weak-Minty operators, weak convergence follows under standard demiclosedness and solution-set assumptions, with norm convergence in finite dimensions. The proof combines a Lyapunov identity with a matching spectral obstruction and yields best-iterate bounds for squared residuals and increments. Under the stronger pairwise condition of co-hypomonotonicity, we further obtain last-iterate rates on a subregion, and on the full region for affine operators. The new region substantially enlarges previously known sufficient regions, especially as : on a quadratic minimax example with , a parameter rule from the new region uses about times fewer operator evaluations than tuned candidates from earlier regions.

Primary area:
optimization
Keywords:
optimistic gradient descent ascent, weak Minty variational inequalities, nonconvex-nonconcave minimax optimization, co-hypomonotone operators, last-iterate convergence, Lyapunov analysis, step-size selection

Reviews

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

This paper characterizes the exact admissible parameter region of generalized optimistic gradient descent (GOGD) for Lipschitz operators satisfying the weak-Minty condition. The authors establish necessary and sufficient conditions for bounded iterates and square-summable increments and residuals, using a Lyapunov analysis for sufficiency and a two-dimensional linear counterexample for necessity. For monotone operators, the region also characterizes weak convergence of the iterates. Additional last-iterate convergence results are established under co-hypomonotonicity. Numerical experiments demonstrate that the enlarged parameter region can substantially reduce operator evaluations compared with previously known sufficient regions.

Critical strengths

1. Sharp characterization of the admissible parameter region. Unlike previous analyses that establish sufficient parameter conditions, this paper provides an exact characterization for a broad class of weak-Minty operators. I find the matching sufficiency and necessity results particularly valuable, as they clarify the fundamental stability limits of an existing and widely studied method.

2. Meaningful improvement over existing parameter bounds. The new region can be substantially larger than previously known regions, especially as ρL\rho L approaches one. The theoretical improvement is supported by numerical experiments showing considerable reductions in operator evaluations on challenging quadratic minimax instances.

Critical weaknesses

1. Sensitivity to problem constants and practical parameter selection. The admissible region depends on the Lipschitz constant LL and the weak-Minty parameter ρ\rho, which may be difficult to estimate accurately in practice. Moreover, the proposed explicit parameter rule approaches the stability boundary as ρL\rho L tends to one, potentially making it sensitive to errors in these estimates. This limits the immediate practical applicability of the enlarged region.

2. Limited evidence of practical benefits on nonlinear problems. The largest empirical improvements are obtained on structured quadratic instances closely related to the extremal linear operators used to establish the sharpness result. While these experiments effectively illustrate the benefits of the enlarged parameter region, its practical impact on more general nonlinear problems remains less clear. The paper includes a nonlinear Polar game, but this example has a relatively small ρL\rho L, where the difference between the new and previously known parameter regions is less pronounced.

Questions for authors
  1. How robust is the proposed explicit parameter rule to inaccurate estimates of LL and ρ\rho? In particular, when ρL\rho L is close to one, relatively small underestimations of ρ\rho can place the selected parameters outside the admissible region. Could the authors discuss whether a more conservative parameter rule retains most of the empirical improvement?

  2. Could the authors provide additional evidence or discussion regarding the benefits of the enlarged parameter region on nonlinear problems, particularly when ρL\rho L is relatively large? This would help clarify whether the substantial improvements observed near the theoretical stability boundary extend beyond the structured quadratic examples.

1 comment

Thank you for your review. You raise important questions about parameter selection and practical robustness. We agree that the exact admissible region assumes knowledge of the problem constants, which may be difficult to estimate accurately. We have clarified this limitation in Section 4.

Q1. Sensitivity to inaccurate parameter estimates

We agree that the explicit rule (14) is sensitive when ρL\rho L is close to one: it lies close to the boundary of the admissible region and tolerates an underestimation of ρL\rho L of only order (1−ρL)2(1-\rho L)^2. A simple conservative alternative is to reduce α\alpha by 20% while keeping β\beta unchanged. This retains most of the improvement: across the four high-dimensional settings, it increases the number of operator evaluations by 17–19%, and at ρL=0.9\rho L=0.9 it still requires about 15 times fewer evaluations than the best tuned parameters from the earlier GOGD regions.

In return, if LL is known, the reduced rule tolerates any underestimation of ρL\rho L smaller than three-eighths of the estimated gap 1−ρ^L1-\widehat{\rho}L, for every estimate ρ^L∈(0,1)\widehat{\rho}L\in(0,1). On our benchmark with true ρL=0.9\rho L=0.9, the original rule fails to converge for the tested estimates of 0.89 and below, whereas the reduced rule converges for every tested estimate down to 0.85 at essentially unchanged cost. Underestimating LL is tolerated much less, so a valid upper bound on LL should be used. The new Appendix C.5 gives the exact tolerances and this experiment.

Q2. Nonlinear problems with larger ρL\rho L

We have added a nonlinear Polar game with ρL≈0.89\rho L\approx0.89, described in Appendix D.4. On this example, tuning GOGD over our exact region requires about 17 times fewer operator evaluations than tuning over the previous region from Böhm (2023, Theorem A.1).

HPE remains faster on this example. Nevertheless, the experiment shows that the benefit of the enlarged GOGD region is not limited to the quadratic instances used to establish sharpness.

The example is still low-dimensional and structured, and we do not claim that it establishes broad practical superiority. Appendix D.4 provides the experimental setup and detailed results.

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

In this paper, the authors consider the generalized optimistic gradient method (GOGD), a class of first-order methods that has two step-size parameters α\alpha and β\beta, for solving nonlinear equations. Assuming that the operator is LL-Lipschitz and satisfies a weak-Minty condition with parameter ρ\rho, they investigate the admissible choices of α\alpha and β\beta that guarantee convergence. Specifically, when −1≤ρL<1-1\leq \rho L <1, they exactly chracterize the admissible region of (α,β)(\alpha, \beta) that ensures the increments and the operator residuals to converge to 0, which strictly generalizes the existing admissible results for GOGD. Under further regularity conditions on the operator, they also establish weak/strong convergence of the iterates. Moreover, with the stronger assumption of co-hypomonotonicity, they also establish a last-iterate convergence rate of O(1/N)O(1/N) for a more restrictive choice of the parameters.

Critical strengths
  • The theoretical results in the paper are rather comprehensive. Using a carefully chosen Lyapunov potential function, the authors establish the convergence of the generalized optimistic gradient method over a wider choice of (α,β)(\alpha, \beta) than in the existing work. Moreover, when −1≤ρL<1-1 \leq \rho L <1, they also use a two-dimensional linear instance to show that the above conditions on (α,β)(\alpha, \beta) are necessary for convergence, thereby providing a relatively complete characterization of the admissible region for the generalized optimistic gradient method.
  • Overall, the proofs are conceptually clear: the convergence result is based on a potential function argument and the lower bound is based on a simple two-dimensional linear instance.
Critical weaknesses
  • My main concern is that the authors provided little detail on how the potential function in (17) was constructed and only mentioned that it was found with the help of AutoLyap. While this does not affect the correctness of the paper, the potential function is the key ingredient of the convergence proof, and thus it is worth explaining the process of its construction and comparing it with those used in other papers. This way, the readers may gain a better understanding of how this potentially could be generalized to other settings and how it improves upon the existing work.
  • While the authors established the convergence of GOGD for a wider range of parameters, it is unclear whether this actually leads to a better constant in the final convergence rate. In Section 4, the authors only briefly mentioned that the enlarged admissible region can lead to a better constant. My understanding is that the improvement becomes more significant as ρL\rho L approaches 1, which also appears to be the case in the numerical experiments, but the authors should discuss this more thoroughly.
  • The presentation of the paper can be further improved.
    • Proposition 3.4 can be consolidated and presented more concisely. In particular, both (a) and (b) are direct corollaries of (c), and in finite dimensions, convergence in norm directly follows from weak convergence.
    • The discussions about co-hypomonotonicity in Lines 179--185 are not well-organized. I think the authors intend to provide a proof sketch regarding why Condition (6) implies that FF is demiclosed, but in its current form, the arguments are a bit compressed and not very helpful. The authors should also provide a pointer to the complete proof in the appendix.
    • It would also be helpful if the authors could give a proof sketch of Theorem 3.5 and explain how co-hypomonotonicity enables last-iterate rates.
Questions for authors

Please see the "Critical Weaknesses" above.

1 comment

Thank you for the positive assessment and helpful suggestions. We have revised the manuscript to make the Lyapunov construction, convergence constants, and last-iterate analysis easier to understand.

Construction of the potential

Section 5 now explains the construction starting from a shifted iterate, following a similar idea to Böhm (2023, Lemma A.1) and Gorbunov et al. (2023, Lemma C.6). We then introduce correction terms so that the change in the potential can be expressed using the Lipschitz and weak-Minty inequalities. Appendix A.3 explains how these terms and their coefficients are obtained.

An important observation is that both inequalities hold with equality on the planar counterexample. This explains why the Lyapunov analysis and the spectral stability analysis give exactly the same parameter boundary. We have highlighted this connection in Section 6 to provide more intuition about the construction and its sharpness.

Convergence constants

We agree that a larger admissible region does not necessarily imply better convergence constants. Our original discussion was imprecise in this respect. We have therefore revised Section 4 and added Appendix E, where we compare complete residual bounds, including initialization, with those of Böhm (2023, Theorem A.1).

The comparison shows that suitable parameters from our region yield a better certified bound, with an improvement factor of about 1.7 when ρL=0.9\rho L = 0.9. However, the more aggressive parameter rule used in our experiments has a worse certified constant, despite requiring fewer operator evaluations. We now make this distinction explicit.

Presentation and last-iterate convergence

We have consolidated Proposition 3.4, clarified the discussion of demiclosedness, and added a proof sketch after Theorem 3.5. The sketch explains how co-hypomonotonicity allows us to construct a nonincreasing residual quantity, which yields the last-iterate convergence rate. The complete proof is given in Appendix A.5.

Reviewer_sEhYOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the generalized optimistic gradient method (GOGD) with stepsize α\alpha and correction parameter β\beta on problems that satisfy the ρ\rho-weak-MVI (Minty variational inequality) condition. In particular, this paper investigates the exact set of parameters (α,β,ρ)(\alpha, \beta, \rho) that guarantee convergence of GOGD in terms of the (saddle-)gradient norm squared ∥∥F∥∥2\|\|F\|\|^2. The paper shows that asymptotic convergence is achieved in that set, and provides a counterexample that shows nonconvergence outside that set.

Critical strengths

The paper provides an exact characterization of the set that ensures convergence (as mentioned above). More quantitative convergence rates are provided, albeit not in full generality. The technical details and derivations seem sound.

Critical weaknesses

The paper, in its current form, reads like nothing more than a list of technical results. It seriously lacks motivations, such as why we should consider GOGM over other methods and what advantages the method has, why we should be interested in zero finding problems of operators (which form a problem class larger than that of finding zeros of the gradients of the loss functions), why we should consider the ρ\rho-weak-MVI condition, why we should care about the exact parameter regions, etc.
The convergence in ρ\rho-weak-MVIs, in particular, requires extra special discussions, because being a zero of the given operator does not necessarily mean that it is the point we would want to find. For example, as we can see also in the quadratic minimax problem example in the experiments section, (0,0)(0, 0) is a point where the saddle gradient vanishes, but because the objective function is concave-convex, it is by no means optimal and it is the very point we should avoid converging to.

The convergence analysis part also does not go even a single step beyond being a list of technically correct statements. After reading the proofs and analyses, I believe it is natural to expect to gain some takeaways, such as learning some intuition about how the Lyapunov potentials can be built, what new techniques or ideas are proposed, how the analyses could be reused/extended to other methods if possible, etc. Unfortunately, this paper provides very little in this respect; the best I can infer from what is currently written is that the authors used the (already existing) AutoLyap framework, with computers autonomously doing the work, and the human authors simply read the result and formatted the result into the ICLR template file. If this turns out to be the case, it would be very difficult for me to identify what is really novel in this paper.

Questions for authors
  1. It would be great if the authors could provide more motivations regarding this work. Why should we be interested in GOGM over other existing methods? Why is the ρ\rho-weak-MVI condition useful, considering that the convergence guarantee for such problems makes the method converge in minimax problems where the convergence should not occur?

  2. What additional effort was made beyond using the AutoLyap framework and making the computers (and possibly LLMs) work autonomously? Is there something this paper adds to the AutoLyap framework?

  3. What are nn and κ\kappa in the experiments section? Also, Table 1 says the results for Exact-explicit and Exact-tuned are identical, can you explain why this is the case? Moreover, in connection to the first question, other methods seem to be outperforming GOGD, so what (practical) advantages does GOGD have? Does GOGD show good performance on real-world machine learning tasks, or at least beyond toy examples?

1 comment

Thank you for asking us to make the motivation and scientific insight explicit. We have clarified why an exact characterization is useful and how the analytic proof establishes it.

Why study this method and its exact region?

GOGD is an existing, simple single-call method: it stores an operator value and requires no inner solve or line search. The question is where this method works, not whether it dominates all alternatives. Existing analyses give sufficient regions, but whether any of these regions is tight has remained open. Our characterization answers this over the nonlinear weak-Minty class. In particular, it establishes when unequal step and correction parameters are necessary for a class-wide guarantee and quantifies the step sizes excluded by previous analyses.

The characterization also advances the classical monotone case. Corollary 3.3 gives the exact two-parameter region guaranteeing weak convergence to a zero from every initialization for every monotone Lipschitz operator with a nonempty zero set, extending the bilinear characterization of Zhang and Yu (2020, Theorem 3.3). In convex–concave saddle problems, these zeros are saddle points.

Why is zero-finding a meaningful target?

We agree that a zero of a saddle-gradient operator need not solve a minimax problem. The introduction now distinguishes these concepts. Stationarity and variational-inequality solutions under weak-Minty assumptions are established targets in Diakonikolas et al. (2021), Pethick et al. (2022), and Böhm (2023). The absence of a general minimax-optimality guarantee is a limitation shared by this problem class; our contribution is an exact convergence region for an existing method within it.

In the quadratic example, sup⁡yf(x,y)=+∞\sup_y f(x,y)=+\infty for every xx, and strict convexity in yy precludes a local maximizer. There is therefore no global or local minimax point for an algorithm to find. The origin is the unique stationary point, not a saddle. Section 7 now identifies this example as an extremal stability test, not a demonstration of minimax optimization. It appears as a lower-bound construction in Pethick et al. (2022, Example 5), and was also used to evaluate HPE by Pethick et al. (2025, Section 9), rather than being a benchmark introduced here.

The weaker assumption also covers desirable targets. Appendix F gives

\phi(t)=t^2/2+8(1-\cos t).$$ This game is nonconvex–nonconcave, but its unique stationary point is its unique global saddle. The appendix verifies $L=8+\sqrt{26}$ and $\rho=1/16$, giving $\rho L\approx 0.819<1$. Proposition 3.4 therefore guarantees convergence to that saddle from every initial pair when the parameters lie in our region. The example illustrates when the theorem's target has the desired meaning; it does not claim that stationarity always implies optimality. **What insight goes beyond AutoLyap?** Section 5 and Appendix A.3 now reconstruct the potential analytically. A shifted iterate removes the memory term from the update. Cancellation and coefficient matching produce an identity retaining the weak-Minty and Lipschitz slacks, and coercivity is proved separately. Section 6 explains why these slacks vanish on the planar obstruction and why the same coefficient determines descent and spectral stability. This provides a concrete approach to seeking sharp analyses, not only a list of valid inequalities. The paper does not claim to extend AutoLyap. As disclosed in the paper, AI tools assisted the research. However, the suggestion that the authors merely formatted autonomous computer output is not an accurate account of the work. Our contributions are the closed-form exact characterization, its analytic sufficiency proof, and the matching necessity construction. The fixed-parameter numerical search performed by AutoLyap does not by itself establish these results, and each can be checked independently of how it was found. **Experimental questions** Section 7 now defines $n$ as the real dimension and $\kappa$ as the singular-value condition number. Exact-explicit and Exact-tuned coincided because the explicit pair was among the 32 candidates and was selected at all four settings. Tables 1 and 2 now list the shared values once. We do not claim that GOGD is generally faster than HPE or AdaptiveEG+. Both outperform GOGD in several reported settings; HPE is also faster in the larger-parameter Polar case in Appendix D.4. The experiments compare parameter regions of GOGD; we have not evaluated real-world learning tasks. The motivation for the theorem is to identify the exact limits of this simple existing method, with the experiments illustrating consequences rather than establishing a new algorithm.

Comments on the paper

1 comment

We thank the reviewers for their careful reading and constructive feedback. We have revised the manuscript to better explain the motivation, the Lyapunov analysis, and the significance of the exact parameter characterization.

In particular, we have clarified how the potential function is constructed, corrected the comparison of convergence constants, and expanded the explanation of the last-iterate result. We have also clarified the distinction between stationarity and minimax optimality, and added a sensitivity analysis of the explicit parameter rule and a nonlinear experiment with a larger weak-Minty parameter.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.