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

Apr 22, 2026

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

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.

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

Ask PDF

Apr 5, 2026

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

Stochastic bilevel optimization (SBO) has been integrated into many machine learning paradigms recently, including hyperparameter optimization, meta learning, and reinforcement learning. Along with the wide range of applications, there have been numerous studies on the computational behavior of SBO. However, the generalization guarantees of SBO methods are far less understood from the lens of statistical learning theory. In this paper, we provide a systematic generalization analysis of the first-order gradient-based bilevel optimization methods. Firstly, we establish the quantitative connections between the on-average argument stability and the generalization gap of SBO methods. Then, we derive the upper bounds of on-average argument stability for single-timescale stochastic gradient descent (SGD) and two-timescale SGD, where three settings (nonconvex-nonconvex (NC-NC), convex-convex (C-C), and strongly-convex-strongly-convex (SC-SC)) are considered respectively. Experimental analysis validates our theoretical findings. Compared with the previous algorithmic stability analysis, our results do not require reinitializing the inner-level parameters at each iteration and are applicable to more general objective functions.

Xuelin Zhang, Hong Chen, Bin Gu +2

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

Stochastic Bilevel Optimization Bilevel Optimization Generalization Bounds Algorithmic Stability Stochastic Gradient Descent

Ask PDF

Jun 5, 2026

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

We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic or stochastic rounding. We show that deterministic rounding degrades the generalization error of GD on convex, Lipschitz, and smooth loss functions, increasing the rate from

O(T/n)

O(T/\sqrt{n})

, and establish matching lower bounds. We further prove that uniform stability of GD becomes

Ω(T)

, showing that stability-based generalization bounds are vacuous in this setting. In contrast, for the same losses, stochastic gradient descent with deterministic rounding admits nontrivial uniform stability guarantees, which differ qualitatively from the real-valued case and exhibit distinct dependencies on the number of iterations and the dimension: we prove tight bounds

O(T/n)

for one dimension and

O(T^2/n)

for higher dimensions. We also show that stochastic rounding can introduce generalization error that increases with the dimension; such a phenomenon is absent in standard real-valued optimization and in the deterministic rounding case. Finally, we provide upper bounds on uniform argument stability for stochastic rounding schemes and show that these bounds are tight when the loss can be represented as a sum of coordinate-wise functions.

Jonghyun Shin, Sejun Park

Department of Artificial Intelligence Korea University Seoul, Korea

Algorithmic Stability Gradient Descent Stochastic Gradient Descent Generalization Bounds

Ask PDF

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