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.

通过与半空间和所谓的并行煎饼分布的新颖联系，我们以统一的方式获得了较强（而且令人惊讶地简单）的在不适当的情况下学习半空间交集的下界，这是过去几年强大的高维统计学中许多下界构造的核心，我们还给出了统计查询框架下的无条件难度结果。