Abstract
Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
Introduction: Beyond Pure Nash Equilibria
In machine learning, many problems—most notably Generative Adversarial Networks (GANs) and robust optimization—can be framed as a zero-sum game between two players, such as a Generator and a Discriminator. While practitioners often seek a Pure Nash Equilibrium, where each player selects a single optimal strategy, such equilibria frequently do not exist in continuous, non-convex settings.
The alternative is a Mixed Nash Equilibrium (MNE), where players choose a probability distribution over strategies. Although MNEs are guaranteed to exist under broader conditions, finding them in high-dimensional spaces is computationally challenging. Traditional methods like mirror descent suffer from the "curse of dimensionality," failing as the number of parameters grows. This research introduces a scalable framework to identify mixed equilibria without requiring restrictive convexity assumptions.
Methodology: Lifting to Measure Spaces
The core proposal is to "lift" the game from the space of individual strategies to the infinite-dimensional space of probability measures. To make this tractable, measures are represented as sets of particles. The authors analyze two primary dynamics:
- Langevin Descent-Ascent (L-DA): Particle positions are updated via gradient descent-ascent with added diffusion (noise). This noise prevents particles from collapsing into suboptimal points.
- Wasserstein-Fisher-Rao (WFR) Dynamics: A key contribution of this work, WFR dynamics allow for joint updates of both particle positions and weights.
The theoretical foundation rests on a mean-field analysis. By applying a "law of large numbers" to these particles, the authors demonstrate that as the number of particles $n$ grows, the discrete system converges to a global "mean-field" flow. The Wasserstein-Fisher-Rao metric is utilized to combine the transport geometry of moving mass with the information-theoretic updates of changing mass.
Key Results and Scalability
The effectiveness of these methods was tested on synthetic polynomial games, 2D Gaussian Mixture Models (GMMs), and standard image datasets like MNIST and CIFAR-10.
A critical finding is the robustness of particle-based methods in high dimensions. While mirror descent's performance degrades rapidly as dimensionality increases, L-DA and WFR-DA maintain low Nikaidô-Isoda (NI) errors—a metric indicating proximity to a Nash Equilibrium.
In GAN training on CIFAR-10, WFR-DA led to more stable convergence and improved FID scores. By updating both generator weights and parameters, the model effectively handled complex, multi-modal data compared to single-generator baselines.
Insights: Teleportation and Specialization
The WFR approach introduces a "teleportation" effect. In standard transport (Wasserstein) flows, a strategy must move continuously through the parameter space. In WFR, a "bad" strategy can simply have its weight decreased to zero while a "good" strategy's weight increases elsewhere, effectively bypassing barriers in the loss landscape.
Furthermore, when training mixtures of GANs, different generators naturally "specialize" in different modes of the data distribution without explicit labels. This unsupervised clustering allows for better coverage of the target distribution.
Conclusion and Future Directions
This work provides a strong theoretical and empirical basis for finding mixed equilibria in high-dimensional games. While global convergence is established for Langevin dynamics, future work aims to provide quantitative convergence rates for WFR dynamics. Additionally, while the particle-based approach is effective, the computational overhead of managing large populations of neural networks remains a practical challenge for scaling to even more complex domains.
Summary updated