Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912191919161344 |
|---|---|
| author | Chandrasekaran, Gautam Kontonis, Vasilis Stavropoulos, Konstantinos Tian, Kevin |
| author_facet | Chandrasekaran, Gautam Kontonis, Vasilis Stavropoulos, Konstantinos Tian, Kevin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_09851 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random Chandrasekaran, Gautam Kontonis, Vasilis Stavropoulos, Konstantinos Tian, Kevin Machine Learning Data Structures and Algorithms 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. |
| title | Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.09851 |