Abstrac

Recent applications that arise in machine learning have surged significant interest insolvingmin-maxsaddlepointgames. Thisproblemhasbeenextensivelystudied in the convex-concave regime for which a global equilibrium solution can be computed efficiently. In this paper, we study the problem in the non-convex regime and show that an ε–first order stationary point of the game can be computed when one of the player’s objective can be optimized to global optimality efficiently. In particular, we first consider the case where the objective of one of the players satisfies the Polyak-Łojasiewicz (PL) condition. For such a game, we show that a simplemulti-stepgradientdescent-ascent algorithmfindsan ε–first order stationary point of the problem in iterations. Then we show that our framework can also be applied to the case where the objective of the “max-player" is concave. In this case, we propose a multi-step gradient descent-ascent algorithm that finds an ε–first order stationary point of the game in iterations, which is the best known rate in the literature. We applied our algorithm to a fair classification problem of Fashion-MNIST dataset and observed that the proposed algorithm results in smoother training and better generalization.