Robustly Learning Single-Index Models via Alignment Sharpness
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_ | 1866909121795588096 |
|---|---|
| author | Zarifis, Nikos Wang, Puqian Diakonikolas, Ilias Diakonikolas, Jelena |
| author_facet | Zarifis, Nikos Wang, Puqian Diakonikolas, Ilias Diakonikolas, Jelena |
| contents | We study the problem of learning Single-Index Models under the $L_2^2$ loss in the agnostic model. We give an efficient learning algorithm, achieving a constant factor approximation to the optimal loss, that succeeds under a range of distributions (including log-concave distributions) and a broad class of monotone and Lipschitz link functions. This is the first efficient constant factor approximate agnostic learner, even for Gaussian data and for any nontrivial class of link functions. Prior work for the case of unknown link function either works in the realizable setting or does not attain constant factor approximation. The main technical ingredient enabling our algorithm and analysis is a novel notion of a local error bound in optimization that we term alignment sharpness and that may be of broader interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_17756 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robustly Learning Single-Index Models via Alignment Sharpness Zarifis, Nikos Wang, Puqian Diakonikolas, Ilias Diakonikolas, Jelena Machine Learning Data Structures and Algorithms Optimization and Control Statistics Theory We study the problem of learning Single-Index Models under the $L_2^2$ loss in the agnostic model. We give an efficient learning algorithm, achieving a constant factor approximation to the optimal loss, that succeeds under a range of distributions (including log-concave distributions) and a broad class of monotone and Lipschitz link functions. This is the first efficient constant factor approximate agnostic learner, even for Gaussian data and for any nontrivial class of link functions. Prior work for the case of unknown link function either works in the realizable setting or does not attain constant factor approximation. The main technical ingredient enabling our algorithm and analysis is a novel notion of a local error bound in optimization that we term alignment sharpness and that may be of broader interest. |
| title | Robustly Learning Single-Index Models via Alignment Sharpness |
| topic | Machine Learning Data Structures and Algorithms Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2402.17756 |