[Submitted on 29 Oct 2026]
Abstract:Membership queries let a learner label arbitrary points and give near-optimal $tilde O(nlog(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(nlog^3nlog(n/(epsdelta)))$ labels, uniformly over all such marginals and targets, without density, moment, concavity or isotropy assumptions. The same label bound holds for non-homogeneous halfspaces under every marginal with full support and no mass on affine hyperplanes, including Gaussians. Dropping either angular assumption admits $Omega(1/eps)$ pool versus $O(log(1/eps))$ membership-query separations, even with unlimited unlabeled data. The price is paid in unlabeled data: in dimension $nge3$, for every unlabeled budget fixed in advance, some marginal satisfying both assumptions forces $Omega(1/eps)$ labels. For isotropic $s$-concave marginals in dimension $nge3$, unlimited pools keep logarithmic label rates for every finite $s$. With an unlabeled budget fixed in advance, class-uniform polylogarithmic rates hold exactly for $s>-1/(n+1)$, or $s>-1/n$ under central symmetry, and in the general class the optimal rate between these thresholds is $tildeTheta(eps^{-(n-2)/n})$. This extends the range $sge-1/(2n+3)$ of previous sample-based guarantees, in the realizable setting.
Submission history
From: Dravyansh Sharma [view email]
[v1] Thu, 29 Oct 2026 21:34:42 UTC (129 KB)
