Learning Functions of Halfspaces Using Prefix Covers
Parikshit Gopalan, Adam R. Klivans and Raghu Meka JMLR W&CP 23: 15.1 - 15.10, 2012
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 O((nk/ε)k+1) under any product distribution on {0, 1}n using read-once branching programs as a hypothesis. This gives the first poly(n, 1/ε) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on {0, 1}n previously known algorithms had an exponential dependence either on the accuracy parameter ε 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.
