A mean-field analysis of two-player zero-sum games
arXiv:2002.06277
Abstract
Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
References in corpus (13)
- GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- Generalization and Equilibrium in Generative Adversarial Nets (GANs)
- A Variational Inequality Perspective on Generative Adversarial Networks
- Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
- The Mechanics of n-Player Differentiable Games
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
- A new optimal transport distance on the space of finite Radon measures
- Convergence of Learning Dynamics in Stackelberg Games
- A JKO splitting scheme for Kantorovich-Fisher-Rao gradient flows
- Global convergence of neuron birth-death dynamics
- SGD Learns One-Layer Networks in WGANs