Reliable Learning of Halfspaces under Gaussian Marginals
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_ | 1866929595094138880 |
|---|---|
| author | Diakonikolas, Ilias Ren, Lisheng Zarifis, Nikos |
| author_facet | Diakonikolas, Ilias Ren, Lisheng Zarifis, Nikos |
| contents | We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012). The reliable PAC model captures learning scenarios where one type of error is costlier than the others. Our main positive result is a new algorithm for reliable learning of Gaussian halfspaces on $\mathbb{R}^d$ with sample and computational complexity $$d^{O(\log (\min\{1/α, 1/ε\}))}\min (2^{\log(1/ε)^{O(\log (1/α))}},2^{\mathrm{poly}(1/ε)})\;,$$ where $ε$ is the excess error and $α$ is the bias of the optimal halfspace. We complement our upper bound with a Statistical Query lower bound suggesting that the $d^{Ω(\log (1/α))}$ dependence is best possible. Conceptually, our results imply a strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11238 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reliable Learning of Halfspaces under Gaussian Marginals Diakonikolas, Ilias Ren, Lisheng Zarifis, Nikos Machine Learning Data Structures and Algorithms We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012). The reliable PAC model captures learning scenarios where one type of error is costlier than the others. Our main positive result is a new algorithm for reliable learning of Gaussian halfspaces on $\mathbb{R}^d$ with sample and computational complexity $$d^{O(\log (\min\{1/α, 1/ε\}))}\min (2^{\log(1/ε)^{O(\log (1/α))}},2^{\mathrm{poly}(1/ε)})\;,$$ where $ε$ is the excess error and $α$ is the bias of the optimal halfspace. We complement our upper bound with a Statistical Query lower bound suggesting that the $d^{Ω(\log (1/α))}$ dependence is best possible. Conceptually, our results imply a strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting. |
| title | Reliable Learning of Halfspaces under Gaussian Marginals |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.11238 |