acceptodds
Under review as a conference paper at ICLR 2027

Obtaining First-Order Game-Stationary Points for Smooth Nonconvex–Nonconcave Minimax Problems via First-Order Methods

Abstract

Minimax optimization is a fundamental framework in machine learning, robust optimization, and game theory, yet finding first-order stationary points of general nonconvex–nonconcave minimax problems remains challenging without additional structural assumptions. Existing guarantees often rely on global PL- or KL-type conditions that connect max-player stationarity to global inner optimality, or on Minty-type conditions that impose a global relation on the game gradient field relative to a reference solution; local KL variants relax the former requirement but typically require initialization and tracking within a near-optimal region. Such conditions may be difficult to satisfy in many applications. In contrast, we develop a first-order method that finds an \(\epsilon\)-stationary point within \(\mathcal O(\epsilon^-2)\) first-order iterations under a local inverse-Lipschitz regularity condition around approximate max-player stationary points, together with a compactness condition on a penalty sublevel set. Our condition places no optimality requirement on stationary points of the inner maximization problem: they need not be globally, or even locally, maximizing. We further provide sufficient conditions for the required regularity. In the unconstrained setting, it follows from uniform nonsingularity of the maximization-variable Hessian near stationary points; for constrained upper Moreau envelopes, it follows from standard KKT regularity conditions. These results establish first-order complexity guarantees for classes of nonconvex–nonconcave minimax problems not covered by the above PL-, KL-, or Minty-type frameworks.

Primary area:
optimization
Keywords:
minimax, first-order, nonconvex

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_z2GVOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studied nonconvex–nonconcave minimax problems, under additional structural assumptions. They proposed a first-order algorithm based on the penalty method, and derives O~(ϵ−2)\tilde{O}(\epsilon^{-2}) convergence rate. The paper also provides sufficient conditions for the proposed regularity assumption, including Hessian nondegeneracy and certain KKT conditions. Numeircal experiments are provided to show the outperformace of the proposed method.

Critical strengths
  1. The paper studied game stationarity in nonconvex–nonconcave minimax optimization under structural assumptions, which do not require the inner stationary points to be globally optimal.
  2. Theorem 3.1 transfers approximate penalty stationarity to game stationarity, which is a meaningful contribution.
Critical weaknesses
  1. The motivation for and practical relevance of the proposed assumptions insufficiently developed. Although the authors provide sufficient conditions and examples for the local inverse-Lipschitz regularity assumption, the scope and restrictiveness of the combined assumptions, especially the compact-sublevel condition, remain unclear. A more systematic comparison with existing NC-(Strongly-Concave)/PL/KL works can further help to understand the significance of the proposed assumptions. Moreover, it would help to further strengthen the significance if authors can provide more representative nonlinear examples or applications (beyond quadratic problems in the experiments) satisfying the proposed assumptions.
  2. The presentation could be substantially improved, particularly in terms of the flow the paper story, the definitions of mathematical statements and the justification of key assumptions.
Questions for authors
  1. Proposition 2.4 considers the special case where$F$ admits a Moreau envelope representation. I wonder how restrictive this structural requirement is in practice. In general, evaluating such an envelope and its gradient should be hard as a closed-form solution is often unavailable (different from your Example 2.5). Could the authors elaborate on the practical applicability of this formulation.
  2. Can you further elaborate on the difference between your results and Tsaknakis & Hong, 2021 (like formulation, assumptions, stationarity guarantees, and complexities)? Also do you think it is necessary to add their algorithms (or similar RNI-type algorithms) into your numerical experiments?
5 comments
AuthorsOpenReview ↗

Response to Reviewer z2GV (1/4): Scope and Restrictiveness of the Assumptions

We thank the reviewer for the careful reading and the constructive comments.

W1. Scope and restrictiveness of the assumptions

Geometrically, our method stabilizes the consistency between the current max-player iterate and its proximal point. The proximal term makes this point unique and Lipschitz continuous, while the gap penalty measures the inconsistency between the two and vanishes exactly at max-player stationary points. The penalty can be viewed locally as creating a valley around the max-player stationary set. Assumption 2 ensures that this valley is bounded: its floor does not run off to infinity. Assumption 3 ensures that the penalty adds curvature that penalizes departures from this set.

Together, the two assumptions cover problems in which the penalty function has compact sublevel sets and a local regularity condition holds at the max-player stationary points in such a set. Below, each assumption is followed by verifiable sufficient conditions; these are stronger than what Theorem 3.1 needs, and their purpose is to let one check whether a given problem fits the method. The comparison with strong concavity, one-sided PL and one-sided KL follows in the next comment.

Assumption 2: Compactness of penalty sublevel sets. Assumption 2 requires that, for a fixed penalty parameter ρc\rho_c, the sublevel sets of PρcP_{\rho_c} are compact. The penalty term ρG\rho \mathcal G is of the order of ρ∥∇yF(x,y)∥2\rho\Vert\nabla_y F(x,y)\Vert^2. Hence, when ∥∇yF(x,y)∥2\Vert\nabla_y F(x,y)\Vert^2 grows in yy fast enough to dominate the decrease of FF, the assumption holds once ρc\rho_c is sufficiently large.

Sufficient conditions checkable from FF:

  • Proposition 2.2 (proof in Appendix A.2) gives a sufficient condition by imposing growth conditions on FF. These conditions hold for objectives with a coercive regularizer for each player in which the max-player regularizer dominates the coupling loss.
  • Remark 2.1 gives two further cases (Propositions A.3 and A.4 in Appendix A.3): (1) the max-player objective is strongly concave and F⋆(x):=max⁡yF(x,y)F^\star(x):=\max_y F(x,y) has compact sublevel sets; (2) the max-player is constrained to a compact set, in which case it suffices that the constrained objective is coercive in xx. Both conditions are natural here, since xx is the minimized variable and the objective is usually bounded below in xx.

Assumption 3: Local inverse-Lipschitz regularity. Within the compact sublevel set containing our initial point, Assumption 3 requires that, when yy and w=w(x,y)w=w(x,y) are sufficiently close and both approximately max-player stationary,

\le \kappa_s\Vert\nabla_y F(x,w)-\nabla_y F(x,y)\Vert.$$ It can be verified in two standard settings: - **Unconstrained max-player (Proposition 2.5, proof in Appendix A.5.1).** When the objective is $C^2$, Assumption 3 holds if $\nabla^2_{yy}F$ is nonsingular at the max-player stationary points, with no sign condition. This is strong metric regularity of $\nabla_yF(x,\cdot)$, a well-studied condition (Robinson, 1980; Dontchev & Rockafellar, 2014). It gives the inverse-Lipschitz inequality for arbitrary pairs $y,y'$ near a stationary point, whereas Assumption 3 needs it only for the proximal pair. - **Constrained max-player (Proposition 2.6, proof in Appendix A.5.2).** Although our method is stated for unconstrained problems, it also applies when the max-player is constrained: we pass to the upper Moreau envelope of the objective, and our assumptions can then be verified directly from properties of the constrained problem. Proposition 2.6 does this for Assumption 3 in a standard problem formulation that encompasses budget-constrained adversarial training as an important practical application (see the discussion after Proposition 2.6 in Section 2). Its conditions are the standard ones for a well-behaved KKT system: the Slater condition, strict complementarity (an active budget has a positive multiplier), and a nonsingular reduced Lagrangian Hessian, which holds automatically when the multiplier is large enough. **Examples that satisfy all assumptions but fail one-sided PL/KL.** The paper provides two explicit examples that satisfy all of Assumptions 1–3, and hence all conditions of our main convergence guarantee, while violating the one-sided PL/KL conditions: Example 2.7 and Example A.7 (verified in Propositions B.1 and B.2 in Appendix B).
AuthorsOpenReview ↗

Response to Reviewer z2GV (2/4): Comparison with NC-SC, PL, and KL, and Nonlinear Examples

W1 (continued). Systematic comparison with NC-(Strongly-Concave)/PL/KL

The two assumptions play separate roles and are checked separately, so we compare each of them with the existing conditions in turn.

Assumption 2. It is a joint growth condition on FF and ∥∇yF∥2\Vert\nabla_yF\Vert^2. Under strong concavity of the max-player objective, it holds if F⋆(x):=max⁡yF(x,y)F^\star(x):=\max_yF(x,y) has compact sublevel sets (Remark 2.1).

Assumption 3.

  • Strong concavity. If F(x,⋅)F(x,\cdot) is μ\mu-strongly concave, the inequality holds globally, for arbitrary pairs, with κs=1/μ\kappa_s=1/\mu.
  • PL. The one-sided μ\mu-PL condition implies Assumption 3 with κs=2/μ\kappa_s=2/\mu when F(x,⋅)F(x,\cdot) is C2C^2 and its yy-Hessian is Lipschitz continuous uniformly in xx (Remark 2.4, with the proof in Proposition A.8, Appendix A.5.3).
  • Strictness (Example 2.7). Both implications are strict: Assumption 3 allows max-player stationary points that are not maximizers, which strong concavity and PL exclude.
  • KL. For the general KL condition ∥∇yF(x,y)∥≥c (F⋆(x)−F(x,y))θ\Vert\nabla_yF(x,y)\Vert\ge c\thinspace(F^\star(x)-F(x,y))^\theta with θ>1/2\theta>1/2, neither condition implies the other: KL allows flat maxima, at which Assumption 3 can fail, and Assumption 3 allows non-maximizing stationary points, which violate KL.

For flat maxima, where Assumption 3 can fail, Appendix C replaces Assumption 3 by a weaker cross-gradient condition (Assumption 4) and gives a gradient complexity of O~(ε−4)\tilde O(\varepsilon^{-4}) (Corollary C.4). The contribution of the paper is a different structural route: a penalty reformulation with stationarity transfer yields game-stationary points by first-order methods.

W1 (continued). Nonlinear examples and applications beyond quadratic problems

  • Experiment. The test problem in Section 4 is a smooth nonlinear nonconvex–nonconcave problem containing the term −4∑icos⁡xi-4\sum_i\cos x_i, in dimensions 3 and 30.
  • Applications. Remark 2.3 gives a general regularized template that covers robust regression, adversarial training with penalized perturbations, and Wasserstein GANs with a penalized critic. Example A.7 gives an explicit robust-regression instance on which all assumptions are verified (Proposition B.2, Appendix B).
AuthorsOpenReview ↗

Response to Reviewer z2GV (3/4): Practical Applicability of the Moreau-Envelope Formulation

Q1. Practical applicability of the Moreau-envelope formulation

At first glance, applying our method to the Moreau-envelope reformulation appears to require computing the Moreau envelope of another Moreau envelope, which might suggest an additional layer of computational overhead. However, a simple derivation shows that these two nested Moreau envelopes can be equivalently expressed as a single Moreau envelope with a modified parameter. Consequently, evaluating the nested envelope requires solving only one proximal subproblem, rather than two nested proximal problems. Therefore, the nested Moreau-envelope structure does not introduce additional computational overhead.

Specifically, the envelope representation is a reformulation of the constrained problem

min⁡xmax⁡c(u)≤0g(x,u),\min_x\max_{c(u)\le0}g(x,u),

not an additional restriction on it.

For F=FλF=F_\lambda, the penalty function simplifies to

Pρ=Fλ+ρ(Fλp−Fλ),λp=λpλ+p.P_\rho=F_\lambda+\rho(F_{\lambda_p}-F_\lambda), \qquad \lambda_p=\frac{\lambda p}{\lambda+p}.

The key identity follows from

max⁡v{−λ2∥u−v∥2−p2∥v−y∥2}=−λp2(λ+p)∥u−y∥2.\max_v \left\lbrace -\frac{\lambda}{2}\Vert u-v\Vert^2 -\frac{p}{2}\Vert v-y\Vert^2 \right\rbrace = -\frac{\lambda p}{2(\lambda+p)} \Vert u-y\Vert^2.

Thus, the nested envelope reduces to a single proximal maximization problem with parameter λp\lambda_p. The resulting expression of PρP_\rho is stated after Proposition 2.6 in Section 2. If the reviewer considers the derivation helpful, we would be glad to add it.

As a result, computing the gradient of PρP_\rho only requires the maximizers of two single-level constrained problems,

Fη(x,y)=max⁡c(u)≤0{g(x,u)−η2∥u−y∥2},F_\eta(x,y) = \max_{c(u)\le0} \left\lbrace g(x,u)-\frac{\eta}{2}\Vert u-y\Vert^2 \right\rbrace,

with η=λ\eta=\lambda and η=λp\eta=\lambda_p, respectively. No nested optimization is needed.

Both problems are strongly concave when λp>Lg\lambda_p>L_g, and projected gradient ascent solves them at a linear rate.

The effect of these inexact solutions can be analyzed in the same way as in Theorem 3.5. In general, if the inner solutions have error at most δ\delta, the gradient g~k\tilde g^k that is used satisfies

∥g~k−∇Pρ(zk)∥=O(ρδ).\Vert\tilde g^k-\nabla P_\rho(z^k)\Vert = O(\rho\delta).

With step size 1/Lρ1/L_\rho, the descent lemma gives

Pρ(zk+1)≤Pρ(zk)−12Lρ∥∇Pρ(zk)∥2+12Lρ∥g~k−∇Pρ(zk)∥2.P_\rho(z^{k+1}) \le P_\rho(z^k) -\frac{1}{2L_\rho}\Vert\nabla P_\rho(z^k)\Vert^2 +\frac{1}{2L_\rho} \Vert\tilde g^k-\nabla P_\rho(z^k)\Vert^2.

The function value decreases as long as ∥∇Pρ(zk)∥\Vert\nabla P_\rho(z^k)\Vert exceeds the gradient error, so the iterates remain in K\mathcal K up to the first index kk at which

∥∇Pρ(zk)∥2=O(1/N+δ2).\Vert\nabla P_\rho(z^k)\Vert^2 = O(1/N+\delta^2).

Summing the descent inequality shows that such an index exists among the first NN iterations.

Taking δ=O(ε)\delta=O(\varepsilon) and N=O(ε−2)N=O(\varepsilon^{-2}) makes this bound at most (ε/Cρ)2(\varepsilon/C_\rho)^2, and Theorem 3.1 then gives an ε\varepsilon-game-stationary point.

Each inner solve costs O(log⁡(1/δ))O(\log(1/\delta)) gradient evaluations, so the total is

O~(ε−2)\tilde O(\varepsilon^{-2})

(Corollary 3.6).

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

This paper studies nonconvex-nonconcave minimax problems through a penalty function. Under a compactness assumption of the sublevel set and a local regularity condition, the (approximate) stationary points of this function are related to the stationary points of the original objective. Moreover, it is shown to be Lipschitz smooth, after which a standard gradient descent method is applied.

Critical strengths

The paper studies an important problem and there do not seem to be major errors in the results.

Critical weaknesses

The writing quality of the paper could be better. The authors introduce many auxiliary notations with long dependencies, see for example Line 276 which defines a constant CyC_y that depends on DD, which in turn depends on BB, C0C_0, F‾K\underline{F}_{\mathcal{K}}, … Moreover, the appendix does not contain a single citation, even though important prior results are named (Danskin, singular-value perturbation inequalities, the standard gradient descent analysis has been redone in Theorem 3.4!)

There is discussion lacking on the motivation of the assumptions and their strictness. Assumption 2 is stronger than assuming that the iterates are bounded; is it much stronger? Further, Assumption 3 is related to strong metric regularity which is not mentioned at all. The proof of Proposition 2.3 follows from standard arguments in the related literature that should be mentioned, see “Dontchev & Rockafellar, Implicit Functions and Solution Mappings: A View from Variational Analysis”. Similarly, Proposition 2.4 can be simplified considerably. Lastly, a more thorough comparison with PL type conditions should also be given. An example is already provided that is not PL but satisfies the assumptions of the paper. What about the converse?

Minor comments:

  • Line 89: The statement that the Minty condition imposes a global condition should be relaxed slightly. It need only hold on a ball containing the iterates. See Remark 3.3 in (Diakonikolas et al., 2021).
  • Line 158: the stated smoothness definition is wrong. The constant in Lemma 2.1(v) is therefore also wrong.
  • Line 216: K\mathcal{K} should be explicitly assumed compact
  • Line 313: F‾\overline{F} is undefined
  • Line 972: Should be Proof of Theorem 3.1
  • The paper implicitly assumes sup⁡yF(x0,y)<∞\sup_y F(x^0, y) < \infty for some x0x^0. This assumption does not hold for the simple toy experiment that they consider.
Questions for authors

Aside from the questions mentioned in the weaknesses, could the method from (Raghunathan et al., 2019) also be included in the experiment?

6 comments
AuthorsOpenReview ↗

Response to Reviewer WFko (1/4): Assumption 2 and Bounded Iterates

We thank the reviewer for the careful reading and pointing out the typos and missing citations.

W2, part 1. Is Assumption 2 much stronger than bounded iterates?

We agree that Assumption 2 implies bounded iterates.

Importantly, we emphasize that all our theoretical guarantees remain valid under the bounded-iterates assumption, provided Assumption 3 holds on a compact set containing the iterates. Thus, the compact-sublevel-set condition in Assumption 2 is not essential to our theoretical analysis; rather, it provides a verifiable sufficient condition for boundedness of the iterates.

We restated Assumption 2 in a simpler form: for a fixed penalty parameter ρc\rho_c, the sublevel sets of the penalty function PρcP_{\rho_c} are compact. The penalty term ρG\rho \mathcal G is of the order of ρ∥∇yF(x,y)∥2\rho\Vert\nabla_y F(x,y)\Vert^2. Hence, when ∥∇yF(x,y)∥2\Vert\nabla_y F(x,y)\Vert^2 grows in yy fast enough to dominate the decrease of FF, the assumption holds once ρc\rho_c is sufficiently large.

We state Assumption 2 in this form since it is a property of the problem that can be checked before the method is run, whereas boundedness of the iterates depends on the trajectory. Moreover, it can be verified from FF through the sufficient conditions:

  • Proposition 2.2 (proof in Appendix A.2) gives a sufficient condition by imposing growth conditions on FF. These conditions hold for objectives with a coercive regularizer for each player in which the max-player regularizer dominates the coupling loss, a common setting in robust regression, adversarial training with penalized perturbations, and Wasserstein GANs with a penalized critic (Remark 2.3).
  • Remark 2.1 gives two further cases (Propositions A.3 and A.4 in Appendix A.3): (1) the max-player objective is strongly concave and F⋆(x):=max⁡yF(x,y)F^\star(x):=\max_y F(x,y) has compact sublevel sets; (2) the max-player is constrained to a compact set and the constrained objective is coercive in xx.

Besides, Assumption 2 is a condition on PρcP_{\rho_c}, not on FF, and FF may be unbounded below. It plays a role analogous to that of a lower bound on the objective function in nonconvex minimization.

AuthorsOpenReview ↗

Response to Reviewer WFko (2/4): Assumption 3 and Strong Metric Regularity

W2, part 2. Assumption 3 and strong metric regularity; Propositions 2.3 and 2.4 (now 2.5 and 2.6)

We agree that Assumption 3 is closely related to strong metric regularity. The connection is now stated in the main text right after Proposition 2.5, with references to Robinson (1980) and to Dontchev & Rockafellar (2014), and the appendix cites these references where the corresponding arguments are used.

  • Assumption 3 is strictly weaker than strong metric regularity. It requires the inverse-Lipschitz bound only for the proximal pairs (y,w(x,y))(y,w(x,y)), not for all pairs near a max-player stationary point. For example, take F(x,y)=f(x)−12y12F(x,y)=f(x)-\tfrac12y_1^2 with y∈R2y\in\mathbb R^2. The Hessian ∇yy2F=diag(−1,0)\nabla^2_{yy}F=\mathrm{diag}(-1,0) is singular at every max-player stationary point, so strong metric regularity fails. Yet w−y=−y11+pe1w-y=-\tfrac{y_1}{1+p}e_1 and ∇yF(x,w)−∇yF(x,y)=y11+pe1\nabla_yF(x,w)-\nabla_yF(x,y)=\tfrac{y_1}{1+p}e_1, so ∥w−y∥=∥∇yF(x,w)−∇yF(x,y)∥\Vert w-y\Vert=\Vert\nabla_yF(x,w)-\nabla_yF(x,y)\Vert everywhere and Assumption 3 holds with κs=1\kappa_s=1. This example is not in the current revision; we would be glad to add it if the reviewer finds it helpful.

  • Proposition 2.5 (proof in Appendix A.5.1). The hypothesis of Proposition 2.5 is closely related to strong metric regularity, and the two are equivalent when FF is C2C^2 (Robinson, 1980; Dontchev & Rockafellar, 2014). We keep our formulation because it is easier to verify: it is a pointwise nonsingularity condition on ∇yy2F\nabla^2_{yy}F, whereas strong metric regularity is a property of the stationarity mapping on a neighbourhood of each stationary point and is typically established through an implicit-function-type argument. Our proof is self-contained: it derives Assumption 3 directly from this hypothesis, without relying on the strong metric regularity theory.

  • Proposition 2.6 (proof in Appendix A.5.2). This proposition is a simple concrete example of how our method extends to a constrained max-player and how the assumptions can be verified in that case. Its statement is now more compact: the former hypotheses (iii) and (iv) are merged into a single hypothesis (iii), which is imposed at the KKT points of the near-stationary pairs in the enlarged set K+\mathcal K^+ (those with ∥∇yF(x,y)∥≤ηM\Vert\nabla_yF(x,y)\Vert\le\eta_M). Hypothesis (iii) is the classical nondegeneracy condition for constrained problems: strict complementarity together with a nonsingular reduced Hessian.

We use these two propositions as standard, verifiable conditions that illustrate the applicability of our method. They are not the main contribution of this paper. To keep the paper self-contained, we prove directly that each of them implies Assumption 3, and the revision acknowledges the related literature where they appear.

More importantly, strong metric regularity is a well-established and widely used condition in optimization and variational analysis. The fact that this classical condition implies our inverse-Lipschitz regularity condition further supports the naturalness and practical relevance of Assumption 3. At the same time, our condition is strictly weaker than strong metric regularity, as it only requires the inverse-Lipschitz bound for proximal pairs rather than arbitrary nearby points. Thus, our assumption is both well motivated by classical regularity theory and applicable to a broader class of problems.

AuthorsOpenReview ↗

Response to Reviewer WFko (3/4): Comparison with PL Conditions

W2, part 3. Comparison with PL conditions

We would first like to emphasize that when F(x,⋅)F(x,\cdot) is C2C^2 and its yy-Hessian is Lipschitz continuous uniformly in xx, the one-sided μ\mu-PL condition implies our Assumption 3, with κs=2/μ\kappa_s=2/\mu. Therefore, within this commonly studied smoothness class, our Assumption 3 is strictly weaker than the one-sided PL condition. We have included this result in Remark 2.4, with a detailed proof in Proposition A.8 (Appendix A.5.3).

Consequently, to construct an example that satisfies the PL condition but violates Assumption 3, the Lipschitz continuity of the Hessian must fail. In particular, this can happen when the Hessian is discontinuous. We can indeed construct such an example, which has a Lipschitz-continuous gradient and satisfies the PL condition but violates Assumption 3.

Consider the following one-dimensional example.

Let F(y)=−∫0yg(t) dtF(y)=-\int_0^y g(t)\thinspace dt for y∈Ry\in\mathbb R, where

g(t)=tfor t≤0,g(t)=t \quad \text{for }t\le0,

and

\quad\text{for }a\le t<2a, \quad a=2^k,\ k\in\mathbb Z.$$ It is continuous and nondecreasing. Hence $F$ is concave with the Lipschitz gradient $F'=-g$, and $0$ is its unique maximizer. **PL holds.** Since $\frac23|t|\le|g(t)|\le|t|$ for all $t$, we have $$F(0)-F(y)=\int_0^yg(t)\thinspace dt\le\tfrac12y^2,$$ and therefore $$|F'(y)|^2=g(y)^2 \ge \tfrac49y^2 \ge 2\cdot\tfrac49\bigl(F(0)-F(y)\bigr),$$ which is the PL condition with $\mu=4/9$. **Assumption 3 fails.** Fix $p>2$ and $a=2^k$, and take $w=a$ and $y=(1+1/p)a$. Both points lie in $[a,\tfrac32a]$, where $g\equiv a$, so $$F'(w)=F'(y)=-a=p(w-y).$$ The equality $F'(w)=p(w-y)$ is the optimality condition of the strongly concave problem $$\max_u\left\lbrace F(u)-\tfrac p2(u-y)^2\right\rbrace,$$ hence $w$ is the proximal point of $y$. For this proximal pair, $$|w-y|=a/p>0,$$ while $$F'(w)-F'(y)=0.$$ Thus, the inequality of Assumption 3 fails for every $\kappa_s$. Letting $k\to-\infty$, such pairs exist arbitrarily close to the stationary point $0$. In this example, the Hessian is not continuous, and therefore does not satisfy the Lipschitz-continuity condition required for the PL implication above. This illustrates why the additional Hessian regularity matters. If the reviewer consider this counterexample helpful, we would be happy to include it in the revised manuscript. For this type of function, Appendix C replaces Assumption 3 by a weaker cross-gradient condition (Assumption 4) and gives a gradient complexity of $\tilde O(\varepsilon^{-4})$ (Corollary C.4). Overall, under the mild additional condition of a Lipschitz-continuous Hessian, one-sided PL implies our Assumption 3, whereas the converse does not hold, demonstrating that our regularity condition is strictly weaker within this smoothness class.
Reviewer_zAPKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes a penalty method for finding approximate game-stationary points in smooth nonconvex–nonconcave minimax problems. Unlike existing approaches that rely on P--L or K--L conditions, or whose surrogate stationary points do not necessarily correspond to those of the original problem, this work establishes an O~(ϵ−2)\widetilde{\mathcal{O}}(\epsilon^{-2}) first-order complexity guarantee under a local inverse-Lipschitz regularity condition near max-player stationary points and a compactness condition on the penalty sublevel set.

Critical strengths

The paper introduces an alternative set of assumptions for finding game-stationary points in nonconvex–nonconcave minimax problems and develops a corresponding penalty-based first-order method. This avoids imposing restrictive global P--L or K--L conditions, which is a meaningful contribution.

Critical weaknesses

The proposed assumptions are not sufficiently discussed, particularly their geometric interpretation and how restrictive they are compared with existing P--L and K--L conditions.

The theoretical results are somewhat difficult to follow. In particular, Lemma 2.1 and Proposition 2.4 involve numerous technical statements and conditions, but the logical connections among them and their roles in the overall analysis are not sufficiently explained.

Questions for authors

The motivation for seeking game-stationary points is not sufficiently discussed. Since these points do not necessarily correspond to Nash equilibria or local minimax solutions, their practical significance remains unclear. Experiments on a representative game-theoretic application would help demonstrate the usefulness of the proposed method.

The convergence rate is not sufficiently compared with existing results, making it difficult to assess its significance relative to the literature. A comparison table summarizing the convergence rates and underlying assumptions of existing methods would be helpful.

Penalty-based methods have been widely studied in related fields, such as bilevel optimization. However, the discussion of these works is insufficient, and the differences between the proposed method and existing penalty-based approaches are not clearly explained.

6 comments
AuthorsOpenReview ↗

Response to Reviewer zAPK (1/4): Motivation and Strictness of the Assumptions

We thank the reviewer for the careful reading and for identifying where the assumptions, theoretical results, and motivation need clearer explanations.

W1. Geometric interpretation and restrictiveness of the assumptions

We revised the statement of Assumptions 2 and 3 in Section 2 to make them easier to read and clarified their relationship to standard conditions (Remarks 2.1 and 2.4). For clarity, the revised assumptions are stated in a form that is somewhat stronger than what the stationarity-transfer theorem (Theorem 3.1 in Section 3) actually needs.

Geometrically, our method stabilizes the consistency between the current max-player iterate and its proximal point. The gap penalty measures the inconsistency between the two and vanishes exactly at max-player stationary points. It can be viewed locally as creating a valley around the max-player stationary set. Assumption 2 ensures that this valley is bounded: its floor does not run off to infinity. Under our regularity condition, the penalty adds curvature that penalizes departures from the set. The resulting penalty function balances the original objective with this consistency requirement. This interpretation is now given in Section 1.2.

AuthorsOpenReview ↗

Response to Reviewer zAPK (2/4): Assumptions 2 and 3, Sufficient Conditions, and Comparison with PL and KL

W1 (continued). Assumptions 2 and 3 compared with PL and KL conditions

Assumption 2: Compactness of penalty sublevel sets. Assumption 2 now requires that, for a fixed penalty parameter ρc\rho_c, the sublevel sets of PρcP_{\rho_c} are compact. The penalty term ρG\rho \mathcal G is of the order of ρ∥∇yF(x,y)∥2\rho\Vert\nabla_y F(x,y)\Vert^2 (see Eq. (9)). Hence, when ∥∇yF(x,y)∥2\Vert\nabla_y F(x,y)\Vert^2 grows in yy fast enough to dominate the decrease of FF, the assumption holds once ρc\rho_c is sufficiently large.

Assumption 2 is a condition on PρcP_{\rho_c}, not on FF, and FF may be unbounded below. It plays the role that a lower bound on the objective plays in nonconvex minimization (Remark 2.1).

We also provide verifiable sufficient conditions:

  • Proposition 2.2 (with proof in Appendix A.2) gives a sufficient condition by imposing growth conditions on FF. These conditions hold for objectives with a coercive regularizer for each player in which the max-player regularizer dominates the coupling loss, as in robust regression, adversarial training with penalized perturbations, and Wasserstein GANs with a penalized critic (Remark 2.3 with details in Appendix A.4).
  • Remark 2.1 gives two further cases (Propositions A.3 and A.4 in Appendix A.3): (1) the max-player objective is strongly concave and F⋆(x):=max⁡yF(x,y)F^\star(x):=\max_y F(x,y) has compact sublevel sets; (2) the max-player is constrained to a compact set and the constrained objective is coercive in xx.

Assumption 3: Local inverse-Lipschitz regularity. Assumption 3 is strictly weaker than strong concavity of the max-player objective. Within the class of C2C^2 objectives with a Lipschitz-continuous yy-Hessian, it is also strictly weaker than the one-sided PL condition.

Within the compact sublevel set K\mathcal K that contains our initial point, Assumption 3 requires that, when yy and w=w(x,y)w=w(x,y) are sufficiently close and both approximately max-player stationary,

\le \kappa_s\Vert\nabla_y F(x,w)-\nabla_y F(x,y)\Vert.$$ Importantly, we require this condition to hold **only locally and only on the proximal pair** $(y,w(x,y))$, instead of on arbitrary pairs of points. If $F(x,\cdot)$ is $\mu$-strongly concave, the inverse-Lipschitz inequality holds globally for arbitrary pairs, with constant $1/\mu$. Moreover, if $F(x,\cdot)$ is $C^2$ and its $y$-Hessian is Lipschitz continuous uniformly in $x$, the one-sided $\mu$-PL condition implies Assumption 3 with $\kappa_s=2/\mu$ (Remark 2.4, with a detailed proof in Proposition A.8, Appendix A.5.3). **These implications are strict:** Assumption 3 allows max-player stationary points that are not maximizers, whereas strong concavity and the one-sided PL condition rule out such points. We provide two concrete examples that satisfy all of Assumptions 1–3, and hence all conditions of our main convergence guarantee, while violating the one-sided PL and one-sided KL conditions: Example 2.7 (verified in Proposition B.1, Appendix B) and the explicit robust-regression instance of Example A.7 (verified in Proposition B.2, Appendix B). In particular, for $C^2$ objectives, Assumption 3 holds whenever $\nabla^2_{yy}F$ is nonsingular at the max-player stationary points in $\mathcal K$, with no definiteness requirement (Proposition 2.5). It therefore accommodates nondegenerate inner local minima and saddle points as well as local maxima. For one-sided KL conditions $$\Vert\nabla_yF(x,y)\Vert \ge c (F^\star(x)-F(x,y))^\theta$$ with exponent $\theta>1/2$, neither condition implies the other in general: such KL conditions allow flat maxima at which Assumption 3 can fail, while Assumption 3 allows nonmaximizing stationary points that violate the one-sided KL condition (Remark 2.4, with the example $F(x,y)=f(x)-y^4/4$). **Further relaxation.** We further relax Assumption 3 to a weaker cross-gradient condition (Assumption 4 in Appendix C), covering some flat cases excluded by Assumption 3. Under this weaker condition, stationarity still transfers (Theorem C.2), and our method achieves a gradient complexity of $\tilde O(\varepsilon^{-4})$ (Corollary C.4).
AuthorsOpenReview ↗

Response to Reviewer zAPK (3/4): Theoretical Results, Motivation, and Penalty Methods

W2. Roles of Lemma 2.1 and Proposition 2.4

In the overall analysis, Lemma 2.1 (now Lemma A.1) gives the properties of PρP_\rho that are used throughout; Theorem 3.1 transfers stationarity from PρP_\rho to FF under Assumptions 2 and 3; and Propositions 2.2, 2.5 and 2.6 give standard cases in which our assumptions hold and can be verified from properties of FF.

Lemma 2.1. We agree that the full lemma in the main text may interrupt the flow of the argument, and we moved it to the appendix (Lemma A.1). The main text keeps only the two facts that are helpful for understanding our method:

  • The gap G\mathcal G is equivalent to ∥∇yF∥2\Vert\nabla_yF\Vert^2 up to constants. Hence G≥0\mathcal G\ge0 vanishes exactly at max-player stationary points, and ρG\rho \mathcal G is a valid penalty for max-player stationarity.
  • PρP_\rho has a Lipschitz gradient. Hence minimizing PρP_\rho is a smooth nonconvex minimization problem, and gradient descent applies.

Proposition 2.4 (now Proposition 2.6). Proposition 2.6 gives a verifiable sufficient condition for Assumption 3 when the max-player is constrained. We pass to the upper Moreau envelope of the objective, and our assumptions can then be verified directly from properties of the constrained problem. It is stated for a standard problem formulation that encompasses budget-constrained adversarial training as an important practical application. Its conditions are the standard ones for a well-behaved KKT system: the Slater condition, strict complementarity (an active budget has a positive multiplier), and a nonsingular reduced Lagrangian Hessian, which holds automatically when the multiplier is large enough.

Q1. Motivation for seeking game-stationary points

We added a detailed explanation of our motivation to Section 1. Global nonconvex minimization, the special case of the nonconvex–nonconcave setting without a max-player, is already NP-hard (Murty & Kabadi, 1987), so one cannot expect to find global minimax solutions or Nash equilibria efficiently in the general setting. This motivates considering local computational objectives. For smooth unconstrained problems, game stationarity (∇xF=0\nabla_xF=0 and ∇yF=0\nabla_yF=0) is the first-order necessary condition for both local Nash equilibria and local minimax points (Jin et al., 2020). This condition means that neither player has a unilateral direction of first-order improvement. It is also the target of most existing work on nonconvex–nonconcave problems (Diakonikolas et al., 2021; Pethick et al., 2022; Tsaknakis & Hong, 2021; Zheng et al., 2023; Li et al., 2025; Lu & Wang, 2026).

Game-theoretic experiment. As suggested, we added an empirical game-theoretic experiment in Appendix D: a two-party weighted-majority resource-allocation game (Morales & Thraves, 2021), in which each party divides a budget over five regions and the objective is the probability of winning a weighted majority. We compare with TSGDA, GNI and RNI. On 225 test instances with a budget of 1,500 gradient evaluations, our method reaches the target on 128 instances, compared with 108 for RNI, 51 for GNI and 13 for TSGDA. The target is a game-stationary point at which the maximizing allocation is certified to be a near-best response.

Experiments. The experiment in Section 4 now considers a smooth nonlinear nonconvex–nonconcave problem and includes further baselines. Our method converges to the game-stationary point. Gradient descent and descent–ascent diverge. The two Nikaido–Isoda-type methods stop at stationary points of their merit functions that are not game-stationary. On the application side, Remark 2.3 shows that our assumptions cover objectives arising in robust regression, adversarial training with penalized perturbations, and Wasserstein GANs with a penalized critic, with a concrete instance in Example A.7 that satisfies all of Assumptions 1–3 (verified in Proposition B.2, Appendix B).

Q3. Penalty methods

We added a detailed explanation of penalty methods in Section 1. Penalty methods are widely used by incorporating constraint violations into the objective through penalty terms (Nocedal & Wright, 2006). For example, in bilevel optimization, lower-level optimality is commonly formulated as a constraint and subsequently penalized, enabling fully first-order methods (Liu et al., 2022; Shen & Chen, 2023; Kwon et al., 2023; 2024; Lu & Mei, 2024); regularized gap functions have also served as penalty terms in constrained minimization (Li & Nahak, 2009).

Our method differs in the problem it solves and in the structure it uses. We solve the minimax problem and penalize the max-player. The min-player and the max-player share the same function FF, with opposite goals. We use this structure to transfer stationarity: under Assumption 3, every stationary point of PρP_\rho in the sublevel set is a game-stationary point of FF, for a finite ρ\rho that does not depend on ε\varepsilon.

Comments on the paper

5 comments

We sincerely thank all reviewers for their constructive comments. We would like to clarify two important points that arose across the reviews.

1. Improvements to the presentation

We have substantially revised the manuscript to improve its clarity and organization. In particular, we have clarified the motivation and geometric interpretation of our assumptions, simplified the presentation of technical results, strengthened the comparison with existing methods, and provided additional discussions and experiments to demonstrate the practical relevance of our framework.

  • Motivation, related work and geometric interpretation. Section 1 now further explains why game-stationary points are the computational target and places our method among penalty methods. Table 1 compares the structural assumptions, stationarity measures and gradient complexities of representative methods. Section 1.2 gives a geometric interpretation of our method and assumptions.
  • Assumptions. We restated Assumptions 2 and 3 in a simpler form in Section 2, and Remarks 2.1 and 2.4 relate them to standard conditions. Each assumption is followed by verifiable sufficient conditions. For Assumption 2, we added a growth condition on FF that holds when each player has a coercive regularizer in Proposition 2.2 (proof in Appendix A.2), and Remark 2.3 (details in Appendix A.4) shows that it covers general applications such as robust regression, adversarial training with penalized perturbations, and Wasserstein GANs with a penalized critic. We also clarified the sufficient conditions for Assumption 3 in Propositions 2.5 and 2.6 (proof in Appendix A.5). In addition, Example A.7, an explicit robust-regression example (verified in Appendix B.2), satisfies all of Assumptions 1–3.
  • Technical results. We moved the original Lemma 2.1, which collects the properties of the penalty function, to the appendix (Lemma A.1). The complexity results are Theorems 3.4 and 3.5, with the total gradient complexity in Corollary 3.6.
  • Experiments. The experiment in Section 4 now includes the methods of Raghunathan et al. (2019) and Tsaknakis & Hong (2021) as baselines.
  • Extension. Assumption 3 is relaxed to a weaker cross-gradient condition (Assumption 4) in Appendix C, under which stationarity still transfers (Theorem C.2) with gradient complexity O~(ε−4)\tilde O(\varepsilon^{-4}) (Corollary C.4).

2. Our contributions

Our contribution is not only to introduce alternative structural assumptions and achieve a nearly optimal O~(ε−2)\tilde O(\varepsilon^{-2}) complexity, but also, more importantly, to demonstrate how these structural properties can be exploited to design a provably tractable first-order algorithm for finding game-stationary points in challenging nonconvex–nonconcave minimax problems.

Unlike one-sided PL and value-gap KL conditions, our assumptions allow the max-player objective to have local minima and saddle points, better accommodating the nonconvex–nonconcave nature of the problem. Our goal is not to replace existing PL, KL, or Minty-type frameworks, but to provide a complementary perspective on exploitable structures beyond these conditions.

We believe that establishing first-order tractability under these alternative structural conditions offers a new theoretical perspective and a promising starting point for future research in nonconvex–nonconcave minimax optimization.

We thank the reviewers again for their valuable feedback.

Dear Reviewers,

Thank you again for your thoughtful reviews and constructive feedback. We have updated our manuscript to address your comments, with additional results and clarifications discussed in our rebuttal.

We kindly invite you to review the updated PDF alongside our responses to see whether they resolve your concerns. If you have any remaining questions or concerns, we'd appreciate hearing from you soon so we have time to respond before the discussion closes on November 18. If the revisions address the points you raised, we would be really grateful if you would consider updating your overall assessment.

Thank you once again for your time and feedback!

Best regards, The Authors of Submission 12675

Dear authors

Would it be possible to highlight the changes in a different color in the revised manuscript to make them easier to identify?

Best, Reviewer WFko

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.