# Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 80 references that are in the map.
- First posted on arXiv 28 May 2022.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [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)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [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)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [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)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)

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

- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Bootstrap SGD: Algorithmic Stability and Robustness](https://mlsanity.com/paper/2409.01074/) (2024)
- [Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity](https://mlsanity.com/paper/2601.19730/) (2026)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)
- [Unveiling High-Probability Generalization in Decentralized SGD](https://mlsanity.com/paper/2605.10205/) (2026)
- [SIMS: Scale-Invariant Merit-Function-Based Scalarization for Multi-Task Learning](https://mlsanity.com/paper/2609.12599/) (2026)
- [Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2610.19322/) (2026)

## Abstract (arXiv)

This paper takes an initial step to systematically investigate the generalization bounds of algorithms for solving nonconvex-(strongly)-concave (NC-SC/NC-C) stochastic minimax optimization measured by the stationarity of primal functions. We first establish algorithm-agnostic generalization bounds via uniform convergence between the empirical minimax problem and the population minimax problem. The sample complexities for achieving ε-generalization are tildeO(dkappa2ε-2) and tildeO(dε-4) for NC-SC and NC-C settings, respectively, where d is the dimension and kappa is the condition number. We further study the algorithm-dependent generalization bounds via stability arguments of algorithms. In particular, we introduce a novel stability notion for minimax problems and build a connection between generalization bounds and the stability notion. As a result, we establish algorithm-dependent generalization bounds for stochastic gradient descent ascent (SGDA) algorithm and the more general sampling-determined algorithms.