- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2(+1)
Read review
Paper summary
The paper studies the statistical validity of certifying threshold-based decisions when evaluation observations are not fully independent. The authors consider two dependence structures: (r)-wise independence and independent clusters with potentially dependent observations. Using symmetrisation and discrete moment problems, they derive finite-sample certification procedures, exact sample-complexity results, and primal-dual certificates of validity or impossibility.
Critical strengths
The paper addresses a fundamental weakness of many ML evaluation protocols: treating correlated outcomes as independent observations and consequently overstating the statistical evidence supporting performance claims.
The experiments demonstrate that a large number of observations does not necessarily imply a large effective evaluation sample. The LLM example, with 9,000 generations from only 180 prompts, is particularly relevant to current evaluation practices.
Critical weaknesses
1/ there is a huge litterature in the statistical community about assumptions that weaken independence. None is studied here.
2/. The results rely heavily on common Bernoulli marginals and specific independence assumptions across clusters. Heterogeneous populations, unequal cluster sizes, adaptive evaluation designs, and dependence across clusters are important in practice but are not fully covered by the proposed guarantees.
3/T he theoretical analysis is compelling, but (r)-wise independence is difficult to justify empirically. In realistic applications, dependence is generally induced by shared latent factors, prompts, patients, or temporal structure. The paper acknowledges this limitation, but it considerably reduces the direct operational relevance of the central hierarchy.
Questions for authors
1/ How should practitioners justify an independence order?
2/Why optimise nominal retention under full independence?
3/What is the precise boundary of theoretical novelty? Since moment-constrained minimax tests, polynomial duality, and limited-independence concentration bounds are established, could the authors more clearly identify which mathematical results are genuinely new and which follow from adaptations of known techniques?
Thank you for the review and for recognising that the paper addresses a fundamental weakness of many ML evaluation protocols. Your questions helped us sharpen the paper, and one of them led to a new result.
Question 1:
Answer: In practice, the guarantees come from the cluster audits of Propositions 2 and 3. These only ask that clusters, such as patients or prompts, are independent of each other, which is a matter of how the evaluation was designed. Within a cluster, the dependence can be anything. Therefore, a practitioner does not have to argue for a particular independence order. An order can be justified directly when units are selected with a k-wise independent hash (Carter & Wegman, 1979), as described in the introduction and Section 5, because the outcomes are then k-wise independent by construction. The hierarchy of orders plays a different role, as a sensitivity analysis. By Lemma 1, the worst case at each order is a hidden common factor that matches independence in its first r moments, and the robustness order tells us how many of these moments a conclusion actually depends on. We will make this clearer in the introduction.
Question 2:
Answer: Thank you for this question. It made the paper stronger. We asked for validity in the worst case because that is what a certificate promises. Retention is different. It describes how useful the audit is when the system does meet its target, so we first measured it under the design the evaluator actually intends to use, which also gives every independence order the same benchmark and makes their sample sizes comparable. Your question led us to go one step further and certify the sample sizes when retention is also required in the worst case. As the table shows, this costs at most 13% more units. For clustered designs, Proposition 2 already asks for retention under every cluster law.
Question 3:
Answer: The novelty lies in the problem and its exact solution. We pose certification under limited independence as a test design problem over a continuum of null rates and solve it exactly. This yields exact minimum sample sizes with matching rational certificates in both directions (Theorems 1 and 2), the scaling law in α, whose lower bound holds for every procedure (Proposition 4), the fact that odd orders help only through the range of the count (Theorem 3), and the exact characterisation of clustered designs (Proposition 2), which pairs a lower bound from perfectly dependent clusters with a one unit per cluster design. These results are new. They build on established tools, such as moment problem duality (Prékopa, 1990), moment constrained minimax tests (Magesh et al., 2023) and tail bounds under limited independence (Schmidt et al., 1995). Those tools bound the tail of a statistic chosen in advance, whereas we use them to design the test itself. The introduction and Section 6 draw this distinction, and we will sharpen it in the list of contributions and extend the comparison in Section 6 with other ways of weakening independence, such as mixing and association.
Every result is proved in the appendix, and every exact claim can be checked with the verifier we released. If any step still raises a concern, we would be glad to go through it.
References
Carter, J. L. and Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143–154.
Magesh, A., Sun, Z., Veeravalli, V. V. and Zou, S. (2023). Robust hypothesis testing with moment constrained uncertainty sets. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).
Prékopa, A. (1990). The discrete moment problem and linear programming. Discrete Applied Mathematics, 27(3), 235–254.
Schmidt, J. P., Siegel, A. and Srinivasan, A. (1995). Chernoff–Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2), 223–250.