Audited Pruning: Early Stopping with a Guarantee on What You Threw Away

Hyperparameter search wastes most of its compute on bad settings, so modern tools stop runs early. They train hundreds of candidate configurations briefly, look at their partial learning curves, and kill the ones that look worse. Every kill is an implicit statistical claim: "this configuration would not have won if trained to the end." These tools make thousands of such claims per search, on noisy early data, and never check any of them. This is a multiple comparisons problem: run enough tests and some will be wrong by chance alone. Here it is made worse because early scores are not even unbiased samples of final scores. A heavily regularized model that learns slowly can look hopeless at epoch 5 and win at epoch 200.

We propose a pruning rule that comes with a guarantee a practitioner can read directly. Among the configurations the search discarded, at most a fraction $\alpha$ would have beaten the configuration it finally returned. Inside each search, a small random "audit set" of configurations is trained to completion. Because the audit configurations are drawn the same way as everyone else, their (partial curve, final score) pairs calibrate any learning-curve predictor without trusting its own uncertainty estimates. Each pruning decision becomes a test. The family of all such tests, across configurations and across checkpoints, is controlled with online false-discovery-rate machinery that stays valid under arbitrary dependence. Aggressiveness then becomes a quantity the data sets, not a fixed knob. When early curves predict final performance well, the rule prunes hard. When they do not, it refuses to prune.

Core Claim

The errors that matter in aggressive early stopping come mostly from extrapolating early scores to final ones, not from measurement noise. Existing statistical racing methods correct for the wrong error. Hoeffding races (Hoeffding Races) bound sampling noise in a model's current error. CVST (Fast cross-validation via sequential testing) and I/F-Race (Fine-tuning of support vector machine parameters using racing algorithms) repeatedly apply Friedman or Cochran's Q tests to current performance. CVST adds a heuristic safety zone. None of the three adjusts for repetition across rounds, and none tests a hypothesis about final performance.

Bandit methods such as Successive Halving (Non-stochastic Best Arm Identification and Hyperparameter Optimization) and Hyperband (Hyperband) make no error claims at all. DyHPO (Supervising the Multi-Fidelity Race of Hyperparameter Configurations) and latent-Kronecker Gaussian-process Successive Halving (Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes) do model final performance. They trust a model-based probability whose calibration on a new task is unknown.

Our claim is that a within-search audit set plus e-value online false discovery rate control gives three things at once. First, a finite-sample bound on the false-prune rate that holds per task. Second, automatic retreat on tasks with late bloomers. Third, speedups close to Hyperband on tasks with predictable learning curves.

Research Program

Each sampled configuration $i$ carries a null hypothesis $H_i$: "$y_i \le \tau$." Here $y_i$ is the configuration's final-budget validation loss and $\tau$ is the loss of the best fully trained configuration so far, the incumbent. The incumbent only improves, so rejecting $H_i$ against the current $\tau$ remains correct against the final winner.

At checkpoint $b$, a learning-curve predictor produces $\hat y_i(b)$ from the partial curve. The predictor can be anything, from a power-law fit to the latent-Kronecker Gaussian process of Scaling Gaussian Processes for Learning Curve Prediction via Latent Kronecker Structure. The audit set holds $m$ configurations sampled from the same proposal distribution and trained to completion, with predictions $\hat y_j(b)$ and true final losses $y_j$. From these we form a conformal p-value:

$$p_i(b) = \frac{1 + \#\{j \le m : \hat y_j(b) - y_j \ \ge\ \hat y_i(b) - \tau\}}{m+1}.$$

This p-value is valid whenever the audit and tested configurations are exchangeable. That holds by construction under random sampling, as in Hyperband or asynchronous Successive Halving. It holds no matter how wrong the predictor is.

These p-values have two awkward properties. They share one calibration set, and the same configuration is tested again at successive checkpoints. Their dependence structure is therefore intricate. We convert each p-value to an e-value through a fixed calibrator; an e-value is a nonnegative statistic with expectation at most one under the null. We then feed the stream of (configuration, checkpoint) tests into e-LOND (Online multiple testing with e-values). E-LOND sets the threshold at test $t$ to $\alpha\gamma_t(|R_{t-1}|+1)$, where $\gamma_t$ is a spending sequence summing to one and $|R_{t-1}|$ is the number of earlier prunes. Its validity under arbitrary dependence is exactly why we use e-values rather than p-value methods, which would pay reshaping penalties.

Asynchronous parallel searches start and stop trials at arbitrary times. For these we adapt the conflict-set bookkeeping of Asynchronous Online Testing of Multiple Hypotheses as a comparison point.

The program has three parts. The theory part proves false-discovery control over prunes when one hypothesis is tested repeatedly in the stream. It also analyses the audit-size trade-off: a larger $m$ gives finer p-values and more power, but each audit run costs a full training budget. We also extend the scheme to adaptive samplers via weighted conformal calibration, flagged as harder. The systems part builds the rule as a drop-in pruner for Hyperband-style schedulers, with the audit runs sharing the same workers. The empirical part tests whether the guarantee holds, what it costs, and whether it beats cheaper fixes.

A secondary output addresses selection bias in the returned score. Amplified Early Stopping Bias showed that validation-based stopping can yield ROC-AUC up to 95% on random labels. We report the winner's score on data untouched by any pruning decision. We treat this as hygiene, not the contribution.

Baselines

The naive reference is random search with every configuration trained to completion. It has zero false prunes and is the most expensive. Every method's cost and regret are expressed relative to it.

The strongest bandit competitor is Hyperband (Hyperband), with its asynchronous variant for parallel runs. Hyperband reported "over an order-of-magnitude speedup" over Bayesian optimization tools and was "over 10x faster than competitors" on CIFAR-10. We run it on the same tabular-lookup benchmarks, with the same total budget in epochs, the same random proposal distribution, and $\eta=3$. Our method beats it if it reaches equal or lower final regret at matched budget. It also beats Hyperband in a second sense if it keeps the false-prune rate below $\alpha$ on tasks where Hyperband's realized rate exceeds it.

The strongest model-based competitor is DyHPO (Supervising the Multi-Fidelity Race of Hyperparameter Configurations). DyHPO reported the lowest regret and best average rank across LCBench, TaskSet and NAS-Bench-201, and "outperformed all baselines significantly after using only 50% of the total search budget" on LCBench. We found no reported numeric regret value on Lacuna for DyHPO on LCBench, so we rerun it ourselves under the same budget. We do not expect to beat DyHPO on regret everywhere. The bar is matching its regret within noise while adding a false-prune guarantee it lacks.

The most direct competitor is Successive Halving with latent-Kronecker learning-curve prediction (Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes). It prunes when the model's probability of beating the incumbent is negligible. We give it the identical predictor and the identical audit runs as extra training data, so the only difference is calibration and multiplicity control.

CVST (Fast cross-validation via sequential testing) is the classical statistical racer. CVST reported speedups "up to 120 times" with mean-squared-error ratios near 1.0. We compare against it on its own kernel benchmark suite.

Two ablations isolate the key ingredients. The first keeps the audit set but replaces e-LOND with a Bonferroni split of $\alpha$ across all tests. The second keeps e-LOND but calibrates on other tasks' curves instead of an in-run audit.

Why not just…?

Why not just Bonferroni-correct a Hoeffding or CVST race? That controls the chance that noise in current scores misleads the race. It does not control the chance that current scores mislead about final scores. Yu and Deng's early Hessian diagnostic shows how badly early signals can mislead about late behaviour. In Multiple-Comparison Testing for Cross-Validation Path Optimization Benchmarks, that diagnostic had a 100% false-positive rate because the failure only appeared near convergence. A corrected race on current scores would be confidently wrong in exactly that regime. Our experiments measure its realized false-prune rate on LCBench tasks with crossing learning curves. If a corrected race stays below $\alpha$ there, the audit is unnecessary and we would say so.

Why not just threshold the Gaussian process's own probability of beating the incumbent? This is the real threat. If modern learning-curve models are well calibrated across tasks, the audit is overhead. The comparison against latent-Kronecker Successive Halving with the identical predictor settles it. We report the realized false-prune rate against the nominal level, task by task. A guarantee matters only if that rate exceeds $\alpha$ on a meaningful fraction of tasks. If it does not, the remaining contribution is the per-task certificate, which is a weaker selling point.

Why not just make Hyperband less aggressive? Hyperband already hedges across brackets. A smaller $\eta$ reduces false prunes on every task and costs speed on every task. Our rule should be aggressive where curves are predictable and conservative where they are not. The test is a per-task plot of speedup against false-prune rate. If a single well-chosen $\eta$ matches our curve across all LCBench tasks, the adaptivity claim fails.

Why not calibrate once offline on benchmark curves? It is cheaper, since it needs no audit runs, but it assumes the new task resembles the meta-training tasks. The transfer ablation measures how often that assumption breaks under leave-one-task-out evaluation.

Proposed Experiments

The core testbeds are LCBench (35 tabular tasks), TaskSet (12 language tasks) and NAS-Bench-201 (NAS-Bench-201). Because these store full learning curves, every pruned configuration's true final score is known. False prunes can therefore be counted exactly rather than estimated. For NAS-Bench-201 the reference best test accuracies are 94.37% on CIFAR-10, 73.51% on CIFAR-100 and 47.31% on ImageNet-16-120. We use the CVST kernel suite for the classical comparison.

The metrics are four. The first is realized false-prune rate: the fraction of prunes whose configuration would have beaten the returned winner. The second is final regret against the benchmark optimum. The third is total epochs consumed. The fourth is the gap between the winner's search-time score and its untouched held-out score.

The first decisive check is validity. Over 50 seeds per task, the realized false-prune rate must stay at or below $\alpha \in \{0.05, 0.1, 0.2\}$ on every task. That includes tasks we deliberately select for crossing learning curves. Baselines that exceed the level must be reported as such.

The second check is cost. At $m \in \{10, 20, 50\}$ audit runs, total budget should stay within a small factor of Hyperband's on tasks with predictable curves. Regret should be no worse than DyHPO's within seed variance.

The third check is retreat. On tasks where early and final ranks correlate poorly, the rule should prune little and approach full random search. Hyperband's false-prune rate on those same tasks should be visibly higher. If the audit cost swamps the savings at realistic $m$, or if the uncalibrated Gaussian-process threshold already holds the level, the proposal's practical case collapses. The design is meant to reveal that cleanly.