Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
This addresses the problem of robust learning under Massart noise for machine learning practitioners, offering a significant improvement in sample complexity over previous methods.
The paper tackles PAC learning of margin halfspaces with Massart noise, proposing the Perspectron algorithm that achieves classification error at most η + ε with sample complexity Õ((εγ)^{-2}), improving upon prior works with worse sample complexity or milder noise assumptions.
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.