On hardness of learning intersection of two halfspaces

Subhash Khot, Rishi Saket

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ℓ 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 ℓ linear threshold functions can correctly classify at most 1/2+ ε fraction of the points.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages345-353
Number of pages9
ISBN (Print)9781605580470
DOIs
StatePublished - 2008
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CountryCanada
CityVictoria, BC
Period5/17/085/20/08

Keywords

  • Approximation
  • Halfspaces
  • Hardness
  • Learning

ASJC Scopus subject areas

  • Software

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

  • Cite this

    Khot, S., & Saket, R. (2008). On hardness of learning intersection of two halfspaces. In STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing (pp. 345-353). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/1374376.1374426