Letting the Evidence, Not the Clock, Retire an Expert's Prior in Cost-Aware Bayesian Optimization

Practitioners tuning expensive models almost always know something before they start, such as "learning rates near 1e-3 tend to work." A family of methods for Bayesian optimization (BO), which picks the next configuration to try using a statistical model fit to past results, lets that knowledge steer early trials and then fades it out on a fixed schedule. That schedule counts trials, so the tenth trial erodes the prior by the same amount whether it took ten seconds or ten GPU-hours. A separate line of work decides when to stop tuning by weighing expected improvement against the cost of each evaluation, but it assumes no expert prior at all. This proposal joins the two pieces: how strongly the optimizer trusts the prior, and when it decides to stop.

The core idea is to stop scheduling the decay. The optimizer instead keeps an explicit probability that the expert's prior is right. It updates that probability with Bayes' rule from every observation, and it uses the same belief both to choose cost-weighted next evaluations and to decide when stopping is rational. Under this design the prior fades because the data contradict it, not because trials have passed. Cheap evaluations that test the prior become worth running for that reason, and the stopping rule sees beliefs that are neither inflated by a prior that should already be gone nor stripped of a prior the data have confirmed.

Core Claim

Existing prior-decay methods attach a fixed schedule to the prior. πBO multiplies the acquisition function by $\pi(x)^{\beta/n}$. DynMeanBO blends an expert mean into the Gaussian-process (GP) surrogate with a weight that shrinks exponentially in $n$. DynaBO stacks decaying priors and rejects a new one with a fixed-threshold check. All three index decay by iteration count $n$, and all three run for a fixed number of trials. Cost-aware Stopping for Bayesian Optimization supplies the other piece. It shows that stopping when the Pandora's Box Gittins Index (PBGI) turns non-positive is equivalent to stopping when log expected improvement per unit cost (LogEIPC) falls below zero, it carries a "no worse than stopping immediately" guarantee, and it is evaluated only with uninformative priors.

Our claim is that, once evaluation costs differ across configurations, a decay weight set by evidence gives lower cost-adjusted regret than any iteration-indexed or cost-indexed schedule. We define cost-adjusted regret, following Xie et al., as the final best-found gap plus the total evaluation cost spent. The gain should be largest when the prior points toward expensive regions, or when a cheap test can quickly confirm or refute it. We also claim that feeding a scheduled-decay surrogate into a cost-aware stopping rule miscalibrates stopping in a predictable direction. A prior mean that has not decayed enough inflates expected improvement in unexplored prior-favored regions, which delays stopping under bad priors. An evidence-weighted belief removes this bias.

Mechanism

We maintain two GP surrogates that share kernel hyperparameters. One, $M_1$, uses the expert's prior mean $m_{prior}(x)$. The other, $M_0$, uses a constant mean. The weight on the expert model after data $D_t$ is

$$w_t = \frac{p(D_t \mid M_1)\, w_0}{p(D_t \mid M_1)\, w_0 + p(D_t \mid M_0)(1-w_0)},$$

where $p(D_t \mid M_i)$ is the GP marginal likelihood and $w_0$ is the starting credence elicited from the expert. The predictive model is the two-component mixture, which is DynMeanBO's convex blend with $\gamma_n$ replaced by $w_t$. Both the acquisition step and the stopping step read from this one mixture. The acquisition step maximizes expected improvement per cost. The stopping step applies the PBGI/LogEIPC rule, computed on the mixture predictive. We estimate unknown costs with a separate log-cost GP, as in Xie et al.

GP marginal likelihoods can become overconfident early, so we floor $w_t$ at a small value and temper the likelihood ratio with a single exponent. We tune that exponent on synthetic functions only and then freeze it.

The analysis has two goals. The first is to show that the mixture inherits the no-worse-than-immediate property of PBGI stopping, since that argument depends only on the stopping index being computed under some coherent belief. The second is to bound how many evaluations are needed for $w_t$ to fall below a given level when the prior mean is misplaced by a given margin. That bound is the evidence-based counterpart of DynMeanBO's asymptotic recovery result.

Research Program

We first build the method on the official CostAwareStoppingBayesOpt codebase, because its stopping rules, cost models and benchmark loaders define the comparison. We add mixture surrogates and prior injection following DynaBO's protocol of Expert, Advanced, Local and Adversarial priors.

We then construct a controlled cost-prior alignment study on synthetic functions. These are Hartmann, Levy and Rosenbrock, as in DynMeanBO, together with the GP-sampled 1D and 8D functions of Xie et al. We attach synthetic cost surfaces that are positively correlated, negatively correlated or uncorrelated with the prior's favored region. This study tests the mechanism directly, since a schedule cannot know where the cost is.

Finally, we move to real cost heterogeneity. LCBench records true runtimes across 35 OpenML datasets and is used by both DynaBO and Xie et al. NATS-Bench records training cost per architecture. PD1 provides large-model tuning with strong practitioner priors.

Baselines

The naive reference is vanilla GP-BO with expected improvement per cost and PBGI stopping. It uses no prior, so it shows what the prior is worth at all. The fixed-budget variants of every method show what cost-aware stopping is worth.

The strongest existing competitor is DynMeanBO combined with PBGI stopping. DynMeanBO is the only decay method whose prior lives inside the surrogate, so a stopping rule can read it directly, and it already beat standard BO across all seven acquisition functions on PD1. We also run πBO with expected improvement per cost and PBGI computed on its plain GP. This is the decoupled design, in which the prior steers search but never touches stopping. DynaBO with its safeguard is included as the strongest robust-to-bad-priors competitor.

For fairness, every method receives the same prior, initial design, cost model, kernel family and random seeds. Each method's decay hyperparameter ($\beta$ for πBO, the decay rate for DynMeanBO, the temper exponent for ours) gets the same tuning budget on synthetic functions only, and is then frozen for LCBench, NATS-Bench and PD1.

The ablation that isolates our key ingredient is DynMeanBO whose decay is indexed by cumulative cost rather than $n$, with its rate fitted to the same budget. If our method does not beat this cost-indexed schedule, the contribution reduces to reindexing.

We found no reported result on Lacuna for cost-adjusted simple regret of any prior-decay method, or of PBGI, on LCBench, NATS-Bench or PD1. The file reports only qualitative rankings for PBGI on these benchmarks. The closest numbers are not comparable, for example πBO's 12.5× time-to-accuracy speedup and 94.14% validation accuracy on ImageNette-128. All baseline numbers will therefore be produced by our own runs. Beating DynMeanBO+PBGI means lower median cost-adjusted regret at matched seeds, with a paired Wilcoxon test across LCBench datasets, under Adversarial priors, without losing more than a small margin under Expert priors.

Why not just…?

Why not just reindex the existing decay by spent budget? This is the most serious threat, and it is the main ablation. Replacing $n$ with cumulative cost fixes the case where three huge trials barely erode the prior. It still decays a correct prior as fast as a wrong one, and it cannot speed up rejection when a cheap trial clearly refutes the prior. The negatively correlated cost-prior condition is designed to separate the two approaches. If the cost-indexed schedule matches our method there and on LCBench, we will report that, and the paper becomes a negative result favoring the simpler fix.

Why not just keep πBO for search and run PBGI on the plain GP? This decoupled design is principled and cheap. Its weakness is that the stopping rule ignores everything the prior says about unexplored regions, so it may stop too early under correct priors. Measuring stopping time against the "Hindsight" optimal stopping time from Xie et al. under each prior quality will show whether this happens.

Why not just use DynaBO's safeguard to reject bad priors? DynaBO's threshold test makes an accept-or-reject decision once, when the prior is injected. It does not register gradual evidence or the cost of gathering it. Our method can be read as a continuous, likelihood-based version of that safeguard. Under Local priors, which are partly right, a binary filter should either discard useful guidance or keep misleading guidance, and our comparison on that condition tests this.

Decisive Checks

The method succeeds if three things hold together. First, under Adversarial priors on LCBench and NATS-Bench, it recovers to vanilla-BO cost-adjusted regret with less total cost than DynMeanBO+PBGI. Second, its stopping time stays closer to Hindsight than both decoupled and scheduled designs. Third, it beats the cost-indexed schedule in the anti-correlated cost condition. A further diagnostic is the trajectory of $w_t$. If it collapses within a few cheap evaluations under bad priors and stays high under Expert priors, the mechanism is working as intended. If it drifts regardless of prior quality, the likelihood tempering is doing the work, and the claim fails.