压缩学习的风险估计达到大数定律收敛速率

压缩框架下的泛化风险新结果

压缩方案（compression schemes）是推导学习算法数据依赖型风险界的一个通用框架。它的核心思想是：如果一个学习算法可以用一小部分训练样本来"压缩"并重建出假设，那么这种压缩能力本身就蕴含了泛化保证。样本越少、重建越准确，模型越可能具有良好的泛化性能。

这篇论文聚焦于基于**偏好压缩（preferent compression）**的学习规则，并对其风险上界给出了一个在收敛速率上更为紧致的结果。研究的核心贡献，是证明了此前风险界中出现的对数因子并非本质性的，从而将收敛速率提升到了与经典大数定律一致的水平。

从对数因子到大数定律速率

在已有的理论结果中，针对偏好压缩的学习规则，风险被一个样本依赖的复杂度量 $\boldsymbol{k}$ 所刻画。这里的 $\boldsymbol{k}$ 定义为压缩集合的基数，再加上那些重建假设在其上表现不当（inappropriate）的训练样本数量。

问题在于，这类已有结果给出的风险界，会在 $\boldsymbol{k}/N$ 之上附加一个量级为 $O(\sqrt{\ln N / N})$ 的余项。其中的对数因子 $\sqrt{\ln N}$ 虽然增长缓慢，但在理论上使得收敛速率略逊于最优。

论文的主要定理证明：对每个固定的置信水平 $1-\delta$，风险以至少 $1-\delta$ 的概率被下式所界定——

$$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right) $$

而且这一上界对 $\boldsymbol{k}$ 的所有可能取值是一致成立的。换言之，对数因子被完全消除，基于偏好压缩的风险估计达到了与"固定事件概率的经验估计"相同的大数定律收敛速率 $O(1/\sqrt{N})$。这是一个在速率意义上无法再改进的结果。

主导项 k/N 的必要性

理论工作往往不仅要给出更紧的上界，还要说明这个界是否已经触及极限。论文在这方面同样给出了回答：主导项 $\boldsymbol{k}/N$ 是必要的，不能被进一步去除或减小。这意味着复杂度量 $\boldsymbol{k}$ 确实是刻画压缩学习风险的本质参数，而 $O(1/\sqrt{N})$ 的余项则是围绕它的最优波动范围。

这种"上界可达 + 下界必要"的双向论证，使得结果在理论上更为完整。它清晰地界定了基于压缩的风险估计所能达到的精度边界。

与经验风险的对比

论文另一个有价值的方向，是探讨复杂度量 $\boldsymbol{k}/N$ 与传统**经验风险（empirical risk）**之间的关系。经验风险是机器学习中最常用的性能度量，但它在不同场景下的收敛行为差异很大。

研究识别出了几类不同的"区制（regimes）"：

• 在某些区制中，经验风险仍然保持 $O(1/\sqrt{N})$ 的收敛速率，与基于复杂度的估计器一致；
• 在另一些区制中，经验风险的收敛速度明显变慢；
• 还存在一些区制，经验风险甚至不再具有一致性（consistency），即无法随样本增多而收敛到真实风险。

而无论处于哪一类区制，基于压缩复杂度的估计器都能稳定地保持 $O(1/\sqrt{N})$ 的收敛速率。这一对比凸显了压缩框架的稳健性：当经验风险因样本结构或假设复杂度而失效时，复杂度型估计仍然提供可靠的泛化保证。

意义与定位

这项工作属于统计学习理论的基础研究范畴。它不涉及具体的工程实现或模型架构，而是在泛化界的理论精度上做出改进。将收敛速率从 $O(\sqrt{\ln N/N})$ 提升到 $O(1/\sqrt{N})$，看似只是去掉一个对数因子，但在理论上代表着风险估计触及了信息论意义上的最优速率。

对于关注泛化理论、PAC 学习、样本压缩界的研究者而言，这一结果补齐了偏好压缩框架在收敛速率上的最后一块短板，并通过与经验风险的对比，进一步说明了压缩型复杂度量作为风险估计工具的理论优势。