Poisson Process for Bayesian Optimization
Authors: Xiaoxing Wang
Jiaxing Li
Chao Xue
Wei Liu
Chaoyue Wang
Weifeng Liu
Xiaokang Yang
Junchi Yan
Dacheng Tao
Venue: Submitted to ICLR 2023 (2023)

Abstract: Bayesian Optimization (BO) is a sample-efficient, model-based method for optimizing black-box functions which can be expensive to evaluate. Traditionally, BO seeks a probabilistic surrogate model, such as Tree-structured Parzen Estimator (TPE), Sequential Model Algorithm Configuration (SMAC), and Gaussian process (GP), based on the exact observed values. However, compared to the value response, relative ranking is hard to be disrupted due to noise resulting in better robustness. Moreover, it has better practicality when the exact value responses are intractable, but information about candidate preferences can be acquired. Thus, this work introduces an efficient BO framework, named PoPBO, consisting of a novel ranking-based response surface based on Poisson process and two acquisition functions to accommodate the proposed surrogate model. We show empirically that PoPBO improves efficacy and efficiency on both simulated and real-world benchmarks, including HPO and NAS.

Under review as a conference paper at ICLR 2023
POISSON PROCESS FOR BAYESIAN OPTIMIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Bayesian Optimization (BO) is sample-efficient, model-based method for opti- mizing black-box functions which can be expensive to evaluate. Traditionally, BO seeks probabilistic surrogate model, such as Tree-structured Parzen Estimator (TPE), Sequential Model Algorithm Configuration (SMAC), and Gaussian pro- cess (GP), based on the exact observed values. However, compared to the value response, relative ranking is harder to be disrupted due to noise resulting in better robustness. Moreover, has better practicality when the exact value responses are intractable. but information about candidate preferences can be acquired. This work introduces an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO), consisting of novel ranking- response surface based on Poisson process and two acquisition functions to accommodate the proposed surrogate model. We show empirically that PoPBO improves efficacy and effi- ciency on both simulated and real-world benchmarks, including HPO and NAS. Source code will be made publicly available.
INTRODUCTION
Bayesian optimization (BO) (Mockus et al., 1978) is a popular black-box optimization paradigm and has achieved great success in a number of challenging fields, such robotic control (Calandra
et al., 2016), biology (González et al., 2015), and hyperparameter tuning for complex learning tasks (Bergstra et al., 2011). A standard BO routine usually consists of two steps: (1) Learning a probabilistic response surface that captures the distribution of an unknown function f(x); (2) Optimizing an acquisition function that suggests the most valuable points for the next query iteration. Popular response surface for the first step includes Random Forest (SMAC) (Hutter et al., 201 1), Tree- structure Parzen Estimator (TPE) (Bergstra al., 201 Gaussian Process (GP) (Snock al., 2012) and Bayesian Neural Network (BNN) (Springenberg et al., 2016; Snoek et al., 2015). Acquisition functions for the second step include Expected Improvement (EI) (Mockus, 1994), Thompson Sampling (TS) (Chapelle & Li, 2011; Agrawal & Goyal, 2013) and Upper/Lower Confidence Bound (UCB/LCB) (Srinivas et al., 2012), which are designed to trade off exploration and exploitation.
Most of the existing BO methods (Bergstra et al., 2011; Hutter et al., 2011; Snoek et al., 2012) adopt absolute response surfaces that attempt to the black-box function based on the observed absolute function values. However, such an absolute metric can have the following disadvantages. 1) Absolute response can be difficult to obtain or even unavailable in some practical scenarios, such as sports games and recommender systems where only relative evaluation can be provided by pairwise comparison (He et al., 2022). 2) Absolute response can be sensitive to noise, which is also pointed out by Rosset et al. (2005). Such an issue will affect the performance of BO in real-worke scenarios, where absolute responses are usually noisy. 3) It can be challenging to directly transfer absolute response surfaces. In particular, multi-fidelity metrics usually have different absolute responses for the same candidate, making it hard to utilize history observations on a coarse-fidelity metric to warm up the training of surrogate models on fine-grained grained-fidelity one. Similarly, hyperparameter optimization (HPO) and neural architecture search (NAS) tasks, performance on different datasets of the same hyperparameter selection or neural architectures also different and is hard to be transferred across datasets.
In this work, 'ahsolute evaluation (response)" of one query is defined as its exact black-box function value. II this work, 'relative evaluation (response)' of one query is defined as its ranking, which can be computed by comparing with other candidates.

---

Under review as a conference paper at ICLR 2023
Relative metrics can be effective cure for the above issues. 1) Relative response such ranking has better practicality when the information about candidate preferences can be more easily acquired than raw value (González et al., 2017), which is also widely used in many prior works (Kahneman & Tversky, 2013; Brusilovsky et al., 2007; González et al., 2017). 7). 2) Relative response is more robust to noise than absolute response since relation such as ranking between candidates is harder to be disrupted to noise, but absolute values are sensitive. In this work, we analyze the robustness of rankings in Sec. 3.1 under the common additive Gaussian noise assumption, showing that rankings are more insensitive to noise than absolute values. Similar conclusions are also made in other areas regarding the advantage of ranking models e.g. (Rosset et al., 2005). 3) Relative response has better transferability. such rankings between candidates, since they are usually comparable among multi-fidelin metrics or evaluations across different datasets for the same candidate. It also demonstrated by (Salinas et al., 2020; Nguyen et al., 2021; Feurer et al., 2018).
Some Bayesian Optimization methods also adopt relative responses and are related to our work. Preferential BO methods (González et al., 2017; Mikkola et al., 2020) attempt to capture the relative preference by comparing pair of candidates. However, they have to rely on a computationall-epennsi soft- coft-Copeland score (PBO) have to optimize EI by the projective preferential query (PPBO) to propose the next query (optimal candidate). Moreover, they ignore tie situations, which commonly exist in real scenarios. Nguyen al. (2021) extend the above method by comparing k samples. Specifically, they utilize Gaussian Process to model the absolute function values and leverage a multi- nominal logit model to build the evidence likelihood of local ranking of k observations. Although this method overcomes the computational disadvantage and takes ties into account, it essentially models the absolute response and simply captures the relationship (local ranking) among k candidates.
In contrast to the above methods, we propose to capture the global ranking of each candidate in a feasible domain (search space) and model the relative response. On the one hand, we can directly search the optimum based on our relative response surface and obtain the next query without computationally expensive procedure (González et al., 2017; Mikkola et al., 2020). On the other hand, unlike (Nguyen et al., 2021) that first build an absolute response surface and then derive local ranking among candidates as the evidence, our method directly fits a ranking- -aased relative response surface. Moreover, due to the nature of ranking, our method can handle tie situations where candidates have the same ranking. Specifically, we adopt Poisson Process (PP) to capture the global ranking, which is naturally suitable since the ranking of candidate can be figured out by counting the number of better candidates. Fig. I shows the superiority of our response surface to capture the global ranking against the GP-based one. Specifically, we conduct experiments on the Forrester function with various degrees of additive Gaussian noise. The setting details can be found in Appendix C. Our response surface is more robust to noise and can better capture the global ranking. Furthermore, we derive two acquisition functions to accommodate our response surface for a better exploitation-exploaatte trade-off. Finally, we propose a novel Bayesian Optimization framework, named PoPBO, achieving lower regret (better performance) with faster speed. Our contributions can be summarized as follows:
1) Ranking-based Response Surface based on Poisson Process. Unlike the prior absolute response surface (Bergstra et al., 2011 1; Snoek et al., 2012), nor those (Nguyen et al., 2021) using relative evidence likelihood based on absolute responses, this work, to the best of our knowledge, is the first to directly capture the global ranking over feasible domain via Poisson process. The robustness against noise is also analyzed in Sec. 3.1 and illustrated in Fig. 1.
2) Tailored Acquisition Function for Ranking- Response Surface. Two acquisition functions for our response surface, named R-LCB and ERI, are deduced from the vanilla LCB and El for better trade-off. Gradients of the proposed acquisition functions w.r.t. candidates are also derived, so the next query can be optimized by SGD.
3) Computational- -fffcccietttitttttt Bayesian Optimization Framework. The proposed ranking- based response surface and acquisition functions form a novel Bayesian optimization framework: Poisson Process Bayesian Optimization (PoPBO). Our framework is much faster than Gaussian process-basse BO methods. Specifically, the computational complexity of PoPBO is O(N2) compared to O ((v3) of GP, where N is the number of samples (see Fig. 3).
4) Extensive Empirical Study with Strong Performance. Our method achieves substantial im- provements over many prior BO methods on the simulated functions and multiple benchmarks on real-world datasets, including hyperparameter optimization and neural architecture search.
2

---

Under review as a conference paper at ICLR 2023
oracle
oraele
100
0 0.00
100
0.00
Ranking
0.15
Ranking
80
0.15
60
60
0.45
40
40
20
20
0.0
0.4
0.8
0.0
0.4
0.8
X
X
(a) GP (value-based) Response Surface
(b) PP (ranking-based) Response Surface
Figure 1: We compare the sensitivity of additive Gaussian noise between GP (value-based) response surface and PoPBO (ranking-bar based response surface) on the Forrester function. Based on the Forrester function value, the solid black line (oracle) indicates actual rankings over 100 points evenly spaced from 0 to 0.8. We draw lines between the 100 predictions by linear interpolation for clear illustration. The dash lines indicate predicted rankings over the 100 points by (a) Gaussian process and (b) Poisson process on observations with varying degrees of noise whose standard deviation a ranges from 0 to 0.45. Each response surface is trained on the same 15 queries. Note that GP performs worse as the standard deviation of noise increases. In contrast, PP performs consistently well due to its great robustness against noise in our analysis.
2 PRELIMINARIES AND BACKGROUND
Bayesian Optimization. Consider minimizing black-box target function f()): X IR defined on d-dimensional feasible domain X R. our goal is find a global minimum of f(-).
arg min fx)). x
(1)
These black-box objective functions can be expensive be evaluated, such as those without closed- form expression/derriative functions and long-time training neural networks. Bayesian Optimization (BO) is efficient method to solve these problems (Brochu al., 2010; Perrone al., 2018). relies on a response surface built on the black-box function, which fits sequentially using the new query selected according an exploit-explore trade-off acquisition function. A Gaussian Process with nonlinear kernel is one of the most popular choices of the response surface, which places a GP prior the unknown function f. gives its posterior an exact form conditioned to the prior observations D = {Iz). ) SMAC (Hutter et al., 2011) introduces random forest models for regression, which can be used handle those categorical hyperparameters. TPE (Bergstra al., 2011) is another BO method that models two densities ((x) ply < a/r, D) and g(x) = ply a/x, D) via kernel density estimator instead of modeling p(y(z) directly like GP, and then the ratio 1xx) (x))((>)))))))) will be optimized as the acquisition function to find the next query. Recently, Bayesian neural network was introduced into BO framework (Snoek et al., 2015) to model the response surface due to its flexibility and scalability, and Springenberg et al. (2016) using more robust stochastic gradient MCMC method (Chen et al., 2014) to evaluate the posterior. Besides a powerful response surface, BO also needs an exquisite criterion for suggesting the next query considering the trade-off between exploitation and exploration. The most common acquisition function is El since it is intuitive and has achieved strong performance in various tasks. Another common criterion is LCB, which minimizes regret during sequential optimization.
BO with Relative Metrics. The relative metric does not have to utilize absolute responses of the black-box function. Some methods focus on the cases where the function evaluation is not directly accessible (Brusilovsky al., 2007; González et al., 2017: Mikkola et al., 2020; Siivola et al., 2021). Absolute responses can be difficult to obtain or even unavailable in some practical scenarios, such as sports games and recommender systems (Brusilovsky et al., 2007) where only relative evaluation can be provided by pairwise comparisons. Preferential Bayesian Optimization (PBO) (González et al., 2017) captures correlations between different inputs to find the optimal value of a latent function, which requires limited comparisons. To handle high- digh-dimensionll black-box function, Projective Preferential Bayesian Optimization (PPBO) (Mikkola et al., 2020) proposes a projective preferential query allowing for the feedback given by human interaction. However, they ignore the
3

---

Under review as a conference paper at ICLR 2023
tie situations and have rely computationally expensive procedure to suggest the next query. Nguyen et al. (2021) extend the above method by comparing k samples but have to model the absolute response surface by Gaussian Process and assume the noise obeys Gumbel distribution. In addition, ranking-based methods (Feurer et al., 2018; 8; Salinas et al., 2020) can also facilitate the identification of similar runs for transfer learning, reusing insights from past similar experiments. This work, on the contrary, makes the first attempt to directly capture the global ranking of candidates based on Poisson process and derive a novel Bayesian Optimization framework named PoPBO. We analyze the robustness of relative metric (ranking) against noise and show the outstanding performance of our method on various simulated benchmarks and real-world datasets.
POISSON PROCESS FOR BAYESIAN OPTIMIZATION
This section first introduces a ranking- baaed evaluation and analyzes its robustness compared to the value-based evaluation. Then, we propose novel response surface based on Poisson process to capture the ranking-based evaluation for each candidate and derive the log-likelihood on observations. Finally, we fit the ranking- provide the posterior probability.
mankin-bbased based response surface by training the weights through SGD and then
3.1 RANKING-BASED EVALUATION
Suppose a black-box score function f()) is defined on a feasible domain X consisting of all optional candidates. Given sample X and a subset of the feasible domain S X, we define a set S. = (yly S, f'y) < f(z)), consisting of the better candidates than x in a set S. Considering the physical meaning of Sz,, we can estimate the superiority of for f() against the points in set S by measuring Sz- Specifically, considering two points Ii, 22 Sa, has a larger measure value, representing that there are more points in S better than æ1, so 2 worse than x2.
To construct such a metric, we first introduce sets Q {Sa|S c X, E X). Given a sampled set X. We can define metric j on the space (X, Q) by the number of elements in Sr S ((Sz) = |Sg n S1.
(2)
Robustness Analysis. Suppose black-box function f(x:) with additive Gaussian noisy observations f(x) f(x) + c, /V,,00)0 o²). Consider two queries 2 I2 with observations f( (x2). We
assume f(x1)) fx2) without loss of generality, the probability of correctly ranking I1, 22 is:
P(f(z)) < f(x2)) = P(ci c2 Since (1, C2 ~ (N(000 are independent variables, A = c2 According to three- sigma rule of thumb. if f(22) f(z1) /2o, the probability of correctly ranking #2 is larger than 82.639 22.63%; If f(x2) - f(x1) 2/2a, the probability correctly ranking æ 22 is larger than 97.72%. Therefore, even if observations are noisy, the ranking of candidates is hard to be disrupted. Fig. 1(b) verifies the robustness to noise ranking-basee evaluation. Specifically, we do not involve any prior distribution for noise when training PP response surface, but it can still capture the correct ranking (black line) under various noise levels.
3.2 CAPTURING THE RANKING VIA POISSON PROCESS
Given a sample r and a set S, we utilize a random process (S). X to capture the ranking x. Though R. (8) also depends on Š, we omit it for conciseness. In particular, we define R2 = (x) denote the ranking of over the whole feasible domain X, which a random variable. We can model R. (S), YS X as independent increment counting process, since the objective function f(x) is black-box and we assume the rankings of x over two disjoint areas are independent, i.e., (S, 11 (S,), VS,
X, S1 n S2 Ø. Moreover, Rx (S) has the following properties: 1) (Ø) 0 and 2) limas-o P( ( As) Re (S) 2) 0. VS X. Detailed discussion provided in Appendix A. Since the supremum of (S) (Š]. (S) obeys truncated non- homogeneous Poisson process (Yigiter & Inal, 2006) as Eq. 4 with parameter \(s, e X.
(5) ~ Poisson (Sg 2ss,
(4)
4

---

Under review as a conference paper at ICLR 2023
Hence, the ranking of over the whole feasible domain is RR RX), the probability of R is:
= - (Ux )ds) exp (- ex ((5,
(A<(z)[X1)*
exp (-)e (5)
k! (x)
k!. 2(x)
|8M(1] 2(x)= Σ
x) exp exp (-p(-\(,+)))x
(6)
k!
where (x)) is the normalized coefficient and {ax) indicates the number of sampled sets without r. There exists f X satisfying Jx M x )) = Xx according to the mean value theorem for integrals. We can approximate )ς(x)) by a multi-layer perception (MLP) Ag (x; 0) with parameter
Give NNN >= 2) samples = (x; رر= the ranking of each sample over S is K = (he 1 With the independent assumption of observations similar (Salinas et al., 2020), the log-likelihood is:
(A=(z;:0))x)) i!
log L(R|S;))
ke, log (Ag (=)(0)))) - llg (kx,!) !)- - log
(7)
We can train the weights by minimizing the negative log-likelihood on observations in Eq. 7 by SGD, whose gradient can be computed as follows:
i ( log I(K(s)) N (7((zz;0) a0
kay
ΣN- 2 (Ac(2;10) X1)
x! |X]
(8)
ad
(e(oo;;))
ENNO1 i!
(Ac(az;00) X
Once 0 is determined after training on the observations (8, K). the ranking of new sample x" over the whole feasible domain X can be predicted, where Z is the normalized coefficient by Eq. 6.
P P (X) (X) = =00,x", S)) (>c(**;0)(x1) exp x)(x==00)X1) k! -(x*)
The proposed Bayesian optimization framework with Poisson process (PoPBO) is outlined in Alg. 1 in Appendix B. The acquisition function will be introduced in the next section.
4 ACQUISITION FUNCTION FOR POPBO
The existing acquisition functions are designed for absolute response surface considering independent mean and variance, which can be improper for our response surface since the mean of Poisson distribution is the same the variance. Directly applying these acquisition functions our PoPBO will cause the over-exploitation issue. To this end, we introduce a series of acquisition functions, named Rectified Upper Confidence Bound (R-LCB) and Expected Ranking Improvement (ERI), derived from vanilla LCB and EI, respectively.
4.1 RECTIFIED LOWER CONFIDENCE BOUND (R-LCB)
The ranking of each point x obeys Poisson distribution as Eq. 9, with expectation u(z) = Xe (x(x))
NN- (Ae((()))))))) xD) and standard deviation (2) = vu(z). Thus the vanilla LCB cach point is:
EN (A)(
(LC p())))))(>>---a))p) -(())Ba(())
((x) (Vu(x)
(10)
However, Poisson distribution with a large expectation has a larger variance, indicating less confidence in the ranking prediction. So the vanilla LCB will be easily trapped into over-exploitation issue. Therefore, we propose to restrict the lower value as a threshold and define the rectified LCB (R-LCB):
(LLCB()) (x)
if de (x; < Sf
OR-LCB (x)
(11)
Ez U[0
Otherwise
where en is used for re-parameterization, and is some quantile of the number of existing samples, according to which, the threshold q| can adaptively adjusted during the BO process. To minimize R-LCB, we randomly sample set of start points and adopt LBFGS (Liu & Nocedal, 1989) for optimization. In particular, LBFGS will not update the samples whose predicted ranking is larger than S| and they have a probability of being selected as the next query the sampled e, is very small. We set q 0.6 by default. Results in Fig. show the advantage of our R-L.CB against LCB.
5

---

Under review as a conference paper at ICLR 2023
Random Search
SMAC
GP-EI
PPBO
PoPBO-ERI
TPE
BOHAMIANN
GF-LCB
HEBO
PoPBO-R-I.CB
Minimum Regret
Minimum Regret
2.5
3.0
Minitumm Regret
40
2.0
10"
1.5
0.5
20
40
60
60
20
40
60
80
Iteration
Iteration
(a) 2-d Branin
(b) 6-d Hartmann
(c) 6-d Rosenbrock
Figure 2: Performance of various black-box optimization methods on three simulation functions.
Y-axis indicates the residual between the optimum function value and the incumbent. We run each method ten times and plot the average performance and standard deviation the line and shadow.
4.2 EXPECTED RANKING IMPROVEMENT (ERI)
Inspired by EI, we introduce ERI to maximize the expected improvement on ranking over the worst tolerable ranking Km balance exploitation and exploration. We set Kn, 5 by default.
Kig
CEER( (x) > (Km k.) kP PP = kl0,z),
(12)
k=-
where P P(R x) is defined in Eq. 9 representing the prediction of ranking of The gradient of ERI w.r.t. is defined as follows, where (e(x) (z;
ŌAERI(
Km
Km k 0
((+(+)))x)** exp A(COO)XDI]
Σ
Or
k!
dx
k!. (xx)
k-0
Km
(Km - 1:) (x)()))x1)) |X|
N ()c()))(1²
N-1 (Ac()))x)² (x) Σ
h
E =0
AI(EN) (A(())ID3 )²
i!
i!
0--
Hence, we can get the next query x" by minimizing ( through LBFGS optimizer. Similar to R-LCB, we also apply the rectified technique in Eq. 11 to ERI.
5 EMPIRICAL ANALYSIS
Benchmarks. We verify the efficacy of PoPBO on both simulated and real-world benchmarks, including HPO and NAS, For the simulated benchmark, we apply PoPBO to optimize three sim- ulation functions: 1) 2-d Branin function with the domains of each dimension are [-5, 10] and [0,15] 15] respectively; 2) 6-d Hartmann function in [0. 1] for all six dimensions; 3) 6-d Rosenbrock function defined in [-5, 10]6. For the HPO task, test PoPBO the tabular benchmark HPO- Bench (Eggensperger et al., 2021), containing the root mean square error (RMSE) of a 2-layer feed-forward neural network (FCNET) (Klein & Hutter, 2019) trained under 62208 hyper-parameter configurations on four real-world datasets: protein structure (Rana, 2013), slice localization (Graf al., 2011) I), naval propulsion (Coraddu al., 2016) and parkinsons telemonitoring (Tsanas al., 2010). The averaged RMSE over four independent runs under the same configuration is utilized as the performance that configuration. For the NAS task, we test on NAS-Bende Bench-enhhh0 -001 (Dong Yang, 2020) containing 15,625 architectures in cell search space that consists of 6 categorical parameters, and each parameter has five choices. Fach architecture evaluated on three datasets. Following the setting of (Dong & Yang, 2020), search for the best architecture according to its performance the CIFAR-10 validation set after 12 epochs training.
Baselines. We compare against random search (RS) (Bergstra & Bengio, 2012) and various value- based Bayesian optimization methods, including Gaussian Process (GP) (Snoek et al., 2012), Tree- structured Parzen Estimation (TPE) (Bergstra et al., 201 1), and Sequential Model Algorithm Configu- ration (SMAC) (Hutter al., 2011). BOHAMIANN (Springenberg et al., 2016), and HEBO (Cowen- Rivers al., 2020). For GP methods,
EI and LCB acquisition functions, which

---

Under review as a conference paper at ICLR 2023
optimized by LBFGS, and adopt the ARD Matérn 5/2 covariance function to be the kernel function. We also compare with PPBO (Mikkola et al., 2020), one of state the art preferential BO methods that also utilizes relative response (preferential between pair of candidates). Detailed settings of the baselines are provided in Appendix C.2.
Settings. We run all the methods for 80 iterations with 12 initial points by default. For the Rosenbrock- 6d simulation function, we run all methods for 80 iterations with 30 initial points due to its complex search space. The MLP Xe 0) used to approximate the parameter of the Poisson process has three hidden layers with 128 nodes and a ReLU activation function. The MLP is trained for 100 steps by ADAM with 64 batch sizes and a 0.01 initial learning rate multiplied by 0.2 every 30 steps. All methods are evaluated ten times independently on an Intel(R) Xeon(R) Silver 4210R CPU.
5.1 PERFORMANCE ON THE SIMULATED BENCHMARKS
2-d Branin. Fig. ((a) compares PoPBO and baselines on Branin, which a widely used simulation benchmark, verifying the efficacy of our PoPBO with both ERI and R-LCB.
6-d Hartmann. This function has higher dimensions than Branin and thus is more difficult optimize. As shown in Fig. 2(b), although the standard GP temporarily outperforms others the early stage, our PoPBO achieves the best at around 40-th iterations and takes the lead till the end of the BO procedure. In particular, PPBO performs great in the early stage but falls into a local optimum after ten iterations.
PoPBO
Time cost per iteration
GP
PPBO
25
6-d Rosenbrock. Optimizing the 6-d Rosebrock function is much more complicated than Branin and Hartmann since its global optimum lies in a narrow valley (Picheny et al., 2013) as well as a more ex- tensive search space. Hence, increase the initial points to 30 for a better preview of the Rosenbrock landscape for all methods. Fig. 2(c) shows that our PoPBO can quickly find the valley and significantly outperforms other BO methods.
Iteration
Figure 3: Time cost of Gaussian process Bayesian optimization (GP), PPBO (Mikkola et al., 2020) and PoPBO. All the methods are applied optimize 6-d Hartmann function.
Computational Cost. Fig. 3 compares the time cost of three peer methods, showing that the cost of GP- BO and PPBO are much higher than PoPBO as the number of observations increases. Specifically, GP has to compute the inverse of covariance matrix resulting in O(N*) computational complexity. PPBO is also based on GP and requires computing another covariance matrix of size J J, where J the number of random samples during optimization. In contrast, the computational bottleneck of PoPBO lies in the training of an MLP, which is O(N²) as shown in Eq. 7.
5.2 PERFORMANCE ON THE REAL-WORLD BENCHMARKS
HPO-Bench. we run each method for ten times and plot the trend of minimum regret during the BO procedure. Fig. 4 compares PoPBO with advanced Bayesian optimization methods and random search on HPO-Bench (Eggensperger al., 2021), showing that PoPBO achieves the best on all the four datasets. In contrast, other methods are unable to perform consistently well and even worse than random search. Moreover, the performance of our method has lower standard deviation than other methods, indicating its outstanding stability. The numerical performance of all methods on the four datasets are provided in Table in Appendix C.3.
NAS-Bench-201. Table reports the performance on the NAS task. The first block shows the performance prior tar--parmetee--sarnng--bo-e algorithm, reinforcement learning, and Bayesian optimization. We adopt the same initial observations when testing Random Search, GP-BO, and our PoPBO for a fair comparison. As for SMAC and TPE, directly the open-source codes, which have different sampling implementations from ours, making hard to sample the same initial observations as ours even under the same random seed. Our method achieves the best performance on the three datasets and, in particular,
NAS methods, including random search, evolution
7

---

Under review as a conference paper at ICLR 2023
Random Searh
TPE
SMAC
GP-EI
GP-JCR
RoPBO-ERI
POPBO-R-LCH
Mininum Regret
Minimum Regret
10"
10
Iteration
Iteration
(a) HPO- HiPO-Bench-Naval
(b) HPO-Bench Parkinson H00--Benh-Paarkison
10"
Minimum Regret
Minimum Regret
10
10
10
40
Iteration
Iteration
(c) HPO-Bench-Proutte
(d) HPO-Bench-Slice
Figure Minimum regret comparison with random search and various Bayesian optimization methods on tabular datasets in function value and the incumbent. We run each method ten times and plot the average performance and standard deviation of the incumbent as the line and shadow. Our PoPBO can quickly discover good samples and achieves the best performance (lowest regret).
Y-axis indicates the residual between the optimum
Table I: Top-1 mean accuracy (%) for classification NAS- 20S-Bench-201. The first block shows the performance of non-parameter sharing algorithms and various Bayesian optimization methods. The second block shows the performance of PoPBO with ERI and R-LCB acquisition functions. f; Results are obtained from MAS--ench-2201 Otherwise, we independently run the method for ten times. The best mean accuracy in each column in bold.
CIFAR-10
CIFAR-100
ImageNet- 16-120
Methods
valid
test
valid
test
valid
test
REINFORCE (1992)*
91.0910.37
93.8510.37
71.61=1.12 7..71+1.09 45.05:1.02
45.24 1.18
REA (2019)*
91.1910.31
93.9210.30
71.81a1.12
71.8410.99
45.1510.89
45.5411.03
Random Scarch (2012)
91.00+0.38
93.83+0.31
71.29=1.29
71.47+1.16
44.83+1.11
45.05+1.14
BOHB (2018)t
90.82+0.53
93.61+0.52
70.74=1.29
10.85+1.28
44.26+1.36
44.42+1.49
TPE (2011)
91.06=0.38
93.9010.34
71.29=1.29
71.85+1.13
45.04+1.23
45.27:1.49
SMAC (2011)
91.09+0.38
93.95+0.28
71.40=1.23
71.66+1.11
45.1140.99
45.32+1.09
GP (ED (2012)
91.40+0.18
94.23+0.15
72.67=0.83
72.75+0.47
45.83+0.45
46.20=0.63
GP (LCB) (2012)
91.30+0.25
93.9810.22
72.00=0.80
72.05x0.76
45.3710.83
45.60=0.94
BOHAMIANN (2016)
91.3610.16
94.1310.23
72.36=0.82
72.381081
45.9310.66
46.1810.60
PoPBO (ERI)
91.52+0.05
94.35+0.03
73.21=0.29
73.25+0.18
46.27+0.36
46.54+0.19
PoPBO (R-LCB)
91.52+0.04
94.33+0.08
73.21=0.36
73.19+0.31
46. 12.1244.43 46.61=0.32
outperforms the sfate-of-the-ar Bayesian optimization methods BOHB (Falkner et al., 2018) and BOHAMIANN (Springenberg et al., 2016). Additionally, we plot the performance trend of various methods on the test set of CIFAR-10, CIFAR- 100, and ImageNetl 6-120 in Fig. 5. We observe that though our PoPBO slightly falls behind GP an early stage, it catches up with GP at around 30-th epoch and takes the lead till the end of the search procedure. The performance trend on the validation set is also displayed in Fig. 7 in Appendix C.3.
5.3 EFFECTIVENESS OF RECTIFIED TECHNIQUE The quantile parameter in Eq. 11 controls the trade-off between exploration and exploitation. smaller q has better exploration ability. On the one hand, undesirable to set q as a rather small value since method degrades Random Search when q 0, making PoPBO suffers
8

---

Under review as a conference paper at ICLR 2023
Random Seach
SMAC
GP-EI
GP-LOR
PoPBO-ERI
PoPBO-R-LCC
46
Best Ace
44
Bes
70
Ros
42
68
20
40
60
80
20
40
60
80
20
40
60
80
Iteration
Iteration
Iteration
(a) CIFAR-10 test-set
(b) CIFAR100 test-sct
(c) ImageNet-16- 16-120 test-set
Figure 5: Performance trend of random search and Bayesian optimization methods on NAS-Bi NAS-Bench-
201. We run 10 times for each setting and plot the mean accuracy as the lines. Note that when testing Random Search, GP-BO, and our PoPBO, we adopt the same initial random seeds for all settings at each run for fairness. Hence, the lines in each plot have the same initial point (at the O-th iteration).
10*
10
Minimum Regret
Minimum Rogret
10"
10
10'
10"
10
10*
20
40
60 80
20
40
60
Iteration
Iteration
(a) Results of R-LCB Rosenbrock
(b) Results of ERI Rosenbrock
Figure 6: Ablation study hyperparameter q, which controls the polloiatiion-xxllrattiio trade-off. We test on the Rosenbrock simulation function, a complex landscape, and show the effect on (a) R-LCB and (b) ERI. For each setting, run ten times and plot the average performance of the incumbent. Notice that we adopt the same initial random seeds for all settings at each run for fairness. Hence, the lines in each plot have the same initial point (at the 0-th iteration).
over-exploration issue. On the other hand, our method degrades to the vanilla acquisition functions when q + 1, making PoPBO suffers an over-exploitation issue as our analysis Sec. Fig. evaluates the effect of quantile parameters 9 both R-LCB and ERI. We independently run ten times for each setting and adopt the same initial random seeds for all settings at each run for a fair comparison. Hence, the lines in Fig. 6 have the same initial point (at the 0-th iteration). We discover that the best setting of the quantile parameter g for R-LCB 0.6, and the best for ERI is 0.4.
6 CONCLUSION
We have proposed novel Bayesian Optimization framework, named PoPBO, for optimizing black- box functions with relative responses, being more robust to noise than absolute responses. Specifically, we introduce a relative response surface to capture the global ranking of candidates based on the Poisson process that is suitable for modeling discrete count events. We give the likelihood and posterior forms of ranking under the general assumption of non non-hooogeneous Poisson process. To balance the trade-off between exploration and exploitation, we design two acquisition functions, namely Rectified Lower Confidence Bound (R-LCBB and Expected Ranking Improvement (ERI), for our ranking-bart based response surface. Our method enjoys a lower computational complexity O(N2) compared to GP's ( and performs competitively both simulated and real-worke benchmarks.
Limitations and Future Work. This work analyzes the robustness of relative response against noise and thus does not involve prior knowledge of noise. However, there exist real scenarios where the noise is too large to disrupt the ranking observations, and we would like to leave it as our future work. Additionally, the mean of Poisson distribution is the same as variance, which has potential over-exploitation issue as mentioned in Sec. 4. This work introduces a rectified technique to alleviate it, and would like explore other elegant acquisition functions in future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In ICML, 2013.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal Of Machine Learning Research, 2012.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for Syper-parammeter optimization. In NeurlPS, 2011.
Eric Brochu, Vlad M. Cora, and Nando de Freitas. tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. Computer Research Repository, 2010.
Peter Brusilovsky, Alfred Kobsa, and Wolfgang Nejdl (eds.). The Adaptive Web, Methods and Strategies of Web Personalization, volume 4321 of Lecture Notes in Computer Science, 2007.
Springer.
Roberto Calandra, André Seyfarth, Jan Peters, and Mare Peter Deisenroth. Bayesian optimization for learning gaits under uncertainty experimental comparison dynamic bipedal walker. Annals of Mathematics and Artificial Intelligence, 2016.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In NeurIPS, 201 1.
Tianqi Chen, Emily B. Fox, and Carlos Guestrin. Stochastic gradient hamiltonian monte carlo. In ICML, 2014.
Andrea Coraddu, Luca Oneto, Aessandro Ghio, Stefano Savio, Davide Anguita, and Massimo Figari. Machine learning approaches for improving condition-basee maintenance of naval propulsion plants. Proceedings of the Institution of Mechanical Engineers, Part M: Journal of Engineering for the Maritime Environment, 2016.
Alexander I. Cowen-Rivers, Wenlong Lyu, Zhi Wang, Rasul Tutunov, Jianye Hao, Jun Wang, and Haitham Bou-Ammar. HEBO: heteroscedastic evolutionary bayesian optimisation. CoRR, abs/2012.00826,, 2020.
Xuanyi Dong and Yi Yang. Nas-bench-200 Extending the scope of reproducible neural architecture search. In /CLR, 2020.
Katharina Eggensperger, Philipp Müller, Neeratyoy Maliik, Matthias Feurer, René Sass, Aaron Klein, Noor H. Awad, Marius Lindauer, and Frank Hutter. Hpobench: A collection of reproducible multi-fidelity benchmark problems for HPO. In NeurlPS, 2021.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: robust and efficient hyperparameter optimiza- tion scale. In ICML, 2018
Matthias Feurer, Benjamin Letham, and Eytan Bakshy, Scalable meta-learning for bayesian opti- mization using ranking-weighte gaussian process ensembles. In AutoML Workshop at ICML, 2018.
Javier González, Zhenwen Dai, Andreas C. Damianou, and Neil Lawrence. Preferential bayesian optimization. In ICMI., 2017.
Javier González, Joseph Longworth, David C. James, and Neil D. Lawrence, Bayesian optimization for synthetic gene design. arXiv preprinl urXiv:/505.00ee 01627, 2015.
Franz Graf, Hans-Peter Kriegel, Matthias Schubert, Sebastian Pölsterl, and Alexander Cavallaro. 2d image registration in CT images using radial image descriptors. In MICCAI, 2011.
Y. He, Q Gan, D. Wipf, G. Reinert, J. Yan. and M. Cucuringu. Gnnrank: from pairwise comparisons via directed graph neural networks. In ICML, 2022.
Learning global rankings
Frank Hutter, Holger H. Hoos, and Kevin Leyton-Browt Brown. Sequential model-basee optimization for general algorithm configuration. In LJON, 2011.
10

---

Under review as a conference paper at ICLR 2023
Daniel Kahneman and Amos Tversky. Prospect theory: An analysis of decision under risk. In Handbook of the fundamentals of financial decision making: Part I, pp. 99-127. World Scientific, 2013.
Aaron Klein and Frank Hutter. Tabular benchmarks for joint architecture and hyperparameter optimization. Computer Research Repository, 2019.
Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Math. Program., 45(1-3):503-533 1989. doi: 10.1007/BF01589116 URL https: //doi. org/10. 1007007/000 8F 589116.
Petrus Mikkola, Milica Todorovic, Jari Järvi, Patrick Rinke, and Samuel Kaski. Projective preferential bayesian optimization. In ICML, 2020.
Jonas Mockus. Application of bayesian approach numerical methods of global and stochastic optimization. Journal of Global Optimization, 1994.
Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of bayesian methods for seeking the extremum. Towards global optimization, 1978.
Quoc Phong Nguyen, Sebastian Tay, Bryan Kian Hsiang Low, and Patrick Jaillet. Top-k ranking bayesian optimization. In AAAI, 2021.
Valerio Perrone, Rodolphe Jenatton, Matthias W. Seeger, and Cédric Archambeau. Scalable hyperpa- rameter transfer learning. In NeurIPS, 2018.
Victor Picheny, Tobias Wagner, and David Ginsbourger. A benchmark of kriging-basse based infill criteria for noisy optimization. Structural and multidisciplinary optimization, 2013.
PS Rana. Physicochemical properties of protein tertiary structure data set. UCI Machine Learning Repository, 2013.
Esteban Real, Alok Aggarwal, Yamping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
Saharon Rosset, Claudia Perlich, and Bianca Zadrozny. Ranking-based evaluation of regression models. In ICDM, 2005.
David Salinas, Huibin Shen, and Valerio Perrone. A quantile-based approach for hyperparameter transfer learning. In ICML, 2020.
Eero Siivola, Akash Kumar Dhaka, Michael Riis Andersen, Javier González, Pablo Garcia Moreno, and Aki Vehtari. Preferential batch bayesian optimization. In MLSP, 2021.
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In NeurlPS, 2012.
Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Md. Mostofa Ali Patwary. Prabhat, and Ryan P. Adams. Scalable bayesian optimization using deep neural networks. In ICML. 2015.
Jost Tobias Springenberg, Aaron Klein, Stefan Falkner, and Frank Hutter. Bayesian optimization with robust bayesian neural networks. In NeurIPS, 2016.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. infommation-theorede regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 2012.
Athanasios Tsanas, Max A. Little, Patrick E. McSharry, and Lorraine O. Ramig. Accurate telemon- itoring of parkinson's disease progression by noninvasive speech tests. IEEE Transactions Biomedical Engineering, 2010.
Ronald Williams. Simple statistical gradient- algorithms for connectionist reinforcement learning. Machine Learning. 1992.
A Yigiter and Inal. Right truncated homogeneous poisson process. STATISFICS-ALL SERIES, 22(1):69, 2006.
PAKISTAN JOURNAL OF
11

---

Under review as a conference paper at ICLR 2023
A DISCUSSION ON THE ASSUMPTIONS FOR (S)
We assume R2 (S) the following properties: 1) (2) = and 2) limas-o lim (S") As)- (S') 2 2) 0, VS' c S. The first assumption is naturally satisfied since there are points x' Ø satisfying f(x') > f()), where f(z) indicates the observation of point æ. The second assumption is naturally satisfied when the black-box function has discrete domain of definitions since we find small enough As that only contains one point. We further assume that it still holds in the case of continuous spaces since we have no prior information about the black-box function whose observation is noisy and thus discrete everywhere. Specifically, we introduce the following proposition.
Proposition 1. Suppose a black-bou function f(x) whose observation f f(x) = f(x) + has additive noise e~ N (0, obeying Gaussian distribution. Then the observation f()) is discrete everywhere.
Proof. We would like first give the definition of continuous, and then provide the definition of discrete through the negative continuous proposition.
Definition of continuous. If yu 0, 36 > 0, Val 0(x) A (a' |ol 6) satisfying [f(/)- ,r, we say f(x) is continuous at point sc
Definition of discrete (negative continuous proposition). If 3yx ((x'))(()))) 2 p. we say f() is discrete (not continuous) at point x.
4ō 0, 3xd 5(x) satisfying
Consider proposition 1, Vir
((t))))(((++(( c/. where é',e indicates the observation noise at I.. Ac= (<=) (0, also obeys Gaussian distribution since e' and are independent stochastic variables obeying Gaussian distribution. Hence, P(3x's e ( 2) 1- P(Vx's ((x), - f()) (u) = -[)ss())) P(se E (-μ f(x') + f(2)- f() is almost surely discrete anywhere.
1, since (1) is continuous in 5(x). Therefore, we say that
In our implementation, (S) depends on a discrete set Sn S. We can find a small enough As satisfying Asn S = Ø. Therefore, the property 2 (sparse assumption) is naturally satisfied in our implementation.
B ALGORITHM DETAILS
As the number of observations N increases, the right truncated Poisson distribution gradually approaches to the normal meiiitee & Inal, 2006), which has a smaller computational cost. Hence, we use normal Poisson process model the response surface when N 12.
C SUPPLEMENTARY OF EXPERIMENTS
C.I EXPERIMENTAL SETTINGS ON ROBUSTNESS ANALYSIS
We compare the sensitivity to additive Gaussian noise between GP (value-based) response surface and PoPBO (ranking-basee based) response surface on Forrester function. To simulate the performance of GP, first utilize Gaussian process to fit a certain number of (15 in this paper) observed values and plot the ranking of e.g. 100 points according to the values predicted by GP as Fig. ((a). Meanwhile, our method utilizes Poisson process to directly capture the ranking response surface based the same 15 observations and predict the ranking of 100 points as shown in Fig. 1(b). We observe that our response surface is more robust to noise and can better capture the global ranking.
C.2 DETAILED SETTINGS OF BASELINE METHODS
In this section, we provide the specific details of each baseline mentioned in the paper: "Specifically, sorting function can serve the Rank(-).
12

---

Under review as a conference paper at ICLR 2023
Algorithm 1: PoPBO: Bayesian Optimization with Poisson Process
Inputs:
1) A function Rank(())) to rank samples based on a black-box box function f(-);
A feasible domain (search space) X;
3) An acquisition function a (R-LCB Eq. 11 or ERI as Eq. 12);
4) The number initial points N;
5) The number of total training iterations T
Random sample N initial points S == { from X; Initialize the parameters 0 of (x));
for t := from 1 to 'I' do
Get their rankings R Rank(S):
Learn based on points S and ft by minimizing Eq. 7 with gradient as Eq. 8; Get the next query x² by minimizing acquisition function o;;
Update the set of points $ = {2²}
end
Get the best query Topt in history based on Rank(S)) Output: The best point Topt in history.
Random Search
TPE
SMAC
GP-EI
GP-LCB
PaPBO-ERI
PaPBO-R-LCB
91
Best Acc
Best Ace
Best Ace
90
70
89
68
40
60
80
40
80
Iteration:
Lteration
Iteration
CIFAR-10 valid-set
(b) CIFARI00 valid-set
(c) ImageNet-16-122 valid-set
46
72
Dest Are
44
Dest
70
42
68
40
20
40
60
20
40
20
40
60
80
Iteration
Iteration
Iteration
(d) CIFAR-10 10 test-set
(e) CIFAR100 test-set
(f) ImageNet-166 16-126--102000 120 test-set
Figure 7: Performance trend of random search and Bayesian optimization methods on
201. We run 10 times for each setting and plot the mean accuracy the lines. Note that when testing Random Search, GP-BO, and our PoPBO, we adopt the same initial random seeds for all settings at each run for fairness. Hence, the lines each plot have the same initial point (at the O-th iteration).
Random Search (RS), Following the description in Bergstra & Bengio (2012), we sample candi- dates uniformly at random.
BO with Gaussian Process (GP). follow the settings that described by Snoek et al. (2012) and use the implementation of our own. We use expected improvement (EI) and lower confidence bound (LCB) as acquisition functions and adopt LBFGS to optimize them. When the search space completely discrete like Dong & Yang (2020), which gives the maximizer of the acquisition function among 1000 random samples. For kernel function, use ARD Matérn 5/2 kernel for GP. During the training process, adopt slice sampling,
random sampling to find the next query,
13

---

Under review as a conference paper at ICLR 2023
Protein
Random Search (2012)
9.51 10"5 =3.76 =3,76
10"5
7.89 10 4.18 10
3.01x 10 1.51 10
10 7.45 10
TPE (201))
1.67 1079
4.49
2.55
1.86x 10
1.37
10"2
1000 + 10"
SMAC (201))
2.94 10 3 10-4
1.88x 10 9.38
10
2.05 10 2
1.14x
10:2
3.16
1 10-1
GP (2012)
1 10 1.77 10
620x
2.4
8.6 10-2
4.53
10"2
1.00 47.00
GP (LCB) (2012)
1.38 10 1.77
10-4
5.31 10
2.79
10
8.08 10 1.02
10"2
1,93 x 10 1,30 10
(ERI)
1.18x 10
10-3
10
5.77 3.55 10-4
4.83
10-3
PoPBO (R. LCB)
1.07 x 10 1.000=.. 6.26 10
2.41x 10 1.83
4.82 10 3.91
3.14x 10 1.74 10
Table 2: Regret of the configuration discovered by various methods on the four datasets of HPO- Bench. We run each method for ten times and report the mean and standard deviation. The best performance (lowest mean value and standard deviation) is in bold.
efficient Markov chain Monte Carlo (MCMC) method, fit the hyperparameters of GP, which find to work more robustly for GP.
Tree Parzen Estimator (TPE). Bergstra al. (2011) adopt kernel density estimators to model the probability of points with bad and good performance respectively. Then TPE give the next query by optimizing the ratio between the two estimated likelihood, which is proved be equivalent to optimizing EI. We use the default settings provided in hyperopt package (https: / / / titb..b...
com htmmhhpperott/yypzzra.
SMAC. Hutter et al. (2011) adopt random forest to model the response surface of the black-box function. We use the default settings given by scikit-optimize package (https: / / githhu....................... com/ scikit-optimg ze/ teikiittppiimmi
Unlike Snoek et al. (2012), BOHAMIANN adopts bayesian neural network to build the response surface, whose weights are sampled via stochastic gradient Hamiltonian Monte-Carlo (SGHMC) method. We use the default settings provided in pyban package (https: //github. com/ coam/automla automm/pybnn) and use El as the acquisition function.
BOHAMIANN.
This an effective preferential BO method based on pairwise comparisons, attempting to learn preferences in high-dimensional spaces. We use the default settings provided by PPBO package (https:/ //gtttb..t..//////// com/ Aa Aataaaaa00MM/PO)).
PPBO.
HEBO. Heteroscedastic Evolutionary Bayesian Optimisation that the NeurIPS 2020 black-bor -bx optimisation competition. We use the default strategy and its default parameters provided HEBO package (https: // //gttb..b. com/ hhaawi-nnoee /HBO). For fair comparison, uniform sampling strategy instead of a sobol one during initialization and candidates generation.
C.3 DETAILED RESULTS ON HPO-BENCH AND NAS- AAS-BENCH-201
Table 2 reports the numerical performance of PoPBO and other methods on the four datasets on HPPO-Bench. Fig. 7 displays the performance trend of PoPBO and other methods on the validation set and test set under the search space of TAS-Bencc--25
C.4 IS THE GAIN IN PERFORMANCE OF PoPBO DUE TO THE COMPLEX REPRESENTATION OF MLP IN THE SURROGATE MODEL?
We utilize the same MLP architecture and training settings as PoPBO's to fit the Gaussian likelihood of each candidate. We denote such a setting as GP-MLP. We plot the regret GP-MLP, GP, and our PoPBO on Hartmann and Rosenbrock in Fig. 8. We observe that GP-MLP performs much worse than GP and ours, showing that the complex representation of the MLP in the surrogate model not the main reason for the gain in performance.
C.5 ABLATION STUDY ABOUT THE WORST TOLERANT RANKING K,, IN BRI
Fig. compares the performance of ERI under various settings for the worst tolerant ranking Km.- We observe that PoPBO-ERI is not very sensitive to Km. Specifically, for Branin, ERI with larger
14

---

Under review as a conference paper at ICLR 2023
3.5
10
GP-MLP-LCH PoPBO-ERI
Minimum Regret
3.0
GP-LCB
POPBO-ERI POPBO-R-LCC
Minimum Regref
2.5
GP-MLP-EI
10
GP-MLP-EI
POPBO-R-LCC
2.0
10
1.5
1.0
10
0.5
20
40
60
80
20
40 Iteration
60
80
Iteration
(a) 6-d Hartmann
(b) 6-d Rosenbrock
Figure 8: Performance trend of GP, GP-MLP, and PoPBO Hartmann and Rosenbrock simulated
benchmarks.
10
Minimum Regret
Minimum Rogret
Keurl
10*
Kound
Kear
10
10
Iteration
Iteration
(a) 2-d Branin
(b) 6-d Rosenbrock
Figure Ablation study ERI on the two simulation functions. K Kmar the worst tolerable ranking,
and higher Kmaz leads to higher rate of exploration.
Ki, converges faster but ERI with various Km have similar ultimate performance after 80 iterations. For Rosenbrock that has larger search space and more complex landscape, better exploitation ability more important than exploration, and thus ERI with lower Km achieves better performance.
C.6 MORE ITERATIONS ON 6-D ROSENBROCK FOR GP AND PoPBO
Since 6-d Rosenbrock has a large search space and is hard to converge, we run GP and PoPBO for more iterations (200 queries) and plot the regret in Fig. 10. We observe that PoPBO consistently outperforms GP after 50 epochs. Moreover, both PoPBO-ERI and PoPBO-R-LCB have lower variance than GP-EI and GP-LCB.
C.7 ROBUSTNESS TO VARIOUS NOISE LEVEL.
In our settings, the observations in the simulation function are noiseless, while the observations in the real-world benchmark (HPO-Bench and NAS-Bench-201. are noisy. For HPO-Bench, the
10.
GP-EI
PaPBO-ERI
Minimum Regret
PoPRO-R-L.C
10
2
50
100
150
200
Number of observations
Figure 10: Performance trend of PoPBO and GP by running 200 iterations 6-d Rosenbrock. For each setting, we conduct replicated experiments for six times with various random seeds.
15

---

Under review as a conference paper at ICLR 2023
GP-EI
GP-LCB
PoPBO-ERI
PoPBO-R-LCB
Miniaun Rogres
3.0
Minimum Rogret
3.0
3,0
2.5
2.5
2.5
2.0
2.0
2,0
Minicum
1.5
1.5
1.5
0.5
0.5
0.5
80
Iteration
Iteration
Iteration
(a) 6-d Hartmann (ar
(b) 6-d Hartmann 0.075)
(c) 6-d Hartmann (a 0.1)
Mininum Rogret
Minimum Regret
Minimum Regrot
1
40
60
80
80
Iteration
Iteration
Iteration
(d) 2-d Branin (a 0)
(e) 2-d Branin (a 2)
(f) 2-d Branin (a 5)
10a
10¹
10a
Minimam Regret
20*
10
40
10*
Minimam
10*
Miniman
10²
10'
10*
10"
20
40
60
80
20
40
60
80
20
40
60
80
Iveration
Itration
lteration
(g) 6-d Rosenbrock (a 0)
(h) 6-d Rosenbrock (a 2)
(i) 6-d Rosenbrock (a 5)
Figure 11: Comparison the robustness to noise between GP-BO and PoPBO. We add Gaussian noises with zero mean and various standard deviation the objective function. Notice that Branin and Rosenbrock have much larger range of value than Hartman, so we add noises with larger variance
them.
performance of each configuration (hyperparameters FCNet) is evaluated 4 times under different random seeds. In the experiment settings of EIPO-Bench, the average performance is used as the observation, which is naturally noisy. NAS-Bench-200 attempts to search for neural architecture that performs best after 200 training epochs. However, following the experiment settings of NAS- Bench-201, only the validation accuracy after 12 training epochs of each architecture can be queried, making the observations noisy.
To verify the robustness to noise of PoPBO on simulated benchmarks, we add Gaussian noises with zero mean and various standard deviation (a) Hartmann, Branin, and Rosenbrock simulation functions and run GP-BO and PoPBO separately. Trends of average regret among six parallel tests are plotted in Fig. 11, showing that GP performs worse with the increment of noise level. In contrast, PoPBO performs much more stable. Moreover, PoPBO outperforms GP when the objective function has large noise (a 0.1 for Hartmann, o for Branin and Rosenbrock). The results demonstrate the robustness of PoPBO to noise.
D NOTATIONS
X is the whole feasible domain (search space). X is continuous, |X] is the volume of X. While X is discrete, X is the cardinality of it. S2 {vly E S, fv) < fx)) is the set of better points than r in X, where can be any continuous domain discrete set.
16

---

Under review as a conference paper at ICLR 2023
S is discrete set containing both initial samples for BO and the history queries. Given specific S, (S) is a random variable denoting possible ranking of æ over discrete set Sg S. Hence, (S) depends on S, we utilize hat symbol" to simplify the notation.
E BROADER IMPACT AND LIMITATIONS
This paper addresses the problem of Bayesian Optimization (BO) enable efficient and effective black-box optimization. It has broad applications perception tasks, especially computer vision, robotic control and biology. This, the hand, would facilitate our daily life, and the other hand, we shall be careful about their abuse which may break one's privacy. In this sense, privacy- protection BO also needed for development, and our techniques can also be of specific help for its generality.
17


Reviews:
[{"review_id": "ey5phMFnVAl", "reviewer": "Reviewer_dFd1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces Bayesian optimization modeling and optimizing the ranking of evaluations. \nTo this end, a new surrogate model based on Poisson processes is proposed. \nPairing with the novel ranking-based surrogate model, two acquisition functions are proposed. \nThe method, PoPBO, outperforms existing methods consistently on simulated functions and hyperparameter optimization benchmarks. \nIn addition to its superior performance, by replacing Gaussian processes with Poisson processes, it avoids cubic complexity enabling a significant reduction in runtime.", "summary_of_the_review": "The novelty of the Poisson process surrogate model and its empirical effectiveness with well-paired acquisition functions are the primary contribution of this paper. \nEven though it seems that some aspects of the approach are not covered and the presentation of the idea is a bit unclear, I think these can be improved in the rebuttal. \nOverall, I think the novel contribution of this paper outweighs its weaknesses. \nAs long as the presentation of the idea is improved or my concern about the correctness of some argument is resolved, I would increase the score and support for acceptance of this paper. ", "strength_and_weaknesses": "### Strengths\n- The paper provides a novel surrogate model for ranking which has many advantages over conventional surrogate models for values.\n- Two acquisition functions utilizing a ranking-based surrogate model are proposed. \n- Many aspects of the proposed surrogate model and acquisition functions are empirically covered by ablation studies.\n- Empirically, rank-based BO using the Poisson process surrogate model is shown to outperform existing methods consistently.\n- PoPBO avoids the cubic complexity coming from Gaussian processes, which enables a significant reduction in runtime.\n\n\n### Weaknesses\n- The explanation of the Poisson process surrogate model in 3.1, 3.2, and Appendix A is a bit unclear. (However, in the 'point process interpretation' below, I suggest a different perspective that may allow dismissing the below issues. The authors may want to check that first.)\n    - In Eq.(2), does the definition of $\\hat{R}_x$ depend on the choice of $\\hat{S}$? This does not seem a natural way to define Poisson processes.\n    - In the proof of Prop.1, what does the first line mean? Even without $|x'-x| < \\delta$, it holds that $f(x')-f(x) = \\hat{f}(x')-\\hat{f}(x)+\\epsilon-\\epsilon'$ for all $x$ and $x'$. Why is $\\delta$ necessary?\n    - It argues that since $P(|f(x') - f(x)| = 0) = 0$, $f(x)$ is discrete. But for $f(x)=x$ and $\\sigma=0$, we can say $P(|f(x') - f(x)| = 0) = 0$ as long as $x \\neq x'$, but $f$ is not discrete.\n    - It seems that the inverse of the $\\epsilon$-$\\delta$ method was tried in Prop.1. What was tried to prove is that $f$ is discontinuous everywhere? If not, what is the rigorous definition of 'discrete'? For example, there should be something like 'For $a \\in A \\subset R^N$, $a$ is a discrete point of $A$ if there exists an open neighborhood of $a$ which does not intersect with $A$'.\n    - Also, it is not clear how to conclude the property 2) is derived from Prop.1. Can you elaborate on this?\n- Confusing notations hinder understanding of the idea.\n    - In the 4-th line of 3.2, $\\hat{R}_x (S + \\Delta s | x) - N(S|x)$ seems to mean $\\hat{R}_x (S + \\Delta s) - \\hat{R}_x (S)$.\n      In Appendix A, $N(S|x)$ is used.\n      For the reasons I elaborate below, it seems that using the notation for the count $N(S|x)$ is more natural.\n    - In many lines, $| \\cdot |$ is used for both finite sets and infinite sets. I guess $|\\hat{S}|$ is the number of elements and $|X|$ is the volume of  $X$.\n    - In Eq.(2), I guess it meant $| S_x \\cap \\hat{S} |$ without curly brackets.\n    - In Eq.(4), since for a given set $S$, $\\hat{R}_x(S)$ is a Poisson random variable, it should be either\n$$\n\\hat{R}_x(S) \\sim Poisson(\\int_S \\lambda(s, x) ds) \\quad \\text{OR} \\quad \\hat{R}_x \\sim \\mathcal{P}_n(\\lambda(s,x))\n$$\n\n\n### Other questions\n- **How good is the uncertainty of the Poisson process surrogate model?**\n    - It seems that the trick 'rectification' is crucial in performance. I don't see this as a critical issue when claiming empirical superiority and robustness since a single choice for $q=0.6$ gives good performance on various problems. \nHowever, it may imply that the Poisson process surrogate model may not be good as expected. \n    - Even though the property of the Poisson random variable is pointed out as a possible reason in the paper, I am curious whether it is because of the way how the Poisson process surrogate model is trained.\nIt seems that the way the Poisson process surrogate model is trained is different from how GP, BNN, Deep ensemble, etc are trained.\nGP and BNN are fitted in Bayesian way using posteriors in their prediction. Also, Deep ensemble is claimed to mimic Bayesian inference. However, the Poisson process surrogate model is a single density model fitted with MLE, so poor uncertainty may come from this training procedure.\n- **Point process interpretation** In the below comments, I share my own interpretation to have a better picture of the method. Mostly I am curious about authors' opinions on theses.\n    - On the surface, PP just replaces the absolute response in GP with the ranking response. \nIt seems that from the point process interpretation rather than ranking interpretation, the explanation of the Poisson process surrogate model can be improved. \n    - At each round of PoPBO, the data used to fit the PP surrogate model is the collection of evaluations chosen by PoPBO.\nIt seems that the PP surrogate model this generative process. \nI guess that the probability of a set $\\\\{x_1, \\cdots, x_N \\\\}$ from PP model in PoPBO is\n$$\n\\sum_{\\pi \\in S_N} p(x_{\\pi^{-1}(1)}) \\cdot p(x_{\\pi^{-1}(2)} | x_{\\pi^{-1}(1)}) \\cdots p(x_{\\pi^{-1}(N)} | x_{\\pi^{-1}(N-1)}, \\cdots, x_{\\pi^{-1}(1)})\n$$ \nwhere $p(x_{\\pi^{-1}(n)} | x_{\\pi^{-1}(n-1)}, \\cdots, x_{\\pi^{-1}(1)})$ is the probability that $x_{\\pi^{-1}(n)}$ is selected as the next query given previous $n-1$ evaluations $\\\\{ x_{\\pi^{-1}(n-1)}, \\cdots, x_{\\pi^{-1}(1)} \\\\}$ at $n$-th round of PoPBO. \nSince PP does not consider a sequence but a set ignoring orders, I guess the probability will be the sum of all possible sequences but I believe that it is likely that the sequence appearing in the BO run has the highest density.\n    - The point process interpretation allows a more natural definition of $\\hat{R}_x$ in Eq.(2).\nIn Eq.(2), $\\hat{R}_x(S)$ which should be a Poisson random variable by Eq.(4), depends on $\\hat{S}$, the sampled candidates.\nThen from this definition, it seems that the Poisson process surrogate model also depends on the choice of $\\hat{S}$.\nHowever, in the point process interpretation, $\\hat{R}_x(S)$ is defined as the number of random points $S_x$ where the random points are a set of queries generated by PoPBO.\n    - I guess that when $N$ evaluations are given, then the intensity $\\lambda(s,x)$ is fitted so that $P(\\hat{R}_x(S)=k)$ is the probability that $S_x$ contains $k$ points in the queries suggested by PopBO under the response surface model based on given evaluations, i.e. $\\hat{R}_x(S)$ is the number of points in $S$ whose evaluation is better than $f(x)$, which would be suggested by PoPBO when PoPBO has its model on the response surface based on $N$ evaluations.\n    - Since what the Poisson process surrogate model does is not explained in detail, I tried to reach some reasonable interpretation as above. With the above interpretation, since the Poisson process surrogate model uses $N$ evaluations to have its own picture on the response surface, I guess the current training procedure using MLE on a single probabilistic model could be a weakness of the approach, especially in uncertainty quantification.\n    - With this new definition of $\\hat{R}_x$ without $\\hat{S}$, it seems that the truncation in Eq.(5) is not necessary anymore, which is also aligned with what is done in the implementation.\n    - Moreover, the point process interpretation can remove the necessity of the justification that $\\hat{R}_x$ is the Poisson process in Appendix A, which is a bit confusing.\n    - With this description of what PP models, it can be interpreted that PP in PoPBO is kind of a generative model in contrast to the discriminative model of GP. \nBy modeling how input points are generated, the generative process may model how the next queries are chosen.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "T2MbPQebXW", "reviewer": "Reviewer_v6dz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a method for Bayesian optimisation based on Poisson processes. The interesting concept is that the authors introduce novel ranking response surfaces in addition to two acquisition functions that exploit the proposed model. They perform experiments on various benchmarks and demonstrate favourable results compared to the baseline technique.\n\nThe paper is well-written, easy to follow, and nice to read. \n", "summary_of_the_review": "Please see above.", "strength_and_weaknesses": "Strengths: \n- Well-written paper \n- Clear set of contributions \nWeaknesses: \n- Experimental study: Although the authors perform an extensive experimental study, I am left wondering why HEBO (heteroscedastic and evolutionary Bayesian optimisation) is not a baseline? The reason I ask is that such an approach introduces input and output warping functions to `correct' the noise process of the observed data. It also changes the acquisition to a multi-objective one. It has also been demonstrated to outperform some of the baselines presented in the paper. I would like to kindly ask the authors to baseline and compare against newer SOTA methods (HEBO being one of them). \n- The authors demonstrate that their techniques enjoy lower computational complexity of O(N^2) compared to the GP O(N^3). This is interesting and worth emphasising. However, how does this compare to induced point GPs? Can the authors perform scalability experiments compared to variational GPs for instance? What would the cost look like in this case? \n-  In Figure 2, it seems that on 2d Branin and 6d Hartmann, GP-EI performs the best. If that is the case, when should we use the algorithm proposed by this paper versus standard BO? Can the authors help give guidance on the applicability domains of their technique? \n- The same question goes for when to use R-LCB versus ERI. Can the authors elaborate on those results in accordance with Table 1? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JCMcNJWlKwn", "reviewer": "Reviewer_rWSY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This work proposes a novel modeling approach within the Bayesian optimization (BO) framework. More concretely, it proposes to use a (truncated) Poisson process to model the ranking induced by the underlying objective function over a feasible domain. It is argued that such an approach is more robust to noise in the objective function observations. Two acquisition functions inspired by the GP-UCB and EI acquisition functions are proposed. The performances of the proposed approach and several benchmarks from the literature are compared across several synthetic and realistic test problems, showing favorable results.", "summary_of_the_review": "This work proposes a novel probabilistic model within the Bayesian optimization framework. While I have some concerns about the proposed approach, it is technically sound overall, and its empirical performance is promising. Unfortunately, this paper is tough to follow, with several missing details and poor descriptions. In addition, the proposed acquisition functions, which would play a significant role in making the proposed modeling approach successful in practice, seem too heuristic and complicated to use due to their dependence on hyperparameters. Overall, I believe this work requires significant improvements to merit publication at a venue such as ICLR.", "strength_and_weaknesses": "Strengths:\n1. The proposed modeling approach is novel and technically sound.\n2. The empirical performance of the proposed approach is promising. \n\nWeaknesses:\n1. The problem setting and proposed probabilistic model descriptions are hard to follow. For example, it is not specified what the observations are. This is more clearly articulated in the supplement, where the ranking function is mentioned. The description of the probabilistic model is also hard to follow since MLP and $\\theta$ are not defined. \n2. The proposed acquisition functions are too heuristic. They both rely on hyperparameters which seem to affect their performance significantly. It would be more appealing to derive an acquisition function based on an information-theoretic or decision-theoretic analysis.\n3. Some aspects of the empirical evaluation were not specified. For example, was the domain discretized? If not, how is $|X|$ handled in equations 6-9? Also, was noise added to the objective function observations in the numerical experiments? If so, this should be stated. Moreover, the effect of the noise level should be assessed to support the claim that the proposed approach is more robust to noise than standard BO approaches.\n4. The proposed modeling approach is technically sound overall. However, the independence of rankings over disjoint sets seems counterintuitive. In general, one would expect the rankings of nearby regions to be correlated.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IIgJtmfjf_a", "reviewer": "Reviewer_55na", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes to use relative function evaluation, in particular, ranking, to guide the Bayesian optimization (BO) process. The argument is that relative response is more robust to noise than absolute response, thus, if we model the objective function by relative response, the performance of the BO process might be better. The paper proposes to use Poisson Process to model this relative response, and then propose two new acquisition functions for their proposed method that are based on the LCB and EI acquisition functions. Finally, the paper evaluates the proposed method on some synthetic and real-world problems.", "summary_of_the_review": "Even though I like the main idea of the paper, but I still have various concerns regarding the rigorousness and soundness of the proposed method. These concerns include both the theoretical and empirical aspects of the paper. Please refer to my comments above.", "strength_and_weaknesses": "Strengths:\n+ Overall, I think the idea of modelling the relative response and use this model to guide the BO process is interesting and new.\n+ The paper writing is also easy to understand in general (except the mathematical formulas).\n+ The proposed method has good performance on some problems.\n\nWeaknesses: I still have various concerns regarding the paper, especially, its rigorousness. Please find in the below my concerns:\n+ The sentences \"Considering the physical meaning of S_x, we can estimate the superiority of x for f(⋅) against the points in set S by measuring S_x. Specifically, considering two points x1, x2, S_x1 has a larger measure value, representing that there are more points in S better than x1, so x1 is worse than x2.\" in Section 3.1 are ambiguous and are not clear to understand. What do we mean by \"measuring S_x\", S_x is a set, so what property we want to measure? Here, I think the paper means to say we need to come up with a metric/value to quantify S_x?\n\n+ The important notations in the paper are unclear and confusing, which make it hard to understand the maths behind the proposed method. For example, I don't understand Eq. (2), in particular, why the notation \\hat{R}_x(S) does not depend on \\hat{S}. Does this mean for any set of sampled candidates \\hat{S}, the value is \\hat{R}_x(S) is the same? Later, in Section 3.2, whenever the term \\hat{R}_x(S) is mentioned, there is no mention about \\hat{S} anymore. This really confuses me. Also, if I read the notation correctly, is Q a set of sets? Also, what is a set of sampled candidates (the notation \\hat{S} in the paper)? \n+ I also have more concerns regarding the measure \\hat{R}_x(S). For continuous domain X, will \\hat{R}_x(S) be infinite? As the cardinality of all the sets will be infinite. In this case, then I don't understand how the proposed method will work.\n+ In Figure 1, the paper illustrates the relative response surface with a Gaussian Process, but later, a component of the Poisson process is approximated by MLP, so I don't know if the gain in performance is due to the relative response (ranking) idea or due to the complex representation of the MLP in the surrogate model.\n+ In the R-LCB acquisition function, in Eq. (11), what is \\epsilon_x? how to compute it? \n+ In the ERI acquisition function, in Eq. (12), K_m is a hyperparameter. How is the performance of BO sensitive to this value? More discussion is needed.\n+ For the 6-d Rosenbrock function, I expect more iterations (e.g., 20-30d) to be conducted as 80 iterations are a bit small compared to the dimension and complexity of this function.\n+ Most importantly, in the experiments, are the observations of the objective functions (Branin, Hartman, Rosenbrock) noisy? And what will be the noise in the real-world benchmark problems? I can't find any information in the main paper. This is critical as robustness to noise is the main argument of the paper regarding the advantage of the proposed method over the standard BO methods.\n\nMinor comments:\n+ Some definitions about \"relative evaluation\" and \"absolute response\" should be explained early in the paper. In the introduction section, when these terms are first mentioned, I had some difficulties in understanding what they mean.\n+ I think the relative evaluation is still sensitive to noise, it's just not as severe as absolute response. So, it's better to say it is harder to be disrupted to noise (not hard to be disrupted by noise as in many places in the paper).\n+ I think the statement about \"absolute response surface has poor transferability\" is too overstated. It has been shown that warm-starting (reuse the data from other tasks) is very useful in BO and HPO, therefore, this shows that it is possible to transfer knowledge from other tasks to a new task in the BO or HPO process. \n+ The contribution \"Efficient BO Framework\" seems to be too generic. Here, the paper means computational efficient?\n+ First sentence of Section 3.1: block-box --> black-box\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject