mlsanityData to 14 Oct 2026

Stability and Generalization of Stochastic Gradient Methods for Minimax Problems

arXiv 2105.03793 ↗First posted 8 May 2021cs.LG cs.AIcited by 36

Not on the map. Why?

Abstract (arXiv)

Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs), AUC maximization and robust estimation, to mention but a few. A substantial amount of studies are devoted to studying the convergence behavior of their stochastic gradient-type algorithms. In contrast, there is relatively little work on their generalization, i.e., how the learning models built from training examples would behave on test examples. In this paper, we provide a comprehensive generalization analysis of stochastic gradient methods for minimax problems under both convex-concave and nonconvex-nonconcave cases through the lens of algorithmic stability. We establish a quantitative connection between stability and several generalization measures both in expectation and with high probability. For the convex-concave setting, our stability analysis shows that stochastic gradient descent ascent attains optimal generalization bounds for both smooth and nonsmooth minimax problems. We also establish generalization bounds for both weakly-convex-weakly-concave and gradient-dominated problems.

Key facts. Cited by 36 papers in the map (data through 14 Oct 2026). Builds on 35 of its 68 references that are in the map. First posted on arXiv 8 May 2021.

Builds on

35 of 68 references.

References · 35

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2017Empirical Analysis of the Hessian of Over-Parametrized Neural Networkscited by 290
  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. 2016Variance-based regularization with convex objectivescited by 155
  7. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  8. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  9. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  10. 2019Sharper bounds for uniformly stable algorithmscited by 93
  11. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  12. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
23 more
  1. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  2. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  3. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  4. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  5. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  6. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  7. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  8. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  9. 2013One-Pass AUC Optimizationcited by 42
  10. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 42
  11. 2017Algorithmic stability and hypothesis complexitycited by 39
  12. 2014Empirical risk minimization for heavy-tailed lossescited by 37
  13. 2017Robust Optimization for Non-Convex Objectivescited by 35
  14. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 34
  15. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  16. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  17. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  18. 2019Hypothesis Set Stability and Generalizationcited by 23
  19. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  20. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  21. 2018Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descentcited by 14
  22. 2019Stochastic Proximal AUC Maximizationcited by 14
  23. 2018Learning with Non-Convex Truncated Losses by SGDcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 11; 2023: 11; 2024: 4; 2025: 3; 2026: 6.

36 papers.

Sort:

By area:

  1. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  2. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  3. 2022Differentially Private SGDA for Minimax Problemscited by 23
  4. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  5. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  6. 2021Stable Conformal Prediction Setscited by 19
  7. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  8. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  9. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  10. 2022On the Role of Generalization in Transferability of Adversarial Examplescited by 9
  11. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 9
  12. 2022Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stabilitycited by 8
24 more
  1. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  2. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  3. 2023Continuous Invariance Learningcited by 6
  4. 2023Understanding the Generalization Ability of Deep Learning Algorithms: A Kernelized Renyi's Entropy Perspectivecited by 5
  5. 2024Stability and Generalization in Free Adversarial Trainingcited by 5
  6. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  7. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  8. 2024How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysiscited by 3
  9. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  10. 2026Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimizationcited by 3
  11. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  12. 2023On the Stability and Generalization of Triplet Learningcited by 2
  13. 2024Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometrycited by 2
  14. 2022On Stability and Generalization of Bilevel Optimization Problemcited by 1
  15. 2023Confounder Balancing in Adversarial Domain Adaptation for Pre-Trained Large Models Fine-Tuningcited by 1
  16. 2024Towards Sharper Risk Bounds for Minimax Problemscited by 1
  17. 2025Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysiscited by 1
  18. 2025Finite-sample guarantees for data-driven forward-backward operator methodscited by 1
  19. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  20. 2026Supervised Learning as Lossy Compression: Characterizing Generalization and Sample Complexity via Finite Blocklength Analysiscited by 0
  21. 2026Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysiscited by 0
  22. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimizationcited by 0
  23. 2026Stability and Generalization for Decentralized Markov SGDcited by 0
  24. 2026Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problemscited by 0