EUVIMEDEUVIMED entdecken
Crossref

Improved Hardness Results for Learning Intersections of Halfspaces

Stefan Tiegel

TheoretiCS · 28.04.2026 · Volume 5

DOI: 10.46298/theoretics.26.8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, online erschienen am 28.04.2026. Verfasst von Stefan Tiegel.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show strong (and surprisingly simple) lower bounds for weakly learning intersections of halfspaces in the improper setting. Strikingly little is known about this problem. For instance, it is not even known if there is a polynomial-time algorithm for learning the intersection of only two halfspaces. On the other hand, lower bounds based on well-established assumptions (such as approximating worst-case lattice problems or variants of Feige's 3SAT hypothesis) are only known (or are implied by existing results) for the intersection of super-logarithmically many halfspaces [KS09,KS06,DSS16]. With intersections of fewer halfspaces being only ruled out under less standard assumptions [DV21] (such as the existence of local pseudo-random generators with large stretch). We significantly narrow this gap by showing that even learning $ω(\log \log N)$ halfspaces in dimension $N$ takes super-polynomial time under standard assumptions on worst-case lattice problems (namely that SVP and SIVP are hard to approximate within polynomial factors). Further, we give unconditional hardness results in the statistical query framework. Specifically, we show that for any $k$ (even constant), learning $k$ halfspaces in dimension $N$ requires accuracy $N^{-Ω(k)}$, or exponentially many queries -- in particular ruling out SQ algorithms with polynomial accuracy for $ω(1)$ halfspaces. To the best of our knowledge this is the first unconditional hardness result for learning a super-constant number of halfspaces. Our lower bounds are obtained in a unified way via a novel connection we make between intersections of halfspaces and the so-called parallel pancakes distribution [DKS17,BLPR19,BRST21] that has been at the heart of many lower bound constructions in (robust) high-dimensional statistics in the past few years.

Zitieren

APA

Tiegel, S. (2026). Improved Hardness Results for Learning Intersections of Halfspaces. TheoretiCS, Volume 5. https://doi.org/10.46298/theoretics.26.8

Vancouver

Tiegel S. Improved Hardness Results for Learning Intersections of Halfspaces. TheoretiCS. 2026;Volume 5. doi:10.46298/theoretics.26.8

BibTeX
@article{Tiegel2026,
  author = {Tiegel, Stefan},
  title = {Improved Hardness Results for Learning Intersections of Halfspaces},
  journal = {TheoretiCS},
  year = {2026},
  volume = {Volume 5},
  doi = {10.46298/theoretics.26.8}
}
Kostenlos starten →