Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

Details Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

2010-10-18

arxiv.org/abs/1010.3484v1

Computer Science

Learning

full version of SODA'11 paper

Scientific paper

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$, {itemize} 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. {itemize} 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.

Affiliated with

Also associated with

No associations

Rating

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-305190