On the hardness of learning intersections of two halfspaces

Subhash Khot, Rishi Saket

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)129-141
Number of pages13
JournalJournal of Computer and System Sciences
Volume77
Issue number1
DOIs
StatePublished - Jan 2011

Keywords

  • Approximation
  • Halfspaces
  • Hardness
  • Learning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the hardness of learning intersections of two halfspaces'. Together they form a unique fingerprint.

  • Cite this