The Mechanics of n-Player Differentiable Games

Abstract

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 stable fixed points in GANs -- whilst at the same time being applicable to -- and having guarantees in -- much more general games.

ICML 2018, final version

References in corpus (3)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• First-order Methods Almost Always Avoid Saddle Points

Cited by in corpus (65)

• A Survey and Critique of Multiagent Deep Reinforcement Learning
• Understanding and mitigating gradient pathologies in physics-informed neural networks
• 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
• The Unusual Effectiveness of Averaging in GAN Training
• Stabilizing Generative Adversarial Networks: A Survey
• LOGAN: Latent Optimisation for Generative Adversarial Networks
• Competitive Gradient Descent
• The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies
• Convergence of Learning Dynamics in Stackelberg Games
• Re-evaluating Evaluation
• Lower Dimensional Kernels for Video Discriminators
• Last-iterate convergence rates for min-max optimization
• A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
• Global Convergence to the Equilibrium of GANs using Variational Inequalities
• Accelerating Smooth Games by Manipulating Spectral Shapes
• Towards a Better Understanding and Regularization of GAN Training Dynamics
• Learning to Incentivize Other Learning Agents
• Negative Momentum for Improved Game Dynamics
• Implicit competitive regularization in GANs
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Training Generative Adversarial Networks by Solving Ordinary Differential Equations
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
• Newton-type Methods for Minimax Optimization
• Stable Opponent Shaping in Differentiable Games
• Learning in Nonzero-Sum Stochastic Games with Potentials
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• A mean-field analysis of two-player zero-sum games
• Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs
• Non-saturating GAN training as divergence minimization
• Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent
• Solving Structured Hierarchical Games Using Differential Backward Induction
• Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes
• Latent-Optimized Adversarial Neural Transfer for Sarcasm Detection
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Universality Theorems for Generative Models
• Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings
• Implicit Gradient Regularization
• Taming GANs with Lookahead-Minmax
• Stochastic Potential Games
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
• Modeling Friends and Foes
• Extragradient with player sampling for faster Nash equilibrium finding
• The Evolutionary Dynamics of Independent Learning Agents in Population Games
• Training Generative Adversarial Networks with Adaptive Composite Gradient
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks
• Momentum Accelerates Evolutionary Dynamics
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• A Differential Game Theoretic Neural Optimizer for Training Residual Networks
• Neural Lyapunov Redesign
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
• Finding Mixed Strategy Nash Equilibrium for Continuous Games through Deep Learning
• Competitive Mirror Descent
• Geometry-Aware Universal Mirror-Prox
• SyMetric: Measuring the Quality of Learnt Hamiltonian Dynamics Inferred from Vision
• Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
• Hamiltonian descent for composite objectives
• Functional Space Analysis of Local GAN Convergence
• Follow the Neurally-Perturbed Leader for Adversarial Training
• Learning to Classify and Imitate Trading Agents in Continuous Double Auction Markets
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Polymatrix Competitive Gradient Descent
• The Geometric Occam's Razor Implicit in Deep Learning