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 using a hypothesis which is a function of up to ℓ halfspaces (linear threshold functions) for any integer ℓ. Specifically, we show that for every integer ℓ and an arbitrarily small constant , 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 , or whether any function of ℓ halfspaces can correctly classify at most fraction of the points.