The Mechanics of n-Player Differentiable Games

By David Balduzzi, Sébastien Racanière, James Martens, Jakob N. Foerster, Karl Tuyls, Thore Graepel. 2018

315 citations recorded by the source corpus.

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 the dynamics in general games. The key result is to decompose the second-order dynamics into two components. The first is related to potential games, which reduce to gradient descent on an implicit function; the second relates to Hamiltonian games, a new class of games that obey a conservation law, akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in general games. Basic experiments show SGA is competitive with recently proposed algorithms for finding local Nash equilibria in GANs -- whilst at the same time being applicable to -- and having guarantees in -- much more general games.

Subfields: Aerospace Engineering, Artificial Intelligence, Management Science and Operations Research, Optimization & Training, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

In Game & Decision Theory

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “From its definition, it is clear that the update rule is essentially a weighted combination of GDA and the Hamiltonian gradient descent (HGD) of Balduzzi et al. [2018]. In practice, implementing CO in a mini-batch setting (stochastic) leads to biased estimates of the gradient of the Hamiltonian func”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “, 2017) and Hamiltonian gradient descent (Balduzzi et al., 2018; Abernethy et al., 2019).”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “Gidel et al. (2019b) and Balduzzi et al. (2018) mentioned two particular classes of games, which can be seen as the two opposite ends of a spectrum.”
A Closer Look at the Optimization Landscapes of Generative Adversarial Networks (2019, background): “This cyclic behavior has been explained in (Balduzzi et al., 2018) by a non-zero Hamiltonian component in the Helmholtz decomposition of the Jacobian of the game vector field.”
Negative Momentum for Improved Game Dynamics (2018, background): “These notions of adversarial and cooperative games can be related to the notions of potential games (Monderer and Shapley, 1996) and Hamiltonian games recently introduced by Balduzzi et al. (2018): a game is a potential game (resp.”
Understanding and mitigating gradient pathologies in physics-informed neural networks (2020, methodology): “From an optimization standpoint, this setting has motivated the development of proximal gradient algorithms [36] that have been successfully applied to ill-posed inverse problems involving stiff regularization terms [37], as well as effective algorithms for finding Nash equilibria in multi-player ga”
The Unusual Effectiveness of Averaging in GAN Training (2018, methodology): “These connections have recently been exploited by Balduzzi et al. (2018) to design training algorithms for GANs (see also Bailey & Piliouras (2019)).”
LOGAN: Latent Optimisation for Generative Adversarial Networks (2019, methodology): “This correspondence based on ﬁrst order Taylor expansion is unsurprising, as SGA is based on linearising the adversarial dynamics (Balduzzi et al., 2018).”
Open-ended Learning in Symmetric Zero-sum Games (2019, methodology): “A low-dim representation of the EGS can be constructed via the Schur decomposition, which is the analog of PCA for antisymmetric matrices (Balduzzi et al., 2018b).”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, background): “Despite its popularity, this algorithm fails to converge even for simple bilinear zero-sum games [41, 39, 14, 2, 32].”
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “This problem can be resolved by introducing second-order optimization (Balduzzi et al., 2018; Foerster et al., 2017; Mescheder et al., 2017; Letcher et al., 2019), negative momentum (Gidel et al.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “…of goodness or the development of new procedures for reducing oscillations [Daskalakis and Panageas, 2018b, Adolphs et al., 2018, Mazumdar et al., 2019] and speeding up the convergence of gradient dynamics [Heusel et al., 2017, Balduzzi et al., 2018, Mertikopoulos et al., 2019, Lin et al., 2018].”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “• We show theoretically and empirically that FR addresses the notorious rotational behaviour of gradient dynamics around fixed points (Balduzzi et al., 2018) and thus allows a much larger learning rate compared to GDA.”
Stable Opponent Shaping in Differentiable Games (2018, methodology): “Regarding unstable ﬁxed points and strict saddles, note that H (¯ θ ) 0 implies H ( θ ) 0 in a neighbourhood, hence being equivalent to the deﬁnition in Balduzzi et al. (2018).”
Differentiable Game Mechanics (2019, background): “The deﬁnition is adapted from Letcher et al. (2019), where conditions on the Jacobian hold at the ﬁxed point; in contrast, Balduzzi et al. (2018a) imposed conditions on the Jacobian in a neighborhood of the ﬁxed point.”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, background): “A relevant special case is a n-players convex game, where ω∗ corresponds to a Nash equilibrium (Balduzzi et al., 2018).”
Optimizing Millions of Hyperparameters by Implicit Differentiation (2019, background): “However, using only the direct gradient does not work in general games [40].”
Re-evaluating evaluation (2018, background): “A major theme underlying the paper is that the fundamental algebraic structure of tournaments and evaluation is antisymmetric [23].”