# The limits of min-max optimization algorithms: convergence to spurious non-critical sets

arXiv: https://arxiv.org/abs/2006.09065 · HTML: https://mlsanity.com/paper/2006.09065/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

## Built on by (most cited first, 30 of 50)

- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [A unified stochastic approximation framework for learning in games](https://mlsanity.com/paper/2206.03922/) (2022)
- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [Unifying GANs and Score-Based Diffusion as Generative Particle Models](https://mlsanity.com/paper/2305.16150/) (2023)
- [Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes](https://mlsanity.com/paper/2410.23126/) (2024)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [Provable Maximum Entropy Manifold Exploration via Diffusion Models](https://mlsanity.com/paper/2506.15385/) (2025)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [A Simple Yet Effective Strategy to Robustify the Meta Learning Paradigm](https://mlsanity.com/paper/2310.00708/) (2023)
- [On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization](https://mlsanity.com/paper/2109.14213/) (2021)
- [Neural Sinkhorn Gradient Flow](https://mlsanity.com/paper/2401.14069/) (2024)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations](https://mlsanity.com/paper/2112.13826/) (2021)
- [Riemannian stochastic optimization methods avoid strict saddle points](https://mlsanity.com/paper/2311.02374/) (2023)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [Fast Offline Policy Optimization for Large Scale Recommendation](https://mlsanity.com/paper/2208.05327/) (2022)
- [STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games](https://mlsanity.com/paper/2210.09769/) (2022)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Solving Constrained Variational Inequalities via a First-order Interior Point-based Method](https://mlsanity.com/paper/2206.10575/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Generating Less Certain Adversarial Examples Improves Robust Generalization](https://mlsanity.com/paper/2310.04539/) (2023)
- [Stable Nonconvex-Nonconcave Training via Linear Interpolation](https://mlsanity.com/paper/2310.13459/) (2023)
- [Exploiting hidden structures in non-convex games for convergence to Nash equilibrium](https://mlsanity.com/paper/2312.16609/) (2023)

## Abstract (arXiv)

Compared to ordinary function minimization problems, min-max optimization algorithms encounter far greater challenges because of the existence of periodic cycles and similar phenomena. Even though some of these behaviors can be overcome in the convex-concave regime, the general case is considerably more difficult. On that account, we take an in-depth look at a comprehensive class of state-of-the art algorithms and prevalent heuristics in non-convex / non-concave problems, and we establish the following general results: a) generically, the algorithms' limit points are contained in the ICT sets of a common, mean-field system; b) the attractors of this system also attract the algorithms in question with arbitrarily high probability; and c) all algorithms avoid the system's unstable sets with probability 1. On the surface, this provides a highly optimistic outlook for min-max algorithms; however, we show that there exist spurious attractors that do not contain any stationary points of the problem under study. In this regard, our work suggests that existing min-max algorithms may be subject to inescapable convergence failures. We complement our theoretical analysis by illustrating such attractors in simple, two-dimensional, almost bilinear problems.