局部 Rademacher 复杂度

形式陈述 ​

全局 Rademacher 复杂度对整个函数类取上确界，无论其中的函数离最优解多远。经验风险最小化真正可能输出的却通常只是低经验风险区域。若远处函数极其丰富、近最优区域相当规整，全局界会让这些不可能胜出的函数抬高所有候选的复杂度，最终只得到常见的 $m^{-1/2}$ 速率。

局部化的想法是让统计半径与复杂度互相约束：先只看方差、$L_2(P)$ 距离或超额风险不超过 $r$ 的函数，再计算该小类的Rademacher 复杂度理路Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity通过拟合随机符号理解函数类复杂度，推导线性类、有限类和泛化界，并说明损失类与数据依赖选择的区别。；若复杂度本身小于 $r$，便能证明学习器不会逃出这个半径。最小的自洽半径形成不动点。

一种标准定义 ​

令 $F$ 是非空预测器类，对每个 $f$ 有可测损失函数 ${\ell }_f(z)\in [0,1]$。记 $Pg=E_{Z\sim P}g(Z)$，并假定类内最小风险由 $f^{\ast }\in \arg \underset{f\in F}{min}P{\ell }_f$ 取得。相应的超额损失类理路超额风险与误差分解Excess risk · Error decomposition把相对最优决策的风险差拆成逼近、估计和优化来源。为

取 $m\ge 1$ 个 IID 观测，假定下述上确界可测，例如各局部类有固定可数决定子类。对 $r>0$，可按二阶矩定义局部子类

这里选用 Rademacher 复杂度页的分布相关版本：先对给定样本的随机符号取平均，再对 $S\sim P^m$ 取平均。相应的期望局部复杂度为

也可用 $Pg\le r$、经验二阶矩或到 $f^{\ast }$ 的 $L_2(P)$ 距离定义局部集合。不同版本不能无条件互换；从风险半径转成方差半径需要曲率或 Bernstein 条件。

次根函数与不动点 ​

分析常用一个非负、单调非减的上界函数 $\psi (r)$ 满足

并要求 $\psi (r)/\sqrt{r}$ 随 $r$ 非增。这类函数称为 sub-root function。若存在唯一正不动点 $r^{\ast }$ 使

那么 $r^{\ast }$ 给出统计误差的自然尺度：在补上方差—均值桥梁和集中条件后，以 $r^{\ast }$ 定标的足够大壳层上，随机波动才会小于确定性超额风险，从而排除坏候选。

例如再有固定 $B\ge 1$ 使所有 $g\in \mathcal{L}$ 满足 $P{g}^2\le BPg$，并让非零次根函数 $\psi$ 上界 $B{\mathfrak{R}}_m(\mathcal{L}(r))$。此时经典局部复杂度定理给出如下量级：若输出 $\hat{f}\in F$ 满足 $P_m{\ell }_{\hat{f}}\le \underset{f\in F}{inf}{P}_m{\ell }_f+\eta$，则以至少 $1-\delta$ 的概率

这里 $0<\delta <1$、$\eta \ge 0$，隐含常数允许依赖 $B$；精确 ERM 对应 $\eta =0$。只给局部复杂度定义而没有方差—均值条件，不能推出这一快界。