Venue: NeurIPS 2022 Conference

Reviews:

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 novel variable selection algorithm based on MCTS and BO.
The proposed method, MCTS-VS, outperforms existing approaches in several benchmark problems with relatively large dimensions.

strengths_and_weaknesses: A novel variable selection algorithm outperforms existing work in benchmarks with relatively large dimensions.

The algorithm and the experiments are well described, which should be useful for others in both theory and practice.

Weaknesses:
There are numerous variable selection methods, some of which are useful for high-dimensional problems (such as LASSO-based approaches).
However, this paper only compares against Dropout based methods.
It is not surprising to see MCTS outperforming random selection.
I cannot say that I am fully convinced of the superiority of the proposed method because the comparison is limited.

questions: Can you say that at least in some settings (e.g., some type of 100-1000 dimensional problem), this experimental comparison is sufficient?
Are other well-known variable-selection methods are not applicable or not suitable for these benchmarks?

---
Post rebuttal comments.

Thank you for the clarification.
I changed my score.
limitations: The authors explained the limitations related to the hyperparameters in the main material and the appendix.
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 investigates a Monte Carlo tree search (MCTS) strategy of finding a subset of the available variables in a black-box optimization problem to perform Bayesian optimization (BayesOpt) on.
The algorithm first maintains a vector of scores that quantifies how important each variable is according to observed data.
It then selects the leaf node for further inspection using UCB, where each leaf node represents a subset of variables to use for optimization.
After this selection, the algorithm uses a separate BayesOpt method (e.g., TuRBO) to perform the actual optimization and bifurcates the leaf node appropriately.
The authors also present theoretical results for the bound on the cumulative regret of the algorithm, showing a connection to that of Dropout, which is a simple competitor.
Finally, experiment results show that their algorithm is competitive against a wide range of baselines in the literature, including a MCTS that limits the range of each variable.
strengths_and_weaknesses: This is a well-written paper.
The exposition is clear, and the various components of the algorithm are well-motivated.
The problem of high-dimensional BayesOpt is well-motivated: (1) the curse of dimensionality makes requires exponentially more samples to identify the global optimum, and (2) training and prediction with a Gaussian process (GP) scales poorly.
The approach proposed here is promising because it allows narrowing down a small set of tunable parameters that are important (with respect to optimization), making it amenable to a budgeted search with a GP.
It is clear from their experiment results that their algorithm performs well across various tasks compared to other benchmarks in the literature.

I don't have any major complaints.
The proposed approach seems to be a natural complement to the cited LA-MCTS, which limits the range of the variables, as opposed to finding a subset of them.
Most of my comments and questions are related to the comparison between these two algorithms and are included in the Questions section.

Overall, the submission addresses an important problem and the proposed solution seems to work well on the inspected settings, and I lean towards acceptance.
questions: A couple of questions I have are about the failure modes of MCTS-VS and how it performs against LA-MCTS.
The authors mentioned that the approach might not work well if the percentage of valid variables is high (for example, in Levy experiments).
This is reasonable, and I would be interested to see a synthetic experiment where this percentage could be set to observe the performance of the algorithm as a function of this ratio.

Further, this doesn't mean that the proposed algorithm is not well-motivated, but simply that it isn't appropriate for some functions.
However, could there be ways to automatically flag this during optimization (by inspecting how the tree is being updated and the scores of the leaf nodes maybe)?
I imagine being able to automatically output a message that variable selection might not be useful on a specific function would be a nice feature.

I find it interesting that there are many cases in which MCTS-VS-BO performs better than the TuRBO variant, given how TuRBO has been shown to do well on a wide range of high-dimensional tasks.
Perhaps MCTS-VS is successfully picking out a small set of variables, and doing vanilla BO on this low-dimensional space is more appropriate than using TuRBO.
Did the authors try using LA-MCTS-BO in their experiments?

As a small note, I was hoping more insight could be extracted from the theoretical results.
Are there interpretations about when we could expect the proposed algorithm to have a lower regret bound than Dropout, maybe at some specific settings of $B_T$ or $\alpha_i^*$?
limitations: Yes, the paper mentions its limitations in the Results section and in the appendix.
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 proposes a Monte-Carlo Tree Search (MCTS) approach for variable selection in Bayesian optimization (BO). A key challenge in BO is the optimization of the acquisition function to compute the next point to be evaluated, and this optimization procedure may suffer from the curse of dimensionality (i.e. require a number of evaluations of the acquisition function that grows quickly with the dimension).  The paper tackles this issue by applying MCTS to focus the acquisition on smaller subsets of variables, and decrease the computation cost of the optimization of the acquisition function. 
strengths_and_weaknesses: Strengths:
* The paper provides a novel approach for variable selection in Bayesian optimisation
* The paper provides an theoretical analysis of the regret of algorithms that, at each time t, select only a subset of variables to optimise the acquisition function.
* The approach is validated empirically, showing that in a set of benchmarks the proposed algorithm achieves comparable or better results than the baselines, and verifies that it indeed brings a speed-up with respect to vanilla BO, although slower (as expected) than Dropout BO that does not perform adaptive variable selection. 

Weaknesses: 
* The regret bound seems to be a simple generalisation of the analysis of Dropout-BO (Li et al. 2017) and it is quite generic: it depends on which variables are selected at each time t, so it does not give many insights about the behaviour of the proposed algorithm, notably with respect to the choice of hyperparameters. I believe that an important advantage of presenting theoretical analyses for such kinds of algorithms is to help us understand the effects of hyperparameters on its performance, which is not possible with the generic analysis presented in the paper. 
* As I detail in suggestions below, the presentation of the paper could be improved.

questions: Suggestions:
* In Algorithm 1, several points are not clear, so that the reader needs to look up details in the main text. For instance, here are some points where I believe that more clarification is needed (either in Algorithm 1, or by putting clear references to their definitions in the main text):
	* The parameter $k$ is not mentioned in the list of parameters
	* Line 12: "update $n_{\mathrm{bad}}$
	* Line 20: "update the best $k$ points sampled so far"

* Including a definition of the regret in section 4 would improve the presentation
* Figures 1 and 2 are too small. Maybe section 3 could be shortened by making the presentation of Algorithm 1 clearer, which might create more space for the figures.
* In some parts of the paper (e.g line 59, section 2.2) when talking about the computational complexity of BO, it is not clear whether you refer to the complexity of optimising the acquisition function (which depends on the dimension and is tackled in the scope of the paper, if I understood correctly), and the complexity of keeping/updating a GP model (which depends mostly on the number of samples). Clearly making this distinction would be helpful for understanding the contributions of the paper.

limitations: Regarding the limitations, I suggest the authors add more details about how to choose the hyperparameters of the algorithm. Although they provide some sensitivity analyses in the appendix, one of the limitations of the proposed approach is the amount of hyperparameters required and their impact on the runtime (in addition to their impact on the performance of the optimization). A more in-depth theoretical analysis could help us understand the impact of the hyperparameters and how to choose them.
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: This paper proposes a high-dimensional Bayesian optimization adopting Monte Carlo Tree Search as a variable selector. The competence of the proposed details of MCTS is demonstrated by consistent performance in a range of experiments.
strengths_and_weaknesses: Strengths
* MCTS is effectively designed and used for the variable selection for high dimensional BO.
* The proposed algorithm exhibits consistent performance on various problems, demonstrating the effectiveness of the detailed design of MCTS.
* The experiments are conducted from various angles, and many ablation studies seem to be performed adequately.
* The algorithm is clearly explained.

Weaknesses
* The rationale behind some design choices is a bit unclear (detailed below)
* The provided theoretical bound only guarantees that a better variable selection method reduces the cumulative regret but leaves it as a linear regret (detailed below)
questions: * The effectiveness of MCTS design is well-demonstrated in the experiment. However, some design choices may raise questions to some readers. The critical and novel component of MCTS is 'the variable score' in eq.(2). As explained, it is the sum of query evaluations using given variables. And I can imagine some scenarios where the proposed variable score may not behave as expected.
  * When the objective is positive and the task is maximization, in one extreme, if one variable appears in many subsets then it will have a high score not because it contributes to the optimization but because it just appears more often. 
  * Another case is when the objective is negative and the task is maximization, even when a variable contributes to the optimization, by the design philosophy of the variable score, it should be evaluated more often, but due to its negative value, more addition will decrease its variable score.

> In these cases, how does the variable score behave? Or the objectives are assumed to be positive? Please correct me if there is a misconception.

* It seems that $r$ in Theorem 4.2 appearing in $\beta_t$ is another hyperparameter and any comment on this is missing. Can any comment be added?
limitations: * Even though the provided regret analysis is, in a sense, novel, which allows us to get a sense of the effect of variable selection methods, this bound is quite loose. By using $\min_{i \in [D]} \alpha_i^*$, the right hand side in eq.(4) is lower bounded with a formula with a term linear w.r.t $T$. Therefore, this bound does not tell us the behavior of interest (sublinear). Following the argument in the last paragraph of Section 4, with this bound, what we can say at most is that a better variable selection method reduces the cumulative regret but it is guaranteed only up to having linear regret. Even though a good variable selection method seems helpful, the theoretical argument with this linear in $T$ bound is a bit insufficient. However, this may be a good intermediate step to the bound which tells us the effect of variable selection methods in making the cumulative regret sublinear. It would be better if this point can be addressed.

* The method relies on the assumption of 'low effective dimensionality. The strength of the method is to learn that low dimensions (subset of variables). The benchmarks are such function of low effective dimensionality and NAS-bench is used to show the computational efficiency of MCTS-VS without losing optimization performance. I admit that the MoJuCo experiments support that MCTS-VS may perform well for the function without low effective dimensionality. Still, it would be interesting to see the performance of MCTS-VS on some problems which are known not to have low effective dimensionality. A discussion on this can be addressed in a revised version.
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 the high-dimensional black-box optimization problem and proposes a general variable selection method based on Monte Carlo Tree Search (MCTS) for Bayesian optimization. The authors performed comprehensive experiments to show the effectiveness of the proposed method, as well as theoretical analyses to explain why their method can be better. 
strengths_and_weaknesses: As far as I know, Dropout [Li et al., 2017] is the only variable selection method for high-dimensional BO. This paper proposes another novel one using MCTS.

The main idea is to apply MCTS to select a subset of important variables for optimization in each iteration. A key component of their method is the introduced concept of the variable score, which measures the importance of each variable and is used for node selection and expansion in MCTS. They estimate the score of one variable using the objective values of the data points sampled by optimizing any subset of variables containing it. The idea is natural and reasonable and is expected to be superior to Dropout (random selection), which has been validated by the authors’ experiments. 

The most related method I know is LA-MCTS [Wang et al., 2020], which uses MCTS to divide the range of variables (not to decrease the dimension), and optimizes in a sub-region of the search space. The proposed method so-called MCTS-VS in this paper uses MCTS to select a subset of variables, having better scalability to high-dimensional problems. The authors have made a good explanation of their difference.

The authors did comprehensive experiments. They tested the algorithms on common synthetic functions (their various high-dimensional variants), and various real-world problems, including five NAS-Bench problems (three provided in the appendix) and two MuJoCo tasks in reinforcement learning. The results show that MCTS-VS is superior to Dropout for variable selection, and achieves better performance than SOTA BO methods. They also analyzed the sensitivity of various parameters, giving some guidance on using MCTS-VS in practice. The experiments are convincing to me.

The authors also analyzed the regret bound of variable selection methods. The proofs are non-trivial, but technically not very novel, which is mainly based on [Srinivas et al. 2012]. The derived regret bound is a generalization of GP-UCB [Srinivas et al. 2012] and Dropout [Li et al., 2017]. The theoretical part is not very impressive, but OK, giving some insight into how variable selection methods work. Based on the theoretical findings, the authors have empirically explained why MCTS-CS can be better, by showing that MCTS-CS can select much more significant variables than random selection (Dropout) in the experiments. I suggest the authors to consider specific regret analysis about MCTS-VS, which though seems to be very challenging.

I have read the paper carefully, including the appendix. I did not find any mistakes in their proofs. The authors have described the experiments in sufficient detail, which I believe are reproducible. They also provided the codes in the supplementary material.

The paper is very well written and organized. The method is presented very clearly and is easy to follow. I appreciate that the authors provided an example illustrated in the appendix.

Overall, I think this is a very good work, studying the important high-dimensional black-box optimization problem, proposing a novel variable selection method for BO, performing theoretical analyses (not very impressive, but OK), and showing the effectiveness of the proposed method by very comprehensive experiments. I believe this work would be a good resource to the high-dimensional BO community, which may motivate more variable selection works. 

Some minor comments:
-L56, you should give the full name when first mentioning the abbreviation PI, EI and UCB.

-caption of figure 1, “four synthetic functions” -> “two synthetic functions”

-It needs to explain “recall comparison” more clearly in the caption of Table 2, though I see the explanation in the paper.

-L563 and 580, “a confidence bound of” -> “a confidence bound on”

-In the equations between L651 and 652, you should clearly indicate that $|\cdot|$ denotes the determinant of a matrix, and $tr(\cdot)$ denotes the trace of a matrix.

-L738, the right brackets is missing.

-On top of figure 9, “C_p” (e.g., in Levy10_100_C_p) is redundant.

-L790, “the synthetic functions” -> “a synthetic function”

-L796, “tes ts” -> “tests”
questions: 1. For the unselected variables, you randomly sampled their values from the best $k$ generated data points. The experiments have shown that this strategy is better than selecting the values completely at random. But I also would like to see how about using the average of the best $k$ data points.

2. In figure 14, why is HeSBO not compared?
limitations: Yes.
review_title: null

Meta-review: metareview: This work proposes a variable selection technique based on MCTS that can be integrated with various acquisition functions.  The authors show that this can significantly speed up the optimization of acquisition functions in Bayesian optimization, and in some cases, improve the optimization performance as well.  The reviewers were quite positive about the paper, but few expressed high confidence in their rating.

There were some reservations that the work is not adequately benchmarked against recent algorithms for high-dimensional BayesOpt that include aspects of feature selection (e.g., SAASBO). During the rebuttal, the authors showed that MCTS-VS methods could successfully be used in combination with SAASBO, and that this can improve wall time performance.  I hope that the authors can explore this in more detail in the final version.

The empirical results could be presented in a more rigorous and transparent fashion.  The authors provide compelling evidence that MCTS-VS greatly speeds up "wall clock time". Table 1 does a good enough of a job of communicating the runtime advantages (although it is not clear if this comes from model fitting or AF optimization time).  Such speedups can be particularly helpful in higher throughput scenarios when thousands of iterations occur, or one wishes to use more compute-intensive models, such as the SAAS model.

The goal of Bayesian optimization is to efficiently perform global optimization of expensive-to-evaluate functions.  The performance with MCTS-VS with respect to this goal is a little less consistent, but still promising.  This can be seen in Fig 11 from the rebuttal, where there is no significant difference between most HDBO methods in terms of BayesOpt performance (Fig 3, in this respect, is a somewhat out of place and might mislead readers; I would recommend eliminating such plots, since walltime vs performance plots are really only meaningful for cases like multi-fidelity BO or BO with early stopping, where wall-time refers to the expensive-to-evaluate functions).

Finally, real-world problems likely do not contain many parameters that are truly irrelevant in the same way as the synthetic problems do.  Including more examples of real-world problems in the main text can highlight the practical benefits of this algorithm.  I would recommend using real estate from e.g., the Levy problem, to explore other high-dimensional problems, such as feature selection type problems like the SVM benchmark in the SAASBO paper.
confidence: Less certain
Decision: Accept