Cost-aware Stopping for Bayesian Optimization

In automated machine learning, scientific discovery, and other applications of Bayesian optimization, deciding when to stop evaluating expensive black-box functions in a cost-aware manner is an important but underexplored practical consideration. A natural performance metric for this purpose is the cost-adjusted simple regret, which explicitly captures the trade-off between solution quality and cumulative evaluation cost. Existing stopping rules for Bayesian optimization are either heuristic, or are theoretically grounded but designed to optimize simple regret without accounting for evaluation costs; as a result, they provide no guarantees against unnecessary evaluations when costs are high. We propose a principled cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs without heuristic tuning. Our rule is grounded in a theoretical connection to state-of-the-art cost-aware acquisition functions, namely the Pandora's Box Gittins Index (PBGI) and log expected improvement per cost (LogEIPC). When paired with either acquisition function, we prove that the resulting policy satisfies a theoretical guarantee bounding the expected cost-adjusted simple regret. Across synthetic tasks and empirical benchmarks including hyperparameter optimization and neural architecture size search, pairing our stopping rule with PBGI or LogEIPC usually matches or outperforms other acquisition-function--stopping-rule pairs in terms of cost-adjusted simple regret.

Bayesian optimization is widely used for black-box global optimization when evaluations are expensive, such as in hyperparameter tuning, neural architecture search, robotics, and scientific discovery. At each step, Bayesian optimization uses a probabilistic model together with an acquisition function—a scoring rule for deciding which candidate to evaluate next. In many practical applications, evaluation costs vary across candidates, and this information can be leveraged to make better sequential decisions: not only about where to evaluate next, but also about when to stop the optimization process. Existing stopping rules for Bayesian optimization are often heuristic, or are designed primarily to optimize solution quality without explicitly accounting for evaluation costs. As a result, they may continue evaluating while incurring excessive cumulative evaluation cost. In this work, we derive a cost-aware stopping rule from a theoretical connection between two state-of-the-art cost-aware acquisition functions: the Pandora’s Box Gittins Index (PBGI) and log expected improvement per cost (LogEIPC). PBGI is motivated by the Pandora’s Box problem, a related decision problem from economics that naturally comes with a stopping rule. We show that this stopping rule is equivalent to “stop when no point’s expected improvement is worth its evaluation cost” for acquisition functions derived from the expected improvement design principle, recovering and generalizing an intuitive stopping rule previously proposed in the classical unit-cost setting. We further prove that the matched pairs PBGI + our stopping rule and LogEIPC + our stopping rule satisfy a safeguard guarantee: they are never worse in expectation than stopping immediately after the initial evaluation. Through a systematic comparison across acquisition-function–stopping-rule pairs on synthetic tasks and automated machine learning benchmarks, we find that these matched pairs consistently achieve strong cost-performance trade-offs and usually outperform alternative acquisition-function–stopping-rule combinations.