🔥 今日值得一读
打破噪声极限！多项式时间算法首次实现最优稳健学习，高斯半空间也能搞定！
Efficient Robust Learning at the Information-Theoretic Limit
👨💼 主理人解读 · 为什么值得关注
在噪声数据下高效学习分类器，达到理论最优误差，适合鲁棒模型训练场景。
📖 AI 总结
本文研究在固定分布下对布尔概念类进行鲁棒学习的问题。此前 Blanc（2026）提出了一种算法，能够输出随机化分类器并达到最优误差 η+ε（η 为噪声率），而确定性假设无法将误差降至 2η+ε 以下，但该算法计算效率低下，如何借助经验风险最小化（ERM）预言机实现多项式时间算法是其遗留的核心开放问题。本文解决了这一问题，给出了多项式时间算法，其技术关键出人意料地依赖于多种无遗憾学习器。此外，作者还提出了一种无需 ERM 预言机的高效算法，可鲁棒学习任何在超收缩分布下具有夹逼多项式的函数类。作为推论，本文首次给出了在高斯边缘分布下鲁棒学习半空间的多项式时间算法，对任意常数 ε 均可达到 η+ε 的误差。该工作将鲁棒学习的计算效率推进到信息论极限，具有重要的理论意义。
🔑 关键词速览
| 稳健学习 (Robust Learning) | 在训练数据存在噪声（如标签噪声）的情况下，仍能学习到具有良好泛化性能的分类器的学习范式。 |
| 噪声率 (Noise Rate) | 数据中标签被随机翻转或污染的比例，通常记为 η，是衡量噪声强度的参数。 |
| 经验风险最小化预言机 (ERM Oracle) | 一种理想化的计算模型，能够对给定的样本集返回使经验风险最小化的假设，常用于分析学习算法的计算复杂度。 |
| 无遗憾学习器 (No-Regret Learner) | 在线学习中的一种算法，其累积损失与事后最优策略的累积损失之差（遗憾）随时间次线性增长。 |
| 夹逼多项式 (Sandwiching Polynomials) | 用于逼近目标函数的一对多项式，分别从上下界夹逼该函数，常用于函数类的学习与逼近。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅