Unleashing the Potential of Acquisition Functions in High-Dimensional Bayesian Optimization
Authors: Jiayu Zhao
Renyu Yang
SHENGHAO QIU
Zheng Wang
Venue: Accepted by TMLR ()

Abstract: Bayesian optimization (BO) is widely used to optimize expensive-to-evaluate black-box functions. It first builds a surrogate for the objective and quantifies its uncertainty. It then decides where to sample by maximizing an acquisition function (AF) defined by the surrogate model. However, when dealing with high-dimensional problems, finding the global maximum of the AF becomes increasingly challenging.  In such cases, the manner in which the AF maximizer is initialized plays a pivotal role.  An inappropriate initialization can severely limit the potential of AF.

This paper investigates a largely understudied problem concerning the impact of AF maximizer initialization on exploiting AFs' capability. Our large-scale empirical study shows that the widely used random initialization strategy may fail to harness the potential of an AF. Based on this observation, we propose a better initialization approach by employing multiple heuristic optimizers to leverage the historical data of black-box optimization to generate initial points for an AF maximizer.  We evaluate our approach with a variety of heavily studied synthetic test functions and real-world applications. Experimental results show that our techniques, while simple, can significantly enhance the standard BO and outperform state-of-the-art methods by a large margin in most test cases.

Published in Transactions on Machine Learning Research (01/2024)
Unleashing the Potential of Acquisition Functions in High- Dimensional Bayesian Optimization
An empirical study to understand the role of acquisition function maximizer initializa- tion
Jiayu Zhao
sejzh&leeds.co uk
School of Computing University of Leeds
Renyu Yang
r.yang @loeds ac. uk
School of Compuling University of Leeds
Shenghao Qiu
sc19sg@leeds.cc uk
School of Computing University of Leeds
Zheng Wang
2. wang55āleeds.ac
School Computing
University of Leeds
Reviewed on OpenReview: https: // openreview. net/ forum? id- 0CH7Hfsy61
Abstract
Bayesian optimization (BO) is widely used to optimize sopensive-to-evaluue black-box func- tions. BO first builds surrogate model to represent the objective function and assesses its uncertainty. It then decides where to sample by maximizing an acquisition function (AF) based on the surrogate model. However, when dealing with high-dimensional problems, finding the global maximum of the AF becomes increasingly challenging. In such cases, the initialization of the AF maximizer plays pivotal role, as an inadequate setup can severely hinder the effectiveness of the AF.
This paper investigates largely understudied problem concerning the impact of AF maxi- mizer initialization on exploiting AFs' capability. Our large-scale empirical study shows that the widely used random initialization strategy often fails to harness the potential of an AF. In light of this, we propose a better initialization approach by employing multiple heuristic optimizers to leverage the historical data of black-box optimization to generate initial points for the AF maximizer. We evaluate our approach with a range of heavily studied synthetic functions and real-world applications. Experimental results show that techniques, while simple, significantly enhance the standard BO and outperform state-of- state-of-the-art by large margin in most test cases.
the-art methods
1 Introduction
Bayesian optimization (BO) is well-established technique for expensive black-box function optimization. It has been used in a wide range of tasks from hyper-parameter tuning (Bergstra et al. 2011), onto chemical material discovery ([Lernándezz-Lobatoo el al. 2017) and robot control and planning (Lizotte el al., 2007 Martinez-Cande Cantin et al., (2009). BО tries to improve sampling efficiency by fitting a probabilistic surrogate model (usually Gaussian process (Seeger 2004)) guide its search. This model is used define an acquisition function (AF) that trades off exploitation (model prediction) and exploration (model uncertainty). Maximizing the AF will get the next. sequential query point that BO thinks is promising.

---

Published in Transactions on Machine Learning Research (01/2024)
While BO shows good performance for low-dimensional problems, its application to high-dimensional prob- lems is often not competitive with other techniques (Eriksson et al. 2019 Given that BO's performance depends on both the model-based AF itself and the process of maximizing the AF, either of them can be a bottlenock for high-dimensional BO (HDBO). The vast majority of the prior work in BO has focused on the
Tormer, Tee, designing the surrogate model and AF (Snoek el al. 2012 Srinivas el al. 2009 Wu & Frazier 2016: Wang & Jegelka| 2017 Oh et al. 2018 Moss et al.) |021; Snook et al., 2014). Little work is specialized for improving the latter. A recent development in maximizing AF implements a multi-start gradient- based AF maximizer in batch BO scenarios, achieving better AF maximization results than random sampling and evolutionary algorithms (Wilson et al. 2018). However, as the dimensionality increases, even the multi-start gradient-based AF maximizer struggles to globally optimize the AF. In such cases, the initialization of the AF maximizer greatly influences the quality of AF optimization. Yel, it remains unclear how AF maximizer initialization may impact the utilization of AF's potential and the end-to end-to-end BO performance. Upon exam- ining the implementations of the state-of-tho-art BO packagos, we found that random initialization (sclecting initial points from set of random points) or variant. is typical default strategy for initializing the AF maximizer. This is the case for widely- used BO packages like BoTorch (Balandat et al. 2020), Skopt (Head et al.
2021p. Trieste (Picheny et al. 2023), Dragonfly (Kandasamy et al. 2020) and OPilowOpt (Knudde ct al.
2017a). Specifically, GPflowOpt, Trieste and Dragonfly select the top n points with the highest AF values from a set of random points to serve as the initial points. BoTorch uses a similar but more exploratory strategy by performing Boltzmann sampling rather than top-n selection on random points. Likewise, Skopt directly selects initial points by uniformly sampling from the global search domain. Furthermore, various
HDBO implementations adopt random initialization as their default strategy (Oh et al. 2018: Letham et al., Wang et al., 2018:
2020
Kandasamy et al., 2015 Wu & Frazier 2016; Wang et al. 2017). GPyOpt (The) GPyOpt authors 2016) and Spearmint (Snoek et al. 2012) are two of the few works that provide different
initialization strategies from random initialization. GPyOpt combines random points with the best-observed points to serve as the initial points. Spearmint uses a Gaussian spray around the incumbent best to generate initial points. However, no empirical study shows that these initialization strategics are better than random initialization. As such, random initialization remains the most popular strategy for HDBO AF maximization. There is a need to understand the role of the initialization phase in the AF maximization process.
The paper systematically studies the impact of AF maximizer initialization in HDBO. This is motivated by observation that the pool of available candidates generated during AF maximization often limits the AF's power when employing the widely used random initialization for the AF maximizer. This limitation asks for a better strategy for AF maximizer initialization. To this end, our work provides a simple yet effective AF maximizer initialization method to unleash the potential of an AF. Our goal is not to optimize an arbitrary AF but to find ways to maximize the potential of reasonable AF settings. Our key insight is that when the AF is effective, the historical data of black-box optimization could help identify areas that exhibit better black-box function values and higher AF values than those obtained through random scarches of AF.
We develop AIBCH a Python framework to employ multiple heuristic optimizers, like the covariance matrix adaptation evolution strategy (CMA-ES) (Hansen et al. 2003) and genetic algorithms (GA) (Alam et al. 2020), to utilize the historical data of black-box optimization to generate initial points for a further AF maximizer. We stress that the heuristics employed by AIBO are not used to optimize the AF. Instead, they capitalize on the knowledge acquired from the alrcady evaluated samples to provide initial points to help an AF maximizer find candidate points with higher AF values. For instance, CMA-ES generates candidates from multivariate normal distribution determined by the historical data of black-box optimization. To investigate whether performance gains come from better AF maximization, AIBO also incorporates random initialization for comparison. Each BO iteration runs multiple AF initialization strategies, including random initialization on the AF maximizer, to generate multiple candidate samples. Tt then selects the sample with the maximal AF value for black box evaluation. Thus, heuristic initialization strategies work only when they identify higher AF values than random initialization.
To demonstrate the benefit of ATBO in black-box function optimizations, we integrate it with the multi-start gradient-based AF maximizer and apply the integrated system to synthetic test functions and real-world applications with search dimensionality ranging between 14 and 300. Experimental results show that
ATRO =Acquiitionn function maximizer Initialization Bayesian Optimization.
2

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO significantly improves the standard BO under various AF settings. Our analysis suggests that the performance improvement comes from better AF maximization, highlighting the importance of AF maximizer initialization in unlocking the potential of AF for HDBO.
The contribution of this paper is two-fold. Firstly, it investigates a largely ignored yet significant problem in HDBO concerning the impact of the initialization of the AF maximizer on the realisation of the AF capability. It empirically shows the commonly used random initialization strategy limits AIFs power, leading to over-exploration and poor HDBO performance. Secondly, it proposes simple yet effective initialization method for maximizing the AF, significantly improving the performance of HDBO. We hope findings can encourage more rescarch efforts in optimizing the initialization of AF maximizers of HDBO.
Data availability The data and code associated with this paper are openly available at https://ggiii com/ hamm/glloamiggdda/AAEEE
2 Related Work
2.1
High-diimensonal Bayesian Optimization
Prior works in HDBO have primarily focused on dimensionality reduction or pinpointing the performance bottleneck. There are two common approaches for dimensionality reduction. The first assumes the black-box function has redundant dimensions. By mapping the high-dimensional space to low-dimensional subspace, standard BO can be done in this low-dinensional space and then projected up to the original space for function evaluations (Wang et al.)
2013
Letham et al. 2020 Binois et al., 2020 Qian et al., 2016). A
second approach largets functions with additive structures, i.e., cases where variables in the design space
are separable (Kandasamy et al.
2015
Wang et al.) 2017 Gardner et al. 2017 Rolland et al.) 2018 Li
ctt al. 2018). Espocially, LineBO Kirschner et al.] (019)) restricts the optimization problem to a sequence of
iteratively chosen one-dimensional sub-problems. Both strategies are inadequate for many real-life scenarios
where the black-box function does not exhibit additive structures lacks redundancy in dimensions. Besides these dimensionality reduction techniques, efforts have been made to improve high-dimensional BO directly
(Wang et al.] 2018 Rana et al.) 2017 Oh et al. 2018 Eriksson et al. 2019). with TuRBO (Eriksson et al.
2019) as the stale-of-the-ar( mel
2.2 Acquisition Function Maximization
Given the posterior belief, BO uses an AF to select new querics. Random sampling, evolutionary algorithms and gradient-based optimization are three mainstreamed AF maximization techniques. Random sampling is efficient in low-dimensional problems (Bartz-Beielste be inadequate for high-dimensional problems (Hutter al.] 2011). Evolutionary algorithms
et al. 2005 Hutter al., 2009 2010) but can
often used
where gradient information is unavailable (Kandasamy et al. 2020 Cowen-Rivers et al. 2020 For AFs that support gradient information, multi-start gradient-based optimization method is a good choice for AF optimization (Wilson et al. 2018). Our end-to-end BO framework thus builds upon this technique.
Despite the importance of AF maximization, little attention has been paid to optimizing the initialization phase for AF maximizers. Most prior work (Snock et al.
2012
Knudde et al.
Wu & 2017b Klein et al. 2017
Frazier 2016
Kandasamy al.] 2020: Balandat et al.
2020
Oh et al.) 2018
Kandasamy et al. 2015
Wang
et al. 2018
Cowen-Rivers et al. 2020
Letham et al.
2020
Nayebi et al. 2019) uses random initialization.
This simple strategy can be effective in low dimensions, but
will show in the paper, it is ill-suited for
high-dimensional problems. SMAC (Hutter et al. 2011 and Spcarmint (Snock et al., (012) are a few BO techniques that do not use random initialization. Instead, they use a Gaussian spray around the incumbent best to generate initial points to initialize its local maximizer. Our work provides a systematic study to empirically demonstrate the importance of initialization for AF maximization. It proposes an initialization optimization to improve prior work by leveraging multiple heuristic algorithms to more effectively utilize the evaluated samples, significantly improving the performance of given AF.
3

---

Published in Transactions on Machine Learning Research (01/2024)
AF-based selection (BO-grad)
Optimal selection
Random selection
global optimum
Ackley100
Ackley100
14
Black-box function value
14
12
Black-box function
10
8
0
400 800
1200
1600
2000
400
800
1200
1600
2000
Number of black-box function evaluations
Number of black-box function evaluations
(a) 10 AF maximizer restarts
(b) 1000 maximizer restarts
Figure 1: Evaluating the sample chosen by AF-basod selection against random and optimal selection among all intermediate candidate points generated during the AF maximization process when applying BO-grad to 100D Ackley functions. We use two random initialization settings for AF maximization: (a) 10 restarts and (b) 1000 restarts. In both settings, the performance of the native BO-grad (AF-based selection) is close to optimal selection and better than random selection, suggesting that the AF is effective at selecting a good sample from all candidates but is restricted by the pool of available candidates. Increasing the number of restarts from 10 1000 does not enhance the quality of intermediate candidates, indicating that a more effective initialization scheme, as opposed to random initialization, is necessary.
3 Motivation
As motivation example, consider applying BO to optimize a 100-dimensional black-box Ackley function that is extensively used for testing optimization algorithms. The goal is to find a set of input variables (z) to minimize the output, [(r),..., The search domain - S x; S 10, i 1,2...., ......,100, 100, with a global minimum of 0. For this example, we use a standard BO implementation with a prevalent AF Upper Confidence Bound (UCB) (Srinivas et al. 2009), denoted as:
a (x) = =x(x) + 3r (x)
(1)
where p(x) and oxx) are the posterior mean (prediction) and posterior standard deviation (uncertainly) at point æ predicted by the surrogate model, and Be hyperparameter that trades off between exploration and exploitation. we set 9 = 1.96 in this example.
Here, we use random search create the initial starting points for a multi-start gradient- AF maximizer to iteratively generate multiple candidates, from which the AF chooses a sample for evaluation. In each BO iteration, first evaluate the AF on 100000 random points and then select the top points the initial points for the further gradient-based AF maximizer. We denote this implementation as BD-grad. In this example, we use two settings = 10 and n 1000.
As shown Fig. aa), the function output given by BO-grad with 10 AF maximizer restarts is far from the global minimum of O. We hypothesize that while the AF is effective, the low quality of candidate samples generated in AF maximization limits the power of the AF. To verify our hypothesis, we further consider two strategies: (1) cither randomly select the next query point from all the candidate points generated during AF maximization or (2) exhaustively evaluate them al each BO iteration. The former and latter stralegies correspond to "random selection" and "optimal selection" schemes, respectively. Despite the ideal but costly "optimal selection" search scenario, BO does not converge well, indicating intrinsic deficiencies in the AF maximization process. Mcanwhile, the AF itself can choose a good candidate sample point to evaluate,
20ther acquisition functions include the probability improvemett (PI) and expected improvement (FI).
4

---

Published in Transactions on Machine Learning Research (01/2024)
the performance of the native AF-based BO-grad is close to that of "optimal selection' and better than that of "random selection". This observation suggests that the AF is effective at selecting a good sample in this case but its power is severely limited by the candidate samples generated during the AF maximization process. We also observe similar results manifest when using other representative maximizers like random sampling and evolutionary algorithms.
We then test what happens when we increase the number of AF maximization restarts of BO-grad to generate more candidates for AF to select at each iteration. However, in Fig. [[b,, it is evident that even with an increase in random restarts to 1000, the quality of intermediate candidate points generated during the AF maximization process remains similar to that with 10 restarts. Furthermore, in the case of 1,000 restarts, the performance of BO-grad is still close to that of "optimal selection', reinforcing our observation that the pool of candidates restricts AF's power. This observation suggests that we need a better initialization scheme rather than simply increasing the number of restarts of random initialization.
This example motivates us to explore the possibility of improving the BO performance by providing the AF with better candidate samples through enhanced AF maximizer initialization. Our intuition is that the potential of AF is often not fully explored in HDBO. Moreover, the commonly used random initialization of the AF maximization process is often responsible for inferior candidates. We aim to improve the quality of the suggested samples through an enhanced mechanism for AF maximizer initialization. As we will show in Section O our strategy significantly improves BO on the 100D Ackley function, finding an output minimum of less than 0.5, compared to given by BO-grad after evaluating 5,000 samples.
4 Methodology
Our study focuses on evaluating the initialization phase of AF maximization. To this end, we developed AIBO, open-source framework to facilitate exhaustive and reproducible assessment of AF maximizer initialization methods.
4.1 Heuristic Acquisition Function Maximizer Initialization
AIBO leverages multiple heuristic optimizers' candidate generation mechanisms to generate high-quality initial points from the already evaluated samples. Given the proven effectiveness of heuristic algorithms in various black-box optimization scenarios, they are more likely to create initial candidates near promising regions. As an empirical study, we aim to explore whether this initialization makes the AF optimizer yield points with higher AF values and superior black-box function values compared to random initialization.
As described in Algorithm | AIBO maintains multiple black-box heuristic optimizers oo, 01-11 At each BO iteration, each heuristic optimizer o, is asked to generate raw points X' based on its candidate genera- tion mechanisms (e.g., CMA-ES generates candidates from a multivariate normal distribution). AIBO then selects the best n points X from X' for each optimizer o,, respectively. After using these points to initial- ize and run AF maximizer for each initialization strategy, we obtain multiple candidates "!.,,, Finally, the candidate with the highest AF value is chosen as the sample to be evaluated by querying the black-box function. Crucially, the evaluated sample is used as feedback to update each optimizer o; for example, updating CMA-ES's normal distribution. This process repeats at each subsequent BO iteration.
Our current default implementation employs CMA-ES, GA and random search as heuristics for initialization. We use the Coomiin-then-selede approach because allows us to examine if GA/CMA-ES initialization could find better AF values than random initialization. Our scheme only chooses GA/CMA-ES initialization if it yields larger AF values than random initialization. Besides, while heuristics like GA already provide ex- ploratory mechanisms and altering its hyperparameters can achieve different trade-offs, the usage of random initialization here could also mitigate the case of over-exploitation.
CMA-ES CMA-ES uses a multivariate normal distribution ((m, C*) to generate initial candidates in each BO iteration. Here, the mean vector m determines the center of the sampling region, and the covariance matrix C determines the shape of the region. The covariance matrix m is initialized at the beginning of the BO search, and each direction (dimension) will be assigned an initial covariance, ensuring exploration across
5

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 1 Acquisition function maximizer initialization for high-dimensional Bayesian optimization (AIBO)
Input:
The number of search iterations T
Output:
The best-performing query point x.
1: Draw N samples uniformly to obtain an initial datasct Do
2: Specify set of heuristic optimizers O, where the size is I
3: Use Do to initialize a set of heuristic optimizers ?
4: for t= 0: 7- do
5: Fit Gaussian process G to the current dataset Dt
6: Construct acquisition function axx) based on G
7: for i = 0: do
8:
X -...ak((uum = k)
Ask the heuristic to generate & candidates
9:
X top(a(X")),))
D. Sclect top-n (n < k) candidates from X according to a(a)
Use X initialize an acquisition function maximizer M
s; < arg max a
b Use to maximize o(x)
sEx
12:
end
13:
2t + arg mag a(x) x (x. of
Select the point with the highest AF value b Evaluate the selected sample
14:
Ve - [(xe)
15:
for each or E do
16:
octtel((z,, 8t)
Update heuristic optimizer or with (#1, ve)
17: end for
18: Update dataset De+1 = De U ((rt.e)))
19:
end for
all directions. By updating and C using new samples after each BO iteration, CMA-ES can gradually focus promising regions.
GA GA keeps a population of samples to determine search region. uses biologically inspired operators like mutation and crossover generate new candidates based on the current population. Its population is updated by newly evaluated samples after each BO iteration.
Random Most BO algorithis or library implementations use random search for initializing the AF max- imizer. We use it here to eliminate the possibility of AlBO's performance improvement stemming from GA/CMA-ES initialization, yiclding points with better black-box function values but smaller AF values.
Our heuristic initialization process is AF-related, as the heuristic optimizers are updated by AF-chosen samples. Usually, a more explorative AF will make the heuristic initialization also more explorative. For instance, in GA, if the AF formula leans towards exploration, the GA population composed of samples chosen by this AF will have greater diversity, leading to generating more diverse raw candidates. The details of how GA and CMA-ES generate candidates and update themselves are provided in Appendix A.2.
4.2 Implementation Details
Since this study focuses the AF maximization process, we utilize other BO settings that have demonstrraed good performance in prior work. We describe the implementation details as follows.
Gaussian process regression To support scalable GP regression, we implement the GP model based on an optimized GP library GPyTorch (Gardner et al. 2018 GPyTorch implements the GP inference via a modified batched version of the conjugate gradients algorithm, reducing the asymptotic complexity of exact GP inference from O(z²) to On?)). The overhead of running BO with GP model for few thousand evaluations should be acceptable for many scenarios that require hundreds of thousands or more evaluation iterations.
We select the Matérn-5/2 kernel with ARD (each input dimension has a separate length scale) and a constant mean function to parameterize our GP model. The model parameters are fitted by optimizing the log- marginal likelihood before proposing a new batch of samples for evaluation. Following the usual GP fitting procedure, re-scale the input domain to [0, 1jd. We also power transforms to the function values to

---

Published in Transactions on Machine Learning Research (01/2024)
Table 1: Benchmarks used in evaluation.
Function/Task
# #Dimensions
Search Range
Ackley
100, 300
[-5, 10]
Roseubrock
20, 100, 300
[-5, 10]
Synthetie
Rastrigin
20, 100, 300
-5.12, 5.12]
Griewank
20, 190, 300
-10, 10]
Levy
20, 100, 300
6600, 600]
Rohot pushing
14
(o, I]
Robotics
Rover trajectory planning
60
Half-Cheetah locomotion
[-1,
make data more Gaussian-like. This transformation is useful for highly skewed functions like Rosenbrock and has been proven effective in real-world applications (Cowen-Rivers et al. 2020 We use the following bounds for the model parameters: length-scale A [0.005, 20.0], noise variance o² E (l0=1,
Batch Bayesian optimization To support batch evaluation for high-dimensional problems, we employ the UCB and ET AFs estimated via Monte Carlo (MC) integration. Wilson et al. (0188) have shown that MC Afs naturally support queries parallel and can maximized via a greedy sequential method. Algorithm [ shows the case where the batch size is one. Assuming the batch size is q, the process of greedy sequential acquisition function maximization can be expressed as follows:
1. Maximize the initial MC acquisition function (x()) to obtain the first query point Tp-
2. Use the first query sample (Io, (xo)) to update (xx) to (x) and maximize a (x) to obtain the second query point Z1.
3. Similarly, successively update and maximize a² .... (*) and obtain query points 22, Tq-
We implemented it based on BoTorch [Balandat et al. 2020), which provided the MC-estimated acquisition functions and the interface for function updating via query samples. Details of the calculation of MC- estimated AFs are provided in Appendix A.5.
Hyper-parameter settings We use N = 50 samples to oblain all benchmnrrks' initial dataset Do. We set k 500 and n for each AF maximizer initialisation strategy. We use the implementations pycma (Hansen et al. 2022 and pymoo (Blank & Deb 2020) for the CMA-ES and the GA initialization strategies, respectively. For CMA-ES, we set the initial standard deviation to 0.2. For GA initialization, we set the population size to 50. The default, AF maximizer in AIBO is the gradient-based optimization implemented in Bo'Torch The default AF is UCB with 3r = 1.96 (default setting in the skopt library (Head ct al. 2021)), ), and the default batch size is sct to 10. In Section 6.6 we will also show the impact changing these hyper-parameters in our experiments.
5
Experimental Setup
5.1
Benchmarks
Table ! lists the benchmarks and the problem dimensions used in the experiments. These include synthetic functions and three tasks from the robot planning and control domains.
Synthetic functions We first apply AIBO and the baselines to four common synthetic functions: Ack- ley, Rosenbrock, Rastrigin and Griewank. All these functions allow flexible dimensions and have global minimum of 0. We select 20, 100 and 300 dimensions in our study to show how higher dimensions of the same problem influence the BO performance.
Robot pushing The task used in TurBO Eriksson al. (2019) and Wang et al. 2018 to validate high-dimensional BOs. The goal is to tune controller for two robot hands to push two objects to given

---

Published in Transactions on Machine Learning Research (01/2024)
target locations. Despite having only 14 dimensions, this task is particularly challenging the reward is sparse in its search space.
Rover trajectory planning The task, also considered in Briksson el al. (2019): Wang el al. (2018), is to maximize the trajectory of a rover over rough terrain. The trajectory is determined by fitting a B-spline to 30 points in a 2D plane (thus, the state vector consists of 60 variables). This task's best reward is 5.
Half-cheetah robot locomotion We consider the 102D half-cheetah robot locomotion task simulated in MuJoCo (Todoroy et al. 2012) and use the lincar policy a = Ws introduced in (Mania et al. 2018) to control the robot walking. Herein, 8 the stale vector, the action vector, and W is the linear policy be searched for marimize the reward. Each component of W continuous and within [-1,1].
5.2 Evaluation Methodology
We design various experiments to validate the significance of the initialization of the AF maximization process. All experiments are run 50 times for evaluation. In Section 6.1 we evaluate AIBO's end-to-end BO performance by comparing to various baselines including standard BO implementations with AF maximizer random initialization, heuristic algorithms and representative HDBO methods. In Section 6.2 we evaluato the robustness of AIBO under different AFs. In Section 6.3 evaluate AIBO's three initialization strategies in terms of AF values, GP posterior mean, and GP posterior variance under different AF settings. This will show whether AIBO's heuristic initialization strategies lead to better AF maximization. In Section 6.4 use ablation experiments to examine the impact of the three individual initialization strategies in AIBO. In Section 6.5 we compare ATBO to BO implementations with alternative AF maximizer initialization
strategies rather than selecting initial points with the highest AF values from a set of random points. In
Section 6.6 we show the impact of hyper- parrmmpaaasssers on the performance AIBO. In Section 6.7 we provide
the algorithmic runtime of our method.
6 Experimental Results
Highlights of our evaluation results are:
AIBO significantly improves standard BO and outperforms heuristic algorithms and representative HDBO methods in most test cases (Sec. 6.1 and Sec. 6.2
By investigating ATBO's three initialization strategies in terms AF maximization, we show that random initialization limits AFs' power by yielding lower AF values and larger posterior variances, leading to over- exploration, empirically confirming
hypothesis (Sec. 6.3);
We provide a detailed ablation study and hyper-parameterss analysis to understand the working mecha- nisms of AIBO (Sec. 6.4 and Sec. 6.6
6.1
Comparison with Baselines
6.1.1
Setup
We first compare ATBO to eight baselines: BO-grad, BO-es, BO-random, TuRBO, HeSBO, CMA-ES, GA and AIBO-none. We describe the baselines follows.
BO-grad, BO-es and BO-random respectively refer to the standard BO implementations using three AF maximizers: multi-start gradient-based, CMA-ES and random sampling. These standard BO implementa- tions use the same base settings as AIBO but with a random initialization scheme for AF maximization. To show the effectiveness of AIBO, BO-grad is allowed to perform more costly AF maximization; we set = 2000 and n = 10.
TuRBO Eriksson et al. 2019 HeSBO Nayebi et al. 2019) and Elastic BO Rana et al. 2017 are rep- resentive HDBO methods. We N 50 samples to obtain the initial dataset. Do for all three HDBO
8

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO (ours)
BO-grad BO-es
BO-random
HeSBO Elastic B0
CMA-ES
AIBO-none (ours)
TURBO
GA
(lower better)
Ackley100 (ewer better)
Ackiey300 betteri
16
16-
14
Black tuncsion
12.5
10
10.0
Black-box
7.5
0-
5.0
2.5
200
4.0
600
800
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number black-box function evaluations
Number blace-bxx function evaluatiion
Number of black-bxx function ovalcations
Rosenbrork20 (lower is better]
Roserbrack 10 (lower better)
Rosenbroce100 (lower is better)
100
202
Black-hoe furction
Black-boe furction
10*
Baack-oo firetion
20"
10*-
100
2.0m
1.00
10*
1.F
107
10²
10
104
100
200
400
800
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number black-bax function ovaluations
Number black-ox function evaltations
Number black function ovaluations
Rastrigan20 better)
Rastrgin100 better]]
Rastrign
2000
6000
Bock box hingla
35.0
300
1750
1500
Bacc-aos function
5000
250
1250
200
1000
2000
13.
750
2000
500
50
250
1000
200
400
600
900
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of black box funciion evalustions
Number of back-Box funccion evalustions
Number of black box function eve babons
Griewarke20 Dower &s better)
Griwank100 flower is better)
Criewane330 (lower is better)
tundion value
800
Badeboo fonction 1
8000
2000
500
6000
400
1500
5000
300
10000
200
3000
2000
100
1000
0
2000
600
800
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Wumber black box function evalusaions
Number black-bxx
Number of black Runction
RobotRush24 thigher better)
Reverto thigher better
HalfCheetah102 (higher bettert
3000
11.
2000
Reward
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
0
1000 2000
3000 4000 5000
Number of bbllckkkaa box function evaluations
Number of black-box function evailations
Number of black function evaluation
Figure 2: Results on both synthetic functions (lower is better) and real-world problems (higher is better). AIBO consistently improves BO-grad on all test cases and outperforms other competing baselines in most cases.
methods. For HeSBO, we use target dimension of 8 for the 14D robot pushing task, 20 for the 102D robot locomotion task and 100D or 300D synthetic functions, and 10 for other tasks. Other settings are default in the reference inplementations.
CMA-ES and GA are used to demonstrate the effectiveness of AF itself. Given that AIBO employs AF to further scarch the query point from the initial candidates generated by CMA-ES and GA black-box optimizers, if the AF is not sufficiently robust, the performance of AIBO might be inferior to CMA-ES/GA. For CMA-ES, the initial standard deviation is set to 0.2, and the rest. of the parameters defaulted in
9

---

Published in Transactions on Machine Learning Research (01/2024)
pycma (Hansen et al. 2022 For GA, the population size is set to 50, and the rest of the parameters are defaulted in pymoo (Blank& & Deb 2020
AIBO-none is a variant of AIBO. In each BO iteration, following the initialization of the AF maximization process, AlBO-none directly selects the point with the highest AF value while AIBO uses a gradient- based AF maximizer to further search points with higher AF values. This comparison aims to assess whether better AF maximization can improve performance.
6.1.2 Results
Fig 2 reports the full comparison results about the black-box function performance our method ATBO with various baselines on all the benchmarks. We use UCB1.96 (UCB with 3, = 1.96) as the default AF.
AIBO versus BO-grad While the performance varies across target functions, ATBO consistently im- proves BO-grad on all test cases. Espocially for synthetic functions which allow flexible dimensions, AIBO shows clear advantages in higher dimensions (100D and 300D). We also observe that BO-grad exhibits a similar convergence rate AIBO at the early search stage. This is because AF maximization is relatively casy to fulfil when the number of samples is small. However, as the scarch progresses, more samples can bring more local optimums to the AF, making the AF maximization process increasingly harder.
AIBO versus CMA-ES/GA As AIBO introduces CMA-ES and GA black-box optimizers to provide initial points for AF maximization, comparing AIBO with CMA-ES and GA will show whether the AF is good enough to make the AF maximization process find better points than the initial points provided by CMA-ES/GA initialization. Results show AIBO outperforms CMA-ES and GA in most cases except for the 20D Rastrigin function, where GA shows superior performance. However, in the next section, we will demonstrate that adjusting UCB's beta from 1.96 to 1 will enable AIBO lo maintain its performance advantage over GA. This suggests that with the appropriate choice of the AF, BO's model-based AF can offer a better mechanism for trading off exploration and exploitation compared to heuristic GA/CMA-ES algorithms.
AIBO versus other HDBO methods When compared to representative HDBO methods, including TuRBO, Elastic BO and HeSBO, AIBO performs the best in most cases except for the 20D Rastrigin function, for which TuRBO shows the fastest convergence. However, for higher dimensions (100D and 300D), AIBO performs better than TuRBO on this function.
AIBO versus AIBO-none Without the gradient-based AF optimizer, AlBO-none still shows worse performance than AIBO. This indicates that better AF maximization can improve the BO performance. This trend can also be observed in the results of standard BO with different AF maximizers, where BO-grad and BO-es outperform B0-random.
Overall, these experimental results highlight the importance of the AF maximization process for HDBO, as simply changing the initialization of the AF maximization process brings significant improvement.
6.2 Evaluation under Different AFs
We also evaluate the performance of ATBO and BO-grad under different AFs. Besides the default. AF setting UCB1.96 (UCB with 3 1.96), we also seleet UCB1 (3. = 1), UCB4 (3, = 4) and ET as the AF, respectively. This aims to provide insights into how well AIBO enhances BO-grad across different AF settings, shedding light on its robustness and effectiveness across diverse contexts.
Fig. shows comprehensive evaluation of the effectiveness of our AIBO method across various AFs. Changing the AF has a noticeable impact on performance, highlighting the importance of AF selection. If an inappropriate AF is used, such as using UCB4 in Rastrigin20, the performance improvements achieved through the use of AIBO remain highly limited. Despite that, the results we obtained are highly encouraging. While different AFs exhibit varying convergence rates, we consistently observe noteworthy enhancement in the performance of our method when compared to the standard BO-grad approach. The advantage is
10

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO -UC8199
AIBO-UCB4
80-grad-UCB1.96
80-grad-UCB4
AIBO-UCB1
AIBO-EI
80-grad-UCB1
80-grad-EI
Ackley20
17.5
17.5
14-
15.0
15.0
12.5
12.5
8
10.0
10.0
Slcckoor
Blackbor
7.5
5.0
5.0
0.0
200
600
1000
1000
4000
5000
1000
3000
4000
5000
Number black-nox function evalustions
Number of black-box functin mvsiuattonn
Nummber black-box function evalaations
ResenBrack20
Rosenbrock100
Rocenbradk300
Bartcboo funetion value
Blcckbbo fanction volue
10'
100
207
10/
10'
10a-
10t
20
Black boo tuncris
10"
10f
10
10*
107
10z
100
30*
104
200
400
600
800
1000
1000
2000
3000
4000
5000
2000
2000
2000
4000
5000
Number black box function eva luaiions
Number of black box function evolusaioons
Number of black box function evaluations
Rastrigin20
Rastrigin100
Rastrigin300
Bladedoo funcition value
2000
eudcooo function value
6000
350
1750
5000
300
15:00
250-
1250
200
1000
3000
150
750
1.00
500
250
1000
200
4.00
1000
1000
20000
3000
4000
5000
1000
2000
3000
4000
5000
Number black function evaluations
Number black function evaluations
Num
function evalustions
Griewank20
1400
Griewank100
Blackbox function value
5000
Griewank300 nk300
Grieea
800
1200
4000
Black box fundren
600
Blackbox functon
800
3000
400
600
200
400
1000
200
0-
0
200
400
600
800
1000
0
1000
2000
5000
4000
5000
1000
2000
3000
4000
5000
Number of black-bbx fanction evaluations
Number of black-box function evalvations
Num ber of black-box function evaluations
RobotPush14
HaltCheetah102
functinn 911 11.
Black-bo function valla
Black-box function value
10-
2000
1000
2 2
11000
-2000
5000
4000
4000
5000
Number black-box function evaiuations
Number blackbbaaoo function evallations
Number black-box function
Figure 3: Evaluating the performance of AIBO and BO-grad under different AFs on both synthetic functions (lower is better) and real-world problems (higher is better).
clearer higher dimensions (100D and 300D) than lower dimensions (20D). These findings highlight the robustness and effectiveness of our initialization method across different AFs.
6.3 Over-exploration of Random Initialization
The aforementioned experimental results have demonstrated that heuristic AF maximizer initialization in AIBO lcads to significant end-to-end BO performance improvements compared to random initialization. In this subsection, we evaluate AIBO's three initialization strategies in terms of AF values, GP posterior mean, and GP posterior variance under different AF settings.
11

---

Published in Transactions on Machine Learning Research (01/2024)
initialization
cmaes initialization
random initialization
g 5000
1000 Ackley 4 Withest AF value
5000
100D Ackley, #lowest mean
5000
1000 Ackle. #highest variance
3000
3000
3000
snighe
2000
1000
1000
1000
1000
2000
1000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Nblack box Runction evaluations
# Buackbox incllnnevlluatior
Zbladibox function evaluations
Rasenbrock: whighest
100D Rose Roserbrack: Alowest
1000 fasenbreck:
4000
4000
4000
3000
2000
2000
2000
1000
1000
1000
1000
2000
1000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Aunction evalluations
blackbox function evaluatiooss
#bladkbok function evaluations
5 5500
1000 Rastrigin: #highest AF value
5000
100D
Rastrigin: #lowest in con
5000
1000
Rastrigin: #highest veriance
3000
3000
3000
2000
2000
1000
1000
1000
0
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000 5000
Ablack box Aunction evaiuations
4 #tackbbox function evaluattoon
#bladkbox function evaluations
#ho Thgnest: 33
Griewank: shighest AF
100D Griwanik:
1000
Griewank #highest
4000
4000
4000
3000
2000
2000
2000
1000
1000
2000
4000
5000
1000
4000
4000
function evalusaions
evalusaions
#black
evaluations
(highess 1au
5000
140 Robotoush: #highest AF value
5000
140 Roboipush: #lowest mean
5000
14D Rebctpush: #highest veriance
2000
3000
3000
2000
1000
1000
1000
0
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
#black box Runction evaluations
#tack box innctionevalussse
#black box function evaluations
600 dhighest AF
60D
variance
phignert 8
4000
4000
4000
2000
2000
2000
1000
1000
1000
1000
2000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
#black Bunction evaluations
cvalussionn
#black evaluations
1020 HailCheeth:: #highest All value
1,2D HalfCheetah: elowest mean
1020 HallCheetah: #highest variance
5500
5000
5000
3000
3000
3000
2000
2000
1000
1000
1000
0
1000
2000
3000
4000 5000
0
1000 2000 3000
4000 5000
1000
2000 3000 4000 5000
Nblack box Runction evaiuations
#uack box wunctoon evalussions
#black box function evaluations
Figure 4: Evaluating AIBO's three initialization strategies in terms of AF values, GP posterior mean, and GP posterior variance when using UCB1.96 the AF. The left column shows the number of times each initialization achieves the highest AF value among all the three strategies throughout the search process. Similarly, the middle column and right column indicate instances of achieving the lowest postcrior mean (exploitation) and the highest posterior variance (exploration), respectively.
12

---

Published in Transactions on Machine Learning Research (01/2024)
initialization
cmaes initialization
random initialization
5000
1000 Ackley: thighest AF value
5000
1000 Ackley #lowest meen
55000
1000 Ackley: #highest varance
3000
3000
3000
2000
2000
2000
1000
1000
1000
1000
2000
3000
4000
5000
2000
3000
4000
2000
box function evalusaions
#black function evaluations
#black: function tvaluations
100D
Roseribrcck &highest AF value
1000
Basinbreck: Nlowest mein
100D Rasentrock: #highest variance
50000
4000
6000
4000
3000
2000
2000
2000
1000
1000
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000 5000
1000
2000
3000
4000
5000
#black box function evalustions
#black box function evaluations
#black box function tvaluations
hastrigin: Whighest valua
1000 Restrigin: mean
Rastrigin: #highest variance
5500
5000
5000
aF
3000
30.00
3000
2000
2000
2000
1000
1000
0
1000
3000
4000
5000
55000
1000 Griewank: #highwst AF valua
1000 Griewannc: louest mein
55000
1000 Griewank: #highest variance
4000
4000
4000
2000
2000
2000
1000
1000
1080
1000
2000
3000 4000
5000
1000
2000
3000
4000 5000
1000
2000
3000
4000 5000
#biack-bax function evalustions
#black-box funttion evaluations
#black-bax function evalustions
5000
140
Robotpush: #highest AP
5000
140
Robot dlowest mean
5500
Robatpush: @highest variance
3000
3000
3000
2000
2000
2000
0
2000
3000
4000
5000
3000 evalvations
@bisck-bax function evalustions
mblack evalustions
5000
600 Rover: Whighest AF value
60D Rover: llowest mean
60D Rover: #highest variance
4000
4000
4080
2000
2000
2000
1000
1000
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
#blcck function evalustions
#black box function evalvations
#black box function evalustions
HarCheetah: ahighest value
HaifChestah: menn
102D
HalfCheetah: atighest variance
5000
50000
5000
3000
3000
3000
2000
2000
1000
1000
1000
0
1000
2000
3000
4000
5000
2000 3000 4000
#black-box
evaluations
Figure 5: Evaluating AIBO's three initialization strategies in terms of AF values, GP posterior mean, and GP posterior variance when using UCB1 as the AF. The left column shows the number of times each initialization achieves the highest AF value among all the three strategies throughout the search process. Similarly, the middle column and right column indicate instances of achieving the lowest postcrior mean (exploitation) and the highest posterior variance (exploration), respectively.
13

---

Published in Transactions on Machine Learning Research (01/2024)
initialization
cmaes initialization
random initialization
5000
1000 Ackley: thighest AF value
5000
1000 Ackley #lowest meen
55000
1000 Ackley, #highest varance
3000
3000
3000
2000
2000
2000
1000
1000
1000
1000
2000
3000
4000
5000
2000
3000
4000
5000
2000
box function evalusaions
#black evaluations
#black: function tvaluations
100D
Roseribrcck &highest AF value
1000 Basinbreck: Nlowest mein
100D Rasentrock: #highest variance
50000
4000
6000
4000
3000
2000
2000
2000
1000
1000
1000
0
1000 2000
3000
4000
5000
1000
2000
3000
4000 5000
1000
2000
3000
4000
5000
#black box function evalustions
#black box function evaluations
#black box function tvaluations
hastrigin: Whighest valua
1000 Restrigin: mean
Rastrigin: #highest variance
5500
5000
5000
aF
3000
30.00
3000
2000
2000
2000
1000
1000
0
1000
2000
3000
4000
5000
2000
55000
1000 Griewank: #highwst AF valua
1000 Griewannc: lovest mein
55000
1000 Griewank: #highest variance
4000
4000
4000
2000
2000
2000
1000
1000
1080
1000
2000
3000 4000
5000
1000
2000
3000
4000 5000
1000
2000
3000
4000 5000
#biack-bax function evalustions
#black-box function evaluations
Dolack-bax function evalustions
5000
140
Robotpush: #highwst AP
5000
140
Robot dlowest mean
5500
Robatpush: @highest variance
3000
3000
3000
2000
2000
2000
0
2000
3000
4000
5000
3000 evalvations
@bisck-bax function evalustions
mblack evalustions
5000
600 Rover: Whighest AF value
60D Rover: llowest mean
60D Rover: #highest variance
4000
4000
4080
2000
2000
2000
1000
1000
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
@black function evalustions
#black box function evalvations
#black box function evalustions
HarCheetah: ahighest value
HaifChestah: mlnn
102D
HalfCheetah: atighest variance
5000
50000
5000
3000
3000
3000
2000
2000
1000
1000
1000
0
1000
2000
3000
4000
5000
2000
3000 4000
#block-box
evaluations
Figure 6: Evaluating AIBO's three initialization strategies in terms of AF values, GP posterior mean, and GP posterior variance when using El the AF. The left column shows the number of times each initialization achieves the highest AF value among all the three strategies throughout the search process. Similarly, the middle column and right column indicate instances of achieving the lowest postcrior mean (exploitation) and the highest posterior variance (exploration), respectively.
14

---

Published in Transactions on Machine Learning Research (01/2024)
In each iteration of AIBO, each initialization of yields candidate zi after AF maximization (Line 11 in Algorithm D. For each initialization, we count. the number of times zi achieves the highest. AF value among ( (.t:22) oi} until the current iteration. This number will show what initialization dominates the search process by yielding the highest AF value. Similarly, we also count the number of times 2 achioves the lowest GP posterior mean (exploitation) and highest. GP posterior variance (exploration) respectively. This will examine how different initialization schemes trade-off between exploration and exploitation.
The left column in Fig. 4 showss the number of times each initialization achieves the highest AF value among all the three strategies throughout the search process when using UCB1.96 (3, 1.96) as the AF. The middle and right columns indicate the number of times each initialization achieves the lowest posterior mcan (exploitation) and the highest posterior variance (exploration), respectively. Compared to CMA-ES/GA initialization, random initialization always yields lower AF values and higher posterior variance, leading to over-oxploration.
This over-exploration caused by random initialization not exclusive the UCB1.96 AF. As shown in Figs. 5 and [ when decreasing 3, from 1.96 to 1, or using El as the AF, random initialization still yields lower AF values and higher posterior variance. This is due to the curse of the dimensionality, Since the search space size grows much faster than sampling budgets as the dimensionality increases, most regions are likely to have a high posterior variance. Given that more samples can bring more local optimums to AFs as the search progresses, random initialization tends to guide the AF maximizer to find local optimums in regions of high posterior variance. Even if the AF designed to prioritize regions with lower GP posterior mean values for exploitation (e.g. UCB with a lower Be), these regions are sparse and may be inaccessible through random initialization. AIBO is designed to mitigate the drawback of random initialization, and the results presented here validate AIBO indeed achieves better AF maximization by optimizing the initialization phase.
6.4 Ablation Study
To better understand the role played by each initialization strategy in AIBO, we evaluate the three in- dividual initialization strategies in AIBO, leading to three variants of AIBO: AIBO ga, AIBO_ _mmass and AIBO random. We note that AIBO random is equivalent to BO-grad discussed earlier. Our fourth variant, AIBO gacma, removes the random initialization strategy in AIBO.
As shown in Fig. i advanced heuristic initialization strategics like GA and CMA-ES show better perfor- mance than random initialization in most cases, showing the advantage of heuristic algorithm over random initialization. Using a single advanced heuristic initialization, A1B0 ga and AIBO cmaes achieve similar performance to AIBO in most cases. This suggests that CMA-ES and GA can be the main source of per- formance improvement for AIBO. AIBO _acmaaaaaa shows similar performance to AIBO in all cases. This is because GA/CMA-FS initialization dominates ATBO's search process.
Besides, although AIBO emaes is competitive in most problems, it is ineffective for the 14D robot pushing problem, suggesting there is no cone-fits-fo--all heuristic across tasks. By incorporating multiple heuristics, the ensemble strategy used by ATBO gives a more robust performance than the individual components.
6.5 Comparison with Other Initialization Strategies
In previous experiments, we implemented random initialization by selecting the top-n points with the highest AF values as the initial points from a large set of random points. Some existing BÖ implementations have employed alternative initialization strategics. The impact of these methods has not been systematically evaluated. We conduct comparison of the following methods alongside AIBO: BO-emaes grad, BO- boltzmann grad and BO-Gaussian grad..
6.5.1 Setup
BO-cmacs goad uses CMA-ES optimize the AF to provide better initial points for further gradient-based AF maximization. We note that in this case, CMA-ES is used directly for AF optimization. In contrast, the 'CMA-ES" in AIBO is used to provide initial points by leveraging the history of black-box optimization.
15

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO
neB_rrndom (BO-grad)
AIBO ga
AIBO cmaes
AIBO AlBO_gacma
Adkley20
Ackiey100
Ackley300
Black-bxx function volue
16
144
10-
10
12-
12
8-
Black-box
6
4-
2
0
200
400
600
800
1000
0
1000
2000
2000
4000
5000
1000
2000
2000
4000
5000
Number black-box function evaliaations
Number black-bor finction
Number of k-box function evalisations
Rosenlbrack20
Nosenbrock100
Rasenbrack300
Burkbor funetion value
Blackboo function value
10'
Back function valuee
10F
105
20t
300
10x
10a
10f
10'
102
100
10*
10
100
200
400
800
1000
2000
2000
4000
5000
1000
2000
3000
4000
5000
Number black-box function wos lattion
Number blacksbox function evaluxttons
Number blacksbox function evituations
Rastrigin20
Rastrigin100
Rasttiign300
.400
eudk-bx function value
300
350
Buda-boo banction
15:0
1750
5000
4000
box
200
150
1000
750
3000
100
500
50
250
1000
200
400
600
8:0
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of black bax function evaluations
Number of black box function evaluations
Number ber of black box function evalustions
Griewark20
Griewank100
600
800
700
1400
12:00
Black-boxx function value
3000
3500
Blacketoo functoon
1000
500
400
8:0
2000
300
6:0
1500
200
400
100
2:0
500-
200
400
1000
1000
20000
3000
4000
5000
1000
2000
3000
4000
5000
Number black function evaluations
Number of black box foxtunction evaluations
Num
function evalustions
RobotPush14
Roverto
3000
HaltCheetah102
Black-boo function value
Bladkbox function value
2000
Black box fundion
9-
1000
8
0
1000
2000
3000
4000
5000
1000
2,000
3000
4000
5,00
-2000
0
1000
2000
3000
4000 5000
Number of black-box functtion evaluations
Number black-bax function evaluations
Number of blackbbxx function evaluations
Figure 7: Comparing AIBO to its variants AIBO gacma, AIBO ga, AIBO cinaes and AIBO random (BO-grad). While single advanced heuristic heuristic strategy CMA-ES/GA already performs well in most cases, using the ensemble strategy improves the robustness.
Comparing these two methods will reveal the importance of the black-box optimization history in the AF maximization process.
BO-boltzmann grad refers to the default implementation in Bo which uses Boltzmann sampling to generate initial points for the gradient-based AF maximization. In each BO iteration, it evaluates the AF on a large set of points and then uses an annealing heuristic (rather than top-n) to select the restart points.
BO-Gaussian graau uses a Gaussian spray around the incumbent best to generate initial points for the gradient- based AF maximizer. This initialization strategy has been used in Spearmint (Snock al. 2012). and we replace the AF maximizer with the advanced gradient-based method for fair comparison.
16

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO
BO B0-cmaes_ grad
BO- So0-bolzzman,,,ommm g_aad
BO- 400-Gausiian __raddgrra
Addley20
Acklsy100
Ackley300
1-4
Black-bux function volue
14
Blackebux functin
12
10:
Black
200
600
1000
1000
2000
2000
4000
5000
1000
3000
4000
5000
Number of black-box function ovaluations
Number of black-box function uatiors
Number of blackbox function ovaluations
ResenBrookk00
Rosenbrock100
Rosenbrod:300
Blacetex furctio volue
104
Blackbox function volue
Blaceboo furction value
10
100
102
20
1.0
2on
10f
10
200
207
20*
100
200
400
600
200
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number black: box function eve luations
Number biack-box function evalisations
Number of black box function evaluations
Rastrigin20
Rastrigin100
400
2000
Back-bor Bunctton value
350
tueeton
300-
Back-box finction
250
1250
200
1000
150
100
500
250
1000
200
400
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number black function
Number black function evMluaions
Num
function
600
Griewark20
Griewank100
8000
Criewarkk100
Siddkbar function value
2000
500
Block box on
1500
6000
300
1000
4000
200
3000
100
500
1000
0
200
400
600
800
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of bladk- box fanction evaluations
Number of black box function evaluation
Num ber of black-box function evaluations
3000
11
10-
2000
Roword
1000
-1000
-2000
Number functiinnnnooo evaluations
Number black-bor function evaluations
Number function
Comparing AIBO to standard BO with other AF initialization methods that do not use random search on both synthetic functions (lower is better) and real-world problems (higher is better).
Figure 8:
6.5.2 Results
Fig. presents the comparison result between AIBO and other initialization strategies. BO-cmaes grad and BO-boltzmann, grad exhibit significantly inferior performance compared to AIBO. Both approaches do not leverage prior black-box optimization history and instead attempt to optimize the AF in the global space directly to provide initial points for further gradicnt-basee AF optimization. This underscores the challenges of AF optinization in high-dinensional problems and the importance of utilizing the black-box optimization history. NO-Gaassian__gae takes into account the best points from the past black-bon optimization history as a basis for maximizing the AF. This approach performs well in some cases (c.g., Rastrigin but may lead significant performance drop in other situations (e.g., Robotpush14) due over-exploitation. Overall, ATBO exhibits significantly better performance compared to these non-random initialization strategies.
17

---

Published in Transactions on Machine Learning Research (01/2024)
Ackley300
AcclyyD0
Actloy100
144
botch stee
Biecooler fuweitee
G4 popsize-100, EM6-55 e=
GA popsiae-0, CRMES pm D.2
k=1000, fw10
Bock Aundtion
12
30
1000
2000
3000
4000
5000
1000
2000
5000
4.00
5000
Number blecbbax Lunction ersliations
Namber bleceobca funetam mod custint
Number black-box funccion valuition
Rosenbrock100
Reseebrookko0
0300 100.bo funcdin value
popdic=550 CMA
307
k=100,
Sh00-bor Larciin vilue
100
batch sic-5
G4 p100 CM-E5 05
201
200
batch siam10 10
24 popeize 26, CMME5 pm 0.3
203
kn 1000 1=10
4.0
batch sizen
20*
207
102
1.10P
5
1000
2000 3000
4000 5000
1000
2000 3000
4000
5000
1000
2000
3000
4000
5000
Number of black box fundtion eralustinn
Number back-box ox fancioon evaluations
Number of black box fundtion ovaluations
Restrigi100
Restrightt Do
Bestrigin100
2000
2000
2000
54 papsine---0 50, CM-ES o- 02
3 11550
k=100, n-1
17750
hetrh sime
1500
1250
24 p00 EMA-15 e- 3.5
04 p0. CMAES gm
1500
1250
k-1000 10
k-000 n-1
Bbackbor 8
11500
1250
batchh 52c-10
betch sume
1500
3000
10000
750
750
750
250
250
0
1000
2000
3000
4030
5000
1000
2000
3300
4000
5000
0
1000
2000
5000
4000
5000
Numbber of black-bos funciion walkaiion
Number ol biblllkkoor function oralustionn
Number blaci-boo funciion wnluutions
Griewank100
Griswank100
Griewark100
G4 G4popsiee-55 50, CMNES g=
stace lunutionn value
k=100, n=]
Bockbbo funcctontioonnn valu
2000
batch 5ize
24 popdze-100, EMM-55 um 0.5
k=1000, n-1
batch sto-10
Norcbox funchen
G4 p00pizz-22..0c o-
1500
k- 1000 n 10
15000
betrh siw--5 50
1.000-
3000
10000
500
303
5.0
1000
2000
4000
1000
3000
5000
1000
2000
3000
4000
Numbbr of bludk box function soluctions
Numbcr of bbakk box function exclustions
Numbor of back box function collations
RobotPush14
Rob:1Fush14
RobotPushh4
11
Back-bo Biriecoo fondlor
300
9
BbxC 20x Tunctes
popazz-500 CMA 02
k-100, n=1
betch siw-5
G4 -1p CMA E5 05
k=1050 n=1
batch sbc-10 10
G4 popszz--2. 0.
k=1000, 10
batch 500
3000 Number backebrx function evaliations
4200 Number bisceebox function evaluations
1000
Number blackebox function evaluations
Rover60
Rover60
RoverE0
Slack-boo function value
Blackibow function value
popsicem50 ENA-E3 e- D22
k=100, n=1
batch siz-5
G4 papsiteee10, 100, CMM-5 am 0.5
1000
betch sie- 10
20, CMG-E5 e- D.2
k=1000,
1=10
batch 500-50
3000 evaluations
4000
5000
2000
Number of
Number box function evaluations
Number function evaluations
In#rChetah102
HalfCheethh102
HaFChhetahi.22
Bludk box fanction value
3020
Block box fondonnn
3000
-1000
GA 1005 OMA ES ow 0,5
GA 50gsiz=-50, CMA ES 022
-1000
km100
k=1000,
-1000
batch sizem batch sbeu
2000
popsizen20, gm0.1
-2000
-2000
1300 2008 30000 4000
3000
3000
2000
1000
4000
5000
1000
2000
3000 4000 5000
Figure 9: The impact of hyper- paree-parseeters on AIBO, The left column shows the impact of GA population size and CMA-ES initial standard deviation a. The middle column reports the impact of the number of raw candidates generated from heuristics k and the number of selected initial points n. The right column shows the impact of the batch size.
18

---

Published in Transactions on Machine Learning Research (01/2024)
Table 2: Algorithmic runtime
Synthetic
RobotPush
Rover
HalfCheetah
Dimensions
20
100
300
14
60
102
#Samples
1000
5000
5000
5000
5000
5000
AIBO
min
2.5 h
3.6
1.8 h
h
2.5
BO-grad
12 min
3.3 h
5
2.5 h
h
4
6.6 Evaluation under Different Syper-Parameters
Multiple hyper-parameters in AIBO, including GA population size, CMA-ES initial standard deviation the number of raw candidates generated from heuristics k, the number of selected initial points and the batch size could impact its performance.
GA pop size and CMA-ES a As ATBO employ heuristics to initialize the AF maximization process, these heuristies' hyper-parameters control the quality of initial points of the AF maximization process and affect the trade-off between exploration and exploitation. A larger GA population size and larger CMA-ES initial standard deviation will encourage more exploration. As shown in the left column of Fig. different tasks favour different tradc-offs. A more exploratory sctting (popsize=100 and = 0.5) works well for the HallCheetah102 task but reduces the performance on Ackley 100. Our experiments suggest opting for a GA population size between 20 and 100 and selecting the CMA- initial a value within the range of 0,2 to 0.5.
k and n Based on Algorithm D increasing the number of raw candidates generated from heuristics k and the number of selected initial points might help AF maximization but requires more calculation. However, as shown in the middle column of Fig. increasing & and n does not yield significant performance improvement in most cases except for the Rover60 task. We recommend setting k to 100 ~ 1000 and setting n to ~ 10.
Batch size As shown the right column of Fig. g AIBO performs well across different batch sizes, and reducing the batch size can slightly enhance convergence speed in all cases.
6.7 Algorithmic Runtime
In Table we provide the algorithmic running time (exchuding the time spent evaluating the objective function) for our method with a batch size of 10, For comparison, we also show the algorithmic runtime of BO-grad. The experiments are run on an NVIDIA RTX 3090 GPU equipped with a 20-core Intel Xcon Gold 5218R CPU Processor. As described in Sec 6.1.1 to show the effectiveness of AIBO, BO-grad is allowed to perform more costly AF maximization. AIBO uses less algorithmic runtime because it costs less AF maximization time than the standard BO-grad method. AIBO's algorithmic runtime is also acceptable for actual expensive black-box optimization tasks (only several hours for a few thousand evaluations).
7 Conclusion and Future Work
We have presented large-scale empirical study to understand the impact of the acquisition function (AF) maximizer initialization process when applying Bayesian optimization (BO) for high-dimensional problems. Our extensive experiments show that the AF maximizer initialization can greatly impact the realization of the AF, and the widely random initialization strategy may fail to unlock the potential of an AF.
We then propose AIBO, a framework to optimize the initialization phase AF maximization BO. AIBO is designed overcome the limitation of the random initialization technique for high-dimensional BO. AIBO employs a simple yet effective optimization strategy. It employs multiple heuristic optimizers generate the raw samples for the acquisition function maximizer to better trade-off exploration and exploitation.
19

---

Published in Transactions on Machine Learning Research (01/2024)
We evaluate AIBO by applying it to syuthetic test functions, robot control, and planning tasks. Experimental results show that ATBO can significantly boost the standard BO's performance in high-dimensional problems and outperform prior high-dimensional BО techniques.
Previous theoretical studies on the convergence of BO methods have largely relied on a fundamental as- sumption that. the AF could be globally optimized. While this assumption may hold in low-dimensional tasks, our large-scale empirical study suggests that this assumption could be violated in high-dimensional problems. We show that how the AF is optimized plays crucial role in determining the overall efficacy of the BO method. Our future work will examine the theoretical underpinnings governing BO convergence when AF maximization is suboptimal. We hope this study, with extensive empirical evidence, can promote more research in high-dimensional BO by jointly optimizing the AF and the process of maximizing the AF.
Acknowledgments
This work supported in part by the UK Engineering and Physical Sciences Research Council (EP- SRC) under grant agrecment EP/ EP/X018202/1. For any correspondence, please contact Zheng Wang (Email: z. ..wang5leeds.cc.uk))
References
Tanweer Alam, Shamimul Qamar, Amit Dixit, and Mohamed Benaida. Genetic algorithm: Reviews, imple- mentations, and applications. International Journal of Engineering Pedagogy, 2020.
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wilson, and Eytan Bakshy. Botorch: framework for efficient monto-carlo bayesian optimization. Advances in neural information processing syslems, 33:21524 21538, 2020.
Thomas Beies-nei, Christian WG Lasarezyk, and Mike Preuß. Sequential parameter optimization. In 2005 IEEE congress evolutionary computation, volume 1, pp. 773 780. IEEE, 2005.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for mization. Advances in neural information processing systems, 24, 2011.
opti-
Mickaël Binois, David Ginsbourger, and Olivier Roustant. On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of global oplimization, 76(1):69 90, 2020.
J. Blank and K. Deb. pymoo: Multi-objective optimization in python. IEEE Access, 8:89497 89509, 2020.
Alexander I Cowen-Rivers, Wenlong Lyu, Zhi Wang, Rasul Tutunov, Hao Jianye, Jun Wang, and Haitham Bou Ammar. Hebo: Heteroscedastic evolutionary bayesian optimisation. arXiv e-prints, pp. arXiv-2012, 2020.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian oplimization. Advances in Newral Information Processing Systems, 32, 2019.
Jacob Gardner, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse, Discovering and exploit- ing additive structure for bayesian optimization. In Artificial Intelligence and Statistics, pp. 1311-1319. PMLR, 2017.
Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson. Gpylorch: Blackbox matrix- matrix-matrix gaussian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018.
Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos. Roducing the time complexity of the deran- domized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computation, 11(1): 1-18, 2003.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Nikolaus Hansen, yoshihikoueno, ARF1, Kento Nozawa, Luca Rolshoven, Matthew Chan, Youhci Akimoto, brieglhostis, and Dimo Brockhoff. pycma: r3.2.2, March 2022. /00pp////oo..rr//000522//oooo 5281//eeooo.
6370326 https://doi.org: wtt..o/0/1...///eeoeee.e 637.0/00...3332666 6370326
Tim Hcad, Manoj Kumar, Holger Nahrstacdt, Gilles Louppe, and Iaroslav Shcherbatyi. scikit-
aplimizze/cikiiiopliiiiee, October 2021. https::/dbi.org// 5281/ 5565057
José Miguel Hernández-Lobato James Requeima, Edward O
and Alán Aspuru-Guzik. Par- allel and distributed thompson sampling for large-scale accelerated exploration of chemical space. Tn International conference on machine learning, pp. 1470 1479. PMLR, 2017.
Frank Hutter, Holger H Hoos, Kevin Leyton-Brown, and Kevin P Murphy. An experimental investigation of model-based parameter oplimisation: Spo and beyond. In Proceedings of the 11th Anruual conference on Genetic and evolutionory computation, pp. 271 271-278, 2009.
Frank Hutter, Holger H Hoos, Kevin Leyton- Brown, and Kevin Murphy. Time-bounded sequential parameter optimization. In International Conference on Learning and Intelligent Optimization, pp. 281-298. Springer, 2010.
Frank Hutter, Holger H Hoos, and Kevin Leyton- Leyton-Brown. Brown. Sequential model-based optimization for general algorithm configuration. In International conference on learning and intelligent optimization, pp. 507-523. Springer, 2011.
Donald R Jones, Cary D Perttunen, and Bruce Stuckman. Lipschitzian optimization without the lipschitz constant. Journal of oplimization Theory and Applications, 79:157-181, 1993.
Kirthevasan Kandasamy, Jeff Schneider, and Barnabás Póezos. High dimensional bayesian optimisation and bandits via additive modcls. In International conference on machine learning, pp. 295-304. PMLR, 2015.
Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christopher R Collins, Jell Schneider, Barnabas Poczos, and Eric P Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. J. Mach. Learn. Res., 21(81):1-2) 2020.
Johannes Kirschner, Mojmir Mutny, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adaptive and safe bayesian optimization in high dimensions via one-dimensional subspaces. In International Conference on Machine Learning, pp. 3429 3438. PMLR, 2019.
Aaron Klein, Stefan Falkner, Numair Mansur, and Frank Hutter. Robo: A flexible and robust bayesian optimization framework in python. In NIPS 2017 Bayesian optimization workshop, pp. 70, 2017.
Nicolas Knudde, Joachim van der Herten, Tom Dhaene, and Ivo Couckuyt. Gpflowopt: A bayesian opti- mization library using tensorflow. arXiv preprint 17X:::1711.03845, 2017a.
Nicolas Knudde, Joachim van der Herten, Tom Dhaene, and Ivo Couckuyt. Gpflowopt: bayesian opti- mization library using tensorflow. arXio preprint N7111111.09844 2017b.
Ben Letham, Roberto Calandra, Akshara Rai, and Eytan Bakshy. Re-examining linear embeddings for high- dimensional bayosian optimization. Advances in neural information processing systems, 33:1546-1558, 2020.
Cheng Li, Sunil Gupla, Santu Rana, Vu Nguyen, Svetha Venkatesh, and Alistair Shilton. High dimensional bayesian optimization using dropout. arXiv preprint arXiv:1802.054// 2018.
Daniel J Lizotte, Tao Wang, Michael H Bowling, Dale Schuurmans, et al. Automatic gait optimization with gaussian process regression. In IJCAI, volume 7, pp. 944 949, 2007.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides a competitive approach reinforcement learning. Xiv preprint or Xiv: 883.8003000000 2018.
21

---

Published in Transactions on Machine Learning Research (01/2024)
Ruben Carrinez-Canttnn Nando De Freitas, Eric Brochu, José Castellanos, and Arnaud Doucet. A bayesian exploration-exxloitaaioo approach for optimal online sensing and planning with visually guided mobile robot. Autonomous Robots, (7(2):93 103, 2009.
Henry B Moss, David S Leslie, Javier Gonzalez, and Paul Rayson. Gibbon: General-purpose information- based bayesian optimisation. Journal of Machine Learning Research, 22(235):1-49, 2021.
Amin Nayebi, Alexander Munteanu, and Matthias Poloczek. A framework for bayesian optimization in embedded subspaces. In International Conference on Machine Learning, pp. 4752-4761, PMLR, 2019.
ChangYong Oh, Efstratios Gavves, and Max Welling. Bock: Bayesian optimization with cylindrical kernels. In International Conference on Machine Learning, pp.
PMLR, 2018.
Victor Picheny, Joel Berkeley, Henry B Moss, Hrvoje Stojic, Uri Granta, Sebastian W Ober, Artem Artemev, Khurram Ghani, Alexander Goodall, Andrei Paleyes, et al. Trieste: Efficiently exploring the depths of black-box functions with tensorflow. arXie preprint wxXi:2230..84436 2023.
Hong Qian, Yi-Qi Hu, and Yang Yu. Derivative-free optimization of high-dimensional non-convex functions by sequential random embeddings. In IJCAI, pp. 1946 1952, 2016.
Santu Rana, Cheng Li, Sunil Gupta, Vu Nguyen, and Svetha Venkatesh. High dimensional bayesian opti- mization with clastic gaussian process. In International conference on machine learning, pp. 2883-2891. PMLR, 2017.
Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. High-dimensional bayesian optimiza- tion via additive models with overlapping groups In International conference on artificial intelligence and statistics, pp. 298-307 PMLR, 2018.
Matthias Seeger. Gaussian processes for machine learning, International journal of neural systems, 14(02): 69-106, 2004.
Kenan Schic, Alexandre Gramfort, Joseph Salmon, and Luigi Nardi. Lassobench: high-dimensionall hyperparameter optimization benchmark suite for lasso. arXiv preprint arXic:2111.02790 2021.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Jasper Snoek, Kevin Swersky, Rich Zemel, and Ryan Adams. Input warping for bayesian optimization of non-stationary functions. In International Conference on Machine Learning, pp. 1674 1682. PMLR, 2014.
Niranjan Srinivas, Andreas Kranse, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.399) 2009.
The GPyOpt authors GPyOpt: A bayesian optimization framework in python. http://github. com/
SheffieldMLGGPyOpt 2016.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 TEEE/RS) international conference on intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient bayesian optimization. In International Conference on Machine Learning, pp. 3627-3635. PMLR, 2017.
Zi Wang, Chengtao Li, Stefanie Jegelka, and Pushmeet Kohli. Batched high-dimensional bayesian opti- mization via structural kernel learning. In International Conference on Machine Learning, pp. 3656-3664. PMLR, 2017.
Zi Wang, Clement Gehring, Pushmect Kohli, and Stefanic Jegelka. Batched large-scale bayesian optimization in high-dimensional spaces. In International Conference on Artificial Intelligence and Statistics, pp. 745- 754. PMT.R, 2018.
22

---

Published in Transactions on Machine Learning Research (01/2024)
Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, Nando De Freitas, et al. Bayesian optimization in high dimensions via random embeddings. In IJCAT, pp. 1778-1784. Citeseer, 2013.
James Wilson, Frank Hutter, and Mare Deisenroth. Maximizing acquisition functions for bayesian optimiza- tion. Advances in neural information processing systems, 31, 2018.
Jian Wu and Peter Frazier. The parallel knowledge gradient method for batch bayesian optimization. Ad- vances in neural information processing systems, 29, 2016.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench-
101: Towards reproducible neural architecture search. In International conference on machine learning, pp. 7105 7114. PMLR, 2019.
23

---

Published in Transactions on Machine Learning Research (01/2024)
A Appendix
A.1 The case of over-exploitation
shohow AIBO's random initialization can help alleviate the over-exploitation issue, we create a variant of our _gacma, by removing random initialization. Using default hyperparameters, AIBO AIBO_gacmaa gaamm
technique, AIBO_gacma, performs well in the RobotPush14 optimization task. However, after adjusting the hyperparameterrs an over-exploitation case by setting GA population size 3 and CMA-ES initial standard deviation performs less effectively. Upon reintroducing random initialization,
0.01, observe that observed significant performance improvement, suggesting that random initialization could help mitigate over-exploitation.
AIBO gacma (popsize=3, CMA-ES a= 0.01)
AIBO (popsize=3, CMA-ES o= 0.01)
AIBO _acmaaaaaaaaa (popsize=50, CMA-ES a= 0.2)
AIBO (popsize=50, CMA-ES a= 0.2)
RobotPush14
Black-box function value
10
9
8
7
5
1000
2000
3000
4000
5000
Number of black-box function evaluations
Figure 10: Comparision of AIBO and AIBO
gacma under a standard hyperparameter setting and over- exploilative setting. Results show that random initialization could help miligate over-exploitation.
A.2 Details of GA and CMA-ES in AIBO
In this section, we explain how GA and CMA-ES optimizers in ATBO initialized (Line 3 in Algorithm updated (Line 16 in Algorithu D and asked to generate candidates (Line 8 in Algorithm [ We use the implementations in pyema and pymoo for the CMA-ES and the GA strategies, respectively.
Initialization of GA At the beginning of the search process in AIBO, we will draw N samples uniformly and evaluate them produce GA's initial population.
Candidate generation of GA To generate new candidates, GA will sequentially perform selection, crossover and mutation operations. The selection operation aims to select individuals from the current population of GA to participate in mating (crossover and mutation). The crossover operation combines parents into one several offspring. Finally, the mutation operation generates the final candidates based on the offspring created through the crossover. It helps increase the diversity in the population. The selection, crossover and mutation operations used in AIBO are shown as follows.
Tournament Selection: It involves randomly picking T individuals from the population, comparing their fitness, and selecting the individual with the highest fitness. This process is repeated to fill the new generation. We use the default sctting of pymoo. i.c., 2.
Simulated Binary Crossover (SBX): This is a widely used crossover technique. binary notation can represent real values, and then point crossovers can be performed. SBX simulated this operation by using an exponential probability distribution simulating the binary crossover. For this operation, also the default. SBX implementation of pymoo where the crossover probability is set to 0.5.
24

---

Published in Transactions on Machine Learning Research (01/2024)
Polynomial Mutation: This mutation follows the same probability distribution the simulated binary crossover to introduce small, random changes to individuals in the population to maintain genetic diversity. We use the default polynomial mutation implementation of pymoo where the mutation probability is set to 0.9.
Update of GA We update the population of GA using the most recently evaluated samples in AIBO, Here, sort the samples based their fitness (black-box function value), ultimately retaining those with superior fitness.
Initialization of CMA-ES The key of CMA-ES is multivariate normal distribution M(m,, of which is initialized at the beginning of the search process in AIBO. In particular, we will draw N samples uniformly and evaluate them. The coordinates of the sample with the best black-box function value will used as the imitial mean vector ma. The step size σg is initialized to a constant op = 0.2, and the covariance matrix Ck is initialized as an identity matrix Co I.
Candidate generation of CMA-ES At each iteration k CMA-ES generates candidates by sampling from its current multivariate normal distribution, i.e.,
3; N(ma, C.r) my + oh NO Ck)
(2)
Update of CMA-ES The update of CMA-ES involves updating the multivariate normal distribution N(m,, Cx). Assuming the batch size of AIBO is X, the samples are evaluated on the objective function f to be minimized. The only feedback from the objective function here is ordering the sampled candidato solutions due to the indices i Denoting the f-sorted candidate solutions as
faua | = li. AJ (a, i 1....... A} and ((x1)) S.......... .... ((EE)) (( s...,
the new mean value is computed
m
Wi TisA
1=1
m2
+
Wi (I+: mp)
i=1
where the positive (recombination) weights w/ 2 W2 2 ... 2 wp > O sum to one. Typically, μ S A/2 and the weights are chosen such that Mu == 1/ ビ w/ ~ A/4.
The step-size σ is updated using "cumulative step-size adaptation" (CSA), sometimes also denoted "path length control". The evolution path (or search path) Pa is updated first.
complements for discounted variance
displacement of m
Po + (1- Co
Po +
V1 (1 )2
Vhu C5 Mg+1 m
discount factor
distributed as Ni(o.) under neutral selection
Co do
lp E (O,
-1)
Tkt1 03 X exp
uubiased about under neutral selection/
where
25

---

Published in Transactions on Machine Learning Research (01/2024)
O n// is the backward time horizon for the evolution path Po and larger than one (co 1 is reminiscent of an exponential decay constant as (1 -a) x exp(-cak) where of is the associated lifetime and In(2 ~ 0.7cp the half-life),
Ne = (_ w?) -1 is the variance effective selection mass and 1 S Phu S μ by definition of ws
C - V = ca is the unique symmetric square root the inverse of Ck. and
d, is the damping parameter usually close to For d, Co 0, the step size remains unchanged.
The step size d% is increased if and only if I|-ll is larger than the expected value
E El 1)11 v2r
n
+
/T
Vn
1
4n
21n
and decreased if it is smaller. For this reason, the step-size update tends to make consecutive steps Cg conjugate, in that after the adaptation has been successful
ML42- (
C m = 0.
Øk11
Finally, the covariance matrix is updated, where again, the respective evolution path updated first.
Pe + (1 - ce)pe + (
cc) k
/
m
Ok
Ck+1 - cp c.)Ck capete + Cp Σ
Tid mi
Ti:A
Tk
Okk
where 7' denotes the transpose and
n/4 4 is the backward time horizon for the evolution path Pe and larger than one,
1.5 and the indicator function 1 (Iaa) evaluates one iff || E [0, av or, in other words, || S ayn, which is usually the case,
(1-1 -1=1 c1c=) (2-cc) makes partly up for the small variance loss in case the indicator is zero,
~ 2/n² is the learning rate for the rank-one update of the covariance matrix and
Cn pw/n" is the learning rate for the rank-j update of the covariance matrix and must not exceed c1c
A.3 Additional real-world benchmarks
Here we provide two additional real-world benchmarks Lasso-DNA (Schić et al., 2021 and Nasbench YYngg et al. 2019), to improve the claim for the real-world performance of our method. The Lasso-DNA task minimizes the mean squared error (MSE) of weighted Lasso sparse regression for real-world DNA datascts by tuning 180 parameters. The Nasbench task is to design a neural architecture cell topology defined a DAG with nodes and up to 9 edges to maximize the CIFAR-10 test-set accuracy, subject to constraint where the training time was less than 30 minutes. We follow the parameterization approach used by Letham et al. 2020) to make the Nasbench task become a 36-dimensional black-box function.
For Lasso-DNA, AIBO still significantly outperforms BO-grad. For Nasbench- 101, AIBO only shows a modestly improved performance compared BO-grad. This is because the search space size of Nasbench- 101 is small (only 423,624 samples). For such a small search space size, AF maximization is no longer a challenge.
26

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO (ours)
BO-grad
BO-random
HeSBO
CMA-ES
AIBO-none (ours)
B0-es
TURBO
Elastic BO
GA
lasso-DNA DNA (lower is better)
lasso-
Nasbench (higher is better)
Black-box function value
0.35
Black-box function value
0.940
0.34
0.938
0.33
0.936
0.32
0.934
0.31
0.932
0.930
0.30
0.928
0.29
0.926
0.28
0
1000
2000
3000
4000
5000
25
50
75
100
125
150 175 200
Number black-box function evaluations
Number of black-box function evaluations
Figure 11: Results on two additional real-world problems Lasso-DNA and NasBench.
A.4 Comparision with DIRECT initialization
As the DIRECT (Jones et al. 1993 we also use it to optimize the AF for generating initial points for further gradient-based optimizers. The corresponding BO method is denoted as BO-DIRECT grad. We compare BO-DIRECT grad with ATBO AIBO outperforms BO-DIRECT grad in all cases, and the
algorithm is widely used for the acquisition function optimization,
in all the benchmarks. As shown in Fig. 12
performance gap is notable in most cases.
A.5 Monte Carlo acquisition function
Here, we provide details about how Monte Carlo acquisition functions are calculated. Many common acqui- sition functions can be expressed the expectation of some real-valued function of the model output(s) the design point(s):
o(X)= =[(((S) 1 (((((X))
where X (x1, (,i. Rg), and P(f(X) D) is the posterior distribution of the function f at X given the data D observed so far.
Evaluating the acquisition function thus requires evaluating an integral over the posterior distribution. In most cases, this analytically intractable. In particular, analytic expressions generally do not cxist for batch acquisition functions that consider multiple design points jointly (i.e. q > 1).
An alternative is use (quasi-) Monte- Carlo sampling to approximate the integrals. An Monte- Morlo Carlo (MC) approximation of a at X using N MC samples is
1 ((X) R N
Σ a(t)
where& & P(f(X) D).
For instance, for MC-estimated Expected Improvement, have:
(E
max - il.....
& &(P(((
where f is the best function value observed so far (assuming noiseless observations).
27

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO
BO-DIRECT __rddd
Arkley20
Ackiey1 o0
Ackley 900
Bardeboor function value
Blad-boo function value
1.4
Book box funelce
12-
12
10
10
4
0
200
400
600
800
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of black function evaluations
Number of black box function ova uatirrs
Number of black function evaluations
Rodertereck0
Roserbrock100
Rosenbrack300
Baddekox fonction valum
10a
103
Bladctoo function
10t
Backbor function
3.07
10
1.00
1or
100
104
207
202
10*
200
800
1000
1000
2000
1000
6000
5000
1000
2000
3000
5000
function ova
blackboxx function ovaluations
function evaluations
Rastrigin0o
Rastrigin100
Rastrigin300
-400
Bladebbx fundiio vale
350
tundtoo
300
Blackebxx fanction
15:00
250
1250
200
150
750
100
500
250
200
400
600
800
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number black-bak function evaluations
Number of black-bxx function evaltations
Number blark-box function evaluntions
800
Griewark20
Gricwank100
8000
Griewa nk300
500
Black-bux flnntion valuue
2000
7000
6000
functon
1500
5000
300
200
3000
1000
5.0
1000
200
400
600
800
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
black-bak function evaluationn
Number black-bax function ecaluations
Nur
black-bax
RobetPush14
RovereO
HaifChsetah102
11
Reward
Reward
1.000
-1000
2000
3000
5000
2000 3000
5000
1000
2000
4000 5000
Number black-nox funciion aaaluations
Number of black-bax function evalisations
Number black-box function evaluationn
Figure 12: Comparing AIBO to BO-DIRECT grad. AIBO outperforms BO-DIRECT grad in all cases.
Using the reparameterization trick (Wilson et al. 2018).
qEI(X)
Σ max (max(p(X) j (I(X)e) j-1",0)} a~, jl.....
where u(X) the posterior mean of f at X, and L(X)L(X)* Σ(X) is root decomposition of the posterior covariance matrix.
28

---

Published in Transactions on Machine Learning Research (01/2024)
AIBO (batch_size=1)
BO-grad
Adkiey22 (owwr better)
Ackrey10 (lower is betteri
Ackity200 (owwr is better)
12-
12.5
Blackbbx Sunction
12
10
10.0
a-
7.5
8
Blick-box
0
200
400
600
800
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of black-box funciion avalustions
Number of black-box function evaluations
Number of biac E-box function avalustions
200
Rosenbrock20 (lower is betterl
10f
Rcsembrack1 DO (lower is better)
Backsoox turctton vatue
Rasenbrock300 (lwer is betteri
Baccklo function
20*
function
10f
10"
101-
10
2.0
:00
10'
107
107
102
10
104
107
102
200
400
600
800
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number b back box function evaluations
Number of black box function evaluations
Number black box function Evaluations
Rastrigin00 (lower better)
Rastrigin000 llower better)
Rastrigin000 (lower better)
box functonn sake
.000
2000
1750
300
350
1500
Black-box functio
5000
25.0
1250
200
1000
2000
15.0
Blacksbo
750
100
500
2000
250
1000
800
1000
1000
2000
3000
4000
5000
10000
2000
30:00
4,00
5000
black box function evaluations
Number function evalustions
Number black function lattons
Criewarli20 Dower is better)
Criewank100 100 flower is better)
Griewank300 (lower is better)
tungsson value
600
8000
500
7000
Black function
6000
400
1550
5000
200
1000
100
200
500
bos
2000
1000
3000
200
400
600
800
1000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Numbbe black-bax function avaluations
Number of black-hox function evaluations
Number of black-bor function bations.
RobotFush24
Revergo (higher
HaifCheetah102 Ohigher bettert
3000
11
2000
Reward
1000
1000 2000
2000
4000
5000
1000 2000
2000
4000 5000
0
1000
2000
3000 4000 5000
Number blacksbox function ecaluations
Number blackebox function evaliations
Numbbrr black-box function evaluations
Figure 13: Evaluating AIBO and BO-grad on analytical UCB AF with 3, = 1.96. We set the batch size Lo to support the analytical AF, AIBO still outperforms BO-grad in all cases.
A.6
Evaluations on analytical acquisition functions
To evaluate method analytical AFs (unsuitable for batch BO), we set the batch size to 1. As shown in Fig. B Using analytical UCB AF B 1.96, AIBO still outperforms BO-grad in all cases.
A.7
The impact of Acquisition Function on the diversity of GA population
Our heuristic initialization process is AF-related, as it depends on past samples selected by the given AF, Usually, a more explorative AF setting will make the heuristic initialization in AIBO also more explorative.
29

---

Published in Transactions on Machine Learning Research (01/2024)
For instance, if the AF formula leans towards exploration in GA, the GA population composed of samples chosen by this AF will have greater diversity, generating more diverse raw candidates.
To illustrate this point. We select two different AF settings: UCB1.96 (3, = 1.96), and UCB9 (3, 9, more exploratory). When applying AIBO to Ackley100, we calculate the average distance between individuals the GA population at each BO iteration, which
good measure of the population diversity. We repeated this experiment 50 times. As shown in Fig. [4 AIBÒ with UCB9 achieves more diverse GA populations than AIBO with UCB 1.96, suggesting that more explorative AF setting will make GA initialization more explorative.
Ackley100
Average distance of GA pop
(higher means more diverse GA population)
AIBO-UCB1.96
AIBO-UCB9
109
10-1
1000
2000
3000
4000 5000
Number of black-box function evaluations
Figure 14: Evaluating the average distance between individuals in the GA population when applying AIBO- UCB1.96 and AIBO-UCB9 (more exploratory) to the Ackley100 function. With the same number of BO iterations, AIBO-UCB9 always owns a more diverse GA population than AIBO-UCBI.96 suggesting that a more exploratory AF setting will make the GA initialization in AIBO also more exploratory.
30


Reviews:
[{"review_id": "XHk9k1foWc", "reviewer": "Reviewer_GeKQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S: As mentioned in the paper, the topic has not been widely studied, and may have potential importance for practical performance of BO. \n\nS: Comprehensive experimental evaluation is performed.\n\nW: Justification of the proposed method is not fully clear to me.\n\nW: Some related work should be mentioned.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers initial value settings of the acquisition function maximization in Bayesian optimization (BO). The basic idea is to use multiple heuristic optimizer such as CMAES and GA and optimize the acquisition function from each of generated initial values. The performance is evaluated several functions with a variety of settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Justification of the tuning strategy of heuristic optimizers using past data should be clarified. For example, in the case of covariance of CMAES, the directions that has never been explored may have zero covariance, which may inhibit the exploration to unknown directions. Although the past data base update of heuristic optimizers is seemingly one of main claims, I'm not fully convinced by a rationale behind this concept.\n\nI think an appropriate initialization should depend on the acquisition function. If the acquisition function tends to exploit, a strategy based on past information may be advantageous for the acquisition function maximization, while if the acquisition function is more explorative, past information may hinder the efficient maximization. For example, in the case of UCB, this balance is changed by beta. How superiority of the single initialization strategy for different exploit-exploration acquisition functions is justified?\n\nSome related approaches are missed to discuss:\n- DIRECT is widely used for the acquisition function optimization, though it is not mentioned. It should also be able to use for generating initial points for gradient-based optimizers.\n- LineBO (ICML2019) is another well-known high dimensional BO, for which the authors should have mentioned. \n\nHow is the MC acquisition function calculated? Explanation in page 6 (Batch Bayesian optimization) is unclear. It should be described in more detail.\n\nMC based acquisition functions may have largely different behavior from analytical acquisition functions (such as the standard formulation of EI). For example, analytical acquisition functions typically only depends on posterior mean and variance, by which the acquisition function surface becomes flat in the region that posterior mean and variance unchange, which may not happen in MC based EI and UCB because the values are fluctuated by random sampling, and it may have effect on the behavior of the gradient-based optimizers. Discussion in the paper is only for MC acquisition function? If so, it should be clearly explained. If not, evaluations on analytical acquisition functions would be desired.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kPSwwFjTMg", "reviewer": "Reviewer_4uty", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Improving acquisition function optimization is an important problem within Bayesian optimization that has received relatively little attention. This work will likely be relevant to many researchers in the BO community.\n\n2. The proposed method is easy to understand and implement. The empirical results are mostly convincing in the general superiority over existing initialization methods. As a result, we could potentially see this method as the new default in acquisition function optimization.\n\n3. The authors provided a comprehensive list of experiments to analyze various aspects of the proposed method. They include varying the acquisition function, varying hyperparameters in acquisition functions, and ablation study for individual components in the method. These experiments illustrate the importance of including all three methods in the initialization process.\n\nWeaknesses:\n1. Some parts of the submission could use more details explaining the practical implementations. Please see the requested changes section.\n\n2. The real-world tasks are still relatively artificial. The experiment on HalfCheetah shows large variances with 50 trials, which makes it difficult to interpret the results. There are more realistic tasks such as NAS-Bench-101 for optimizing neural network architectures worthy of consideration.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors study the problem of improving initializations of acquisition function optimizations in Bayesian optimization algorithms. The main contribution is a novel initialization scheme that employs three different methods (CMA-ES, GA, and random) to propose initialization points based on already queried points. The authors provided extensive empirical evaluations on synthetic and real-world optimization tasks to show the efficacy of the proposed method. Different acquisition functions are used to show the generality as well.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I found the description of the method incomplete. Specifically, AIBO uses CMA-ES and GA to provide initial point candidates. However, details are lacking. For example, how does one update the mean vector $m$ and the covariance matrix $C$ after acquiring new samples? For GA, how does one perform the mutation and crossover operations? In fact, there are different versions of GA so it is important to specify those details. \n\n\n2. In Section 6.4, given that AIBO_ga and AIBO_cmaes are both competitive with the full version AIBO. I think it makes sense to add AIBO_{ga+cmaes} as well to the comparison.\n\n\n3. In Section 6.7 algorithmic runtime comparison, I did not understand why AIBO would be faster than BO-grad. AIBO requires additional function calls for GA and CMA-ES. Is the speedup related to software implementation or the underlying hardware?\n\n\n4. I would consider running NAS-Bench-101 or a comparable benchmark to improve the claim for real-world performance.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bQE3QqvfPV", "reviewer": "Reviewer_YXGR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of this work is the thorough experimental evaluation provided, with \n\n   - comparison to state-of-the-art baselines\n   - an ablation study to understand the benefits and drawbacks of each heuristic\n\nThe conclusions of interest drawn from the presented evaluation are:\n   - the impact of AF maximizer initialization is not negligible in BO\n   - random initialization tends to explore more than heuristic alternatives\n   - selecting initial points from a pool of several heuristic-based candidates can improve downstream BO performance\n\nThe main limitations of this work are:\n   - The studied problem (i.e., the impact of AF maximizer initialization) is very specific and narrow\n   - The proposed algorithm is limited to a \"combine-then-select'' approach: i.e., combine several heuristic initializations to propose $k$ points each, then to select the top $n$ candidates\n   - There is a lack of theoretical motivation, justification or analysis on why the proposed framework may or may not work", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work consists of a comprehensive empirical study of the impact of **Acquisition Function (AF) maximizer initialization** in Bayesian optimization.\n\nThe authors present enough empirical evidence (via simulated and real data) to argue that the commonly used random initialization strategy does not often exploit the full potential of the Bayesian optimization procedure.\n\nIn fact, the authors conclude that random AF maximizer initialization tends to over-explore, and that simply increasing the number of random initialization restarts does not resolve the issue.\n\nMotivated by these insights, the authors present a framework (consisting of a combination and selection among existing heuristics) for a better initialization of the AF maximizer. They propose to combine $k$ points per-initialization strategy, with a later selection of the top-$n$ candidates among them. The aim is to provide a better and more diverse set of points for the AF maximizer to start from, for improved downstream BO performance.\n\nThis work's experimental evidence showcases how the proposed ---heuristic-based combine-then-select--- initialization framework can, across a variety of synthetic and real-world applications, outperform each of its components in isolation, as well as other state-of-the-art methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors argue for the need for other initialization strategies as a countermeasure for the over-exploration of the commonly used random initialization.\n\nHowever, one may wonder whether such exploration is actually a desirable feature in BO, so that one fully covers and evaluates the domain of interest (with an obvious increase in computational cost, of course). On the contrary, the objective of this work seems to focus on exploiting as much as possible.\n\nHence, I would encourage the authors to discuss in detail how important this trade-off is:\n   - e.g., whether there might be other cases (with a more complex optimization landscape) in which AIBO might exploit too early without fully exploring the full domain, or whether this will never occur (as long as random initialization is part of AIBO).\n   - how to reconcile or use model-based AF's within AIBO that the authors acknowledge _\"can offer a better mechanism for trading off exploration and exploitation compared to heuristic GA/CMA-ES algorithms\"_.\n\nIn addition, section 6.6 provides an evaluation of hyperparameter tuning in a single example (Ackley100). The contribution of this work would be strengthen with a more comprehensive hyperparameter evaluation across datasets and a discussion on how it impacts BO performance across tasks.\n\nFinally, some theoretical motivation or discussion would significantly strengthen the impact of this work.\n\nThese are other minor suggestions:\n   - The Introduction section already covers and discusses certain concepts and works cited in the Background section, making the latter a bit redundant. I would suggest the authors consider merging these 2 sections into a single introduction one, where all the necessary background is discussed as needed.\n   - Section 4.2, last sentence of first paragraph seems to be incomplete: _\"GPyTorch, the overhead of running BO with a GP model for a few thousand evaluations would be acceptable\"_\n   - Section 5.2, typo in first paragraph: _\"In Section 6.2, We evaluate\"_ -> _\"In Section 6.2, we evaluate\"_\n   - Section 6.3, typo in second paragraph: _\"highest GP posterior variance exploration)\"_ -> _\"highest GP posterior variance (exploration)\"_", "broader_impact_concerns": "This work does not discuss broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have raised different weaknesses and issues for the initial submission. After rebuttal, the authors have successfully addressed most concerns and requested changes. In the official recommendation, two reviewers vote to clearly accept this work and one reviewer leans toward acceptance. 

I read the paper in detail and also believe this work is valuable for the BO community. One thing that can be improved is a clear and more accurate description of the existing initialization strategies. The current submission simply claims "random initialization is a typical default strategy for initializing the AF maximizer" and "this is the case for widely-used packages like BoTorch, skort, GPyOpt, and GPflowOpt". However, the initialization strategies (even if all belong to random research) are not the same for different packages. For example, according to Appendix B.1 in [1], GPyOpt "augments random restarts with the best points observed so far, or alternatively points generated via
Thompson sampling", and BoTorch "selects initial points by performing Boltzmann sampling on a set of random points according to their acquisition function value". More detailed descriptions of different initialization strategies are also provided there. Since this work focuses on the initialization for BO, a clear and accurate discussion on the initialization strategies for different packages/works could be beneficial to the reader. Therefore, I recommend **accept with minor revision** for this work.

In the revised paper, I expect the authors to: 

+ Add a more comprehensive and detailed discussion on the initialization strategies for different BO methods/packages.

+ Double-check and ensure all the discussions/analyses provided in the rebuttal are well incorporated in the revised paper.

[1] Sebastian Ament, Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Unexpected Improvements to Expected Improvement for Bayesian Optimization. NeurIPS 2023.
Decision: Accept (poster)