Learning halfspaces with noise

Pranjal Awasthi

February 5, 2014

We study the problem of learning halfspaces in the malicious noise model of Valiant. In this model, an adversary can corrupt an $\eta$ fraction of both the label part and the feature part of an example. We design a polynomial-time algorithm for learning halfspaces in $\Re^d$ under the uniform distribution with near information-theoretic optimal noise tolerance.

Our results also imply the first active learning algorithm for learning halfspaces that can handle malicious noise.

Joint work with Nina Balcan and Phil Long.