mlsanityData to 14 Oct 2026

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

arXiv 2205.14278 ↗First posted 28 May 2022math.OC cs.LG stat.MLcited by 7

Not on the map. Why?

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.

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

41 of 80 references.

References · 41

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 337
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  5. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  6. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  7. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  8. 2021On the Convergence and Robustness of Adversarial Trainingcited by 130
  9. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  10. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  11. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  12. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
29 more
  1. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  2. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  3. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  4. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  5. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  6. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 57
  7. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  8. 2018On the Convergence and Robustness of Training GANs with Regularized Optimal Transportcited by 51
  9. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  10. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 45
  11. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  12. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  13. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  14. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  15. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  16. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  17. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  18. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  19. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  20. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 24
  21. 2022Differentially Private SGDA for Minimax Problemscited by 23
  22. 2019Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimizationcited by 19
  23. 2018Graphical Convergence of Subgradients in Nonconvex Optimization and Learningcited by 17
  24. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  25. 2019SGD Learns One-Layer Networks in WGANscited by 16
  26. 2020A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimizationcited by 14
  27. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  28. 2022Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimizationcited by 7
  29. 2021On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correctioncited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 0; 2026: 5.

7 papers.

  1. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  2. 2024Bootstrap SGD: Algorithmic Stability and Robustnesscited by 0
  3. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  4. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0
  5. 2026Unveiling High-Probability Generalization in Decentralized SGDcited by 0
  6. 2026SIMS: Scale-Invariant Merit-Function-Based Scalarization for Multi-Task Learningcited by 0
  7. 2026Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problemscited by 0