Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition

Abstract

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 $\epsilon$--first order stationary point of the problem in $\tilde{\mathcal{O}}({\epsilon }^{-2})$ iterations.

Cited by in corpus (12)

• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Stochastic AUC Maximization with Deep Neural Networks
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Generalization Bounds for Stochastic Saddle Point Problems
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Randomized Stochastic Gradient Descent Ascent