Cost-aware Stopping for Bayesian Optimization
cs.LG
Submitted: 2025-07-16
Updated: 2026-11-03
Comments: Accepted by ICML 2026. This version corrected minor bugs in the computation of stopping iterations and updated the empirical results. The revised results continue to support the main conclusions
Code: https://github.com/QIANJANEXIE/COSTAWARESTOPPINGBAYESOPT
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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…
Terminology
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.
Sources
- Multi-Step Bayesian Optimization for One-Dimensional Feasibility Determination
- Constrained multi-fidelity Bayesian optimization with automatic stop condition
- Descending Price Optimally Coordinates Search
- Cost-aware Bayesian Optimization
- Stopping criteria for boosting automatic experimental design using real-time fMRI with Bayesian optimization
- Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis