Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search

Abstract

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.

References in corpus (14)

• Neural Architecture Search with Reinforcement Learning
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• A Tutorial on Bayesian Optimization
• Simple random search provides a competitive approach to reinforcement learning
• Chip Placement with Deep Reinforcement Learning
• Scalable Global Optimization via Local Bayesian Optimization
• Batched Large-scale Bayesian Optimization in High-dimensional Spaces
• Bayesian Optimization with Exponential Convergence
• BOCK : Bayesian Optimization with Cylindrical Kernels
• Bayesian Multi-Scale Optimistic Optimization
• AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search
• Sample-Efficient Neural Architecture Search by Learning Action Space
• High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups

Cited by in corpus (11)

• Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020
• Neural Feature Search for RGB-Infrared Person Re-Identification
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Solving Black-Box Optimization Challenge via Learning Search Space Partition for Local Bayesian Optimization
• Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation
• Carbon-Efficient Neural Architecture Search
• Multi-objective Optimization by Learning Space Partitions
• Prioritized Architecture Sampling with Monto-Carlo Tree Search
• Scalable Acceleration for Classification-Based Derivative-Free Optimization
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret
• Searching in the Forest for Local Bayesian Optimization