Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909301425045504 |
|---|---|
| author | Diakonikolas, Ilias Kane, Daniel M. Liu, Sihan Zarifis, Nikos |
| author_facet | Diakonikolas, Ilias Kane, Daniel M. Liu, Sihan Zarifis, Nikos |
| contents | We study the task of testable learning of general -- not necessarily homogeneous -- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testable learning framework, the goal is to develop a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data.Our main result is the first polynomial time tester-learner for general halfspaces that achieves dimension-independent misclassification error. At the heart of our approach is a new methodology to reduce testable learning of general halfspaces to testable learning of nearly homogeneous halfspaces that may be of broader interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_17165 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Testable Learning of General Halfspaces with Adversarial Label Noise Diakonikolas, Ilias Kane, Daniel M. Liu, Sihan Zarifis, Nikos Machine Learning Data Structures and Algorithms We study the task of testable learning of general -- not necessarily homogeneous -- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testable learning framework, the goal is to develop a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data.Our main result is the first polynomial time tester-learner for general halfspaces that achieves dimension-independent misclassification error. At the heart of our approach is a new methodology to reduce testable learning of general halfspaces to testable learning of nearly homogeneous halfspaces that may be of broader interest. |
| title | Efficient Testable Learning of General Halfspaces with Adversarial Label Noise |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.17165 |