Obtaining 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 ε-stationary point within Õ(ε−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.
Related
- A sequential smoothing majorant stochastic approximation method for nonconvex nonconcave minimax problems
- Riemannian ascent--descent for nonconvex nonconcave minimax landscapes: convergence to basin saddle points and applications to distributionally robust optimization
- Preconditioned Three-Term Conjugate Gradient Framework for Nonconvex Finite Minimax Problems
- ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{dong2026obtaining,
title = {{Obtaining Game-Stationary Points for Smooth Nonconvex-Nonconcave Minimax Problems via First-Order Methods}},
author = {Mengxuan Dong and Yao Yao and Jiawei Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32970},
eprint = {2609.32970},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32970},
}
RIS
TY - UNPB
TI - Obtaining Game-Stationary Points for Smooth Nonconvex-Nonconcave Minimax Problems via First-Order Methods
AU - Mengxuan Dong
AU - Yao Yao
AU - Jiawei Zhang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.32970
UR - https://arxiv.org/abs/2609.32970
AB - 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 ε-stationary point within Õ(ε^−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.
ER -