Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

Learning in the presence of noisy data is a central challenge in machine learning. In this work, we study the efficient learnability of halfspaces when a fraction of the training labels is adversarially corrupted. As our main contribution, we show that non-convex SGD efficiently learns homogeneous halfspaces in the presence of adversarial label noise with respect to a broad family of well-behaved distributions, including log-concave distributions. Before we state our contributions, we provide some background and motivation for this work.