Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

A standout element is the surrogate-loss construction for zeroth-order SGDA (Lemma 4, Section 5.2). By defining $\tilde{f}_{1},\tilde{f}_{2}$ as smoothed versions of $f$, the zeroth-order gradient becomes unbiased for the surrogate, allowing the bias term $\bar{B}$ to be set to zero in the general bound. The authors note: "the second statement shows that they are unbiased gradient estimates of the surrogate functions. Then, the bias defined in Eq. (4.5) is 0. This shows the benefit of surrogate functions in the stability analyses." (Section 5.2). Additionally, for standard SGDA the framework strictly improves on prior work: compared to Lei et al. [30], "we relax the bounded gradient assumption to the bounded second moment assumption (Assumption 2)" (Remark 3, Section 5.1), and the resulting stability bound matches the existing rate under a milder hypothesis.

The analysis is limited to convex-concave problems, whereas the motivating settings—GANs, adversarial training, and black-box robustness—are typically nonconvex. The authors concede: "As we only consider the convex-concave problem, it is interesting to extend our analysis to strongly-convex-strongly-concave ... and nonconvex-concave problems" (Section 6). A more specific concern is the Clipped-SGDA regime: to achieve optimal rates the clipping thresholds must scale as $\tau_{1},\tau_{2} \asymp L^{1/2}GT^{1/2}$ (Remark 9, Section 5.3), which grow with the number of iterations and can render clipping inactive for typical gradient norms bounded by $G$. Furthermore, the generalization gap in Theorem 1 depends on $\sqrt{\mathbb{E}[G_{S,A}^{2}]}$, a data- and algorithm-dependent constant that is interpretable for the studied methods but less transparent than a universal Lipschitz bound for general readers.

Within the convex-concave setting, the theoretical evidence supports the claims well. The bounds for zeroth-order SGDA compare favorably against prior minimization-focused results (Table 2), removing dimension-dependent requirements on the smoothing parameter $\mu$ while preserving the $O(1/\sqrt{n})$ rate. The authors fairly state that "In comparison, we relax the Lipschitzness assumption in Lei et al. [30] to the bounded second moment assumption" (Remark 3, Section 5.1). The empirical evaluation is limited but consistent: on AUC maximization with small LIBSVM datasets, stability paths of all three algorithms are "comparable" and the generalization errors align qualitatively with theory (Appendix A). However, the experiments are a sanity check on narrow linear scoring models rather than a broad empirical study.

Reproducibility is partially satisfied. The authors provide a GitHub repository link and specify public LIBSVM datasets, hyperparameters $\eta \in \{0.01,0.03,0.05\}$, and quantities such as $\mu_{1}=\mu_{2}=0.0001$ and $K=d$ for zeroth-order SGDA and chosen $\tau$ for Clipped-SGDA (Appendix A). They define the neighboring dataset by replacing the last example and measure $\Delta_{t}$ exactly as in the theoretical definition. However, the paper omits runtime, hardware, and seeding details, and verifying the generalized Lipschitz conditions (Eq. 4.6–4.8) for any new algorithm requires tedious case-by-case derivations of constants $A,\bar{A},B,\bar{B},\widetilde{G}$, which limits plug-and-play use of the framework.