学习理论 30 年悬案获重大突破:样本压缩猜想逼近 O(d²)
canondetortugas · x · 2026-11-21
arXiv 新论文《Near-Quadratic Sample Compression for All VC Classes》在learning theory 长期悬案上取得突破。
背景:
- 样本压缩猜想起源于 Littlestone 与 Warmuth 1980 年代的工作:若预测器只依赖训练样本的一小部分且保持一致,则大概率能泛化。
- Floyd 与 Warmuth(1995)猜想每个 VC 维为 d 的二分概念类都存在 O(d) 大小的压缩方案;更弱的版本只要求多项式大小,此前一直未解决。此前仅与 d 相关的最好界(Moran-Yehudayoff 2016)是指数级的。
本文结果:作者团队(Yang Cai、Vineet Gupta、Christopher Liaw、Shay Moran、Manfred Warmuth 等 9 人)构造出大小为 O(d² log² d) 的压缩方案,证明了弱猜想,将指数级界直接降到近二次。这是泛化理论与算法分析方向的重要进展。
「研究」频道最新
- Claude系统卡曝已训练蛋白质序列,生物基础模型或被通用模型取代 — chaitjo · 2026-11-22
- Axiom 招募药企合作:出钱跑药物实验,资产 100% 归你 — cjmaddison · 2026-11-22
- 神经网络进化骑手浏览器竞速,能看着 AI 学会跟车与冲刺 — AjdDavison · 2026-11-22
- Lean 与 Mathlib 称 Alpöge 与 Claude 的黎曼猜想证明已验证正确 — queenofartists · 2026-11-22
- AlphaProof Nexus 用 Lean 形式化证明解决量子光学悬而未决问题 — dair_ai · 2026-11-22
- Lean 社区验证 1700 万行代码,确认 Claude 参与证明黎曼猜想 — Polymarket · 2026-11-22