Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strengths:
1. The proposed modeling approach is novel and technically sound.
2. The empirical performance of the proposed approach is promising. 

Weaknesses:
1. 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. 
2. 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.
3. 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.
4. 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.
clarity,_quality,_novelty_and_reproducibility: As described above, this paper is tough to follow since several critical pieces of information were omitted. Moreover, the code to reproduce the experiments was not included. Thus, this work performs very poorly in terms of clarity and reproducibility. The proposed modeling approach is novel and technically sound. On the other hand, the proposed acquisition functions seem too heuristic and hard to trust in practice. Overall, I believe this paper enjoys significant novelty but low execution quality.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

The paper is well-written, easy to follow, and nice to read. 

strength_and_weaknesses: Strengths: 
- Well-written paper 
- Clear set of contributions 
Weaknesses: 
- 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). 
- 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? 
-  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? 
- The same question goes for when to use R-LCB versus ERI. Can the authors elaborate on those results in accordance with Table 1? 


clarity,_quality,_novelty_and_reproducibility: The paper is well-written, and I enjoyed reading it. I am happy to change my scores per the rebuttal and the execution of the extra experiments.
summary_of_the_review: Please see above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces Bayesian optimization modeling and optimizing the ranking of evaluations. 
To this end, a new surrogate model based on Poisson processes is proposed. 
Pairing with the novel ranking-based surrogate model, two acquisition functions are proposed. 
The method, PoPBO, outperforms existing methods consistently on simulated functions and hyperparameter optimization benchmarks. 
In addition to its superior performance, by replacing Gaussian processes with Poisson processes, it avoids cubic complexity enabling a significant reduction in runtime.
strength_and_weaknesses: ### Strengths
- The paper provides a novel surrogate model for ranking which has many advantages over conventional surrogate models for values.
- Two acquisition functions utilizing a ranking-based surrogate model are proposed. 
- Many aspects of the proposed surrogate model and acquisition functions are empirically covered by ablation studies.
- Empirically, rank-based BO using the Poisson process surrogate model is shown to outperform existing methods consistently.
- PoPBO avoids the cubic complexity coming from Gaussian processes, which enables a significant reduction in runtime.


### Weaknesses
- 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.)
    - 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.
    - 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?
    - 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.
    - 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$'.
    - Also, it is not clear how to conclude the property 2) is derived from Prop.1. Can you elaborate on this?
- Confusing notations hinder understanding of the idea.
    - 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)$.
      In Appendix A, $N(S|x)$ is used.
      For the reasons I elaborate below, it seems that using the notation for the count $N(S|x)$ is more natural.
    - 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$.
    - In Eq.(2), I guess it meant $| S_x \cap \hat{S} |$ without curly brackets.
    - In Eq.(4), since for a given set $S$, $\hat{R}_x(S)$ is a Poisson random variable, it should be either
$$
\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))
$$


### Other questions
- **How good is the uncertainty of the Poisson process surrogate model?**
    - 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. 
However, it may imply that the Poisson process surrogate model may not be good as expected. 
    - 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.
It seems that the way the Poisson process surrogate model is trained is different from how GP, BNN, Deep ensemble, etc are trained.
GP 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.
- **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.
    - On the surface, PP just replaces the absolute response in GP with the ranking response. 
It seems that from the point process interpretation rather than ranking interpretation, the explanation of the Poisson process surrogate model can be improved. 
    - At each round of PoPBO, the data used to fit the PP surrogate model is the collection of evaluations chosen by PoPBO.
It seems that the PP surrogate model this generative process. 
I guess that the probability of a set $\\{x_1, \cdots, x_N \\}$ from PP model in PoPBO is
$$
\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)})
$$ 
where $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. 
Since 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.
    - The point process interpretation allows a more natural definition of $\hat{R}_x$ in Eq.(2).
In Eq.(2), $\hat{R}_x(S)$ which should be a Poisson random variable by Eq.(4), depends on $\hat{S}$, the sampled candidates.
Then from this definition, it seems that the Poisson process surrogate model also depends on the choice of $\hat{S}$.
However, 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.
    - 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.
    - 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.
    - 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.
    - 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.
    - 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. 
By modeling how input points are generated, the generative process may model how the next queries are chosen.
clarity,_quality,_novelty_and_reproducibility: As mentioned in 'Weaknesses', I think there is room to improve for a better presentation of the idea. I guess the suggested 'point process interpretation' may help to resolve to improve the clarity.
Among others, I value the novelty of the Poisson process surrogate model. 
The Poisson process has been studied extensively and there are many extensions of it, this paper can stimulate the development of various surrogate models utilizing the theory of Poisson processes.
Despite my concern about the explanation of the surrogate model, all implementation detail and algorithms seem to be provided with enough detail to try this PoPBO.
Along with detailed information on the implementation, the empirical analysis is reasonable enough to show the superiority of the method accompanied by many ablation studies.

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. 
Even 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. 
Overall, I think the novel contribution of this paper outweighs its weaknesses. 
As 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:
+ Overall, I think the idea of modelling the relative response and use this model to guide the BO process is interesting and new.
+ The paper writing is also easy to understand in general (except the mathematical formulas).
+ The proposed method has good performance on some problems.

Weaknesses: I still have various concerns regarding the paper, especially, its rigorousness. Please find in the below my concerns:
+ 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?

+ 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)? 
+ 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.
+ 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.
+ In the R-LCB acquisition function, in Eq. (11), what is \epsilon_x? how to compute it? 
+ 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.
+ 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.
+ 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.

Minor comments:
+ 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.
+ 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).
+ 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. 
+ The contribution "Efficient BO Framework" seems to be too generic. Here, the paper means computational efficient?
+ First sentence of Section 3.1: block-box --> black-box

clarity,_quality,_novelty_and_reproducibility: The paper writing is also easy to understand in general (except the mathematical formulas which are confusing) - please refer to my comments above.

I have various concerns regarding the quality of the paper - please refer to my comments above.

I think the main idea of the paper is interesting and new - please refer to my comments above.

There is no code uploaded as part of the submission.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers Bayesian optimization where we observe rankings over points' rewards, rather than the rewards directly. This has the potential to be more robust to noise. The paper proposes a truncated Poisson process surrogate and two novel acquisition functions. The proposed method is evaluated on several synthetic and real-world problems.

Strengths
- The idea of using rankings rather than absolute observations seems valuable
- Novel approach 
- Evaluation shows consistent improvement over existing methods
- New method offers reduced runtime over standard Gaussian processes

Weaknesses
- Proposed acquisition functions lack justification and are sensitive to their hyperparameters
- Substantial lack of clarity, both in terms of the problem setting, model, and experimental evaluation. 
- The reviewers raised several concerns about the rigor of the analysis: dFd1's first and second weakness; the concerns about the paper's rigor from 55na, and rWSY's concern that rankings over disjoint sets cannot be treated as indpendent. Some of these may simply be due to a lack of clarity and small errors in mathematical descriptions, but the concern about independence of rankings over disjoint sets remains substantial following a detailed and careful discussion between rWSY and the authors.
justification_for_why_not_higher_score: - Concern about rigor
- Lack of justification for proposed approach
Decision: Reject