Improved Hardness Results for Learning Intersections of Halfspaces
arXiv:2402.15995v2 Announce Type: replace-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…