# The Mechanics of n-Player Differentiable Games

@article{Balduzzi2018TheMO, title={The Mechanics of n-Player Differentiable Games}, author={David Balduzzi and S{\'e}bastien Racani{\`e}re and James Martens and Jakob N. Foerster and Karl Tuyls and Thore Graepel}, journal={ArXiv}, year={2018}, volume={abs/1802.05642} }

The cornerstone underpinning deep learning is the guarantee that gradient descent on an objective converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, where there are multiple interacting losses. The behavior of gradient-based methods in games is not well understood -- and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new techniques to understand and control… Expand

#### Supplemental Code

Github Repo

Via Papers with Code

A colab that implements the Symplectic Gradient Adjustment optimizer from "The mechanics of n-player differentiable games"

#### Figures and Topics from this paper

#### Paper Mentions

#### 171 Citations

Differentiable Game Mechanics

- Computer Science, Mathematics
- J. Mach. Learn. Res.
- 2019

New tools to understand and control the dynamics in n-player differentiable games are developed and basic experiments show SGA is competitive with recently proposed algorithms for finding stable fixed points in GANs -- while at the same time being applicable to, and having guarantees in, much more general cases. Expand

Learning in Matrix Games can be Arbitrarily Complex

- Computer Science, Mathematics
- COLT
- 2021

It is proved that replicator dynamics, the continuous-time analogue of Multiplicative Weights Update, even when applied in a very restricted class of games—known as finite matrix games—is rich enough to be able to approximate arbitrary dynamical systems. Expand

Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent

- Computer Science, Mathematics
- ArXiv
- 2021

It is proved that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to the von-Neumann solution of a slightly perturbed zero-sum game. Expand

Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study

- Mathematics, Computer Science
- ICML
- 2020

This work provides insights into the optimization landscape of zero-sum games by establishing connections between Nash and Stackelberg equilibria along with the limit points of simultaneous gradient descent and derive novel gradient-based learning dynamics emulating the natural structure of a StACkelberg game using the implicit function theorem. Expand

Stochastic Hamiltonian Gradient Methods for Smooth Games

- Computer Science, Mathematics
- ICML
- 2020

This work proposes a novel unbiased estimator for the stochastic Hamiltonian gradient descent (SHGD) and shows that SHGD converges linearly to the neighbourhood of a stationary point, and provides the first global non-asymptotic last-iterate convergence guarantees for certain classes of Stochastic smooth games. Expand

Average-case Acceleration for Bilinear Games and Normal Matrices

- Computer Science, Mathematics
- ICLR
- 2021

This work shows that for zero-sum bilinear games the average-case optimal method is the optimal method for the minimization of the Hamiltonian, and provides an explicit expression for the optimal methods corresponding to normal matrices, potentially non-symmetric. Expand

Negative Momentum for Improved Game Dynamics

- Computer Science, Mathematics
- AISTATS
- 2019

It is proved that alternating updates are more stable than simultaneous updates and both theoretically and empirically that alternating gradient updates with a negative momentum term achieves convergence in a difficult toy adversarial problem, but also on the notoriously difficult to train saturating GANs. Expand

Mirror descent in saddle-point problems: Going the extra (gradient) mile

- Computer Science, Mathematics
- ICLR
- 2019

This work analyzes the behavior of mirror descent in a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality-a property which it is called coherence, and shows that optimistic mirror descent (OMD) converges in all coherent problems. Expand

Minimax Optimization with Smooth Algorithmic Adversaries

- Computer Science
- ArXiv
- 2021

A new algorithm is proposed for the min-player to play against smooth algorithms deployed by the adversary instead of against full maximization, guaranteed to make monotonic progress, and to find an appropriate “stationary point” in a polynomial number of iterations. Expand

A mean-field analysis of two-player zero-sum games

- Computer Science, Mathematics
- NeurIPS
- 2020

A law of large numbers that relates particle dynamics to mean-field dynamics is proved, which establishes global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. Expand

#### References

SHOWING 1-10 OF 38 REFERENCES

Gradient descent GAN optimization is locally stable

- Computer Science, Mathematics
- NIPS
- 2017

This paper analyzes the "gradient descent" form of GAN optimization i.e., the natural setting where the authors simultaneously take small gradient steps in both generator and discriminator parameters, and proposes an additional regularization term for gradient descent GAN updates that is able to guarantee local stability for both the WGAN and the traditional GAN. Expand

Training GANs with Optimism

- Computer Science, Mathematics
- ICLR
- 2018

This work addresses the issue of limit cycling behavior in training Generative Adversarial Networks and proposes the use of Optimistic Mirror Decent (OMD) for training Wasserstein GANs and introduces a new algorithm, Optimistic Adam, which is an optimistic variant of Adam. Expand

GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium

- Mathematics, Computer Science
- NIPS
- 2017

This work proposes a two time-scale update rule (TTUR) for training GANs with stochastic gradient descent on arbitrary GAN loss functions and introduces the "Frechet Inception Distance" (FID) which captures the similarity of generated images to real ones better than the Inception Score. Expand

Cycles in adversarial regularized learning

- Computer Science, Mathematics
- SODA
- 2018

It is shown that the system's behavior is Poincare recurrent, implying that almost every trajectory revisits any (arbitrarily small) neighborhood of its starting point infinitely often. Expand

The Numerics of GANs

- Computer Science
- NIPS
- 2017

This paper analyzes the numerics of common algorithms for training Generative Adversarial Networks (GANs) and designs a new algorithm that overcomes some of these limitations and has better convergence properties. Expand

Nash Q-Learning for General-Sum Stochastic Games

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2003

This work extends Q-learning to a noncooperative multiagent context, using the framework of general-sum stochastic games, and implements an online version of Nash Q- learning that balances exploration with exploitation, yielding improved performance. Expand

Connecting Generative Adversarial Networks and Actor-Critic Methods

- Computer Science, Mathematics
- ArXiv
- 2016

It is shown that GANs can be viewed as actor-critic methods in an environment where the actor cannot affect the reward, and it is hoped that by highlighting this formal connection it will encourage both GAN and RL communities to develop general, scalable, and stable algorithms for multilevel optimization with deep networks. Expand

Generative Adversarial Nets

- Computer Science
- NIPS
- 2014

We propose a new framework for estimating generative models via an adversarial process, in which we simultaneously train two models: a generative model G that captures the data distribution, and a… Expand

Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

- Computer Science, Mathematics
- NIPS
- 2014

This paper proposes a new approach to second-order optimization, the saddle-free Newton method, that can rapidly escape high dimensional saddle points, unlike gradient descent and quasi-Newton methods, and applies this algorithm to deep or recurrent neural network training, and provides numerical evidence for its superior optimization performance. Expand

On the convergence properties of GAN training

- Computer Science, Mathematics
- ArXiv
- 2018

It is shown that in the more realistic case of distributions that are not absolutely continuous, unregularized GAN training is generally not convergent, and a simplified gradient penalty is proposed with the same effects on local convergence as more complicated penalties. Expand