学习理论 30 年悬案获重大突破:样本压缩猜想逼近 O(d²)

canondetortugas · x · 2026-11-21

arXiv 新论文《Near-Quadratic Sample Compression for All VC Classes》在learning theory 长期悬案上取得突破。

背景:

本文结果:作者团队(Yang Cai、Vineet Gupta、Christopher Liaw、Shay Moran、Manfred Warmuth 等 9 人)构造出大小为 O(d² log² d) 的压缩方案,证明了弱猜想,将指数级界直接降到近二次。这是泛化理论与算法分析方向的重要进展。

原文链接 →

「研究」频道最新

更多「研究」频道 AI 资讯 →