A note on large deviations for interacting particle dynamics for finding mixed equilibria in zero-sum games

Viktor Nilsson, Pierre Nyquist

Viktor Nilsson and Pierre Nyquist

Abstract

Finding equilibria points in continuous minimax games has become a key problem within machine learning, in part due to its connection to the training of generative adversarial networks. Because of existence and robustness issues, recent developments have shifted from pure equilibria to focusing on mixed equilibria points. In this note we consider a method proposed by Domingo-Enrich et al. for finding mixed equilibria in two-layer zero-sum games. The method is based on entropic regularisation and the two competing strategies are represented by two sets of interacting particles. We show that the sequence of empirical measures of the particle system satisfies a large deviation principle as the number of particles grows to infinity, and how this implies convergence of the empirical measure and the associated Nikaidô-Isoda error, complementing existing law of large numbers results.

Introduction

In the landscape of modern machine learning, many optimization problems are framed as zero-sum games, most notably in the training of Generative Adversarial Networks (GANs). In these settings, a generator and a discriminator compete to reach a Nash equilibrium. However, in non-convex-concave scenarios, a "pure" Nash equilibrium—where each player chooses a single optimal strategy—often does not exist or is computationally intractable to find.

To address this, researchers have shifted focus toward Mixed Nash Equilibria (MNE), where players choose from a probability distribution of strategies. A common approach to finding MNEs involves using interacting particle systems, where two populations of particles (representing the strategies of the two players) evolve according to Langevin-style dynamics. While the Law of Large Numbers (LLN) ensures these systems converge to the correct distribution as the number of particles ($n$) approaches infinity, the nature of their fluctuations and the likelihood of "rare event" deviations have remained poorly understood. This paper establishes a Large Deviation Principle (LDP) to provide a rigorous mathematical framework for these dynamics.

The Particle System and Entropic Regularization

The authors analyze a system of $2n$ coupled Stochastic Differential Equations (SDEs). These equations represent the strategies of two competing players, smoothed via entropic regularization. By adding a controlled amount of noise to the gradient descent-ascent process, the system is better equipped to explore the strategy space and converge toward mixed equilibria.

As $n$ grows, the empirical measures of these particles are expected to follow a mean-field limit. The core contribution of this work is quantifying the rate at which the empirical measure of the $n$-particle system converges to this limit, specifically by identifying the probability that the system deviates significantly from its expected path.

Establishing the Large Deviation Principle

Using a sophisticated framework for weakly interacting particle systems (building on the work of Budhiraja et al., 2012), the authors prove that the sequence of empirical measures satisfies an LDP.

The Rate Function

A central component of this proof is the derivation of a rate function, $J$. In Large Deviation Theory, the rate function acts as a "cost" for deviations: the higher the value of $J$ for a particular trajectory, the less likely the system is to follow that path. The authors demonstrate that the "zero-cost" path—the trajectory where $J=0$—corresponds exactly to the entropy-regularized gradient flow. This confirms that the most probable behavior of the particle system is indeed the intended gradient flow used in optimization.

Convergence of the Nikaidô-Isoda Error

To make these results applicable to game theory, the authors apply the contraction principle to translate the LDP of particle positions into an LDP for the Nikaidô-Isoda (NI) error. The NI error is a standard metric used to measure how far a pair of strategies is from a true Nash equilibrium.

By proving an LDP for the NI error, the paper establishes that the probability of the particle system failing to approximate the equilibrium (i.e., maintaining a large NI error) decays exponentially as the number of particles increases. This provides a powerful theoretical guarantee for the robustness and reliability of particle-based training methods in GANs.

Key Theoretical Results

  1. Theorem 3.2 (Core LDP): Formally proves that the empirical measures satisfy an LDP with rate function $J$. This provides the foundation for analyzing stochastic fluctuations in the system.
  2. Corollary 3.3 (LLN Recovery): Shows that the Law of Large Numbers is a natural consequence of the LDP, ensuring almost sure convergence to the mean-field equations.
  3. Proposition 3.4 & Corollary 3.5: These results establish that the NI error converges to zero almost surely and satisfies its own LDP, quantifying the exponential disappearance of error in the large-population limit.

Limitations and Future Directions

While this work provides a rigorous foundation, it relies on certain regularity assumptions. Specifically, the loss function $l$ and its gradient $ abla l$ are assumed to be bounded and Lipschitz continuous. In practice, deep learning loss surfaces can be significantly more complex and non-smooth, suggesting a need for future proofs that relax these conditions.

Additionally, while the current work focuses on Euclidean space, the authors suggest that extending these results to Riemannian manifolds or more complex dynamics—such as Wasserstein-Fisher-Rao dynamics—could offer deeper insights into the performance of modern optimization algorithms like mirror descent. This note serves as a critical step in using statistical mechanics to provide convergence guarantees for the competitive dynamics inherent in artificial intelligence.

Summary updated

Abstract

Finding equilibria points in continuous minimax games has become a key problem within machine learning, in part due to its connection to the training of generative adversarial networks. Because of existence and robustness issues, recent developments have shifted from pure equilibria to focusing on mixed equilibria points. In this note we consider a method proposed by Domingo-Enrich et al. for finding mixed equilibria in two-layer zero-sum games. The method is based on entropic regularisation and the two competing strategies are represented by two sets of interacting particles. We show that the sequence of empirical measures of the particle system satisfies a large deviation principle as the number of particles grows to infinity, and how this implies convergence of the empirical measure and the associated Nikaid\^o-Isoda error, complementing existing law of large numbers results.
BibTeX
@misc{nilsson2022note,
  author = {Viktor Nilsson and Pierre Nyquist},
  title = {{A note on large deviations for interacting particle dynamics for finding mixed equilibria in zero-sum games}},
  year = {2022},
  eprint = {2206.15177},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.15177},
}
Figure