Sharp Bounds on the Winner’s Bias under Independent and Nonnegatively Correlated Noise

Reporting the best of \(M\) noisy but unbiased scores overstates the winner’s true value by up to \(c\sqrt{V}\), where \(V\) is the total noise variance and the constant \(c\) depends on how the noise is dependent. The sharp constant was known only for arbitrary dependence, where it is \(\sqrt{(M-1)/M}\), and for independent identically distributed noise.

The authors settle two intermediate classes. For independent but not identically distributed noise the constant is \(\sqrt{(M-1)/(2M)}\); for pairwise nonnegatively correlated noise it is \((M-1)/M\). Explicit finite constructions attain both, which answers the maximum version of an open question about the expected range for uncorrelated noise, and gives sharp bounds on the bias of the cross-validation estimator. All theorems are formally verified in Lean 4.

Across 448 language-model and classifier selection pipelines, designs with separate items per candidate reach a median of 0.75 of the independent-class ceiling. At a fixed item budget, scoring every candidate on shared items is much less optimistic.