Holdout method enables unbiased evaluation of best-of-n selection policies
Holdout Best-of-N: Unbiased Evaluation and Its Cost
Computation and Language
Summary
Selecting the best option from many based on some scores can lead to overly optimistic estimates if the same scores are reused for evaluation. The authors studied how to fairly evaluate such selection processes using separate data for choosing and judging, proving it’s only unbiased if the number of evaluation scores is less than the number of selection scores. They provide formulas and methods to do this efficiently, showing the tradeoff between unbiasedness and evaluation accuracy as more scores are used.
What this means in practice
- •For machine learning engineers: Accurately evaluate model selection procedures by separating data for choosing and testing to obtain unbiased performance estimates.
- •For algorithm developers: Implement efficient unbiased evaluation algorithms for ranking or selection problems using scoring subsamples, guaranteeing reliable metric estimates.
A theory result. No direct application yet.
Authors
Shrey Shah, Yinheng Li
Abstract
Reusing the scores that select a Best-of-$N$ winner can overstate its expected reward. We study evaluation from a fixed matrix of $K$ independent scores per candidate for a policy that selects using $J$ fresh scores. A single estimator based only on this matrix is exactly unbiased for expected judge reward under every independent, stable collection of candidate-specific score laws if and only if $J<K$, for every pool size $M\ge N\ge2$. At $J=K-1$, the selector deepens as $K$ grows. For independent Gaussian scores with common variance and fixed $M\ge N\ge2$, the unbiased minimax risk in this regime is of order $σ^2/\sqrt K$, attained by Holdout; allowing bias improves the rate to $σ^2/K$. For two candidates, we derive the minimum-variance unbiased estimator at known variance and the sharp asymptotic unbiased minimax constant $1/(π\sqrt2)$, which Holdout attains without knowing the variance. The cyclic average over subsets and ties can be computed in $O(MK\log M)$ operations. At fixed selector depth, cyclic evaluation of bounded scores has $O(K^{-1})$ risk uniformly in pool size. The impossibility result concerns the fixed matrix: one additional fresh winner score permits unbiased evaluation of the all-$K$ policy.