Deciding a model is good enough

The running maximum is a biased estimator#

The validation column above is $\max_{j \le i} \hat{R}_V(h_j)$ over $i$ candidates, and the quantity of interest is $R(h_{\hat{j}})$ for the selected $\hat{j}$. These differ by an optimism term. For $i$ candidates with roughly independent evaluation noise of scale $\sigma$, the expected maximum of the noise exceeds zero by approximately $\sigma\sqrt{2\ln i}$, so the reported score inflates with the logarithm of the number of things tried, at fixed model quality. The bound is loose under the strong correlation between similar configurations, but the direction is guaranteed and monotone: more search always inflates the reported number, and never deflates it.

This is the multiple-comparisons problem in a form that has no natural correction, because the hypotheses are chosen adaptively as the campaign proceeds. Dwork et al. (2015), The Reusable Holdout: Preserving Validity in Adaptive Data Analysis (Science), formalise adaptive data analysis and show that after $k$ adaptive queries a holdout of size $n$ supports accurate answers only for $k$ growing polynomially in $n$ under naive reuse — and give differential-privacy-based mechanisms (Thresholdout) that restore validity to exponentially many queries by adding calibrated noise and answering only when the holdout materially disagrees with the training estimate. The practical descendant is the rule above: a final holdout consulted exactly once.

The reassuring empirical counterweight is Recht et al. (2019), Do ImageNet Classifiers Generalize to ImageNet? (ICML), who built fresh test sets for CIFAR-10 and ImageNet after a decade of community-wide adaptive selection. Absolute accuracy dropped substantially on the new sets, but the ranking of models was almost perfectly preserved. The lesson is precise: adaptive selection corrupts the reported level far more than the ordering, so a leaderboard remains useful for choosing between models and useless for predicting deployed performance.

The ceiling: irreducible error and its estimation#

Excess risk decomposes into approximation, estimation and optimisation terms over an irreducible floor — the Bayes error $R^\star = \mathbb{E}_x[\min_k(1 - P(y=k \mid x))]$, determined by the overlap of the class-conditional distributions and by label noise. Under a uniform label-flip rate $\rho$ applied to an otherwise separable problem, the floor is $\rho$ directly. Note the arithmetic for this dataset: scikit-learn's flip_y re-assigns that fraction of labels uniformly over the $k$ classes rather than flipping them, so the effective flip rate is $\rho = \text{flip_y} \cdot (k-1)/k = 0.075$ for two classes — which is why flip_y=0.15 caps this dataset near 0.925 rather than near 0.85.

Estimating $R^\star$ on real data is genuinely hard, and the practical proxies each answer a slightly different question. Inter-annotator agreement (Cohen's $\kappa$, Krippendorff's $\alpha$) bounds the achievable accuracy of a model trained to imitate those annotators, and is the standard instrument in NLP and medical imaging. Re-annotation studies of benchmark test sets — Northcutt, Athalye and Mueller (2021), Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks (NeurIPS Datasets and Benchmarks) — found label errors averaging 3.4% across ten widely used benchmarks and, more consequentially, showed that correcting them can reverse the ranking of models whose measured gap is smaller than the error rate. Any reported improvement smaller than the test set's label-noise rate is uninterpretable, which is a sharper stopping criterion than most projects apply.

Direct Bayes-error estimation from data is possible under assumptions — nearest-neighbour error rates bracket $R^\star$ asymptotically via the classical Cover–Hart result $R^\star \le R_{\text{1NN}} \le 2R^\star(1-R^\star)$ — but the constants are weak enough at finite sample that the annotation-based estimates are the ones that change decisions.

Stopping as a decision problem#

The engineering question "when do we stop" is a sequential decision under uncertainty, and the framings that transfer are worth naming. Under optimal stopping, one continues while the expected value of the next experiment exceeds its cost; since gains decay roughly as a power law in effort while cost is linear, a finite optimal horizon always exists and is usually much shorter than teams assume. Bandit and Bayesian-optimisation formulations make this operational: expected improvement acquisition functions supply an explicit termination criterion when expected improvement falls below a threshold (Bayesian optimisation for hyperparameters), and successive halving allocates a fixed budget rather than an open-ended one — a structural defence against unbounded campaigns.

The larger point is that the metric is a proxy whose relationship to value is rarely linear. Utility is usually a step function of a thresholded decision, so accuracy gains that do not move examples across the operating threshold have literally zero value (choosing a threshold from costs). Converting a metric delta into a decision delta — how many cases change hands, at what expected cost — is the calculation that ends most tuning arguments, and it belongs in the project brief beside the target rather than being improvised at the end.

What to learn next#

• Test-set overfitting — the mechanism that inflates the number you are chasing.
• Defining the success metric — writing the finish line before the work starts.
• Monitoring and drift — why "good enough" has an expiry date.