Extragradient with player sampling for faster Nash equilibrium finding

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....

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-07
Main Authors: Carles Domingo Enrich, Jelassi, Samy, Domingo-Enrich, Carles, Scieur, Damien, Mensch, Arthur, Bruna, Joan
Format: Article
Language:English
Subjects:
Convergence
Economic models
Empirical analysis
Extrapolation
Game theory
Iterative methods
Multiagent systems
Sampling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422