Sample costs rise with rules in selective classification testing
The Price of Choice in Selective Prediction
Machine Learning
Summary
Selective classification means a system can choose when to make predictions, aiming to keep errors low while covering enough cases. The paper studies how much data is needed to trust decisions about which rules from a set actually meet error and coverage goals. The authors show that the more rules you test, the more samples you generally need, especially when you want strict guarantees. They explain when these costs can be avoided or are unavoidable, and confirm their findings with experiments on image classifiers and other models.
What this means in practice
- •For machine learning engineers: Determine the sample size needed to audit different decision thresholds in selective classifiers to ensure error and coverage guarantees.
- •For quality assurance teams: Assess the reliability of audit procedures that test multiple prediction rules simultaneously, improving validation of risky automated decisions.
Tested on simulated data.
Authors
Daniel Cieślak, Andrzej Czyżewski
Abstract
A selective classifier may be claimed to satisfy a risk-coverage contract if some rule from a predeclared menu (a threshold or a union of $K$ score intervals) attains coverage at least $κ$ and error at most $α$. Refuting this existential claim requires ruling out every permitted rule. The intersection-union test (IUT) achieves validity without a multiplicity correction, but its sample cost can increase with menu richness. We characterize this cost and compare it with the optimal audit. For a fixed interior risk target $α$ and gap $γ$, the minimax sample size for K-interval menus at coverage floor $κ$ is $K(1-κ)/(κγ^2)$, up to logarithmic factors, in the stated small-gap, large-menu regime; exact IUT attains this rate. The lower bound holds even with a known score distribution, while the upper bound extends to menus of VC dimension $d$. Procedures that refuse to reject whenever any rule appears feasible on the audit sample can pay a linear $K$ cost even when a square-root rate is possible. Reference-free testing reaches a smaller scale under constant-risk alternatives, whereas unknown heterogeneous risks can make the linear cost unavoidable. In simulations with $K=4$, the raw menu cost varies 7.7-fold between $κ=.5$ and $κ=.95$; after theorem-motivated normalization the endpoint values differ by approximately 5%. Held-out experiments with three VLM judges show positive exact-hiding windows in all 60 split-specific confidence-gate families, with 28/30 contracts chosen on audit-A remaining hidden on untouched audit-B. On a cleaner multi-annotator target, hiding is weaker and transfers in 3/10 resplits. Frozen image and multimodal classifiers show boundary behavior consistent with the IUT guarantee and strong power relative to practical certificates.