PaperlayerView exact revision on arXiv

Source-linked AI summary

The Mechanics of n-Player Differentiable Games

David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, Thore Graepel

arXiv:1802.05642v2cs.LGcs.GTcs.MAcs.NE

TL;DR

Gradient descent lacks convergence guarantees in games with multiple interacting losses, where cyclic behavior can occur. The paper decomposes game dynamics into potential and Hamiltonian components, then derives SGA for stable fixed points; experiments report faster, more robust convergence and rapid GAN convergence where simultaneous gradient descent fails.

  • Problem

    Gradient-based methods in games can cycle, converge slowly, and lack a single objective for measuring progress.

  • Method

    The paper decomposes game Hessians into symmetric and antisymmetric components and derives Symplectic Gradient Adjustment for general games.

  • Results

    SGA yields faster, more robust convergence and rapid GAN convergence where simultaneous gradient descent completely fails.

  • Takeaways & Limitations

    Potential and Hamiltonian games become separately tractable, while SGA provides a gradient-based approach for stable fixed points in more general games.

  • Takeaways & Limitations

    The behavior of SGA near indefinite fixed points is not analyzed, and pure first-order alternatives remain an open direction.

Abstract

from arXiv · show

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.

1. Introduction

Gradient descent behaves predictably for single objectives but can cycle, diverge, or lack useful progress in games with interacting losses. The paper decomposes game dynamics and introduces SGA to find stable fixed points in general games.

  • Motivation: Multiple interacting objectives invalidate the local-minimum convergence guarantee associated with ordinary gradient descent.The paper motivates this problem using GANs and other models trained as games between cooperating or competing modules.
  • Motivation: Gradient descent in games can cycle, converge too slowly, or provide no single objective for measuring progress.Rotational forces may require very small learning rates, while application-specific proxies such as inception score are limited during training.
  • Core analysis: The paper decomposes second-order game dynamics into symmetric and antisymmetric components, identifying potential and Hamiltonian games as tractable cases.Potential games correspond to gradient descent on an implicit function, while Hamiltonian games obey a conservation law.
  • Core method: Symplectic gradient adjustment (SGA) targets stable fixed points in general games and is guaranteed to find stable equilibria in potential and Hamiltonian games.SGA uses two Hessian-vector products, costing two backpropagation iterations.
  • Results: SGA allows higher learning rates and faster, more robust convergence, while GAN experiments report rapid convergence where simultaneous gradient descent fails.Correctly choosing the adjustment sign slightly improves convergence in the reported GAN setup.
  • Scope: SGA does not analyze fixed points that are neither positive nor negative semidefinite, leaving indefinite fixed points for future work.This is explicitly identified as a caveat of the analysis.

2. The infinitesimal structure of games

The paper studies game dynamics through their vector fields and Hessians, separating symmetric potential-like behavior from antisymmetric Hamiltonian-like behavior. Potential games reduce to optimization, while Hamiltonian games conserve a quantity whose gradient descent can reach local Nash equilibria.

  • Game dynamics: A game consists of players with twice continuously differentiable losses over jointly represented parameters, and its simultaneous gradient forms the game vector field.The dynamics follow the negative vector field with infinitesimal steps, which need not be the gradient of a single function.
  • Second-order structure: The Hessian of any game decomposes uniquely as H(w) = S(w) + A(w), with S symmetric and A antisymmetric.This generalized Helmholtz decomposition is preserved under orthogonal changes of coordinates.
  • Game classes: Potential games have A(w) ≡ 0, whereas Hamiltonian games have S(w) ≡ 0.The general case combines potential-like and Hamiltonian-like dynamics and is more delicate.
  • Stable fixed points: Stable fixed points are local Nash equilibria, while fixed points that are neither positive nor negative definite are outside the paper's scope.The stability definition is based on the symmetric component S near the fixed point.
  • Potential games: In potential games, simultaneous gradient descent is gradient descent on a single potential function and can converge to a local minimum of that function.The paper uses the exact-potential special case with unit scaling factors.
  • Hamiltonian games: Hamiltonian dynamics are orthogonal to ∇H, preserve H's level sets, and can cycle around equilibria.For Hamiltonian games, H(w) = 1/2∥ξ(w)∥2 and gradient descent on H converges to a local Nash equilibrium under invertibility and coercivity conditions.

3. Algorithms

The paper develops SGA for finding stable fixed points in general games by combining potential and Hamiltonian dynamics. It adjusts the game gradient using a Hessian-derived term, with the sign chosen to improve stability and convergence.

  • Finding fixed points: Consensus optimization can converge to unstable fixed points, including global maxima in basic potential games.Descent on ξ + λ · H^Tξ converges to the global maximum unless λ < 1.
  • Symplectic gradient adjustment: SGA outputs ξ + λ · A^Tξ and can be plugged into any optimizer.The adjustment uses the antisymmetric Hessian component and is designed for general games.
  • Symplectic gradient adjustment: SGA satisfies D1–D3 for λ > 0, while negative λ is necessary near S ≺ 0.D1 and D2 remain valid for λ < 0; the sign is selected to address stable and unstable equilibria.
  • Symplectic gradient adjustment: Positive λ can fail when weak repulsion combines with strong rotational force, causing convergence to an unstable equilibrium.In the stated example, convergence to the unstable equilibrium occurs when λ > ε.
  • How to pick sign(λ): Rotational forces make the original gradient dynamics follow non-steepest paths, requiring smaller learning rates and slowing convergence.Increasing alignment with the steepest direction improves convergence.
  • How to pick sign(λ): The sign of λ is chosen from alignment checks so the adjusted dynamics point toward stable and away from unstable fixed points.The criterion uses the signs of ⟨ξ, ∇H⟩ and ⟨A^Tξ, ∇H⟩.
  • Aligned consensus optimization: Aligned consensus optimization satisfies D3–D5 but can slow convergence in potential games by increasing the usual condition number.The Hessian multiplication increases the gap between small and large eigenvalues.

4. Experiments

Experiments compare SGA with gradient-based alternatives in synthetic, zero-sum, and multimodal GAN settings. SGA generally converges faster or across a wider learning-rate range, and avoids the mode collapse and hopping seen with simultaneous gradient descent.

  • 4. Experiments: The experiments compare SGA with simultaneous gradient descent, optimistic mirror descent, and consensus optimization.The comparisons cover basic settings including a zero-sum bimatrix game and a multimodal GAN.
  • 4.1. Learning rates and alignment: SGA converges faster and more robustly than gradient descent under a weak attractor coupled to a strong rotational force.Gradient descent converges slowly or diverges as η increases through {0.01, 0.032, 0.1}; SGA converges faster at η = 0.01 and η = 0.032 and overshoots only at η = 0.1.
  • 4.2. Comparison with optimistic mirror descent: SGA converges for a wider range of learning rates than optimistic mirror descent, although OMD has better peak performance.OMD diverges outside [0.3, 1.2], while simultaneous gradient descent oscillates without converging.
  • 4.3. Generative adversarial networks: In a 16-Gaussian multimodal GAN, simultaneous gradient descent exhibits mode collapse followed by later mode hopping.The generator and discriminator are six-layer ReLU networks trained on a 4 × 4 grid of Gaussian modes.
  • 4.3. Generative adversarial networks: Unaligned SGA converges to the correct distribution, while alignment speeds convergence slightly.Consensus optimization performs similarly but can converge to local maxima.

5. Discussion

The discussion frames game dynamics through a generalized Helmholtz decomposition that separates symmetric and antisymmetric second-order effects. It presents SGA as a direct application while acknowledging that better methods may exist and that player losses are not its primary target.

  • 5. Discussion: The generalized Helmholtz decomposition applies independently of the number of players and links dynamics to symmetric and antisymmetric second-order terms.The interplay between simultaneous gradients and these matrices guides algorithm design and governs gradient-adjustment dynamics.
  • 5. Discussion: SGA is unlikely to be the only or best method for finding stable fixed points.The paper identifies deeper interactions between potential and Hamiltonian components as a route to more effective algorithms.
  • 5. Discussion: A stated direction is developing pure first-order methods that do not use Hessian-vector products.SGA is described as a straightforward application of the Helmholtz decomposition.
  • 5. Discussion: The paper prioritizes stable fixed points over the players’ losses themselves.Gradient adjustments may increase an individual player’s loss when this encourages convergence to a stable fixed point.

A. Stable fixed points vs local Nash equilibria

The paper prefers stable fixed points over local Nash equilibria because local Nash equilibria can be unstable in general potential games. In two-player zero-sum games, however, the two concepts coincide.

  • A. Stable fixed points vs local Nash equilibria: Stable fixed points are also local Nash equilibria, but local Nash equilibria need not be stable fixed points.The paper gives an example of a local Nash equilibrium that is not stable.
  • A. Stable fixed points vs local Nash equilibria: In two-player zero-sum games, local Nash equilibria are stable fixed points.For this game class, the two solution concepts therefore coincide.
  • A. Stable fixed points vs local Nash equilibria: The paper distinguishes the solution concepts because their equivalence depends on the game class.The equivalence holds for two-player zero-sum games but not for potential games generally.
  • A. Stable fixed points vs local Nash equilibria: Example 7 is a potential game whose Nash equilibrium is a saddle point of its potential function.Its dynamics satisfy ξ = ∇φ and H = ∇2φ.
  • A. Stable fixed points vs local Nash equilibria: Local Nash equilibrium is rejected as the preferred solution concept because convergence to a potential-function saddle does not count as good behavior.The paper instead uses stable fixed points for its purposes.

B. Proofs

The proofs establish conservation and alignment properties for Hamiltonian games and analyze how SGA modifies directions and allowable step sizes. They connect these results to convergence toward stable fixed points under stated matrix and smoothness conditions.

  • Hamiltonian games: Skew-symmetry makes the directional derivative of H vanish in Hamiltonian games, establishing conservation along the dynamics.The proof uses A = −A⊺ to show ξ⊺A⊺ξ = 0.
  • Hamiltonian games: In Hamiltonian games, gradient descent on the conserved quantity H reaches points where ∇H = 0, which become local Nash equilibria when the Hessian is invertible.The proof uses ∇H = H⊺ξ and the positive-semidefinite symmetric component S = 0.
  • Proofs for potential and mixed games: For positive-semidefinite S, the proof bounds λ using σmax and shows positivity of the resulting terms.It reduces the argument to σmin = 0 and κ = σmax, then uses a square-root matrix T with T⊺T = S.
  • Alignment: The sign of λ is selected so the adjusted direction increases alignment with stable fixed points and decreases alignment with unstable ones.A small ϵ > 0 adds a weak bias toward stable fixed points.
  • Alignment and convergence rates: The alignment lemma shows that a unit-vector update remains within the unit ball when 0 ≤ η ≤ 2w⊺ξ.Thus, smaller cosine alignment restricts the allowable learning rate.

C. TensorFlow code to compute A⊺ξ:

The TensorFlow implementation computes antisymmetric Jacobian adjustments from player losses and variables, using forward and transposed forward gradients.

  • TensorFlow interface: The code accepts a list of n losses, Ls, and a corresponding list of player variables, xs.The forward-gradient utility is imported from tf.contrib.kfac.utils.
  • Jacobian utilities: jac_vec computes Jacobian–vector quantities, while jac_tran_vec computes their transposed counterparts.The transposed routine stops gradients through xs and substitutes zero tensors when derivatives are unavailable.
  • Validation: Figure 7 compares OMD and SGA convergence times on two four-player games, with times capped after 5000 iterations.The left game uses weakly positive definite S with ϵ = 1 100, while the right has no symmetric component.
  • Symplectic adjustment: get_sym_adj constructs each player’s antisymmetric adjustment from the difference between forward and transposed Jacobian terms.For each player, it forms one-half of the difference between H_xi and Ht_xi.

D. Further experiments

Further experiments compare SGA with OMD and examine GAN and geometric connections. SGA converges faster and more robustly in the reported four-player games, while alignment improves consensus optimization slightly.

  • OMD and SGA: SGA converges faster and more robustly than OMD across the tested learning rates in a four-player game.OMD diverges for learning rates > 0.22 and is considerably slower across the full range.
  • Consensus optimization: Alignment slightly improves consensus optimization’s convergence speed and final result, although intermediate results are ambiguous.The comparison is shown in figure 9.
  • Geometric connections: The antisymmetric game-Hessian component is connected to rotational behavior through differential forms and the curl analogy.The antisymmetric matrix captures the infinitesimal tendency of the gradient field to rotate in parameter space.
  • Geometric connections: A Hamiltonian vector field is characterized using a symplectic form and an associated Hamiltonian function.In the game setting, the antisymmetric matrix is a closed, potentially degenerate two-form, hence presymplectic.

E.3. The Hodge decomposition

The Hodge decomposition separates differential forms into three components, but its direct application to games on Rn is not straightforward because Rn is noncompact.

  • Hodge decomposition: Hodge’s theorem decomposes k-forms on a compact manifold into three types, and setting k = 1 yields a decomposition resembling generalized Helmholtz decomposition.The harmonic component corresponds to de Rham cohomology and vanishes for k = 1 on Rn.
  • Scope boundary: The Hodge decomposition does not straightforwardly apply to Rn because Rn is not compact.The relationship between generalized Helmholtz and Hodge decompositions is therefore unclear in this setting.
  • Related decomposition: Candogan et al.’s game-theoretic Hodge decomposition is related in spirit but differs technically from the paper’s generalized Helmholtz decomposition.Their work treats finite strategy sets with multilinear losses and uses combinatorial Hodge theory.

F.1. Units in classical mechanics

The classical-mechanics analogy assigns physical units to positions, momenta, losses, and differential forms, using a corrected musical isomorphism to recover the symplectic structure and Hamiltonian.

  • Physical quantities: In classical mechanics, q denotes position, p = µ · ˙q denotes momentum, µ denotes mass, κ denotes surface tension, and H measures energy.The associated physical units include meters, kilograms, seconds, and joules.
  • Symplectic formulation: The flow of the classical system is reformulated using symplectic geometry and a symplectic form.Contracting the flow with the Hamiltonian provides the corresponding geometric relation.
  • Game-theoretic analogy: The Hamiltonian dynamics can be represented game-theoretically by defining losses and differentiating them with respect to position and momentum.This construction recovers the Hamiltonian.
  • Type consistency: Naively mapping the vector field to a differential form creates a type violation because objects with different types cannot be added.The paper corrects this inconsistency by modifying the musical isomorphism.
  • Type consistency: The corrected musical isomorphism compensates for coupling terms involving µ and κ, yielding the appropriate differential form and associated two-form.The resulting two-form recovers the symplectic form up to sign, with units τ(ω) = kg·m2 s.
  • Extension to games: The paper extends the units analysis to quadratic two-player games, where methods depend only on first and second derivatives.It uses symmetric matrices and corrects the musical isomorphism according to off-diagonal coupling blocks, with singular value decomposition available for the factorization.

F.3. What does type-consistency buy?

Example 8 shows that type-consistency can identify when no symplectic gradient adjustment is needed, even when the vector field is not a potential field. In this case, the field performs gradient descent on a family of functions with possibly non-optimal coordinate-wise learning rates.

  • Example 8 considers the vector field ξ = (y, 2x), for which no potential function φ satisfies ∇φ = ξ.
  • Although ξ is not a potential field, it performs gradient descent on functions φα(x, y) = α · xy with coordinate-wise learning rates.The learning rates may not be optimal.
  • This situation can arise when neural-network training adaptively rescales different parameters by positive learning-rate factors.
  • Type-consistency yields zero symplectic gradient adjustment, detecting that this example requires no adjustment.
Loading 1802.05642v2…