Research map / Optimization / Nonconvex and smooth optimization

Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic gradient last-iterate analysis

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Develops a stability-based generalization framework for biased stochastic gradient descent-ascent on convex-concave minimax problems, applied to zeroth-order and clipped SGDA, yielding O(1/√n) excess risk bounds under a bounded second-moment assumption.

Problem

Generalization of biased stochastic gradient methods (zeroth-order SGDA and clipped SGDA) for convex-concave minimax learning, which prior work analyzed only for optimization, not generalization.

Approach

Connects argument stability to the weak primal-dual generalization gap under a bounded second-moment condition instead of bounded gradients, and introduces generalized Lipschitz-type conditions on bias and gradient estimators via surrogate losses, giving a general stability bound for biased SGDA.

Key results

• Zeroth-order SGDA and Clipped-SGDA achieve stability bounds of the same order as SGDA under mild smoothing/clipping parameter conditions (e.g., K ≍ d, τ ≳ G T^{1/4}).
• Excess risk bounds of order O(1/√n) are derived for projected Zeroth-order SGDA and Clipped-SGDA on convex-concave smooth problems with T ≍ n and η ≍ 1/(L√T).
• Experiments on AUC maximization show Δt and generalization error of SGDA, Zeroth-order SGDA, and Clipped-SGDA are comparable across three datasets.

Surprising findings

• On GAN experiments, Clipped-SGDA showed smaller stability (Δt) than SGDA, contrary to the expectation that the methods are comparable.

Limitations

• Analysis restricted to convex-concave smooth problems; nonconvex settings left to future work.
• Stability bounds for zeroth-order and clipped methods require conditions on smoothing/clipping parameters and step sizes (e.g., L^2 η^2 constraints).
• Experiments are limited to small AUC maximization datasets and a single GAN setting, with no evaluation at scale.

Experimental setup

Datasets: svmguide3 sonar DNA MNIST CIFAR-10 CelebA

Benchmarks: svmguide3 sonar DNA MNIST CIFAR-10 CelebA

Metrics: argument stability (Euclidean distance between models on nei test AUC generalization gap

Baselines: SGDA Zeroth-order SGDA Clipped-SGDA

Builds on: Lei et al. SGDA generalization analysis Hardt et al. stability of SGD Zeng and Lei biased SGD stability with surrogate loss Shalev-Shwartz smoothing

Closest papers by meaning

• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems (ICML 2021 · similarity 0.93)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods (NeurIPS 2022 · similarity 0.93)
• Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.91)
• High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.91)
• Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.90)
• Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations (ICML 2024 · similarity 0.89)