Efficient active learning of sparse halfspaces

We study the problem of efficient PAC active learning of homogeneous linear classifiers (halfspaces) in ℝd, where the goal is to learn a halfspace with low error using as few label queries as possible. Under the extra assumption that there is a t-sparse halfspace that performs well on the data (t ll d), we would like our active learning algorithm to be em attribute efficient, i.e. to have label requirements sublinear in d. In this paper, we provide a computationally efficient algorithm that achieves this goal. Under certain distributional assumptions on the data, our algorithm achieves a label complexity of O(t · polylog(d, frac 1 ε)). In contrast, existing algorithms in this setting are either computationally inefficient, or subject to label requirements polynomial in d or frac 1 ε.