Technical Summary: Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach

Problem Statement

While the Adam optimizer has achieved remarkable success in training neural networks for minimization problems, its descent-ascent counterpart, Adam-DA, is the de facto standard for solving zero-sum games, particularly in Generative Adversarial Networks (GANs). Despite its widespread practical adoption, the theoretical understanding of Adam-DA in zero-sum settings lags significantly behind its minimization counterpart. Existing theoretical frameworks often assume that principles derived from minimization (e.g., the benefits of positive momentum) apply directly to games. However, empirical evidence in GAN training suggests that negative momentum often improves stability, creating a gap between theory and practice. This paper addresses the need for a rigorous theoretical framework to understand Adam-DA's dynamics, specifically investigating how its parameters influence local convergence and implicit gradient regularization in zero-sum games.

Methodology

The authors employ an Ordinary Differential Equation (ODE) approach to analyze the continuous-time limits of the discrete-time Adam-DA algorithm. This methodology, rooted in Polyak's seminal work on momentum methods, allows for a tractable analytical framework to study complex dynamics.

1. Derivation of Continuous-Time Models: The paper derives a specific set of ODEs, termed "Continuous Adam-DA," which serve as the continuous-time limit of the Adam-DA algorithm. The authors establish that these ODEs approximate the discrete-time trajectories with a local error of $O(h^3)$, a significant improvement over previous min-max adaptations like SignGDA-flow, which have $O(h^2)$ errors.
2. Local Convergence Analysis: Using dynamical systems theory, the authors analyze the Jacobian matrix of the Continuous Adam-DA at a local Nash equilibrium. They derive a quadratic polynomial relationship between the Jacobian of Adam-DA and the Jacobian of the standard Gradient Descent-Ascent (GDA) method. This relationship allows for the derivation of convergence conditions based on the eigenvalues of the underlying game dynamics.
3. Implicit Gradient Regularization (IGR) Analysis: The authors analyze the higher-order terms in the derived ODEs to understand how the algorithm interacts with the geometry of the loss landscape. Specifically, they examine how the momentum parameters influence the algorithm's tendency to explore "flatter" regions (regions with lower gradient norms).
4. Empirical Validation: The theoretical predictions are validated through extensive experiments on GAN training across multiple architectures (ResNet, CNN, Self-Attention) and datasets (CIFAR-10, STL-10, CelebA). The experiments measure cumulative average gradient norms and Inception Scores (IS) to correlate parameter choices with landscape flatness and training performance.

Key Contributions

1. Local Convergence Dynamics

The paper provides quantitative local convergence results for both the Continuous Adam-DA ODEs and the discrete Adam-DA algorithm. A central finding is the reversal of the momentum parameter's role compared to minimization:

• First-Order Momentum ($\beta$): In minimization, a larger $\beta$ typically allows for a wider range of step sizes for convergence. In contrast, the authors prove that in zero-sum games, a smaller $\beta$ (including negative values) enables local convergence over a broader range of step sizes.
• Bilinear Games: The analysis reveals that Adam-DA always diverges on bilinear objectives ($f(x,y) = x^\top Ay$), regardless of parameter choices. This contrasts with minimization, where Adam can converge to a neighborhood of a local minimum under suitable parameters.

2. Implicit Gradient Regularization (IGR)

The paper characterizes how Adam-DA's parameters affect the exploration of the loss landscape geometry:

• Reversed IGR Effect: In minimization, larger $\beta$ and smaller second-order momentum $\rho$ guide trajectories toward flatter minima. The authors demonstrate that in zero-sum games, the effect is exactly opposite: smaller $\beta$ and larger $\rho$ guide trajectories toward flatter regions of the min-max loss landscape (defined by lower $\ell_1$ norms of gradients).
• Theoretical Justification: This behavior is derived from the ODE analysis, showing that the interaction term $K(\beta, \rho) = \frac{1+\beta}{1-\beta} - \frac{1+\rho}{1-\rho}$ dictates the regularization strength. In interaction-dominated games, reducing this term (via smaller $\beta$ and larger $\rho$) minimizes the ascent on gradient norms, promoting stability.

3. Continuous-Time Approximation

The authors provide a rigorous error bound showing that their proposed Continuous Adam-DA ODEs approximate the discrete algorithm with $O(h^3)$ local error. This high-order approximation is shown to be superior to existing continuous-time models (like SignGDA-flow) in capturing the true dynamics of Adam-DA, particularly in scenarios where simpler models diverge or converge to incorrect equilibria.

Results

• Theoretical Predictions: The derived convergence bounds confirm that the stability region for Adam-DA expands as $\beta$ decreases. The analysis of bilinear games confirms inherent divergence for this class of problems under Adam-DA.
• Experimental Validation:
  • Gradient Norms: Experiments on GANs show that smaller $\beta$ and larger $\rho$ consistently result in lower cumulative average gradient norms, indicating trajectories are staying in flatter regions of the loss landscape.
  • Performance: Models trained with parameter settings that yield lower gradient norms (smaller $\beta$, larger $\rho$) achieve higher Inception Scores, suggesting better generalization and training stability.
  • Negative Momentum: The experiments support the empirical observation that negative momentum (negative $\beta$) can improve GAN training stability, a phenomenon previously lacking theoretical explanation.

Significance and Claims

The paper claims to provide the first rigorous theoretical explanation for the distinct behavior of Adam in zero-sum games compared to minimization. By deriving continuous-time limits and analyzing their Jacobian structures, the authors demonstrate that the roles of momentum parameters are fundamentally inverted in game-theoretic settings.

The significance of this work lies in:

1. Bridging Theory and Practice: It explains why empirical practices in GAN training (such as using negative momentum or specific momentum ratios) succeed, where standard minimization theory fails.
2. Extending Separation Results: It extends prior theoretical separations between game dynamics and minimization dynamics—previously established for simpler methods without adaptivity or momentum—to the complex, adaptive, and momentum-based Adam algorithm.
3. Foundational Step: The authors position this deterministic analysis as a necessary first step toward a complete theory of Adam in zero-sum games, noting that while the analysis is deterministic, the findings align with stochastic experimental results in GAN training.

The paper concludes that understanding these reversed dynamics is crucial for designing better optimizers for zero-sum games and suggests future work in more complex settings, such as multi-player general-sum games.