" PAC Learning of Halfspaces with Noise: Efficient algorithms for the Massart and Tsybakov models "
Christos Tzamos (UW Madison)
Abstract: We study the problem of PAC learning of halfspaces in the presence of noise. Specifically, we are given a set of labeled examples (x, y) drawn from a distribution D on R^d whose labels y are flipped independently with some probability controlled by an adversary. The goal is to find a hypothesis h that minimizes the misclassification error Pr[h(x) ≠ y].
One important case studied in the statistics literature is the Massart model where the flipping probabilities are assumed to be bounded below a parameter η. Our main result is a polynomial-time algorithm that achieves misclassification error close to η. Prior to our work, no computationally efficient algorithm was known that achieves any non-trivial guarantees and has been posed as an open question in various works.
When the distribution on unlabeled examples is known to be structured, satisfying certain concentration and (anti-)anti-concentration properties, we show that it is possible to achieve near optimal error efficiently. We obtain polynomial-time algorithms for the Massart model and extend them to tackle the more challenging Tsybakov noise model where there is no absolute bound on the label-flipping probabilities.
The talk is based on joint work with Ilias Diakonikolas, Themis Gouleakis, Vasilis Kontonis, and Nikos Zarifis.
Bio: Christos Tzamos is an Assistant Professor in the Department of Computer Sciences at University of Wisconsin-Madison and a member of the Theory of Computing group. His research interests lie in the interface of Theory of Computation with Economics and Game Theory, Machine Learning, Statistics and Probability Theory. He completed his PhD in the Theory of Computation group of MIT. Before his PhD, he studied Electrical and Computer Engineering at NTUA and afterwards he was a postdoctoral researcher at Microsoft Research (New England) working on Mechanism Design, Algorithms and Machine Learning. He is the recipient of a Simons Foundation award, the George M. Sprowls award, the best paper and the best student paper award in EC 2013 and of the outstanding paper award in NeurIPS 2019.