Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.
I. Diakonikolas and
R. O'Donnell and
R. Servedio and
Y. Wu.
In
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011, pp. 1590-1606.
Abstract:
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 results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in $\R^n \times \{-1,1\}.$
We prove that for any constants $d\geq 1, \eps > 0$,
Assuming the Unique Games Conjecture, no polynomial-time algorithm can find a degree-$d$ PTF that
is consistent with a $(\half + \eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$, even if there exists a degree-$d$ PTF that is consistent with a $1-\eps$ fraction of the examples.
It is $\NP$-hard to find a degree-2 PTF that is consistent with
a $(\half + \eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$, even if
there exists a halfspace (degree-1 PTF) that is consistent with a $1 - \eps$ fraction of the
examples.
These results immediately imply the following hardness of learning results: (i) Assuming the
Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-$d$ PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-$2$ PTFs and agnostically learns halfspaces (i.e. degree-$1$ PTFs) under arbitrary distributions.
pdf (full version).
Back to
main papers page