Cost-Sensitive Freeze-thaw Bayesian Optimization for Efficient Hyperparameter Tuning

AI summary

Overview

• Research area: Hyperparameter optimization (HPO) for deep learning, specifically multi-fidelity Bayesian optimization and automated early stopping.
• Technical level: Advanced — requires familiarity with Bayesian optimization, acquisition functions, Gaussian processes, and Transformer-based surrogates.
• One-sentence scope: The paper introduces CFBO, a cost-sensitive freeze-thaw Bayesian optimization method that maximizes a user-defined cost–performance utility rather than raw validation accuracy, using a preference-estimated utility function, a new utility-based acquisition function, a regret-based stopping criterion, and transfer learning to make its surrogate model sample-efficient.

What This Paper Is About

Standard hyperparameter optimization and multi-fidelity methods aim to reach the best possible validation performance given a large budget. This ignores the reality that many users (cloud customers, Slurm users, practitioners with limited GPU time) care about the trade-off between how much compute they spend and how much performance they get. The paper formulates this as cost-sensitive HPO: the goal is to automatically stop the search near the point of maximum utility — defined by the user's own preference about cost versus accuracy — rather than running until an arbitrary budget is exhausted.

Key Contributions

1. New problem formulation — cost-sensitive multi-fidelity HPO. Instead of optimizing asymptotic validation performance, the paper formalizes the objective as maximizing a utility function U(b, ỹ_b) that explicitly trades off budget spent against best-cumulative performance achieved, and that can be estimated from user preference data.
2. A utility-based acquisition function for freeze-thaw BO. A modified Expected Improvement criterion that computes the expected improvement of utility rather than of accuracy, and dynamically picks the best future epoch Δt to train toward — instead of fixing the target epoch to the final epoch or a random one.
3. A regret-based stopping criterion with an adaptive threshold. BO terminates automatically when the estimated normalized regret at the current step exceeds a threshold δ_b, which is itself modulated by the probability that the currently selected configuration will still improve utility (a Beta-CDF transformation). This lets the method defer or trigger stopping based on real evidence of remaining upside.
4. Transfer learning via "LC mixup" for the surrogate model. A Prior-Fitted Network (PFN) learning-curve extrapolator trained with a two-stage mixup that interpolates across datasets and across configurations, creating effectively unlimited synthetic training LC data and making extrapolation accurate even in the very early stages of BO.

Main Findings

• CFBO wins on cost-sensitive settings: Across three benchmarks (LCBench, TaskSet, PD1), CFBO achieved the lowest normalized regret and best average rank on most utility-function settings (linear, quadratic, and square-root penalties with α ∈ {2⁻⁶ … 2⁻²}), beating both non-transfer baselines (Random Search, BOHB, DEHB, DyHPO, DPL, ifBO) and transfer baselines (Quick-Tune†, FSBO).
• Even the non-transfer variant is strong: CFBO-NT, which keeps only the utility acquisition and adaptive stopping (using ifBO's extrapolator), outperformed all non-transfer baselines and even surpassed the transfer-learning baseline FSBO in several PD1 settings.
• Conventional HPO performance is preserved: With α = 0 (no cost penalty), CFBO is comparable to ifBO and to transfer-BO baselines — so the cost-sensitivity machinery does not sacrifice standard performance.
• The stopping criterion works when it matters: Visualization on PD1 shows CFBO stops nearly at the optimum for stronger penalties (α ∈ {2⁻⁴, 2⁻³, 2⁻²}); even when the penalty is weak and it stops slightly late, the resulting regret is still lower than baselines'.
• Runtime overhead is negligible in practice: CFBO costs 1.52 s/step (LCBench), 0.78 s (TaskSet), 0.23 s (PD1) versus 0.58 / 0.30 / 0.08 for ifBO on an A100 — trivial compared to the ~90 s needed to train one ResNet-50 epoch on CIFAR-100.
• Real-world validation: On a real object-detection learning-curve dataset collected by the authors, CFBO achieved the best normalized regret and rank among all baselines.
• Acquisition shifts from exploration to exploitation: As performance saturates and cost accumulates, the utility-based acquisition becomes greedier, favoring continued training of the current best configuration rather than launching new ones.

Methodology in Plain English

The authors build on freeze-thaw Bayesian optimization, where a surrogate model looks at partially completed learning curves (validation accuracy after k epochs) and decides at each step which configuration to train for one more epoch — effectively pausing and resuming different runs.

Their changes:

1. Define utility instead of accuracy. A function U(b, ỹ_b) that rises with performance and falls with budget. Common choices are ỹ_b − α(b/B)^c for c ∈ {1, 2, 0.5}. Users who cannot state this function explicitly can instead answer a small number of "which of these two outcomes would you prefer?" questions; the paper fits the utility via the Bradley-Terry preference model with a cross-entropy loss.
2. Change the acquisition function. Standard Expected Improvement asks "how much better could accuracy get?" CFBO asks "how much better could utility get?", and it evaluates that across every possible future stopping epoch, picking the Δt with the largest expected utility gain. Crucially, the reference point isn't the best utility seen so far (budget is irreversible) but the most recent utility — so the reference can move up or down.
3. Stop automatically. The paper computes a rough normalized regret R̂_b and triggers termination when it exceeds a threshold δ_b. δ_b is adaptive: it grows with the probability that the selected configuration can still improve utility, so the optimizer is more willing to continue when upside genuinely remains, and less willing when it doesn't.
4. Make the surrogate sharp early with transfer learning. The PFN that extrapolates learning curves is trained on many real datasets, augmented by mixup: interpolating between two datasets' curves and between two configurations' curves to synthesize endless training examples. This prevents the model from overfitting to a small number of real learning curves and prevents premature stopping in early BO steps.

The full procedure is given as Algorithm 1 (blue-highlighted parts are CFBO-specific). Evaluation uses normalized regret R ∈ [0, 1] against the true optimal utility, averaged over multiple runs.

Why This Matters

Impact on research. The paper reframes multi-fidelity HPO from a "best attainable accuracy under a big budget" problem to a "best utility under a user's own cost preferences" problem. This opens a cleaner interface between HPO and preference learning, and shows that expected-improvement machinery can operate on a utility surface with irreversible budget — a setting where the standard monotone-best-reference assumption breaks down. The LC-mixup transfer approach is also a reusable recipe for any PFN-based surrogate that needs stronger generalization from limited real curves.

Real-world applications:

• Cloud HPO services (GCP, AWS, Azure): Users paying per training hour can set a penalty coefficient and let CFBO stop once additional credits stop buying meaningful accuracy.
• Cluster job schedulers (Slurm, LSF): Teams with wall-clock quotas can terminate sweeps at the point of maximum utility rather than wasting an allocation on marginal gains.
• AutoML platforms for enterprises: A preference-learning front end (just a handful of pairwise "which do you prefer?" queries) converts a customer's vague cost-versus-accuracy intuition into a concrete utility function without requiring them to tune meta-parameters.
• Resource-constrained research labs and academic groups: Where GPU hours are the binding constraint, CFBO gives a principled stopping rule instead of an arbitrary epoch budget.

Industry relevance. The method plugs into existing freeze-thaw and transfer-BO pipelines with small changes, runs at essentially the same speed as ifBO, and its utility function is the natural knob a business would actually want to expose to customers. The public code release at github.com/db-Lee/CFBO lowers the barrier for adoption.

Future Directions

• Beyond the parameterized utility family. The paper assumes one of a small set of functional forms (linear, quadratic, square-root, staircase). Future work could learn richer, non-parametric utility functions directly from preference data.
• Multi-objective and fairness-aware HPO. Extending the utility framework to more than one cost axis (e.g., dollars, carbon, latency) or to fairness constraints across tasks is a natural generalization.
• Weaker or noisier preference signals. How robust is the Bradley-Terry estimation under inconsistent users, cold-start (zero preference queries), or preferences that change during a sweep? The appendix suggests ~30 pairs suffice for their family, but the boundaries of that claim are open.
• Better transfer across domains. LC mixup provides a simple augmentation; whether learned task embeddings, hierarchical PFNs, or meta-learned priors could dominate it on low-resource or heterogeneous task suites remains to be tested.
• Alternative stopping theories. The regret threshold with Beta-CDF modulation is one design; comparing it to explicit expected-value-of-computation or information-theoretic stopping rules would sharpen the analysis.

Target Audience

• ML systems and AutoML researchers working on multi-fidelity HPO, freeze-thaw BO, transfer learning for surrogates, or early-stopping algorithms.
• Practitioners running large hyperparameter sweeps on cloud or cluster infrastructure who need a principled way to stop when marginal gains no longer justify compute.
• Preference-learning and human-in-the-loop researchers interested in bridging user preferences with optimization objectives.
• Graduate students with a solid background in Bayesian optimization and deep learning who want a concrete example of modifying EI and stopping criteria for a new decision-theoretic objective.

Authors’ abstract

In this paper, we address the problem of \emph{cost-sensitive} hyperparameter optimization (HPO) built upon freeze-thaw Bayesian optimization (BO). Specifically, we assume a scenario where users want to early-stop the HPO process when the expected performance improvement is not satisfactory with respect to the additional computational cost. Motivated by this scenario, we introduce \emph{utility} in the freeze-thaw framework, a function describing the trade-off between the cost and performance that can be estimated from the user's preference data. This utility function, combined with our novel acquisition function and stopping criterion, allows us to dynamically continue training the configuration that we expect to maximally improve the utility in the future, and also automatically stop the HPO process around the maximum utility. Further, we improve the sample efficiency of existing freeze-thaw methods with transfer learning to develop a specialized surrogate model for the cost-sensitive HPO problem. We validate our algorithm on established multi-fidelity HPO benchmarks and show that it outperforms all the previous freeze-thaw BO and transfer-BO baselines we consider, while achieving a significantly better trade-off between the cost and performance. Our code is publicly available at https://github.com/db-Lee/CFBO.