skip to content

Why is the best CV score from a 200-configuration random search a biased estimate of that model's skill?

level: middleimportance: should knowfreq 55%

answer

  1. a maximum is not an average
  2. you selected on the noise too
  3. more candidates, more optimism
  4. inflation scales with sqrt(2 ln m)

basics

~20 s

Taking the maximum over 200 noisy cross-validation scores selects for lucky noise as well as for real skill, so the winning number sits above that configuration's true performance. Re-estimate the winner on data that played no part in choosing it.

solid answer

~50 s

Every candidate's CV score is its true skill plus estimation noise from the particular fold split. Keeping only the maximum over 200 such scores selects jointly on skill and on favourable noise, so two things go wrong: the reported number is optimistically biased as an estimate of the winner's true skill, and the config that won may not be the genuinely best one — it may just have drawn the friendliest folds. The optimism grows with the number of candidates and with the fold noise, so searching wider makes it worse. Practically, I quote the winner's score only from data that took no part in the selection, treat the top handful of configurations as tied rather than ranked, and state how many configurations were searched next to the number, because the search size is what tells a reader how inflated to expect it to be.

code

python · 16 lines
python
import random, statistics

random.seed(0)
TRUE_SKILL = 0.800   # every candidate is EQUALLY good
NOISE_SD = 0.030     # fold-split noise in one CV estimate
CANDIDATES = 200

def best_of_a_search():
    scores = [random.gauss(TRUE_SKILL, NOISE_SD) for _ in range(CANDIDATES)]
    return max(scores)          # what you would put in the report

winners = [best_of_a_search() for _ in range(2000)]
reported = statistics.mean(winners)

print(round(reported, 3))                # ~0.883  the number you quote
print(round(reported - TRUE_SKILL, 3))   # ~0.083  pure selection optimism

go deeper

for a junior

Recall the one-liner: the highest score out of many tried configurations is flattered by luck, so it is not what the model will score on new data.

for a middle

Be ready to decompose a CV score into true skill plus fold noise and explain why maximising over that sum picks up positive noise, and why the effect grows with the number of candidates.

for a senior

Show how you operate around it: quote the winner's score only from data uninvolved in the choice, cut fold noise with repeated splits, and state the search size next to every number you publish.

for a principal

Own the tradeoff between search breadth and estimate credibility — a wider sweep buys a prettier headline number and a shakier ranking, and you decide what the organisation is allowed to quote.

## The setup You define a search space — tree depth, learning rate, number of trees, feature subsample fraction — and score, say, 200 sampled configurations by k-fold cross-validation. You sort the table, take the top row, and write its score in the report. That number is the one almost everybody quotes, and it is almost always too high. ## Why the maximum is biased upward Model each candidate's measured CV score as ``` observed_i = true_skill_i + noise_i ``` where `noise_i` comes from which rows happened to land in which fold, from the randomness inside the learner, and from the finite size of each held-out fold. Averaged over many hypothetical fold splits, `noise_i` has mean zero, so `observed_i` is a roughly unbiased estimate **of that one candidate, chosen in advance**. The bias appears the moment you take a maximum. `max_i(observed_i)` is not an unbiased estimate of `true_skill` of the argmax, because the arg-maximising index was chosen using the noise. A candidate wins by being genuinely good, by being lucky, or — most often — by both. Conditional on having won, its noise term is positive in expectation. That is the winner's curse: selection and estimation done on the same numbers. A useful worst case: suppose all 200 candidates have **identical** true skill, so there is nothing to discover, and the noise is roughly bell-shaped with standard deviation `sigma`. The expected maximum of `m` such draws grows on the order of `sigma * sqrt(2 * ln m)`; for `m = 200` it works out at roughly 2.7 `sigma`, and it keeps creeping up with `m` (slowly, because of the logarithm). With a realistic `sigma` of 0.03, that is roughly eight accuracy points of pure illusion on a table where every candidate is the same model in disguise. ## Two distinct damages 1. **The reported number is inflated.** The score you publish is not what the model will do on new data. 2. **The ranking is unreliable.** The winner is often not the best candidate — with 200 near-equivalent configs, the top of the table is mostly a noise ranking. Re-run the search with a different fold seed and a different config wins. The second is the one people miss. It is why a 0.002 gap between rank 1 and rank 4 should never be read as "we found the best settings". ## What makes it worse, what makes it better - **More candidates makes it worse.** Optimism rises with the number of configurations scored, so a bigger sweep buys you a better-looking number faster than it buys you a better model. - **Noisier estimates make it worse.** Small datasets, small held-out folds, high-variance learners and a single fold split all raise `sigma`, and the inflation is proportional to `sigma`. - **Quieter estimates make it better.** Repeating cross-validation over several different fold splits and averaging shrinks `sigma`, which shrinks both the inflation and the chance the ranking is noise. - **A coarser, better-reasoned search space makes it better.** Fifteen candidates chosen with domain sense carry far less selection bias than 2,000 sampled blindly, and often land in the same place. ## What to actually report The honest score for the selected configuration comes from data that had no role in selecting it. Anything measured on the same numbers you optimised over is a selection statistic, not a performance estimate. Beyond that, report so a reader can judge the optimism themselves: - state the **number of configurations scored** — without it, a single score is uninterpretable; - report the **spread**, not just the mean, of the chosen model's fold scores; - show the **top few candidates together** rather than the single winner, so the reader sees they are within noise; - resist re-quoting the maximum after any further poking at the same data. ## The interview framing The crisp sentence is: *cross-validation gives an unbiased estimate of a model you named in advance, and a biased one of a model you picked by looking.* Everything else — how large the bias is, how it scales, what to do about it — follows from that single distinction between choosing and measuring.

  • How much optimism should you expect, and what does it depend on?
    It scales with the fold noise and grows with the number of candidates roughly like `sqrt(2 * ln m)` — about 2.7 noise standard deviations at 200 candidates, and only slowly larger beyond that. So halving the estimation noise (repeated cross-validation, larger held-out folds, more data) buys more than trimming the candidate list, though a smaller, better-reasoned search space helps on both fronts.
  • A public-leaderboard leader drops twelve places when the private split is revealed. Same phenomenon?
    Yes, with the teams playing the role of candidates. Hundreds of submissions are ranked on one shared scoring split, so the top of the public board is partly whoever fit that split's noise best. On a fresh private split the noise redraws and the ranking reshuffles, most violently among entries that were separated by less than the scoring noise.
  • If the top five configurations are within noise of one another, how do you pick?
    Treat them as tied on accuracy and break the tie on things measured without noise: fewer parameters or shallower trees, faster inference, fewer features to maintain, more stable behaviour across fold splits. Then say in the report that the choice was a tie broken on cost, not that this configuration was the best performer.

Two hundred equally fast sprinters each run one race on a gusty day. The winner is probably the one who caught the best tailwind, so the winning time flatters them — and re-running the meet would likely crown someone else.

saying these in an interview costs you the question

  • Says the best CV score is an unbiased estimate of the winner
  • Believes cross-validation cannot overfit because folds are held out
  • Treats a 0.002 gap between the top two configs as a real improvement
  • Thinks searching more configurations always yields a better model
  • Assumes only training-set scores can be optimistic

context

resolving links…