Skip to content
Preprint

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

Sep 2026 · 0 citations · 34 references
Mathematics

TL;DR

This work develops a first-order method that finds an $\epsilon$-stationary point within $\widetilde{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.

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 $\widetilde{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.

View source

Similar papers

Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex-Concave Minimax Optimization

A new single-loop algorithmic framework for smooth nonconvex--concave minimax optimization and a lower bound of $\Omega(L^2D_Y\Delta_\phi\varepsilon^{-3})$ for optimization stationarity over projected zero-respecting first-order methods is established.

Ming-Hao Zhang, Zi Xu · 4 citations · ⚡1

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $\mu$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-en...

Qi-Hao Zhou · 2 citations
Preprint Sep 2026

Efficient Parameter-Free First-Order Methods for Nonsmooth Composite Minimax Optimization

In this paper we propose first-order methods for a class of nonsmooth composite strongly convex--strongly concave and nonconvex--concave minimax optimization. We first develop an inexact proximal method and an accumulative regularizated method for strongly convex--strongly concave problems. The latter achieves the opti...

Shao-Zhe Ke, Sanyou Mei, Ji-Heng Zhang · 0 citations
Preprint Sep 2026

Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity

We study deterministic first-order bilevel optimization under weak lower-level convexity, allowing nonconvex lower-level objectives and without assuming strong convexity, the Polyak-{\L}ojasiewicz condition, or an error-bound property. We consider a $\delta$-relaxed Moreau-gap constraint, with $\delta>0$, for the lower...

Jan Harold Alcantara, Masahiro Inoue, Akiko Takeda · 0 citations
Preprint Oct 2026

Parameter-Free Adaptive Extragradient Methods for Generalized-Smooth Variational Inequalities

Variational inequalities (VIs) provide a unified framework for optimization, saddle-point, equilibrium, and learning problems, where operators need not be globally Lipschitz. The $\alpha$-symmetric generalized-smoothness condition allows local operator variation to grow with the operator norm, but existing extragradien...

Zhao-Yang Chu, Hong-Wei Liu, Ya-Kui Huang · 1 citation
#machine learning Preprint Oct 2026

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a $(\delta,\varepsilon)$-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities...

G. Buzaglo, Guy Kornowski · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.