2025/01/16 by Gautam Chandrasekaran, Chandrasekaran, Gautam, Vasilis Kontonis +5 · 3 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.2501.09851
openalex publication_date 2025/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \widetildeO((εγ)-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.