通过压缩学习：风险估计达到大数定律速率

arXiv:2610.13442v1 公告类型：cross 摘要：压缩方案为推导依赖于数据的学习算法风险界提供了一个通用框架。对于基于偏好压缩的学习规则，现有结果根据依赖于样本的复杂度 $\boldsymbol{k}$ 对风险给出上界，其中 $\boldsymbol{k}$ 定义为压缩集与训练样本中重构假设不适用的样本所组成集合的基数。然而，这些结果在 $\boldsymbol{k}/N$ 之上产生了一个量级为 $O(\sqrt{\ln N/N})$ 的裕量。在本文中，我们证明这一对数因子并非内在因素。我们证明，对于任意固定的置信水平 $1-\delta$，以至少 $1-\delta$ 的概率，风险满足 $$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right), $$ 且该结论对 $\boldsymbol{k}$ 的所有可能取值一致成立。因此，基于偏好压缩的学习算法的风险估计达到了与固定事件概率的经验估计相同的大数定律速率。我们还证明了首项 $\boldsymbol{k}/N$ 是必要的，并考察了它与经验风险之间的关系。特别地，我们确定了若干情形：在这些情形下，经验风险保持 $O(1/\sqrt{N})$ 的收敛速率；同时也确定了另一些情形：在这些情形下，经验风险的收敛速度更慢，或不再具有一致性，而基于复杂度的估计量仍保持 $O(1/\sqrt{N})$ 的速率。