Competitive Gradient Descent

Abstract

We introduce a new algorithm for the numerical computation of Nash equilibria of competitive two-player games. Our method is a natural generalization of gradient descent to the two-player setting where the update is given by the Nash equilibrium of a regularized bilinear local approximation of the underlying game. It avoids oscillatory and divergent behaviors seen in alternating gradient descent. Using numerical experiments and rigorous analysis, we provide a detailed comparison to methods based on \emph{optimism} and \emph{consensus} and show that our method avoids making any unnecessary changes to the gradient dynamics while achieving exponential (local) convergence for (locally) convex-concave zero sum games. Convergence and stability properties of our method are robust to strong interactions between the players, without adapting the stepsize, which is not the case with previous methods. In our numerical experiments on non-convex-concave problems, existing methods are prone to divergence and instability due to their sensitivity to interactions among the players, whereas we never observe divergence of our algorithm. The ability to choose larger stepsizes furthermore allows our algorithm to achieve faster convergence, as measured by the number of model evaluations.

arXiv commentAppeared in NeurIPS 2019. This version corrects an error in theorem 2.2. Source code used for the numerical experiments can be found under http://github.com/f-t-s/CGD. A high-level overview of this work can be found under http://f-t-s.github.io/projects/cgd/

References in corpus (13)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• FeUdal Networks for Hierarchical Reinforcement Learning
• The Numerics of GANs
• The Mechanics of n-Player Differentiable Games
• Online Learning with Predictable Sequences
• Gradient Descent Converges to Minimizers
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Forward-Mode Automatic Differentiation in Julia
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• On the Limitations of First-Order Approximation in GAN Dynamics
• Differentiable Game Mechanics
• Global Convergence to the Equilibrium of GANs using Variational Inequalities
• An Online Learning Approach to Generative Adversarial Networks

Cited by in corpus (13)

• Understanding and mitigating gradient pathologies in physics-informed neural networks
• Stabilizing Generative Adversarial Networks: A Survey
• A Systematic Survey of Regularization and Normalization in GANs
• A Game Theoretic Framework for Model Based Reinforcement Learning
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• On the distance between two neural networks and the stability of learning
• Implicit competitive regularization in GANs
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Scalable Balanced Training of Conditional Generative Adversarial Neural Networks on Image Data
• Towards Deep Learning Models Resistant to Large Perturbations
• DYSAN: Dynamically sanitizing motion sensor data against sensitive inferences through adversarial networks
• Reproducibility Challenge NeurIPS 2019 Report on "Competitive Gradient Descent"