Black Box Optimization Using Latent Action Monte Carlo Tree Search (LaMCTS)
Black box optimization has numerous applications in industries. From a/b testing to experimental designs of new ads or UI, hyper-parameter tuning in the machine learning models, or to find the optimal configuration of a system, black-box optimization tries to optimize your decision solely by exploring the problem configurations. Existing black-box solutions such as Bayesian Optimization and Evolutionary Algorithms have been widely employed to solve many challenging real-world problems. One common issue is that they could suffer the curse of dimensionality for high-dimensional optimization problems.
In this article, we introduce our Latent Action Monte Carlo Tree Search (LA-MCTS). Using LaMCTS, two teams won 3rd and 8th places in the NeurIPS2020 black-box optimization challenge (https://bbochallenge.com/leaderboard), in which over 80 teams from both academia and industry labs participated.
LA-MCTS is a new meta-level algorithm that recursively learns the space partition using MCTS. When paired with Bayesian Optimization, LA-MCTS improves the sample-efficiency by optimizing a region (rather than the entire space), which is a lot easier to optimize. A quick comparison of LA-MCTS to Bayesian Optimization can be found below.
LA-MCTS uses a tree to partition the entire search space. Each node in the tree represents a region (or a subset) of the search space, and a node uses a learned classifier (called “latent action”) to partition the node’s region into a good and bad region, represented by its left and right results. We use the Support Vector Machine (SVM) for such a classifier for partitioning the space. By recursively partitioning the entire search space into disjoint regions, a tree is formed. We apply Monte Carlo Tree Search (MCTS) to trade-off the exploration of new regions and the exploitation of the current best region to avoid trapping into a sub-optimal space partition.
Searching on a region learned from LA-MCTS v.s. the entire search space renders many benefits. First, reducing the search space can alleviate the over-exploring issue in Bayesian Optimization, especially for high dimensional problems. Second, LA-MCTS significantly reduces the complexity of acquisition optimization, as classifiers located on the nodes to the leaf can be used as the constraints to sample the candidate solutions.
LA-MCTS introduces a few hyper-parameters to tune, in addition to those in Bayesian Optimization. One important hyper-parameter is Cp that controls the amount of exploration and exploitation. A reference Cp is around 0.1 * max value of f(x), or a Cp that quickly makes the progress in the first few iterations.
For a complete list of hyper-parameters and their potential impact on the performance, please refer to our NeurIPS’20 paper (https://arxiv.org/abs/2007.00708), “Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search”, for details.
We also prepare a tutorial for you to quickly evaluate LA-MCTS v.s. vanilla Bayesian optimization, and evolutionary algorithms. Please follow the steps below.
– Download the source codes from https://github.com/facebookresearch/LaMCTS.
– Run LA-MCTS by following the codes below:
cd LA-MCTS
python run.py –func ackley –dims 10 –iterations 100
– We use the Bayesian Optimization from scikit-optimize.
pip install scikit-optimize
cd LA-MCTS-baselines/Bayesian-Optimization
python run.py –func ackley –dims 10 –iterations 100
– We also use SoTA evolutionary solver NGOPT from Nevergrad.
pip install nevergrad
cd LA-MCTS-baselines/Nevergrad
python run.py –func ackley –dims 10 –iterations 100
Please make sure you run each solvers for at least 3 times to compare the final results. Here is an example of output from LA-MCTS, which shows the tree details, the current best f(x) and the corresponding x. Please note here we intend to minimize the ackley function.
Our code can be found at https://github.com/facebookresearch/LaMCTS. In addition to the new black box solver, our release also includes the application of LA-MCTS to Neural Architecture Search, which automatically designs neural networks from scratch.
Here is a list of the main content in the current release.
Black-box optimization
- Performance with baselines: 1-minute evaluations of LA-MCTS v.s. Bayesian Optimization and Evolutionary Search.
- Mujoco Experiments: LA-MCTS on Mujoco environment.
Neural Architecture Search (NAS)
- Evaluation on NASBench-101 : Evaluating LaNAS on NASBench-101 on your laptop without training models.
- Our Searched Models, LaNet: SoTA results: • 99.03% on CIFAR-10 • 77.7% @ 240MFLOPS on ImageNet.
- One/Few-shot LaNAS: Using a supernet to evaluate the model, obtaining results within a few GPU days.
- Distributed LaNAS: Distributed framework for LaNAS, usable with hundreds of GPUs.
- Training heuristics used: We list all tricks used in ImageNet training to reach SoTA.
We will give a 45min talk on Apr. 1 2:20 pm ET at the Open Data Science Conference (ODSC) East 2021, titled “Learning to Optimize High-Dimensional Optimization Problems.”
About the author/ODSC East 2021 speaker:
Yuandong Tian is a Research Scientist and Manager in Facebook AI Research, working on deep reinforcement learning in games and theoretical analysis of deep models. He led OpenGo, a super-human Go bot from Facebook AI. Prior to that, he was a Software Engineer/Researcher in the Google Self-driving Car team during 2013–2014. He received his PhD in the Robotics Institute, Carnegie Mellon University in 2013, Bachelors and Masters degrees of Computer Science at Shanghai Jiao Tong University. He is the recipient of the 2013 ICCV Marr Prize Honorable Mentions.
