Monday, January 25, 2010

11:00 AM

Computer Studies Bldg. 209

Rocco Servedio

Columbia University

Learning Halfspaces with Malicious Noise

One of the most basic and intensely studied problems in machine learning is the problem of learning an unknown halfspace. In this binary classification problem, the learner is given a data set of labeled points in n-dimensional space, where each point's label is either + (for positive examples) or - (for negative examples). The goal of the learner is to find a hyperplane in n-dimensional space which ideally separates all of the positively labeled points from all of the negatively labeled ones.

This problem has been studied from many different perspectives, and is notoriously difficult if the data can be noisy (meaning that there is no perfect hyperplane separating all positive from negative examples). We study a challenging version of this problem called the "malicious noise model"; roughly speaking, in this model an omniscient adversary may corrupt both the labels and the underlying probability distribution of the noisy examples.

We describe new algorithms for learning halfspaces in this malicious noise model. Our algorithms can tolerate malicious noise rates exponentially larger than previous work in terms of the dependence on the dimension n. The algorithms succeed for the fairly broad class of all isotropic log-concave data distributions.

Joint work with Adam Klivans (UT Austin) and Phil Long (Google).

Bio: Rocco Servedio is an Associate Professor of Computer Science at Columbia University in New York. He received his A.B. in Mathematics and Ph.D. in Computer Science from Harvard, where he studied under Les Valiant. Rocco's research interests are centered around computational learning theory and computational complexity. Rocco has received an NSF Career Award and a Sloan Foundation Fellowship, and his research is currently supported by DARPA, Google, and the NSF.

Refreshments will be provided at 10:45 AM