Dudley 熵积分

定理陈述 ​

设 $(X_t{)}_{t\in T}$ 是中心化随机过程，并存在伪度量 $d$，使任意 $s,t\in T$ 与 $\lambda \in \mathbb{R}$ 满足次高斯增量条件

$$\mathbb{E}\exp (\lambda (X_t-X_s))\le \exp \left(\frac{{\lambda }^{2}d(s,t{)}^2}{2}\right).$$

若 $(T,d)$ 全有界，则对任意基点 $t_0\in T$，Dudley 界给出

$$\mathbb{E}\underset{t\in T}{sup}(X_t-X_{t_0})\le C{\int }_0^{\mathrm{diam}(T,d)}\sqrt{\log N(\epsilon ,T,d)}d\epsilon ,$$

其中 $C$ 是普适常数。不同文献会把积分上限写成直径的一半，并相应改变 $C$；核心内容是对数覆盖数的平方根在所有尺度上的累积。

当小尺度积分可能发散或只需要有限样本版本时，常用截断形式

$$\mathbb{E}\underset{t\in T}{sup}(X_t-X_{t_0})\le C[\alpha +{\int }_{\alpha }^{\mathrm{diam}(T,d)}\sqrt{\log N(\epsilon ,T,d)}d\epsilon ],$$

再对 $\alpha >0$ 优化。经验 Rademacher 过程中，最细层还可用有限样本的平凡上界替代，使截断项带上与 $m$ 有关的比例。

为什么一张网不够 ​

只选一个 $\epsilon$-cover，会把每个 $t$ 近似为单个代表。粗网代表少，却留下大的近似误差；细网误差小，但一次并集界要支付庞大的 $\log N(\epsilon )$。chaining 不在二者间二选一，而是构造逐渐变细的网

$$T_0\subset T_1\subset T_2\subset \cdots ,$$

并把每个索引写成望远镜和

$$X_t-X_{t_0}=\sum _{j\ge 1}(X_{{\pi }_j(t)}-X_{{\pi }_{j-1}(t)}),$$

其中 ${\pi }_j(t)$ 是 $t$ 在第 $j$ 层的近邻。

第 $j$ 层有更多候选增量，但每个增量的次高斯尺度也更小。对这一层取最大值的代价约为

$$2^{-j}\mathrm{diam}(T)\sqrt{\log |T_j|}.$$

把各层求和，再把 dyadic 和式比较为积分，就得到熵积分。证明的关键不是某个神奇常数，而是“细尺度只为细微修正付费”的多分辨率组织。

Rademacher 过程中的版本 ​

给定样本 $S=(x_1,\dots ,x_m)$ 与实值函数类 $F$，定义

$$X_f=\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}f(x_i),$$

其中 ${\sigma }_i$ 是独立 Rademacher 符号。条件于 $S$，Hoeffding 引理说明 $X_f-X_g$ 对经验度量

$$d_S(f,g)={(\frac{1}{m^2}\sum _{i=1}^m(f(x_i)-g(x_i){)}^2)}^{1/2}$$

具有次高斯增量。因此 Dudley 界可把经验Rademacher 复杂度公理库Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity用随机正负号衡量函数类在给定样本上拟合无结构噪声的能力。控制为 $F$ 在样本度量下的覆盖熵积分。若改用常见的经验 $L_2$ 度量 $d_{S,2}$，公式外会显式出现 $1/\sqrt{m}$。

例如，若

$$\log N(\epsilon ,F,d_{S,2})\lesssim d\log \left(A/\epsilon \right),$$

积分给出约 $A\sqrt{d/m}$ 的复杂度，而单尺度离散化往往多付一个不必要的对数。这个改进来自多尺度几何，不是把并集界常数调得更精细。

不能省略的假设 ​

覆盖数有限并不自动保证 Dudley 公式可用。首先必须建立随机过程相对于所选度量的次高斯增量；若只有重尾矩界，最大增量的尾部可能完全不同。其次要处理可分性或可测上确界，否则 $\mathbb{E}\underset{t}{sup}{X}_t$ 本身可能没有通常意义。经验学习论常通过可数稠密子类或外期望消除这一技术障碍。

熵积分是上界而非恒等式。某些集合的覆盖数估计很粗，积分就会松；对高度各向异性的过程，Talagrand 的 generic chaining 与 ${\gamma }_2$ 泛函能给更准确的几何刻画。基础学习界通常不需要引入整套 generic chaining，但不能把 Dudley 界称为任意过程上确界的精确公式。

与其他复杂度的接口 ​

覆盖数公理库度量熵与覆盖数Metric entropy · Covering number · 覆盖数在指定尺度和度量下，用有限网覆盖函数类，并以覆盖数或度量熵量化其有效大小。描述确定性几何，Dudley 定理把它转成随机上确界；Rademacher 泛化界再把随机上确界转成风险偏差。三步的假设各不相同：函数类有小 cover、过程增量次高斯、损失和抽样协议允许泛化归约。任何一步失效，都不能靠下一步的公式补救。

局部化时，只对围绕低风险解的子类计算熵积分，可进入局部 Rademacher 复杂度公理库局部 Rademacher 复杂度Local Rademacher complexity · 局部化复杂度围绕低风险或低方差函数逐层收缩函数类，以复杂度不动点刻画快于全局平方根速率的超额风险。和 fast rate。这里需要额外的方差—均值关系，而不是简单把全局 $F$ 换成一个看起来更小的集合。

参考资料

• Richard M. Dudley, “The Sizes of Compact Subsets of Hilbert Space and Continuity of Gaussian Processes,” Journal of Functional Analysis, 1967.
• Michel Ledoux and Michel Talagrand, Probability in Banach Spaces, Chapter 11.
• Peter L. Bartlett and Shahar Mendelson, “Rademacher and Gaussian Complexities,” JMLR, 2002.