Learning functions of halfspaces using prefix covers

Parikshit Gopalan, Adam Klivans, and Raghu Meka

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 eps in time O((nk/eps)k+1) under any product distribution on 0,1n using read-once branching programs as a hypothesis.. This gives the fifirst poly(n, 1/eps) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0,1n; previously known algorithms had an exponential dependence either on the accuracy parameter eps or the dimension n.

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.

Details

Publication typeInproceedings
Published inCOLT'12
PublisherJournal of Machine Learning Research
> Publications > Learning functions of halfspaces using prefix covers