arXiv preprint ·
Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Reporting the best of $M$ noisy, unbiased scores overstates the winner's value by up to $c\sqrt{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 ($\sqrt{(M-1)/M}$) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is $\sqrt{(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Deep Learning for Random Objects in Metric Spaces: Beyond Manifold Assumptions
Exact Global Minimax Risk near Nonidentification
Dimension-free regimes for unadjusted Langevin in ridge-separable models: A subspace robust Wasserstein analysis
Score-Preserving Continual Lasso under Task Shift
Phase Transition from Random Features to Fully Trainable Networks
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.