Adaptive Candidate Restriction for Scalable Random-Forest Bayesian Optimisation: Matched Accuracy at a Fraction of the Acquisition Cost

Abstract

: Random-forest sequential model-based optimisation (RF-SMBO) is a robust, CPU-friendly method for hyperparameter optimisation (HPO), but its conventional implementation scores every unevaluated configuration with the acquisition function at each iteration. On modern search grids containing tens of thousands of configurations— such as the transfer-HPO benchmarks widely used in automated machine learning (AutoML) research—this exhaustive scoring, not the objective evaluations, dominates the per-iteration cost. Practical solvers such as SMAC3 already restrict the candidate set heuristically, but the candidate count is fixed by convention and no existing analysis characterises when restriction is safe or how to size the candidate set automatically. We provide that analysis. We introduce randomised candidate restriction, in which the acquisition function is maximised over a small random subset of candidates rather than the full pool. The subset is sized online by adaptive-K, a schedule driven by the forest’s own predictive dispersion: it scores few candidates while the surrogate is unreliable and more as the surrogate becomes reliable, and it reverts to exact full scoring whenever the pool is small. The rule is a one-line change to any RF-SMBO implementation, and its three constants are frozen once on a single development space and never retuned. A coverage analysis formalises why restriction is safe. We prove that a random subset of K candidates misses every near-optimal configuration with probability at most ( 1 − p ) K , where p is the fraction of near-optimal configurations in the pool. This bound decays exponentially in K , so a few thousand random candidates contain a near-optimal configuration with high probability and the candidate budget is not an accuracy-sensitive hyperparameter. We verify this prediction by direct measurement: the restricted subset retains a candidate within 5% of the full-pool acquisition maximum on 85.5% of steps. An optimiser’s-curse measurement rules out selection-bias reduction as the operative mechanism. Empirically, across 14 HPO-B search spaces, 157 held-out tasks and 20 seeds, adaptive-K matches full-candidate RF-SMBO within a pre-specified margin of 0.01 normalised regret (median per-task difference zero), while scoring 20–27 × fewer candidates per step and accelerating the acquisition step by up to 4.7 × on the largest grids. It improves on random search and tree-structured Parzen estimator (TPE) baselines by more than 25% ( p < 10 − 5 ). Two live-training studies, tuning XGBoost over a 22,680-configuration grid and a random forest over a 6048-configuration grid on OpenML classification datasets, confirm these results when every evaluation is a real model fit. Restriction also generalises beyond the random-forest surrogate: fixed-K restriction matches full scoring for TPE and Gaussian-process upper confidence bound (GP-UCB) surrogates. All code, frozen configurations, and analysis scripts needed to reproduce our results are publicly available at https://doi.org/10.5281/zenodo.22886237.