A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets
arXiv:2002.05820
Abstract
Adversarial training, a special case of multi-objective optimization, is an increasingly prevalent machine learning technique: some of its most notable applications include GAN-based generative modeling and self-play techniques in reinforcement learning which have been applied to complex games such as Go or Poker. In practice, a \emph{single} pair of networks is typically trained in order to find an approximate equilibrium of a highly nonconcave-nonconvex adversarial problem. However, while a classic result in game theory states such an equilibrium exists in concave-convex games, there is no analogous guarantee if the payoff is nonconcave-nonconvex. Our main contribution is to provide an approximate minimax theorem for a large class of games where the players pick neural networks including WGAN, StarCraft II, and Blotto Game. Our findings rely on the fact that despite being nonconcave-nonconvex with respect to the neural networks parameters, these games are concave-convex with respect to the actual models (e.g., functions or distributions) represented by these neural networks.
arXiv commentAppears in: Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021). 19 pages
References in corpus (10)
- Large Scale GAN Training for High Fidelity Natural Image Synthesis
- Spectral Normalization for Generative Adversarial Networks
- Safe and Nested Subgame Solving for Imperfect-Information Games
- What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
- LOGAN: Latent Optimisation for Generative Adversarial Networks
- Open-ended Learning in Symmetric Zero-sum Games
- Convergence of Learning Dynamics in Stackelberg Games
- A Convex Duality Framework for GANs
- A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
- Finding Mixed Strategy Nash Equilibrium for Continuous Games through Deep Learning