Extragradient with player sampling for faster Nash equilibrium finding
arXiv:1905.12363
Abstract
Data-driven modeling increasingly requires to find a Nash equilibrium in multi-player games, e.g. when training GANs. In this paper, we analyse a new extra-gradient method for Nash equilibrium finding, that performs gradient extrapolations and updates on a random subset of players at each iteration. This approach provably exhibits a better rate of convergence than full extra-gradient for non-smooth convex games with noisy gradient oracle. We propose an additional variance reduction mechanism to obtain speed-ups in smooth convex games. Our approach makes extrapolation amenable to massive multiplayer settings, and brings empirical speed-ups, in particular when using a heuristic cyclic sampling scheme. Most importantly, it allows to train faster and better GANs and mixtures of GANs.
References in corpus (10)
- GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- The Numerics of GANs
- A Variational Inequality Perspective on Generative Adversarial Networks
- 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
- Reducing Noise in GAN Training with Variance Reduced Extragradient
- A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
- Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games