Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
This addresses a theoretical gap in min-max optimization for non-convex non-concave settings, though it is incremental as it builds on prior work by adding a specific condition.
The paper tackles the problem of solving non-convex non-concave min-max games by assuming the Polyak-Łojasiewicz condition, showing that a multi-step gradient descent-ascent algorithm finds an ε-first order stationary point in Õ(ε⁻²) iterations.
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-Łojasiewicz (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 $\widetilde{\mathcal{O}}(\varepsilon^{-2})$ iterations.