- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies how query-pool geometry affects the optimal Bayes prediction risk under a limited label budget. The authors compare fixed, two-batch, and fully adaptive acquisition under random and structured query pools. The main result shows that, within a certain budget regime, a structured two-batch policy can achieve strictly lower asymptotic risk than even fully adaptive acquisition on random pools. The paper also provides numerical experiments to support the theoretical findings.
Critical strengths
I think the paper studies an interesting question about how the geometry of the available query pool affects the value of adaptive acquisition. The main result gives a nontrivial separation: with the same statistical model, pool cardinality, and label budget, a structured pool allows two-batch acquisition to outperform even fully adaptive acquisition on a uniformly random pool. This seems potentially interesting as a demonstration that the usefulness of adaptivity can depend strongly on query access geometry.
Critical weaknesses
My main reservation is that the theoretical setting seems rather specialized, relying on noisy binary affine functions with known regional structure and noise rates. It is not entirely clear to me how broadly the main insights extend to more general active learning problems.
In addition, the theoretical results allow unrestricted computation, and the proposed methods may be computationally expensive. I would appreciate more discussion of the practical implications of the results and whether similar advantages could be achieved by computationally efficient algorithms.
Questions for authors
-
How essential is the noisy affine prediction setting to the main separation result? I would be interested in understanding whether similar results could hold for more general function classes or active learning problems.
-
The main results concern statistical optimality without computational constraints. Do the authors see a promising direction toward computationally efficient algorithms that could achieve similar benefits from structured query pools?
4 comments
Finite-sample benefits of two-batch acquisition
As a small exact illustration, consider , , and a budget of nine labels. A four-point parity check followed by a five-label second batch matches the fully adaptive optimum on 18 common held-out targets, achieving a Brier risk of , compared with for both EPIG and one-step Brier acquisition (Appendices N.5 and O.2, Tables 19 and 24).
We hope these clarifications address your questions about which aspects generalize and when computationally efficient recovery is possible.
I thank the author for the detailed explanations! I find these clarifications helpful in understanding the scope of the paper better. I maintain my positive assessment, although this paper is somewhat outside my area of expertise.
Dear Reviewer 17Hf
Thank you for taking the time in reviewing our paper and positive assessment.
Best regards
Authors
Response to Reviewer 17Hf
Thank you for your constructive comments on model generality and computational efficiency. Our allocation argument provides a general framework, while establishing a separation for a new function class requires class-specific testing and recovery guarantees. The diagnostic stage is already computationally efficient, and polynomial-time recovery is also possible when the continuation coordinates can be designed.
Which parts extend beyond noisy affine rules?
General allocation conditions. Theorem 2 (Appendix A) isolates two conditions underlying our random-pool lower bound:
When reaching the evidence cutoff in one region leaves insufficient budget for another to cross the recovery cutoff, at most one region can deliver substantial prediction gain. A strict separation additionally requires a structured-pool diagnostic test that improves regional allocation while preserving enough budget for recovery.
Finite sign dictionaries. In the uniform affine model, labels on affinely independent inputs are jointly fair, and independent flips exponentially attenuate the evidence in long parity checks. Theorem 3 (Appendix B) extends the low-count prediction bound to general finite sign dictionaries under independent flips through the dictionary's effective dimension. This generalizes one component of the lower bound; early indistinguishability, structured testing, and recovery still require class-specific proofs.
A contrasting Gaussian example. Appendix A.5 illustrates why separation is not universal. Both signal states induce identical query laws, and prediction improves with each observation. Fixed, two-batch, and fully adaptive acquisition therefore achieve identical risk for all budgets 0≤b≤D, where D is the number of coordinates per region (Eq. 50).
Other loss functions. The separation also holds for log loss and 0-1 classification error. For a common fixed noise rate 0<η<1/2 and budget ratio c<λ<c+1, where c=[1−h2(η)]−1, Theorem 5 establishes a strict separation between structured two-batch and fully adaptive random-pool acquisition whenever public information leaves uncertainty about the signal location (Appendix F.4, Eqs. 109-110).
Further extensions within the affine model.
When is an efficient algorithm possible?
Diagnostic testing and uniform continuation. A Walsh-Hadamard transform evaluates the diagnostic subcube test in O(tlogt) operations for t=Θ((logr)2) block points, with r=d+1. Under the original uniform continuation, our exact computation of the full vector of population predictions takes O(d2d+b) arithmetic operations (Appendix I.1). Whether a polynomial-time predictor can attain the oracle limiting risk at a fresh uniform target under this continuation law remains open.
Polynomial-time recovery with designed continuation. Appendix T.1 gives a constructive route when the data collector can also design the continuation coordinates. Partition the slope coordinates into groups of size Klogr+O(1), with K sufficiently large, and vary one group at a time while holding the others at zero. Each group then has only polynomially many candidate affine rules. For fixed noise, a sampling ratio ρ with c<ρ<λ lets the second batch recover all groups with probability 1−o(1).
This construction preserves the pool cardinality and label budget while changing the continuation geometry. The resulting predictor attains the oracle limiting risk and requires O(d) operations per fresh target after polynomial-time recovery.