Improved Hardness Results for Learning Intersections of Halfspaces
Stefan Tiegel
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 $\omega(\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^{-\Omega(k)}$, or
exponentially many queries -- in particular ruling out SQ algorithms with
polynomial accuracy for $\omega(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.