Negative Momentum for Improved Game Dynamics

Abstract

Games generalize the single-objective optimization paradigm by introducing different objective functions for different players. Differentiable games often proceed by simultaneous or alternating gradient updates. In machine learning, games are gaining new importance through formulations like generative adversarial networks (GANs) and actor-critic systems. However, compared to single-objective optimization, game dynamics are more complex and less understood. In this paper, we analyze gradient-based methods with momentum on simple games. We prove that alternating updates are more stable than simultaneous updates. Next, we show 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.

arXiv commentAppears in: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2019). Minor changes with respect to the AISTATS version: typo corrected in Thm. 6 (squared condition number instead of condition number; and small change in constant) and dependence in $\beta$ changed in Theorem 5 for the formal statement; not changing the conclusions. 28 pages

References in corpus (16)

• Conditional Generative Adversarial Nets
• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Spectral Normalization for Generative Adversarial Networks
• Which Training Methods for GANs do actually Converge?
• BEGAN: Boundary Equilibrium Generative Adversarial Networks
• Unrolled Generative Adversarial Networks
• Stabilizing Training of Generative Adversarial Networks through Regularization
• The Numerics of GANs
• A Variational Inequality Perspective on Generative Adversarial Networks
• The Mechanics of n-Player Differentiable Games
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• YellowFin and the Art of Momentum Tuning
• Is Generator Conditioning Causally Related to GAN Performance?
• Local Saddle Point Optimization: A Curvature Exploitation Approach

Cited by in corpus (12)

• The Unusual Effectiveness of Averaging in GAN Training
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
• Finding Mixed Nash Equilibria of Generative Adversarial Networks
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Understanding and Stabilizing GANs' Training Dynamics with Control Theory
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum