论文标题
使用蒙特卡洛树搜索学习黑盒优化的搜索空间分区
Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search
论文作者
论文摘要
高维黑盒优化具有广泛的应用，但仍然是一个具有挑战性的问题。给定一组样品$ \ {\ vx_i，y_i \} $，构建一个全局模型（例如贝叶斯优化（BO））在高维搜索空间中遭受了维度的诅咒，而贪婪的搜索可能会导致次级优势。通过将搜索空间递归分为具有高功能值的区域，最近的作品（如Lanas）在神经体系结构搜索（NAS）中表现出良好的性能，从而从经验上降低了样本的复杂性。在本文中，我们将LANAS扩展到其他领域的LA-MCT。与以前的方法不同，LA-MCT使用一些样本及其功能值以在线方式学习了搜索空间的分区。尽管Lanas使用线性分区并在每个区域进行统一的采样，但我们的LA-MCT采用了非线性决策边界，并学习了当地模型来选择良好的候选者。如果非线性分区函数和本地模型与地面黑框函数非常吻合，则可以使用较少的样本来达到良好的分区和候选物。 LA-MCT通过使用现有的Black-Box优化器（例如BO，Turbo）作为其本地模型，用作\ EMPH {meta-Algorithm}，在一般的黑盒优化和加强学习基准中实现了强大的性能，尤其是用于高维问题。
High dimensional black-box optimization has broad applications but remains a challenging problem to solve. Given a set of samples $\{\vx_i, y_i\}$, building a global model (like Bayesian Optimization (BO)) suffers from the curse of dimensionality in the high-dimensional search space, while a greedy search may lead to sub-optimality. By recursively splitting the search space into regions with high/low function values, recent works like LaNAS shows good performance in Neural Architecture Search (NAS), reducing the sample complexity empirically. In this paper, we coin LA-MCTS that extends LaNAS to other domains. Unlike previous approaches, LA-MCTS learns the partition of the search space using a few samples and their function values in an online fashion. While LaNAS uses linear partition and performs uniform sampling in each region, our LA-MCTS adopts a nonlinear decision boundary and learns a local model to pick good candidates. If the nonlinear partition function and the local model fits well with ground-truth black-box function, then good partitions and candidates can be reached with much fewer samples. LA-MCTS serves as a \emph{meta-algorithm} by using existing black-box optimizers (e.g., BO, TuRBO) as its local models, achieving strong performance in general black-box optimization and reinforcement learning benchmarks, in particular for high-dimensional problems.
