Rademacher 复杂度

定义 ​

给定样本 $S=(Z_1,\dots ,Z_m)$ 与实值函数类 $\mathcal{F}$，经验 Rademacher 复杂度定义为

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

其中 ${\sigma }_i$ 独立且等概率取 $\pm 1$。总体样本复杂度是

$${\mathfrak{R}}_m(\mathcal{F})={\mathbb{E}}_{S\sim D^m}{\hat{\mathfrak{R}}}_S(\mathcal{F}).$$

全库采用上式不额外乘 $2$ 的 convention；引用采用其他归一化的定理时，常数必须随之换算。

概念图像 ​

固定输入点后，${\sigma }_i$ 是完全没有规律的随机标签。若类仍能让带符号和很大，它就能追逐样本噪声；若所有函数在这些点上的取值受共同结构约束，正负贡献大多抵消。它度量的是一个函数类相对于样本的丰富度，不是某个已训练模型的“复杂分数”。

线性类的计算 ​

设 $\mathcal{F}=\{x\mapsto ⟨w,x⟩:\Vert w{\Vert }_2\le B\}$。由对偶范数与 Cauchy–Schwarz，

$${\hat{\mathfrak{R}}}_S(\mathcal{F})=\frac{B}{m}{\mathbb{E}}_{\sigma }{\Vert \sum _i{\sigma }_i{x}_i\Vert }_2.$$

再用 Jensen 与符号独立性消去交叉项，

$${\hat{\mathfrak{R}}}_S(\mathcal{F})\le \frac{B}{m}\sqrt{\sum _i\Vert x_i{\Vert }_2^2}.$$

若每个 $\Vert x_i{\Vert }_2\le R$，便得到 $BR/\sqrt{m}$。这个推导展示复杂度同时依赖范数半径和实际数据几何，而不只依赖参数个数。

与泛化的关系 ​

对称化公理库对称化与 Ghost Samplesymmetrization · ghost sample用独立幽灵样本和随机符号，把未知总体均值偏差化为可分析的经验过程。通常给出

$$\mathbb{E}\underset{f\in \mathcal{F}}{sup}(Pf-P_{m}f)\le 2{\mathfrak{R}}_m(\mathcal{F}),$$

随后再用集中不等式得到高概率界。若学习损失是 $\varphi \circ f$，必须先证明 contraction 条件，例如 $\varphi$ 为 Lipschitz；不能把 score 类的复杂度直接当作无界 log-loss 类的复杂度。

边界与约定 ​

经验复杂度随 $S$ 随机，总体复杂度还依赖分布 $D$。有些文献在 supremum 内加入绝对值，或假设类关于取负对称；两者可能带来常数差。若类包含任意常数平移，单边定义会受平移影响，因此常先中心化或使用对称闭包。归一化因子 $1/m$ 不能遗漏，否则样本增大时量级会反向增长。

参考资料

• Peter L. Bartlett, Shahar Mendelson, Rademacher and Gaussian Complexities, JMLR, 2002.
• Mehryar Mohri et al., Foundations of Machine Learning, 2nd ed., MIT Press, 2018.