[Colloquium] Show and Tell Series Talk at TTI-C 11/2

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE
SHOW AND TELL SERIES TALK
 
Speaker: Adam Klivans
Speaker's homepage: http://www.tti-c.org/klivans.html
Title:  Hardness Results for Learning Intersections of Halfspaces 
 
Time: Tuesday, November 2nd, 12:15pm
Place: TTI-C conference room (1427 E. 60th St. - 2nd Floor) Lunch
provided
 
Abstract: Polynomial-time algorithms for learning halfspaces are at the
heart of many systems used by practitioners from fields such as
artificial intelligence, statistics, and computational biology to
classify data. 
Surprisingly, the complexity of learning the intersection of even two
halfspaces is unknown. Intersections of halfspaces are a powerful
concept class, as they are capable of expressing any convex body. The
problem of PAC learning intersections of halfspaces remains an important
challenge.
Our focus during this talk will be the computational hardness of solving
these problems. For example, Blum and Rivest proved that learning the
intersection of k halfspaces is NP-hard if the hypothesis output by the
learner is an intersection of k halfspaces (for k \geq 3).
We will present several improved hardness results: 
** Learning the intersection of $n^{a}$ halfspaces is NP-hard if the
output hypothesis is an intersection of $n^{b}$ halfspaces for any
constants a,b > 0. 
** Learning the intersection of two halfspaces is NP-hard if the output
hypothesis is an intersection of any constant number of halfspaces.
Our results also imply that it is NP-hard to properly learn
polynomial-size DNF formulas and polynomial-size decision trees,
completing a long line of research in this area. If time permits I will
talk about some new {\it upper} bounds on learning intersections of
halfspaces, to contrast with these hardness results. 
Joint work with M. Alekhnovich, M. Braverman, V. Feldman, and T.
Pitassi.
 
If you have questions, or would like to meet the speaker, please contact

Katherine at 4-1994 or kcumming at tti-c.org
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041027/653ff94d/attachment.htm