Title: Recent Progress on Learning Halfspaces with Noise
Speaker: Pranjal Awasthi, Rutgers University
Date: Wednesday, September 30, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
This talk will focus on the problem of learning halfspaces in the presence of noise. I will describe recent results for this problem under various noise models ranging from the notorious malicious noise model of Valiant to the more realistic Massart noise model studied in statistical learning theory. In the malicious noise model, an adversary can corrupt an η fraction of both the label part and the feature part of an example. In the Massart noise model, the label of each example can be flipped with a probability upper bounded by a constant less than half. For the malicious noise model we design a polynomial-time algorithm for learning halfspaces in R^d under the uniform distribution with near optimal noise tolerance. We also provide the first efficient algorithm for learning linear separators under the Massart noise model when the underlying distribution is uniform.
Our results also imply the first active learning algorithm for learning halfspaces that can handle near optimal noise.
Based on joint work with Nina Balcan, Nika Haghtalab, Phil Long and Ruth Urner.
See: https://dragon.rutgers.edu/~mk1029/theoryseminarF15.html