Rademacher 收缩引理 | Codeboy's Blog

形式陈述

设 $m\ge1$ ， $A\subseteq\mathbb R^m$ 为非空有界集合，以保证下述有限符号平均为有限值。 $\sigma_1,\ldots,\sigma_m$ 为独立 Rademacher 符号。对每个坐标，设 $\phi_i:\mathbb R\to\mathbb R$ 满足 $\phi_i(0)=0$ 且具有$L$-Lipschitz 连续性。采用Rademacher 复杂度的不带外层绝对值版本时，收缩引理的一种规范形式为

\mathbb E_\sigma\sup_{a\in A}\sum_{i=1}^m\sigma_i\phi_i(a_i) \le L\,\mathbb E_\sigma\sup_{a\in A}\sum_{i=1}^m\sigma_i a_i.

取 $A=\{(f(Z_1),\ldots,f(Z_m)):f\in F\}$ 并除以 $m$ ，便有

\widehat{\mathfrak R}_S(\phi\circ F)\le L\widehat{\mathfrak R}_S(F).

若改用 $\mathbb E_\sigma\sup_{a\in A}|\sum_i\sigma_i a_i|$ 的绝对值版本，或类不对称且同时控制双边偏差，常见版本会多一个因子 $2$ 。 $\phi_i(0)=0$ 可由中心化实现：固定偏移在对随机符号取期望时不携带函数类选择信息，但具体写法必须与采用的版本一致。

一坐标一坐标地证明

核心只需证明把最后一个坐标 $a_m$ 换成 $\phi_m(a_m)$ 不会放大期望超过 $L$ 。条件于前 $m-1$ 个符号，记其贡献为 $u(a)$ 。对 $\sigma_m$ 平均后，左侧成为

\frac12\left[\sup_a\{u(a)+\phi_m(a_m)\}+\sup_b\{u(b)-\phi_m(b_m)\}\right].

把两个上确界同时放大到对 $(a,b)$ 的上确界，出现 $\phi_m(a_m)-\phi_m(b_m)$ 。Lipschitz 性给

\phi_m(a_m)-\phi_m(b_m)\le L|a_m-b_m| =\max_{s\in\{-1,1\}}Ls(a_m-b_m),

右侧正对应线性坐标在两个符号取值下的平均上确界。重复消去 $m,m-1,\ldots,1$ 个坐标，得到结论。这个证明也解释了“收缩”的图像：非线性可以折弯数轴，却不能把任意两候选输出间的距离扩张超过 $L$ 倍。

直觉

随机符号过程只关心候选输出之间能拉开多远。Lipschitz 变换至多按 $L$ 倍扩张任意两点距离，因此不会凭非线性创造新的拟合随机符号能力；逐坐标证明把这一直觉精确落实到上确界中。

例子与边界

Hinge 与 logistic 损失

二元标签 $y\in\{-1,1\}$ ，score 为 $s=f(x)$ 。hinge 损失 $\ell_y(s)=\max(0,1-ys)$ 是 $1$ -Lipschitz；减去常数 $\ell_y(0)=1$ 后可直接应用引理。因此 hinge 损失类的经验 Rademacher 复杂度不超过 score 类。logistic 损失 $\log(1+e^{-ys})$ 的导数绝对值不超过 $1$ ，同样成立。结合 Rademacher 泛化界，就能从预测函数的范数控制推到实际代理风险。

平方损失 $(y-s)^2$ 的导数为 $2(s-y)$ ，在整条实线上没有统一 Lipschitz 常数。若 $|s|\le B$ 、 $|y|\le Y$ ，才可在该范围取 $L=2(B+Y)$ ；没有范围约束时直接声称“收缩后至多乘 2”是错误的。

不能混用的推广

本页是逐坐标的标量定理。向量值映射、多个输出坐标共享非线性、谱范数控制的网络层需要向量收缩或专门的链式界，不能把 $L$ 机械乘上去。引理也只控制复杂度，不判断代理损失是否分类校准；后者属于分类代理损失与校准。

推论与应用

把 score 类先按范数或核几何控制，再用收缩引理穿过 hinge、logistic 等 Lipschitz 损失，就得到损失类的 Rademacher 泛化界。平方损失只有在预测和标签范围受限后才进入这条链。

深层组合需要逐层追踪 Lipschitz 常数、范数与向量收缩结构；简单相乘可能给出合法但极松的界，也可能因共享坐标而根本不适用。应用时应先核对定理版本的绝对值与对称性 convention。

参考资料

Michel Ledoux and Michel Talagrand, Probability in Banach Spaces: Isoperimetry and Processes, Springer, 1991, Ch. 4, Theorem 4.4.
Peter L. Bartlett and Shahar Mendelson, “Rademacher and Gaussian Complexities: Risk Bounds and Structural Results,” Journal of Machine Learning Research 3, 2002, pp. 463–482.

形式陈述 ​

一坐标一坐标地证明 ​

Hinge 与 logistic 损失 ​

不能混用的推广 ​

反向链接

形式陈述

一坐标一坐标地证明

Hinge 与 logistic 损失

不能混用的推广