Learning Noisy Halfspaces with a Margin: Massart is No Harder than
Random
Learning Noisy Halfspaces with a Margin: Massart is No Harder than
Random
We study the problem of PAC learning $\gamma$-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetilde{O}((\epsilon\gamma)^{-2})$ and achieves classification error at most $\eta+\epsilon$ where $\eta$ is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in …