形式陈述
令 A ⊆ R m σ 1 , … , σ m ϕ i : R → R ϕ i ( 0 ) = 0 $L$-Lipschitz 连续性 公理库 Lipschitz 连续 Lipschitz continuity · Lipschitz condition 用统一常数定量限制函数输出距离相对于输入距离的增长。 Rademacher 复杂度 公理库 Rademacher 复杂度 Rademacher complexity · empirical Rademacher complexity 用随机正负号衡量函数类在给定样本上拟合无结构噪声的能力。
E σ sup a ∈ A ∑ i = 1 m σ i ϕ i ( a i ) ≤ L E σ sup a ∈ A ∑ i = 1 m σ i a i . 取 A = { ( f ( Z 1 ) , … , f ( Z m ) ) : f ∈ F } m
R ^ S ( ϕ ∘ F ) ≤ L R ^ S ( F ) . 若定义在上确界外带绝对值，或类不对称且同时控制双边偏差，常见版本会多一个因子 2 ϕ i ( 0 ) = 0
一坐标一坐标地证明
核心只需证明把最后一个坐标 a m ϕ m ( a m ) L m − 1 u ( a ) σ m
1 2 [ sup a { u ( a ) + ϕ m ( a m ) } + sup b { u ( b ) − ϕ m ( b m ) } ] . 把两个上确界同时放大到对 ( a , b ) ϕ m ( a m ) − ϕ m ( b m )
ϕ m ( a m ) − ϕ m ( b m ) ≤ L | a m − b m | = max s ∈ { − 1 , 1 } L s ( a m − b m ) , 右侧正对应线性坐标在两个符号取值下的平均上确界。重复消去 m , m − 1 , … , 1 L
直觉 随机符号过程只关心候选输出之间能拉开多远。Lipschitz 变换至多按 L
例子与边界 Hinge 与 logistic 损失
二元标签 y ∈ { − 1 , 1 } s = f ( x ) ℓ y ( s ) = max ( 0 , 1 − y s ) 1 ℓ y ( 0 ) = 1 log ( 1 + e − y s ) 1 Rademacher 泛化界 公理库 Rademacher 泛化界 Rademacher generalization bound 用样本上的 Rademacher 复杂度给出对整个有界实值函数类同时成立的数据依赖总体风险上界。
平方损失 ( y − s ) 2 2 ( s − y ) | s | ≤ B | y | ≤ Y L = 2 ( B + Y )
不能混用的推广
本页是逐坐标的标量定理。向量值映射、多个输出坐标共享非线性、谱范数控制的网络层需要向量收缩或专门的链式界，不能把 L 分类代理损失与校准 公理库 分类代理损失与校准 classification calibration · classification surrogate loss 说明可优化代理风险在什么条件下能够控制二分类的零一超额风险。
推论与应用 把 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.
