提出在恶意噪声下高效学习半空间的新方法，实现恒定噪声容忍度。
Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate
- 通过重加权铰链损失，缓解恶意噪声对梯度的破坏。
- 在分布假设与大间隔条件下，可实现恒定噪声容忍度。
- 适合研究噪声鲁棒学习的算法工程师与理论学者。
理解机器学习算法的抗噪能力是学习理论的核心问题。本文研究在恶意噪声环境下，如何计算高效地进行半空间的PAC学习，其中对手可同时污染训练样本的实例与标签。现有最佳结果的噪声容忍度依赖于目标误差率（在分布假设下）或间隔参数（在大间隔条件下）。本文证明，当两类条件同时满足时，通过最小化重加权铰链损失，可实现恒定噪声容忍度。关键贡献包括：1）设计了一种高效算法，用于寻找能控制受污染样本梯度退化的权重；2）提出了针对带权重铰链损失的新鲁棒性分析。
原文摘要 · Abstract (English)
Understanding noise tolerance of machine learning algorithms is a central quest in learning theory. In this work, we study the problem of computationally efficient PAC learning of halfspaces in the presence of malicious noise, where an adversary can corrupt both instances and labels of training samples. The best-known noise tolerance either depends on a target error rate under distributional assumptions or on a margin parameter under large-margin conditions. In this work, we show that when both types of conditions are satisfied, it is possible to achieve constant noise tolerance by minimizing a reweighted hinge loss. Our key ingredients include: 1) an efficient algorithm that finds weights to control the gradient deterioration from corrupted samples, and 2) a new analysis on the robustness of the hinge loss equipped with such weights.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。