一致性稳定性的尖锐尾部

# 一致稳定性的尖锐尾部 来源：https://arxiv.org/html/2608.24098
#### 摘要
均匀稳定性控制单个训练样本能在任何测试点上改变损失的程度。一个新的对数无关上界表明，一个具有损失范围在$[0,L]$内的$\gamma$-一致稳定算法，其泛化差距以概率$1-\delta$不超过
$O\!\left(\gamma\log(1/\delta)+L\sqrt{\frac{\log(1/\delta)}{n}}\right)$。
一个实际的有界损失学习算法能否实现对$\log(1/\delta)$的线性依赖仍然悬而未决。已知的构造仅对点位范围随$n$增长的辅助弱依赖随机变量实现了这一点。已知的学习下界仅以常数概率成立。我们弥合了这一差距。对于每一个$n$、稳定性级别$\gamma$和损失界$L$，我们构造了一个确定性的$\gamma$-一致稳定学习问题，其尾部同时满足（对于$1\leq p\leq cn$）
$\mathbb{P}\!\left(R(A_{S})-R_{S}(A_{S})\geq c^{\prime}\min\!\left\{L,\gamma p+L\sqrt{p/n}\right\}\right)\geq e^{-p}$。
该构造是具有常数标签的普通有界绝对损失回归。其关键在于使用了多尺度的稀有拉德马赫特征集合。按坐标分级的斜坡在sup范数下是稳定的，而一个奇数对称化最大值将一个独特的极端特征转化为$\gamma p$量级的差距而不违反损失界。几何间距的斜坡将所有置信水平放入同一问题中。结合对数无关上界，这确定了均匀稳定性的最优高概率和矩依赖关系（至多常数因子差异）。
## 1 引言
算法稳定性通过学习规则的行为而非假设类上的一致收敛来解释泛化。当替换一个训练样本时，学习算法$A$在每个测试点上的损失变化最多为$\gamma$，则称该算法是$\gamma$-一致稳定的（Bousquet和Elisseeff，2002）。这一性质为正则化经验风险最小化、梯度方法和随机优化提供了保证（Shalev-Shwartz等人，2010；Hardt等人，2016）。其期望保证简单而精确：
$\|\mathbb{E}[R(A_{S})-R_{S}(A_{S})]\|\leq\gamma$。
获得正确的高概率保证经历了一系列更长的结果。经典的有界差异论证给出了$\gamma\sqrt{n\log(1/\delta)}$量级的偏差项（Bousquet和Elisseeff，2002）。Feldman和Vondrák（2018）将因子$\gamma\sqrt{n}$替换为$\sqrt{\gamma L}$，Feldman和Vondrák（2019）获得了具有对数开销的近乎最优界。Bousquet等人（2020）将学习问题简化为弱交互函数的矩不等式。他们的结果在稳定性项中留下了一个$\log n$因子。非常近期，Nguyen-Cung和Nguyen（2026）移除了该因子并证明了
$\|R(A_{S})-R_{S}(A_{S})\|_{p}\leq 33p\gamma+L\sqrt{\frac{2p}{n}},\qquad p\geq 2.$
(1)
平凡的范围界随后将右侧限制在$L$内。公式 (1) 给出了干净的尾部尺度 $\min\!\left\{L,\gamma\log(1/\delta)+L\sqrt{\frac{\log(1/\delta)}{n}}\right\}$. (2)
下界方面尚未跟上这一进展。Bousquet等人（2020）构造了具有$p$阶矩$\Omega(pn\gamma+L\sqrt{pn})$的弱交互函数。他们的函数具有$n\gamma$量级的点位幅度，因此该构造并非来自具有统一损失界$L$的学习算法。他们明确询问，由一个一致稳定学习器诱导的函数是否可能表现出相同的行为。Liu和Lu（2020）后来构造了一个有界损失学习器，在常数概率下具有$\Omega(\gamma+L/\sqrt{n})$的差距，并将对小失败概率的依赖性问题留待开放。新的上界论文也将其结果与这个确切的学习下界问题分离开来（Nguyen-Cung和Nguyen，2026）。我们的下界定理和证明独立于该预印本。公式 (1) 仅用于确定匹配的上界尺度。我们证明 (2) 中的每一项都是必要的。更强烈地说，一个有限维问题在所有置信水平$e^{-p}$（$p\leq cn$）下实现了完整的曲线。这不是为每个$p$选择的不同问题。
#### 为什么明显的二次构造会失败。
令$X_{1},\ldots,X_{n}$为拉德马赫符号，$T=\sum_{i}X_{i}$，并且让一个学习器以幅度$\gamma T$进行预测。线性损失具有$\gamma T^{2}/n$的泛化差距，其$p$阶尺度为$\gamma p$。在该事件上的预测幅度是$\gamma\sqrt{np}$。将其裁剪到损失范围$L$内时，当$p\gtrsim L^{2}/(\gamma^{2}n)$时被激活。这正是$\gamma p$项开始主导$L\sqrt{p/n}$的地方。因此，裁剪破坏了需要证明的尾部部分。
#### 新机制。
我们用多个独立的拉德马赫特征替换一个特征。在选定的尺度上，指数多个坐标被放置在固定大偏差阈值之下。宽度为$\Theta(p)$的斜坡仅在一个坐标越过该阈值时给出$\Theta(\gamma p)$的幅度。无论坐标数量多少，该斜坡在坐标上都是$\gamma$-稳定的。损失通过奇函数$H_{a}(x)=\max_{j}a_{j}x_{j}-\max_{j}(-a_{j}x_{j})$读取坐标。(3)
在对称总体下它中心对称，并且在sup范数下关于$a$是2-李普希茨的。当存在一个主导坐标时，其经验平均值远离零，因此它对差距贡献$\Theta(\gamma p)$。具有较小斜坡的坐标可以在不改变效应符号的情况下存在。具有较大斜坡的坐标在干净的极端事件上是缺失的。我们使用几何间距的斜坡宽度。在尺度$p_k$上的事件具有远大于$e^{-p_k}$的概率，这留下足够的概率将其与普通的采样偏差事件相交。一个单独的稳定记忆项处理常数置信度和范围饱和情况。所有组件在绝对损失下的标量预测器中组合。
特征库$d_{k}\asymp e^{-p_k/2}/q_{\star}$独立符号 $\Longrightarrow$ 稀有越过一个分数 $\geq s_{\star}$ 概率 $\gtrsim e^{-p_k/2}$ $\Longrightarrow$ 稳定读出斜坡$\gamma p_k$奇数最大值 $\Longrightarrow$ 完全差距 $\gamma p_k+L\sqrt{p/n}$ 概率 $\geq e^{-p}$
图1：多尺度机制。倒数概率特征复制使罕见的大偏差穿越可见。坐标稳定的斜坡和奇数最大值将该穿越转化为经验偏差。独立记忆和采样项填充尾部的常数置信和平方根部分。$p_k$的几何选择将每个$p\leq cn$放入一个学习器中。
#### 贡献。
- 我们给出了第一个具有$\Omega(\gamma\log(1/\delta))$高概率泛化差距的有界损失一致稳定学习器。
- 一个单一问题同时为所有$1\leq p\leq cn$实现了$\Omega(\min\{L,\gamma p+L\sqrt{p/n}\})$。因此，公式 (1) 中的矩上界对于实际学习算法是紧的。
- 该构造使用确定性学习和标准绝对回归损失。我们证明在所有替换数据集上的一致稳定性，而不仅仅是在高概率事件上。
#### 相关扩展。
几条近期的研究路线改变了假设，而非最坏情况下的下界问题。Klochkov和Zhivotovskiy（2021）在伯恩斯坦条件下获得了更快的超额风险速率。Zhou等人（2023）推导了随机一致稳定算法的PAC-Bayes界，这些算法的随机稳定性参数满足亚指数条件。Yuan和Li（2022）使用子袋法来提升随机算法的置信度，这些算法基于更弱的、依赖于分布的$L_2$稳定性概念。Fan和Lei（2024）引入了逐点一致稳定性，并推导了函数值和梯度泛化界，应用于SGD。在互补的2026方向，Lei等人（2026）用有限$L_p$替换一封套替代有界差异，并为无界损失获得高斯加多项式上尾。这些结果从额外结构或修改后的算法中提供了更尖锐的结论。它们没有为普通的确定性一致稳定性条件 (4) 提供高概率下界。我们的结果恰恰涉及这个最坏情况条件以及Bousquet等人（2020）、Liu和Lu（2020）以及Nguyen-Cung和Nguyen（2026）留下的有界损失极小极大差距。
## 2 设置与结果
令$S=(Z_{1},\ldots,Z_{n})\sim P^{n}$。算法$A$将$S$映射到预测器$A_{S}$。对于值域在$[0,L]$内的损失$\ell$，定义
$R(A_{S})=\mathbb{E}_{Z\sim P}\ell(A_{S},Z),\qquad R_{S}(A_{S})=\frac{1}{n}\sum_{i=1}^{n}\ell(A_{S},Z_{i}),\qquad G_{S}=R(A_{S})-R_{S}(A_{S}).$
如果对于任何$S$和$S'$仅在一个坐标上不同，算法是$\gamma$-一致稳定的，则
$\sup_{z}|\ell(A_{S},z)-\ell(A_{S'},z)|\leq\gamma.$ (4)
我们的定理陈述使用未指定的通用常数。附录追踪了构造的具体常数。
#### 定理 1（尖锐下尾）。
存在通用常数$c_{0},c_{1}>0$和$n_{0}\in\mathbb{N}$，具有以下性质。对于每个$n\geq n_{0}$、$L>0$和$0\leq\gamma\leq L$，存在一个有限输入空间、一个分布$P$和一个确定性的$\gamma$-一致稳定绝对损失回归算法，其损失在$[0,L]$内，使得对于每个实数$p\in[1,c_{0}n]$，同时满足
$\mathbb{P}_{S\sim P^{n}}\!\left(G_{S}\geq c_{1}\min\!\left\{L,\gamma p+L\sqrt{p/n}\right\}\right)\geq e^{-p}.$ (5)
回归标签恒为零。该问题可能依赖于$(n,L,\gamma)$，这在极小极大下界中是标准的。关键在于，它不依赖于$p$或$\delta$。同时陈述立即给出矩紧性。
#### 推论 2（矩紧性）。
对于定理 1 中的问题和每个$p\in[2,c_{0}n]$，
$\|G_{S}\|_{p}\geq c_{2}\min\!\left\{L,\gamma p+L\sqrt{p/n}\right\}$ (6)
对于通用$c_{2}>0$。确实，(5) 意味着$\|G_{S}\|_{p}\geq e^{-1}$乘以其显示的阈值。结合推论 2 与 (1) 和范围界，得到极小极大律
$\sup_{(P,A,\ell)}\|G_{S}\|_{p}\asymp\min\!\left\{L,\gamma p+L\sqrt{p/n}\right\},\qquad 2\leq p\leq c_{0}n,$ (7)
其中上确界取自所有损失在$[0,L]$内的$\gamma$-稳定算法。(7) 中的上常数和下常数是通用的。
## 3 多尺度学习器
我们现在定义每个$p$使用的单一问题。训练输入是$Z=(X,J,\Sigma,U)$。所有组件独立。向量$X$由独立的拉德马赫坐标组成，$J$在$[D]$上均匀分布，$\Sigma,U$是拉德马赫符号。$X$的维度被分成由几何尺度集索引的组。令
$p_{k}=16\cdot4^{k},\qquad r_{k}=p_{k}/16=4^{k},\qquad p_{k}\leq\min\{n/64,L/\gamma\},$ (8)
其中$L/0=+\infty$。令$B_{n}$为$n$个独立拉德马赫符号的和。选择第一个可获得的分数$s_{\star}\geq n/4$并设置$q_{\star}=\mathbb{P}(B_{n}\geq s_{\star})$, $d_{k}=\left\lfloor\frac{8e^{-p_{k}/2}}{q_{\star}}\right\rfloor$, $t_{k}=s_{\star}-2r_{k}$. (9)
第$k$组包含$d_{k}$个独立坐标。对于样本，写$S_{kj}=\sum_{i=1}^{n}X_{i,kj}$并定义斜坡幅度
$a_{kj}(S)=\min\left\{\gamma r_{k},\frac{\gamma}{2}(S_{kj}-t_{k})_{+}\right\}.$ (10)
如果尺度集为空，$X$具有一个幅度为零的虚拟坐标。总特征维度是有限的，通常相对于$n$是指数级的，因为$q_{\star}=e^{-\Theta(n)}$。第7节解释了为何使用此多重性。
记忆组件使用$D=8n^{2}$个单元。令
$b_{j}(S)=c_{\rm mem}\,\operatorname{sgn}\!\left(\sum_{i:J_{i}=j}\Sigma_{i}\right),\qquad c_{\rm mem}=\min\{\gamma/4,L/8\},$ (11)
其中$\operatorname{sgn}(0)=0$。将所有斜坡幅度收集在向量$a(S)$中，并使用(3)中的对称化最大值$H_{a}$。预测器是
$h_{S}(X,J,\Sigma,U)=\frac{L}{2}-\frac{1}{4}H_{a(S)}(X)-b_{J}(S)\Sigma-\frac{L}{4}U.$ (12)
回归标签为零，损失是绝对误差。我们将证明$h_{S}\in[0,L]$，因此损失等于$h_{S}$本身。(12)中的四个部分具有不同的作用。中心$L/2$强制有效的损失范围。对称化最大值产生$\gamma p$尾部。单元记忆产生常数量级的稳定性差距，并处理低于16或高于$L/\gamma$的尺度。最后一个符号产生普通的$L\sqrt{p/n}$采样尾部。
## 4 稳定性与中心化
两个基本的李普希茨性质使该构造得以工作。
#### 引理 3（对称化最大值）。
对于非负向量$a,a'$和偶