Cost-aware Stopping for Bayesian Optimization
This addresses a practical issue in automated machine learning and scientific discovery by providing a theoretically grounded stopping rule to avoid excessive costs, though it is incremental as it builds on existing cost-aware acquisition functions.
The paper tackles the problem of deciding when to stop evaluating expensive black-box functions in Bayesian optimization, proposing a cost-aware stopping rule that adapts to varying evaluation costs and is free of heuristic tuning, with experiments showing it matches or outperforms other methods in cost-adjusted simple regret on tasks like hyperparameter optimization and neural architecture search.
In automated machine learning, scientific discovery, and other applications of Bayesian optimization, deciding when to stop evaluating expensive black-box functions is an important practical consideration. While several adaptive stopping rules have been proposed, in the cost-aware setting they lack guarantees ensuring they stop before incurring excessive function evaluation costs. We propose a cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs and is free of 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. We prove a theoretical guarantee bounding the expected cumulative evaluation cost incurred by our stopping rule when paired with these two acquisition functions. In experiments on synthetic and empirical tasks, including hyperparameter optimization and neural architecture size search, we show that combining our stopping rule with the PBGI acquisition function usually matches or outperforms other acquisition-function--stopping-rule pairs in terms of cost-adjusted simple regret, a metric capturing trade-offs between solution quality and cumulative evaluation cost.