# Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Lojasiewicz Condition

arXiv: https://arxiv.org/abs/1812.02878 · HTML: https://mlsanity.com/paper/1812.02878/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2018.

## Built on by (most cited first, 7 of 7)

- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problems](https://mlsanity.com/paper/2212.02724/) (2022)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Randomized Stochastic Gradient Descent Ascent](https://mlsanity.com/paper/2111.13162/) (2021)
- [CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems](https://mlsanity.com/paper/2105.14216/) (2021)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Iterative Minimax Games with Coupled Linear Constraints](https://mlsanity.com/paper/2212.04672/) (2022)

## Abstract (arXiv)

In this short note, we consider the problem of solving a min-max zero-sum game. This problem has been extensively studied in the convex-concave regime where the global solution can be computed efficiently. Recently, there have also been developments for finding the first order stationary points of the game when one of the player's objective is concave or (weakly) concave. This work focuses on the non-convex non-concave regime where the objective of one of the players satisfies Polyak-Lojasiewicz (PL) Condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an varepsilon--first order stationary point of the problem in widetildeO(varepsilon-2) iterations.