cs.LGJul 16, 2025

Cost-aware Stopping for Bayesian Optimization

Authors: Qian Xie, Linda Cai, Alexander Terenin, Peter I. Frazier, Ziv Scully

Organizations: Cornell University, Ithaca, New York, USA · University of California, Berkeley, Berkeley, California, USA

Abstract

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.

Figures & tables

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index

    Jun 28, 2024Qian Xie, Raul Astudillo, Peter I. Frazier +2Bayesian Optimization

  2. Cost-Aware Stopping for Freeze-Thaw Bayesian Optimization: When Does One-Step Lookahead Suffice?

    Oct 30, 2026Long Vu, Jongseong Brad Choi, Binoy Ravindran +1Bayesian OptimizationOptimal Stopping