Differentiable Game Mechanics

Abstract

Deep learning is built on the foundational guarantee that gradient descent on an objective function converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, that exhibit 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 tools to understand and control the dynamics in n-player differentiable games. The key result is to decompose the game Jacobian into two components. The first, symmetric component, is related to potential games, which reduce to gradient descent on an implicit function. The second, antisymmetric component, 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 differentiable games. 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.

JMLR 2019, journal version of arXiv:1802.05642

Cited by in corpus (17)

• LOGAN: Latent Optimisation for Generative Adversarial Networks
• Competitive Gradient Descent
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• On the Suboptimality of Negative Momentum for Minimax Optimization
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Smooth markets: A basic mechanism for organizing gradient-based learners
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
• Learning in Matrix Games can be Arbitrarily Complex
• Competitive Mirror Descent
• Adversarial Deep Learning for Online Resource Allocation
• Data-efficient Alignment of Multimodal Sequences by Aligning Gradient Updates and Internal Feature Distributions
• ScrofaZero: Mastering Trick-taking Poker Game Gongzhu by Deep Reinforcement Learning
• Complex Momentum for Optimization in Games
• Inverse-Weighted Survival Games
• Polymatrix Competitive Gradient Descent