跳转至

Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

会议: NeurIPS 2026
arXiv: 2610.19322
OpenReview: https://openreview.net/forum?id=BXzpp9Ihuq
论文: https://arxiv.org/abs/2610.19322
领域: 优化/理论
关键词: 极小极大优化, 有偏随机梯度, 算法稳定性, 泛化误差界, 最优超额风险

一句话总结

本文建立了首个面向极小极大问题有偏随机梯度法的泛化分析框架,将已有文献强依赖的全局有界梯度条件放宽至二阶矩有界假设,并在零阶与梯度截断 SGDA 上均证明了匹配无偏基准的 \(\mathcal{O}(1/\sqrt{n})\) 最优超额风险界。

研究背景与动机

极小极大优化(Minimax Optimization)是现代机器学习的核心范式之一,广泛支撑着对抗训练(Adversarial Training)、生成对抗网络(GANs)、鲁棒优化以及 AUC 最大化等关键任务。为了在大规模数据集上高效求解鞍点问题,随机梯度下降上升(SGDA)及其变体成为了标准算法。然而,理论界的大多数现有工作均假设随机梯度估计算子是严格无偏的(Unbiased),即条件期望精确恢复总体或经验梯度。但在许多真实工业级与黑盒应用中,无偏梯度要么无法获取、要么计算开销过大,研究者与工程师往往被迫采用有偏随机梯度估计(Biased Stochastic Gradients)。典型代表包括无梯度黑盒对抗攻击中的零阶估计(Zeroth-order SGDA),以及大语言模型预训练与差分隐私学习中用于抑制重尾噪声和梯度爆炸的梯度截断(Clipped-SGDA)。

尽管针对此类有偏算法在训练集上的收敛速度分析已有诸多进展,但其泛化性能(Generalization Gap)的理论研究却始终处于空白状态。极小极大优化涉及原变量最小化与对偶变量最大化的双重动态耦合,其泛化差距分析远比传统单目标最小化问题复杂。此外,现有极小极大算法稳定性文献几乎无一例外地强行要求损失函数具备全局有界梯度(即 \(G\)-Lipschitz 连续性),这一严苛假设不仅与常见的二次增长、重尾噪声或非紧紧支撑数据分布严重冲突,而且难以适配梯度截断前梯度可能无界的典型场景。

面对有偏梯度带来的系统性偏差累积以及有界梯度假设过强这两大瓶颈,本文的核心目标是打破无偏与全局 Lipschitz 限制,系统刻画有偏随机梯度估计、算法稳定性和泛化界之间的本质内在联系。核心 idea:引入代理损失函数(Surrogate Loss)解耦梯度估计偏差,将极小极大稳定性分析中的全局有界梯度条件弱化为数据依赖的二阶矩有界假设,并由此建立统一的算法参数依赖稳定性边界与 \(\mathcal{O}(1/\sqrt{n})\) 最优超额风险。

方法详解

整体框架

本文针对定义在欧氏空间紧凸子集 \(\mathcal{W} \times \mathcal{V} \subset \mathbb{R}^d \times \mathbb{R}^d\) 上的凸-凹(Convex-Concave)光滑鞍点问题 \(\min_{\mathbf{w}\in\mathcal{W}}\max_{\mathbf{v}\in\mathcal{V}} F(\mathbf{w}, \mathbf{v}) := \mathbb{E}_{z}[f(\mathbf{w},\mathbf{v};z)]\),提出了一套基于均匀引数稳定性(Uniform Argument Stability)的弱原对偶(Weak Primal-Dual)泛化分析理论框架。

整体方法流程从建立稳定性与弱原对偶泛化误差的定量转化关系出发,引入两个双边代理损失函数 \(\tilde{f}_1\) 与 \(\tilde{f}_2\) 来吸收随机梯度估计中的结构化偏差;随后提出控制梯度估计扰动、偏差漂移和代理梯度散度的广义 Lipschitz 连续型条件,导出有偏 SGDA(Biased-SGDA)的通用期望引数稳定性界;最后将该理论框架具象化实例化到零阶 SGDA 与截断 SGDA 两个经典算子中,结合优化收敛速度导出极小极大最优超额风险界。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["凸-凹极小极大问题与数据扰动邻域对<br/>S 与 S^(i) 仅相差单样本"] --> B["二阶矩有界假设下的泛化-稳定性转化<br/>放宽全局 G-Lipschitz 限制"]
    B --> C["双代理损失函数与广义偏差分解<br/>f~1, f~2 吸收原对偶估计偏置"]
    C --> D["广义 Lipschitz 扰动控制条件<br/>梯度估计扰动 A,B 与偏差漂移 A_bar,B_bar"]
    D --> E["递归收敛与步长配比稳定性界<br/>导出 ε-引数稳定性"]
    E --> F["下游特化与最优超额风险达成<br/>Zeroth-order SGDA 与 Clipped-SGDA 达到 O(1/√n)"]

关键设计

1. 弱原对偶泛化与算法稳定性的二阶矩松弛桥梁:摆脱全局梯度上界约束

在极小极大博弈中,弱原对偶总体风险定义为 \(\triangle^{w}(\mathbf{w},\mathbf{v}) = \sup_{\mathbf{v}'\in\mathcal{V}} \mathbb{E}_{\mathbf{w}}[F(\mathbf{w},\mathbf{v}')] - \inf_{\mathbf{w}'\in\mathcal{W}} \mathbb{E}_{\mathbf{v}}[F(\mathbf{w}',\mathbf{v})]\)。以往工作在建立弱原对偶泛化差距 \(\triangle^w - \triangle_S^w\) 与算法稳定性之间的不等式时,必须假设所有样本和所有参数点处的梯度范数均严格小于固定常数 \(G\)。本文发现,只要目标函数满足联合 \(L\)-光滑性(Assumption 1),即可利用柯西-施瓦茨不等式与均值不等式将原对偶梯度的内积交叉项进行分裂。对于任意算法输出以及邻近数据集替换样本 \(z_i\),利用对称性展开后,对任意调节因子 \(\gamma > 0\) 均有: $$ \mathbb{E}[f(A_{\mathbf{w}}(S^{(i)}),\mathbf{v}';z_i) - f(A_{\mathbf{w}}(S),\mathbf{v}';z_i)] \le \frac{L+\gamma}{2}\mathbb{E}[|A_{\mathbf{w}}(S^{(i)})-A_{\mathbf{w}}(S)|2^2] + \frac{1}{2\gamma}\mathbb{E}[|\nabla';z_i)|}} f(A_{\mathbf{w}}(S),\mathbf{v2^2] $$ 通过将梯度项仅约束在算法解处的期望二阶矩上界 \(\mathbb{E}_r[\|\nabla_{\mathbf{w}}f(A_{\mathbf{w}}(S),\mathbf{v};z_r)\|_2^2] \le G_{S,A}^2\),并选取平衡参数 \(\gamma = \sqrt{2\mathbb{E}[G_{S,A}^2]}/\epsilon\),成功证明了弱原对偶泛化误差满足: $$ \triangle^w(A\epsilon $$ 该设计在 }}(S),A_{\mathbf{v}}(S)) - \triangle_S^w(A_{\mathbf{w}}(S),A_{\mathbf{v}}(S)) \le \frac{L}{2}\epsilon^2 + \sqrt{2\mathbb{E}[G_{S,A}^2]\(\epsilon \lesssim 1\) 时保持了与经典 Lipschitz 条件下同阶的 \(\mathcal{O}(\sqrt{\mathbb{E}[G_{S,A}^2]}\epsilon)\) 渐进界,但在本质上兼容了无界梯度的重尾概率测度。

2. 双代理损失解耦与广义偏差定义:分离梯度扰动与系统偏置

对于任意迭代步的有偏梯度估计算子 \(g(\mathbf{w}_t,\mathbf{v}_t;z_{i_t}) = (g_{\mathbf{w}}, g_{\mathbf{v}})^\top\),其条件期望并不等于经验损失梯度 \(\nabla F_S\)。本文构造了两个可分别作用于原变量和对偶变量的平滑代理函数 \(\tilde{f}_1(\mathbf{w},\mathbf{v};z)\) 和 \(\tilde{f}_2(\mathbf{w},\mathbf{v};z)\),并定义广义偏置向量 \(b_t = (b_{t,\mathbf{w}}, b_{t,\mathbf{v}})^\top = \mathbb{E}_{i_t}[g(\mathbf{w}_t,\mathbf{v}_t;z_{i_t})] - \nabla \widetilde{F}_S(\mathbf{w}_t,\mathbf{v}_t)\)。该构造的核心价值在于:在无需实际计算代理函数显式表达的前提下,使得某些复杂有偏估计在代理函数意义下实现“条件无偏”(即 \(b_t \equiv 0\))。

在此基础上,本文提出了三组广义 Lipschitz 控制条件: - 梯度估计方差扰动界:\(\mathbb{E}\big[\frac{1}{n}\sum_{i=1}^n \|g_t^{(i)} - g_t\|_2^2\big] \le \mathbb{E}\big[\frac{A}{n}\sum_{i=1}^n \|(\mathbf{w}_t-\mathbf{w}_t^{(i)}, \mathbf{v}_t-\mathbf{v}_t^{(i)})^\top\|_2^2 + B\big]\); - 偏差变化率界:\(\mathbb{E}\big[\frac{1}{n}\sum_{i=1}^n \|b_t^{(i)} - b_t\|_2^2\big] \le \mathbb{E}\big[\frac{\bar{A}}{n}\sum_{i=1}^n \|(\mathbf{w}_t-\mathbf{w}_t^{(i)}, \mathbf{v}_t-\mathbf{v}_t^{(i)})^\top\|_2^2 + \bar{B}\big]\); - 代理函数梯度差异上界:跨样本梯度扰动满足二阶范数不超过 \(\widetilde{G}^2\)。

3. 投影单调性算子递归与通用引数稳定性推导:显式界定偏差乘数放大效应

为了推导跨步迭代的扰动累积,针对投影投影算子 \(\text{Proj}_{\mathcal{W}\times\mathcal{V}}\) 的非扩张性质(Non-expansiveness),展开第 \(t+1\) 步状态距离平方差。利用凸-凹函数梯度映射的单调性不等式 \(\langle (\mathbf{w}-\mathbf{w}', \mathbf{v}-\mathbf{v}')^\top, (\nabla_{\mathbf{w}}\tilde{f}_1-\nabla_{\mathbf{w}}'\tilde{f}_1, \nabla_{\mathbf{v}}'\tilde{f}_2-\nabla_{\mathbf{v}}\tilde{f}_2)^\top \rangle \ge 0\),可消去跨数据集更新中绝大部分同索引样本的交叉正负项,仅残留 \(1/n\) 缩放的非重叠单样本梯度差异。令 \(\bar{\Delta}_t = (\frac{1}{n}\sum_{i=1}^n \mathbb{E}[\|(\mathbf{w}_t-\mathbf{w}_t^{(i)}, \mathbf{v}_t-\mathbf{v}_t^{(i)})^\top\|_2^2])^{1/2}\),递推关系严格受控于: $$ \bar{\Delta}_{t+1}^2 \le (1 + A\eta^2 + 2\bar{A}^{1/2}\eta)\bar{\Delta}_t^2 + 2\eta\Big(\sqrt{\bar{B}} + \frac{\widetilde{G}}{n}\Big)\bar{\Delta}_t + \eta^2 B $$ 当学习率满足 \(A\eta^2 + 2\bar{A}^{1/2}\eta \le 1/T\) 时,求解最大偏差的二次代数不等式,得到算法最终的 \(\epsilon\)-引数稳定性界为 \(\mathcal{O}\big(\eta\sqrt{BT} + (\sqrt{\bar{B}} + \frac{\widetilde{G}}{n})\eta T\big)\)。该理论深刻揭示了系统偏置与方差的影响不对称性:估计方差项 \(B\) 仅按 \(\eta\sqrt{T}\) 亚线性放大,而纯系统偏差 \(\bar{B}\) 则会以 \(\eta T\) 线性放大,因此设计有偏算法时应优先最小化残余偏差 \(\bar{B}\)。

4. 算法特化与超额风险极小极大最优性证明:零阶与截断机制闭环

针对两个代表性算法,框架分别给出了关键引理支撑: - 零阶 SGDA(Zeroth-order SGDA):采用单位球面上 \(K\) 个随机方向的双点函数值差分估计原/对偶梯度,步长参数分别为 \(\mu_1, \mu_2\)。本文证明选取单位球体内的平均球平滑函数 \(\tilde{f}_1(\mathbf{w},\mathbf{v};z) = \mathbb{E}_{\mathbf{u}\sim\operatorname{Unif}(\mathbb{B}^d)}[f(\mathbf{w}+\mu_1\mathbf{u},\mathbf{v};z)]\) 作为代理函数时,零阶梯度估计恰为代理梯度的严格无偏估计,从而奇迹般地获得 \(\bar{A}=0, \bar{B}=0\)。当设置抽样方向数 \(K \asymp d\) 时,仅需步长 \(\eta \asymp 1/(L\sqrt{T})\),无需对平滑参数 \(\mu\) 施加任何阻碍训练的苛刻衰减限制,稳定性界完全恢复为与一级无偏 SGDA 完全一致的 \(\mathcal{O}(\eta\sqrt{T/n})\)。 - 截断 SGDA(Clipped-SGDA):通过设定阈值 \(\tau_1, \tau_2\) 实施矢量截断 \(\text{clip}(\mathbf{v}, \tau) = \mathbf{v}\min(1, \tau/\|\mathbf{v}\|_2)\)。在此场景下直接令 \(\tilde{f}_1 = \tilde{f}_2 = f\)。利用截断算子的非扩张性证明了当 \(\tau_1, \tau_2 \asymp L^{1/2}GT^{1/2}\) 时,偏差项 \(\bar{B}\) 衰减极快,同样导出与 SGDA 相同的 \(\mathcal{O}(G\eta T/n + G\eta\sqrt{T/n})\) 稳定性。 - 结合经验优化误差分解,在总迭代步数 \(T \asymp n\) 时,两者最终均取得了关于样本量 \(n\) 的 \(\mathcal{O}(1/\sqrt{n})\) 极小极大最优超额风险界。

实验关键数据

主实验

为了验证理论预测的有偏算法稳定性表现与泛化性能,实验在三个标准 LIBSVM 基准数据集(svmguide3, sonar, DNA)上测试了 AUC 极大化凸-凹极小极大问题(样本数 \(n\) 与维度 \(d\) 分别涵盖 21 至 180 维)。比较基线包括标准无偏 SGDA、零阶 SGDA(Zeroth-order SGDA)以及梯度截断 SGDA(Clipped-SGDA)。实验设置学习率 \(\eta_t = \eta/\sqrt{T}\),重复 25 次独立随机实验,统计平均值与标准差。

数据集 维度 \(d\) 算法配置 步长 \(\eta\) 参数稳定性距离 \(\Delta_T\) 测试集 Test AUC (%) 理论超额风险量级
svmguide3 21 标准 SGDA 0.01 0.042 ± 0.003 82.45 ± 0.42 \(\mathcal{O}(1/\sqrt{n})\)
svmguide3 21 Zeroth-order SGDA (\(K=d, \mu=10^{-4}\)) 0.01 0.048 ± 0.004 82.38 ± 0.45 \(\mathcal{O}(1/\sqrt{n})\)
svmguide3 21 Clipped-SGDA (\(\tau=0.5\)) 0.01 0.041 ± 0.003 82.51 ± 0.38 \(\mathcal{O}(1/\sqrt{n})\)
sonar 60 标准 SGDA 0.03 0.089 ± 0.007 86.12 ± 0.65 \(\mathcal{O}(1/\sqrt{n})\)
sonar 60 Zeroth-order SGDA (\(K=d, \mu=10^{-4}\)) 0.03 0.096 ± 0.008 85.95 ± 0.71 \(\mathcal{O}(1/\sqrt{n})\)
sonar 60 Clipped-SGDA (\(\tau=0.1\)) 0.03 0.087 ± 0.006 86.20 ± 0.60 \(\mathcal{O}(1/\sqrt{n})\)
DNA 180 标准 SGDA 0.05 0.135 ± 0.011 94.80 ± 0.28 \(\mathcal{O}(1/\sqrt{n})\)
DNA 180 Zeroth-order SGDA (\(K=d, \mu=10^{-4}\)) 0.05 0.148 ± 0.013 94.65 ± 0.32 \(\mathcal{O}(1/\sqrt{n})\)
DNA 180 Clipped-SGDA (\(\tau=0.1\)) 0.05 0.131 ± 0.009 94.88 ± 0.25 \(\mathcal{O}(1/\sqrt{n})\)

零阶平滑参数 \(\mu\) 与截断阈值 \(\tau\) 敏感性消融分析

理论表明:零阶算法的稳定性对平滑因子 \(\mu\) 具有免疫性,而截断算法在阈值适度时能够完美复现甚至超越经典 SGDA 的稳定性。表 2 总结了在 svmguide3 数据集上变化超参数时的稳定性距离与泛化表现(固定迭代 10 个数据 passes,\(\eta=0.01\)):

算法机制类型 调节参数设定 稳定性距离 \(\Delta_t\) 测试集 Test AUC (%) 理论一致性判定
Zeroth-order (\(\mu\) 扫描) \(\mu = 10^{-2}\) 0.049 ± 0.004 81.60 ± 0.58 \(\mu\) 过大损害优化误差,泛化轻度下降
Zeroth-order \(\mu = 10^{-3}\) 0.048 ± 0.004 82.30 ± 0.46 满足 \(\mu \lesssim \mathcal{O}(n^{-1/2})\) 准则,匹配基线
Zeroth-order \(\mu = 10^{-4}\) (默认) 0.048 ± 0.004 82.38 ± 0.45 稳定性距离对 \(\mu\) 不敏感,完美吻合 Remark 5
Zeroth-order \(\mu = 10^{-5}\) 0.047 ± 0.004 82.40 ± 0.43 极小微扰不影响引数稳定性
Clipped-SGDA (\(\tau\) 扫描) \(\tau = 0.05\) (过强截断) 0.028 ± 0.002 79.15 ± 0.85 稳定性极强但严重牺牲训练收敛
Clipped-SGDA \(\tau = 0.20\) 0.038 ± 0.003 82.10 ± 0.41 逼近最优平衡区间
Clipped-SGDA \(\tau = 0.50\) (默认推荐) 0.041 ± 0.003 82.51 ± 0.38 达到与 SGDA 相同稳定性且方差更低
Clipped-SGDA \(\tau = 2.00\) (弱截断) 0.042 ± 0.003 82.46 ± 0.40 退化为接近标准无偏 SGDA

非凸-非凹生成对抗网络(GAN)拓展检验

论文进一步在 MNIST、CIFAR-10 和 CelebA 数据集上探索了非凸-非凹鞍点问题(GAN 训练,生成器与判别器交替更新,\(\eta=0.0002\))。实验观察到:在深度神经网络场景下,Zeroth-order SGDA 与 Clipped-SGDA 的经验扰动距离曲线走势与 SGDA 维持完全一致的动态演化特征;更具启发性的是,由于深度模型梯度常呈现重尾特征,Clipped-SGDA 展现出了比无偏 SGDA 更低的经验敏感度 \(\Delta_t\),表明梯度截断在控制非凸极小极大泛化误差方面具备优良实用价值。

关键发现

  • 稳定性与无偏基准并轨:在合适的平滑半径 \(\mu\) 与截断阈值 \(\tau\) 配合下,Zeroth-order SGDA 与 Clipped-SGDA 的经验稳定性距离曲线与标准 SGDA 几乎重合,且在测试集上的弱原对偶泛化 AUC 差异在 0.1% 的置信区间内。
  • 平滑参数的解耦鲁棒性:消融实验严格印证了 Theorem 5 的预测,零阶 SGDA 的算法稳定性在上界理论和实际运行中均对平滑步长 \(\mu\) 不存在下界依赖,彻底改变了以往文献要求 \(\mu \lesssim 1/(d\sqrt{n})\) 才能保证稳定性的局限认知。
  • 深度非凸环境下的截断增益:在复杂 GAN 架构中,Clipped-SGDA 不仅没有因为梯度截断诱发稳定性劣化,反而由于截断了极端异常样本的暴增梯度,在参数空间内获得了比纯 SGDA 更加紧致的轨迹聚集度。

亮点与洞察

  • 双代理损失(Surrogate Loss)的数学构思:面对黑盒零阶导数估计所天然内生的一阶系统偏差,作者巧妙地构造出基于均匀球体扰动的原对偶双平滑代理,使得函数空间原本“有偏”的估计在代理空间中变成“无偏”,一举将偏差项 \(\bar{B}\) 彻底化为零,展现了深厚的优化分析功力。
  • 对全局 Lipschitz 假设的颠覆:以往极小极大泛化分析将 \(G\)-有界梯度作为默认公理,这不仅将二次损失排除在外,也与梯度截断的真实动因自相矛盾。本文通过结合联合 \(L\)-光滑性与自适应柯西-施瓦茨缩放,首次将假设松弛至仅在算法当前解处成立的局部二阶矩有界条件。
  • 偏差放大效应的层级分离:理论明确量化了方差型波动(以 \(\eta\sqrt{T}\) 增长)与系统偏差(以 \(\eta T\) 线性增长)在极小极大博弈迭代中的不同放大阶数,为分布式通信压缩、延迟梯度更新等其他有偏极小极大算子的设计提供了清晰的理论准绳。

局限与展望

  • 理论分析局限于凸-凹架构:主定理的核心推导高度依赖凸-凹目标函数在原对偶参数上的单调算子性质(Monotonicity)。尽管附录开展了 GAN 实验,但针对弱凸-弱凹(Weakly-Convex-Weakly-Concave)或完全非凸-非凹问题,目前尚缺少严格的闭式泛化上界。
  • 零阶方法对维度的隐式依赖:为了在零阶 SGDA 中完全匹配无偏 SGDA 的稳定性上界,理论要求随机采样方向数满足 \(K \asymp d\)。在超高维机器学习或超大模型参数微调中,单步执行 \(d\) 次函数前向评估会带来显著的额外计算开销。
  • 未来方向:作者指出可进一步将此理论拓展至去中心化分布式极小极大优化(Decentralized SGDA)、带有延迟补偿的有偏异步系统,以及利用宽神经网络的 \(\rho\)-弱凸性(\(\rho \asymp 1/\sqrt{m}\))建立神经鞍点学习的泛化理论。

相关工作与启发

  • vs Lei et al. (ICML 2021) [30]:Lei 等人首次建立了凸-凹无偏 SGDA 的均匀引数稳定性理论,但其强依赖全局 \(G\)-Lipschitz 连续性且仅能处理无偏梯度。本文在无偏特化下以局部二阶矩假设重构并恢复了其 \(\mathcal{O}(\eta\sqrt{T/n})\) 经典界,更将其拓展至普适有偏估计算子。
  • vs Zeng & Lei (JMLR 2026) [55]:Zeng 和 Lei 探讨了单目标凸优化下有偏 SGD 的稳定性与代理损失概念。本文将其系统性升维至鞍点极小极大领域,提出了原对偶非对称解耦的双代理架构,解决了最大-最小双向非平凡耦合带来的分析难点。
  • vs Farnia & Ozdaglar (ICML 2021) [18]:该工作主要分析确定性 GDA 或强凸-强凹设置下的泛化。本文则聚焦随机有偏算法,给出了无需强凸性假设下的 \(\mathcal{O}(1/\sqrt{n})\) 极小极大最优超额风险保证。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ [首个建立有偏极小极大随机梯度法泛化理论框架,双代理构造与二阶矩松弛极富数学创新]
  • 实验充分度: ⭐⭐⭐⭐☆ [覆盖经典 AUC 极小极大基准与深度 GAN 架构,消融深入,唯缺更大规模模型实测]
  • 写作质量: ⭐⭐⭐⭐⭐ [定理层层递进,从抽象偏置界到零阶/截断特化一气呵成,逻辑结构极为严谨整洁]
  • 价值: ⭐⭐⭐⭐⭐ [彻底填补了有偏鞍点算法缺乏泛化理论的长期空白,为黑盒鲁棒学习与截断优化奠定了坚实理论基石]