首页 时政热点 科技头条 智能AI 安全攻防 数码硬件 开发者生态 归档 标签 关于
智能AI morning

所有 VC 类的近二次样本压缩

2026-11-20 1 阅读 约1分钟阅读 Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang, Manfred K. Warmuth
分享:
字号:
arXiv:2611.25011v1 公告类型:新 摘要:样本压缩猜想是学习理论中长期存在的开放问题,起源于 Littlestone 和 Warmuth 在 20 世纪 80 年代的工作。其核心是简化和泛化之间的联系:如果仅使用该样本的一小部分来定义与训练样本一致的预测变量,那么它很可能会泛化。样本压缩方案形式化了这个想法,并且许多自然学习算法都可以通过这种方式进行分析。 Floyd 和 Warmuth (1995) 的样本压缩猜想断言 VC 维度 $d$ 的每个二元概念类都承认大小为 $O(d)$ 的样本压缩方案;较弱的猜想仅要求 $d$ 中的大小多项式。两者都保持开放状态:根据 Moran 和 Yehudayoff (2016) 的说法,第一个边界仅取决于 $d$,并且与 $d$ 呈指数关系。我们通过构建大小为 $O(d^2 \log^2 d)$ 的样本压缩方案来证明较弱的猜想。
这篇文章对您有帮助吗?

订阅66必读

每日精选科技资讯,直达你的邮箱