压缩学习风险界去掉对数因子，达到大数定律速率！
Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
📖 AI 总结
这篇论文研究基于压缩方案的学习算法的风险界。压缩方案为推导数据依赖的风险上界提供了通用框架，此前针对基于偏好压缩的学习规则，已有结果以样本依赖复杂度k（压缩集基数加上重建假设不适用的训练样本数）来上界风险，但会多出一个O(√(ln N/N))量级的余项。作者证明该对数因子并非本质的：对任意固定置信水平1-δ，风险以至少1-δ的概率被k/N加O(1/√N)所界定，且该结论对所有k值一致成立。这意味着此类学习算法的风险估计达到了与大数定律相同的收敛速率，即与固定事件概率的经验估计相当。作者还证明主导项k/N是必要的，并考察其与经验风险的关系，识别出经验风险保持O(1/√N)速率、收敛更慢甚至不再一致的多种情形，而基于复杂度的估计量始终维持O(1/√N)速率。该结果深化了对压缩学习理论的理解，表明复杂度型风险估计在经验风险失效的场景下仍具稳健性。
🔑 关键词速览
| 偏好压缩 (preferent compression) | 一种基于压缩方案的学习框架，通过选择能压缩样本的假设来构造学习规则。 |
| 数据依赖风险界 (data-dependent risk bound) | 依赖于具体观测样本而非仅依赖样本量的风险上界。 |
| 样本依赖复杂度 $\boldsymbol{k}$ | 由压缩集大小和重构假设不适用的训练样本数共同定义的复杂度度量。 |
| 大数定律速率 (law-of-large-numbers rate) | 指估计误差以 $O(1/\sqrt{N})$ 的速度收敛，与独立同分布随机变量均值的收敛速率相同。 |
| 经验风险 (empirical risk) | 学习算法在训练样本上的平均损失，用于估计真实风险。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅