Efficient Proper Agnostic Learning of Halfspaces

Abstract

We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm 1{\}}^n$. Given query access to an arbitrary function $f:\{\pm 1{\}}^n\to \{\pm 1\}$, our algorithm runs in time $\mathrm{poly}(n)+2^{\mathrm{poly}(1/\epsilon )}$ and outputs a halfspace with error at most $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is the error of the best-fitting halfspace for $f$. Previously, even with membership queries, the best known running time was $n^{\mathrm{poly}(1/\epsilon )}$, 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 $\{\pm 1{\}}^n$ whose running time is polynomial in $n$ with an exponent independent of $\epsilon$. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same $\mathrm{OPT}+\epsilon$ guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on $\epsilon$. To our knowledge, this is the first sample-based proper agnostic learner in the Boolean setting with running time $2^{o(n)}$ for every fixed $\epsilon >0$.

arXiv comment47 pages, 4 figures