Robustly Learning a Single Neuron via Sharpness
Puqian Wang Nikos Zarifis Ilias Diakonikolas Jelena Diakonikolas
We study the problem of learning a single neuron with respect to the
$L_2^2$-loss in the presence of adversarial label noise. We give an efficient
algorithm that, for a broad family of activations including ReLUs, approximates
the optimal $L_2^2$-error within a constant factor. Our algorithm applies under
much milder distributional assumptions compared to prior work. The key
ingredient enabling our results is a novel connection to local error bounds
from optimization theory.