Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization
Authors: Lei Song
Ke Xue
Xiaobin Huang
Chao Qian
Venue: NeurIPS 2022 Accept (2022)
Keywords: Black-box Optimization
High-dimensional Optimization
Bayesian Optimization
Variable Selection
Monte Carlo Tree Search

Abstract: Bayesian optimization (BO) is a class of popular methods for expensive black-box optimization, and has been widely applied to many scenarios. However, BO suffers from the curse of dimensionality, and scaling it to high-dimensional problems is still a challenge. In this paper, we propose a variable selection method MCTS-VS based on Monte Carlo tree search (MCTS), to iteratively select and optimize a subset of variables. That is, MCTS-VS constructs a low-dimensional subspace via MCTS and optimizes in the subspace with any BO algorithm. We give a theoretical analysis of the general variable selection method to reveal how it can work. Experiments on high-dimensional synthetic functions and real-world problems (e.g., MuJoCo locomotion tasks) show that MCTS-VS equipped with a proper BO optimizer can achieve state-of-the-art performance.

Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization
Lei Song, Ke Xue, Xiaobin Huang, Chao Qian' State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China {songl, xuek, huangxb, qianc)@lamda. njju edu.
Abstract
Bayesian optimization (BO) is class of popular methods for expensive black-box optimization, and has been widely applied to many scenarios. However, BO suffers from the curse of dimensionality and scaling it to high-dimensional problems is still a challenge. In this paper, we propose a variable selection method MCTS-VS VS based Monte Carlo tree search (MCTS), to iteratively select and optimize subset of variables. That is, MCTS- VS constructs fow-dimensional subspace via MCTS and optimizes in the subspace with any BO algorithm. We give theoretical analysis of the general variable selection method to reveal how it can work. Experiments on high-dimensional synthetic functions and real-world problems (i.e., NAS-bench problems and MuJoCo locomotion tasks) show that MCTS- VS equipped with a proper BO optimizer can achieve sfate-of-the-- -ott----r-- performance.
1 Introduction
In many real-world tasks such as neural architecture search (NAS) 41 and policy search rein- forcement learning (RL) [6]. often needs to solve the expensive black-box optimization problems. Bayesian optimization (BO)
23 32 is sample-efficient algorithm for solving such problems. It iteratively fits surrogate model, typically Gaussian process (GP), and maximizes acquisition function to obtain the next point to evaluate. While BO has been employed in a wide variety of settings, successful applications
often limited low-dimensional problems.
Recently, scaling BO to high-dimensional problems has received a lot of interest. Decomposition- based methods [13 [55 17 26 31) assume that the high-dimensional function to be optimized has a certain structure, typically the additive structure. By decomposing the original high-dimensional function into the sum of several low low-dimensional functions, they optimize each low-dimensional function to obtain the point in the high- sigh-dimensional space. However, it not easy to decide whether decomposition exists well to learn the decomposition.
Other methods often assume that the original figh-dimensional function with dimension has low-dimensional subspace with dimension d < D, and then perform the optimization in the low-dimensional subspace and project the low-dimensional point back for evaluation. For example, embedding- based methods (20 27 42) use random matrix to embed the original space into the low- dimensional subspace. Another way is to select a subset of variables directly, which can even avoid the time-consuming matrix operations of embedding -bssd methods. For example, Dropout [21] selects d variables randomly in each iteration. Note that for both embedding and variable selection methods, the parameter d can have large influence the performance, which is, however, difficult to set in real-world problems.
Equual Contribution
Corresponding Author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we propose a new Variable Selection method using Monte Carlo Tree Search (MCTS), called MCTS-VS. MCTS is employed to partition the variables into important and unimportant ones, and only those selected important variables are optimized via any black-box optimization algorithm, e.g., vanilla BO [32 or TuRBO [0] The values of unimportant variables are sampled using historical information. Compared with Dropout-BO, MCTS-VS can select important variables automatically.
We also provide regret and computational complexity analyses of general variable selection methods, showing that variable selection can reduce the computational complexity while increasing the cumulative regret. Our regret bound generalizes that of GP-UCB [8] which always selects all variables, as well as that of Dropout [21] which selects d variables randomly in each iteration. The results suggest that a good variable selection method should select as important variables as possible.
Experiments on nigh-dimensional synthetic functions and real-world problems (i.e., NAS and RL problems) show that MCTS-VS is better than the previous variable selection method Dropout (1], and can also achieve the competitive performance to state-of-the-art BO algorithms. Furthermore, its running time small due the advantage of variable selection. We also observe that MCTS-VS can select important variables, explaining its good performance based on our theoretical analysis.
2 Background
2.1 Bayesian Optimization
We consider the problem max f(x), where is black-box function and X' C R.P is the domain. The basic framework of BO contains two critical components: a surrogate model and an acquisition function. GP is the most popular surrogate model. Given the sampled data points {(z', y=) where y² = f(x) + et and e¹ (O, v/²) the observation noise, GP at iteration seeks to infer ~ A(( + I)) specified by the mean su(-) and covariance kernel i(-,-,, where I is
the identity matrix of size D. After that, an acquisition function, e.g., Probability of Improvement
(PI) [19) Expected Improvement (EI) [16] or Upper Confidence Bound (UCB) [38] is used to determine the next query point x² while balancing exploitation and exploration.
2.2 High-dimensional Bayesian Optimization
Scaling BO high-dimensional problems is challenge due to the curse of dimensionality and the computation cost. As the dimension increases, the search space increases exponentially, requiring more samples, and thus more expensive evaluations, find a good solution. Furthermore, the computation cost of updating the GP model and optimizing the acquisition function will be very time-consuming [30). There have been a few common approaches to tackle high-dimensional BO with different assumptions.
Decomposition. Assuming that the function can be decomposed into the sum of -in-immesional functions with disjoint subspaces, Kandasamy et al. [17] proposed the Add-GP-UCB algorithm to optimize those low-dimensional functions separately, which was further generalized to overlapping subspaces 226 3T]. Wang et al.
(43) proposed ensemble BO that uses an ensemble of additive GP models for scalability. Han et al. 13 constrained the dependency graphs of decomposition to tree structures to facilitate the decomposition learning and optimization. For most problems, however, the decomposition is unknown, and also difficult to learn.
Embedding. Assuming that only a few dimensions affect the high-dimensional function significantly, embedding- based methods embed the high-dimensional space into a low-dimensional subspace, and optimize in the subspace while projecting the point back for evaluation. REMBO and its variants use random matrix to embed the search space into -iw-iimensional subspace [3] 42). Nayebi et al. 27 used a hash-based method for embedding. Letham et al. 200 proposed ALEBO, focusing on several misconceptions in REMBO to improve the performance. The VAE-based approaches were also employed to project a structured input space (e.g., graphs and images) to a low-dimensional subspace 12 (2).
Based on the same assumption as embedding, variable selection methods iteratively select subset of variables to build a low-dimensional subspace and optimize through BO. The selected variables can be viewed as important variables that are valuable for exploitation, or having high uncertainty that are valuable for exploration. A classical method is Dropout [21).
Variable Selection.

---

which randomly chooses d variables in each iteration. Spagnol et al. B7 uses Hilbert Schmidt Independence criterion to guide variable selection. When evaluating the sampled point, the values of those unselected variables are obtained by random sampling or using historical information. VS-BO [3 selects variables with larger estimated gradients and uses CMA-ES [14 to obtain the
values of unselected variables. Note that variable selection can be faster than embedding, because the embedding cost (e.g,, matrix inversion) is time-consuming for nigh-dimensional optimization.
Both embedding and variable selection methods need to specify the parameter d, i.e., the dimension of cow-dimensional subspace, which will affect the performance significantly, but is not easy to set. There are also some methods to improve the basic components of BO directly for figh-dimensional problems. For example, DNGO [36] uses the neural network as an alternative of GP speed up inference; BO-PP [29] generates pseudo-points (i.e., data points whose objective values are not evaluated) to improve the GP model; SAASBO [9] uses sparsity-inuucing prior to perform variable selection implicitly, making the coefficients of unimportant variables near to zero and thus restraining over-exploration on these variables. Note that different from Dropout and our proposed MCTS-VS, SAASBO still optimizes all variables, and also due to its high computational cost of inference, it is very time-consuming as reported in [9]. These methods can be combined with the above-mentioned dimensionality reduction methods, which may bring further improvement.
2.3 Monte Carlo Tree Search
MCTS [5] is a tree search algorithm based on random sampling, and has shown great success in high-dimensional tasks, such as Go 34 35 A tree node represents a state, describing the current situation, e.g., the position in path planning. Each tree node X stores value ux representing its goodness, and the number nx that it has been visited. They are used to calculate UCB 1 i.e.,
Ux + 2Cp (Cp/2(lop) (20oo//)))m) np)/
where Cp is hyper-parameter and up is the number of visits of the parent of X. UCB considers both exploitation and exploration, and will used for node selection.
MCTS iteratively selects a leaf node of the tree for expansion. Each iteration can be divided into four steps: selection, expansion, simulation and back kack-propagation is to recursively select a node with larger UCB until a leaf node, denoted as X. Expansion is to execute certain action in the state represented by X and transfer to the next state, e.g., move forward and arrive at new position in path planning. We use the child node Y of X to represent the next state. Simulation is obtain the value by via random sampling. Propaproong is to update the value and the number of visits of Y's ancestors.
Starting from the root node, selection
To tackle high-dimensional optimization, Wang et al. 40 proposed LA-MCTS, which applies MCTS to iteratively partition the search space into small sub-regions, and optimizes only in the good sub- regions. That is, the root of the tree represents the entire search space Ω, and each tree node X represents a sub-region Ωxx The value ux is measured by the average objective value of the sampled points in the sub-region 12x, In each iteration, after selecting a leaf node X, LA-MCTS performs the optimization in f2x by vanilla BO (32 or TuRBO [10), and the sampled points are used for clustering and classification to bifurcate f2x into two disjoint sub-regions, which are "good" and "bad", respectively. Note that the sub-regions are generated by dividing the range of variables, and their dimensionality does not decrease, which still the number of all variables. Wang et [40] have empirically shown the good performance of LA-MCTS. However, as the dimension increases, the search space increases exponentially, and more partitions and evaluations are required to find a good solution, making the application of LA-MCTS to high-dimensional optimization still limited.
3 MCTS-VS Method
In this section, propose a Variable Selection method based MCTS for high-dimensional BO, briefly called MCTS-VS. The main idea is to apply MCTS to iteratively partition all variables into important and unimportant ones, and perform BO only for those important variables. Let D) denote the indexes of all variables æ, and Is denote the subset of variables
[D] - indexed by M C (D).
We first introduce a D-dimensional vector named variable score, which a key component of MCTS- VS. Its i-th element represents the importance of the i-th variable z;. During the running
3

---

process of MCTS-VS VS, after optimizing subset ZM of variables where M S [D] denotes the indexes of the variables, a set D of sampled points will be generated, and the pair (Ma D) will be recorded into a set DD, called information set. The variable score vector is based on ID, and calculated as
Σ Σ (M, (2 (N)
3' g((0))
Σ (M.D)ED
|D| s(Ml) )
where the function g: : 2| + {0, 132h gives the Boolean vector representation of variable index subset M C [D] (i.e., the i-th element of (M)) is if E MI, and 0 otherwise), and / is the element- wise division. Each dimension of > (MD)) (ee y² ((M) is the sum of query evaluations using each variable, and each dimension of E E [D] ((M) is the number of queries using each variable. Thus, the i-th element of variable score 8, representing the importance of the i-th variable r; is actually measured by the average goodness of all the sampled points that are generated by optimizing a subset of variables containing T;. The variable score s will be used to define the value of each tree node of MCTS as well as for node expansion.
In MCTS-VS, the root of the tree represents all variables. A tree node X represents a subset of variables, whose index set is denoted by Ax S [D], and it stores the value ux and the number n of visits, which are used to calculate the value of UCB as in Eq. (T). The value ux is defined as the average score (i.e., importance) of the variables contained by X, which can be caleulated by 8 (Ax)/ [/xa)//xxx where g(Ax) ) is the Boolean vector representation of Ax and A is the size of Ax i.e., the number of variables in node X.
At each iteration, MCTS- -SS first recursively selects a node with larger UCB until a leaf node (denoted as X), which is regarded as containing important variables. Note that if we optimize the subset ZAx of variables represented by the leaf directly, the variables in aax will have the same score (because they are optimized together), and their relative importance cannot be further distinguished. Thus, MCTS-VE uniformly selects a variable index subset M. from Ax at random, and employs BO to optimize UM as well as Txx /Mi this process is repeated for several times. After that, the information set D will be augmented by the pairs of the selected variable index subset M (or Ax M) and the corresponding sampled points generated by BO. The variable score vector s will be updated using this new DD Based on 8, the variable index set Ax represented by the leaf X will be divided into two disjoint subsets, containing variables with larger and smaller scores (i.e., important and unimportant variables), respectively, and the leaf X will be bifurcated into two child nodes accordingly. Finally, the v values of these two children will be calculated using the variable score vector 8, and back- propagation will be performed to update the value and the number of visits of the nodes along the current path of the tree.
MCTS-VS VS can be equipped with any specific BO optimizer, resulting in the concrete algorithm MCTS- VS-BO, where BO is used to optimize the selected subsets of variables during the running of MCTS- VS. Compared with LA-MCTS 40], MCTS- -VS applies MCTS to partition the variables instead of the search space, and thus can be more scalable. Compared with the previous variable selection method Dropout (21], MCTS-V VS can select important variables automatically instead of randomly selecting a fixed number of variables in each iteration. Next we introduce in detail.
3.1 Details of MCTS-VS
The procedure of MCTS-VE- VS is described in Algorithm| 1 In line 1, it first initializes the information set ID. In particular, a variable index subset M. is randomly sampled from [D), and the Latin hypercube sampling [24] is used to generate two sets (denoted as D; and Dj) of N, points to form \ M, This process will be repeated for N, times, resulting in the initial IB = {MM, D.), (M,, D The variable score vector s is calculated using this initial D in line 3, and the Monte Carlo tree is initialized in line 4 by adding only root node, whose e value is calculated according to s and number of visits is O. MCTS- VS uses the variable t to record the number of evaluations it has performed, and thus is set to 2 x N, x N, in line 5 as the initial ID contains x N,, x N₂ sampled points in total.
the two pairs of (MI;, D.) and (MI,, where M, = [D]
In each iteration (i.e., lines 7-28) of MCTS-VS. it selects leaf node X by UCB in line 10, and optimizes the variables (i.e., Txx) represented by X in lines 13-23. Note that to measure the relative importance of variables in Tax. MCTS- VS optimizes different subsets of variables of TAx

---

Algorithm MCTS-VS
Parameters: batch size N. of variable index subset, sample batch size No. total number Ne of evaluations, threshold Naad for re-initializing a tree and Napti for splitting a node, myper-parametce k for the best-k strategy Process:
1: Initialize the information set ID = {M,, D.), (M, P:)
2: Store the best k sampled points in I3;
3: Calculate the variable score using ID) as in Eq.
4: Initialize the Monte Carlo tree:
5: Set = x N₂ x N₂ and Rbadd 0:
6: while N2, do
7: if Wiad > Nbad then
8: Initialize the Monte Carlo tree and set risedd = 0
9: end if
10: X+ + the leaf node selected by UCB:
11:
Let Ax denote the indexes of the subset of variables represented by X;
12:
Increase Rbadd by once visiting a right child node on the path from the root node to X; for j= 1: N, do
13:
14:
Sample a variable index subset M. from Ax uniformly at random;
15:
Fit GP model using the points { y y') sampled-so-fal where only the variables indexed by M are used;
16:
Generate { C+-1 Ji=1 by maximizing an acquisition function;
17:
Determine fae (-++ N,
(D i=1
by the "fill-in" strategy;
18:
Evaluate x r [ [D]MM to obtain y for i = 1, 2, ...,, No:
19:
= D U {MM, ((xtt,, }
20:
Store the best points sampled-so-far;
21:
1 1- No:
22:
Repeat lines 15-21 for M Ax \ M
23:
end for
24:
Calculate the variable score using ID as in Eq. 2
25:
if [Ax| sppti then
26:
Bifurcate the leaf node X into two child nodes, whose value and number of visits are calculated by and set to O, respectively
end if
28:
Back-propagate to update the value and number of visits of the nodes on the path from the root to X
29:
end while
instead of xax directly. That is, a variable index subset M. is randomly sampled from x in line 14, and the corresponding subset arg of variables is optimized by BO in lines 15-16. The data points [aake y² ( sampled-so-far is used to fit a GP model, and N, (called sample batch size) new points N, (artt) R==1 are generated by maximizing an acquisition function. Note that this is standard BO procedure, which can be replaced by any other variant. To evaluate x(++( need to fill in the values of the other variables t-i " which will be explained later. After evaluating w+++ [a [D]]aal
line 18, the information set augmented with the new pair of (M, {(x"+i,y" ) in line 19, and is increased by N, accordingly in line 21. For fairness, the complement subset Zgg of variables, where M x M, also optimized by the same way, i.e., lines 15-21 of Algorithm) i repeated for M. The whole process of optimizing øyg and øgg in lines 14-22 will be repeated for N. times, which is called batch size of variable index subset.
To fill in the values of the un-optimized variables in line 17, we employ the best-k strategy, which utilizes the best It data points sampled-so-fe denoted the & largest objective values observed-so-fai If the i-th variable is un-optimized, its value will be uniformly selected from (x." د random. Thus, MCTS-VS needs to store the best & data points in line 2 after initializing the information set ID, and update them line 20 after augmenting ID. Other direct "fill-in" strategies include sampling the value randomly, using the average variable
""""" That is, { are
5

---

value of the best k data points. The superiority of the employed best-k strategy will be shown in the experiments in Appendix D.
After optimizing the variables TAx represented by the selected leaf X, the variable score vector s measuring the importance of each variable will be updated using the augmented T in line 24. If the number | of variables in the leaf X is larger than threshold N Sppiae (i.e., line 25), Ax will be divided into two subsets. One contains those "important" variable indexes with score larger than the average score of TAx. and the other contains the remaining "unimportant" ones. The leaf X will be bifurcated into a left child Y and a right child Z in line 26, containing those important and unimportant variables, respectively. Meanwhile, By and 22 will be calculated according to s, and the number of visits is i.e., ny ng = O. Finally, MCTS-VS performs back propagation in line 28 to re-calculate the v value and increase the number of visits by 1 for each ancestor of Y and Z.
MCTS-VS will run until the number / of performed evaluations reaches the budget Ne- Note that as the Monte Carlo tree may be built improperly, we use a variable Rsad to record the number of visiting a right child node (regarded as containing unimportant variables), measuring the goodness of the tree. In line of Algorithm D Rbad is initialized as O. During the procedure of selecting a leaf node by UCB in line 10, Rbad will be increased by once visiting right child node, which is updated in line 12. If Rbaad is larger than a threshold Noad (i.e., line 7), the current tree is regarded as bad, and will be ce-initiaiized in line 8. Furthermore, the frequency of re-initialization can be used to indicate whether MCTS-VE VS can do good variable selection for the current problem. For ease of understanding, we also provide an example illustration of MCTS- VS in Appendix A.
4 Theoretical Analysis
Although it is difficult to analyze the regret of MCTS-VS directly, we can theoretically analyze the influence of general variable selection by adopting the acquisition function GP-UCB. The considered general variable selection framework is as follows: after selecting a subset of variables at each iteration, the corresponding observation data (i.e., the data points sampled-so-fal where only the selected variables are used) is used to build a GP model, and the next data point is sampled by maximizing GP-UCB. We use M, to denote the sampled variable index subset iteration f, and let [M] d.
Regret Analysis. Let x" denote an optimal solution. We analyze the cumulative regret Pr Ei fxx"), i.e., the sum of the gap between the optimum and the function values of the selected points by iteration T. To derive an upper bound on Rr, we pessimistically assume that the worst function value, i.e., min piya, f( (DD))M,)) given Det, is returned in evaluation.
As in 21 38). we assume that X' c [0,r] is convex and compact, and f satisfies the following Lipschitz assumption.
Assumption 4.1. The function f is GP sample path. For some a. b > 0. given L > 0, the partial derivatives of ʃ satisfy that Vi E (D), 3o; 2 O,
P (suux=x 10f/ < L, 2 1 ac (L//))
(3)
Based on Assumption 4.1 we define a to be the minimum value of such that Eq. 33 holds, which characterizes the importance of the i-th variable F,. The larger at the greater influence of x; on the function f. Let 0mmx | o.-
Theorem 4.2 gives an upper bound on the cumulative regret Po with high probability for general
variable selection methods. The proof is inspired by that of GP-UCB without variable selection (38 and provided in Appendix B. If we select all variables each time (i.e., Vt: M, = (D) and assume
Vi aa < 1, the regret bound Eq. (4) becomes Ri S /C,T8777 + 2, which is consistent with (38). Note that Vt [M,] d, D in this case, which implies that Be increases with t, leading to 37 Br. We can see that using variable selection will increase Ry by 2 2T Exerpyyas aj Lr, related to the importance (i.e., ax)) of unselected variables at each iteration. The more important variables unselected, the larger Ry. Meanwhile, the term / /TT will decrease as 37 relies on the number d, of selected variables positively. Ideally, if the unselected variables at each iteration are always unrelated (i.e., Oē =0), the regret bound will be better than that of using all variables (38).
Theorem 4.2. 48 E (0, 1). let Be = 2 llog(4x,// + 2d, log log(d, br Log(d,?brr//oggl)) (log(4Da/8)) and L = / log (D) where is the upper bound each variable, and { Ji21 satisfies Σσ21 Th 1

---

and n3 > O. Let S7 = maxi Sb. At iteration T, the cumulative regret
R / CCTT97 + 20m + 2 T
E Lr
(4)
holds with probability at least 8, where C₁ a constant, p pI I [yp, fD), I(.') :) is the information guin, and yo and fo are the noisy and true observations of a set DD of points, respectively.
By selecting d variables randomly at each iteration and assuming that == and Vi: of S 1, it has been proved [2T that the cumulative regret of Dropout satisfies
RT VCTTBT +2 2T d).
(5)
In this case, we have de = [M,] = d, r = and Vi o 1 Thus, Eq.
becomes
Rr S VCT + 2 2TI.(D -d).
Note that 37 = By here, as 3; increases with given de = d. This implies that our bound Eq. (4) for general variable selection is generalization of Eq. (5) for Dropout [21]. In [33], regret bound analysis has also been performed for variable selection, by optimizing over fixed important variables and using common parameter to characterize the importance of all the other D variables.
Computational Complexity Analysis. The computational complexity of one iteration of BO depends on three critical components: fitting GP surrogate model, maximizing acquisition function and evaluating a sampled point. If using the squared exponential kernel, the computational complexity of fitting GP model at iteration is Ot + (.d.). Maximizing acquisition function is related to the optimization algorithm. we use the Quasi-Newton method to optimize GP-UCB, the computational
complexity is (m((t + tdl + dl)) (28). where m denotes the Quasi-Newton's 's running rounds. The cost of evaluating a sampled point fixed. Thus, by selecting only a subset of variables, instead of all variables, to optimize, the computational complexity can be decreased significantly. The detailed analysis is provided in Appendix B.2.
Insight. The above regret and computational complexity analyses have shown that variable selection can reduce the computational complexity while increasing the regret. Given the number de of variables to be selected, good variable selection method should select as important variables as possible, i.e., variables with as large ag as possible, which may help to design and evaluate variable selection methods. The experiments in Section 5.1 will show that MCTS-VS can select a good subset of variables while maintaining a small computational complexity.
Experiment
To examine the performance of MCTS-VS, we conduct experiments on different tasks, including synthetic functions, NAS- bench problems and MuJoCo locomotion tasks, to compare MCTS- -S with other black-box optimization methods. For MCTS-VE VS, except Cp. which is used for calculating UCB in Eq. ( For Dropout and embedding based methods, set the parameter d to the number of valid dimensions for synthetic functions, and reasonable value for real-world problems. The hyper-parameters of the same components different methods set to the same. We five identical random seeds (2021-2025) for all problems and methods. More details about the settings can be found in Appendix C. Our code is available at https: tgg.. www.addaaaabboaaa---//
the same hyper-parameters
5.1 Synthetic Functions
We use Hartmann (d = 6) and Lovy (d 10) as the synthetic benchmark functions, and extend them to high dimensions by adding unrelated variables as (20) 27 42). For example, Hartmann6. ,300 has the dimension D = 300, and is generated by appending 294 unrelated dimensions to Hartmann. The variables affecting the value of f are called valid variables.
Effectiveness of Variable Selection. Dropout 21 is the previous variable selection method which randomly selects d variables in each iteration, while our proposed MCTS- VS applies MCTS to automatically select important variables. We compare them against vanilla BO 32 without variable selection. The first two subfigures in [ that Dropout-BO and SCCS--V--BC are better than vanilla BO, implying the effectiveness of variable selection. We can also see that MCTS-VS- -OO performs the best, implying the superiority of MCTS- based variable selection over random selection.
7

---

We also equip MCTS-VS and Dropout with the advanced BO algorithm TuRBO [T0], resulting in MCTS-VS- TU-BBO and Propout-TuRBO The last two subfigures in Figure show the similar results except that MCTS-VS- TuRBO needs more evaluations to be better than Dropout- TuRBO. This is because TuRBO costs more evaluations than BO on the same selected variables, and thus needs more evaluations to generate sufficient samples for an accurate estimation of the variable score in Eq. 2
Vanilla
Dropout-B0
MCTS-V5-BO
TURBO
Dropout-TuRBO
MCTS-VS-TURBO
harmannt
Hartmarrs
Hatimarrh
3 8
N: Numberd Bas Litten
Numonr of mvl Jateen
Numoor mal Mabin
Number of soMiatioon
Figure 1: Performance comparison among the two variable selection methods (i.e., MCTS-VS and Dropout) and the BO methods (i.e.. Vanilla BO and TuRBO) on two synthetic functions.
Comparison with State-of- Ahe Methods. We compare MCTS-VS with the state-of-the-ar methods, including TuRBO [TO]. MA-MCTS-TTRBB 40) SAASBO 9. HeSBO [27] ALEBO [0]
and CMA-ES [14]. TuRBO fits a collection of local models to optimize in the trust regions for
overcoming the homogeneity of the global model and over-exploration. LA-MCTS-TURBB applies MCTS to partition the search space and uses TuRBO to optimize in small sub-region. SAASBO uses sparsity-inducing prior to select variables implicitly. HeSBO and ALEBO are state-of-the-art embedding methods. CMA-ES is a popular evolutionary algorithm. We also implement VAE-BO by combining VAE [88 with vanilla BO directly, as bascline of learning- based embedding. For MCTS-VS, implement the two versions of MCTS-VS COCTS-V--BO and cquipped with vanilla BO and TuRBO.
i... MCTS-VS
As shown in Figure 2 MCTS-VS can achieve the best performance except on Levy10_ 100, where it is a little worse than TuRBO. For oiw-dimensional functions (e.g.. D 100 for (evy10_100), TuRBO can adjust the trust region quickly while MCTS-VS needs samples to estimate the variable score. But as the dimension increases, the search space increases exponentially and it becomes difficult for TuRBO to adjust the trust region; while the number of variables only increases linearly, making MCTS-V -S more scalable. SAASBO has similar performance to MCTS-V3 -S due to the advantage of -inducin prior. HcSBO is not stable, which has a moderate performance on Hartmann but a relatively good performance on Levy. Note that we only run SAASBO and ALEBO for 200 evaluations on Hartmann functions because it has already taken more than hours to finish one iteration when the number of samples is large. More details about runtime are shown in Table T VAE-BO has the worst performance, suggesting that the learning algorithm in nigh-dimensional BO needs to be designed carefully. We also conduct experiments on extremely low and high dimensional variants of Hartmann (i.e., Hartmann6_100 100 and Hartmann6 1000m) showing that MCTS-VS still performs well, and perform the significance test by running each method more times. Please see Appendix E.
MCTS-VS-BO
MCTS-VS-TURBO
TURBO
LA-MCTS-TURBO
SAASBO
HeSBO
ALEBO
CMA-ES
VAE-BO
Hanmavrs.90 2012
Hartmanrs_so 502
15
137 100 30
301 100
Figure 2: Comparison among MCTS-VE -S and state-of-the-ar art methods on synthetic functions.
Next, we compare the practical running overheads of these methods. We run each method for 100 evaluations independently using 30 different random seeds, and calculate the average wall clock time. The results are shown in Table [. As expected, when using variable selection (i.e., Dropout and MCTS-VS), the time is less than that of Vanilla BO or TuRBO, because we only optimize subset of variables. MCTS-VS is a little slower than Dropout, which is because MCTS- VS needs to build the search tree and calculate the variable score, while Dropout only randomly selects variables. MCTS- VS is much faster than LA-MCTS-- partitioning the search space. SAASBO optimizes all variables instead of only a subset of variables and uses No-U- sampler (NUTS) to inference, consuming x500 x 1000 time. HeSBO and
showing the advantage of partitioning the variables to
8

---

Table 1: Wall clock time (in seconds) comparison among different methods.
METHOD
LEVY10_100
LEVY10_300
HARTMANNÓ_MN _00
HARTMANN6_500
VANILLA BO
3.190
4.140
4.844
5.540
DROPOUT-BO
2.707
3.225
3,237
3.685
MCTS-VS-BO
2.683
3.753
3,711
4.590
TURBO
8.621
9.206
9.201
9.754
LA-MCTS-TURBO
14,431
22.165
25.853
34.381
MCTS-VS-TURBE
4.912
5.616
5.613
5.893
SAASBO
/
2185.678
1163.121
HESBO
220.459
185.092
51,678
55.699
ALEBO
/
470.714
512.641
CMA-ES
0.030
0.043
0.043
0.045
Table 2: Recall comparison between MCTS-VS and Dropout.
METHOD
LEVY10_100
LEVY10_300
HARTMANN6_3MD
HARTMANN6_500
DROPOUT
0.100
0.030
0.020
0.012
MCTS-VS 0.429
0.433
0.352
0.350
ALEBO consume x10 x 500 time compared with the variable selection methods. CMA-ES is very fast because it does not need to fit GP model or optimize acquisition function. The reasons for the small running overhead of MCTS- VS can summarized as follows: 1) it only optimizes a selected subset of variables; 2) the depth of the search tree is shallow, i.e., O(log D) in expectation
and less than D the worse case; 3) the variable score vector in Eq. (2) easy to calculate for bifurcating a tree node.
Why MCTS-VS Can Perform Well. The theoretical results have suggested that a good variable selection method should select as important variables as possible. Thus, we compare the quality of the variables selected by MCTS-VS and Dropout (i.e., random selection). measured by the recall dž /d, where d is the number of valid variables, and dž is the number of valid variables selected at iteration Dropout randomly selects d variables each iteration, and thus, the recall is d/ in expectation. For MCTS-VS, we run MCTS- PEISS-VV-BL "S-OO for 600 evaluations on five different random seeds, and calculate the average recall. As shown in Table [ the average recall of MCTS- VS is much larger than that of Dropout, implying that MCTS-VS can select better variables than random selection, and thus achieve good performance as shown before. Meanwhile, the recall between 0.35 and 0.433 of MCTS-VS also implies that the variable selection method could be further improved.
5.2 Real- World Problems
We further compare MCTS- -VS with the baselines on real-world problems, including BAS-Bench- 101 [44), NAS-Bench-201 77) Hopper and Walker2d. NAS-Bench problems are popular benchmarks in high-dimensional BO. Hopper and Walker2d are robot locomotion tasks in MuJoCo (39), which is popular black-box optimization benchmark and much more difficult than NAS-Bench problems. The experimental results on more real-world problems can refer to Appendix E.
NAS-Bench Problems. MAS-Bench-100) is a tabular data set that maps convolutional neural network architectures to their trained and evaluated performance on CIFAR-10 10, and we create a constrained problem with D = 36 in the same way as (20). NAS-Bench-201 is an extension to NAS-Bench-100 101, leading to a problem with wall clock time as the r-axis, where the gray dashed line denotes the optimum. The results using the number of evaluations as the r-axis are provided Appendix E, showing that the performance of BO-style methods is similar, as already observed in [20). This may be because there many structures whose objective values are close to the optimum. But when considering the actual runtime, MCTS-VS VS-BO is still clearly better as shown in Figure due to the advantage of variable selection. We also provide results on more WAS-Bench problems, including TransNAS-Bench- 101 g and NAS-Bench-ASR 25 in Appendix E.
30 but without constraints. Figure 3 shows the results with the
1Shotl [5]
MuJoCo Locomotion Tasks. Next we turn to the more difficult MuloCo tasks in RI. The goal is to find the parameters of a linear policy maximizing the accumulative reward. Different from

---

MCTS-VS-BB
MCTS-VS-TURBO
LA-MCTS-TURBO VAE-BO
SAASBO
HeSBO
ALEBO
CIA-EE
RdS Serch-10
Welter0
3000
1900
1000
Tere 20r1
Marber iouuaatee
Number
Figure 3: Comparison on NAS-Bench.
Figure 4: Comparison on MuJoCo.
previous problems, the objective f (i.e., the accumulative reward) is highly stochastic here, making it difficult solve. We use the mean of three independent evaluations to estimate f. and limit the evaluation budget to 1200 due to expensive evaluation. Note that we do not run SAASBO, ALEBO, and VAE-BO because SAASBO and ALEBO extremely time-consuming, and VAE-BO behaves badly in previous experiments. The results are shown Figure 4 TuRBO behaves well on Hopper with low dimension D 33, and MCTS-VS-TuRBCG combining the advantage of variable selection and TuRBO, achieves better performance, outperforming all the other baselines. On Walker2d with a high dimension D 102, MCTS-VS-BB performs the best, because of the good scalability. Most methods have large variance due to the randomness of f. For HeSBO, we have little knowledge about the parameter d. and use 10 and 20 for Hopper and Walker2d, respectively. Its performance may be improved by choosing a better d, which, however, requires running the experiment many times, and is conssminn Note that on the two MuJoCo tasks, Hopper and Walker2d, each variable is valid. The good performance of MCTS-WE VS may be because optimizing only a subset of variables is sufficient for achieving the goal and MCTS- VS can select them. For example, the Walker2D robot consists of four main body parts: a torso, two thighs, two legs and two feet, where adjacent ones are connected by two hinges. The goal is move forward by optimizing the hinges, each of which is valid. But even locking the hinges between legs and feet, the robot can still move forward by optimizing the other hinges. This is similar to that when the ankles are fixed, a person can still walk.
Further Studies. We further perform sensitivity analysis about the hyper-parameters of MCTS-VS, including the employed optimizer, "fill-in" strategy, C₂ for calculating UCB in Eq. I number 2 x No x Ne of sampled data in each iteration, threshold Noed for re-initializing tree and N Naplat for splitting a tree node. Please see Appendix D. We conduct additional experiments Appendix E, including experiments on synthetic functions depending on a subset of variables to various extent and with increasing ratio of valid variables, examination of combining MCTS-VS with SAASBO (which can be viewed as hierarchical variable selection method), and comparison with other variable selection methods (e.g., LASSO).
6 Conclusion
In this paper. we propose the MCTS-VS method for variable selection in high-dimensional BO, which uses MCTS to recursively partition the variables into important and unimportant ones, and only optimizes those important variables. Theoretical results suggest selecting as important variables as possible, which may be of independent interest for variable selection. Comprehensive experiments on synthetic, NAS- and MuJoCo problems demonstrate the effectiveness of MCTS-
However, MCTS-VS relies on the assumption of low effective dimensionality, and might not work well if the percentage of valid variables high. The amount of hyper-parameters might be another limitation, though our sensitivity analysis has shown that the performance of MCTS-V VS is not sensitive most hyper- syper-parameters. The current theoretical analysis is for general variable selection, while it will be very interesting to perform specific theoretical analysis for MCTS-VS.
Acknowledgement
The authors would like to thank reviewers for their helpful comments and suggestions. This work was supported by the NSFC (62022039, 62276124) and the Fundamental Research Funds for the Central Universities (0221-1438001
10

---

References
[1] Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning. 47(2):235-22 256,, 2002.
[2] M. Binois and N. Wycoff. A survey on nigh-dimensional Gaussian process modeling with appli- cation to Bayesian optimization. ACM Transactions on Evolutionary Learning and Optimization, 2(2):1-26, 2022.
[3] M. Bimois, D. Ginsbourger, and O. Roustant. warped kernel improving robustness in Bayesian optimization via random embeddings. In Proceedings of the 9th International Conference Learning and Intelligent Optimization (LION'15) pages 281 281-286, Lille, France, 2015.
[4] M. Binois, D. Ginsbourger, and O. Roustant. On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of Global Optimization, 76( 76(1):69-90. 2020.
[5] C. Browne, E. J. Powley, D. Whitehouse, S. M. M. Lucas, P. I. Cowling, P. Rohlfshagen, Tavener, D. P. Liebana, Samothrakis, and S. Colton. A survey of Monte Carlo tree search methods. IEEE Transactions Computational Intelligence and Al in Games, 4(1):1-43, 2012.
[6] R. Calandra, A. Seyfarth, J. Peters, and M. P. Deisenroth. Bayesian optimization for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76(1):5-23, 2015.
[7] X. Dong and Y. Yang. NAS- HAS-Bench-201: Extending the scope of reproducible neural architecture search. Proceedings of the 8th International Conference on Learning Representations (ICLR"20) Addis Ababa, Ethiopia, 2020.
[8] Y. Duan, X. Chen, H. Xu, Z. Chen, X. Liang, T. Zhang, and Z. Li. TransNAS-Bench- Improving transferability and generalizability of cross-task neural architecture search. CoRR ubs/2105.1187/ 2021.
[9] D. Eriksson and M. Jankowiak. High-dimensional Bayesian optimization with sparse axis- aligned subspaces. In Proceedings of the 37th Conference Uncertainty in Artificial Intelli- gence (UAI'21), pages 493-503, Virtual, 2021.
[10] D. Eriksson, M. Pearce, J. R. Gardner, R. D. Turner, and M. Poloczek. Scalable global optimization via local Bayesian optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS' 19), pages 5497-5508, Vancouver, Canada, 2019.
[11] P. Frazier. A tutorial on Bayesian optimization. CoRR abs/l 2018.
[12] R. Hirzel, R. P. Adams, and A. Aspura-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 4(2):268 276, 2018.
D. K. Duvenaud, J. M. Hernández-Lobato, J. Aguilera Iparraguire, T.D.
[13] E. Han, I. Arora, and Scarlett. High-dimension Bayesian optimization via tree-structured additive models. In Proceedings of the 35th Association for the Advancement of Artificial Intelligence (AAAI'21), pages 7630-7638, Virtual, 2021.
[14] N. Hansen. The CMA evolution strategy: A tutorial. CoRR abs/1604.00772. 2016.
[15] T. N. Hoang, Q. M. Hoang, R. Ouyang, and K. H. Low. Decentralized high-dimensional Bayesian optimization with factor graphs. In Proceedings of the 32nd Association for the Advancement of Artificial Intelligence (AAAI'18), pages 3231-3239, New Orleans, LA, 2018.
[16] D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-492, 1998.
[17] K. Kandasamy. J. G. Schneider, and B. Póczos. High dimensional Bayesian optimisation and bandits via additive models. In Proceedings of the 32nd International Conference on Machine Learning (ICML' 15), pages 295-304, Lille, France, 2015.
[18] D. P. Kingma and M. Welling. Auto-encoding variational Bayes CoRR abs/ 2014.

---

[19] H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86(1):97-106, 1964.
[20] B. Letham, R. Calandra, A. Rai, and E. Bakshy, Re-examining linear embeddings for high- dimensional Bayesian optimization. Advances in Neural Information Processing Systems 33 (NeurlPS'20) 20), pages 1546-1558, Vancouver, Canada, 2020.
[21] C. Li. S. Gupta, Rana, V. Nguyen, S. Venkatesh, and A. Shilton. High dimensional Bayesian optimization using dropout. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 17), pages 2096-2102, Melbourne, Australia, 2017.
[22] X. Lu, J. I. González, Z. Dai, and N. D. Lawrence. Structured variationally auto-encoded optimization. Proceedings of the 35th International Conference on Machine Learning (ICML' 18), pages 3306-3314, Stockholm, Sweden, 2018
[23] M. Malu, G. Dasarathy, and Spanias. Bayesian optimization in high-dimensional spaces: brief survey. In Proceedings of the 12th International Conference on Information, Intelligence, Systems Applications (IISA'21 21), pages 1-8, Virtual, 2021.
[24] M. D. McKay, R. J. Beckman, and W. J. Conover. A comparison of three methods for selecting values of input variables the analysis of output from computer code. Technometrics, 21(2): 239 21992255110 1979.
[25] A. Mehrotra, A. G. C. P. Ramos, Bhattacharya, f.. Dudziak, Vipperla, Chau, M. Abdelfattah, S. Ishtiaq, and N. D. Lane. JAS-Bench-ASR. Reproducible neural architecture search for speech recognition. In Proceedings of the 9th International Conference on Learning Representations (ICLR'2I), Virtual, 2021.
[26] M. Mutný and A. Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature Fourier features. In Advances in Neural Information Processing Systems 31 (NeurIPS' 18), pages 9005-9016, Montreal, Canada, 2018
[27] A. Nayebi, A. Munteanu, and M. Poloczek. A framework for Bayesian optimization in em- bedded subspaces. Proceedings of the 36th International Conference on Machine LearninG (ICML' 19), pages 4752-4761, Long Beach, CA, 2019.
[28] Nocedal and Wright. Numerical Optimization. Springer, New York, NY, second edition edition, 2006.
[29] C. Qian, Xiong, and K. Xue. Bayesian optimization using pseudo-points. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI'00, pages 3044-3050, Yokohama, Japan, 2020.
[30] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, Cambridge, MA, 2006.
[31] P. Rolland, J. Scarlett, I. Bogunovic, and V. Cevher. High-dimensional Bayesian optimization via additive models with overlapping groups. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS' 18), pages 298-307, Playa Blanca, Spain, 2018.
[32] B. Shahriari, K. Swersky, Z. Wang. R. P. Adams, and N. De Freitas. Taking the human out of the loop: A review Bayesian optimization. Proceedings of the IEEE, 104(1):148-175, 2015.
[33] Y. Shen and C. Kingsford. Computationally efficient high-dimenssonal Bayesian optimization via variable selection. CoRR (bb/2109.092c.. 2021.
[34] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalch- brenner, I. Sutskever, T. P. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587): 484-489, 2016.
12

---

[35] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonogiou, A. Huang, A. Guez, T. Hubert, L. baker, M. Lai, A. Bolton, Y. Chen, T. P. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, Graepel, and D. Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676): 354-359, 2017.
[36] J. Snock, O. Rippel, K. Swersky, R. Kiros, N. Satish, N. Sundaram, M. M. A. Patwary, Prabhat, and R. P. Adams. Scalable Bayesian optimization using deep neural networks, In Proceedings the 32nd International Conference on Machine Learning ((CML'15), pages 2171-2180, Lille, France, 2015.
[37] A. Spagnol, R. L. Riche, and S. D. Veiga. Bayesian optimization in effective dimensions via kernel-based sensitivity indices. In Proceedings of the 13th International Conference on Applications of Statisties and Probability Civil Engineering (ICASP' 13), Scoul, Korea, 2019.
[38] N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. Information-thherrti regret bounds for Gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 58(5):3250-3265 2012.
[39] E. Todorov, E. Erez, and Y. Tassa. MuJoCo: A physics engine for model-based control. JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033 2012.
[40] L. Wang, Fonseca, and Y. Tian, Learning search space partition for black-box optimization using Monte Carlo tree search. In Advances in Neural Information Processing Systems 33 (NeurIPS' 20)), pages 19511-19522, Vancouver, Canada, 2020.
[41] L. Wang, Xie, Li, R. Fonseca, and Y. Tian. Sample-efficient neural architecture search by learning actions for Monte Carlo tree search. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021.
[42] Z. Wang, F. Hutter, M. Zoghi, D. Matheson, and N. de Feitas. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55(1):361-387, 2016.
[43] Z. Wang, C. Gehring, P. Kohli, and S. Jegelka, Batched large-scale Bayesian optimization in high-dimensional spaces. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 18), pages 745-754, Playa Blanca, Spain, 2018.
[44] C. Ying, A. Klein, E. Christiansen, E. Real, K. Murphy, and F. Hutter. NAS-bench-100 101: Towards reproducible neural architecture search. In Proceedings of the 36th International Conference on Machine Learning (ICML'19) pages 7105-7114 14, Long Beach, CA, 2019.
[45] A. Zela, J. Siems, and F. Hutter. N Shhtl:: Benchmarking and dissecting one-shot neural architecture search. In Proceedings of the 8th International Conference on Learning Representations (ICLR'20) 20), Addis Ababa, Ethiopia, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the end of Section 5. and the last paragraph the paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
3. If you experiments...
13

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either the supplemental material or URL)? [Yes] See Appendix
C, and the code is provided in GitHub.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We show error bars by the length of vertical bars in the figures.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "czzscehp_ju", "reviewer": "Reviewer_EcyS", "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. ", "questions": "Suggestions:\n* 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):\n\t* The parameter $k$ is not mentioned in the list of parameters\n\t* Line 12: \"update $n_{\\mathrm{bad}}$\n\t* Line 20: \"update the best $k$ points sampled so far\"\n\n* Including a definition of the regret in section 4 would improve the presentation\n* 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.\n* 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.\n", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper provides a novel approach for variable selection in Bayesian optimisation\n* 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.\n* 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. \n\nWeaknesses: \n* 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. \n* As I detail in suggestions below, the presentation of the paper could be improved.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WU84T7qH7Zb", "reviewer": "Reviewer_SbWH", "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.", "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.\n  * 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. \n  * 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.\n\n> 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.\n\n* 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.\n\n* 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.\n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* MCTS is effectively designed and used for the variable selection for high dimensional BO.\n* The proposed algorithm exhibits consistent performance on various problems, demonstrating the effectiveness of the detailed design of MCTS.\n* The experiments are conducted from various angles, and many ablation studies seem to be performed adequately.\n* The algorithm is clearly explained.\n\nWeaknesses\n* The rationale behind some design choices is a bit unclear (detailed below)\n* 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)", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "UpUQ-IbL9cm", "reviewer": "Reviewer_xcd6", "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.\nThe algorithm first maintains a vector of scores that quantifies how important each variable is according to observed data.\nIt then selects the leaf node for further inspection using UCB, where each leaf node represents a subset of variables to use for optimization.\nAfter this selection, the algorithm uses a separate BayesOpt method (e.g., TuRBO) to perform the actual optimization and bifurcates the leaf node appropriately.\nThe 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.\nFinally, 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.", "questions": "A couple of questions I have are about the failure modes of MCTS-VS and how it performs against LA-MCTS.\nThe authors mentioned that the approach might not work well if the percentage of valid variables is high (for example, in Levy experiments).\nThis 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.\n\nFurther, this doesn't mean that the proposed algorithm is not well-motivated, but simply that it isn't appropriate for some functions.\nHowever, 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)?\nI imagine being able to automatically output a message that variable selection might not be useful on a specific function would be a nice feature.\n\nI 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.\nPerhaps 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.\nDid the authors try using LA-MCTS-BO in their experiments?\n\nAs a small note, I was hoping more insight could be extracted from the theoretical results.\nAre 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well-written paper.\nThe exposition is clear, and the various components of the algorithm are well-motivated.\nThe 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.\nThe 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.\nIt is clear from their experiment results that their algorithm performs well across various tasks compared to other benchmarks in the literature.\n\nI don't have any major complaints.\nThe 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.\nMost of my comments and questions are related to the comparison between these two algorithms and are included in the Questions section.\n\nOverall, the submission addresses an important problem and the proposed solution seems to work well on the inspected settings, and I lean towards acceptance.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N3ry17Yx07n", "reviewer": "Reviewer_wG4G", "summary": "This paper proposes a novel variable selection algorithm based on MCTS and BO.\nThe proposed method, MCTS-VS, outperforms existing approaches in several benchmark problems with relatively large dimensions.\n", "questions": "Can you say that at least in some settings (e.g., some type of 100-1000 dimensional problem), this experimental comparison is sufficient?\nAre other well-known variable-selection methods are not applicable or not suitable for these benchmarks?\n\n---\nPost rebuttal comments.\n\nThank you for the clarification.\nI changed my score.", "limitations": "The authors explained the limitations related to the hyperparameters in the main material and the appendix.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A novel variable selection algorithm outperforms existing work in benchmarks with relatively large dimensions.\n\nThe algorithm and the experiments are well described, which should be useful for others in both theory and practice.\n\nWeaknesses:\nThere are numerous variable selection methods, some of which are useful for high-dimensional problems (such as LASSO-based approaches).\nHowever, this paper only compares against Dropout based methods.\nIt is not surprising to see MCTS outperforming random selection.\nI cannot say that I am fully convinced of the superiority of the proposed method because the comparison is limited.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FfFIYWtN5N", "reviewer": "Reviewer_do8w", "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. ", "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.\n\n2. In figure 14, why is HeSBO not compared?", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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. \n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nI 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.\n\nThe 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.\n\nOverall, 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. \n\nSome minor comments:\n-L56, you should give the full name when first mentioning the abbreviation PI, EI and UCB.\n\n-caption of figure 1, “four synthetic functions” -> “two synthetic functions”\n\n-It needs to explain “recall comparison” more clearly in the caption of Table 2, though I see the explanation in the paper.\n\n-L563 and 580, “a confidence bound of” -> “a confidence bound on”\n\n-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.\n\n-L738, the right brackets is missing.\n\n-On top of figure 9, “C_p” (e.g., in Levy10_100_C_p) is redundant.\n\n-L790, “the synthetic functions” -> “a synthetic function”\n\n-L796, “tes ts” -> “tests”", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept