aiqbench analysis
This is a theoretical paper on how well biased stochastic gradient methods generalize for minimax problems, a setting that underlies GAN training and adversarial learning. It extends stability-based generalization analysis to relax bounded-gradient assumptions and applies the framework to zeroth-order and clipped SGDA, yielding excess risk bounds of order 1/√n. For practitioners, the value is in clarifying when biased or cheaper gradient estimators (for robustness, communication, or compute savings) don't sacrifice generalization, though the results remain analytical and untested at scale.
Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems
arXiv:2610.19322v1 Announce Type: new Abstract: 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/\sqrt{n}$, where $n$ is the sample size.
Abstract: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/\sqrt{n}$, where $n$ is the sample size.
Artificial Intelligence (cs.AI)
arXiv:2610.19322 [cs.AI]
(or arXiv:2610.19322v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2610.19322 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 282 words
Related coverage
Exploding variance of means of exponentials: least-squares to the rescue – Machine Learning Research Blog
francisbach.com · Sep 27, 2026
Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks
arXiv · Jun 8, 2026
PIRAMID: Progress and Plans
LessWrong · Jul 27, 2026
Expenditure Horizon: Measuring Optimization Ability, with an Application to NanoGPT
METR · Jul 21, 2026