- 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 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
- 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.
- Theorem 3.1 transfers approximate penalty stationarity to game stationarity, which is a meaningful contribution.
Critical weaknesses
- 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.
- 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
- 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.
- 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
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 and . Under strong concavity of the max-player objective, it holds if has compact sublevel sets (Remark 2.1).
Assumption 3.
- Strong concavity. If is -strongly concave, the inequality holds globally, for arbitrary pairs, with .
- PL. The one-sided -PL condition implies Assumption 3 with when is and its -Hessian is Lipschitz continuous uniformly in (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 with , 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 (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 , 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).
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
not an additional restriction on it.
For , the penalty function simplifies to
The key identity follows from
Thus, the nested envelope reduces to a single proximal maximization problem with parameter . The resulting expression of 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 only requires the maximizers of two single-level constrained problems,
with and , respectively. No nested optimization is needed.
Both problems are strongly concave when , 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 , the gradient that is used satisfies
With step size , the descent lemma gives
The function value decreases as long as exceeds the gradient error, so the iterates remain in up to the first index at which
Summing the descent inequality shows that such an index exists among the first iterations.
Taking and makes this bound at most , and Theorem 3.1 then gives an -game-stationary point.
Each inner solve costs gradient evaluations, so the total is
(Corollary 3.6).
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, the sublevel sets of Pρc are compact. The penalty term ρG is of the order of ρ∥∇yF(x,y)∥2. Hence, when ∥∇yF(x,y)∥2 grows in y fast enough to dominate the decrease of F, the assumption holds once ρc is sufficiently large.
Sufficient conditions checkable from F:
Assumption 3: Local inverse-Lipschitz regularity. Within the compact sublevel set containing our initial point, Assumption 3 requires that, when y and 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).