mlsanityData to 14 Oct 2026

Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

arXiv 2610.19322 ↗First posted 14 Oct 2026cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Minimax optimization refers to a class of optimization problems with some variables to minimize and other variables to maximize. Biased stochastic gradient methods have shown practical success in solving minimax problems to either improve robustness, enhance communication efficiency, or decrease computational costs. These successes motivate a lot of theoretical works to study the convergence of biased stochastic gradient methods, while their generalization analysis remains untouched. In this paper, we present the first framework to study the stability and generalization of biased stochastic gradient methods for minimax problems. We establish a connection between stability and generalization for minimax problems by relaxing the existing bounded gradient assumption to a bounded second moment condition. We then introduce a generalized Lipschitz-type condition on bias and gradient estimators, and derive a general stability bound to clarify the connection among bias, gradient estimators, and stability. We apply our general analysis to Zeroth-order and Clipped stochastic gradient descent ascent (SGDA), and derive stability bounds that match those of SGDA under appropriate smoothing/clipping parameters. We combine stability and convergence analyses together, and derive optimal excess risk bounds of order 1/√n, where n is the sample size.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 39 of its 59 references that are in the map. First posted on arXiv 14 Oct 2026.

Builds on

39 of 59 references.

References · 39

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2014Deep Learning Face Attributes in the Wildcited by 3,693
  4. 2016Deep Learning with Differential Privacycited by 2,728
  5. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  7. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  8. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  9. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  11. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  12. 2019FLAML: A Fast and Lightweight AutoML Librarycited by 106
27 more
  1. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  2. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  3. 2019Sharper bounds for uniformly stable algorithmscited by 93
  4. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  5. 2020On the Convergence of SGD with Biased Gradientscited by 83
  6. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  7. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  8. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  9. 2020Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learningcited by 47
  10. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  11. 2023A Guide Through the Zoo of Biased SGDcited by 40
  12. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  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. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  16. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 26
  17. 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 21
  18. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 14
  19. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  20. 2019On Biased Stochastic Gradient Estimationcited by 11
  21. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 11
  22. 2020Gradient-Free Methods for Saddle-Point Problemcited by 9
  23. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 9
  24. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  25. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 5
  26. 2024Regularized Gradient Clipping Provably Trains Wide and Deep Neural Networkscited by 3
  27. 2024Towards Sharper Risk Bounds for Minimax Problemscited by 1

Built on by

Not cited yet.