When Can Unlabeled Data Pools Replace Membership Queries?

Dravyansh Sharma

cs.LGOct 29, 2026

When Can Unlabeled Data Pools Replace Membership Queries?

Authors: Dravyansh Sharma

Organizations: Microsoft · Toyota Technological Institute at Chicago (TTIC)

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δ)))$ 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 $Ω(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 $n\ge3$ , for every unlabeled budget fixed in advance, some marginal satisfying both assumptions forces $Ω(1/\eps)$ labels. For isotropic $s$ -concave marginals in dimension $n\ge3$ , 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 $\tildeΘ(\eps^{-(n-2)/n})$ . This extends the range $s\ge-1/(2n+3)$ of previous sample-based guarantees, in the realizable setting.

Figures & tables

Panel of Figure 1 — Figure 1: Realizable regimes for isotropic $s$ -concave marginals in dimension $n\geq 3$ (axis not to scale). In the two lower rows, darker green marks class-uniform logarithmic disagreement with polylogarithmic labels, and lighter green the sharp polynomial rate. Each $\Theta$ entry is the sharp worst-case rate of the disagreement coefficient and, up to logarithmic factors and at constant confidence, of the labels needed with an unlabeled budget fixed in advance for the class. In the regimes marked $O(\log\frac{1}{\varepsilon})$ we prove only upper bounds. Label upper bounds go through CAL, and both lower bounds come from one packing lemma ( Lemma A.3 ). The red line marks the range $s\geq-1/(2n+3)$ covered by Balcan and Zhang (2017) . An unlimited pool keeps near-optimal labels for every finite $s$ . Only the first row uses Theorem 3.7 .

Work	Main resource and quantifiers	Relation to this paper
Hanneke et al. (2024)	Label budget $k$ . Unlabeled budget $u(k)$ fixed before execution. Rate constants may depend on the joint distribution $P$	Unlabeled budget fixed in advance, whereas ours is adaptive and marginal-dependent
Hanneke et al. (2025b)	Passive labeled sample size. Guarantees may depend on the marginal but are uniform over targets	Uniform over targets, as our precision is, but about passive sample size rather than active labels

Table 1: Quantifier comparison with recent distribution-sensitive frameworks.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Item of Hopkins et al. (2020b)	Statement and hypotheses	Use here and where re-verified
Def. 3.3, Lemma 3.4 (margin oracle)	A $\lambda$ -representative of a sample $S$ is a point $x_{S}$ with $\lambda^{-1}A_{S}\leq\|m(x_{S})\|\leq\lambda A_{S}$ . The Gaussian combination $x_{S}=\sum_{i}g_{i}x_{i}$ is one with probability at least $1-5/\lambda$ for $\lambda\geq 5$ . Oracle-free.	Same construction, restated with a norm bound and proved as Lemma B.4 .
Thm. 4.4 (PartialLearn), Lemma 4.6 (IsoLearn), Lemma 4.10 (StructureSearch), Lemma 4.15 (DimReduce)	The exact-query guarantees of the four subroutines. The proof of Thm. 4.4 simulates the margin oracle with $\lambda=\mathrm{poly}(d)/\delta_{0}$ and a union bound over oracle calls.	Replaced. Primed versions are proved under a subspace-relative oracle in Lemmas B.6 , B.7 and B.8 , with $\lambda$ polynomial in $d/\delta_{0}$ ( Section B.6 ). From Lemma 4.15 we reuse the three-query acceptance test against a scaled reference and the positive-semidefinite domination of spurious accepted subsets.
Def. 4.7 (structured pairs)	$(X,\omega)$ is $(k,t,\varsigma,c)$ -structured (their $s$ is our $\varsigma$ ) if $\Pr_{\omega}[\|m(x)\|\geq t]\geq k/d$ and $\Pr_{\omega}[\|m(x)\|\leq t/\varsigma]\geq 1-ck/d$ . The shorthand “ $(k,t,\varsigma)$ -structured” means $c=5$ .	We use $c=50$ , produced by Lemma B.6 . Lemmas B.7 and B.8 are proved for $c=50$ , so no statement about $c=5$ is invoked.
Claims 4.9, 4.12, 4.13	For $1/4$ -isotropic $(X,\omega)$ , the median of the largest normalized margin in a sample of size $\Theta(d)$ ( $10d$ there) is $\Omega(1/\sqrt{d})$ (4.9). An empirical median over $r$ subsets is a $2/5$ -median (4.12, Chernoff). Hence the level-zero representative has margin $\Omega(1/(\lambda\sqrt{d}))$ with probability $1-O(\delta_{0}/\log d)$ (4.13).	Not invoked. Level zero of Lemma B.6 reuses the isotropy argument from the proof of Claim 4.9 with samples of size $16d$ , and the round-robin quantile and the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality replace deterministic selection and Claims 4.12–4.13. This gives $\tilde{M}_{0}\geq 1/(4\lambda\sqrt{d})$ .
Claim 4.11	Sample-norm tail transfer for a $u$ -median. Oracle-free.	Restated and proved as Lemma B.5 .
Cor. 4.20 (with Lemmas 4.18, 4.19)	For every $(X,\omega)$ and $\varepsilon>0$ there are $1\leq k\leq d$ , a $k$ -dimensional subspace $V$ with $\omega(X\cap V)\geq k/d$ , and an invertible $T:V\to V$ putting the normalized restriction in $\varepsilon$ -isotropic position. Lemma 4.18 is the theorem of Barthe (1998) in the form stated by Dvir et al. (2017) , and Lemma 4.19 characterizes when such a transform exists. Oracle-free.	Used by PartialLearn ′ ( Section B.6 ). Since $\omega(X\cap V)>0$ , $V$ contains a passive-sample point, as Lemma 3.5 requires.

Appendix

Table 2: Results of Hopkins et al. (2020b) that we use or replace.

Assumption removed	Assumption kept	Labels, pool vs. membership queries (unlimited unlabeled data)
Symmetric full support	Hyperplane-nullness, even with a smooth symmetric density	$\Omega(1/\varepsilon)$ vs. $O(\log(1/\varepsilon))$
Hyperplane-nullness	Full support	$\Omega(1/\varepsilon)$ in expectation vs. $O(\log(1/\varepsilon))$
None	Both	No label gap. The unlabeled cost cannot be bounded uniformly ( Propositions 4.3 and 4.5 )

Appendix

Table 3: Role of each angular assumption. Without symmetric full support, unlimited unlabeled data cannot provide the informative directions. When both assumptions hold, informative directions are eventually available, but they can be so rare that no unlabeled budget fixed in advance finds them.

Input from Balcan and Zhang (2017)	Replacement (items of Theorem D.10 )
Theorems 9, 11 (density, bands)	Inner-ball density $\ell_{k}$ , upper density $\bar{f}_{\max}$ , and item (i)
Theorem 12 (angle vs. error)	Item (ii), with $c_{\chi}=\ell_{2}r_{0}^{2}$
Theorem 13 (outside-band error)	Item (iii), with $B$ from the radial-tail integral
Theorem 14 (conditional second moment)	Item (iv)
Lemma 28 (three-halfspace comparison)	Item (v)
Theorem 5 (norm tail)	Integration of the $n$ -dimensional radial envelope

Appendix

Table 4: Substitutions into the Balcan–Zhang analysis.

Row of Figure 1	Previously established	Added here
Unlimited pool	Balcan and Zhang (2017) learn from samples for $s\geq-1/(2n+3)$ . Qualitative links between rich pools and membership queries ( Gonen et al., 2013 , Diakonikolas et al., 2024 )	A label bound uniform over admissible marginals and targets, for every finite $s$ . The unlabeled cost remains marginal-dependent
Balcan–Zhang tools	Balcan and Zhang (2017) for $s\geq-1/(2n+3)$ . Several geometric and moment facts are classical	Extended to $s>-1/(n+2)$ . Uniform constants fail at and below this threshold
Disagreement and fixed-pool labels, general class	Guarantees within the range of Balcan and Zhang (2017) . Threshold unknown	Logarithmic disagreement and polylogarithmic labels above $-1/(n+1)$ . Sharp exponent $(n-2)/n$ between $-1/n$ and $-1/(n+1)$ ( Section 5.1 ), and exponent one at and below $-1/n$
Disagreement and fixed-pool labels, symmetric class	Ball–Bobkov bodies and Fradelizi–Guédon–Pajor comparisons available as tools	Logarithmic disagreement and polylogarithmic labels for $s>-1/n$ . Exponent one at and below $-1/n$ , via the radial construction

Appendix

Table 5: Before-and-after comparison for Figure 1 .

Regime	Unlimited-pool labels	Labels with an unlabeled budget fixed in advance
$n=2$ , every finite $s$	Polylogarithmic	Polylogarithmic, CAL ( Proposition D.16 )
$n\geq 3$ , $s>-1/(n+1)$	Polylogarithmic	Polylogarithmic, CAL on $\tilde{O}(n/\varepsilon)$ points ( Corollary D.15 )
$n\geq 3$ , symmetric, $s>-1/n$	Polylogarithmic	Polylogarithmic, CAL ( Theorem D.21 )
$n\geq 3$ , general, $-1/n<s\leq-1/(n+1)$	Polylogarithmic ( Theorem 3.7 )	$\tilde{\Theta}_{n,s}(\varepsilon^{-(n-2)/n})$ , polynomial pool suffices ( Corollaries G.1 , G.2 and D.33 )
$n\geq 3$ , $s\leq-1/n$ , either class	Polylogarithmic ( Theorem 3.7 )	$\Theta(1/\varepsilon)$ for fixed $n$ ( Theorem D.28 ; passive upper bound $O((n+\log\frac{1}{\delta})/\varepsilon)$ ( Hanneke, 2016 , Bousquet et al., 2020 ) )
Elliptical laws, any tails	Polylogarithmic	Polylogarithmic, $\theta_{D}=O(\sqrt{n})$ ( Proposition D.17 )

Appendix

Table 6: Status by regime, at constant confidence. Polynomial entries are optimal rates achievable with an unlabeled budget fixed in advance, and the lower bounds hold for every such budget. Unlimited unlabeled access removes these polynomial label barriers.

Model	What it provides	Limitation under feedback-induced shift
Fixed offline pool	Selective annotation of previously generated states	Cannot acquire states absent from exploration
Interactive pool	Fresh candidates generated at learner-induced prefixes, then selectively annotated	Requires exploration and supervision on the evolving state distribution
Membership queries	Labels of constructed admissible prefix–candidate pairs	Useful only if such states can be constructed and reliably labeled

Appendix

Table 7: Access models for verifier supervision.

Training interface	Expert supervision	State access for the upper bound
Successful-trace BC	$\Theta(M\log(1/\delta))$ demonstrations	Same number of accepted states
Offline active annotation	$\log_{2}M$ verdicts	$O(M\log(M/\delta))$ i.i.d. proposals
Interactive verification	$\log_{2}M$ verdicts	$\log_{2}M$ controlled proposals

Appendix

Table 8: Resources of the three training interfaces in Theorem E.13 , with

M=2^{m}

targets.

Active Learning

Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.

See all 312 papers

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
Nov 3, 2026Zhijie ZhengHalfspace Learning Statistical Learning Theory
Peking University
On the Sample Complexity of Active Learning with Membership Queries
Sep 23, 2026Ganghua Wang, Shaddin DughmiActive Learning Statistical Learning Theory
Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California
Robust Regression of General ReLUs with Queries
Jun 9, 2026Ilias Diakonikolas, Daniel M. Kane, Mingchen MaReLU Neural Networks Active Learning
University of Wisconsin-Madison · University of California, San Diego

Nov 3, 2026J/K move · Enter open · S save

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

Zhijie Zheng

Peking University

Halfspace Learning Statistical Learning Theory

Open paper AskPDF arXiv

We give a proper constant-factor agnostic learner for affine halfspaces under full-dimensional log-concave marginals. For arbitrary binary labels, the algorithm uses independent labeled samples and returns a single affine halfspace with error at most

C\mathrm{OPT}+\varepsilon

. Its sample and real-arithmetic complexity are polynomial in dimension, inverse accuracy, and the logarithm of the reciprocal failure probability. The mean and covariance of the marginal need not be known, and the sample complexity can be made linear in this logarithmic confidence factor. The main geometric result compares global disagreement with disagreement on a balanced restriction: for a minority halfspace of mass

p

, global disagreement is within universal constant factors of

p

times conditional disagreement, provided the latter is sufficiently small. To construct the restriction from noisy labels, we estimate the minority cap's mean and covariance robustly, approximately minimize the classical zonoid-depth dual objective, and expand a superlevel set to a marginal quantile. The disagreement comparison cancels the noise amplification caused by conditioning and allows the learned halfspace to be used on the entire space. The analysis combines degree-four sum-of-squares moment bounds for log-concave laws with a translation-based reduction from balanced affine learning to homogeneous halfspace learning.

Abstract

Active Learning

Explore similar work

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

On the Sample Complexity of Active Learning with Membership Queries

Robust Regression of General ReLUs with Queries