用随机假设提升抗噪声学习性能，最优误差比确定性方法降低一半以上。
Robust Learning with Optimal Error
- 采用随机化假设替代确定性假设，突破传统学习器的误差下限。
- 在恶意噪声下误差降至η/(2(1-η))，比之前最优结果降低50%。
- 适用于高噪声环境下的鲁棒学习，尤其适合理论研究者和安全应用开发者。
本文构建了在对抗性噪声下具有最优误差的学习算法。核心思想是：使用随机化假设可显著优于确定性假设。对于η率恶意噪声，最优误差为η/(2(1-η))，相比确定性假设的最优误差改进一倍；对于η率恶劣噪声，分布无关学习者的最优误差为3η/2，固定分布学习者为η，均优于确定性假设的2η；对于η率伪标签噪声及紧密相关的恶劣分类噪声模型，最优误差为η，同样优于确定性假设的2η。所有学习器样本复杂度与概念类的VC维线性相关，且与超误差倒数多项式相关。除固定分布恶劣噪声学习器外，其余均可在经验风险最小化预言机支持下高效实现。
原文摘要 · Abstract (English)
We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of \textsl{randomized} hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For $η$-rate malicious noise, we show the optimal error is $\frac{1}{2} \cdot η/(1-η)$, improving on the optimal error of deterministic hypotheses by a factor of $1/2$. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of $6/7$. - For $η$-rate nasty noise, we show the optimal error is $\frac{3}{2} \cdot η$ for distribution-independent learners and $η$ for fixed-distribution learners, both improving upon the optimal $2 η$ error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026). - For $η$-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is $η$, improving upon the optimal $2η$ error of deterministic hypotheses. All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。