Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

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 fnding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in ℝn × {– 1, 1}. We prove that for any constants d ≥ 1, ∊ > 0, Assuming the Unique Games Conjecture, no polynomial-time algorithm can fnd a degree-d PTF that is consistent with a (1/2 + ∊) fraction of a given set of labeled examples in ℝn × {–1, 1}, even if there exists a degree-d PTF that is consistent with a 1 − ∊ fraction of the examples. It is NP-hard to fnd a degree-2 PTF that is consistent with a (1/2 + ∊) fraction of a given set of labeled examples in ℝn × {– 1, 1}, even if there exists a half-space (degree-1 PTF) that is consistent with a 1 − ∊ 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.