Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper focuses on Bayesian Optimization and utilizes Gaussian Processes (GPs) with ensemble tree kernels. The proposed approach advocates a mixed-integer second-order cone optimization formulation, relying on the lower confidence bound (LCB) acquisition criterion, that allows for uncertainty quantification and readily accommodates the incorporation of input constraints. Numerical tests show the benefits of the proposed framework compared to existing methods in the literature. 
strengths_and_weaknesses: STRENGTHS 

- The ensemble tree kernel GP - based approach is intuitive and seems to work well in practice. 
- The paper is well written and the ideas of the paper are well presented.

WEAKNESSES 

- The novelty of the paper is somewhat limited. The ensemble tree kernel is known and the same holds true for Eqs. 3 and 4. In my mind, the advocated approach is just a combination of some intuitive well-known components. 
-  Additional experiments are needed to corroborate the benefits of the proposed approach compared to existing methods in the literature. Except the GP-UCB approach which is indeed a good baseline, there exist many other well-known acquisition criteria combined with GP surrogate model such as Expected Improvement (EI), Thompson Sampling (TS), Entropy Search (ES) and Predictive Entropy Search (PES) to list a few. So, in my opinion it is important to compare with some of these approaches to better demonstrate the benefits of the advocated method, and especially with the EI which seems to be very effective in several BO problems. In addition, there exist some very interesting ensemble approaches that can effectively handle continuous-categorical data; see e.g [1], [2]. A numerical comparison (or even discussion) with these approaches would also be nice. 

[1] Gopakumar, Shivapratap, Sunil Gupta, Santu Rana, Vu Nguyen, and Svetha Venkatesh. "Algorithmic assurance: An active approach to algorithmic testing using bayesian optimisation." Advances in Neural Information Processing Systems 31 (2018).
 
[2] Nguyen, Dang, Sunil Gupta, Santu Rana, Alistair Shilton, and Svetha Venkatesh. "Bayesian optimization for categorical and category-specific continuous inputs." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 5256-5263  (2020).

questions: Some minor comments are listed below:
- In Eq. 6b, instead of $\sigma^2$ it should be $\sigma^2(\mathbf{x})$.
- In line 51, instead of “prior work” it should be “prior works”.
- In line 118, instead of “where data is sparse” it should be “where data are sparse”.
- In line 167, instead of “We compute constant matrix”, it should be “We compute the constant matrix”. 
- In line 199, in the phrase “we found that Gurobi 9 often solves” a citation is needed.

limitations: The limitations subsection is well written. Some additional concerns of mine are mentioned in the “Strengths and Weaknesses” section of the review.
review_title: null

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 framework for Bayesian optimization with mixed-type features and flexible feature constraints. The idea is to utilize a GP model with a kernel function based on tree ensembles that can naturally handle mixed-type features. A mixed-integer optimization technique is used to minimize the piecewise-constant LCB acquisition function. The proposed method shows promising performance in various benchmarks.
strengths_and_weaknesses: Strength:

* A novel framework for Bayesian optimization to handle mixed-type features and flexible feature constraints.
* Promising performance in various benchmarks.

Weakness (see major comments below for details):

* Training of the surrogate model is unclear.
* The experiment in Section 5.1 does not seem solid.
* The paper could benefit from additional sensitivity and timing results.
questions: Major comments:

1. As far as I understand, there are two possible ways to train the proposed surrogate model with a tree ensemble kernel: (i) treat the tree structure as a kernel hyperparameter and learn it by maximizing marginal likelihood (which is an end-to-end approach and provides a coherent statistical model), and (ii) fit the tree structure first by gradient boosting, and then fit a GP model with the given tree structure (which does not seem to be a well-defined statistical model to me). It is unclear to me which approach is used. If (ii) is used, what are the responses used to train boosting trees?

2. The experiment in Section 5.1 aims to verify the uncertainty metrics. However, in Eq. (12a) only the posterior mean is included while the posterior variance (which accounts for uncertainty) is missing. Moreover, the plots in Figure 2 only show the error for the mean prediction, which again does not convey any information on uncertainty. It is unclear to me how the conclusion in Section 5.1 is reached and why the constraint in Eq. (12c) is needed.

3. Since the posterior mean and variance from the tree-kernel GP are piecewise constant functions corresponding to the tree partitions, I wonder how sensitive the performance is with respect to the tree ensemble hyperparameters such as the number of boosting iterations.

4. How is the proposed method compared to its competitors in terms of computation time? I would expect the sparsity in the tree-based covariance matrix can reduce computation for GP.

Minor comments:

* I think the notations in Section 3.3 are quite confusing and should be clearly defined. For example, what do $v_{i, j}$, $\nu_{i, j}$ and $\mathrm{splits}(t)$ mean?
* In Eq. (5a), I understand that the optimization is done over $\mathbf{x}$. But since $\mathbf{z}$ is a function of $\mathbf{x}$ given the tree structures (as in Section 3.1), it should not be included under $\mathrm{argmin}$. It is also not clear what $\nu$ is.
* Line 98: Leaf subspace $\mathbf{x}_l \in \mathbb{R}^n$ -> $\mathbf{x}_l \subset \mathbb{R}^n$.

limitations: Please see the major comments above.
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 proposes a feasible way to perform Bayesian optimization using ensembles of decision trees. Although it is easy to use decision trees ensembles to predict a mean and variance (and therefore formulate acquisition functions like upper confidence bounds), _optimizing_ these acquisition functions is challenging because they are piecewise constant. The key insight of this paper is that if the decision tree predictions are used to form a GP kernel, upper confidence bound acquisition function can be formulated as a conic problem and be inputted into a generic solver to find the global optimum. A secondary advantage of this approach is that the solver can also tolerate a large number of constraints from a variety of families, which is practically useful.

The authors provide the technical details of this formulation and show that it works well for a variety of synthetic optimization problem and one real-world problem over mixed-variable, hierarchical spaces.
strengths_and_weaknesses: Overall I thought that this paper was very good.

### Strengths

- **Very relevant problem choice**: trees are one of the few models that can easily handle mixed-variable/hierarchical data, _and_ work well on small datasets. To my knowledge, optimizing the acquisition function is a significant hurdle preventing the widespread use of tree ensembles in Bayesopt.
- **Elegant solution**: formulating the acquisition function as a cone problem allows for decades of research on convex solvers to be applied. This is a clever insight. It is nice to see a (semi-)exact solution to an optimization problem presented at NeurIPS, where most papers tend to use approximations which are hard to verify.
- **Extremely well-written**: this paper is definitely in the top 10% of writing quality. Everything was extremely clear. I especially appreciated the discussion of the related work and the technical background (section 3). The technical details in section 4 were very well presented. I don't know if I would 100% be able to implement the method based on the paper (the explanation of $\nu$ and $v$ in equations 3-4 could be slightly clearer), but it is closer to this ideal than perhaps 90% of papers at NeurIPS. Also, unlike many ML conference papers, it did not feel like the authors crammed a 12 page paper into 9 pages by moving important explanations/equations into the appendix, which I really appreciated.
- **Highly Usable**: this method seems like it should work "out of the box" (assuming access to a conic solver) because it is simple and could be plugged into any decision tree package. I highlight this because I feel like most methods presented at generally do not work "out of the box" because they are brittle, require a lot of tuning, or have undisclosed limitations.

### Weaknesses

- **Several technical details unclear**: see "Questions" section. These are not absolutely critical to the paper but I would appreciate clarification.
- **Unclear effect of "different objective" vs "exact solution"**: the proposed method has 2 deviations from using the empirical mean/variance of a tree ensemble for Bayesopt: 1) making predictions with a tree kernel GP instead of empirical mean/variance 2) optimizing UCB exactly using a cone solver. In section 5 it was generally unclear to me how much of the difference in final performance came from using the trees to make predictions in a different way (GP instead of empirical mean/variance), and how much came from performing [nearly] exact maximization of the acquisition function. A good experiment to do would be use the GP formulation to find a promising set of candidate points (perhaps using multiple seeds), then use the original empirical mean/variance UCB objective to select a point to query in the end. This would be combining "exact optimization" with the standard way of making predictions.
- **Code requires a non-public library** gurobi. This is not a deal-breaker, and I realize there are academic licenses available, but it would be really nice to have a fully open-source version for the camera-ready paper. I ask some additional questions about the choice of solver below.

### Suggestions

- Given that the paper focuses specifically on non-continuous spaces, why is $x$ defined to be a real number when introducing Bayesopt on line 44? I think $x$ should just be an element of a general space $\mathcal{X}$
- Many readers at NeurIPS may not be very familiar with cone problems / conic solvers. It would be nice to put some information on these in the background, even if it is just a short section saying that "it is a very general way of formulating certain optimization problems, with a variety of established methods for solving them"
- "LCB" is a fairly uncommon formulation of Bayesopt; I think many readers are accustomed to seeing problems posed as UCB _maximization_. Perhaps it would be slightly helpful to the reader to frame the problem as maximization and multiple everything in the paper by $-1$?
- I saw in the appendix that you use Adam to optimize GP kernel hyperparameters. One problem with Adam is that it may converge very slowly if the learning rate is too low, or not fully converge if it is too large. Especially since you are only optimizing 2 hyperparameters, I recommend using L-BFGS instead. In my personal experience this method is much more robust.
- The objective in equation 12 would also be another interesting baseline to see: it would show how much the GP variance actually contributes, as opposed to just finding a point with a sufficient amount of disagreement among ensemble members.


### Overall

Originality: seems high, but I am not very familiar with related work in this area

Quality: high, good paper, good method, good evaluation

Clarity: very high!

Significance: high. The proposed method solves a real problem and is likely to be used in practice, especially if a good open-source library is published.

I definitely recommend accepting this paper and my score reflects that. I would consider increasing my score slightly if my suggestions are addressed. I could also imagine decreasing my score if:
- The novelty is not as high as I thought (I am not very familiar with related work in this area, so perhaps there is a paper that does something very similar which was not cited)
- There were technical flaws that I did not catch (I know only the basics of convex optimization/cone problems, so this is possible)
questions: - Trees are effectively parametric methods: once trained on data, updating the trees generally requires retraining. This is in contrast to the GP with the tree kernel, which will make different predictions conditioned on new data even if the underlying trees are not retrained. _In your baseline experiments, do you keep the trees fixed or do you retrain them?_ If you are not retraining them, this could explain the roughly constant performance of the baselines in e.g. Figure 4. I think that you should be retraining them.
- _Do all tree-based methods use the same underlying trees?_ To minimize external sources of variation, I think that the trees in SMAC/skopt should be the exact same trees used in the GP kernel. If this is not possible/extremely hard to do then don't worry about it.
- _What things are randomized in the random seeds?_ In general I think the main 2 sources of randomness are 1) randomness in the BO procedure (e.g. initialization of interior point methods) and 2) randomness in training of the tree ensembles. Do your error bars in Figures 2-4 cover both of these sources of variation, or just the randomness of BO?
- _How necessary is the gurobi solver specifically?_ Could you use another similar solver? Would other solvers be able to handle the same constraints?
- The solver seems to be able to handle a large family of constraints. _Is the solution exact/nearly exact for all these constraint types, or does the solver lose its guarantees for certain constraint families (e.g. non-convex constraints)?_ (I'm not very familiar with cone solvers)
limitations: As far as I can tell, the limitations of this work are discussed adequately.
review_title: null

Meta-review: metareview: This paper presents a fairly neat take on combining tree ensembles with GPs by creating a kernel function from the tree ensembles. This not only allows for Bayesian optimization over discrete and mixed feature spaces--inheriting the usual advantage of tree ensembles--but allows for UCB/LCB to be optimized using a mixed integer programming tool. 

Based on reviewer questions and responses, there are a few things that surfaced that I do think the paper would benefit from discussion further in the camera ready version. Most particular, while the setting here is certainly reasonable, I do think the paper would be overall better if there was simply just an ablation of optimization performance versus the time allocated to Gurobi. 
confidence: Certain
Decision: Accept