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.
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