Pranjal Awasthi (Theory Seminar F14)

"Learning Halfspaces with Noise"
Pranjal Awasthi
Monday, October 6th, 2014, 2:00 pm
EBU3B, Room 4258
We study the problem of learning halfspaces in the malicious noise model of Valiant. In this model, an adversary can corrupt an η fraction of both the label part and the feature part of an example. We design a polynomial-time algorithm for learning halfspaces in R^d under the uniform distribution with near 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.