# First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2018.

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

- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Wasserstein Convergence of Score-based Generative Models under Semiconvexity and Discontinuous Gradients](https://mlsanity.com/paper/2505.03432/) (2025)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization](https://mlsanity.com/paper/2106.16101/) (2021)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2304.02441/) (2023)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Fairness-aware Regression Robust to Adversarial Attacks](https://mlsanity.com/paper/2211.04449/) (2022)
- [AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems](https://mlsanity.com/paper/2206.12169/) (2022)
- [Asynchronous Multi-Model Dynamic Federated Learning over Wireless Networks: Theory, Modeling, and Optimization](https://mlsanity.com/paper/2305.13503/) (2023)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Games](https://mlsanity.com/paper/2210.07651/) (2022)
- [Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization](https://mlsanity.com/paper/2509.15399/) (2025)
- [An alternative approach to train neural networks using monotone variational inequality](https://mlsanity.com/paper/2202.08876/) (2022)
- [A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm](https://mlsanity.com/paper/2202.09688/) (2022)
- [Semi-Implicit Hybrid Gradient Methods with Application to Adversarial Robustness](https://mlsanity.com/paper/2202.10523/) (2022)
- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [Towards Sharper Risk Bounds for Minimax Problems](https://mlsanity.com/paper/2410.08497/) (2024)
- [A stochastic smoothing framework for nonconvex-nonconcave minEmax problems with applications to Wasserstein distributionally robust optimization](https://mlsanity.com/paper/2502.17602/) (2025)
- [A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2507.01932/) (2025)

## Abstract (arXiv)

In this paper, we consider first-order convergence theory and algorithms for solving a class of non-convex non-concave min-max saddle-point problems, whose objective function is weakly convex in the variables of minimization and weakly concave in the variables of maximization. It has many important applications in machine learning including training Generative Adversarial Nets (GANs). We propose an algorithmic framework motivated by the inexact proximal point method, where the weakly monotone variational inequality (VI) corresponding to the original min-max problem is solved through approximately solving a sequence of strongly monotone VIs constructed by adding a strongly monotone mapping to the original gradient mapping. We prove first-order convergence to a nearly stationary solution of the original min-max problem of the generic algorithmic framework and establish different rates by employing different algorithms for solving each strongly monotone VI. Experiments verify the convergence theory and also demonstrate the effectiveness of the proposed methods on training GANs.