快速停止！早停法实现认证鲁棒性

# 迅速停止！面向认证鲁棒性的早期停止策略  
来源：https://arxiv.org/html/2606.27694  

Andrew C. Cullen  
墨尔本大学  
[email protected]  

& Paul Montague  
DST Group, 阿德莱德  

& Benjamin I. P. Rubinstein  
墨尔本大学  

###### 摘要  

随机平滑（Randomized Smoothing, RS）为神经网络提供了严格的鲁棒性保证，且无需修改网络架构，然而其应用受限于极高的计算开销。标准RS需要对每个输入进行数万次模型评估，并且迫使实践者*事先*承诺固定的样本量。在本文中，我们提出了一种新颖的元学习框架，用于实现任意有效的认证鲁棒性，该框架能够自适应地分配计算资源。通过使用轻量级元学习器预测图像特定的先验分布以用于顺序E过程，我们在保持严格统计保证的同时，将样本复杂度相比传统方法减少了20倍。除了原始效率外，我们还展示了任意有效性如何能够根据特定应用的风险阈值自适应地分配计算资源——这是一种在经典认证框架下无法实现的资源分流形式。而我们的方法在实现这一点的同时还能提供相似的认证性能，说明它为实时、安全关键的认证部署提供了一条可行路径。  

## 1 引言  

尽管神经网络具有变革性的实用性，但它们仍然对常常语义上无意义的修改极其敏感（Szegedy et al., 2013 (https://arxiv.org/html/2606.27694#bib.bib1)）。这些修改现在被称为对抗样本（Goodfellow et al., 2014 (https://arxiv.org/html/2606.27694#bib.bib2); Madry et al., 2018 (https://arxiv.org/html/2606.27694#bib.bib3)），其研究已一致表明，模型的决策边界往往缺乏安全关键部署所需的语义对齐。虽然已经提出了针对这些操纵的防御方法，但它们从根本上受限于技术军备竞赛，其中每项新防御都会带来新的攻击目标（Goodfellow et al., 2014 (https://arxiv.org/html/2606.27694#bib.bib2); Cullen et al., 2025 (https://arxiv.org/html/2606.27694#bib.bib4)）。相比之下，认证鲁棒性（Certified Robustness）已发展为一个严格的框架，用于数学上保证模型在输入的某个邻域内预测不变（Lecuyer et al., 2019 (https://arxiv.org/html/2606.27694#bib.bib6); Cohen et al., 2019 (https://arxiv.org/html/2606.27694#bib.bib5); Cullen et al., 2022 (https://arxiv.org/html/2606.27694#bib.bib7)）。对于分类系统而言，这种形式通常通过半径 \(r\) 来定义，使得对于模型 \(F\)，我们可以保证对于所有在球 \(B_p(x,r) = \{ x' : \|x' - x\|_p \le r \}\) 内的 \(x'\)，都有 \(F(x) = F(x')\)。在各类认证方法中，随机平滑（RS）独树一帜，因为它可以应用于任何模型而无需修改架构。然而，这种灵活性是有代价的——要完成一次认证，样本必须通过模型数万次，每次副本都加上一个从正态分布中抽取的小扰动。这种高样本复杂度（用于控制第一类错误（假阳性））使得认证的实时应用几乎不可能，尤其是对于大规模模型。  

最近的研究进展试图通过顺序测试和早期停止来减轻这一开销。最值得注意的是，E值（Shafer and Vovk, 2019 (https://arxiv.org/html/2606.27694#bib.bib15); Ramdas et al., 2023 (https://arxiv.org/html/2606.27694#bib.bib16)）和测试鞅的引入，使得任意有效的认证成为可能（Voráček, 2024 (https://arxiv.org/html/2606.27694#bib.bib8)）。通过将认证框架化为一个超鞅财富过程，一旦积累了足够的鲁棒性证据，就可以停止采样，而不会违反统计安全性。然而，当前E值在鲁棒性中的应用主要集中在二元假设检验（例如，询问 \(r \ge c\) 与否），将认证器简化为一个简单的基于阈值的分类器。这种局限剥夺了过程所需的区分度信息，无法评估不同样本之间的相对安全性。  

在这项工作中，我们认为任意有效认证的主要效用并不一定在于其计算效率，而在于能够根据基于应用的工作流自适应地设定停止条件。为了支持这一目标，我们的贡献有三个方面：  

1. **针对连续假设的混合方法**：我们将E值认证扩展为一种基于混合的多假设方法，以匹配传统的认证工作流。  
2. **样本自适应的元学习**：我们引入了一种优化的E值形式，其中元学习器预测先验分布以提高效率。我们采用轻量级元学习器来分析初始模型快照，利用贝叶斯负对数似然（NLL）目标来拟合给定输入下平滑模型成功率的分布。  
3. **对抗性退出**：我们引入了任务自适应的终止条件，允许基于预先指定的领域任务提前终止，从而以优化全局计算的方式实现高效的认证和拒绝。  

通过实验验证，我们证明了我们的方法能够比固定样本方法显著更快地构建认证——在不到500个样本内即可构建可行的认证，相比之前的认证工作流减少了20倍。也许更重要的是，我们的创新允许应用级和样本级特定的退出条件，这对于帮助认证从计算成本高昂的概念转变为产生现实世界安全性的可行框架至关重要。  

### 1.1 动机案例  

为了强调本文所引入方法的实用性，我们突出了三种非常契合任意有效认证的场景。第一种是自然的：**计算效率**。一旦达到目标精度就立即停止，我们移除了现实部署的主要障碍。第二种是**资源分流**：在大规模系统中，证书可用于根据输入的鲁棒性将其路由到不同的验证路径。在这种情况下，证明样本落在某个特定风险桶内，比其精确半径更为关键。最后，我们还提出，**流式场景**（例如自动驾驶）也可以应用这种方法，其中来自先前帧的先验信息可用于初始化E值认证，从而允许在时间演变的环境中实现更快的收敛。  

## 2 相关工作  

随机平滑（RS）已从差分隐私基础（Lecuyer et al., 2019 (https://arxiv.org/html/2606.27694#bib.bib6); Dwork et al., 2006 (https://arxiv.org/html/2606.27694#bib.bib36)）发展到当前基于Neyman-Pearson引理的最先进方法（Cohen et al., 2019 (https://arxiv.org/html/2606.27694#bib.bib5)）。其核心，所有基于RS的认证都将基础模型 \(f\) 转化为平滑对应物 \(g\)，并附带可证明的 \(\ell_p\) 边际保证。如 Cohen et al. (2019 (https://arxiv.org/html/2606.27694#bib.bib5)) 所确立的，对于噪声水平 \(\sigma\)，认证半径 \(r\) 是最可能类别 \(c_A\) 的成功概率 \(p_A = \mathbb{P}_{\epsilon \sim \mathcal{N}(0, \sigma^2 I)} [f(x + \epsilon) = c_A]\) 的函数：
\[
r = \sigma \Phi^{-1}(p_A).
\tag{1}
\]
在实践中，认证是通过一个独立的两阶段方法构建的，其中第一阶段使用初始批次确定目标类别，然后通过阶段II中的蒙特卡洛采样估计 \(p_A\)。为了控制虚假认证的风险，标准方法使用Clopper-Pearson区间（Clopper and Pearson, 1934 (https://arxiv.org/html/2606.27694#bib.bib9)）来获得高概率下界 \(\underline{p_A}\)。对紧致下界的需求是RS高计算成本的主要驱动因素。高方差输入可能需要数万个样本才能产生有意义的证书。  

关键的是，窥视问题（Johari et al., 2017 (https://arxiv.org/html/2606.27694#bib.bib42)）使得如果实践者监视经验均值并提前停止，则Clopper-Pearson界在第一类错误率上失效。因此，\(N\) 必须*事先*固定，导致简单输入的大量过度采样，而边缘输入的完全认证失败。  

作为回应，顺序测试已成为通向高效鲁棒性的途径。为此，显著性预算 \(\alpha\) 通过Bonferroni校正或alpha支出函数（Horváth et al., 2022 (https://arxiv.org/html/2606.27694#bib.bib32)）被划分为多个不同的停止点 \(\{n_1, n_2, \ldots, n_k\}\)。虽然这些方法允许早期停止，但它们仍然保留了频率派框架的基本缺陷：在每个 \(n_i\) 之后，如果模型未能认证，则模型将进一步采样到 \(n_{i+1}\)。然而，检查多个停止点的校正要求 \(\alpha\) 按潜在比较次数（也须*事先*设置）缩放，从而增加了认证到给定水平所需的样本数量。因此，这些早期停止框架为了认证一个样本，可能需要比 Cohen et al. (2019 (https://arxiv.org/html/2606.27694#bib.bib5)) 更朴素实现评估多得多的净样本。虽然通过*事先*估计适当的样本数量可以找到额外的效率（Chen et al., 2022 (https://arxiv.org/html/2606.27694#bib.bib33)），但这些方法本质上仍然是保守且昂贵的。  

E值提供了一种自然的解决方案来规避这些限制，因为它们是任意有效的，并且不受窥视问题的影响。这使得认证可以以一种允许基于任意标准早期停止的方式构建。该方法的原始开创者 Voráček (2024 (https://arxiv.org/html/2606.27694#bib.bib8)) 主要考虑了如何将其应用于二元鲁棒性假设（例如，\(r \ge r_0\)）。在本文中，我们利用**混合方法**（Method of Mixtures）（Waudby-Smith and Ramdas, 2024 (https://arxiv.org/html/2606.27694#bib.bib17); Grünwald et al., 2020 (https://arxiv.org/html/2606.27694#bib.bib18)）来支持连续半径估计。值得注意的是，先前基于混合的方法依赖于Krichevsky–Trofimov（KT）估计器（Krichevsky and Trofimov, 1981 (https://arxiv.org/html/2606.27694#bib.bib13)），该估计器针对*任意*序列进行优化。然而，我们认为RS序列并非任意；它们与特定的输入流形相关联。这一差异是我们元学习框架的理论基础，该框架学习参数化定制先验，以充分加速任意有效性。为叙述清晰，更深入的认证讨论可见附录A (https://arxiv.org/html/2606.27694#A1)。  

## 3 任意有效的半径认证  

为了评估模型在点 \(x\) 处对类别 \(c_A\) 预测的鲁棒性，我们考虑平滑分类器的成功概率 \(p = P(f(x + \epsilon) = c_A)\)（我们强调，为数学方便，我们预设已知 \(c_A\)，并且在我们的算法中会适当估计该类别）。假设我们观察到一个无限的独立同分布伯努利试验序列 \(X_1, X_2, \ldots\)，其中每个 \(X_i = \mathbb{I}[f(x + \epsilon_i) = c_A]\) 表示用噪声 \(\epsilon_i \sim \mathcal{N}(0, \sigma^2 I)\) 对 \(x\) 进行的第 \(i\) 次扰动是否与目标类别一致。为了构建认证，我们必须能够针对任何阈值 \(p_0 \in [0,1]\) 检验零假设 \(H_0: p \le p_0\)，从而构建一个关于 \(p\) 的任意有效下置信界。  

##### 测试鞅与E值  

为此，我们利用*E值*，它是一个非负随机变量 \(E\)，满足 \(\mathbb{E}_{H_0}[E] \le 1\)（Vovk and Wang, 2021 (https://arxiv.org/html/2606.27694#bib.bib19); Shafer, 2019 (https://arxiv.org/html/2606.27694#bib.bib44)）。在我们的伯努利设定中，对于点零假设 \(H_0: p = p_0\) 和点备择假设 \(H_1: p = q\)，合适的E值是似然比（Waudby-Smith and Ramdas, 2024 (https://arxiv.org/html/2606.27694#bib.bib17)）：
\[
E_i = \frac{q^{X_i} (1 - q)^{1 - X_i}}{p_0^{X_i} (1 - p_0)^{1 - X_i}}.
\tag{2}
\]

为了验证累积E值的显著性，我们采用受赌博游戏启发的过程（Shafer, 2019 (https://arxiv.org/html/2606.27694#bib.bib44); Vovk and Wang, 2021 (https://arxiv.org/html/2606.27694#bib.bib19)）。考虑财富过程 \(W_t(p_0) = \prod_{i=1}^t E_i\)，即 \(t\) 个样本上E值的累积。那么，若 \(h_t = \sum_{i=1}^t X_i\) 是前 \(t\) 次试验中的成功次数，总财富必须为：
\[
W_t(p_0) = \frac{q^{h_t} (1 - q)^{t - h_t}}{p_0^{h_t} (1 - p_0)^{t - h_t}}.
\tag{3}
\]
该表达式表示在备择假设下观察到的序列的似然与在零假设下的似然的比值。过程 \((W_t(p_0))_{t \ge 1}\) 是一个非负鞅，在 \(p = p_0\) 下满足 \(\mathbb{E}[W_t] = 1\)。根据Ville不等式（Ville, 1939 (https://arxiv.org/html/2606.27694#bib.bib11); Doob, 1940 (https://arxiv.org/html/2606.27694#bib.bib10)），所有尚未使财富跨越拒绝阈值 \(1/\alpha\) 的 \(p_0\) 构成的集合形成置信区间：
\[
C_t = \left\{ p_0 \in [0,1] : \max_{\tau \le t} W_\tau(p_0) < \frac{1}{\alpha} \right\}
\]
其中下置信界（LCB）为 \(\underline{p_t} = \inf C_t\)。  

###### 定理1（正确性）  
对于目标类别 \(c_A\)，显著性水平 \(\alpha \in (0,1)\)，以及先验混合 \(Q\)，下置信界 \(\underline{p_t} = \inf \{ p_0 : \max_{\tau \le t} \overline{W}_\tau(p_0) < 1/\alpha \}\) 满足：
\[
P(\exists t: \underline{p_t} < p) \ldots
\]
（详见第6节 (https://arxiv.org/html/2606.27694#S6)）。  

##### 对抗性退出和平坦退出  

我们优先对非鲁棒样本进行快速拒绝（\(p < 0.5\)）。如果 \(W_t(0.5) \ge 1/\alpha\) 且经验均值 \(\hat{p}_{mle} < 0.5\)，则意味着上置信界小于 \(0.5\)，样本被拒绝。此外，我们监控半径速度：如果 \(\underline{r_{lcb}}\) 在连续四个区间内没有改善超过 \(5\%\)，系统会基于当前的LCB触发认证，若累积证据仍低于鲁棒性阈值则有效拒绝样本，并避免进一步计算以节省计算预算。  

##### 算法  

我们方法的完整操作流程见下文。