Membership queries let a learner label arbitrary points and give near-optimal 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(nlog3nlog(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≥3, for every unlabeled budget fixed in advance, some marginal satisfying both assumptions forces Ω(1/\eps) labels. For isotropic s-concave marginals in dimension n≥3, 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 Θ~(\eps−(n−2)/n). This extends the range s≥−1/(2n+3) of previous sample-based guarantees, in the realizable setting.
Figures & tables
Figure 1: Realizable regimes for isotropic s -concave marginals in dimension n≥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 Θ 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ε1) 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≥−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 λ -representative of a sample S is a point xS with λ−1AS≤∣m(xS)∣≤λAS . The Gaussian combination xS=∑igixi is one with probability at least 1−5/λ for λ≥5 . Oracle-free.
Same construction, restated with a norm bound and proved as Lemma B.4 .
The exact-query guarantees of the four subroutines. The proof of Thm. 4.4 simulates the margin oracle with λ=poly(d)/δ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 λ polynomial in d/δ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,ω) is (k,t,ς,c) -structured (their s is our ς ) if Prω[∣m(x)∣≥t]≥k/d and Prω[∣m(x)∣≤t/ς]≥1−ck/d . The shorthand “ (k,t,ς) -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,ω) , the median of the largest normalized margin in a sample of size Θ(d) ( 10d there) is Ω(1/d) (4.9). An empirical median over r subsets is a 2/5 -median (4.12, Chernoff). Hence the level-zero representative has margin Ω(1/(λd)) with probability 1−O(δ0/logd) (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 M~0≥1/(4λ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,ω) and ε>0 there are 1≤k≤d , a k -dimensional subspace V with ω(X∩V)≥k/d , and an invertible T:V→V putting the normalized restriction in ε -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 ω(X∩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
Ω(1/ε) vs. O(log(1/ε))
Hyperplane-nullness
Full support
Ω(1/ε) in expectation vs. O(log(1/ε))
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 ℓk , upper density fˉmax , and item (i)
Theorem 12 (angle vs. error)
Item (ii), with cχ=ℓ2r02
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≥−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≥−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≥3 , s>−1/(n+1)
Polylogarithmic
Polylogarithmic, CAL on O~(n/ε) points ( Corollary D.15 )
n≥3 , symmetric, s>−1/n
Polylogarithmic
Polylogarithmic, CAL ( Theorem D.21 )
n≥3 , general, −1/n<s≤−1/(n+1)
Polylogarithmic ( Theorem 3.7 )
Θ~n,s(ε−(n−2)/n) , polynomial pool suffices ( Corollaries G.1 , G.2 and D.33 )
n≥3 , s≤−1/n , either class
Polylogarithmic ( Theorem 3.7 )
Θ(1/ε) for fixed n ( Theorem D.28 ; passive upper bound O((n+logδ1)/ε) ( Hanneke, 2016 , Bousquet et al., 2020 ) )
Elliptical laws, any tails
Polylogarithmic
Polylogarithmic, θD=O(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
Θ(Mlog(1/δ)) demonstrations
Same number of accepted states
Offline active annotation
log2M verdicts
O(Mlog(M/δ)) i.i.d. proposals
Interactive verification
log2M verdicts
log2M controlled proposals
Appendix
Table 8: Resources of the three training interfaces in Theorem E.13 , with M=2m targets.
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 COPT+ε. 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.
This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.
Ganghua Wang, Shaddin Dughmi
Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California
We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses poly(d,1/ε) labeled examples and outputs a hypothesis with error O(opt)+ε, where opt is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses dpolylog(1/ε)+O~(min{1/p,1/ε}) black-box label queries, where p is the bias of the target function, and achieves error O(opt)+ε. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires Ω~(d/ε) labels, unless it draws a super-polynomial number of unlabeled examples.
Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma
University of Wisconsin-Madison · University of California, San Diego