Cost-aware Bayesian Optimization

1. Introduction

• BO minimizes analytically unavailable, potentially noisy black-box objectives by modeling evaluations and selecting new points with an acquisition function.Gaussian processes commonly model the objective, while acquisition functions balance exploration and exploitation.Source: §1 · p. 1
• Unequal evaluation costs can make iteration-based convergence misleading, because HPO runtimes often vary by an order of magnitude or more and most configurations are cheap.This creates an opportunity for cost-efficient rather than purely sample-efficient optimization.Source: §1 · p. 1
• CArBO combines a cost-effective initial design with a budget-aware acquisition function to minimize objectives under time, energy, or monetary budgets.The method supports both sequential and batch optimization.Source: §1 · p. 1
• Across 20 real-world HPO problems, CArBO significantly outperforms competing methods within the same cost budget.The paper also reports that low-variance cost models can further improve cost-aware BO.Source: §1 · p. 1

2. Background and Related Work

• Multi-fidelity, multi-task, and cost-preference methods evaluate cheap proxies or points before expensive evaluations, but they require additional cost or fidelity information and do not generally apply to black-box BO.The paper identifies general black-box cost-aware BO as insufficiently investigated.Source: §2 · pp. 1–2
• Runtime distributions across five HPO problems vary often by an order of magnitude or more, undermining the assumption that BO evaluations have equal cost.The experiments use KNN, MLP, SVM, DT, and RF problems trained on w2a.Source: Figure 1 · p. 2
• Figure 2 shows EIpu evaluating many cheap KNN points while EI evaluates fewer expensive points, with EIpu performing poorly when the optimum is among the most expensive points.This illustrates why a bias toward cheap points is risky when the optimum’s cost is unknown.Source: Figure 2 · p. 2, §2 · p. 2
• EIpu normalizes acquisition by a learned cost model, but it can underperform when the optimum is expensive because cost division penalizes evaluations near that optimum.In the benchmarks, EIpu was worse than EI on nine of twenty HPO problems.Source: §2 · p. 2
• Batch BO selects diverse candidates for parallel evaluation, but achieving linear scaling with batch size remains challenging.Batch fantasizing extends acquisition functions by predicting multiple future evaluation trajectories.Source: §2 · pp. 2–3
• With fixed batch size, the paper measures cost by time, treating it as equivalent to energy and money when parallel resources consume equal power or dollars per unit time.This equivalence does not hold when batch size varies.Source: §2 · p. 3

CArBO

• CArBO combines a cost-effective initial design with cost-cooling, transitioning from cost-sensitive exploration toward standard EI as optimization proceeds.The method supports sequential and batch evaluation, using the total budget to control its cost-aware behavior.Source: §3 · pp. 3–4

Cost-effective initial design

• A cost-effective initial design fits more, well-distributed evaluations into the warm-start budget than a traditional design.It minimizes the fill criterion subject to the initial cost budget, balancing coverage against evaluation cost.Source: §3 · p. 3
• Algorithm 1 builds the design by repeatedly removing expensive and nearby candidates, leaving a cheap point far from existing evaluations.The procedure updates the cost surrogate after each evaluation and repeats until the initial budget is exceeded.Source: §3 · pp. 3–4
• With equal cost, the cost-effective design contains 15 points versus four for a grid and covers the search space better.Figure 4 compares the two designs over a synthetic cost-function contour.Source: Figure 4 · p. 4, §3 · p. 4

Cost-cooling

• Cost-cooling uses a positive warped-GP cost model and decreases its influence as the fraction of spent budget increases.When α decays from one to zero, EI-cool transitions from EIpu to EI.Source: §3 · p. 4

CArBO

• EI-cool is not guaranteed to outperform both EIpu and EI, although it usually outperforms at least one of them.Its intended schedule performs cheap evaluations before expensive ones.Source: §3 · p. 4
• CArBO uses τinit = τ/8 by default and batch-fantasizes cost-cooling to support parallel evaluations and linear wall-clock scaling.The algorithm evaluates the initial design, updates objective and cost surrogates, then iterates EI-cooling batches until the budget is exhausted.Source: §3 · p. 4

• The benchmark suite contains five scikit-learn HPO problems, four classification datasets, and 51 replications per benchmark on independent AWS machines.Each benchmark receives its own wall-clock budget.Source: §4 · pp. 4–5
• CArBO outperforms EI and EIpu by a large margin across all batch sizes.The evaluation averages normalized classification error across four datasets for each of five HPO problems.Source: §4 · pp. 5–6
• CArBO is best on 16, 18, 17, and 16 HPO problems for batch sizes one, three, seven, and eleven, respectively.It exploits more BO iterations than EI or EIpu for the same wall-clock time.Source: §4 · p. 6, Table 1 · p. 6
• CArBO achieves roughly 40 percent average cost savings across all benchmarks and batch sizes.Savings measure the time CArBO needs to reach results comparable to the next-best optimizer.Source: §4 · p. 6, Table 2 · p. 6

Batch Scaling

• CArBO scales linearly up to batch size 16, with little to no performance loss when total compute time is held constant.Wall-clock budgets decrease from 2400 to 150 seconds as batch size increases from 1 to 16.Source: §5 · p. 6, Figure 6 · p. 7

Initial Design

• Varying the initial-design budget from 1/8 to 6/8 leaves performance relatively unchanged, although the extreme 6/8 allocation degrades it slightly.A systematic method for selecting the initial-design budget is left for future work.Source: §5 · p. 7, Figure 7 · p. 7

Ablation Study

• The cost-effective initial design contributes more performance improvement than EI-cooling in the ablation study.The full CArBO configuration using EI-cooling performs best among the compared variants.Source: §5 · p. 7, Figure 8 · p. 7

6. Cost Surrogates

• Low-variance cost models improve cost-aware BO by extrapolating better than high-variance Gaussian-process cost predictions.The models use flop-based features and robust regression with Huber loss; they are applied to MLPs and CNNs.Source: §6 · p. 7
• The low-variance model improves EIpu performance on four MLP benchmarks under the stated architecture and training settings.The experiments use k = 4, layer sizes 10–300, batch size 100, and 200 epochs; median classification error and cost savings are reported in Table 3.Source: §6 · p. 7, Table 3 · p. 8
• A GP with a low-variance linear mean is the most accurate of three tested cost models on 10,000 random hyperparameter configurations.The comparison includes a warped GP, a low-variance model, and a GP whose mean is the low-variance model.Source: §6 · p. 8
• On MLP a1a, the low-variance cost model significantly improves performance over the default cost model.This is the best-performing benchmark among the four MLP benchmarks evaluated.Source: §6 · p. 8
• For CNNs, the low-variance model is better only with fewer than 20 training examples, because flop counts may not reflect optimized convolution runtime.In the limited-data regime it converges faster, but both models converge to the same optimum.Source: §6 · p. 8, Figure 10 · p. 8

7. Conclusion

• CArBO combines a cost-effective initial design with cost-cooling and outperforms EI and EIpu on real-world benchmarks in sequential and batch settings.The conclusion describes this result as applying to black-box cost-aware BO, where no external cost information is given.Source: §7 · p. 8
• Accurate cost modeling remains important, and the paper suggests extending flop-counting models, combining CArBO with multi-fidelity methods, and varying batch size.The authors identify these as future-work directions.Source: §7 · p. 8

A. Batch Bayesian Optimization

• Batch fantasizing evaluates the selected candidates in parallel after aggregating multiple possible future evaluation trajectories.The fantasies represent different posterior outcomes for previously selected points.Source: A. Batch Bayesian Optimization · p. 11
• The algorithm initializes nf copied outcome datasets, selects x1 by maximizing EI, and iteratively adds fantasized observations before selecting later points.The returned batch is X_b = {x1, ..., xb}.Source: A. Batch Bayesian Optimization · p. 11
• Batch fantasizing selects the first point by EI, then constructs remaining batch points by averaging EI across posterior fantasy models.CArBO uses 10 fantasies by default and repeats the procedure until b points are selected.Source: A. Batch Bayesian Optimization · p. 11

B. Cost Cooling

• As α decays from one to zero, EI-cool transitions from EIpu to EI rather than targeting either baseline exclusively.The method depreciates the cost model as the consumed budget τ_k approaches the total budget τ.Source: B. Cost Cooling · p. 11
• EI-cool usually outperforms at least one of EIpu or EI, but it is not guaranteed to outperform both on every benchmark.The KNN example is better than EIpu but worse than EI, while aggregate performance across four KNN benchmarks is better than both.Source: B. Cost Cooling · p. 11, Figure 11 · p. 11

• CArBO performs better than competing methods on all five evaluated problems.Source: C. CArBO · p. 11
• CArBO schedules cheap evaluations before expensive ones without requiring additional information.Source: C. CArBO · p. 11, Figure 12 · p. 12
• This scheduling pattern enables CArBO to converge faster than EI and EIpu, whose evaluation times vary widely because they lack explicit scheduling.Source: Figure 12 · p. 12