Improved Hardness Results for Learning Intersections of Halfspaces

arXiv:2402.15995v1 Announce Type: cross
Abstract: 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 …

abstract algorithm arxiv cs.cc cs.lg instance intersection math.st polynomial results show simple stat.ml stat.th type