提出新算法，高效学习带噪声的分类边界。
Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
- 设计透视感知机算法，处理马萨特噪声下的半空间学习。
- 样本复杂度达 (εγ)⁻²量级，误差控制在 η+ε 内。
- 适用于广义线性模型，适合研究噪声鲁棒学习者。
我们研究了在马萨特噪声下学习 γ-间隔半空间的 PAC 学习问题。提出一种简单且正确的学习算法——透视感知机（Perspectron），其样本复杂度为 Õ((εγ)⁻²)，可实现分类误差不超过 η+ε，其中 η 为马萨特噪声率。此前工作 [DGT19, CKMY20] 的样本复杂度更差（在 ε 与 γ 上），或仅能处理随机分类噪声 [DDK+23, KIT+23]——这是一种更温和的噪声假设。我们还证明，该结果可扩展至已知链接函数的广义线性模型学习场景，在该设定下样本复杂度与半空间情形相当。这显著优于 [CKMY20] 提出的先前最优结果，后者首次引入了该模型。
原文摘要 · Abstract (English)
We study the problem of PAC learning $γ$-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetilde{O}((εγ)^{-2})$ and achieves classification error at most $η+ε$ where $η$ is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in both $ε$ and $γ$) or could only handle random classification noise [DDK+23,KIT+23] -- a much milder noise assumption. We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to [CKMY20], who introduced this model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。