On the hardness of learning intersections of two halfspaces

摘要

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 a function of up to e halfspaces (linear threshold functions) for any integer e. Specifically, we show that for every integer e and an arbitrarily small constant ε > 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 function of e halfspaces can correctly classify at most 1/2+ ε fraction of the points.