Title : On Hardness of Learning Intersection of Two Halfspaces.
Speaker : Rishi Saket (Georgia Tech, visiting NYU)
Abstract:
Learning intersections of halfspaces is a well studied problem in
learning theory. It is known that it is hard to PAC-learn intersections
of two halfspaces using a hypothesis of intersection of constant number
halfspaces[ABFKP 04]. We show that, unless NP=RP, it is hard to (even)
weakly PAC-learn intersection of two halfspaces in R^n using a
hypothesis which is an intersection of \ell halfspaces for any integer
\ell. Specifically, we show that for every integer \ell and an
arbitrarily small constant \eps > 0, unless NP=RP, no polynomial time
algorithm can distinguish whether there is an intersection of two
halfspaces that correctly classifies a given set of labeled points in
R^n, or whether any intersection of \ell halfspaces can correctly
classify at most 1/2 + \eps fraction of the points.
Joint Work with Subhash Khot.