# Cost-aware Stopping for Bayesian Optimization

arXiv: https://arxiv.org/abs/2507.12453 · HTML: https://mlsanity.com/paper/2507.12453/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 33 references that are in the map.
- First posted on arXiv 16 Jul 2025.

## Builds on (most cited first, 18 of 18)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [NATS-Bench: Benchmarking NAS Algorithms for Architecture Topology and Size](https://mlsanity.com/paper/2009.00437/) (2020)
- [Auto-PyTorch Tabular: Multi-Fidelity MetaLearning for Efficient and Robust AutoDL](https://mlsanity.com/paper/2006.13799/) (2020)
- [Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables](https://mlsanity.com/paper/1910.01688/) (2019)
- [Cost-aware Bayesian Optimization](https://mlsanity.com/paper/2003.10870/) (2020)
- [Automatic Termination for Hyperparameter Optimization](https://mlsanity.com/paper/2104.08166/) (2021)
- [Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs](https://mlsanity.com/paper/2111.06537/) (2021)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [Stopping Bayesian Optimization with Probabilistic Regret Bounds](https://mlsanity.com/paper/2402.16811/) (2024)
- [Stopping criteria for boosting automatic experimental design using real-time fMRI with Bayesian optimization](https://mlsanity.com/paper/1511.07827/) (2015)
- [Descending Price Optimally Coordinates Search](https://mlsanity.com/paper/1603.07682/) (2016)
- [Weitzman's Rule for Pandora's Box with Correlations](https://mlsanity.com/paper/2301.13534/) (2023)
- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)
- [Bayesian Optimization with Adaptive Kernels for Robot Control](https://mlsanity.com/paper/2402.07021/) (2024)
- [A Corrected Expected Improvement Acquisition Function Under Noisy Observations](https://mlsanity.com/paper/2310.05166/) (2023)
- [Constrained multi-fidelity Bayesian optimization with automatic stop condition](https://mlsanity.com/paper/2503.01126/) (2025)
- [Multi-Step Bayesian Optimization for One-Dimensional Feasibility Determination](https://mlsanity.com/paper/1607.03195/) (2016)

## Built on by (most cited first, 4 of 4)

- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimization](https://mlsanity.com/paper/2605.22561/) (2026)
- [Converge Then Diversify: Decoupling Convergence and Diversity in Multi-Objective Bayesian Optimisation](https://mlsanity.com/paper/2609.13396/) (2026)
- [Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices](https://mlsanity.com/paper/2609.25645/) (2026)

## Abstract (arXiv)

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.