形式陈述
设 是由有界损失公理库损失函数与总体风险Loss function · Population risk · Expected risk损失刻画一次决策的代价，总体风险是未知分布下的平均代价。组成、从 到 的固定函数类，。采用Rademacher 复杂度公理库Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity用随机正负号衡量函数类在给定样本上拟合无结构噪声的能力。
其中 是独立均匀的 符号。则在可测性条件下，以至少 的概率，同时对所有 有
把未知的期望复杂度换成样本可计算的经验复杂度，一种常用版本是
不同文献若在复杂度定义中预先放入 ，定理前的系数会相应变化；不能只换定义而保留常数。
从总体偏差到随机符号
考察单边偏差
引入独立 ghost sample ，Jensen 不等式与对称化公理库对称化与 Ghost Samplesymmetrization · ghost sample用独立幽灵样本和随机符号，把未知总体均值偏差化为可分析的经验过程。依次给出
第二步利用每对 可交换：乘上随机符号不会改变联合分布，再把两个符号和分别以上确界控制。此处得到的是整个类的期望最大偏差，而非单个训练后模型的事后估计。
替换 中一个观测时，每个 至多变化 ，所以上确界 也至多变化 。有界差分不等式公理库有界差分不等式McDiarmid inequality · 有界差异不等式独立输入的函数若对单个坐标不敏感，其输出便以次高斯速度集中在期望附近。把期望提升为第一条高概率界。经验复杂度本身对单点替换也至多变化 ，再做一次集中并合并失败事件，得到第二条完全数据依赖的版本。
直觉
上界把泛化代价拆成两部分：函数类在当前样本上拟合随机符号的能力，以及把随机上确界从期望提升到高概率所付的集中项。经验版本因直接读取样本几何而可计算，却还要为自身随机波动再支付一次集中常数。
例子与边界
线性预测器经过损失后的真例
设 score 类
对固定输入样本，Cauchy–Schwarz 给
若损失 在预测范围上是 -Lipschitz，并把每个 上的损失减去与 无关的 ，则Rademacher 收缩引理公理库Rademacher 收缩引理Rademacher contraction lemma · Ledoux–Talagrand contraction principle逐坐标 Lipschitz 变换至多按 Lipschitz 常数放大标量函数类的 Rademacher 复杂度。给出中心化损失类的复杂度至多 。对固定样本，把 加回每个函数只增加一个公共符号和，其关于 的期望为零，所以原损失类具有相同的经验 Rademacher 复杂度。若原损失值还被归一化到 ，本页定理得到
同时对所有 成立。这里使用真实范数、数据半径和 Lipschitz 常数，而不是把参数个数机械塞进公式。
例如 、、 时，期望复杂度项至多 ，集中项为
因此该版本给出的统一风险附加量约为 。这是充分上界，不表示每个样本都恰好出现同样大小的 gap。
失效边界与相邻方法
平方损失在无界预测范围上无界且非全局 Lipschitz，本页两个关键步骤——单点变化至多 与有界差分集中——都失效。此时应先限制预测/标签范围，或使用次高斯、截断、方差敏感的经验过程工具，不能只把 删除。
必须在看见样本前固定，或有额外条件保证数据依赖不会泄漏到复杂度选择中。该界与 VC 界同为一致控制，但 Rademacher 复杂度可响应实际样本几何并直接处理实值类；它不是某个单模型的“复杂度分数”，也不自动给无界深网一个有限保证。
推论与应用
配合收缩引理，范数受限线性 score 类可转成 hinge、logistic 等代理损失的风险界；配合 Dudley 熵积分，则可由多尺度覆盖数控制复杂度。两条路线分别利用代数几何和度量几何。
局部化只对低风险或低方差子类重复这套论证，并用不动点给出快速度。若数据重尾或类由样本选择，应使用相应的稳健集中、条件复杂度或独立选择协议，而不是删除有界性假设。
参考资料
- 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, 2nd ed., MIT Press, 2018.
