Cost-aware Stopping for Bayesian Optimization

Technical Summary: Cost-aware Stopping for Bayesian Optimization

Problem Statement
In automated machine learning, scientific discovery, and other applications of Bayesian optimization (BO), practitioners face the challenge of deciding when to terminate the evaluation of expensive black-box functions. While existing stopping rules exist, they often fail to account for varying evaluation costs in a principled manner.

• Heuristic rules (e.g., fixed iteration counts or stopping when the best value remains unchanged) lack theoretical guarantees and may stop too early or incur unnecessary evaluations.
• Regret-based rules (e.g., UCB-LCB, Knowledge Gradient) are theoretically grounded for minimizing simple regret but are typically designed for uniform-cost settings. They do not explicitly account for evaluation costs, often leading to excessive cumulative costs and high cost-adjusted regret when costs are high.
• Cost-aware acquisition functions (e.g., Pandora's Box Gittins Index (PBGI) and log expected improvement per cost (LogEIPC)) have been developed to optimize the trade-off between solution quality and cost, but their integration with adaptive stopping rules has not been systematically studied.

The core objective is to design a stopping rule that optimizes the expected cost-adjusted simple regret, defined as the sum of the simple regret (the difference between the best found solution and the global optimum) and the cumulative cost of data collection.

Methodology
The authors propose a novel, principled cost-aware stopping rule derived from the Pandora's Box decision framework. The methodology establishes a theoretical connection between two state-of-the-art cost-aware acquisition functions:

1. Pandora's Box Gittins Index (PBGI): Derived from the dynamic programming solution to the Pandora's Box problem, adapted for correlated Bayesian optimization.
2. Log Expected Improvement per Cost (LogEIPC): A one-time-step approximation of the Bayesian-optimal policy.

The proposed stopping rule, termed the PBGI/LogEIPC stopping rule, is defined by the condition that optimization should cease when no unobserved point offers an expected improvement worth its evaluation cost. Mathematically, the rule stops at time $\tau$ when:
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
or equivalently:
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
where $y^*_{1:\tau}$ is the best observed value so far.

Key implementation details include:

• Posterior Update Timing: The rule utilizes the acquisition function values computed after the posterior update of the current iteration (forward-looking), which the authors argue better reflects the "fair value" intuition and yields empirical gains over backward-looking approaches.
• Handling Unknown Costs: When costs are unknown, they are modeled stochastically (e.g., as a Gaussian Process on the log-cost), and the expected cost $E[c(x)]$ is used in the stopping condition.
• Stabilization: To prevent spurious stops caused by model fluctuations or imperfect acquisition function optimization (especially in high dimensions), the authors enforce a stabilization period and apply a moving average smoothing to the stopping signal.

Key Contributions

1. A Novel Cost-Aware Stopping Rule: The paper presents an adaptive stopping rule derived from Pandora's Box theory that naturally extends to the expected improvement design principle. It provides a unified framework applicable to both classic and cost-aware BO.
2. Theoretical Guarantees: The authors prove that when paired with either PBGI or LogEIPC acquisition functions, the proposed stopping rule satisfies a theoretical upper bound on the expected cost-adjusted simple regret. Specifically, the policy is guaranteed to perform no worse than the "immediate stopping" baseline (stopping right after the first evaluation). This constitutes the first theoretical guarantee of this type for any adaptive stopping rule in Bayesian optimization.
3. Empirical Validation: The study provides a systematic evaluation across synthetic tasks and empirical benchmarks (LCBench for hyperparameter optimization and NATS-Bench for neural architecture search).

Results

• Synthetic Tasks: In 1D and 8D Bayesian regret settings with uniform, linear, and periodic cost functions, the PBGI/LogEIPC stopping rule paired with its corresponding acquisition function consistently matches or outperforms other pairs (including UCB-LCB, LogEIPC-med, and PRB). It is particularly robust in high-cost scenarios.
• Empirical Benchmarks:
  • On LCBench (35 datasets), the proposed rule paired with PBGI or LogEIPC ranks in the top 3 for approximately 75% of tasks.
  • On NATS-Bench, the rule performs competitively, approaching the hindsight-optimal performance.
  • The rule reliably stops before the iteration cap (200 iterations), whereas baseline regret-based rules (like SRGap-med and UCB-LCB) frequently fail to stop early, incurring excessive costs.
  • The authors note that underperformance on specific small datasets is likely due to benchmark-intrinsic validation/test mismatches rather than the stopping rule itself.

Significance and Claims
The paper claims to address a critical but underexplored practical consideration in Bayesian optimization: the cost-aware determination of when to stop.

• Theoretical Advancement: The work bridges the gap between cost-aware acquisition functions and adaptive stopping, providing the first formal guarantee that an adaptive policy will not incur a cost-adjusted regret worse than immediate stopping.
• Practical Utility: The proposed rule eliminates the need for heuristic tuning of stopping thresholds (e.g., fixed constants or median-based thresholds) by deriving the threshold directly from the evaluation cost.
• Robustness: The framework demonstrates robustness across varying cost structures and model misspecifications, offering a principled alternative to heuristic stopping criteria in expensive optimization tasks.

The authors conclude that their framework can be extended to settings involving noisy, multi-fidelity, or batched evaluations, and to alternative objective formulations, though these are noted as future directions rather than current contributions.