- Rating
- 2(+1)
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies asymptotic minimax complexity for detecting positives from a set of items under the group testing framework. The authors also provide tight lower bounds by constructing hard instances and also study the complexity tradeoff under sparsity as well.
Critical strengths
This paper characterizes the number of queries required to identify a positive set of size , given that its ranks have a prescribed total displacement from the top positions. All ranks are measured with respect to a total order fixed before querying.
Critical weaknesses
I divide my criticism of the paper into three parts. a) Lack of connection to machine learning and b) Presentation and clarity issues.
Lack of connection to machine learning
I tried to read this paper carefully but I could find only minimal connection to machine learning, nor did the authors try to make any connection to machine learning community apparent in the paper. This seemed to me like a paper that might go into an Algorithms conference provided the writing and presentation issues are fixed in the paper.
Clarity issues
I found the paper quite hard to read and I feel that a lot of notations and terminologies are not set up the way they should be set up actually. Let me point a few of these below.
In section 3.2, the authors actually try to give the construction of a lower bound without being explicit about it. From section 3.2, the authors use terms like common active set, mutually disjoint negative pairs and the notion of a tree is never defined here at all actually. This makes the paper very hard to read without defining these technical terms. This problem remains throughout the paper.
Questions for authors
Please refer to the weakness section above.
5 comments
Response to Ukbb Part 2: Clarifying the setup, algorithm, and lower-bound construction
We revised Section 3.2 to state its lower-bound objective, start with a concrete example, and define the decision tree before deriving the bound. We also clarified the surrounding setup and algorithm descriptions. The key argument is self-contained below.
1. What the sets and pairs mean [W2: candidate sets and terminology].
A support is the set of positive ranks; a candidate support is one possible labeling at the prescribed positive count and AUC. To lower-bound the entire class, it suffices to construct a hard subfamily.
Take , , and . Let W be the first eight ranks, with later ranks negative:
| Candidate | Positive ranks | Deleted pair |
|---|---|---|
| S1 | 1, 2, 4, 5, 6, 7 | 3, 8 |
| S2 | 1, 2, 3, 5, 6, 8 | 4, 7 |
| S3 | 1, 2, 3, 4, 7, 8 | 5, 6 |
The original “common active set” W contains every candidate support. Each candidate deletes one pair, making that pair negative. “Mutually disjoint” means no rank belongs to two listed pairs. Every pair sums to 11, so each support has rank sum and displacement , hence identical AUC.
2. Why pooling cannot split this family evenly [W2: meaning of disjoint negative pairs].
An OR query is positive if its pool contains a positive item. Testing rank 3 gives a negative answer only for S1. Testing ranks 3 and 4 together is positive for all three candidates and reveals nothing.
A query is informative when its answer differs across remaining candidates. For a negative answer, every queried rank inside W must lie in the true deleted pair. Disjointness therefore allows at most one candidate to answer negatively; a positive answer retains all the others. Equal pair sums keep AUC fixed; disjointness restricts discrimination.
3. From this obstruction to a query lower bound [W2: decision tree and lower-bound objective].
A deterministic adaptive procedure is a binary decision tree: internal nodes specify queries, branches specify answers, and leaves output supports. Each informative negative branch isolates at most one candidate; the positive branch continues. A depth-t tree can therefore be correct on at most candidates.
For a randomized procedure with uniform budget t, fix its seed and apply the same bound. Averaging over m equally likely candidates and then over the seed gives average success at most . Per-candidate success of at least 2/3 requires .
Our general construction gives m proportional to D at every , with all candidates at exactly that displacement. This proves the linear-in-D lower bound.
4. Clarifications throughout the main text [W2: clarity beyond Section 3.2].
Beyond the example and tree argument in Section 3.2, we made these changes:
- Section 2: define support and rank coordinates, and distinguish instance cost from the class-wide uniform budget .
- Section 3: map the upper bounds and three lower-bound constructions before developing them.
- Section 4: explain the boundary window and rank-band fallback before the pseudocode; spell out generalized binary splitting and the scheduling rule.
- Section 5: describe the relevant classes through bandwise positive counts and common displacement.
We sincerely hope our revisions and responses address the concerns you raised and provide a clearer basis for reassessing the paper's contribution and relevance to the ML community.
Thank you again for your feedback. For details, please refer to the revised paper.
Follow-up to Ukbb on our response
Thank you again for taking the time to explain your concerns. We hope the clearer ML connection, revised definitions, and worked example address the issues you raised. Could you let us know whether any concerns remain? We would greatly appreciate your updated assessment and the opportunity to discuss them further with you.
Response to Ukbb Part 1: What a learned ranking guarantees about downstream recovery
Thank you very much for identifying where the ML connection and mathematical setup needed clearer explanation. Your comments prompted us to make the prediction-to-measurement connection explicit and revise the exposition across Sections 2–5. Our question is: how much can a learned ranking reduce the measurements needed to identify all positives?
1. From ranking evaluation to downstream measurement cost [W1: connection to ML].
A model ranks candidates before screening, while their true labels remain unknown. A pooled OR measurement asks whether a selected group contains a positive. The recovery algorithm uses the ranking and known positive count s to choose its tests.
Of the s(d−s) positive-negative pairs, let D be misordered. Empirical AUC is then 1−D/[s(d−s)]. This D also equals the total displacement of positive ranks from the first s positions: fixing the rank sum specifies exactly the possible labelings at a given AUC.
AUC evaluates pairwise ordering; our question is how that predictive quality translates into the cost of acquiring the remaining labels. When a learned ranking guides pooled screening, its operational value depends on the measurements it saves. The exact-AUC curve makes this connection quantitative: it gives the optimal worst-case recovery budget guaranteed by each quality level and shows how the required accuracy changes with sparsity.
This provides a task-dependent interpretation of ranking performance. A high AUC alone can conceal whether the prediction improves the recovery order; the characterization identifies when it does. The recovery algorithm receives only the ranking and s, not AUC, so the quality measure defines the performance benchmark without becoming an additional input required to exploit the prediction.
2. What this tells us about learned predictions [W1: implications for ML].
Revisions: The Introduction now opens with this prediction-to-measurement problem. Section 3.4 develops the sparsity-dependent accuracy requirement; Sections 6.2–6.3 evaluate learned HIV/PCBA rankings and same-AUC recovery costs. Our second response explains the changes to definitions and proofs.