PaperlayerView exact revision on arXiv

Source-linked AI summary

Negative Momentum for Improved Game Dynamics

Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Remi Lepriol, Gabriel Huang, Simon Lacoste-Julien, Ioannis Mitliagkas

arXiv:1807.04740v5cs.LGstat.ML

TL;DR

Gradient-based optimization in games is harder to analyze than single-objective minimization because different players jointly pursue distinct objectives. The paper analyzes update ordering, step-size, and momentum, finding that alternating updates with negative momentum improve convergence in bilinear games and saturating GANs.

  • Problem

    Game dynamics are less understood than single-objective optimization, including whether update ordering and momentum can improve convergence toward local Nash equilibria.

  • Method

    The paper analytically and experimentally studies simultaneous and alternating gradient updates with different step-sizes and momentum values on smooth games and GANs.

  • Results

    Alternating updates with negative momentum converge in bilinear smooth games and improve convergence properties for adversarial games and saturating GANs.

  • Takeaways & Limitations

    Negative momentum can make convergence to Nash equilibria easier in simple adversarial games and supports training with saturating GAN losses.

  • Takeaways & Limitations

    The convergence analysis excludes purely adversarial games with pure imaginary eigenvalues and provides no guarantees for large negative momentum values.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies gradient-based dynamics in differentiable games, focusing on update ordering, step-size, and momentum. It argues that alternating updates with negative momentum improve convergence in bilinear games and GAN training.

  • Differentiable games assign different objectives to multiple players and can be optimized through simultaneous or alternating gradient updates.
  • The authors study simultaneous versus alternating updates and how step-size and momentum affect adversarial-game dynamics.Their approach uses momentum with alternating gradients to manipulate oscillatory behavior.
  • Alternating gradient updates with negative momentum are the only studied setting that converges on the bilinear smooth game.Zero or positive momentum and simultaneous updates fail to converge in that setting.
  • Negative momentum can improve local convergence when the Jacobian has eigenvalues with large imaginary parts.
  • Negative momentum benefits GAN training with saturating losses on toy settings and real datasets.

2 BACKGROUND

The background frames GAN training and differentiable games as local-Nash-equilibrium problems whose gradient dynamics can differ from ordinary minimization. It introduces cooperative, adversarial, and intermediate games through Jacobian eigenvalues.

  • GAN training is a differentiable two-player game involving discriminator and generator objectives.The discriminator distinguishes real from generated examples, while the generator seeks to produce confusingly realistic examples.
  • Purely adversarial games have purely imaginary Jacobian eigenvalues, as in the bilinear game L(ϕ, θ) := ϕ⊤Aθ.
  • Purely cooperative games have real positive Jacobian eigenvalues and can reduce to separate convex minimization problems.
  • The paper studies intermediate games with eigenvalues having non-negative real parts and non-zero imaginary parts.
  • Games seek local Nash equilibria, where no player can locally and unilaterally improve its objective.Stable stationary points of gradient dynamics need not be local Nash equilibria.

3 TUNING THE STEP-SIZE

This section characterizes step-size selection through the Jacobian spectrum and spectral radius. It shows that eigenvalues with large imaginary components can constrain step-sizes and slow convergence.

  • Linear convergence near a fixed point is guaranteed when the update operator has spectral radius ρmax < 1.
  • The update operator’s eigenvalues are 1 −ηλ for Jacobian eigenvalues λ, linking step-size selection to the game dynamics spectrum.
  • The optimal step-size ηbest minimizes the spectral radius through a convex quadratic-by-parts problem when all Jacobian eigenvalues have positive real parts.
  • When ηbest = ℜ(1/λ1), the best convergence rate satisfies ρmax(ηbest)^2 = sin(ψ1)^2.
  • Large imaginary eigenvalue components can force small step-sizes and convergence rates arbitrarily close to 1.The paper motivates momentum as a way to improve convergence by changing the Jacobian spectrum.

4 NEGATIVE MOMENTUM

Negative momentum modifies gradient dynamics by shifting relevant eigenvalues toward the origin, which can improve convergence when adversarial oscillations are present. The guarantees are local and exclude purely imaginary eigenvalues.

  • 4 NEGATIVE MOMENTUM: Negative momentum can damp oscillations by shifting relevant Jacobian eigenvalues toward the origin.The method adds friction-like behavior to the update dynamics; state-augmentation eigenvalues can remain smaller in magnitude.
  • 4 NEGATIVE MOMENTUM: Small negative momentum improves convergence when Jacobian eigenvalues have substantial imaginary components.Large imaginary parts otherwise restrict the usable step-size and slow convergence.
  • 4 NEGATIVE MOMENTUM: Figure 4 shows a smaller negative-momentum convergence circle than the gradient-method circle across a broad range of step-sizes.For η = 1.55 and β = −.25, the transformed eigenvalues move toward the origin while state-augmentation eigenvalues do not determine the rate.
  • 4 NEGATIVE MOMENTUM: The local theorem guarantees improvement when one limiting eigenvalue exists or when the relevant eigenvalue intervals have a nonempty intersection.If |Arg(λ1)| > π/4, the theorem places the optimal step-size in the corresponding interval.
  • 4 NEGATIVE MOMENTUM: The analysis provides no guarantee for large negative momentum and does not cover games with purely imaginary eigenvalues.Purely adversarial bilinear games are excluded because the first-order analysis cannot push the relevant eigenvalue into the unit circle.

5 BILINEAR SMOOTH GAMES

For bilinear smooth games, alternating updates alter the Jacobian spectrum in a way that can stabilize the dynamics. With suitably chosen negative momentum, alternating methods converge linearly, whereas simultaneous methods diverge.

  • 5 BILINEAR SMOOTH GAMES: The analysis assumes that the bilinear game has an equilibrium, requiring the offset vectors to lie in the relevant column spaces.Translations then reduce the setting to centered variables without loss of generality.
  • 5.1 Simultaneous gradient descent: Simultaneous gradient methods diverge geometrically for β ≥ −1 under the stated nonnegative step-size conditions.The eigenvalue magnitudes are always larger than 1 in the analyzed setting.
  • 5.2 Alternating gradient descent: Alternating updates change the characteristic polynomial and can place its eigenvalues inside the unit disk with suitable negative momentum.The alternating method uses the newly updated parameter in the second player’s update, changing a key polynomial term’s degree.
  • 5.2 Alternating gradient descent: With zero momentum, alternating iterates remain bounded, while well-chosen negative momentum yields convergence for bilinear smooth games.The paper’s theorem establishes a convergent regime under an explicit step-size and momentum choice.
  • 5.2 Alternating gradient descent: The paper concludes that alternating steps improve gradient-method convergence properties and that negative momentum can make the method linearly convergent.The positive-momentum divergence claim is supported by the paper’s experiments and appendix analysis.

6 EXPERIMENTS AND DISCUSSION

Experiments test negative momentum in bilinear games and saturating-loss GANs. They compare update schedules, momentum values, and step-sizes across toy and image-generation settings.

  • Min-Max Bilinear Game: The bilinear experiment compares positive and negative momentum under both alternating and simultaneous gradient updates.The setup uses φ, θ ∈ R with A = 1.
  • Min-Max Bilinear Game: Figure 5 evaluates alternating momentum and step-size combinations using normalized distance to the equilibrium after 500k iterations.Values above 1 indicate divergence, while values below 1 indicate convergence.
  • Min-Max Bilinear Game: Figure 5’s parameter grid compares momentum β and step-size η, with color encoding normalized distance to equilibrium.The figure’s key comparison is whether negative momentum permits convergence at larger step-sizes than positive momentum.
  • Fashion MNIST and CIFAR 10: GAN experiments apply negative momentum with alternating steps and saturating loss on CIFAR-10 and Fashion-MNIST.Residual generator and discriminator networks without batch normalization are used, with generator momentum fixed at 0.5.

7 RELATED WORK

Related work places negative momentum within broader studies of optimization dynamics, GAN stabilization, eigenvalue analysis, and alternative gradient methods. The paper distinguishes its momentum mechanism from OGDA and connects GAN behavior to Jacobian conditioning and spectra.

  • Optimization: Prior optimization studies analyze momentum and momentum tuning, but the cited work had not considered negative momentum in this game setting.Asynchronous single-objective optimization provides a related negative-momentum interpretation, but not the same game formulation.
  • Optimization: The paper distinguishes Polyak momentum, based on past iterates, from OGDA, which uses differences between previous gradients.Both can be viewed as gradient-method variants with additional terms, but the terms are structurally different.
  • GANs as games: Other GAN methods address training dynamics through extrapolation, averaging, extra-gradient updates, or decompositions of game dynamics.These approaches provide alternative mechanisms for analyzing or stabilizing GAN optimization.
  • GANs as games: Related GAN analyses connect training behavior to Jacobian conditioning and eigenvalues moving away from one along the real axis.Figure 6 instead compares negative and positive momentum using inception scores or generated samples on two datasets.

8 CONCLUSION

The paper concludes that alternating updates with negative momentum improve convergence in bilinear games and support training with saturating GAN losses. It also argues that negative momentum may explain declining momentum choices in GAN research and should be included in hyper-parameter searches.

  • 8 CONCLUSION: Alternating updates with negative momentum are the only studied setting that converges in bilinear smooth games.Simultaneous updates and alternating updates with zero or positive momentum fail to converge within the study parameters.
  • 8 CONCLUSION: Negative momentum can improve convergence by shifting Jacobian eigenvalues into a smaller convergence disk.This claim is presented for a large class of adversarial games.
  • 8 CONCLUSION: Experiments support negative momentum for saturating losses on Gaussian mixtures, CIFAR-10, and fashion MNIST.The conclusion also notes that fully stabilizing GAN learning requires understanding highly nonlinear dynamics.
  • 8 CONCLUSION: The authors encourage practitioners to include negative momentum values in GAN hyper-parameter searches.They connect this recommendation to a reported decline in momentum values used by GAN papers.
  • 8 CONCLUSION: Figure 7 shows simultaneous updates have eigenvalue magnitudes above 1, whereas alternating updates have regions below 1 for suitable η and β.For alternating updates, magnitudes below 1 imply linear convergence in the bilinear setting.

A.2 Mixture of Gaussian

The Gaussian-mixture experiment tests whether negative momentum prevents mode collapse in a saturating-loss GAN. Negative momentum considerably improves the generated results relative to zero or positive momentum.

  • A.2 Mixture of Gaussian: The experiment uses eight Gaussian distributions uniformly arranged around the unit circle and evaluates whether the generator produces diverse samples.The setup is intended to test mode collapse in a simple but difficult GAN task.
  • A.2 Mixture of Gaussian: Figure 8 compares real data with SGD using zero generator momentum and negative, zero, or positive discriminator momentum.The figure isolates the discriminator momentum choice while keeping generator momentum at zero.
  • A.2 Mixture of Gaussian: The network uses four fully connected hidden ReLU layers with 256 units per layer.The supplied experimental description specifies this architecture.
  • A.2 Mixture of Gaussian: Negative momentum considerably improves results compared with positive or zero momentum after 100,000 SGD iterations.Training uses learning rate 0.01 and momentum values 0, −0.5, and 0.5.

B DISCUSSION ON MOMENTUM AND CONDITIONING

This section studies how game structure and matrix conditioning affect the optimal momentum. The analysis finds that adversarial structure can favor negative momentum even when the condition number is large.

  • B DISCUSSION ON MOMENTUM AND CONDITIONING: The model extends a bilinear min-max game with a mixing parameter α and a positive-definite diagonal matrix D.The matrix condition number is defined as κ(D) = d_n,n/d_1,1.
  • B DISCUSSION ON MOMENTUM AND CONDITIONING: Figure 9 computes the β minimizing the maximum spectral radius across step sizes and condition numbers.The matrix is normalized so its diagonal entries sum to n.
  • B DISCUSSION ON MOMENTUM AND CONDITIONING: The spectral radius ρ(∇F_η,β) is the largest magnitude among the eigenvalues generated by step size η and momentum β.The section uses this quantity to evaluate convergence behavior.
  • B DISCUSSION ON MOMENTUM AND CONDITIONING: The optimal momentum reflects a competition between adversarial versus cooperative game structure and the conditioning of D.The reported numerical setting varies both factors.
  • B DISCUSSION ON MOMENTUM AND CONDITIONING: Even with a large condition number, sufficiently adversarial games can have a negative optimal momentum.The authors suggest this points toward a multidimensional condition number combining matrix ill-conditioning and adversarial difficulty.

C LEMMAS AND DEFINITIONS

This section establishes spectral-radius criteria and supporting lemmas for analyzing gradient dynamics. It connects eigenvalue magnitude to boundedness, divergence, and local linear convergence, then characterizes optimal step sizes and momentum effects.

  • C LEMMAS AND DEFINITIONS: The spectral radius is the maximum magnitude of a matrix’s eigenvalues and governs the asymptotic behavior of linear iterates.The supporting lemmas distinguish cases where the radius is greater than, equal to, or less than 1.
  • C LEMMAS AND DEFINITIONS: For bilinear games, iterates remain in subspaces determined by spans of A and A^⊤.This invariant-subspace property is used for both simultaneous and alternating updates.
  • C LEMMAS AND DEFINITIONS: If ρ(M) > 1, some initializations grow asymptotically at least as fast as ρ(M)^t.The unit-radius diagonalizable case yields bounded iterates up to norm-equivalence constants.
  • C LEMMAS AND DEFINITIONS: If ρ(M) < 1, the iterates decay at rate O((ρ(M))^t∥u_0∥_2).The result follows by diagonalizing M and bounding its powers.
  • C LEMMAS AND DEFINITIONS: A fixed point with Jacobian spectral radius below 1 has locally linear convergence at rate O((ρ(∇F_η(x*)) + ε)^t).The result requires initialization within a neighborhood of the stationary point.
  • C LEMMAS AND DEFINITIONS: For positive-real-part eigenvalues, the best no-momentum step size minimizes a piecewise-quadratic spectral-radius objective.At η_best = ℜ(1/λ_1), the squared radius is sin(ψ_1)^2.

D.5 Proof of Thm. 5

The proof analyzes the simultaneous and alternating momentum operators through characteristic polynomials and spectral radii in a bilinear game. It establishes divergence for simultaneous updates while contrasting this with convergence behavior under a suitable alternating negative-momentum setting.

  • Simultaneous updates: The simultaneous gradient step with momentum is represented by a linear operator whose characteristic polynomial accounts for the positive eigenvalues and null singular values of A.The analysis diagonalizes A⊤A and reduces the determinant to contributions from its spectrum.
  • Simultaneous updates: For β ≥0, the radial spectrum is lower bounded by 1 + η1η2σ2 max(A), while for −1/16 ≤β < 0 it is lower bounded by 1 + η1η2σ2 max(A)/17.Both bounds remain above 1 when the step sizes are positive, supporting divergence of the simultaneous dynamics.
  • Alternating updates: For alternating updates, eigenvalue magnitudes can be smaller than 1 over a large range of step-size and momentum values, motivating analytical convergence-rate results.The numerical observation is followed by Theorem 6, which imposes a step-size condition and a negative momentum choice.
  • Alternating updates: The alternating operator is analyzed by reducing the dynamics to independent four-dimensional linear operators associated with the positive singular values of A.Orthogonal transformations place the dynamics in the span of a diagonal matrix, so each eigenspace can be studied separately.
Loading 1807.04740v5…