Hardness of Learning a Single Neuron with Adversarial Label Noise

Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi · Lisheng Ren

[ Abstract ]
Wed 30 Mar 8:30 a.m. PDT — 10 a.m. PDT
Oral presentation: Oral 8: Learning theory / Sampling methods
Wed 30 Mar midnight PDT — 1 a.m. PDT


We study the problem of distribution-free learning of a single neuronunder 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 andunder 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.

Chat is not available.