Multi-objective Optimization by Learning Space Partitions
This addresses the problem of efficiently finding Pareto frontiers in multi-objective optimization for applications like neural architecture search and molecular design, representing a novel method for a known bottleneck.
The paper tackles multi-objective optimization by proposing LaMOO, a method that learns to partition the search space based on dominance numbers and uses Monte Carlo Tree Search to balance exploration and exploitation, resulting in up to 225% improvement in sample efficiency for neural architecture search and up to 10% for molecular design on the HyperVolume benchmark.
In contrast to single-objective optimization (SOO), multi-objective optimization (MOO) requires an optimizer to find the Pareto frontier, a subset of feasible solutions that are not dominated by other feasible solutions. In this paper, we propose LaMOO, a novel multi-objective optimizer that learns a model from observed samples to partition the search space and then focus on promising regions that are likely to contain a subset of the Pareto frontier. The partitioning is based on the dominance number, which measures "how close" a data point is to the Pareto frontier among existing samples. To account for possible partition errors due to limited samples and model mismatch, we leverage Monte Carlo Tree Search (MCTS) to exploit promising regions while exploring suboptimal regions that may turn out to contain good solutions later. Theoretically, we prove the efficacy of learning space partitioning via LaMOO under certain assumptions. Empirically, on the HyperVolume (HV) benchmark, a popular MOO metric, LaMOO substantially outperforms strong baselines on multiple real-world MOO tasks, by up to 225% in sample efficiency for neural architecture search on Nasbench201, and up to 10% for molecular design.