Theory Lunch Seminar

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

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.

Keywords:
For More Information, Please Contact:

ggurugan [atsymbol] andrew.cmu.edu