Hardness of Agnostically Learning
Halfspaces by degree-2 PTFs
Ilias Diakonikolas,
Ryan O’Donnell, Rocco Servedio, Yi Wu
Manuscript, 2009
Abstract:
We
show that, unless NP=RP, it is hard to (even weakly) agnostically learn halfspaces using a hypothesis which is a degree-2
polynomial threshold function. Specifically, we show that unless NP=RP, for any
constant ε>0, no polynomial
time algorithm can distinguish whether there is a halfspace
that is consistent with 1-ε
fraction of labeled points in Rn, or whether any degree-2 threshold function can
correctly classify at most a ½+ ε
fraction of the points.
Preliminary version: to be posted