Monte Carlo Tree Search based Space Transfer for Black Box Optimization
Authors: Shukuan Wang, Ke Xue, Song Lei, Xiaobin Huang, Chao Qian
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on synthetic functions, real-world problems, Design-Bench and hyperparameter optimization show that MCTS-transfer can demonstrate superior performance compared to other search space transfer methods under different settings. |
| Researcher Affiliation | Academia | Shukuan Wang1,2 , Ke Xue1,2 , Lei Song1,2, Xiaobin Huang1,2, Chao Qian1,2 1National Key Laboratory for Novel Software Technology, Nanjing University 2School of Artificial Intelligence, Nanjing University |
| Pseudocode | Yes | The detailed process is presented in Algorithm 2. We apply breadth-first search to traverse all tree nodes and use a queue Q to manage the sequence of nodes. In addition, we set a queue N to store the nodes that need to be reconstructed. If the potential of the right child of a node is better than that of the left child (line 6), the subtree of this node is deleted (line 7), and it should be reconstructed and is added into the queue N (line 8). Otherwise, the two child nodes will enter into the queue Q (lines 10 11) and will be examined later. After traversing the tree T , we reconstruct the subtrees of nodes in N (lines 15 19). If a node in N is splitable, i.e., the contained samples in the node exceeds θ and can be clustered and divided by a binary classifier, it will be further expanded. Thus, Treeify can fine-tune the tree structure and reserve some history information; meanwhile, it can adaptively be more suitable to the target task. |
| Open Source Code | Yes | Our code is available at https://github.com/lamda-bbo/mcts-transfer. |
| Open Datasets | Yes | BBOB [9] is a popular benchmark for BBO. It offers 24 synthetic functions tailored for the continuous domain. We randomly select one function from each of the five function classes of BBOB as our target task, i.e., Griewank Rosenbrock, Lunacek, Rastrigin, Rosenbrock, and Sharp Ridge. [...] To verify the performance of MCTS-tranfer in more complex and high-dimensional cases, we consider the 3 continuous problems from Design-Bench14 [39]. [...] The HPO-B benchmark [24], sourced from Open ML, includes 176 search spaces/algorithms and 196 datasets, totaling 6.4 million HPO evaluations. |
| Dataset Splits | No | The paper describes the construction and use of source task data for 'pre-learning' and 'mixed transfer' settings, and the evaluation on a 'target task'. However, it does not explicitly provide percentages or counts for a dedicated validation set split for the target task data in the conventional sense of train/validation/test splits. |
| Hardware Specification | No | The paper does not explicitly describe the specific hardware used for running its experiments, such as CPU models, GPU models, or memory specifications. |
| Software Dependencies | No | The paper mentions using 'the GP model in Scikit-learn8' and 'reference implementations for LA-MCTS3, Box-GP4, Ellipsoid-GP5, Supervised-GP6 and PFNs4BO7'. While it lists libraries and frameworks, it does not provide specific version numbers for Scikit-learn or any other software dependencies, which is required for reproducible software description. |
| Experiment Setup | Yes | Detailed configurations and settings of the hyper-parameters for each algorithm are provided in Appendix B.1. For MCTS-transfer-GP, we set γ = 0.99, α = 0.5. We adopt 5 best solutions distance as similarity measure and linear-change strategy as weight assignment. Other parameters and sampling method is consistent with LA-MCTS. The parameters of GP are consistent with GP-EI. For LA-MCTS [43], we set Cp = 0.1, θ = 10. We adopt global GP as the modeling approach. SVM with rbf kernel is used for space division in Sphere2D, BBOB, and HPOB, while Logistic Regression is applied for real-world problems. In the sampling process, we sample the entire space 10,000 times, retaining qualifying candidate points, and repeat this process three times. |