AISTATS 2022poster14 citations
Hardness of Learning a Single Neuron with Adversarial Label Noise
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren
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.
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. }
}