局部 Rademacher 复杂度

全局界为何会浪费信息 ​

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

局部化的想法是让统计半径与复杂度互相约束：先只看方差、$L_2(P)$ 距离或超额风险不超过 $r$ 的函数，再计算该小类的 Rademacher 复杂度；若复杂度本身小于 $r$，便能证明学习器不会逃出这个半径。最小的自洽半径形成不动点。

一种标准定义 ​

令 $F$ 是实值函数类，$f^{\ast }\in \arg \underset{f\in F}{min}Pf$，并写超额损失类

$$\mathcal{L}=\{{\ell }_f-{\ell }_{f^{\ast }}:f\in F\}.$$

对 $r>0$，可按二阶矩定义局部子类

$$\mathcal{L}(r)=\{g\in \mathcal{L}:P{g}^2\le r\},$$

相应的期望局部复杂度为

$${\mathfrak{R}}_m(\mathcal{L}(r))={\mathbb{E}}_{S,\sigma }\underset{g\in \mathcal{L}(r)}{sup}\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}g(Z_i).$$

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

次根函数与不动点 ​

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

$${\mathfrak{R}}_m(\mathcal{L}(r))\le \psi (r),$$

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

$$\psi (r^{\ast })=r^{\ast },$$

那么 $r^{\ast }$ 给出统计误差的自然尺度：在大于 $r^{\ast }$ 的壳层上，随机波动小于该层的确定性超额风险，坏候选无法击败最优函数。

典型高概率结果在适当有界性和 Bernstein 条件下呈现为

$$P{\ell }_{\hat{f}}-P{\ell }_{f^{\ast }}\lesssim r^{\ast }+\frac{\log \left(1/\delta \right)}{m},$$

其中 $\hat{f}$ 是 ERM 或近似 ERM。精确常数取决于局部类、损失范围及曲率假设，本页不把不同版本压成一个看似通用的公式。

一个快速度图像 ​

有限类 $F$ 在最坏情况下的全局复杂度约为 $\sqrt{\log |F|/m}$。若超额损失满足

$$P{g}^2\le BPg,$$

则风险不超过 $r$ 的候选同时具有方差尺度 $Br$。局部最大偏差因而大致为

$$\psi (r)\asymp \sqrt{\frac{Br\log |F|}{m}}+\frac{\log |F|}{m}.$$

求解 $\psi (r)\approx r$ 得

$$r^{\ast }\asymp \frac{B\log |F|}{m},$$

比全局 $m^{-1/2}$ 速率更快。加速并非来自有限类计数本身，而是低风险同时意味着低方差；没有这条联系，局部集合可能仍保留全局波动。

证明机制 ​

局部证明通常把类按风险或方差切成几何壳层，例如 $2^j{r}^{\ast }<Pg\le 2^{j+1}{r}^{\ast }$。每一层上用 symmetrization 与 Rademacher 复杂度控制经验偏差，再对层数取并集界。因为 $\psi (r)/\sqrt{r}$ 递减，半径越大，确定性信号相对于随机噪声越强。最终排除所有远离最优解却经验上更优的函数。

实际应用还需要把不可观测的总体局部类换成经验可计算版本。常见定理证明经验不动点与总体不动点以高概率相互控制；这一步依赖有界差分或集中不等式，不能把从同一数据算出的随机半径直接当作确定阈值。

边界 ​

局部复杂度不是把全局公式中的 $F$ 手工替换为“看起来不错的模型邻域”。邻域必须由学习问题的风险、方差或可验证经验量定义，并证明输出确实留在其中。若损失重尾、最优解不唯一，或风险在最优集附近近乎平坦，不动点可能仍是 $m^{-1/2}$ 量级。

“fast rate”也不是优化收敛更快。它描述样本数增加时的统计超额风险公理库超额风险与误差分解Excess risk · Error decomposition把相对最优决策的风险差拆成逼近、估计和优化来源。，而非梯度法迭代次数。优化误差若大于 $r^{\ast }$，会遮住局部统计收益，必须在近似 ERM 分解中另行保留。

参考资料

• Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson, “Local Rademacher Complexities,” Annals of Statistics, 2005.
• Vladimir Koltchinskii, Oracle Inequalities in Empirical Risk Minimization, 2011.
• Martin Wainwright, High-Dimensional Statistics, localized complexity chapters.