Robustly Learning a Single Neuron via Sharpness

Puqian Wang; Nikos Zarifis; Ilias Diakonikolas; Jelena Diakonikolas

ICML 2023oral9 citations

Robustly Learning a Single Neuron via Sharpness

Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, Jelena Diakonikolas

Abstract

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. Notably, our algorithm succeeds 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.

BibTeX

@inproceedings{icml2023_robustlylearning,
  title = {Robustly Learning a Single Neuron via Sharpness},
  author = {Puqian Wang and Nikos Zarifis and Ilias Diakonikolas and Jelena Diakonikolas},
  booktitle = {ICML 2023},
  year = {2023}
}