Title:Efficient Algorithms for Agnostic Learning
Speaker: Adam Klivans University of Texas
Time: 2008-06-12 14:20-2008-06-12 15:20
Venue:FIT Building 4-603, Tsinghua University
Download:Click!

Abstract:

The Agnostic framework of learning is a notoriously difficult generalization of the PAC learning model where a learner must succeed in the presence of adversarial noise. Over the last decade in computational learning theory, almost every result regarding agnostic learning has been negative.
        In recent work, we have obtained the first positive results for agnostically learning well-studied concept classes (such as halfspaces and decision trees) with respect to natural distributions. Most of the talk will be devoted to presenting a polynomial-time query algorithm for agnostically learning decision trees with respect to the uniform distribution over {0,1}^n.



Short Bio:

Adam Klivans received his PhD in 2002 from MIT and was an NSF Postdoctoral Research Fellow at Harvard University from 2002-2004.He is currently an Assistant Professor in the Department of Computer Science at the University of Texas at Austin. In 2007 he was awarded the NSF CAREER award and in 2001 he received the Danny Lewin Best Student Paper Award at the Symposium on Theory of Computing (STOC). He is a member of the editorial board of Theory of Computing and Machine Learning. His research interests include computational learning theory, cryptography, and the relationship between the two.