The Price of Robustness: Stable Classifiers Need Overparameterization¶

会议: ICLR 2026
arXiv: 2603.02806
代码: 无
领域: 学习理论 / 泛化理论
关键词: 过参数化, 鲁棒性, 稳定性, 分类器, 泛化界, margin

一句话总结¶

建立了不连续分类器的稳定性-泛化界，证明了分类任务中的"鲁棒性代价定律"：任何参数量 \(p \approx n\) 的插值分类器必然不稳定，实现高稳定性需要 \(p \approx nd\) 量级的过参数化。

研究背景与动机¶

过参数化的悖论：经典学习理论认为参数越多过拟合越严重，但现代神经网络在过参数化时反而泛化更好（双下降现象）
Bubeck & Sellke 2021 的鲁棒性定律：证明了回归场景中 Lipschitz 连续函数的平滑性-过参数化权衡。但该结果依赖 Lipschitz 假设，不适用于分类器（离散输出，天然不连续）
经验发现：大规模研究（Jiang et al. 2019）显示 40+ 复杂度度量中，与泛化最一致相关的是 margin（到决策边界的距离），而非范数类度量
核心问题：如何为不连续分类器建立稳定性驱动的泛化理论？

方法详解¶

整体框架¶

整篇论文围绕一条逻辑链展开：先用"期望 margin"把分类器的鲁棒性量化成一个可分析的标量 \(S(f)\)，再借助数据分布的等周性把这个量塞进 Rademacher 复杂度的上界，从而证明稳定性会压低模型类的有效复杂度。反过来推，就得到"鲁棒性代价定律"——要让一个能插值训练集的分类器同时保持高稳定性，参数量必须从 \(p \approx n\) 抬升到 \(p \approx nd\) 量级。最后再把这套从有限函数类得到的结论，借助得分函数的 Lipschitz 连续性推广到神经网络这种无限函数类。

关键设计¶

1. 类稳定性：用期望 margin 把"不连续"变成可分析的标量。 分类器输出离散标签、天然不连续，没法直接套用回归里的 Lipschitz 平滑性框架，于是作者改用样本到决策边界的距离来刻画鲁棒性。对分类器 \(f: \mathcal{X} \to \{-1, 1\}\)，先定义无符号 margin 为样本到最近异类点的欧氏距离 \(h_f(x) := |d_f(x)| = \inf\{\|x - z\|_2 : f(z) \neq f(x), z \in \mathcal{X}\}\)（定义 1），它度量了把 \(x\) 推过决策边界所需的最小扰动。再取它在数据分布下的期望，得到类稳定性 \(S(f) := \mathbb{E}[h_f]\)。\(S(f)\) 越大，说明平均而言要更大的扰动才能翻转预测，正好对应"分类器对输入扰动的平均鲁棒性"，且它是一个连续标量，可以进入后续的复杂度分析。

2. 等周假设：把高维集中现象注入泛化界。 要让 margin 真正约束泛化，必须刻画数据在高维空间里的几何。作者假设分布 \(\mu\) 满足 \(c\)-等周性：对任意有界 \(L\)-Lipschitz 函数 \(f\) 和 \(t \geq 0\)，有 \(\mathbb{P}(|f(x) - \mathbb{E}[f]| \geq t) \leq 2 e^{-\frac{dt^2}{2cL^2}}\)。高斯分布、球面均匀分布等都满足这一条件，它表达的是高维测度集中——函数值以指数速度集中在均值附近，而集中的速率由维度 \(d\) 控制。根据流形假设，这里的 \(d\) 可解释为数据的内在流形维度，这也是后面 \(nd\) 量级里那个 \(d\) 的来源。

3. 稳定性压低有效复杂度：把 \(S\) 写进 Rademacher 界。 这是整套理论的技术核心：证明稳定性能直接削减模型类的复杂度。在 \(\min_{f \in \mathcal{F}} S(f) > S > 0\) 且 \(\log|\mathcal{F}| \geq n\) 的条件下，定理 4 给出 \(\mathcal{R}_{n,\mu}(\mathcal{F}) \leq K_1 \max\left\{\frac{1}{\sqrt{n}}, \frac{\sqrt{c}}{S} \cdot \frac{\log|\mathcal{F}|}{n\sqrt{d}}\right\}\)；在额外的正则性条件下还能改进为 \(\mathcal{R}_{n,\mu}(\mathcal{F}) \leq K_2 \max\left\{\frac{1}{\sqrt{n}}, \frac{\sqrt{c}}{S}\sqrt{\frac{\log|\mathcal{F}|}{nd}}, 2\exp\left(-\frac{dS^2}{8c}\right)\right\}\)。关键在于 \(1/S\) 出现在 \(\sqrt{\log|\mathcal{F}|}\) 前面——稳定性越高，复杂度项被压得越低，于是一个表面上很大的模型类，只要其中的函数都足够稳定，有效复杂度就会显著下降。

4. 鲁棒性代价定律：低误差与高稳定性不可兼得，除非过参数化。 把上面的复杂度界反向使用，就能逼出参数量的硬性下界。令 \(p := \log|\mathcal{F}| \geq n\)，推论 6 表明在适当条件下、以高概率有 \(\hat{R}_{\text{0-1}}(f) \leq R^* - \varepsilon \implies S(f) < \max\left\{\frac{3K}{\varepsilon}\sqrt{\frac{c\log|\mathcal{F}|}{nd}}, \sqrt{\frac{8c}{d}\log\frac{6K}{\varepsilon}}\right\}\)。这个蕴含式直接读出代价：当 \(p \approx n\) 时，右端的稳定性上界被压得很小，于是任何能插值训练集的分类器都注定不稳定；要同时拿到低训练误差和高稳定性，唯一出路是把参数量抬到 \(p \approx nd\) 量级——这正是"鲁棒性需要过参数化"的精确表述。

5. 推广到无限函数类：用归一化 co-stability 接住神经网络。 上面的结论建立在有限函数类（\(\log|\mathcal{F}|\) 有限）之上，而神经网络是连续参数化的无限类，需要一座桥。作者把分类器写成 \(f = \text{sgn} \circ g_w\)，对得分函数 \(g_w\) 的输出 margin 做归一化，得到归一化 co-stability；再结合 \(g_w\) 在参数 \(w\) 和输入 \(x\) 上的 Lipschitz 连续性，把无限类的复杂度控制住，从而推出对应的泛化界（定理 13）和鲁棒性定律（推论 15）。值得注意的是，这里只要求得分函数 \(g_w\) 连续，而最终分类器 \(\text{sgn} \circ g_w\) 仍可不连续，这让框架能覆盖量化网络、脉冲网络乃至 self-attention 这类不满足整体 Lipschitz 性的模型。

实验结果¶

MNIST 实验¶

网络宽度	测试准确率	类稳定性 \(S(f)\)	谱范数
小	较低	低	无规律
中	中等	中	无规律
大	高	高	无规律

CIFAR-10 实验¶

网络宽度	测试准确率	归一化 co-stability	谱范数
窄	~70%	低	变化不一致
宽	~85%	高	变化不一致
更宽	~90%	更高	变化不一致

关键发现¶

稳定性和归一化 co-stability 随网络宽度单调增加
稳定性与测试性能呈正相关
传统范数度量（谱范数等）与泛化无系统性关联
验证了理论预测：过参数化→高稳定性→好泛化

亮点与洞察¶

扩展到不连续函数：首次将鲁棒性定律从 Lipschitz 回归推广到不连续分类器
0-1 损失的直接分析：不需要 Lipschitz 损失假设
解释过参数化：过参数化不是过拟合的源头，而是实现鲁棒性的必要条件
适用广泛：覆盖量化神经网络、脉冲神经网络等天然不连续模型
Transformer 的特殊意义：self-attention 通常不是 Lipschitz 连续的，本框架比 Lipschitz 框架更适用

局限性¶

等周假设对某些数据分布可能不成立
有限函数类到无限类的推广需要额外的参数 Lipschitz 假设
泛化界可能仍然是 vacuous 的（与 Nagarajan & Kolter 2021 的批评一致）
理论维度 \(d\) 的实际值难以精确估计（外在维度 vs 内在维度）
未建立与优化动力学（如 implicit bias）的直接联系

评分¶

创新性: ⭐⭐⭐⭐ — 将鲁棒性定律推广到分类的自然且重要的扩展
技术深度: ⭐⭐⭐⭐⭐ — 证明技巧精巧，从 Lipschitz 代理到 signed distance 表示
实验充分性: ⭐⭐⭐ — MNIST 和 CIFAR-10 验证，定性为主
实用价值: ⭐⭐⭐⭐ — 为理解过参数化泛化提供理论支撑