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