关于固定点参数下GD和SGD的一致稳定性与泛化误差

# 固定点参数上梯度和随机梯度下降的均匀稳定性与泛化误差

来源：https://arxiv.org/html/2606.06934

Jonghyun Shin  
人工智能系  
高丽大学  
首尔，韩国  
uenjgieonj5448@korea\.ac\.kr

&

Sejun Park  
人工智能系  
高丽大学  
首尔，韩国  
sejun\.park000@gmail\.com

###### 摘要

我们分析了在离散参数空间中，梯度下降（GD）和随机梯度下降（SGD）的泛化误差、均匀稳定性以及均匀参数稳定性，其中每次更新涉及确定性或随机舍入。我们证明，对于凸、Lipschitz 且光滑的损失函数，确定性舍入会恶化 GD 的泛化误差，将其率从 \(O(T/n)\) 提高到 \(O(T/\sqrt{n})\)，并建立了匹配的下界。我们进一步证明了 GD 的均匀稳定性为 \(\Omega(T)\)，表明在此设置下基于稳定性的泛化界是无效的。相反，对于相同的损失，带有确定性舍入的随机梯度下降具有非平凡的均匀稳定性保证，这与实值情况有本质区别，并且在迭代次数和维度上表现出不同的依赖关系：我们证明了一维情况的紧界为 \(O(T/n)\)，而更高维度的紧界为 \(O(T^2/n)\)。我们还表明，随机舍入会引入随维度增加的泛化误差；这种现象在标准的实值优化以及确定性舍入情况下都不存在。最后，我们给出了随机舍入方案的均匀参数稳定性上界，并证明了当损失可以表示为坐标方向函数之和时，这些界是紧的。

## 1 引言

基于梯度的优化算法是现代机器学习的支柱，广泛应用于从线性预测器到深度神经网络的模型训练。从经典的梯度下降（GD）和随机梯度下降（SGD）开始，已经发展出许多变体，以改善大规模和非凸设置下的收敛速度和鲁棒性（Duchi 等人，2011（https://arxiv.org/html/2606.06934#bib.bib27）；Tieleman 和 Hinton，2012（https://arxiv.org/html/2606.06934#bib.bib30）；Kingma 和 Ba，2015（https://arxiv.org/html/2606.06934#bib.bib28）；Liu 等人，2025（https://arxiv.org/html/2606.06934#bib.bib29））。这些算法已被广泛研究，具有丰富的理论来描述它们在各种假设下的收敛行为（Bottou 等人，2018（https://arxiv.org/html/2606.06934#bib.bib34）；Reddi 等人，2018（https://arxiv.org/html/2606.06934#bib.bib35）；Zhou 等人，2024（https://arxiv.org/html/2606.06934#bib.bib36）），以及它们在统计学习框架中的泛化性能（Hardt 等人，2016（https://arxiv.org/html/2606.06934#bib.bib4）；Bassily 等人，2020（https://arxiv.org/html/2606.06934#bib.bib2）；Zhou 等人，2020（https://arxiv.org/html/2606.06934#bib.bib38）；Nguyen 等人，2022（https://arxiv.org/html/2606.06934#bib.bib37））。然而，大多数现有分析依赖于一个理想化的设置，其中优化变量位于连续空间，并且所有算术运算都精确执行。在实践中，优化算法是在数字硬件上实现的，使用离散参数，例如定点或浮点表示（Goldberg，1991（https://arxiv.org/html/2606.06934#bib.bib33）；Gupta 等人，2015（https://arxiv.org/html/2606.06934#bib.bib1））。在这种设置下，参数空间本质上是离散的，并且每次算术运算都会产生舍入误差。因此，优化动态可能与其实值对应情况根本不同：更新被量化，数值误差随时间累积。最近的工作已经开始通过建立收敛性保证来研究离散或量化设置下基于梯度的方法（Markov 等人，2023（https://arxiv.org/html/2606.06934#bib.bib10）；Xin 等人，2025（https://arxiv.org/html/2606.06934#bib.bib11）；Xia 等人，2025（https://arxiv.org/html/2606.06934#bib.bib22））。尽管如此，关于离散参数如何影响泛化的理论理解仍然有限。

除了收敛性，理解优化算法的泛化性质是统计学习理论中的一个核心问题。基于一致收敛的经典方法提供了对假设类上经验风险与总体风险之间差距的界。然而，这类界通常依赖于环境维度（Shalev-Shwartz 和 Ben-David，2014（https://arxiv.org/html/2606.06934#bib.bib31）；Feldman，2016（https://arxiv.org/html/2606.06934#bib.bib32）），并且与所使用的具体优化算法无关，通常导致在现代高维设置中过于悲观的界。这一局限性促使了*依赖于算法*的分析，它考虑了优化过程的动态。这方面的一个经典框架是*算法稳定性*（Bousquet 和 Elisseeff，2002（https://arxiv.org/html/2606.06934#bib.bib7）；Shalev-Shwartz 等人，2010（https://arxiv.org/html/2606.06934#bib.bib9））。在该框架中，学习算法 \(A\) 将数据集 \(S=(z_1,\dots,z_n)\) 映射到参数向量 \(A(S)\)，并且泛化误差由 \(A(S)\) 对数据集微小扰动的敏感性来界定。特别是，*均匀稳定性* 衡量当单个训练样本被替换时损失的变化程度，而*均匀参数稳定性* 衡量在这种扰动下学习到的参数本身的变化程度。当损失函数是 Lipschitz 时，这两个概念直接相关，允许通过跟踪扰动在优化动态中的传播来界定泛化误差。这个框架对于基于梯度的方法特别成功，为 GD 和 SGD 提供了与维度无关的泛化保证（Hardt 等人，2016（https://arxiv.org/html/2606.06934#bib.bib4）；Chen 等人，2018（https://arxiv.org/html/2606.06934#bib.bib6）；Bassily 等人，2020（https://arxiv.org/html/2606.06934#bib.bib2））。

### 1.1 我们的贡献

在本文中，我们在定点参数下重新审视这个框架。具体来说，我们考虑在离散参数空间 \(\{\Delta x : x \in \mathbb{Z}\}^d\) 上进行基于梯度的优化，其中每次更新涉及确定性或随机舍入。在此设置下，我们分析了当损失函数是凸、Lipschitz 且光滑时，有限精度效应如何影响基于梯度的优化算法的泛化误差、均匀稳定性和均匀参数稳定性¹¹ 泛化误差 \(\leq\) 均匀稳定性 \(\leq\) Lipschitz常数 \(\times\) 均匀参数稳定性（见第 2.4 节（https://arxiv.org/html/2606.06934#S2.SS4））。。我们证明，机器算术的离散和不精确性质从根本上改变了这些稳定性度量的行为，导致与经典实值设置相比具有质的不同的泛化保证。特别是，我们的贡献可以总结如下（另见表 1（https://arxiv.org/html/2606.06934#S1.T1））。这里，\(\mathsf{DR}\text{\rm{-GD}}\)、\(\mathsf{SR}\text{\rm{-GD}}\)、\(\mathsf{DR}\text{\rm{-SGD}}\) 和 \(\mathsf{SR}\text{\rm{-SGD}}\) 分别表示在 \(\{\Delta x : x \in \mathbb{Z}\}^d\) 上采用确定性/随机舍入的（随机）梯度下降，而 GD 和 SGD 表示标准（随机）梯度下降（无舍入操作）。此外，为了简洁表示，我们隐藏了 Lipschitz 常数和 \(\Delta\)；我们在第 3 节（https://arxiv.org/html/2606.06934#S3）和第 4 节（https://arxiv.org/html/2606.06934#S4）中给出了包含它们的精确界。

*   • 我们首先证明，当底层样本是二值时，\(T\) 步 \(\mathsf{DR}\text{\rm{-GD}}\) 的泛化误差的上界为 \(O(\eta T / \sqrt{n})\)²² \(\eta\) 表示学习率，\(n\) 表示样本数量。（定理 2（https://arxiv.org/html/2606.06934#Thmtheorem2））；我们还证明了即使对于任意样本空间，这个界也是紧的（定理 3（https://arxiv.org/html/2606.06934#Thmtheorem3））。由于对于凸、Lipschitz 且光滑的损失，GD 的泛化误差是 \(O(\eta T / n)\)，这些结果表明，对定点参数空间进行确定性舍入会恶化 GD 的样本复杂度。
*   • 然而，基于稳定性的方法无法达到这个界：\(\mathsf{DR}\text{\rm{-GD}}\) 的均匀稳定性的下界可以是 \(\Omega(T)\)（定理 4（https://arxiv.org/html/2606.06934#Thmtheorem4））。因此，在这种情况下，\(\mathsf{DR}\text{\rm{-GD}}\) 的均匀稳定性只能产生无效的泛化界。
*   • 另一方面，\(\mathsf{DR}\text{\rm{-SGD}}\) 的情况并非如此。我们证明，当 \(d=1\)（定理 5（https://arxiv.org/html/2606.06934#Thmtheorem5））时，\(\mathsf{DR}\text{\rm{-SGD}}\) 的均匀稳定性有界为 \(O(\eta T / n)\)；当 \(d>1\)（定理 8（https://arxiv.org/html/2606.06934#Thmtheorem8））时，有界为 \(O(\eta T^2 / n)\)。我们进一步证明了这些界的紧性（定理 6（https://arxiv.org/html/2606.06934#Thmtheorem6）和定理 7（https://arxiv.org/html/2606.06934#Thmtheorem7）），这意味着根据环境维度 \(d\) 的不同，均匀稳定性对 \(T\) 的依赖可能不同，而在 SGD 中没有观察到这种依赖性。
*   • 接下来我们考虑随机舍入，并证明 \(\mathsf{SR}\text{\rm{-GD}}\) 和 \(\mathsf{SR}\text{\rm{-SGD}}\) 的泛化误差可能随 \(d\) 增加。具体来说，定理 9（https://arxiv.org/html/2606.06934#Thmtheorem9）指出，存在凸、Lipschitz 且光滑的损失和数据分布，使得 \(\mathsf{SR}\text{\rm{-GD}}\) 和 \(\mathsf{SR}\text{\rm{-SGD}}\) 的泛化误差为 \(\Omega(\sqrt{\eta d^{1/2}}/n)\)。³³ 这里我们假设 \(\eta d^{1/2} = \Omega(1)\)。在没有此假设的界，请参见第 4 节（https://arxiv.org/html/2606.06934#S4）。我们注意到，这种维度依赖性来源于舍入的随机性，并且在 GD、SGD、\(\mathsf{DR}\text{\rm{-GD}}\) 和 \(\mathsf{DR}\text{\rm{-SGD}}\) 中并不会出现。
*   • 我们还证明了均匀参数稳定性的上界：对于 \(\mathsf{SR}\text{\rm{-SGD}}\) 为 \(O(\sqrt{\eta d^{1/2} T^3}/n)\)，对于 \(\mathsf{SR}\text{\rm{-GD}}\) 为 \(O(\eta T / n + \min\{1, \eta d^{1/2} T/n\} \sqrt{\eta d^{1/2} T})\)（定理 11（https://arxiv.org/html/2606.06934#Thmtheorem11）和定理 10（https://arxiv.org/html/2606.06934#Thmtheorem10））。对于可以表示为坐标方向函数之和的损失，我们进一步将这里的 \(T^{3/2}\) 依赖性减少到 \(T\)（定理 12（https://arxiv.org/html/2606.06934#Thmtheorem12）），并证明这些减少后的界是紧的（定理 13（https://arxiv.org/html/2606.06934#Thmtheorem13））。

表 1：迭代算法的泛化与稳定性界总结。所有结果均针对凸、\(L\)-Lipschitz 且光滑的损失，除了 (Bassily 等人，2020（https://arxiv.org/html/2606.06934#bib.bib2）) 考虑凸、Lipschitz 但非光滑的损失。\(\varepsilon_g, \varepsilon_{us}, \varepsilon_{uas}\) 分别表示泛化误差、均匀稳定性和均匀参数稳定性。下界针对最坏情况例子成立，上界对所有例子成立。为简单起见，这里我们取 \(L,\Delta = \Theta(1)\)，\(n>T\)，\(\eta=O(1)\)，且 \(\eta d^{1/2}=\Omega(1)\)；不带这些假设的精确界见第 3 节（https://arxiv.org/html/2606.06934#S3）和第 4 节（https://arxiv.org/html/2606.06934#S4）。\(n\)、\(\eta\)、\(T\) 和 \(d\) 分别表示样本数量、学习率、总迭代次数和参数维度。(1) 下界要求 \(d \geq \min\{T, 1/\eta^2\}\)，(2) 要求样本空间为二值，(3) 要求 \(d=1\)，(4) 要求 \(d \geq 2\)，(5) 要求 \(T=1\)，(6) 要求损失函数是坐标方向函数之和。

## 2 预备知识

### 2.1 符号与问题设置

对于 \(n \in \mathbb{N}\)，我们使用 \([n]\) 表示 \(\{1,\cdots,n\}\)。对于 \(d \in \mathbb{N}\)，我们使用 \(\boldsymbol{0}_d\) 表示 \((0,\cdots,0) \in \mathbb{R}^d\)，使用 \(\boldsymbol{1}_d\) 表示 \((1,\cdots,1) \in \mathbb{R}^d\)。对于 \(n \in \mathbb{N}\) 以及 \(S, S' \in \mathbb{R}^n\)，如果 \(S\) 和 \(S'\) 仅在单个条目上不同，我们称它们是相邻的，记为 \(S \simeq S'\)。对于 \(\Delta > 0\)，我们使用 \(\mathbb{Z}_\Delta\) 表示集合 \(\{\Delta n : n \in \mathbb{Z}\}\)。对于任意 \(x \in \mathbb{R}\)，我们使用 \(\lfloor x \rfloor_\Delta\) 表示 \(\max\{y \in \mathbb{Z}_\Delta : y \leq x\}\)。我们说函数 \(f: \mathbb{R}^d \to \mathbb{R}\) 是可分离的，如果存在函数 \(f_1,\cdots,f_d: \mathbb{R} \to \mathbb{R}\) 使得 \(f(x_1,\cdots,x_d) = \sum_{i=1}^d f_i(x_i)\)。对于逻辑命题 \(P\)，我们定义 \(\mathbbm{1}[P]=1\) 如果 \(P\) 为真，\(\mathbbm{1}[P]=0\) 如果 \(P\) 为假。

### 2.2 监督学习与泛化误差

我们考虑一个监督学习问题。令 \(\mathcal{D}\) 是样本空间 \(\mathcal{Z}\) 上的一个潜在分布，令 \(S=(z_1,\cdots,z_n)\) 是从 \(\mathcal{D}\) 中独立同分布抽取的 \(n\) 个样本的数据集。对于参数空间 \(\mathbb{R}^d\)，损失函数 \(f: \mathbb{R}^d \times \mathcal{Z} \to \mathbb{R}\)，以及学习算法 \(A_f: \mathcal{Z}^n \to \mathbb{R}^d\)，我们将 \(A_f\) 的*泛化误差*定义如下：
\[
\varepsilon_g(A_f; \mathcal{D}) \triangleq \left| \mathbb{E}_{A_f, S=(z_1,\dots,z_n)} \left[ f(A_f(S); S) - f(A_f(S); \mathcal{D}) \right] \right|
\]
其中 \(f(w; \mathcal{D}) \triangleq \mathbb{E}_{z \sim \mathcal{D}}[f(w;z)]\) 和 \(f(w;S) \triangleq \frac{1}{n} \sum_{i=1}^n f(w;z_i)\) 分别表示总体损失和经验损失。在整篇论文中，我们主要关注满足以下条件的损失函数：对于任意 \(z \in \mathcal{Z}\)，\(f(\cdot,z)\) 是可微、凸、Lipschitz 且光滑的。

###### 定义 1。 \(f: \mathbb{R}^d \to \mathbb{R}\) 是凸的，如果对于任意 \(u,v \in \mathbb{R}^d\)，有 \(f(u) \ge f(v) + \langle \nabla f(v), u-v \rangle\)。

###### 定义 2。 \(f: \mathbb{R}^d \to \mathbb{R}\) 是 \(L\)-Lipschitz 的，如果对于任意 \(u,v \in \mathbb{R}^d\)，有 \(|f(u)-f(v)| \le L \|u-v\|_2\)。

###### 定义 3。 \(f: \mathbb{R}^d \to \mathbb{R}\) 是