Rademacher 复杂度 | Codeboy's Blog

给定一批输入点，临时给每个点贴一个完全随机的正负号。然后允许从函数类中挑选最配合这些符号的函数：能否在正号处给高分，在负号处给低分？Rademacher 复杂度衡量的，就是函数类对无规律噪声的适配能力。

它不是统计一个模型有多少参数，而是观察这类函数在实际样本点上能够形成怎样的取值向量。函数数目无限的类，也可能因范数约束而具有很小的复杂度；能够随意记住样本符号的类，则会得到很大的复杂度。这种“拟合噪声”的能力，经由对称化，恰好控制经验平均与总体平均之间的偏差。[1][2]

形式陈述

定义里，谁先随机，谁后选择

设 $\mathcal F$ 是一个非空实值函数类，样本点为 $S=(z_1,\ldots,z_m)$ 。令 $\sigma_1,\ldots,\sigma_m$ 独立，且各以概率 $1/2$ 取 $+1$ 或 $-1$ 。经验 Rademacher 复杂度定义为

\widehat{\mathfrak R}_S(\mathcal F) =E_\sigma\!\left[ \sup_{f\in\mathcal F}\frac1m\sum_{i=1}^m\sigma_i f(z_i) \right].

顺序不能交换：先固定样本，再产生符号，接着针对这组符号选函数，最后对符号平均。若把 $\sup$ 移到期望外面，每个固定函数的带符号平均期望都是零，就丢掉了函数类“事后选择”的能力。

经验定义只需要一组给定的点，不要求这些点独立同分布。若进一步令 $S\sim P^m$ ，则分布相关的复杂度是

\mathfrak R_m(\mathcal F) =E_{S\sim P^m}\widehat{\mathfrak R}_S(\mathcal F).

这里有两层不同随机性：内层是人为添加的独立符号，外层才是数据抽样。后面的泛化定理会使用独立同分布假设，但不应把它误写成经验复杂度的定义条件。

固定样本时，符号只有 $2^m$ 种组合；只要函数类在每个样本点的取值一致有界，这个有限平均就有有限值。把样本也视为随机变量后，还需要上确界具有可测性，例如函数类可数，或满足通常的可分性条件。以下泛化结论默认满足这一条件。

本文采用 $1/m$ 归一化、上确界内不加绝对值的约定。有些文献使用 $2/m$ ，或对相关和取绝对值；引用常数时必须先换算。[3] 对于关于正负号对称的函数类，加绝对值不会改变上确界；一般函数类则不同。准确地说，把 $\mathcal F$ 扩成 $\mathcal F\cup(-\mathcal F)$ 后，不带绝对值的上确界才等于原类带绝对值的上确界。因此 Bartlett–Mendelson 原文的数值等于本文对这个对称化函数类所得数值的两倍；若原类本已对称，才可只乘以二。

直觉

为什么随机符号会控制泛化误差

现在假设 $\mathcal F$ 在抽样前固定，所有函数值都落在 $[0,1]$ ，且 $S\sim P^m$ 。记

Pf=E_{Z\sim P}f(Z),\qquad P_mf=\frac1m\sum_i f(z_i).

在通常的可测性条件下，对任意 $0<\delta<1$ ，以至少 $1-\delta$ 的概率，同时对所有 $f\in\mathcal F$ 有

\boxed{ Pf\le P_mf+2\widehat{\mathfrak R}_S(\mathcal F) +3\sqrt{\frac{\log(2/\delta)}{2m}}. }

对称地控制两个方向并作一次并合界，可得一个方便的双侧版本：

\sup_{f\in\mathcal F}|Pf-P_mf| \le2\widehat{\mathfrak R}_S(\mathcal F) +3\sqrt{\frac{\log(4/\delta)}{2m}}.

这里的常数与本文的归一化一致。[1][2] 双侧版本并非简单地在单侧公式左边加上绝对值而保持所有参数不变。

证明的组织结构是“另一份样本—随机交换—浓缩”。引入独立的幽灵样本 $S'\sim P^m$ ，令 $\Phi(S)=\sup_f(Pf-P_mf)$ 。通过把期望移到上确界外面，

E_S\Phi(S) \le E_{S,S'}\sup_f\frac1m\sum_i\bigl(f(z_i')-f(z_i)\bigr).

每对 $(z_i,z_i')$ 的联合分布对交换二者不变，所以可以独立随机交换这些样本对，也就是在差值前加上 $\sigma_i$ 。将上确界下的差分拆为两部分后，得到

E_S\Phi(S)\le2\mathfrak R_m(\mathcal F).

这一步就是对称化：总体与样本的差异，被转成对称噪声下的选择能力。

最后，替换一个样本点最多让 $\Phi(S)$ 改变 $1/m$ ，也最多让 $\widehat{\mathfrak R}_S(\mathcal F)$ 改变 $1/m$ 。对这两个量分别使用有界差分不等式并合并失败概率，就得到上面的经验复杂度界。常数 $3$ 来自这两次浓缩，而不是噪声拟合直觉本身。

例子与边界

两个样本就能看出选择能力

设 $\mathcal F=\{f_+,f_-\}$ ，其中 $f_+\equiv1,f_-\equiv-1$ ，并取 $m=2$ 。四种符号组合的最优得分如下：

$(\sigma_1,\sigma_2)$	$(+,+)$	$(+,-)$	$(-,+)$	$(-,-)$
$\sup_f \frac12\sum_i\sigma_i f(z_i)$	1	0	0	1

所以 $\widehat{\mathfrak R}_S(\mathcal F)=1/2$ 。这个类只能整体选择正号或负号，不能分别满足相反的两个符号。

若样本点互不相同，而函数类能够在它们上实现任意 $\{-1,+1\}$ 标记，那么对每一组符号都可选 $f(z_i)=\sigma_i$ ，最优得分恒为 $1$ 。此时复杂度达到这一取值范围下的最大值。若两个样本点完全相同，函数在该点只能取一个值，就不能再分别拟合两个相反符号。

另一个有辨识力的端点是单函数类： $\mathcal F=\{f_0\}$ 时，经验复杂度等于零。它没有事后挑选的余地。这并不说明 $f_0$ 的经验均值必定等于真实均值；单个函数的抽样波动由泛化界中的浓缩项控制。若取单函数 $f_0\equiv1$ 与 $m=1$ ，本文定义给 $E_\sigma[\sigma]=0$ ，而带绝对值的定义给 $E_\sigma|\sigma|=1$ ；再使用原论文的 $2/m$ 归一化，则为 $2$ 。这个最小算例表明两种约定对非对称类的区别绝非总是一个固定倍数。

对两个常数函数，四组符号的最优得分为 1、0、0、1，因此经验复杂度为 1/2。

线性函数类：为什么范数比参数个数更直接

考虑

\mathcal F_B=\{x\mapsto\langle w,x\rangle:\|w\|_2\le B\}.

固定 $x_1,\ldots,x_m$ 后，由欧氏范数的对偶性，

\begin{aligned} \widehat{\mathfrak R}_S(\mathcal F_B) &=\frac1m E_\sigma \sup_{\|w\|_2\le B}\left\langle w,\sum_i\sigma_i x_i\right\rangle\\ &=\frac Bm E_\sigma\left\|\sum_i\sigma_i x_i\right\|_2. \end{aligned}

当向量和非零时，最优 $w$ 沿着它的方向；因此第一个看似困难的函数优化，变成了一个随机向量长度的平均。再用 Cauchy–Schwarz 不等式与符号的独立性，

\begin{aligned} E_\sigma\left\|\sum_i\sigma_i x_i\right\|_2 &\le\sqrt{E_\sigma\left\|\sum_i\sigma_i x_i\right\|_2^2}\\ &=\sqrt{\sum_i\|x_i\|_2^2}. \end{aligned}

交叉项消失，是因为 $i\ne j$ 时 $E[\sigma_i\sigma_j]=0$ 。若每个样本满足 $\|x_i\|_2\le R$ ，得到

\boxed{\widehat{\mathfrak R}_S(\mathcal F_B)\le\frac{BR}{\sqrt m}.}

这个上界没有显式出现空间维数；约束的是权重长度与数据长度的乘积。维数仍可能通过 $B,R$ 或数据几何间接进入，不能把“公式中没有维数”理解为一切高维效应都消失了。

该界有时能精确达到。若 $x_1,\ldots,x_m$ 两两正交且长度均为 $R$ ，那么无论符号怎样变化，向量和的长度始终是 $R\sqrt m$ ，故等号成立。这也说明 $m^{-1/2}$ 并不只是推导松弛的产物。

一个会让泛化论证失效的“事后缩小”

训练后已经选出了一个函数，不能再说“候选类只剩它一个，复杂度为零，所以没有过拟合”。定理允许算法在一个预先固定的类中依赖数据选函数；它没有允许用同一份数据随意重定义整个候选类，然后忽略这种选择过程。

取 $[0,1]$ 上的均匀输入分布，在看到 $S$ 后定义

f_S(z)=\mathbf1\{z\notin\{z_1,\ldots,z_m\}\}.

这个函数在训练点上的均值为零，在总体上的均值却为一。事后单函数类 $\{f_S\}$ 的经验 Rademacher 复杂度仍为零。如果忽略“函数类在抽样前固定”这一条件，就会错误地推出二者差异很小。

这并不排除数据依赖的复杂度理论，而是说明它需要独立验证集、条件化论证或专门的数据依赖界。实践中也应避免把某一模型的数值复杂度估计，当作一个未经核对条件的测试误差保证。

推论与应用

有限函数类：从指数矩得到对数依赖

设 $\mathcal F$ 含 $N\ge2$ 个函数，且每个取值向量满足

\sum_{i=1}^m f(z_i)^2\le r^2.

Massart 有限类引理给出

\widehat{\mathfrak R}_S(\mathcal F) \le\frac r m\sqrt{2\log N}.

其核心很短。记 $Z_f=\sum_i\sigma_i f(z_i)$ 。独立符号与 $\cosh t\le e^{t^2/2}$ 给出 $E e^{\lambda Z_f}\le e^{\lambda^2r^2/2}$ 。再把最大值放入指数函数，用最大项不超过总和以及 Jensen 不等式，得到

E\max_f Z_f \le\frac{\log N}{\lambda}+\frac{\lambda r^2}{2}.

对 $\lambda>0$ 优化即得结论； $r=0$ 时直接为零。若 $N=1$ ，复杂度同样为零。特别地， $|f(z_i)|\le1$ 时可取 $r\le\sqrt m$ ，于是得到 $\sqrt{2\log N/m}$ 。

这条界说明有限候选数量以 $\log N$ 而不是 $N$ 进入代价。相比之下，线性类的范数推导直接利用几何结构，无须先把无限多个函数离散化成有限列表。

从预测器类转到损失类

泛化界最终控制的是损失。例如预测器为 $h$ ，样本为 $z=(x,y)$ ，应使用

\mathcal L_{\mathcal H} =\{(x,y)\mapsto\ell(h(x),y):h\in\mathcal H\}.

预测分数的函数类与损失类并不相同。若固定标签后的映射 $a\mapsto\ell(a,y_i)$ 是 $L$ -Lipschitz，则适当形式的收缩引理允许把损失类复杂度控制为预测器类复杂度的 $L$ 倍。与函数选择无关的平移项，在符号期望中为零；不同绝对值约定下的收缩引理常数仍需重新核对。

对于 $\{-1,+1\}$ 分类器，零一损失还有一个直接关系：

\mathbf1_{h(x)\ne y}=\frac{1-yh(x)}2.

固定标记样本后， $\sigma_i y_i$ 仍是独立对称符号，故损失类的经验复杂度是相应预测器类的二分之一。这是由标签取值与特定损失公式产生的关系，不能推广成所有损失都自动除以二。

与其他容量概念的关系

VC 维描述二值函数类在最有利点集上的打散能力；经验 Rademacher 复杂度直接依赖当前样本上的取值几何，既能处理二值函数，也能处理实值分数。它们并非相互替代：VC 维可通过增长函数推导 Rademacher 上界，而范数、间隔和局部几何常能给出比粗粒度计数更有针对性的控制。

阅读顺序可以从本条目的符号实验与线性类计算出发，再进入对称化、收缩引理与局部 Rademacher 理论。最重要的检查始终是：正在度量哪个类、采用什么归一化、样本如何产生，以及这条界最终约束的是哪一种损失。

定义中的样本是允许重复的有序序列；经验复杂度的求和按样本位置计数。

参考资料

[1] Mehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., MIT Press, 2018，第 3 章。作者教材入口。

[2] Mehryar Mohri, Learning with Infinite Hypothesis Sets，课程讲义，经验复杂度、单侧泛化界、对称化证明及有限类引理。讲义。

[3] Peter L. Bartlett and Shahar Mendelson, “Rademacher and Gaussian Complexities: Risk Bounds and Structural Results”, JMLR 3, 463–482, 2002。原论文。该文的定义使用不同的归一化与绝对值约定，阅读时应与本文区分。

形式陈述 ​

定义里，谁先随机，谁后选择 ​

为什么随机符号会控制泛化误差 ​

两个样本就能看出选择能力 ​

线性函数类：为什么范数比参数个数更直接 ​

一个会让泛化论证失效的“事后缩小” ​

有限函数类：从指数矩得到对数依赖 ​

从预测器类转到损失类 ​

与其他容量概念的关系 ​

反向链接