Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

Shuang Zeng; Yunwen Lei; Yiming Ying

cs.AIOct 14, 2026

Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

Authors: Shuang Zeng, Yunwen Lei, Yiming Ying

Organizations: Department of Mathematics, The University of Hong Kong, Hong Kong, China · School of Mathematics and Statistics, The University of Sydney, Sydney, Australia

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.

Figures & tables

Algorithm	Reference	Step size	Iteration number	Excess risk bound
Zeroth-order SGDA	Remark 7	$\eta\asymp 1/(L\sqrt{T})$	$T\asymp n$	$\frac{\mathbb{E}[G_{S}^{2}]/L+LR^{2}}{\sqrt{n}}$
Clipped-SGDA	Remark 9	$\eta\asymp 1/(L\sqrt{T})$	$T\asymp n$	$\frac{G^{2}/L+LR^{2}+G^{2}/L^{2}}{\sqrt{n}}$

Table 1: Excess risk bounds of Zeroth-order SGDA and Clipped-SGDA for convex-concave and smooth problems. For brevity, we assume

\eta_{t}=\eta

and indicate the dependency on

n,L,G,R

. For Zeroth-order SGDA, we take

K\asymp d

and a sufficiently small

\mu

, i.e.,

\mu=(\mu_{1}^{2}+\mu_{2}^{2})^{\frac{1}{2}}\lesssim\frac{\sqrt{\mathbb{E}[G_{S}^{2}]}}{L\sqrt{n}}

. We take

\tau_{1},\tau_{2}\asymp L^{\frac{1}{2}}GT^{\frac{1}{2}}

for Clipped-SGDA under Assumption 3 with

G_{S}\leq G

for some

G>0

Analysis	$\boldsymbol{\eta}$	$\boldsymbol{\mu}$	Assumption	Bounds
Stability in [ 41 ]	$O(\frac{1}{t})$	$O(\frac{1}{d^{3/2}n})$	$L,G$	$O(\frac{T}{n})$
Stability in [ 34 ]	$O(\frac{1}{t})$	$O(\frac{1}{dn})$	$L,G$	$O(\frac{T}{n})$
Stability in [ 55 ]	$O(\frac{1}{\sqrt{T}})$	$O(\frac{1}{d\sqrt{n}})$	$L$	$O(\frac{(1+\sqrt{d/K})\eta\sqrt{T}}{\sqrt{n}}+\frac{\eta T}{n})$
Our stability	$O(\frac{1}{\sqrt{T}})$	No requirement	$L,G_{S}$	$O(\frac{(1+\sqrt{d/K})\eta\sqrt{T}}{\sqrt{n}}+\frac{\eta T}{n})$

Table 2: Stability Analysis for Zeroth-order Methods,

G

denotes the bounded gradient assumption and

G_{S}

denotes the bounded second moment assumption (Assumption 3 ),

L

denotes the smootheness assumption ( Nikolakakis et al. [41] , Liu et al. [34] , Zeng and Lei [55] consider Zeroth-order SGD). We ignore all the factors independent of

d,K,n,T,\eta

Analysis	$\boldsymbol{\eta}$	$\boldsymbol{\mu}$	Assumption	Bounds
Excess risk in [ 55 ]	$O\left(\frac{\sqrt{K/d}}{\sqrt{n}}\right)$	$O(\frac{1}{d\sqrt{n}})$	$L$	$O(n^{-1/2})$
Our excess risk bound	$O\left(\frac{\sqrt{K/d}}{\sqrt{n}}\right)$	$O(\frac{1}{\sqrt{n}})$	$L,G_{S}$	$O(n^{-1/2})$

Table 3: Excess Risk Analysis for Zeroth-order Methods,

G_{S}

denotes the bounded second moment assumption, and

L

denotes the smootheness assumption ( Zeng and Lei [55] consider Zeroth-order SGD).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: $\Delta_{t}$ versus the number of passes for different datasets ( svmguide3 , sonar , DNA ) and $\eta\in\{0.01,0.03,0.05\}$ .

Panel of Figure 2 — Figure 2: Test AUC versus # of passes for different datasets ( svmguide3 , sonar , dna ) and $\eta\in\{0.01,0.03,0.05\}$ .

Panel of Figure 3 — Figure 3: $\Delta_{t}$ versus # of passes. Left: generator, right: discriminator. $\eta=0.0002$ , $K=300$ , $\mu_{1}=\mu_{2}=0.0001,\tau_{1}=\tau_{2}=1$ .

Panel of Figure 4 — Figure 4: Parameter sensitivity of Zeroth-order SGDA w.r.t. the smoothing parameter $\mu$ on svmguide3 : (a) $\Delta_{t}$ versus # of passes; (b) Test AUC versus # of passes. $\eta=0.01$ .

Panel of Figure 5 — Figure 5: Parameter sensitivity of Clipped-SGDA w.r.t. the clipping threshold $\tau$ on svmguide3 : (a) $\Delta_{t}$ versus # of passes; (b) Test AUC versus # of passes. $\eta=0.01$ .

Min-Max Optimization

Min-max optimization studies algorithms for objectives where one decision-maker minimizes loss while an adversary or opponent maximizes it.

See all 38 papers

On the Stability and Generalization of First-order Bilevel Minimax Optimization
Apr 22, 2026Xuelin Zhang, Peipei YuanMin-Max Optimization Bilevel Optimization
College of Informatics, Huazhong Agricultural University, Wuhan, 430070, China · School of Artificial Intelligence, Jianghan University, Wuhan, 430056, China
Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization
Apr 5, 2026Xuelin Zhang, Hong Chen, Bin Gu +2Stochastic Bilevel Optimization Bilevel Optimization
College of Informatics, Huazhong Agricultural University, Wuhan 430070, China · Engineering Research Center of Intelligent Technology for Agriculture, Ministry of Education, Wuhan 430070, China · School of Artificial Intelligence, Jilin University, Jilin 130012, China +2
Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters
Jun 5, 2026Jonghyun Shin, Sejun ParkAlgorithmic Stability Gradient Descent
Department of Artificial Intelligence Korea University Seoul, Korea

Apr 22, 2026J/K move · Enter open · S save

On the Stability and Generalization of First-order Bilevel Minimax Optimization

Xuelin Zhang, Peipei Yuan

College of Informatics, Huazhong Agricultural University, Wuhan, 430070, China · School of Artificial Intelligence, Jianghan University, Wuhan, 430056, China

Min-Max Optimization Bilevel Optimization Stochastic Gradient Descent Generalization Bounds Stochastic Bilevel Optimization Algorithmic Generalization

Open paper AskPDF arXiv

Bilevel optimization and bilevel minimax optimization have recently emerged as unifying frameworks for a range of machine-learning tasks, including hyperparameter optimization and reinforcement learning. The existing literature focuses on empirical efficiency and convergence guarantees, leaving a critical theoretical gap in understanding how well these algorithms generalize. To bridge this gap, we provide the first systematic generalization analysis for first-order gradient-based bilevel minimax solvers with lower-level minimax problems. Specifically, by leveraging algorithmic stability arguments, we derive fine-grained generalization bounds for three representative algorithms, including single-timescale stochastic gradient descent-ascent, and two variants of two-timescale stochastic gradient descent-ascent. Our results reveal a precise trade-off among algorithmic stability, generalization gaps, and practical settings. Furthermore, extensive empirical evaluations corroborate our theoretical insights on realistic optimization tasks with bilevel minimax structures.

Abstract

Min-Max Optimization

Explore similar work

On the Stability and Generalization of First-order Bilevel Minimax Optimization

Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization

Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters