Hardness of Learning a Single Neuron with Adversarial Label Noise

Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:8199-8213, 2022.

Abstract

We study the problem of distribution-free learning of a single neuron under adversarial label noise with respect to the squared loss. For a wide range of activation functions, including ReLUs and sigmoids, we prove hardness of learning results in the Statistical Query model and under a well-studied assumption on the complexity of refuting XOR formulas. Specifically, we establish that no polynomial-time learning algorithm, even improper, can approximate the optimal loss value within any constant factor.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-diakonikolas22a, title = { Hardness of Learning a Single Neuron with Adversarial Label Noise }, author = {Diakonikolas, Ilias and Kane, Daniel and Manurangsi, Pasin and Ren, Lisheng}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {8199--8213}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/diakonikolas22a/diakonikolas22a.pdf}, url = {https://proceedings.mlr.press/v151/diakonikolas22a.html}, abstract = { We study the problem of distribution-free learning of a single neuron under adversarial label noise with respect to the squared loss. For a wide range of activation functions, including ReLUs and sigmoids, we prove hardness of learning results in the Statistical Query model and under a well-studied assumption on the complexity of refuting XOR formulas. Specifically, we establish that no polynomial-time learning algorithm, even improper, can approximate the optimal loss value within any constant factor. } }
Endnote
%0 Conference Paper %T Hardness of Learning a Single Neuron with Adversarial Label Noise %A Ilias Diakonikolas %A Daniel Kane %A Pasin Manurangsi %A Lisheng Ren %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-diakonikolas22a %I PMLR %P 8199--8213 %U https://proceedings.mlr.press/v151/diakonikolas22a.html %V 151 %X We study the problem of distribution-free learning of a single neuron under adversarial label noise with respect to the squared loss. For a wide range of activation functions, including ReLUs and sigmoids, we prove hardness of learning results in the Statistical Query model and under a well-studied assumption on the complexity of refuting XOR formulas. Specifically, we establish that no polynomial-time learning algorithm, even improper, can approximate the optimal loss value within any constant factor.
APA
Diakonikolas, I., Kane, D., Manurangsi, P. & Ren, L.. (2022). Hardness of Learning a Single Neuron with Adversarial Label Noise . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:8199-8213 Available from https://proceedings.mlr.press/v151/diakonikolas22a.html.

Related Material