Prefer a chat interface with context about you and your work?
Agnostic Learning of Monomials by Halfspaces Is Hard
We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples it is NP-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples for arbitrary constants $\epsilon>0$. In …