Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper develops a new approach for local Bayesian optimization by incorporating gradient into the Bayesian optimization as in the work by Muller et al [13] but instead of moving in the direction of the expected gradient, the paper proposes to identify the direction of most likely descent, and then move in that direction. To do so, the paper derives a closed-form solution for the direction of most likely descent at a given location in the input space under a GP belief about the objective function. A corresponding closed-form acquisition function that optimizes (an upper bound of) the one-step maximum descent probability is also developed to form the optimization scheme. Experiments on both synthetic and real-world tasks are conducted to demonstrate the performance of the proposed approach.

################################ AFTER REBUTTAL ###################################
Thanks authors for your detailed response. I understand more about the behaviours of the proposed approach and I do not have any concerns about the Hopper function anymore. I have been thinking again about the work, and I think maybe I'm indeed picky, so I decided to increase my score to 6.
strengths_and_weaknesses: Strengths: The paper is very well-written. All the concepts and the proposed approach are described clearly and easy to understand. The idea of incorporating the gradient information into the optimization process and move to the direction of most likely descent is sound and reasonable. Rigorous mathematical formulas are developed to derive the key components of the proposed approach (the direction of most likely descent and the acquisition function). The proposed approach has good performance in some objective functions.

Weaknesses: Some of the weaknesses of the paper are as follows:

•	Maybe I'm picky but I think the idea is not too novel as it feels like it just fixes a particular issue of an existing BO approach. I do appreciate all the analysis conducted to show the issue of the approach in Muller et al [13] and all the derivations to find the most likely descent direction and to compute the new acquisition function. However, I normally expect the key idea to be more novel, and if it's not too novel, I expect the experiment results to be very impressive. In this case, the experiment results are not really that impressive. The proposed approach does have some very good performance on some objective functions; however, it also performs on par with other baselines in multiple objective functions, and it performs worse for some objective functions. 

•	The proposed approach is developed for the batch setting; however, only sequential setting (batch 1) is conducted in the experiments. 

•	The paper seems to lack of the discussion about some benchmarks on Bayesian optimization with gradient, for example the work Bayesian Optimization with Gradients by Wu et al (NeurIPS 2017).

•	I expect more sensitivity analysis and discussions on some hyperparameters of the proposed approach such as p^*.

questions: Apart from my comments in the Weakness section which the authors can response, I have the following additional questions:

•	How does the hyperparameter p^* affect the performance of the proposed approach?

•	What can be the reasons that the proposed approach performs badly for the objective function 33D Hopper?

limitations: The paper has some discussions on the societal impact of their work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies local Bayesian optimization in which a GP surrogate is used to give a model for the gradient at a point, an acquisition function is used to select points that are informative about the gradient, and then gradient steps are taken to select the next point for evaluation. Past work has used information gain about gradient for acquisition, and the direction of negative expected gradient for taking the gradient step. This paper builds on that work by showing that it is better to move in the direction that maximizes the probability of descent, which because of posterior uncertainty in the gradient, is not necessarily the negative expected gradient. It shows how this quantity can be computed, and then proposes an analytic acquisition function that targets the same quantity. Empirical results show strong performance relative to the work that this builds on, as well as other related work in this same problem space.
strengths_and_weaknesses: I found this paper to be very interesting. It studies an important problem (high-dimensional BO). While it does build directly on top of existing work and so does not present an entirely new approach to the problem, it gives a very insightful analysis into the failure cases for that existing work and does a great job at motivating the new method. The paper is very clearly written and the work is of high quality.

The new method is surprisingly elegant, and is strongly motivated by a very clear mathematical analysis as well as a great illustration in Fig. 1.

The empirical results are very strong and compare to what I think are the most appropriate baselines. An ablation study is included, as are real-world problems.

Below I give a few questions that I had that I expect other readers may be interested in as well, though I consider these all to be minor issues.
questions: When we observe the new value f(x_{t+1}), do we always accept the move from x_{t} to x_{t+1} or do we accept it only if f(x_{t+1}) < f(x_{t})? I imagine that observing x_{t+1} will update the gradient information at x_{t}, so even if we do not accept the step and we repeat the acquisition optimization around the same x_{t} as in the previous optimization, we should take different steps. It sounds from the paper that we are always accepting steps, but I wonder if that is the best strategy.

Is there anything about the 33D Hopper problem that explains why it performs worse?

Was the RBF kernel ARD?

The paper gives results on sensitivity to p* but only for more conservative choices; what about e.g. 0.5?
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a local Bayesian optimization strategy via maximizing a probability of descent.  Unlike the previous work (Muller et al. 2021), this work computes the most likely descent direction by considering the problem of the expected gradient.  More precisely, as described in the paper, the expected gradient is not necessarily the direction maximizing the probability of descent.  The proposed method solves this problem by computing the most likely descent direction.  Finally, the authors demonstrate that the proposed method works well in various experiments.
strengths_and_weaknesses: ## Strengths

+ It solves an interesting topic on local Bayesian optimization.

+ It suggests a novel method by raising the drawbacks of the existing method.

+ Experimental results do not always show the best results, which is very reasonable.  But please describe more thorough analyses on these results.

## Weaknesses

- I do not have specific weaknesses, but writing and presentation can be improved to clearly demonstrate the contributions of this work.

Please see the text box described below.
questions: I would like to ask the authors some questions.

1. In Line 88, a sentence, `Our work addresses this gap.` should be re-written.  Please clearly write the sentence by including what this gap is in the sentence.  I understand that it is not a final version, but please fix it in the final version.

1. In Equation 4, why is an acquisition function over a batch of potential query points?  I think that an acquisition function over a single query is tested (as in Algorithm 1).

1. Please add line numbers in Algorithm 1.

1. In experiments, why are some results fluctuated?  Why are not the best minimum (or maximum) values plotted?
limitations: I do not think that this work has any negative societal impacts and any specific limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper aims to improve Bayesian optimization in high-dimensional search spaces by proposing a new technique for local optimization. The authors build on prior work on local policy search with bayesian optimization (GIBO) by 1) showing that the expected value of the gradient may not coincide with the maximum probability of descent, and 2) proposing an optimization scheme which directly optimizes the probability of descent. In experiments, the approach tends to outperform GIBO as well as other more complicated baselines proposed in the literature.
strengths_and_weaknesses: **Clarity**

The paper was a pleasure to read. Very well-written, easy to follow and self-contained, with enough background on both general and local Bayesian optimization to bring the reader up to speed. It also includes great visualizations (Figure 1) that help build intuition on the behavior of the proposed approach.

**Originality / Significance**

The problem of scaling up Bayesian optimization to high dimensional spaces is significant and the paper builds on the success of local optimization techniques. Showing that the most likely descent direction does not always coincide with the negative expected gradient is an interesting result, worth of value on its own even if unplugged from the resulting method.

While to some extent the work incrementally builds on GIBO, the results improving the local optimization routine are general and can be plugged in any existing approach relying on local optimization (e.g., McLeod et al., Wang et al.). As such, the impact of the method is broader as improved results could potentially be observed for each of these baselines. For this reason, I would have liked to see experiments validating the hypothesis that the proposal is in fact a useful subroutine to replace previous local optimization across the board. This would have further increased the significance and breadth of impact of the paper.

**Quality**

The paper's quality is overall high. The experimental evaluation is carefully carried out and includes ablation studies aiming at separating out the two key contributions of the proposed MPD approach (i.e., the learning phase or the update phase). From these results, it turns out that MPD does not perform consistently better against GIBO when one of the two new components is removed. This shows that both components need to be used in tandem to achieve improved results.

The proposal is theoretically grounded and the empirical evaluation is overall solid. The results show that the proposed approach tends to outperform baselines and particularly so as the dimensionality of the space grows on synthetic functions. While very promising and clearly outperforming baselines on these examples, the gap is not as pronounced on real-world objectives (Figure 3) and MPD is clearly worse on 33D Hopper. It is expected that not 100% of problems will show the benefits of MPD, but I would have liked the authors to elaborate and give intuition as to why there is such a clear drop in 33D Hopper.

Beyond that, I particularly appreciated the results on interesting real-world problems. This sets an example for work in the BO space to evaluate the proposed methods beyond standard problems, such as those from hyperparameter optimization.
questions: 1. Do the authors have any intuition as to why swapping either of the components of MPD does not consistently improve over GIBO in the ablation study? Would we not have expected either one of the two components in isolation to already be an improvement? This may or may not be the case, but I would have liked the authors to give more intuition on this result.
2. Have the authors considered additional ablation studies to quantify the advantages of MPD's local search when plugged as the local routine in McLeod et al. or Wang et al.? While not strictly within the scope of the paper, demonstrating the benefits of MPD as a general technique that can boost existing local optimization method would step up the impact of the paper.
3. [key question] How did the authors come up with the default policy using p∗ = 65%? Since the ablation studies show that the results are to some extent sensitive to this choice, it is important to understand if 1) this is a general purpose default recommendation, and 2) how the recommendation was obtained (i.e., whether it was obtained on a given validation set before comparing to the baselines in Table 1).
4. Have the authors also run ablation studies on the step size, which was set to δ = 0.001? Any insights on the impact of larger and lower step size values?
5. Minor: Some of the compared baselines in Figure 2 do not seem to have fully "converged" (e.g., ARS on the 100D objective). If run for more queries, do all methods get to the same optimum? Do we observe any changes in ranking? While the used budget is arguably already very high, this would be interesting to confirm that on top of being the more query-efficient approach, MPD also tends to consistently converge to th best solution in the long run.
6. Do the authors have any insights into what makes 33D Hopper so different from the other problems that lead MPD to be subpar compared to all three baselines? This is surprising as for very high dimensional spaces, the advantage of MPD was more pronounced on the synthetic functions.
7. The evaluation considers number of queries on the x axis. What's the computational cost of the MPD local optimization step compared to baselines such as GIBO? What would the results look like with wall-clock time no the x axis?
limitations: The authors have adequately discussed the potential negative societal impact of the work, which coincides with the risks of any BO and generally AutoML black-box system (i.e., it can be exploited for malicious purposes). I agree with the authors that the benefits of the proposal outweight these risks.

Beyond that, I believe the main limitations lie in the empirical section, due to some mixed results and the lack of clarity on the process that led to the choice of the method settings (probability of descent and delta). More details in the questions above. I am ready to increase my score if these questions are addressed.
review_title: null

Meta-review: metareview: All reviewers are positive and agree that the paper should be accepted. The primary question raised about the poor performance on Hopper was adequately addressed by the author response. Please integrate the changes and reviewer suggestions around clarity into the final paper.
confidence: Certain
Decision: Accept