Learning Functions of Halfspaces Using Prefix Covers
Abstract
We present a simple query-algorithm for learning arbitrary functions of k halfspaces under any product distribution on the Boolean hypercube. Our algorithms learn any function of k halfspaces to within accuracy ε in time \emphO((nk/ε)^k+1) under any product distribution on 0, 1^\emphn using read-once branching programs as a hypothesis. This gives the first \emphpoly(n, 1/ε) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0, 1^\emphn previously known algorithms had an exponential dependence either on the accuracy parameter ε or the dimension \emphn. To prove this result, we identify a new structural property of Boolean functions that yields learnability with queries: that of having a small prefix cover.
Cite
Text
Gopalan et al. "Learning Functions of Halfspaces Using Prefix Covers." Proceedings of the 25th Annual Conference on Learning Theory, 2012.Markdown
[Gopalan et al. "Learning Functions of Halfspaces Using Prefix Covers." Proceedings of the 25th Annual Conference on Learning Theory, 2012.](https://mlanthology.org/colt/2012/gopalan2012colt-learning/)BibTeX
@inproceedings{gopalan2012colt-learning,
title = {{Learning Functions of Halfspaces Using Prefix Covers}},
author = {Gopalan, Parikshit and Klivans, Adam R. and Meka, Raghu},
booktitle = {Proceedings of the 25th Annual Conference on Learning Theory},
year = {2012},
pages = {15.1-15.10},
volume = {23},
url = {https://mlanthology.org/colt/2012/gopalan2012colt-learning/}
}