Rademacher 泛化界

两个规范版本 ​

设 $F$ 是从 $\mathcal{Z}$ 到 $[0,1]$ 的固定函数类，$S=(Z_1,\dots ,Z_m)\sim D^m$。采用

$${\hat{\mathfrak{R}}}_S(F)={\mathbb{E}}_{\sigma }[\underset{f\in F}{sup}\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}f(Z_i)],{\mathfrak{R}}_m(F)={\mathbb{E}}_S{\hat{\mathfrak{R}}}_S(F),$$

其中 ${\sigma }_i$ 是独立均匀的 $\{-1,+1\}$ 符号。则在可测性条件下，以至少 $1-\delta$ 的概率，同时对所有 $f\in F$ 有

$$Pf\le P_{m}f+2{\mathfrak{R}}_m(F)+\sqrt{\frac{\log \left(1/\delta \right)}{2m}}.$$

把未知的期望复杂度换成样本可计算的经验复杂度，一种常用版本是

$$Pf\le P_{m}f+2{\hat{\mathfrak{R}}}_S(F)+3\sqrt{\frac{\log \left(2/\delta \right)}{2m}}.$$

不同文献若在复杂度定义中预先放入 $2/m$，定理前的系数会相应变化；不能只换定义而保留常数。

从总体偏差到随机符号 ​

考察单边偏差

$$\mathrm{\Phi }(S)=\underset{f\in F}{sup}(Pf-P_{m}f).$$

引入独立 ghost sample $S^{\prime }$，Jensen 不等式与对称化依次给出

$${\mathbb{E}}_S\mathrm{\Phi }(S)\le {\mathbb{E}}_{S,S^{\prime }}\underset{f}{sup}(P_m^{\prime }f-P_{m}f)\le 2{\mathfrak{R}}_m(F).$$

第二步利用每对 $(Z_i,Z_i^{\prime })$ 可交换：乘上随机符号不会改变联合分布，再把两个符号和分别以上确界控制。此处得到的是整个类的期望最大偏差，而非单个训练后模型的事后估计。

替换 $S$ 中一个观测时，每个 $P_{m}f$ 至多变化 $1/m$，所以上确界 $\mathrm{\Phi }(S)$ 也至多变化 $1/m$。有界差分不等式公理库有界差分不等式McDiarmid inequality · 有界差异不等式独立输入的函数若对单个坐标不敏感，其输出便以次高斯速度集中在期望附近。把期望提升为第一条高概率界。经验复杂度本身对单点替换也至多变化 $1/m$，再做一次集中并合并失败事件，得到第二条完全数据依赖的版本。

线性预测器经过损失后的真例 ​

设 $\Vert x{\Vert }_2\le R$，预测器 $x\mapsto ⟨w,x⟩$ 满足 $\Vert w{\Vert }_2\le B$。对固定样本，Cauchy–Schwarz 给

$${\hat{\mathfrak{R}}}_S(F)=\frac{B}{m}{\mathbb{E}}_{\sigma }{\Vert \sum _i{\sigma }_i{x}_i\Vert }_2\le \frac{B}{m}\sqrt{\sum _i\Vert x_i{\Vert }_2^2}\le \frac{BR}{\sqrt{m}}.$$

若损失 $\ell (y,\cdot )$ 在预测范围上是 $L$-Lipschitz，经 Rademacher 收缩引理公理库Rademacher 收缩引理Rademacher contraction lemma · Ledoux–Talagrand contraction principle逐坐标 Lipschitz 变换至多按 Lipschitz 常数放大标量函数类的 Rademacher 复杂度。，损失类复杂度至多为 $LBR/\sqrt{m}$。因此总体风险由经验风险加上 $O(LBR/\sqrt{m}+\sqrt{\log \left(1/\delta \right)/m})$ 控制。这里用到了真实的范数和数据半径，不是把“参数个数”机械塞进公式。

失效边界与相邻方法 ​

平方损失在无界预测范围上无界且非全局 Lipschitz，本页两个关键步骤——单点变化至多 $1/m$ 与有界差分集中——都失效。此时应先限制预测/标签范围，或使用次高斯、截断、方差敏感的经验过程工具，不能只把 $[0,1]$ 删除。

$F$ 必须在看见样本前固定，或有额外条件保证数据依赖不会泄漏到复杂度选择中。该界与 VC 界同为一致控制，但 Rademacher 复杂度可响应实际样本几何并直接处理实值类；它不是某个单模型的“复杂度分数”，也不自动给无界深网一个有限保证。

参考资料

• Peter Bartlett and Shahar Mendelson, “Rademacher and Gaussian Complexities: Risk Bounds and Structural Results,” 2002.
• Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning.