Rademacher 复杂度

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

Rademacher 复杂度依样本和函数值幅度衡量类与随机符号的相关性，能给数据依赖界；VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。以二元打散能力给分布无关的组合维数。VC 维可上界某些 Rademacher 复杂度，但两者不是逐实例相同的数。

线性类的计算 ​

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

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

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

一个可以枚举完的函数类 ​

令 $\mathcal{F}=\{f_{+},f_{-}\}$，其中 $f_{+}(z)=1$、$f_{-}(z)=-1$。对任意样本，

当 $m=2$ 时，符号和为 $2,0,0,-2$，各以概率 $1/4$ 出现，所以经验复杂度为

即使函数不读取数据点，类仍可在两个相反常数之间配合随机符号；随着 $m$ 增加，归一化符号和的典型量级降为 $m^{-1/2}$。

与泛化的关系 ​

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

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

边界与约定 ​

经验复杂度随 $S$ 随机，期望复杂度还依赖分布 $D$。有些文献在 supremum 内加入绝对值；若 $\mathcal{F}=-\mathcal{F}$，取负对称性会把单边上确界自动变成绝对值版本。

把整个类平移同一个固定常数 $c$ 不改变复杂度，因为附加项 $c{m}^{-1}\sum _i{\sigma }_i$ 对符号的期望为零。但若类包含所有可任意选择的常数函数，且常数无界，上确界会在符号和非零时发散。中心化、包络有界性和对称闭包分别处理不同问题，不能笼统称作“平移影响”。归一化因子 $1/m$ 也不能遗漏，否则样本增大时量级会反向增长。

对称化把类上的期望泛化间隙转成 Rademacher 过程，收缩引理再把 Lipschitz 损失类的复杂度归约到 score 类。结合有界差分即可得到数据依赖的高概率泛化界。

覆盖数与 Dudley 熵积分可从多尺度几何上界这一复杂度；局部 Rademacher 复杂度则只考察低风险邻域，并在 Bernstein 条件下产生快于 $m^{-1/2}$ 的速率。