AI RESEARCH
Improved Hardness Results for Learning Intersections of Halfspaces
arXiv CS.LG
•
ArXi:2402.15995v2 Announce Type: replace-cross 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.