@inproceedings{
diakonikolas2024active,
title={Active Learning of General Halfspaces: Label Queries vs Membership Queries},
author={Ilias Diakonikolas and Daniel Kane and Mingchen Ma},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=eXNyq8FGSz}
}
We study the problem of learning general (i.e., not necessarily homogeneous) 
halfspaces under the Gaussian distribution on $\mathbb{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{\Omega}(d/(\log(m)\epsilon))$, where $m$ is the number of unlabeled examples. 
Specifically, to beat the passive label complexity of $\tilde{O}(d/\epsilon)$, 
an active learner requires a pool of $2^{\mathrm{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/p, 1/\epsilon) + d\mathrm{polylog}(1/\epsilon))$
achieving error guarantee of $O(\mathrm{opt}+\epsilon)$. Here $p \in [0, 1/2]$ 
is the bias and $\mathrm{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.
Active Learning of General Halfspaces: Label Queries vs Membership Queries
Ilias Diakonikolas Daniel Kane Mingchen Ma