Evolve Cost-Aware Acquisition Functions Using Large Language Models

Yiming Yao, Fei Liu, Ji Cheng, Qingfu Zhang

Introduction

Bayesian Optimization (BO) has become the standard for optimizing expensive black-box functions, particularly in the realm of machine learning hyperparameter tuning. However, a significant limitation of traditional BO is the assumption of uniform evaluation costs. In real-world scenarios, such as training deep neural networks, evaluating different parameter sets can incur vastly different costs in terms of time and computational resources.

To address this, researchers have introduced EvolCAF (Evolve Cost-aware Acquisition Functions), a framework that leverages Large Language Models (LLMs) and Evolutionary Computation to automatically design "cost-aware" acquisition functions. By evolving executable Python code rather than neural network weights, EvolCAF produces interpretable and highly efficient algorithms that outperform traditional human-designed heuristics.

The Challenge of Cost-Aware Optimization

In cost-aware BO, the goal is to find the global optimum of a function while adhering to a strict budget (e.g., total training time or financial cost). The decision-making process is governed by an Acquisition Function (AF), which determines the next point to sample by balancing exploration and exploitation.

Historically, cost-aware AFs like EIpu (Expected Improvement per unit cost) were hand-crafted by experts. While effective in some cases, these heuristics often suffer from the "low-cost trap," where the optimizer repeatedly samples cheap but uninformative regions of the search space. Recent attempts to use "Meta-BO" to learn these functions via neural networks have resulted in "black-box" models that lack interpretability and are difficult for practitioners to trust or adapt.

Methods: EvolCAF Framework

EvolCAF treats the design of acquisition functions as an evolutionary process in the algorithmic space. The framework consists of several key components:

  1. Algorithmic Evolution: Unlike traditional genetic algorithms that evolve numerical parameters, EvolCAF evolves Python code. Each individual in the population is a complete acquisition function defined by a text description and its corresponding implementation.
  2. LLM as the Genetic Engine: The framework utilizes GPT-3.5-turbo to perform crossover and mutation. By prompting the LLM with successful parent algorithms, the system generates novel variations that refine the logic of the acquisition function.
  3. Fitness Evaluation: Candidate functions are evaluated on a suite of 12 synthetic optimization benchmarks (e.g., Ackley, Rastrigin). Fitness is measured by the "optimal gap"—the distance to the true global optimum—achieved within a fixed budget.

The Discovered "Elite" Function

The evolutionary process yielded a specific, human-readable acquisition function, $\alpha_{EvolCAF}$, which integrates three distinct components:

  • $\alpha_1$ (Enhanced Improvement): A modified version of Expected Improvement that considers the uncertainty across all historical data points, rather than focusing solely on the current best observation.
  • $\alpha_2$ (Budget-Awareness): A term that dynamically balances the remaining budget against the predicted cost of the next evaluation, allowing for more aggressive exploration of expensive regions when the budget permits.
  • $\alpha_3$ (Diversity): A term that encourages the optimizer to sample points far from previously explored regions to ensure a more global search.

Experimental Evaluation

The researchers evaluated EvolCAF against classic baselines, including standard EI, EIpu, and EI-cool, across two primary domains:

  • Synthetic Benchmarks: 12 classic functions with dimensions ranging from 2D to 8D. Costs were simulated using an exponential function centered at the global optimum to test the algorithm's ability to navigate heterogeneous cost landscapes.
  • Real-world Hyperparameter Optimization (HPO): The framework was tested on JAHS-Bench-201, a surrogate benchmark for joint architecture and hyperparameter search. This involved three image classification tasks: CIFAR-10, Colorectal-Histology, and Fashion-MNIST.

Key Insights and Results

Superior Performance and Efficiency

EvolCAF consistently achieved lower optimal gaps on synthetic tasks compared to human-designed heuristics. In real-world HPO tasks, it reached higher validation accuracies within the same time constraints. For instance, on the Fashion-MNIST dataset with a 5000-minute budget, EvolCAF achieved 93.70% accuracy, significantly outperforming EIpu (91.91%).

Interpretability and Generalization

Because the output of EvolCAF is Python code, the resulting strategies are fully interpretable. Analysis showed that the evolved function successfully avoided the "low-cost trap" by learning to prioritize informative, albeit expensive, samples when the remaining budget was sufficient. Furthermore, despite being evolved on simple 2D synthetic functions, the AF demonstrated remarkable zero-shot generalization, performing excellently on high-dimensional machine learning tasks without further tuning.

Conclusion

EvolCAF represents a significant step forward in automated algorithm design. By combining the creative potential of LLMs with the rigorous selection process of evolutionary computation, the framework discovers acquisition functions that are both more effective than human-designed heuristics and more interpretable than deep learning-based meta-optimizers. Future work will focus on expanding EvolCAF to handle diverse cost landscapes, batch optimization, and multi-objective scenarios.

Summary updated

BibTeX
@inproceedings{yao2024evolve,
  author = {Yiming Yao and Fei Liu and Ji Cheng and Qingfu Zhang},
  title = {{Evolve Cost-Aware Acquisition Functions Using Large Language Models}},
  booktitle = {PPSN},
  year = {2024},
  url = {https://openreview.net/forum?id=Njg1e48XQW},
}
Figure