Active Learning of General Halfspaces: Label Queries vs Membership Queries

We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on $R^d$ in the presence of some form of query access. In the classical pool-based active learning model, where the algorithm is allowed to make adaptive label queries to previously sampled points, we establish a strong information-theoretic lower bound ruling out non-trivial improvements over the passive setting. Specifically, we show that any active learner requires label complexity of $\tilde{\mathrm{\Omega }}(d\mathrm{/}(\log (m)\epsilon ))$, where $m$ is the number of unlabeled examples. Specifically, to beat the passive label complexity of $\tilde{O}(d\mathrm{/}\epsilon )$, an active learner requires a pool of $2^{poly(d)}$ unlabeled samples. On the positive side, we show that this lower bound can be circumvented with membership query access, even in the agnostic model. Specifically, we give a computationally efficient learner with query complexity of $\tilde{O}(\min \{1\mathrm{/}p,1\mathrm{/}\epsilon \}+d\cdot polylog(1\mathrm{/}\epsilon ))$ achieving error guarantee of $O(opt)+\epsilon$. Here $p\in [0,1\mathrm{/}2]$ is the bias and $opt$ is the 0-1 loss of the optimal halfspace. As a corollary, we obtain a strong separation between the active and membership query models. Taken together, our results characterize the complexity of learning general halfspaces under Gaussian marginals in these models.