Theory Lunch Seminar

Machine Learning Department
Carnegie Mellon University
Learning Halfspaces with Noise
Wednesday, February 5, 2014 - 12:00pm to 1:00pm
Gates&Hillman Centers

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 ℜ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.

For More Information, Please Contact: