When Can Unlabeled Data Pools Replace Membership Queries?

arXiv:2610.41001v1 Announce Type: new Abstract: Membership queries let a learner label arbitrary points and give near-optimal $\tilde O(n\log(1/\eps))$ label complexity for halfspaces under every marginal. A pool learner may label only sampled points. We ask when unlabeled data can replace membership queries. For homogeneous halfspaces the answer depends only on the angular law of $X/\|X\|$. If this law assigns zero mass to every hyperplane through the origin and positive mass to every nonempty open set of directions together with its reflection, a pool learner uses $O(n\log^3n\log(n/(\eps\delta)))$ labels, uniformly over all such marginals and targets, without density, moment, concavity or isotropy assumptions.