Accounting for Variance in Machine Learning Benchmarks

In plain words

Comparing two machine-learning methods usually means training each one once, on one fixed train/test split, and checking which score is higher. But training is noisy. A different random seed, a different split of the data or a different hyperparameter search can move the score, sometimes by more than the gap between the two methods.

The paper measures how much each of these sources moves the score, and finds that the choice of data split matters most. It then offers a cheaper way to repeat the experiment: draw several random splits, randomise the seeds in each run, and count how often method A beats method B. A conclusion is drawn only when that rate is high enough and its confidence interval clears the thresholds.

The hyperparameter search itself is still run only once in the recommended setup, which adds no cost over the common practice of varying only the seed. The estimate is biased, but its standard error is lower than that of seed-only averaging §3.2.

TL;DR

Single-run or single-split benchmark scores hide variance from data sampling, weight initialisation, data order and hyperparameter optimisation. Data sampling is the largest source in the authors' five case studies §2.2fig. 1. The authors recommend randomising every source except hyperparameter optimisation, which they say costs no more than the usual seed-averaging §3.2§5. They decide between methods with the probability that A outperforms B across runs, requiring at least 0.75 with a bootstrap confidence interval §4.1. All error rates are author-reported simulations.

Problem

Benchmarks often report one score per method, from one training run on one fixed split, so conclusions can rest on arbitrary choices §1. The authors argue that the spread due to these choices is on the order of magnitude of the published gains between methods §2.2fig. 3. Repeating the whole pipeline, including hyperparameter search, for every run is too expensive for most research budgets. With one hyperparameter search shared across runs, the averaged estimate is biased, and its mean squared error does not shrink as runs are added §3.2.2eq. 7.

Method

The paper models a benchmark as a learning pipeline with three parts: training, hyperparameter optimisation (HOpt), and a final retrain on all data §2.1. Random sources are ξ_O (data sampling, augmentation, initialisation, dropout, data order) and ξ_H (HOpt) §2.1§2.2.

1. Model the pipeline. Training minimises a regularised surrogate loss with hyperparameters λ eq. 1. HOpt picks λ to minimise the validation risk over random splits eq. 2. The final predictor is the trained model on all data eq. 3. The benchmark quantity is the expected risk of the pipeline eq. 4, which is estimated from one dataset by an average over splits eq. 5 §2.1.

2. Ideal estimator. Each of the k runs gets its own seeds for every source, including a fresh HOpt. It costs O(k·T) trainings for T trials per HOpt, and its variance is σ²/k §3.2.1alg. 1eq. 6.

3. Biased estimator. HOpt runs once, then the k runs reuse its output and vary only some sources. It costs O(k+T) trainings. Its variance is given by eq. 7: the correlation ρ between runs leaves a term that does not shrink with k §3.2.2alg. 2.

4. Recommended estimator: all sources except HOpt. This is the biased estimator with every ξ_O source randomised in each run, including the out-of-bootstrap data split. The paper calls it FixHOptEst(k, All). It closes most of the gap to the ideal estimator at the cost of the biased estimator §3.2§5app. Randomizing more sources of variance. The pseudocode below follows alg. 2 with that change.

5. Decide. Over k paired runs of A and B, compute the fraction of splits in which A scores higher eq. 9. Build a percentile-bootstrap interval for it. A is significant if the lower bound exceeds 0.5. A is meaningful if the upper bound exceeds γ = 0.75 §4.1app. Statistical test with P(A>B).

6. Plan the sample size. Noether's formula gives the number of paired runs N from α, β and γ. For α = 0.05, β = 0.05 and γ = 0.75 the paper reports N = 29 app. Sample size. Evaluating the printed formula with those values gives about 28.9, which rounds up to 29; this is our arithmetic on the stated formula.

7. Report. Report all configurations inside the significance bounds, not only the top one §5.

# Biased estimator, all sources except HOpt  [alg. 2] [§3.2.2]
# Input:  dataset, number of runs k
# Output: mean and standard deviation of the k scores
def fix_hopt_est_all(dataset, runs):
    # Draw seeds and an out-of-bootstrap split for the HOpt step  [alg. 2]
    seeds = draw_seeds()
    train_val, test = out_of_bootstrap_split(dataset, seeds)
    # Tune hyperparameters once  [alg. 2] [§3.2.2]
    hparams = hopt(train_val, seeds)
    scores = []
    for run in range(runs):
        # Fresh seeds for every source except HOpt  [alg. 2] [§3.2]
        seeds = draw_seeds()
        # New split per run, so the data split varies  [alg. 2]
        # [app. Our bootstrap procedure]
        train_val, test = out_of_bootstrap_split(dataset, seeds)
        model = train(train_val, hparams, seeds)
        scores.append(evaluate(model, test))
    return mean(scores), std(scores)

# Decision rule for A versus B  [eq. 9] [app. Statistical testing]
# Input:  scores_a, scores_b, paired by split (same length N)
# Output: "A is better" or "no conclusion"
def decide(scores_a, scores_b, gamma=0.75):
    # Fraction of paired runs where A scores strictly higher  [eq. 9]
    p_ab = mean(a > b for a, b in zip(scores_a, scores_b))
    # Percentile bootstrap interval over resampled pairs
    # [app. Confidence interval]
    ci_min, ci_max = percentile_bootstrap(scores_a, scores_b)
    # Not significant: the lower bound does not clear 0.5
    # [app. Statistical test with P(A>B)]
    if ci_min <= 0.5:
        return "no conclusion"
    # Not meaningful: the upper bound does not clear gamma
    # [app. Statistical test with P(A>B)]
    if ci_max <= gamma:
        return "no conclusion"
    return "A is better"

Key equations:

\mathrm{Var}(\tilde\mu_k \mid \xi) = \frac{\mathrm{Var}(\hat R_e \mid \xi)}{k} + \frac{k-1}{k}\,\rho\,\mathrm{Var}(\hat R_e \mid \xi) eq. 7

p_{AB} = \frac{1}{k}\sum_{i=1}^{k} \mathbb{1}\{\hat R^A_{ei} > \hat R^B_{ei}\} eq. 9

Hyperparameters

Defaults and search spaces are those of the variance experiments. Search spaces that are log-uniform are marked "log".

Bootstrap split sizes per task are in app. Case studies: CIFAR10 draws 4,000 train, 1,000 validation and 1,000 test samples per class with replacement app. CIFAR10 with VGG11; SST-2 keeps a train/validation ratio of 0.013 and RTE keeps 0.1, without class balancing app. SST-2 and RTE with BERT; PascalVOC uses 2,184 training images and 729 each for validation and test [app. PascalVOC image segmentation]. For MLP-MHC the three sets are bootstrapped separately [app. MHC class I peptide binding].

Results

Author-reported. Setup: five case studies (CIFAR10 with VGG11; PascalVOC with FCN-16s and ResNet18; SST-2 and RTE with BERT; MHC class I binding with a shallow MLP) §2.2. Error rates come from simulations built on measured variances, with k = 50 splits and a true-effect sweep §4.2fig. 5.

Variance findings: bootstrapping data is the largest source of variance. Model initialisation is generally below 50% of the bootstrap variance, and the three HOpt methods add about as much variance on average as weight initialisation §2.2fig. 1. The binomial model matches the bootstrap spread on the classification tasks §2.2fig. 2. Randomising more sources lowers the standard error of the mean; weight initialisation alone is the weakest estimator in every case study §3.2app. Randomizing more sources of variance. The paper's own estimate of the case-study cost is about 8 GPU years §2.2.

Paper vs code

No official code. Searched: the paper and its arXiv listing have no code or project link; the LaTeX source has a commented-out data link, which is not part of the compiled paper and was not followed. GitHub searches for "accounting variance benchmarks", "variance" within the mila-iqia organisation, and the first author's repositories found no repository that names this paper. One unrelated first-author repository, bouthilx/benchmarks ("Group of benchmarks used for experiments"), shows no license and makes no reference to the paper; it is not used.

Pitfalls

• Decision formulas disagree between sections. The main text defines significance as P(A>B) − CI_min > 0.5 and meaningfulness as P(A>B) + CI_max > γ §4.1. The appendix tests CI_min > 0.5 and CI_max > γ directly [app. Statistical test with P(A>B)]. Use the appendix form; the main-text expression is not reconciled with it in the paper.
• Number of bootstrap resamples is not stated. The percentile interval takes K resamples of N pairs, but K is not given anywhere in the text [app. Confidence interval]. Choose K and say so.
• Ties count as "not better". Equation eq. 9 counts only strict inequalities. Tie handling is not stated. The paper notes that SST-2 performance is discretised by its small test set app. Normality of performance distributions, so ties are likely there.
• Pairing is recommended but optional. If runs are not paired, the paper says pairs are picked at random app. Compute P(A>B). Pairing needs the same seeds and splits for A and B, which the paper says is always worth doing when in doubt app. Pairing.
• The bootstrap check is absent. A validation of out-of-bootstrap splits against sub-bootstrap splits appears only as commented-out text in the source [app. Our bootstrap procedure]. The compiled paper does not validate the method.
• Hyperparameter-search details are thin. The Bayesian optimiser (RoBO) had no seeding support, so the authors seeded global RNGs and checkpointed states [app. Notes on reproducibility]. The Bayesian optimisation section is commented out of the appendix, so its settings are not stated.
• Reproducibility depends on the environment. Results changed with the GPU model, CUDA driver and PyTorch version. The paper pins PyTorch 1.2.0, CUDA 10.2 and cuDNN deterministic mode for convolutional layers [app. Notes on reproducibility]. Segmentation could not be made perfectly reproducible; its remaining noise is measured with seeds fixed across 200 runs [app. Notes on reproducibility]fig. 1.
• Log range with a zero bound. The MLP-MHC L2 range is written as log(0, 1) and the text says log-uniform on [0, 1] app. MHC class I peptide binding. A log-uniform distribution cannot include 0, so the sampling rule is not stated.
• Constants fitted from the same five tasks. The threshold δ = 1.9952σ is fitted by regression to published gains §4.2, and γ = 0.75 is chosen from these five tasks §4.2app. Analysis of robustness of comparison methods. Generality beyond them is not shown.
• Comparisons with other tools may be contaminated. The MHCflurry numbers are likely overestimates because its training data may include the test folds; the authors mark them with an asterisk app. MHC class I peptide binding.
• Multiple comparisons are not handled. The paper notes that a correction (e.g. Bonferroni) is one option for many-method comparisons but does not evaluate one §6.
• Compute totals differ. The paper gives about 8 GPU years for the environment §2.2 and 6.4 GPU years for the study's estimator runs §3.3. These measure different things, so do not add or compare them without checking.
• Sample size formula sign. The printed Noether form has (1/2 − γ) in the denominator, which is negative for γ = 0.75. The square removes the sign, so the value is unaffected app. Sample size.

Lineage

• Builds on: the formal sources-of-variation framework of Hothorn et al. (2005), which this paper extends with hyperparameter optimisation §2.1. Out-of-bootstrap resampling follows Hothorn et al. (2005) and Breiman (1996) [app. Our bootstrap procedure]. The decision rule is based on the Mann-Whitney test app. Sample size.
• Compared against: the single-point comparison and the average over k runs, which the paper calls the common practice §4.1§4.2.
• Superseded by: not stated in this wiki yet.