Efficient algorithm learns best halfspace classifiers with few errors
Efficient Proper Agnostic Learning of Halfspaces
Data Structures and AlgorithmsComputational Complexity
Summary
The authors developed a faster method to find the best dividing rule (called a halfspace) that separates data into two categories, even when some data points are mislabeled or noisy. Their algorithm works over inputs made of ±1 values and improves on previous methods by running quickly as the data size grows, regardless of the desired precision. It uses asking questions about specific data points but can also work with just random examples. This means it can find nearly the best way to classify data more efficiently than before.
What this means in practice
- •For machine learning engineers: Design better classifiers that find near-optimal halfspace boundaries quickly even when data is noisy
- •For software developers in data analytics: Implement efficient classification models for high dimensional Boolean data with guaranteed low error rates
Authors
Anindya De, Elchanan Mossel, Shivam Nadimpalli, Joe Neeman
Abstract
We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm1\}^n$. Given query access to an arbitrary function $f:\{\pm1\}^n \to \{\pm1\}$, our algorithm runs in time $\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}$ and outputs a halfspace with error at most $\mathrm{OPT}+\varepsilon$, 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/\varepsilon)}$, 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 $\{\pm1\}^n$ whose running time is polynomial in $n$ with an exponent independent of $\varepsilon$. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same $\mathrm{OPT}+\varepsilon$ guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on $\varepsilon$. 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 $\varepsilon>0$.