On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games

Abstract

We propose local symplectic surgery, a two-timescale procedure for finding local Nash equilibria in two-player zero-sum games. We first show that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due to the existence of non-Nash stationary points. By taking advantage of the differential structure of the game, we construct an algorithm for which the local Nash equilibria are the only attracting fixed points. We also show that the algorithm exhibits no oscillatory behaviors in neighborhoods of equilibria and show that it has the same per-iteration complexity as other recently proposed algorithms. We conclude by validating the algorithm on two numerical examples: a toy example with multiple Nash equilibria and a non-Nash equilibrium, and the training of a small generative adversarial network (GAN).

References in corpus (3)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• The Numerics of GANs
• A Variational Inequality Perspective on Generative Adversarial Networks

Cited by in corpus (38)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Game-Theoretic Multiagent Reinforcement Learning
• A Dual-Dimer Method for Training Physics-Constrained Neural Networks with Minimax Architecture
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Convergence of Learning Dynamics in Stackelberg Games
• Last-iterate convergence rates for min-max optimization
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
• GANs May Have No Nash Equilibria
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Accelerating Smooth Games by Manipulating Spectral Shapes
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Implicit competitive regularization in GANs
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• A mean-field analysis of two-player zero-sum games
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Generative Minimization Networks: Training GANs Without Competition
• Inference-Based Strategy Alignment for General-Sum Differential Games
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings
• On Characterizing GAN Convergence Through Proximal Duality Gap
• Adversarial Environment Generation for Learning to Navigate the Web
• A Game-Theoretic Approach to Multi-Agent Trust Region Optimization
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks
• Generative Adversarial Networks are Special Cases of Artificial Curiosity (1990) and also Closely Related to Predictability Minimization (1991)
• Extragradient with player sampling for faster Nash equilibrium finding
• Minimax Optimization with Smooth Algorithmic Adversaries
• A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
• The Confluence of Networks, Games and Learning
• Polymatrix Competitive Gradient Descent
• Solving Zero-Sum Games through Alternating Projections
• Distributed stochastic subgradient-free algorithm for Nash equilibrium seeking in two-network zero-sum games