Efficient Proper Agnostic Learning of Halfspaces

We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on \±1\ⁿ. Given query access to an arbitrary function f:\±1\ⁿ → \±1\, our algorithm runs in time poly(n)+2poly(1/ε) and outputs a halfspace with error at most OPT+ε, where OPT is the error of the best-fitting halfspace for f. Previously, even with membership queries, the best known running time was npoly(1/ε), achieved by the sample-based algorithm of Kalai, Klivans, Mansour, and Servedio (FOCS 2005). Our algorithm is the first agnostic halfspace learner under the uniform distribution on \±1\ⁿ whose running time is polynomial in n with an exponent independent of ε. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same OPT+ε guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on ε. To our knowledge, this is the first sample-based proper agnostic learner in the Boolean setting with running time 2ᵒ⁽ⁿ⁾ for every fixed ε>0.