Abstract
We show that unless NP = RP, it is hard to (even) weakly PAC-learn intersection of two halfspaces in Rn 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 ε>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 Rn, or whether any function of ℓ halfspaces can correctly classify at most 12+ε fraction of the points.
Original language | English (US) |
---|---|
Pages (from-to) | 129-141 |
Number of pages | 13 |
Journal | Journal of Computer and System Sciences |
Volume | 77 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2011 |
Keywords
- Approximation
- Halfspaces
- Hardness
- Learning
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics