Complex Momentum for Learning in Games

Jonathan Lorraine, David Acuna, Paul Vicol, David Duvenaud

Abstract

We generalize gradient descent with momentum for optimization in differentiable games to have complex-valued momentum. We give theoretical motivation for our method by proving convergence on bilinear zero-sum games for simultaneous and alternating updates. Our method gives real-valued parameter updates, making it a drop-in replacement for standard optimizers. We empirically demonstrate that complex-valued momentum can improve convergence in realistic adversarial games - like generative adversarial networks - by showing we can find better solutions with an almost identical computational cost. We also show a practical generalization to a complex-valued Adam variant, which we use to train BigGAN to better inception scores on CIFAR-10.

Introduction

In standard machine learning, the goal is typically to minimize a single loss function. However, many modern paradigms—such as Generative Adversarial Networks (GANs), multi-agent reinforcement learning, and meta-learning—are structured as differentiable games where multiple players optimize distinct objectives.

Optimizing these games is notoriously difficult. Standard gradient descent with momentum often fails because games introduce "rotational dynamics." Instead of moving directly toward a Nash equilibrium, the optimizer might spiral around it or diverge entirely. While previous work suggested using "negative momentum" to combat this, it is not universally effective. There is a need for a robust, first-order optimizer that can handle the complex mixture of cooperative and adversarial dynamics found in real-world games.

Methodology: Simultaneous Complex Momentum

The authors propose Simultaneous Complex Momentum (SimCM). In classical momentum, a real-valued coefficient $\beta$ (typically $0 < \beta < 1$) determines the retention of the previous update. In Complex Momentum, $\beta$ is generalized to a complex number ($\beta \in \mathbb{C}$).

Key Technical Details

  • Complex Buffer: The momentum buffer $\mu$ becomes complex-valued.
  • Real Updates: To maintain real-valued model parameters, the update rule utilizes only the real part of the complex momentum buffer: $\omega^{j+1} = \omega^j + \text{Re}(\alpha \mu^{j+1})$.
  • Recurrent Linking: Conceptually, this is equivalent to having two real-valued momentum buffers that are "recurrently linked," passing information back and forth.
Evolution from classical momentum to complex momentum. (a) Classical momentum, (b) Aggregated momentum, (c) Recurrently linked buffers, and (d) the proposed Complex Momentum which uses linked buffers representing real and imaginary parts.

This approach is a direct generalization: setting the imaginary part of $\beta$ to zero recovers standard momentum, while a negative real $\beta$ yields negative momentum.

Experimental Evaluation

The method was evaluated across several benchmarks, including bilinear zero-sum games, Dirac-GAN, and a 2D Mixture of Gaussians. To demonstrate practical scalability, the authors trained a large-scale BigGAN model on CIFAR-10.

Key Results

  • Convergence Proofs: The authors provide the first proof of convergence for a momentum method on bilinear zero-sum games using simultaneous updates.
  • BigGAN Improvement: Replacing the standard Adam optimizer with a "Complex Adam" variant improved the Inception Score (IS) on CIFAR-10 from 9.10 to 9.25.
  • Efficiency: The computational cost is nearly identical to standard momentum. While it doubles the memory for the momentum buffer (storing real and imaginary parts), the number of gradient evaluations remains unchanged.

Discussion and Key Insights

  • Oscillation as a Feature: Standard momentum only accumulates gradients. Complex momentum allows the optimizer to oscillate between adding and subtracting historical gradient information at a frequency dictated by the phase of the complex coefficient. This oscillation can cancel out the rotations inherent in adversarial games.
  • Spectral Alignment: Optimal momentum should "match" the eigenvalues of the game's Jacobian. Since games often have complex eigenvalues (representing rotation), a complex-valued optimizer is a more natural fit.
  • Robustness: Real games like GANs are a mix of cooperative and adversarial dynamics. Complex momentum is robust across this spectrum, whereas methods like Extragradient (EG) or Optimistic Gradient (OG) can struggle when the game becomes "too cooperative" or "too adversarial."

Conclusion

Complex Momentum offers a theoretically grounded and practically efficient way to stabilize optimization in differentiable games. By introducing complex-valued coefficients, it effectively manages the rotational dynamics that plague standard optimizers in adversarial settings. Its ease of implementation and minimal computational overhead make it a promising drop-in replacement for standard momentum-based optimizers in complex multi-agent scenarios.

Summary updated

Abstract

We generalize gradient descent with momentum for optimization in differentiable games to have complex-valued momentum. We give theoretical motivation for our method by proving convergence on bilinear zero-sum games for simultaneous and alternating updates. Our method gives real-valued parameter updates, making it a drop-in replacement for standard optimizers. We empirically demonstrate that complex-valued momentum can improve convergence in realistic adversarial games - like generative adversarial networks - by showing we can find better solutions with an almost identical computational cost. We also show a practical generalization to a complex-valued Adam variant, which we use to train BigGAN to better inception scores on CIFAR-10.
BibTeX
@inproceedings{lorraine2022complex,
  author = {Jonathan Lorraine and David Acuna and Paul Vicol and David Duvenaud},
  title = {{Complex Momentum for Learning in Games}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=_Zalktn44Z},
}
Figure