mlsanityData to 14 Oct 2026

The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization

arXiv 1807.03907 ↗First posted 11 Jul 2018math.OC cs.LG stat.MLcited by 101

Not on the map. Why?

Abstract (arXiv)

Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cycle, and there is no good understanding of their limit points when they do not. When they converge, do they converge to local min-max solutions? We characterize the limit points of two basic first order methods, namely Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA). We show that both dynamics avoid unstable critical points for almost all initializations. Moreover, for small step sizes and under mild assumptions, the set of OGDA-stable critical points is a superset of GDA-stable critical points, which is a superset of local min-max solutions (strict in some cases). The connecting thread is that the behavior of these dynamics can be studied from a dynamical systems perspective.

Key facts. Cited by 101 papers in the map (data through 14 Oct 2026). First posted on arXiv 11 Jul 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 26; 2022: 24; 2023: 14; 2024: 12; 2025: 11; 2026: 14.

101 papers.

Sort:

By area:

  1. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  2. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  3. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  4. 2021Sig-Wasserstein GANs for Time Series Generationcited by 60
  5. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  6. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  7. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  8. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  9. 2023Multi-agent Reinforcement Learning: A Comprehensive Surveycited by 33
  10. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 22
  11. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 20
  12. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
38 more
  1. 2021Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometrycited by 18
  2. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  3. 2021Understanding and Mitigating Accuracy Disparity in Regressioncited by 17
  4. 2023Identifiability and Generalizability in Constrained Inverse Reinforcement Learningcited by 16
  5. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 16
  6. 2021Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexitycited by 15
  7. 2021Discretization Drift in Two-Player Gamescited by 14
  8. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  9. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  10. 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
  11. 2022Offline Policy Evaluation and Optimization under Confoundingcited by 12
  12. 2021Learning in Matrix Games can be Arbitrarily Complexcited by 11
  13. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 11
  14. 2024ADAM-SINDy: An Efficient Optimization Framework for Parameterized Nonlinear Dynamical System Identificationcited by 11
  15. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  16. 2022Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithmcited by 9
  17. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  18. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  19. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  20. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  21. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  22. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  23. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  24. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  25. 2021Direct-Search for a Class of Stochastic Min-Max Problemscited by 7
  26. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
  27. 2021A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimizationcited by 5
  28. 2022Robust No-Regret Learning in Min-Max Stackelberg Gamescited by 5
  29. 2022Gradient descent provably escapes saddle points in the training of shallow ReLU networkscited by 5
  30. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  31. 2021Low-rank Matrix Recovery With Unknown Correspondencecited by 4
  32. 2021Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learningcited by 4
  33. 2022STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Gamescited by 4
  34. 2023Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Mapscited by 4
  35. 2023Two-timescale Extragradient for Finding Local Minimax Pointscited by 4
  36. 2024Universal randomised signatures for generative time series modellingcited by 4
  37. 2022Analysis of Dual-Based PID Controllers through Convolutional Mirror Descentcited by 3
  38. 2022Do learned representations respect causal relationships?cited by 3

50 most cited of 101 All 101 (JSON)