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

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

## Key facts

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

## Builds on (most cited first, 30 of 43)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [A Decentralized Parallel Algorithm for Training Generative Adversarial Nets](https://mlsanity.com/paper/1910.12999/) (2019)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Stochastic Hamiltonian Gradient Methods for Smooth Games](https://mlsanity.com/paper/2007.04202/) (2020)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)

## Built on by (most cited first, 7 of 7)

- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Two-timescale Extragradient for Finding Local Minimax Points](https://mlsanity.com/paper/2305.16242/) (2023)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum](https://mlsanity.com/paper/2406.13041/) (2024)
- [Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold](https://mlsanity.com/paper/2405.13392/) (2024)
- [Dual Optimistic Ascent (PI Control) is the Augmented Lagrangian Method in Disguise](https://mlsanity.com/paper/2509.22500/) (2025)

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