2 papers
cs.CC2010
Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra +1
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-\eps)$…
cs.LG2010
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio +1
Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness…