Robustly Learning Single-Index Models via Alignment Sharpness

Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, Jelena Diakonikolas
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:58197-58243, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zarifis24a, title = {Robustly Learning Single-Index Models via Alignment Sharpness}, author = {Zarifis, Nikos and Wang, Puqian and Diakonikolas, Ilias and Diakonikolas, Jelena}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {58197--58243}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zarifis24a/zarifis24a.pdf}, url = {https://proceedings.mlr.press/v235/zarifis24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Robustly Learning Single-Index Models via Alignment Sharpness %A Nikos Zarifis %A Puqian Wang %A Ilias Diakonikolas %A Jelena Diakonikolas %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zarifis24a %I PMLR %P 58197--58243 %U https://proceedings.mlr.press/v235/zarifis24a.html %V 235 %X 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.
APA
Zarifis, N., Wang, P., Diakonikolas, I. & Diakonikolas, J.. (2024). Robustly Learning Single-Index Models via Alignment Sharpness. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:58197-58243 Available from https://proceedings.mlr.press/v235/zarifis24a.html.

Related Material