mlsanityData to 7 Oct 2026

Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems

arXiv 2210.09382 ↗First posted 17 Oct 2022cs.LG math.OC stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

Despite the established convergence theory of Optimistic Gradient Descent Ascent (OGDA) and Extragradient (EG) methods for the convex-concave minimax problems, little is known about the theoretical guarantees of these methods in nonconvex settings. To bridge this gap, for the first time, this paper establishes the convergence of OGDA and EG methods under the nonconvex-strongly-concave (NC-SC) and nonconvex-concave (NC-C) settings by providing a unified analysis through the lens of single-call extra-gradient methods. We further establish lower bounds on the convergence of GDA/OGDA/EG, shedding light on the tightness of our analysis. We also conduct experiments supporting our theoretical results. We believe our results will advance the theoretical understanding of OGDA and EG methods for solving complicated nonconvex minimax real-world problems, e.g., Generative Adversarial Networks (GANs) or robust neural networks training.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 43 of its 55 references that are in the map. First posted on arXiv 17 Oct 2022.

Builds on

43 of 55 references.

References · 43

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  3. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  5. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  6. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  7. 2017Training GANs with Optimismcited by 217
  8. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  9. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  10. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  11. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  12. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
31 more
  1. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  2. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  3. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  4. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  5. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  6. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  7. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  8. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  9. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  10. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  11. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  12. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  13. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  14. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  15. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 34
  16. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  17. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  18. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  19. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  20. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  21. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  22. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  23. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  24. 2020Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learningcited by 24
  25. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  26. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  27. 2020Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Conditioncited by 19
  28. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  29. 2020An Optimal Multistage Stochastic Gradient Method for Minimax Problemscited by 12
  30. 2022On the Linear Convergence of Extra-Gradient Methods for Nonconvex-Nonconcave Minimax Problemscited by 7
  31. 2021Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learningcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 3; 2025: 1.

7 papers.

  1. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  2. 2023Two-timescale Extragradient for Finding Local Minimax Pointscited by 4
  3. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  4. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  5. 2024Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifoldcited by 1
  6. 2024Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentumcited by 1
  7. 2025Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguisecited by 1