Characterizes how many queries are needed to learn a general (possibly non-homogeneous) halfspace over R^d when the inputs are Gaussian. In the pool-based active learning model the label complexity is essentially no better than passive PAC learning unless the unlabeled pool is exponentially large, an information-theoretic barrier. Allowing membership queries, where the learner requests the label of any point it chooses, breaks the barrier with a computationally efficient agnostic learner, giving a provable separation between the two query models.
This paper determines how efficiently a general (not necessarily homogeneous) halfspace over R^d can be learned when the data follow a Gaussian distribution and the learner may ask queries. In the po…