acceptodds
Under review as a conference paper at ICLR 2027

The Price of Choice in Selective Prediction

Abstract

A vendor may claim that some rule from a predeclared menu—a score threshold or a union of score intervals—lets its selective classifier keep a fraction of inputs while erring on at most a fraction of them. Refuting such an existential claim means ruling out every permitted rule at once. The intersection–union test (IUT) does this without a multiplicity correction, but its sample cost as the menu grows, and how close that cost is to the best valid audit, are not captured by the level argument. We characterize both. For a fixed interior risk target , menus of intervals and a risk gap , in the small-gap, large-menu regime of our theorem the minimax sample size at each fixed coverage floor is up to logarithmic factors, and the exact IUT attains it: menu richness costs times the abstention odds, even though validity costs nothing. The lower bound holds for audits that know the score distribution; the upper bound extends to any menu of VC dimension . We then explain the linear cost. Every certificate that never rejects while some rule looks feasible on the audit data—the IUT, Bonferroni, DKW and uniform-convergence bounds—pays it even at laws where samples suffice, because the best-looking rule is optimistically biased. We then identify when the gap can and cannot be avoided: against constant-risk alternatives a reference-free audit reaches the testing scale, including the square-root rate on the sign family in its stated small-gap regime, whereas over a rich class with unknown heterogeneous risk the linear cost is unavoidable up to a logarithm. In simulation with , the raw menu cost changes 7.7-fold between and ; after dividing by the abstention odds and the theorem-motivated localized-VC logarithmic normalization used in Figure 1, the two endpoint values differ by about 5%. Held-out model families show that the same feasible-mixture mechanism is not confined to synthetic constructions: across three contemporary VLM judges, all 60 split-specific confidence-gate families have positive exact-hiding windows and 28/30 contracts selected on audit-A remain hidden on untouched audit-B; on the cleaner multi-annotator Polaris target, hiding persists on all 20 splits but is much narrower and transfers in 3/10 resplits. Frozen image and multimodal classifiers separately show boundary behavior consistent with the exact IUT guarantee and strong power relative to the practical certificates we compare.

Primary area:
learning theory
Keywords:
selective prediction, learning theory, hypothesis testing, model auditing, risk control, minimax testing, intersection-union testing, abstention

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_mB6oOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper works with the following problem: if a vendor of some model claims that some configuration of the model meets some performance guarantee, how much data does an auditor need to prove the vendor false? They propose using an intersection-union test (IUT) and show that while you don't need to do multiple-testing corrections on it to control the false discovery rate, its sample complexity does increase as the possible number of configurations increases, so it's not "free" to have many configurations. They also establish a distinction between estimation and testing, showing that in certain settings their IUT can be less sample-efficient than optimal tests, and investigate when this gap can be avoided. They then also conduct some experiments using both synthetic and real data to illustrate their findings.

Critical strengths

The statistical problem presented in this paper seems well-defined. The theoretical results also seem interesting, like the sample-complexity guarantees, the distinction they present between testing and estimation, trying to characterize when auditing can be made more efficient, and having many cases of empirical evaluation.

Critical weaknesses

This paper is extremely difficult to read.

In the abstract, there is no motivation provided for the problem. The opening sentence is dense enough that someone not very familiar with this area might have no idea what this paper is about. The rest of the abstract reads as if it contains all the results of the paper compressed into a short paragraph, but this has the effect of making it unreadable. Towards the end of the abstract, for example, the references to "audit-A" and "audit-B" and "the cleaner multi-annotator Polaris target" are all provided without any context, so the reader cannot infer what they mean.

The introduction provides some motivation for the problem, but it is not clear where this would occur in real life. Say that a hospital is buying an AI classifier, and it needs it to make predictions on at least 90% of patients and make errors on at most 10% of them. A "configuration" might be defined as the confidence threshold that the model needs to make a prediction (e.g., the model will predict if its confidence is at least 80%). Now say that there are many such possible configurations. Why would the hospital want to buy a system just on the claim that some configuration will work for their requirement, without knowing which one? Maybe there are other cases where it does make sense, but they are not obvious to me. It would be good to provide better motivation for this problem.

The introduction also says "This is the dual of risk control and Learn-then-Test, which certify one rule selected by calibration." However, I don't think the paper formalizes a duality. The meaning of this sentence should be made more precise. Additionally, the average reader of ICLR might not be familiar with Learn-then-Test, so some context might be helpful. Shortly after that, the phrase "one fixed witness rule" isn't obvious in its meaning. Line 55 mentions a "gap" but that term hasn't been defined; γ\gamma is defined as the "risk gap" in line 58 but again it's not clear what that means. The explanation of the "main result in one line" is also not very clear (e.g., the phrase "the auditor must rule out that the errors happen to be concentrated there, and the error mass of such a region fluctuates on the scale of that region, not of the whole sample"). The notion of EFC is introduced without much motivation (and an expansion of the acronym is not given until much after the term is first used).

In Section 2, line 156, δ\delta is used to explain "the exact IUT" before it is introduced in Proposition 1. It might also help to motivate why EFCs are an important class of audits to study. Additionally, it's not clear why it should be called a "certified frontier".

In Theorem 1 of Section 3, it seems like the statement holds for large values of KK and α\alpha bounded in specific way, so it might be helpful to give some intuition as to which settings would one expect this to hold (eg if there was a concrete running example, it could be used here to illustrate the theorem).

Section 4 starts with "the reference P0P_0...", but this implies that it has already been discussed. There's no motivation or context given here. When the text then says "it is infeasible," it's unclear what that means.

The opening sentence of Section 5 could use some context.

In Section 6.3 line 359, the αH,αind\alpha_H, \alpha_\text{ind} are undefined, and the description "exact fixed-marginal hiding window" is not clear. WhideW_\text{hide} is also undefined.

In the experimental protocol in general, there are a lot of undefined terms like 'three-way resplits', ''confidence channels', 'midpoint contracts', and 'transfer'.

Section 7 does not read like a typical related works summary and rather as a list of works. It would be helpful to position this paper amidst the related work and explain its novelty. This is in particular important given the theoretical nature of this work. The limitations are likewise presented as a semicolon-separated list, and some more explanation would be helpful.

In sum, this paper does not feel like it is ready for publication yet; the theoretical results seem interesting but a much clearer writing style and presentation is necessary.

Questions for authors
  1. In Section 2, Eq 3 is very dense and seems to be optimizing over many things; a plain-language explanation would be very helpful.
  2. In Section 2, Eq 4 "the exact IUT," the RHS of the equation minimizes over AA but then the LHS depends on AA. This seems to be inconsistent.
  3. In Section 3, a mathematical definition of "robustly infeasible" is given, but a plain-language explanation/intuition would be very helpful. E.g., why should the alternative be strengthened in this way?
  4. In Section 3, Thm 1, the explanation given below the theorem is very dense. For example, in saying "the magnitudes match their first log KK even moments but differ in their mean by the best polynomial approximation error of u\sqrt{u}," it would be helpful to explain why moment matching or polynomial approximation arise, or how they relate to your auditing problem.
  5. Later in Line 227, "The logarithmic gaps and constants remain open," what exactly does this mean?
  6. In Section 4, in the "sign families" setup, there is again very dense notation. Could you provide a toy example to help in illustrating what is going on?
  7. In Section 4, why is the "effective dimension" introduced? What is its purpose?
  8. In Section 5 what motivates the move to unknown heterogeneous risk? I think this theorem and the previous one differ in their assumptions but clear motivation could be helpful.
  9. In the right panel of Fig 1, there is a very specific logarithmic factor used to divide the values of the curves; could you provide some motivation for this?
Reviewer_hVGYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This is a theoretical paper that analyzes how many samples an auditor needs in order to separate models exhibiting a “feasible law” from models exhibiting an “infeasible law.”

The feasibility of a model’s behavior is defined with respect to a set of rules (Equation 2). The rules could be used in many ways to estimate feasibility; however, the authors focus on “the exact IUT,” which combines the rules in a particular way (Equation 4). If infeasible laws are required to exceed the risk ceiling by a margin γ (a parameter in their formalism), then bounds on the number of samples can be proved (Proposition 2 and Theorem 1). The paper proves tighter bounds for a more specialized class of families of rules and infeasible laws. Using this class, the authors show that the cost is linear in the number of intervals in the rules (Theorems 3 and 5). With more information or structural assumptions, the auditor may avoid the linear cost (Theorems 2 and 4). Using simulations, the authors illustrate the predictions of the theory. They also apply their method to real-world models (Sections 6.3 and 6.4). In Section 6.3, they show that the hiding mechanism from the theory is visible in the experiments. In Section 6.4, they show that the exact IUT performs much better than the other certificates compared.

Critical strengths
  1. The paper develops a novel theory of the number of samples needed for auditing.
  2. It gives bounds on the number of samples needed, and tighter bounds in specialized cases.
  3. It shows that the exact IUT achieves the bound.
  4. The experiments are well designed to illustrate the important aspects of the theory.
Critical weaknesses

The paper was very difficult to read. Here are the places where I got stuck:

a. How a rule works is non-trivial in this paper: it involves K intervals and M cells. It is not clearly explained how this all works; I could only understand it after piecing together many parts of the paper.
b. N_IUT is used with a single argument in Theorem 1 and with no argument after Theorem 3. This is never explained.
c. In line 235, Δ_{B−1} is called a simplex, but it is never defined, and its significance is never explained.
d. In line 233, the sign family is described, but its exact definition is never made clear.
e. In Proposition 3, a level-δ audit is never defined.
f. In Theorem 2, 𝓗_{B,k} is never defined.
g. M is used in line 161 (and in Table 1’s caption) but is defined only in Section 5 (line 280).
h. What is VC in line 240?

I cannot comment on the importance of the results because I am not an area expert.

Questions for authors
  1. Why do you consider rules that are unions of intervals? How should K be chosen in practice?
  2. Could you provide an illustrative example of audit rules, for instance in an appendix, so that readers can understand the meaning of the theorems through concrete examples?
Reviewer_AwkBOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies sample complexity of selective classifier where multiple hypothesis needs to be tested under the IUT. While the main result is intuitive and makes sense to me, my understanding of the paper is severly hindered by the clarity issues.

Critical strengths

None

Critical weaknesses

The paper in its AI usage statement claims that AI was used to improve the clarity as well as the presentation of the work. However, I have several questions starting right from the abstract (see below):

  1. what is menu?
  2. what is a union of KK score intervals?
  3. what is best valid audit?
  4. And most importantly, what is level argument?
  5. what is interior risk?
  6. what does it mean to say "in the small-gap"?
  7. What does it mean to say "coverage floor"?

I think I can go on, but unfortunately, I've struggled quite to make sense of even the first four-five sentences of the abstract. Let's come to the intro: the problem can simply be stated as studying the sample complexity for selective classification where multiple hypothesis needs to be test to certify the selective classifier, which by itself is an interesting problem, however the intro reaches there with a language that clearly is not optimised for clarity and presentation. Instead, it seems AI written with minor or no editing. I get that the conference allows AI usage, however it also requires honest disclosure of it. Unfortunately, my reading of the draft suggests the writing largely AI written in an unedited manner, and not optimised for the reader.

Additionally, because of the same presentation issues, I was not able to verify the technical claims.

Questions for authors

None

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.