Rademacher 收缩引理

标量收缩形式 ​

令 $A\subseteq {\mathbb{R}}^m$，${\sigma }_1,\dots ,{\sigma }_m$ 为独立 Rademacher 符号。对每个坐标，设 ${\varphi }_i:\mathbb{R}\to \mathbb{R}$ 满足 ${\varphi }_i(0)=0$ 且是 $L$-Lipschitz。采用不带外层绝对值的 Rademacher 上确界时，收缩引理的一种规范形式为

$${\mathbb{E}}_{\sigma }\underset{a\in A}{sup}\sum _{i=1}^m{\sigma }_i{\varphi }_i(a_i)\le L{\mathbb{E}}_{\sigma }\underset{a\in A}{sup}\sum _{i=1}^m{\sigma }_i{a}_i.$$

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

$${\hat{\mathfrak{R}}}_S(\varphi \circ F)\le L{\hat{\mathfrak{R}}}_S(F).$$

若定义在上确界外带绝对值，或类不对称且同时控制双边偏差，常见版本会多一个因子 $2$。${\varphi }_i(0)=0$ 可由中心化实现：固定偏移在对随机符号取期望时不携带函数类选择信息，但具体写法必须与采用的版本一致。

一坐标一坐标地证明 ​

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

$$\frac{1}{2}[\underset{a}{sup}\{u(a)+{\varphi }_m(a_m)\}+\underset{b}{sup}\{u(b)-{\varphi }_m(b_m)\}].$$

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

$${\varphi }_m(a_m)-{\varphi }_m(b_m)\le L|a_m-b_m|=\underset{s\in \{-1,1\}}{max}Ls(a_m-b_m),$$

右侧正对应线性坐标在两个符号取值下的平均上确界。重复消去 $m,m-1,\dots ,1$ 个坐标，得到结论。这个证明也解释了“收缩”的图像：非线性可以折弯数轴，却不能把任意两候选输出间的距离扩张超过 $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 泛化界公理库Rademacher 泛化界Rademacher generalization bound用样本上的 Rademacher 复杂度给出对整个有界实值函数类同时成立的数据依赖总体风险上界。，就能从预测函数的范数控制推到实际代理风险。

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

失败边界：不能混用的推广 ​

本页是逐坐标的标量定理。向量值映射、多个输出坐标共享非线性、谱范数控制的网络层需要向量收缩或专门的链式界，不能把 $L$ 机械乘上去。引理也只控制复杂度，不判断代理损失是否分类校准；后者属于 分类代理损失与校准公理库分类代理损失与校准classification calibration · classification surrogate loss说明可优化代理风险在什么条件下能够控制二分类的零一超额风险。。

参考资料

• Michel Ledoux and Michel Talagrand, Probability in Banach Spaces, contraction principles.
• Peter Bartlett and Shahar Mendelson, 2002.