Dudley 熵积分 | Codeboy's Blog

形式陈述

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

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

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

\mathbb E\sup_{t\in T}(X_t-X_{t_0}) \le C\int_0^{\operatorname{diam}(T,d)} \sqrt{\log N(\varepsilon,T,d)}\,d\varepsilon,

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

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

\mathbb E\sup_{t\in T}(X_t-X_{t_0}) \le C\left[ \alpha+\int_\alpha^{\operatorname{diam}(T,d)} \sqrt{\log N(\varepsilon,T,d)}\,d\varepsilon \right],

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

直觉

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

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

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

X_t-X_{t_0} =\sum_{j\ge1}\bigl(X_{\pi_j(t)}-X_{\pi_{j-1}(t)}\bigr),

其中 $\pi_j(t)$ 是 $t$ 在第 $j$ 层的近邻。

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

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

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

例子与边界

Rademacher 过程中的版本

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

X_f=\frac1m\sum_{i=1}^m\sigma_i f(x_i),

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

d_S(f,g)=\left(\frac1{m^2}\sum_{i=1}^m(f(x_i)-g(x_i))^2\right)^{1/2}

具有次高斯增量。因此 Dudley 界可把经验Rademacher 复杂度控制为 $F$ 在样本度量下的覆盖熵积分。若改用常见的经验 $L_2$ 度量 $d_{S,2}$ ，公式外会显式出现 $1/\sqrt m$ 。

例如，若

\log N(\varepsilon,F,d_{S,2})\lesssim d\log(A/\varepsilon),

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

不能省略的假设

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

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

推论与应用

覆盖数描述确定性几何，Dudley 定理把它转成随机上确界；Rademacher 泛化界再把随机上确界转成风险偏差。三步的假设各不相同：函数类有小 cover、过程增量次高斯、损失和抽样协议允许泛化归约。任何一步失效，都不能靠下一步的公式补救。

局部化时，只对围绕低风险解的子类计算熵积分，可进入局部 Rademacher 复杂度和 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, Springer, 1991, Chapter 11.
Peter L. Bartlett and Shahar Mendelson, “Rademacher and Gaussian Complexities,” JMLR, 2002.

形式陈述 ​

Rademacher 过程中的版本 ​

不能省略的假设 ​

反向链接

形式陈述

Rademacher 过程中的版本

不能省略的假设