Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras

Introduction

The training of Generative Adversarial Networks (GANs) is fundamentally a min-max optimization problem. While standard optimization theory often focuses on convex-concave landscapes where convergence to a Nash equilibrium is well-understood, GANs operate in a far more complex non-convex non-concave regime. This complexity often manifests as training instability, mode collapse, or persistent oscillations. In their NeurIPS 2019 paper, Flokas et al. provide a rigorous theoretical framework to explain these phenomena, demonstrating that for a broad class of realistic games, standard algorithms are more likely to exhibit cyclic behavior or converge to "fake" solutions than to reach a true equilibrium.

Modeling Non-Convex Games: Hidden Bilinear Games

To bridge the gap between simple bilinear models and the high-dimensional complexity of neural networks, the authors introduce the concept of Hidden Bilinear Games. In this framework, the objective function is defined as: $$r(\theta, \phi) = F(\theta)^T U G(\phi)$$ Here, $\theta$ and $\phi$ represent the parameters of the two players (e.g., generator and discriminator). The functions $F$ and $G$ are smooth, non-linear mappings that represent the neural network architectures, while $U$ is a payoff matrix representing the underlying strategic interaction. This model captures the essence of GANs, where players do not interact directly through their weights but through the distributions (the "hidden" states) those weights produce.

Dynamics of Gradient-Descent-Ascent (GDA)

The research analyzes the dynamics of Gradient-Descent-Ascent (GDA), the standard iterative method used in GAN training. The authors examine both the continuous-time version (CGDA), modeled as a system of ordinary differential equations, and the discrete-time version (DGDA) used in practice.

By applying tools from Dynamical Systems Theory, the authors identify "constants of motion"—invariant quantities analogous to energy in physical systems. They show that in many "hidden" versions of classic games, GDA behaves like a frictionless pendulum. Instead of spiraling toward an equilibrium, the system conserves a specific "energy" function, forcing it to cycle indefinitely.

Key Insights: Recurrence and Spurious Equilibria

One of the most striking findings is the presence of Poincaré recurrence in higher-dimensional games, such as a "Hidden Rock-Paper-Scissors" setup. In these systems, the training state does not merely follow a simple loop but wanders through the parameter space in a way that eventually brings it arbitrarily close to any previously visited state.

Visualization of Poincaré recurrence in higher-dimensional hidden games.

Beyond cycles, the paper identifies the problem of spurious equilibria. Because of the non-linearity of $F$ and $G$, the gradient of the objective function can vanish at points that are not actually game-theoretic solutions. The authors prove that for a significant portion of initial conditions (a set of positive measure), GDA will converge to these non-optimal "fake" equilibria, explaining why GANs might appear to settle but fail to produce high-quality results.

The Impact of Discrete Time

The transition from continuous theory to discrete practice further exacerbates these issues. The authors prove that in discrete-time GDA, especially when using common activation functions like sigmoids, the "energy" of the system tends to increase over time. This formalizes the observation that GAN training often drifts away from stability, leading to the chaotic divergence frequently encountered by practitioners.

Conclusion

The work of Flokas et al. provides a sobering theoretical perspective on the challenges of min-max optimization in deep learning. By proving the existence of persistent cycles, Poincaré recurrence, and spurious equilibria, the paper highlights why standard GDA is often insufficient for non-convex non-concave games. These findings underscore the need for more sophisticated algorithmic approaches—such as Extra-gradient or Optimistic GDA—that are specifically designed to break these cycles and navigate the complex landscapes of modern adversarial training.

Summary updated

Abstract

We study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. This class of games is motivated by the indirect nature of the competition in Generative Adversarial Networks, where players control the parameters of a neural network while the actual competition happens between the distributions that the generator and discriminator capture. We establish theoretically, that depending on the specific instance of the problem gradient-descent-ascent dynamics can exhibit a variety of behaviors antithetical to convergence to the game theoretically meaningful min-max solution. Specifically, different forms of recurrent behavior (including periodicity and Poincar\'e recurrence) are possible as well as convergence to spurious (non-min-max) equilibria for a positive measure of initial conditions. At the technical level, our analysis combines tools from optimization theory, game theory and dynamical systems.
BibTeX
@inproceedings{flokas2019poincare,
  author = {Lampros Flokas and Emmanouil-Vasileios Vlatakis-Gkaragkounis and Georgios Piliouras},
  title = {{Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=0SHTFHgzfrW},
}
Figure