通过随机投影与量化改进学习算法泛化误差上界，突破现有方法失效瓶颈。
Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization
- 引入随机投影与有损压缩技术优化条件互信息上界
- 在训练集大小n下获得O(1/√n)的紧致泛化上界
- 证明记忆并非良好泛化的必要条件，适合理论研究者阅读
本文利用随机投影和有损压缩，建立了统计学习算法泛化误差的新条件互信息（CMI）上界。结果表明，这些上界普遍优于已有结果。特别地，我们证明了对于某些问题实例，现有信息论上界（如Attias et al. [2024] 和 Livni [2023] 所示）会退化或无法正确描述泛化行为，而我们的上界仍能给出O(1/√n)阶的合理泛化保证，其中n为训练数据集规模。此外，我们用该上界分析了前述工作中提出的“数据记忆”问题，即存在某些学习任务，任何表现良好的算法在特定分布下都必须记忆大量训练数据。我们证明：对任意学习算法，均存在一个不记忆的辅助算法，可在任意数据分布下实现相近的泛化误差。这表明记忆并非良好泛化的必要条件。
原文摘要 · Abstract (English)
In this paper, we leverage stochastic projection and lossy compression to establish new conditional mutual information (CMI) bounds on the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than the existing ones. In particular, we prove that for certain problem instances for which existing MI and CMI bounds were recently shown in Attias et al. [2024] and Livni [2023] to become vacuous or fail to describe the right generalization behavior, our bounds yield suitable generalization guarantees of the order of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the size of the training dataset. Furthermore, we use our bounds to investigate the problem of data "memorization" raised in those works, and which asserts that there are learning problem instances for which any learning algorithm that has good prediction there exist distributions under which the algorithm must "memorize" a big fraction of the training dataset. We show that for every learning algorithm, there exists an auxiliary algorithm that does not memorize and which yields comparable generalization error for any data distribution. In part, this shows that memorization is not necessary for good generalization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。