Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
Abstract
Reporting the best of M noisy, unbiased scores overstates the winner's value by up to c√V, where V is the total noise variance and the sharp constant c depends on how the noise is dependent. It was known only at the two extremes, arbitrary dependence (√((M−1)/M)) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is √((M−1)/(2M)), and for pairwise nonnegatively correlated noise it is (M−1)/M; for uncorrelated noise this answers the maximum version of an open question about the expected range. Explicit finite constructions attain both. As a corollary, the bias of the cross-validation estimator is bounded sharply within each class. All theorems are formally verified in Lean 4. Across 448 language-model and classifier selection pipelines, designs with per-candidate items realize a median 0.75 of the independent-class ceiling. At a fixed item budget, scoring all candidates on shared items is markedly less optimistic than giving each candidate its own items.
Related
- Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex
- Sharp High-Entropy Bounds for Sums of Independent Discrete Random Variables
- Beyond Multiplicity Correction: Sharp Retrieval Thresholds for Attention with Correlated Distractors
- Optimization Risk Bounds for Kolmogorov-Arnold Networks Trained by DP-SGD with Correlated Noise
- Sharp Probabilistic Normwise Backward Error Bounds for LU Factorization
BibTeX
@misc{viakhirev2026sharp,
title = {{Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise}},
author = {Ivan Viakhirev and Kirill Borodin and Grach Mkrtchian},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31948},
eprint = {2610.31948},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31948},
}
RIS
TY - UNPB
TI - Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
AU - Ivan Viakhirev
AU - Kirill Borodin
AU - Grach Mkrtchian
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31948
UR - https://arxiv.org/abs/2610.31948
AB - Reporting the best of M noisy, unbiased scores overstates the winner's value by up to c√V, where V is the total noise variance and the sharp constant c depends on how the noise is dependent. It was known only at the two extremes, arbitrary dependence (√((M−1)/M)) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is √((M−1)/(2M)), and for pairwise nonnegatively correlated noise it is (M−1)/M; for uncorrelated noise this answers the maximum version of an open question about the expected range. Explicit finite constructions attain both. As a corollary, the bias of the cross-validation estimator is bounded sharply within each class. All theorems are formally verified in Lean 4. Across 448 language-model and classifier selection pipelines, designs with per-candidate items realize a median 0.75 of the independent-class ceiling. At a fixed item budget, scoring all candidates on shared items is markedly less optimistic than giving each candidate its own items.
ER -