Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problems

Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames

Abstract

This paper studies properties of fixed points of generalised Extra-gradient (GEG) algorithms applied to min-max problems. We discuss connections between saddle points of the objective function of the min-max problem and GEG fixed points. We show that, under appropriate step-size selections, the set of saddle points (Nash equilibria) is a subset of stable fixed points of GEG. Convergence properties of the GEG algorithm are obtained through a stability analysis of a discrete-time dynamical system. The results and benefits when compared to existing methods are illustrated through numerical examples.

Introduction

Min-max optimization is fundamental to modern machine learning, particularly in training Generative Adversarial Networks (GANs) and multi-agent reinforcement learning. Standard Gradient Descent-Ascent (GDA) often fails in these settings, leading to oscillations or divergence. While Extra Gradient (EG) methods introduce a "lookahead" step to stabilize updates, the theoretical link between their fixed points and the objective function's saddle points has been fragmented. This work provides a unified framework, the Generalised Extra Gradient (GEG) algorithm, to analyze these relationships through the lens of discrete-time dynamical systems.

Methodology

The GEG algorithm generalizes several extragradient variants by employing four step-sizes ($h_{1x}, h_{2x}, h_{1y}, h_{2y}$), which are simplified into two primary parameters:

  • $\gamma$ (Gamma): The ratio between the "extra" step and the main update step.
  • $\tau$ (Tau): The ratio between the step-sizes of the two players (the timescale separation).

By adjusting these parameters, GEG can recover standard EG, two-timescale EG ($\tau$-EG), and EG+. The analysis treats the GEG update as a discrete-time map $z_{k+1} = w(z_k)$. Stability is determined by the Jacobian of this map at critical points. The authors prove that GEG is a local diffeomorphism, allowing the use of the Stable Manifold Theorem to show that the algorithm almost never converges to unstable points.

Key Insights and Results

A central finding is that GEG provides a unified mathematical "umbrella" for extragradient methods. The authors prove that with correct parameter selection ($\gamma, \tau$), every strict saddle point of the objective function becomes an asymptotically stable fixed point of the GEG algorithm. Crucially, GEG avoids "fake" solutions—unstable fixed points that are not saddle points—for almost all initializations.

Stability and Convergence

Theorems in the paper provide explicit bounds on step-sizes to ensure convergence. For instance, in cases with real eigenvalues, $\gamma < 8$ can be sufficient for stability. Empirical validation on a non-convex/non-concave function with eight critical points demonstrates that GEG correctly identifies local Nash equilibria while avoiding other critical points like local maxima or minima for a single player.

Phase plot showing regions of attraction for stable fixed points (Nash equilibria) and avoidance of unstable fixed points.

The following table details the stability of various critical points under the GEG framework, highlighting how it distinguishes between saddle points and other equilibria.

Classification of critical points and their stability under the GEG algorithm.

Scalability

The algorithm was also tested on the Wisconsin Breast Cancer Dataset using a neural network with over 1600 parameters. GEG demonstrated smooth convergence of the gradient norm toward zero, suggesting its applicability to high-dimensional, real-world problems.

Conclusion

The GEG framework offers a robust theoretical foundation for min-max optimization. While the current analysis is primarily local, it establishes that saddle points are stable attractors and that unstable points are avoided. Future work may tighten the sufficient step-size bounds and explore the global convergence properties in highly non-convex landscapes.

Summary updated

Abstract

This paper studies properties of fixed points of generalised Extra-gradient (GEG) algorithms applied to min-max problems. We discuss connections between saddle points of the objective function of the min-max problem and GEG fixed points. We show that, under appropriate step-size selections, the set of saddle points (Nash equilibria) is a subset of stable fixed points of GEG. Convergence properties of the GEG algorithm are obtained through a stability analysis of a discrete-time dynamical system. The results and benefits when compared to existing methods are illustrated through numerical examples.
BibTeX
@article{farzin2025properties,
  author = {Amir Ali Farzin and Yuen-Man Pun and Philipp Braun and Iman Shames},
  title = {{Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problems}},
  journal = {IEEE Control. Syst. Lett},
  year = {2025},
  doi = {10.1109/lcsys.2025.3572068},
}
Figure