arXiv preprint ·
Efficient Proper Agnostic Learning of Halfspaces
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Semidirect sums of tensors and the matrix multiplication exponent
State Synthesis with an NP oracle
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.