FunBO: Discovering Acquisition Functions for Bayesian Optimization with FunSearch

Thanks for your in-depth review of our work and valuable feedback.

Missing Baselines Our work focuses (footnote 2) on AFs that can be evaluated in closed form given GP posterior parameters thus being fast-to-evaluate and easily deployable while avoiding complexities like Monte-Carlo sampling (e.g., for entropy/KG methods). This is a deliberate choice to avoid the complexities of approximations (e.g., MC sampling), which would make both the evaluation of candidate AFs within FunBO computationally intractable and the generation of corresponding code by the LLM significantly more difficult.

As we restricted FunBO's search space to focus on discovering AFs within the class of closed-form deterministic functions, we ensured a fairer comparison by contrasting the discovered AFs against appropriate baselines like EI/UCB/PoI. In terms of end-to-end methods, we view FunBO as complementary. As noted in our Related Work section, Chen et al. (2022) found that even their transformer-based model benefited from using a standard AF (EI) for action selection. This suggests that AFs discovered by FunBO could potentially be integrated into such end-to-end frameworks in the future to further boost performance.

Computational Cost & Variance We acknowledge that the computational cost of FunBO is significant. Note however that FunBO is primarily intended as an offline procedure to discover high-quality AFs. The computational expense is incurred during this one-time search phase. Once discovered, the resulting code-based AF is typically very cheap to evaluate during the actual online BO task. The idea is that FunBO invests computation upfront to find an AF that significantly improves sample efficiency later.
While variance in the quality of the discovered AFs might further increase the computational cost, it's crucial to distinguish between the variance of the search process from the value of its outcome. Once found, a successful AF discovered by FunBO has an intrinsic value that is independent of the stochastic process that generated it. The AF represents a novel optimization strategy whose performance can be evaluated and used independently of the original search.

Discrete AF Optimization Within our experimental evaluation, the optimization of the AF was performed over a discrete Sobol grid to ensure fair comparison across all AFs. However, the discovered AFs are not fundamentally restricted to discrete optimization. As long as the surrogate model is differentiable (like a GP with RBF kernel) and the generated code includes differentiable functions, the AF can be optimized using continuous methods, similarly to EI or UCB. For instance, we could rewrite the AF in Fig 2 to take the input location x, return the corresponding scalar acquisition value and optimize it via L-BFGS.

Robustness to Surrogate Model Our current work focused on discovering AFs conditioned on a specific surrogate model, as stated in Sec 4, to isolate the AF's contribution. The performance of the discovered AFs might indeed depend on this choice. However, the FunBO methodology itself is flexible. By simply modifying the run_bo implementation to use a different surrogate model, FunBO can be used to discover AFs tailored to the specific model's properties.

Interpretation of Discovered AFs Note that we included an AF interpretation on line 287 and commented on the Goldstein-Price AF on line 359. As an additional example, the AF found for GPs-ID can be simplified to be written as (EI ** 2) / (1 + (z / beta)**2 * sqrt(var))**2. This function calculates the standard EI, squares it, and then divides it by a penalty term that increases with both the standardized improvement z = (incumbent - mean) / std and the uncertainty sqrt(var). The squaring of the EI non-linearly amplifies regions with high EI values relative to those with low or moderate EI. It increases the "peakiness" of the acquisition function, leading to stronger exploitation of the most promising point(s). The term (1 + (z/beta)**2 * sqrt(var))**2 penalizes points more heavily if they have a very high expected improvement (z is large and positive) and/or high uncertainty (sqrt(var) is large). This might act as a regularizer against over-optimism or excessive jumps into highly uncertain areas, even if they look very promising according to EI. It's a novel way of balancing exploration and exploitation discovered by FunBO.

Number of Repetitions The mean and standard deviation shown in the regret plots represent the performance variation across the set of test functions, not across multiple independent runs of the BO algorithm on a single function instance. For instance, for OOD-Bench, the average/std dev is over the 9 distinct test functions. We will clarify this point in the captions.

Thanks for your feedback and for highlighting the strengths of our work. We appreciate the constructive comments and recommendation for acceptance. Regarding the specific questions:

Application to Other Real-World Problems This is an excellent point. Our primary goal in this initial work was to establish the FunBO methodology itself, demonstrating its feasibility for discovering novel AFs from code and rigorously evaluating their performance and generalization capabilities using well-understood application domain (standard benchmarks and simple HPO problems). Exploring diverse real-world applications would require careful consideration of the specific problem characteristics and potentially curating relevant sets G representative of the target domain. We agree this is a significant and exciting direction, and we view it as important future work, building upon the foundation laid in this paper.

Incorporating Problem-Specific Information Currently, FunBO provides context to the LLM through the structure of the initial AF, the function docstrings and the prompt structure including prior examples. Building on this, there are indeed several ways the prompt context could be further enriched:

• Adding Performance Data: We could go beyond the implicit ranking in the prompt and explicitly include the numerical scores attained by the included AFs. This might provide the LLM with a clearer signal about the magnitude of improvement to aim for.
• Adding Self-Critique: Another avenue, inspired by self-improvement techniques, could involve incorporating automatically generated or human-written critique/analysis of why the provided example AFs perform as they do directly into the prompt. This could potentially help the LLM focus on refining successful strategies or avoiding pitfalls.
• Adding Problem Descriptions: Incorporating explicit textual descriptions of the problem domain (e.g., "tuning hyperparameters for a binary classification model" or "optimizing a robotic grasp"), as proposed.

From an implementation perspective these can be easily incorporated in the prompt structure used by FunBO. It is plausible that providing richer information through any of these additions could allow the LLM to better leverage its internal knowledge base, potentially leading to further improvements in the discovered AFs. The exploration of the impact of richer prompt contexts (including scores, critique, or domain descriptions) is an interesting direction for future investigation, as mentioned in our Future Work section (Section 5).

Thanks for your in-depth review of our work and valuable feedback.

Transformer Cost We agree that re-training large transformer architectures is expensive. Our statement was intended to mean that a pre-trained transformer surrogate model could benefit from using a cheap-to-evaluate, FunBO-discovered AF instead of standard AFs (like EI, as used in Chen et al. 2022), rather than implying FunBO would be involved in the transformer training itself.

AF/HP optimization We removed the local maximization step from the MetaBO baseline to ensure a consistent comparison framework where all AFs are optimized over the same Sobol grid. This was done to isolate the performance differences attributable purely to the AF's selection logic, removing confounding effects from the quality of optimization routines. For the same reason, we used fixed GP hyperparameters. We aimed for a controlled comparison of the AFs' inherent selection strategies and believe this approach leads to an evaluation that is sound and appropriate as recognized by Reviewer FFHS (“The experimental design carefully controls for confounding factors by maintaining consistent GP hyperparameters …”). We will clarify that this might deviate from a fully realistic deployment scenario.

G cheaper than f FunBO can run even if functions in $G_{\text{Tr}}$ are expensive, but the offline discovery phase becomes proportionally costly. The practicality of FunBO relies on the idea that functions in $G_{\text{Tr}}$ are indeed cheaper (e.g., lower fidelity simulations, see response to Reviewer zkmL) and the large offline cost is amortized by finding an AF that saves numerous evaluations of the truly expensive target function f during online deployment.

Questions:

1. This refers to the AF signature where predictive_mean and predictive_var are NumPy arrays, as opposed to simpler functions found by FunSearch that might only take scalar or tuple inputs.
2. This occurs if $|G|$ is small and/or if the user decides to use all available functions for training to maximize the training signal e.g. in few shot settings.
3. Using a completely random initial AF encourages the LLM to generate AF code that itself included stochastic elements (e.g., various calls to np.random). This makes the resulting BO loop non-deterministic, making scoring inconsistent and reproducibility difficult.
4. The mean and standard deviation shown in the regret plots represent the performance variation across the set of test functions (e.g 9 distinct test functions for OOD-Bench), not across multiple independent runs of the BO algorithm on a single function instance. We used std/2 for visualization purpose.
5. Thanks for pointing us to these references. Notice that the figures you mention are averaging the convergence results over multiple random initializations. In our case we are averaging the convergence results over multiple, completely different, functions. Plotting the performance on the single functions reveals that known AFs outperform random search in most cases, performing better for lower dimensional functions and being competitive on functions with numerous local optima.
6. This refers to the limited number of functions available in G. We will rephrase this to be “by leveraging access to a number of evaluations for a limited set of objective functions.”
7. We omitted them to avoid clattering the figure but we are happy to add them back to the manuscript.

Other comments:

1. For Fig 4 (right panel, HM3), MetaBO is indeed outperforming FunBO. However, in the statement you report we refer to “general purpose AF” (e.g. EI) that are indeed underperforming compared to FunBO.
2. This is a typo. $T_{h_{j}^{\tau}}$​ represents the number of BO trials required by the algorithm using AF $h_j^{\tau}$ to identify the true minimum value $y_j^*$​. This is recorded for each AF $h_j^{\tau}$ sampled at step $\tau$. Note that also $x^*_{j,h^\tau}$ should be $x^*_{j,h_j^\tau}$.
3. The sampling scheme details are given in Appendix C and they are kept fixed with respect to FunSearch. The code for the latter is available on GitHub making the algorithm reproducible.
4. As specified on line 312, all experiments are conducted using FunSearch with default hyperparameters, including the number of examples in the prompt.
5. Thank you for providing this helpful list of suggested references. We will incorporate them in the revised manuscript and add a related discussion. Regarding symbolic regressions, these methods also searches for mathematical expressions, often represented as trees and evolved using genetic operators. FunBO differs by operating directly on code representations, leveraging an LLM for generation/mutation, and using full BO performance as the fitness metric. While related in the goal of finding functional forms, the search space representation and operators are different.

Thanks for your feedback and for highlighting the strengths of our work. We hope the responses below clarify the motivation and practical considerations for FunBO.

Benefits of Representing AFs as Programs Representing AFs as programs offers the following advantages:

• Interpretability: As highlighted in our paper, code-based AFs are inherently interpretable. It is possible to directly inspect, analyze, and understand the logic behind the optimization strategy employed by the discovered AF. This contrasts with neural network based AFs, for which it is difficult to understand why they perform well or how they balance exploration/exploitation.
• Deployability and Simplicity: AFs discovered by FunBO are outputted as concise code snippets (e.g., Python functions). As mentioned in Section 1, these can be readily integrated into existing BO libraries and workflows with minimal overhead.
• Leveraging Foundational Knowledge: LLMs trained on vast code and text have knowledge about code but also about existing BO strategies. FunBO aims at leveraging this embedded knowledge to efficiently explore the program space and construct effective heuristics.

We have further clarified the benefits of the code representation by adding text elaborating on these advantages (Interpretability, Deployability, and Leveraging Foundational Knowledge) around line 92 in Section 1.

Practical Use Cases In the limitation section we mentioned the fact that FunBO's evaluation cost might be high during the discovery phase as it involves running a full BO loop for each candidate AF on functions in G. However, there are scenarios where the evaluation cost for the functions in G might relatively cheap. For instance:

• Simulations/Models at Lower Fidelity: G could consist of faster, lower-fidelity simulators or simplified analytical models related to the expensive target problem f.
• Surrogate Models: G could include cheap surrogate models learned from previous related tasks.
• ML Hyperparameter Optimization. G can represent the performance of a ML model on different (potentially smaller) datasets, where training/evaluation might be faster than on the final, large target dataset.

Note that the computational cost incurred during this one-time search phase is compensated during the online deployment phase where the resulting discovered AF reduces the number of costly function evaluations needed.

We have expanded the discussion on the computational cost within the Limitations paragraph in Section 5 and gave the examples listed above as cases where the auxiliary functions used during the search phase might be relatively inexpensive.