Shared vs Per-Candidate Items: Bias Bounds for Model Selection

TL;DR: Scoring each model on its own data reduces winner's bias to the independent‑noise ceiling (~0.71√V), while shared data inflates bias up to the non‑negative‑correlation ceiling (~0.99√V).

Introduction

When a team runs hundreds of language‑model candidates through a single validation set, the top‑ranked model often looks better than it truly is. The phenomenon—winner’s bias—has a precise statistical footprint: the observed maximum overestimates the true mean by up to c·√V, where V is the total noise variance. Recent work shows that the constant c collapses from √((M‑1)/M) (arbitrary dependence) to √((M‑1)/(2M)) for independent, heteroscedastic noise, and to (M‑1)/M for pairwise non‑negatively correlated noise (Viakhirev et al., arXiv:2610.31948). In plain terms, the more the scores share noise, the larger the upward drift.

Two practical design choices sit at the heart of this bias: shared items (all models evaluated on the same test cases) and per‑candidate items (each model gets a bespoke subset). A 448‑pipeline audit revealed that per‑candidate designs achieve a median 0.75 of the independent‑noise ceiling, whereas shared designs sit near the non‑negative‑correlation ceiling. The stakes are clear: a naive shared‑item strategy can over‑promise by up to 40 % in expected performance.

This article dissects the mathematics behind the three noise regimes, translates the bounds into concrete engineering decisions, and stitches in two seemingly unrelated results—planar discrepancy lower bounds and capped‑participation Hessian‑similar optimization—to reveal a unified story about worst‑case variability when resources are limited.

Winner's Bias under Different Noise Correlations

The core quantity is the bias = E[maxi (μi+εi)] − maxi μi, where μi are true scores and ε_i are zero‑mean noises. Viakhirev et al. proved sharp constants c for three correlation families:

1. Arbitrary dependence: c = √((M‑1)/M). This is the worst case; a constructed covariance matrix attains it.
2. Independent, non‑identical variances: c = √((M‑1)/(2M)). The √2 factor reflects the variance reduction when noises are uncorrelated but allowed to differ per model.
3. Pairwise non‑negatively correlated: c = (M‑1)/M. Here every pair shares a non‑negative component, inflating the maximum.

The proofs rely on extremal constructions: for (2) a set of independent Gaussian noises with variances tuned to half the total variance; for (3) a rank‑one covariance matrix that injects a common noise term into every score. Both constructions are finite and explicit, and every theorem was mechanically verified in Lean 4, guaranteeing no hidden gaps.

From a practical lens, c translates directly into a bias budget. Suppose you evaluate M = 100 models and the aggregate noise variance V = 0.04 (standard deviation 0.2). Under independent noise, the bias cap is √((99)/(200))·0.2 ≈ 0.099. Under non‑negative correlation, the cap jumps to (99/100)·0.2 ≈ 0.198, essentially doubling the optimistic error. The difference is not academic; it reshapes confidence intervals for any leaderboard.

Practical Impact on Cross‑Validation and Item Allocation

Cross‑validation (CV) is the de‑facto estimator for μ_i. The bias bound applies verbatim because CV scores are unbiased averages of noisy folds. Viakhirev et al. therefore derived sharp CV bias limits for each noise class. In the independent regime the CV estimator’s over‑optimism never exceeds √((M‑1)/(2M))·√V, while in the non‑negative regime it can be as large as (M‑1)/M·√V.

Two design patterns emerge:

• ✔️Shared‑Item CV: All folds use the same validation items across models. This enforces pairwise non‑negative correlation because the same item error appears in every model’s score.
• ✔️Per‑Candidate Item CV: Each model’s folds draw from a disjoint pool of items. Independence is approximated, especially when the item pool is large relative to M.

A systematic experiment across 448 pipelines showed that per‑candidate item allocation caps the observed bias at roughly 0.71·√V (the independent‑noise constant for M ≈ 100), while shared allocation routinely hit 0.95·√V. The median improvement of 0.24·√V corresponds to a 12‑point lift on a 0–100 accuracy scale when √V ≈ 0.1.

Implementation tip: When you have a fixed budget of N validation items, allocate ⌊N/M⌋ unique items per model instead of pooling them. In Python, a simple splitter looks like:

import numpy as np
from sklearn.model_selection import KFold

def per_candidate_folds(X, y, n_models, n_splits=5, random_state=0):
    rng = np.random.default_rng(random_state)
    indices = np.arange(len(y))
    rng.shuffle(indices)
    # Partition indices into M disjoint blocks
    blocks = np.array_split(indices, n_models)
    folds = []
    for block in blocks:
        kf = KFold(n_splits=n_splits, shuffle=True, random_state=random_state)
        folds.append(list(kf.split(block)))
    return folds

The code guarantees that no two models ever see the same validation example, thereby enforcing the independent‑noise regime.

Connecting Discrepancy Theory to Worst‑Case Noise

At first glance, planar discrepancy (Hinrichs, arXiv:2610.33085) seems unrelated to model selection. Yet both fields grapple with distributional lower bounds: discrepancy quantifies the minimal deviation of any point set from uniformity, while winner’s bias quantifies the minimal upward deviation of a noisy maximum from its true counterpart.

Hinrichs proved that any n‑point set in the unit square exhibits an unnormalized discrepancy of at least c·√(1+log n) on a set of measure η > 0. This result implies that, no matter how cleverly you place points, a non‑trivial fraction of the domain will suffer a deviation proportional to √log n. Translating to noise, the “points” become validation items, and the “discrepancy” becomes the systematic error component shared across models.

The key insight is scale invariance: as the number of models M grows, the bias constant for independent noise scales like √((M‑1)/(2M)) ≈ 1/√2, while the discrepancy lower bound grows like √log M. In high‑dimensional hyperparameter sweeps (M ≈ 10⁴), the √log M term dominates, warning us that even independent item pools cannot fully escape a logarithmic inflation of bias. In practice, this manifests as a plateau in performance gains when you keep adding candidates without expanding the validation pool.

Therefore, the planar discrepancy theorem provides a theoretical ceiling on how much bias reduction you can achieve by simply increasing the number of unique items. Once the item budget reaches O(M / log M), further splitting yields diminishing returns.

Capped Participation in Distributed Optimization

The third paper (Wang, arXiv:2610.33835) studies Hessian‑similar optimization under a hard cap s on the number of clients contacted per round. The authors derive a lower bound of Ω((m/s)·√(δ/μ)·log(1/ε)) for zero‑respecting algorithms, where m is the total client count, δ captures Hessian variation, and μ is strong convexity.

If we reinterpret clients as validation items and rounds as evaluation passes, the same mathematics applies: limiting the number of items each model sees per pass (capped participation) incurs a provable slowdown in the convergence of the estimated performance. The “virtual master” algorithm (SVRS + Catalyst) attains an upper bound of Õ(m/s + (√(m/s)+m^{3/4}/s)·√(δ/μ)), showing that with a modest increase in s you can dramatically reduce the number of rounds needed to reach a target error ε.

In concrete terms, if you have 10 000 validation items (m) and you restrict each model to 100 items per evaluation (s = 100), the lower bound predicts at least a 100‑fold increase in evaluation rounds compared to unrestricted access. The virtual master technique suggests a hybrid approach: allocate a small shared core of s items to all models (capturing the common Hessian component) while supplementing with per‑model exclusive items to break correlation. This mirrors the per‑candidate item strategy but with a calibrated mixture of shared and private data, achieving a bias constant somewhere between √((M‑1)/(2M)) and (M‑1)/M.

Code sketch for a hybrid evaluator using PyTorch:

import torch

def hybrid_evaluate(models, shared_items, private_items, device='cpu'):
    # shared_items: Tensor[N_shared, ...]
    # private_items: list of Tensors, one per model
    shared_scores = []
    for model in models:
        model.eval()
        with torch.no_grad():
            shared_scores.append(model(shared_items.to(device)).mean())
    private_scores = []
    for model, priv in zip(models, private_items):
        private_scores.append(model(priv.to(device)).mean())
    # Combine with weighting that reflects theory (e.g., 0.3 shared, 0.7 private)
    combined = [0.3 * s + 0.7 * p for s, p in zip(shared_scores, private_scores)]
    return combined

The weighting can be tuned to match the desired correlation level, effectively moving along the bias continuum.

What This Actually Means

The mathematics is crystal clear: shared validation items are the hidden culprit behind inflated leaderboards. Teams that cling to a single test set for dozens of candidates are not just being optimistic—they are mathematically guaranteed to over‑estimate by up to 40 % relative to the independent‑noise optimum. The discrepancy lower bound tells us that no amount of clever shuffling can erase the √log M term, so scaling candidate pools without scaling the validation pool is futile.

Prediction: Within the next 12 months, at least 30 % of major ML platforms (e.g., Hugging Face AutoTrain, Google Vertex AI) will roll out per‑candidate validation splitting as a default feature, because the cost of false‑positive model releases (retraining, deployment, monitoring) will outweigh the modest engineering overhead of disjoint item pools.

Teams that ignore this will accrue maintenance debt: repeated model roll‑backs, wasted GPU hours on re‑training, and degraded user trust. The debt compounds because each new candidate inherits the bias of its predecessor, leading to a cascade of over‑optimistic performance reports.

Frequently Asked Questions

• ✔️Q: How many unique validation items do I need per model to achieve the independent‑noise bound?

A: Roughly N ≥ ⌈total_items / M⌉ unique samples per model; the bound holds as long as the items are drawn without replacement from a large pool.

• ✔️Q: Does per‑candidate splitting increase variance of the CV estimate?

A: Slightly, because each model sees fewer shared examples, but the reduction in upward bias more than compensates; the net mean‑squared error improves.

• ✔️Q: Can I mix shared and private items without breaking the theory?

A: Yes. The virtual‑master analysis shows a convex combination of shared (correlated) and private (independent) scores yields a bias constant between the two extremes; tune the mix to your budget.

• ✔️Q: Is the √log M discrepancy bound relevant for small M (<10)?

A: It becomes negligible; the independent‑noise constant dominates, so per‑candidate splitting offers the biggest gain.

• ✔️Q: How does this relate to federated learning or distributed training?

A: The capped‑participation lower bound is mathematically analogous; limiting the number of clients (or items) per round inflates the convergence time, mirroring the bias inflation in model selection.

Read next: continue exploring bias‑aware evaluation strategies and how they reshape model deployment pipelines.

See more articles on The Looplet

Further reading

Read Next

• ✔️How to Choose the Right Model for Automated Decision Gates
• ✔️Best Way to Train Generalizable Machine Learning Models for Retrieval and Forecasting
• ✔️Best Way to Build Adaptive Multimodal VLMs for Structured Chemical Extraction

Read next: continue with one of these related guides.