Negative Momentum for Improved Game Dynamics

By Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Gabriel Huang, Rémi Le Priol, Simon Lacoste-Julien, Ioannis Mitliagkas. 2018

192 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

In Optimization & Training

Citations in the corpus

A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “Gidel et al. (2019a) interpreted GANs as a variational inequality problem and derive a variant of extragradient which avoids "wasting" a gradient.”
A Closer Look at the Optimization Landscapes of Generative Adversarial Networks (2019, methodology): “We focus on two common GAN loss formulations: we consider both the original nonsaturating GAN (NSGAN) formulation proposed in Goodfellow et al. (2014) and the WGAN-GP objective described in Gulrajani et al.”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “The gradient method does not converge for some convex-concave examples (Mescheder et al., 2017; Gidel et al., 2019a).”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “, 2014; Iusem et al., 2017) for stochastic variational inequalities with bounded constraints. A linearly convergent variance reduced version of the stochastic gradient method has been proposed by Palaniappan and Bach (2016) for strongly monotone variational inequalities.”
Adversarial score matching and improved sampling for image generation (2020, methodology): “Following the trend towards zero or negative momentum (Gidel et al., 2019), we used the Adam optimizer with hyperparameters ( β 1 , β 2 ) = ( − .”
The Unusual Effectiveness of Averaging in GAN Training (2018, methodology): “Averaging at minimax objective: Gidel et al. (2018) used uniform averaging similar to our work, however we show its shortcomings and how exponential decay averaging performs better.”
When can Wasserstein GANs minimize Wasserstein Distance? (2020, background): “2 Related works Generative Adversarial Networks The works [29, 16, 25, 9, 10, 13, 21, 28, 22] considers either local convergence property of the GAN training, or the global convergence property when the objective is convex-concave However, there is no clear evidence of how the local property can be ”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, background): “Previous work has found negative momentum to be useful in asynchronous distributed optimization Mitliagkas et al. (2016) and for stabilizing adversarial training Gidel et al. (2018).”
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? (2019, background): “Gidel et al. [2018] investigate the effect of simultaneous versus alternating gradient updates as well as the effect of momentum on the convergence in bilinear games.”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, background): “Gidel et al. [2018] investigate the effect of simultaneous versus alternating gradient updates as well as the effect of momentum on the convergence in bilinear games.”
On the convergence of single-call stochastic extra-gradient methods (2019, methodology): “First, given the extensive literature on the subject, this list is not exhaustive; see e.g., [30, 31, 36] for a generalization of (OG), [26] for a variant that employs averaging to update the algorithm’s base state X t , and [19] for a proxy deﬁned via “negative momentum”.”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “As noted by Mescheder et al. (2017); Gidel et al. (2019); Balduzzi et al. (2018), the rotational behaviour (instability) of GDA is caused by eigenvalues with large imaginary part.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “…GDA algorithms with constant stepsizes could fail to converge for general smooth function [Mescheder et al., 2018], even for the bilinear games [Gidel et al., 2019]; even when they do converge, the stable limit point may not be a local Nash equilibrium [Daskalakis et al., 2018, Mazumdar and…”