Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
arXiv:2007.05477
Abstract
Motivated by Generative Adversarial Networks, we study the computation of Nash equilibrium in concave network zero-sum games (NZSGs), a multiplayer generalization of two-player zero-sum games first proposed with linear payoffs. Extending previous results, we show that various game theoretic properties of convex-concave two-player zero-sum games are preserved in this generalization. We then generalize last iterate convergence results obtained previously in two-player zero-sum games. We analyze convergence rates when players update their strategies using Gradient Ascent, and its variant, Optimistic Gradient Ascent, showing last iterate convergence in three settings -- when the payoffs of players are linear, strongly concave and Lipschitz, and strongly concave and smooth. We provide experimental results that support these theoretical findings.
arXiv comment16 pages, 3 figures
References in corpus (5)
- NIPS 2016 Tutorial: Generative Adversarial Networks
- Triple Generative Adversarial Nets
- A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- Smooth markets: A basic mechanism for organizing gradient-based learners