在恶意噪声下高效学习稀疏超平面，样本量近似最优
Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
- 基于集中与间隔条件，设计抗恶意噪声的稀疏超平面学习算法
- 仅需 $O(s^2\log^5 d)$ 个样本即可实现近似最优学习
- 适用于高维稀疏数据，对噪声鲁棒，适合理论研究者
稀疏超平面的属性高效PAC学习是机器学习理论中的基本问题。近年来，机器学习算法面临普遍的数据污染甚至恶意攻击，设计在计算和属性上均高效的鲁棒算法成为关键。本文研究数据中存在恒定比例恶意噪声的情形，证明可在满足集中条件与间隔条件的分布下，仅用 $O(s^2\log^5 d)$ 个样本实现对 $s$-稀疏超平面 $w^* \in \mathbb{R}^d$ 的PAC学习。作为补充，我们给出了在无噪声情况下该条件下的信息论样本下界，表明所提方法的样本复杂度可能近乎最优。为验证算法鲁棒性，我们提出一种新的梯度分析方法，精确处理铰链损失最小化中的稀疏性约束，该方法本身亦具独立研究价值。
原文摘要 · Abstract (English)
Attribute-efficient PAC learning of sparse halfspaces has been a fundamental problem in machine learning theory. In recent years, machine learning algorithms are faced with prevalent data corruptions or even malicious attacks. It is of central interest to design computationally and attribute-efficient algorithms that are robust to extreme corruptions. In this paper, we consider that there is a constant amount of malicious noise in the data and show that it is possible to PAC learn an underlying $s$-sparse halfspace $w^* \in \mathbb{R}^d$ with $O(s^2\log^5 d)$ samples. Specifically, we follow a recent line of works and assume that the underlying distribution satisfies a concentration condition and a margin condition at the same time. As a complementary result, we provide an information-theoretic sample lower bound under such conditions even for the noiseless case. There is evidence showing that our sample complexity could be nearly optimal. To show the robustness of our algorithm, we provide a new gradient analysis that carefully handles the sparsity admitted constraints in hinge loss minimization program, which could be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。