Year: 2021

Abstract:
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.

heading: 1 INTRODUCTION
text: Multi-objective optimization (MOO) has been extensively used in many practical scenarios involving trade-offs between multiple objectives. For example, in automobile design (Chang, 2015), we must maximize the performance of the engine while simultaneously minimizing emissions and fuel consumption. In finance (Gunantara, 2018), one prefers a portfolio that maximizes the expected return while minimizing risk.
Mathematically, in MOO we optimize M objectives f(x) = [f1(x), f2(x), . . . , fM (x)] ∈ RM :
min f1(x), f2(x), ..., fM (x) (1) s.t. x ∈ Ω
While we could set arbitrary weights for each objective to turn it into a single-objective optimization (SOO) problem, modern MOO methods aim to find the problem’s entire Pareto frontier: the set of solutions that are not dominated by any other feasible solutions1 (see Fig. 1 for illustration). The Pareto frontier yields a global picture of optimal solution structures rather than focusing on one specific weighted combination of objectives.
As a result, MOO is fundamentally different from SOO. Instead of focusing on a single optimal solution, a strong MOO optimizer should cover the search space broadly to explore the Pareto frontier. Popular quality indicators in MOO, such as hypervolume (HV), capture this aspect by computing the volume of the currently estimated frontier. Specifically, given a reference point R ∈ RM , as shown in Fig. 1(a), the hypervolume of a finite approximate Pareto set P is the M-dimensional Lebesgue measure λM of the space dominated by P and bounded from below by R. That is, HV (P, R) = λM (∪|P|i=1[R, yi]), where [R, yi] denotes the hyper-rectangle bounded by reference point R and yi. Consequently, the optimizer must consider the diversity of solutions in addition to their optimality.
1Here we define dominance y ≺f x as fi(x) ≤ fi(y) for all functions fi, and exists at least one i s.t. fi(x) < fi(y), 1 ≤ i ≤ M . That is, solution x is always better than solution y, regardless of how the M objectives are weighted.
While several previous works have proposed approaches to capture this diversity-optimality trade-off (Deb et al., 2002a; Knowles, 2006; Igel et al., 2007; Deb & Jain, 2014; Daulton et al., 2020), in this paper, we take a fundamentally different route by learning promising candidate regions from past explored samples. Ideally, to find the Pareto frontier in as few function evaluations as possible, we want to sample heavily in the Pareto optimal set ΩP , defined as the region of input vectors that corresponds to the Pareto frontier.
One way to focus samples on ΩP is to gradually narrow the full search space down to the subregion containing ΩP via partitioning. For example, in the case of quadratic objective functions, ΩP can be separated from the non-optimal set Ω\ΩP via simple linear classifiers (see Observation 1,2). Motivated by these observations, we thus design LaMOO, a novel MOO meta-optimizer that progressively partitions regions into sub-regions and then focuses on sub-regions that are likely to contain Pareto-optimal regions, where existing solvers can help. Therefore, LaMOO is a meta-algorithm.
Unlike cutting-plane methods (Loganathan & Sherali, 1987; Hinder, 2018; Vieira & Lisboa, 2019) that leverage the (sub)-gradient of convex objectives as the cutting plane, with global optimality guarantees, LaMOO is data-driven: it leverages previous samples to build classifiers to learn the partition and focuses future samples in these promising regions. No analytical formula of objectives or their sub-gradients is needed. LaMOO is a multi-objective extension of recent works (Wang et al., 2020; Yang et al., 2021) that also learn space partitions but for a single black-box objective.
Empirically, LaMOO outperforms existing approaches on many benchmarks, including standard benchmarks in multi-objective black-box optimization, and real-world multi-objective problems like neural architecture search (NAS) (Cai et al., 2019; 2020) and molecule design. For example, as a meta-algorithm, LaMOO combined with CMA-ES as an inner routine requires only 62.5%, 8%, and 29% as many samples to reach the same hypervolume as the original CMA-ES (Igel et al., 2007a) in BraninCurrin (Belakaria et al., 2019), VehicleSafety (Liao et al., 2008) and Nasbench201 (Dong & Yang, 2020), respectively. On average, compared to qEHVI, LaMOO uses 50% samples to achieve the same performance in these problems. In addition, LaMOO with qEHVI (Daulton et al., 2020) and CMA-ES require 71% and 31% fewer samples on average, compared to naive qEHVI and CMA-ES, to achieve the same performance in molecule discovery.

heading: 2 RELATED WORK
text: Bayesian Optimization (BO) (Zitzler et al., 2003; Knowles, 2006; Ponweiser et al., 2008; Couckuyt et al., 2014; Paria et al., 2018; Yang et al., 2019; Daulton et al., 2020) is a popular family of methods to optimize black-box single and multi-objectives. Using observed samples, BO learns a surrogate model f̂(x), search for new promising candidates based on acquisition function built on f̂(x), and query the quality of these candidates with the ground truth black-box objective(s). In multi-objective Bayesian optimization (MOBO), most approaches leverage Expected Hypervolume Improvement (EHVI) as their acquisition function (Zitzler et al., 2003; Couckuyt et al., 2014; Yang et al., 2019), since finding the Pareto frontier is equivalent to maximizing the hypervolume given a finite search space (Fleischer, 2003). There are methods (Knowles, 2006; Ponweiser et al., 2008; Paria et al., 2018) that use different acquisition functions like expected improvement (Jones et al., 1998) and Thompson
sampling (Thompson, 1933). EVHI is computationally expensive: its cost increases exponentially with the number of objectives. To address this problem, qEHVI (Daulton et al., 2020) accelerates optimization by computing EHVI in parallel, and has become the state-of-the-art MOBO algorithm. In this paper, we leverage qEHVI as a candidate inner solver in our proposed LaMOO algorithm.
Evolutionary algorithms (EAs) (Deb et al., 2002a; Igel et al., 2007a; Zhang & Li, 2007; Beume et al., 2007; Fang et al., 2018) are also popular methods for MOO tasks. One category of MOOEAs (Srinivas & Deb, 1994; Deb et al., 2002a; Deb & Jain, 2014) leverages Pareto dominance to simultaneously optimize all objectives. A second category (e.g., (Zhang & Li, 2007)) decomposes a multi-objective optimization problem into a number of single-objective sub-problems, converting a difficult MOO into several SOOs. Another category is quality indicator-based methods, such as (Beume et al., 2007) and (Igel et al., 2007a). They scalarize the current Pareto frontier using quality indicators (e.g., HV) and transfer a MOO to a SOO. New samples are generated by crossover and mutation operations from existing ones. However the drawbacks of non-quality indicator-based methods (i.e., the first two categories) can be not overlooked. Specifically, for MOO with many objectives, NSGA-II (Deb et al., 2002a) easily gets stuck in a dominance resistant solution (Pang et al., 2020) which is far from the true Pareto frontier. while MOEA/D perform better in many-objective problems but specifying the weight vector for problems with unknown Pareto front is the main obstacle (Deb & Jain, 2014). In addition, A* search based algorithms are also considered to be extended to MOO (Stewart & White, 1991; Tung Tung & Lin Chew, 1992; De la Cruz et al., 2005).
Quality Indicators. Besides hypervolume, there are several other quality indicators (Van Veldhuizen & Lamont, 1998; Zitzler et al., 2000; Bosman & Thierens, 2003) for evaluating sample quality, which can be used to scalarize the MOO to SOO. The performance of a quality indicator can be evaluated by three metrics (Deng et al., 2007; Li et al., 2014), including convergence (closeness to the Pareto frontier), uniformity (the extent of the samples satisfy the uniform distribution), and spread (the extent of the obtained approximate Pareto frontier). Sec. B specifically illustrates the merits of each quality indicator. HyperVolume is the only metric we explored that can simultaneously satisfy the evaluation of convergence, uniformity, and spread without the knowledge of the true Pareto frontier while it may suffer from expensive calculation in many-objective problems. Therefore, throughout this work, we use HV to evaluate the optimization performance of different algorithms.

heading: 3 LEARNING SPACE PARTITIONS: A THEORETICAL UNDERSTANDING
text: Searching in high-dimensional space to find the optimal solution to a function is in general a challenging problem, especially when the function’s properties are unknown to the search algorithm. The difficulty is mainly due to the curse of dimensionality: to adequately cover a d-dimensional space, in general, an exponential number of samples are needed.
For this, many works use a “coarse-to-fine” approach: partition the search space and then focusing on promising regions. Traditionally, manually defined criteria are used, e.g., axis-aligned partitions (Munos, 2011b), Voronoi diagrams (Kim et al., 2020), etc. Recently, (Wang et al., 2019; 2020; Yang et al., 2021) learn space partitions based on the data collected thus far, and show strong performance in NeurIPS black box optimization challenges (Sazanovich et al.; Kim et al.).
On the other hand, there is little quantitative understanding of space partition. In this paper, we first give a formal theoretical analysis on why learning plays an important role in space-partition approaches for SOO. Leveraging our understanding of how space partitioning works, we propose LaMOO which empirically outperforms existing SoTA methods on multiple MOO benchmarks.

heading: 3.1 PROBLEM SETTING
text: Intuitively, learning space partitions will yield strong performance if the classifier can determine which regions are promising given few data points. We formalize this intuition below and show why it is better than fixed and manually defined criteria for space partitioning.
Consider the following sequential decision task. We have N samples in a discrete subset S0 and there exists one sample x∗ that achieves a minimal value of a scalar function f . Note that f can be any property we want, e.g., in the Pareto optimal set. The goal is to construct a subset ST ⊆ S0 after T steps, so that (1) x∗ ∈ ST and (2) |ST | is as small as possible. More formally, we define the reward function r as the probability that we get x∗ by randomly sampling from the resulting subset ST :
r := 1
|ST | P (x∗ ∈ ST ) (2)
It is clear that 0 ≤ r ≤ 1. r = 1 means that we already found the optimal sample x∗. Here we use discrete case for simplicity and leave continuous case (i.e., partitioning a region Ω0 instead of a discrete set S0) to future work. Note N could be large, so here we consider it infeasible to enumerate S0 to find x∗. However, sampling from S0, as well as comparing the quality of sampled solutions are allowed. An obvious baseline is to simply set ST := S0, then rb = N−1. Now the question is: can we do better? Here we seek help from the following oracle: Definition 1 ((α, η)-Oracle). Given a subset S that contains x∗, after taking k samples from S, the oracle can find a good subset Sgood with |Sgood| ≤ |S|/2 and
P (x∗ ∈ Sgood|x∗ ∈ S) ≥ 1− exp ( − k η|S|α ) (3)
Lemma 1. The algorithm to uniformly draw k samples in S, pick the best and return is a (1, 1)-oracle.
See Appendix for proof. Note that a (1, 1)-oracle is very weak, and is of little use in obtaining higher reward r. We typically hope for an oracle with smaller α and η (i.e., both smaller than 1). Intuitively, such oracles are more sample-efficient: with few samples, they can narrow down the region containing the optimal solution x∗ with high probability.
Note that α < 1 corresponds to semi-parametric models. In these cases, the oracle has generalization property: with substantially fewer samples than N (i.e., on the order of Nα), the oracle is able to put the optimal solution x∗ on the right side. In its extreme case when α = 0 (or parametric models), whether we classify the optimal solution x∗ on the correct side only depends on the absolute number of samples collected in S, and is independent of its size. For example, if the function to be optimized is linear, then with d+ 1 samples, we can completely characterize the property of all |S| samples. Relation with cutting plane. Our setting can be regarded as a data-driven extension of cutting plane methods (Loganathan & Sherali, 1987; Vieira & Lisboa, 2019; Hinder, 2018) in optimization, in which a cutting plane is found at the current solution to reduce the search space. For example, if f is convex and its gradient∇f(x) is available, then we can set Sgood := {x : ∇f(x0)>(x− x0) ≤ 0,x ∈ S0}, since for any x ∈ S0 \ Sgood, convexity gives f(x) ≥ f(x0) + ∇f(x0)>(x − x0) > f(x0) and thus x is not better than current x0. However, the cutting plane method relies on certain function properties like convexity. In contrast, learning space partition can leverage knowledge about the function forms, combined with observed samples so far, to better partition the space.

heading: 3.2 REWARDS UNDER OPTIMAL ACTION SEQUENCE
text: We now consider applying the (α, η)-oracle iteratively for T steps, by drawing kt samples from St−1 and setting St := Sgood,t−1. We assume a total sample budget K, so ∑T t=1 kt = K. Note that T ≤ log2N since we halve the set size with each iteration. Now the question is twofold. (1) How can we determine the action sequences {kt} in order to maximize the total reward r? (2) Following the optimal action sequences {k∗t }, can r∗ be better than the baseline rb = N−1? The answer is yes. Theorem 1. The algorithm yields a reward r∗ lower bounded by the following:
r∗ ≥ rb exp [( log 2− ηN αφ(α, T )
K
) T ] (4)
where rb := N−1 and φ(α, T ) := (1− 2−αT )/(1− 2−α).
Remarks. Following Theorem 1, a key condition to make r∗ > rb is to ensure log 2 > ηN αφ(α,T ) K . This holds if when ηN αφ(α,T ) K → 0. Note that since T ≤ log2N , the final reward r
∗ is upper bounded by 1 (rather than goes to +∞). We consider some common practical scenarios below. Non-parametric models (α = 1). In this case, φ(α, T ) ≤ 2 and the condition becomes 12 log 2 > ηN/K. This happens when the total sample budget K = Θ(N), i.e., on the same order of N , which means that the partitioning algorithm obtains little advantage over exhaustive search.
Semi-parametric models (α < 1). In this case, φ(α, T ) ≤ 1/(1− 2−α) and the condition becomes (1− 2−α) log 2 > ηNα/K. This happens when the total sample budget K = Θ(Nα). In this case, we could use many fewer samples than exhaustive search to achieve better reward, thanks to the generalization property of the oracle.
Parametric models (α = 0). Now φ(α, T ) = T and the condition becomes log 2 > ηTK . Since T ≤ log2N , the total sample budget can be set to be K = Θ(logN). Intuitively, the algorithm performs iterative halving (or binary search) to narrow down the search toward promising regions.

heading: 3.3 EXTENSION TO MULTI-OBJECTIVE OPTIMIZATION
text: Given our understanding of space partitioning, we now extend this idea to MOO. Intuitively, we want “good” regions to be always picked by the space partition. For SOO, it is possible since the optimal solution is a single point. How about MOO?
Unlike SOO, in MOO we aim for a continuous region, the Pareto optimal set ΩP := {x : @x′ 6= x : f(x′) ≺ f(x)}. A key variable is the regularity of ΩP : if it is highly non-regular and not captured by a simple partition boundary (ideally a parametric boundary), then learning a space partition would be difficult. Interestingly, the shape of ΩP can be characterized for quadratic objectives: Observation 1. If all fj are isotropic, fj(x) = ‖x− cj‖22, then ΩP = ConvexHull(c1, . . . , cq). Observation 2. If M = 2 and fj(x) = (x − cj)>Hj(x − cj) where Hj are positive definite symmetric matrices, then there exists w1 := H2(c2 − c1) and w2 := H1(c1 − c2), so that for any x ∈ ΩP , w>1 (x− c1) ≥ 0 and w>2 (x− c2) ≥ 0.
In both cases, ΩP can be separated from non-Pareto regions Ω\ΩP via a linear hyperplane. Empirically, ΩP only occupies a small region of the entire search space (Sec. 4), and quickly focusing samples on the promising regions is critical for high sample efficiency.
In the general case, characterizing ΩP is analytically hard and requires domain knowledge about the objectives (Li et al., 2014). However, for MOO algorithms in practice, knowing that ΩP can be separated from Ω\ΩP via simple decision planes is already useful: we could learn such decision planes given previous data that are already collected, and sample further in promising regions.

heading: 4 LAMOO: LATENT ACTION MULTI-OBJECTIVE OPTIMIZATION
text: In Sec. 3, for convenience, we only analyze a greedy approach, which makes decisions on space partitions and never revises them afterwards. While this greedy approach indeed works (as shown in Sec. 5.3), an early incorrect partition could easily rule out regions that turn out to be good but weren’t identified with few samples. In practice, we want to keep the decision softer: while exploiting the promising region, we also explore regions that are currently believed to be sub-optimal given limited samples. It is possible that these regions turn out to contain good solutions when more samples are available, and the oracle can then make a different partition.
To balance the trade-off between exploration and exploitation to cope with the generalization error of the learned classifier, we leverage Monte Carlo Tree Search (MCTS) (Kocsis & Szepesvári, 2006) and propose our algorithm LaMOO. As shown in Alg. 1, LaMOO has four steps: (1) learn to partition the search space given previous observed data points Dt, which are collected {xi, f(xi)} from iterations 0 to t. (2) With this information, we partition the region into promising and non-promising regions, and learn a classifier h(·) to separate them. (3) We select the region to sample from, based on the UCB value of each node. (4) We sample selected regions to obtain future data points Dt+1.
Learning Space Partitions. We construct the partition oracle using the dominance number. Let Dt be the collected samples up to iteration t and Dt,j := Dt ∩ Ωj be the samples within the region Ωj we want to partition. For each sample x ∈ Dt,j , its dominance number ot,j(x) at iteration t is defined as the number of samples in Ωj that dominate x (here I[·] is the indicator function):
ot,j(x) := ∑
xi∈Dt,j
I[x ≺f xi, x 6= xi] (5)
While naive computation requires O(|Dt,j |2) operations, we use Maxima Set (Kung et al., 1975) which runs in O(|Dt,j | log |Dt,j |). For x ∈ ΩP , o(x) = 0. For eachDt,j , we then get good (small o(x)) and bad (large o(x)) samples by ranking them according to o(x). The smallest 50% are labeled to be positive while others are negative. Based on the labeled samples, a classifier (e.g., Support Vector Machine (SVM)) is trained to learn a decision boundary as the latent action. We choose SVM since the classifier needs to be decent in regions with few samples, and has the flexibility of being parametric or non-parametric.
Algorithm 1 LaMOO Pseudocode. 1: Inputs: Initial D0 from uniform sampling, sample budget T . 2: for t = 0, . . . , T do 3: Set L ← {Ωroot} (collections of regions to be split). 4: while L 6= ∅ do 5: Ωj ← pop_first_element(L), Dt,j ← Dt ∩ Ωj , nt,j ← |Dt,j |. 6: Compute dominance number ot,j of Dt,j using Eqn. 5 and train SVM model h(·). 7: If (Dt,j , ot,j) is splittable by SVM, then L ← L ∪ Partition(Ωj , h(·)). 8: end while 9: for k = root, k is not leaf node do 10: Dt,k ← Dt ∩ Ωk, vt,k ← HyperVolume(Dt,k), nt,k ← |Dt,k|. 11: k ← arg max
c ∈ children(k) UCBt,c, where UCBt,c := vt,c + 2Cp
√ 2 log(nt,k)
nt,c
12: end for 13: Dt+1 ←Dt ∪Dnew, where Dnew is drawn from Ωk based on qEHVI or CMA-ES. 14: end for
Exploration Using Upper Confidence Bounds(UCB). As shown in Fig. 2, LaMOO selects the final leaf node by always choosing the child node with larger UCB value. The UCB value for a node j is defined as UCBj := vj + 2Cp √ 2 log nparent(j)/nj , where nj is the number of samples in node j, Cp is a tunable hyperparameter which controls the degree of exploration, and vj is the hypervolume of the samples in node j. The selected leaf corresponds the partitioned region Ωk as shown in Alg. 1.
Sampling in Search Region. We use existing algorithms as a sampling strategy in a leaf node, e.g., qEHVI (Daulton et al., 2020)) and CMA-ES (Igel et al., 2007a). Therefore, LaMOO can be regarded as a meta-algorithm, applicable to any existing SOO/MOO solver to boost its performance.
LaMOO with qEHVI. As a multi-objective solver, qEHVI finds data points to maximize a parallel version of Expected Hypervolume Improvement (EHVI) via Bayesian Optimization (BO). To incorporate qEHVI into LaMOO’s sampling step, we confine qEHVI’s search space using the tree-structured partition to better search MOO solutions.
LaMOO with CMA-ES. CMA-ES is an evolutionary algorithm (EA) originally designed for singleobjective optimization. As a leaf sampler, CMA-ES is used to pick a sample that maximizes the dominance number o(x) within the leaf. Since o(x) changes over iterations, at iteration t, we first update ot′(x) of all previous samples at t′ < t to ot(x), then use CMA-ES. Similar to the qEHVI case, we constrain our search to be within the leaf region.
Once a set of new samples Dnew is obtained (as well as its multiple function values f(Dnew)), we update all partitions along its path and the entire procedure is repeated.

heading: 5 EXPERIMENTS
text: We evaluate the performance of LaMOO in a diverse set of scenarios. This includes synthetic functions, and several real-world MOO problems like neural architecture search, automobile safety
design, and molecule discovery. In such real problems, often a bunch of criteria needs to be optimized at the same time. For example, for molecule (drug) discovery, one wants the designed drug to be effective towards the target disease, able to be easily synthesized, and be non-toxic to human body.

heading: 5.1 SMALL-SCALE PROBLEMS
text: Synthetic Functions. Branin-Currin (Belakaria et al., 2019) is a function with 2-dimensional input and 2 objectives. DTLZ2 (Deb et al., 2002b) is a classical scalable multi-objective problem and is popularly used as a benchmark in the MOO community. We evaluate LaMOO as well as baselines in DTLZ2 with 18 dimensions and 2 objectives, and 12 dimensions and 10 objectives, respectively.
Structural Optimization in Automobile Safety Design (vehicle safety) is a real-world problem with 5-dimensional input and 3 objectives, including (1) the mass of the vehicle, (2) the collision acceleration in a full-frontal crash, and (3) the toe-board intrusion (Liao et al., 2008).
Nasbench201 is a public benchmark to evaluate NAS algorithms (Dong & Yang, 2020). There are 15625 architectures in Nasbench201, with groundtruth #FLOPs and accuracy in CIFAR10 (Krizhevsky, 2009). Our goal is to minimize #FLOPs and maximize accuracy in this search space. We normalized #FLOPs to range [−1, 0] and accuracy to [0, 1].
We compare LaMOO with 4 classical evolutionary algorithms (CMA-ES (Igel et al., 2007a), MOEA/D (Zhang & Li, 2007), NSGA-II (Deb et al., 2002a), and NSGA-III (Deb & Jain, 2014)) and 2 state-of-the-art BO methods (qEHVI (Daulton et al., 2020) and qParego (Knowles, 2006)).
Evaluation Criterion. we first obtain the maximal hypervolume (either by ground truth or from the estimation of massive sampling), then run each algorithm and compute the log hypervolume difference (Daulton et al., 2020):
HVlog_diff := log(HVmax −HVcur) (6)
where HVcur is the hypervolume of current samples obtained by the algorithm with given budget.
Result. As shown in Fig. 3, LaMOO with qEHVI outperforms all our BO baselines and LaMOO with CMA-ES outperforms all our EA baselines, in terms of HVlog_diff .
Evolutionary algorithms rely on mutation and crossover of previous samples to generate new ones, and may be trapped into local optima. Thanks to MCTS, LaMOO also considers exploration and greatly improves upon vanilla CMA-ES over three different tasks with 1000 samples. In addition, by plugging in BO, LaMOO+qEHVI achieves 225% sample efficiency compared to other BO algorithms on Nasbench201. This result indicates that for high-dimensional problems (6 in Nasbench201), space
partitioning leads to faster optimization. We further analyze very high-dimensional problems on Sec. 5.2. For visualization of Pareto frontier by LaMOO+qEHVI, see Fig. 12 in Appendix.
Optimization of Many Objectives. While NSGA-II and NSGA-III perform well in the two-objective problems, all evolutionary-based baselines get stuck in the ten-objective problems. In contrast, LaMOO performs reasonably well. From Fig. 4, qEHVI+LaMOO shows strong performance in ten objectives. When combined with a CMA-ES, LaMOO helps it escape the initial region to focus on a smaller promising region by space partitioning.

heading: 5.2 MULTI-OBJECTIVE MOLECULE DISCOVERY
text: Next, we tackle the practical problem of multi-objective molecular generation, which is a highdimensional problem (search space is 32-dimensional). Molecular generation models are a critical component of pharmaceutical drug discovery, wherein a cheap-to-run in silico model proposes promising molecules which can then be synthesized and tested in a lab (Vamathevan et al., 2019). However, one commonly requires the generated molecule to satisfy multiple constraints: for example, new drugs should generally be non-toxic and ideally easy-to-synthesize, in addition to their primary purpose. Therefore, in this work, we consider several multi-objective molecular generation setups from prior work on molecular generation (Yu et al., 2019; Jin et al., 2020b; Yang et al., 2021): (1) activity against biological targets GSK3β and JNK3, (2) the same targets together with QED (a standard measure of “drug-likeness”) and SA (a standard measure of synthetic accessibility), and (3) activity against SARS together with QED and SA. In each task, we propose samples from a pretrained 32-dimensional latent space from (Jin et al., 2020a), which are then decoded into molecular strings and fed into the property evaluators from prior work.
Fig. 5 shows that LaMOO+qEHVI outperforms all baselines by up to 10% on various combinations of objectives. While EA struggles to optimize these high-dimensional problems due to the limitations mentioned in Sec. 2, LaMOO helps them (e.g., CMA-ES) to perform much better.

heading: 5.3 ABLATION STUDIES
text: Visualization of LaMOO. To understand how LaMOO works, we visualize its optimization procedure for Branin-Currin. First, the Pareto optimal set ΩP is estimated from 106 random samples (marked as black stars), as shown in both search and objective space (Fig. 6(b) and bottom left of Fig. 6(c)). Over several iterations, LaMOO progressively prunes away unpromising regions so that the remaining regions approach ΩP (Fig 6(c)). Fig 6(a) shows the final tree structure. The color of each leaf node corresponds to a region in the search space (Fig 6(b)). The selected region is recursively
bounded by SVM classifiers corresponding to nodes on the selected path (red arrow in Fig 6(a)). The new samples are only generated from the most promising region ΩJ , improving sample efficiency.
Ablation of Design Choices. We show how different hyperparameters and sampling methods play a role in the performance. We perform the study in VehicleSafety below.
Sampling methods. LaMOO can be integrated with different sample methods, including Bayesian Optimization (e.g., qEHVI) and evolutionary algorithms (e.g., CMA-ES). Fig. 7(left) shows that compared to random sampling, qEHVI improves a lot while CMA-ES only improves slightly. This is consistent with our previous finding that for MOO, BO is much more efficient than EA.
The exploration factor Cp controls the balance of exploration and exploitation. A larger Cp guides LaMOO to visit the sub-optimal regions more often. Based on the results in Fig. 7(middle), greedy search (Cp = 0) leads to worse performance compared to a proper Cp value (i.e. 10% of maximum hypervolume), which justifies our usage of MCTS. On the other hand, over-exploration can also yield even worse results than greedy search. Therefore, a "rule of thumb" is to set the Cp to be roughly 10% of the maximum hypervolume HVmax. When HVmax is unknown, Cp can be set empirically.
SVM kernels. As shown in Fig. 7(right), we find that the RBF kernel performs the best, in agreement with (Wang et al., 2020). Thanks to the non-linearity of the polynomial and RBF kernels, their region partitions perform better compared to a linear one.

heading: 6 CONCLUSION
text: We propose a search space partition optimizer called LaMOO as a meta-algorithm that extends prior single-objective works (Wang et al., 2020; Yang et al., 2021) to multi-objective optimization. We demonstrated both theoretically and via experiments on multiple MOO tasks that LaMOO significantly improves the search performance compared to strong baselines like qEHVI and CMAES. In particular, LaMOO + qEHVI achieves state-of-the-art results on a variety of tasks including synthetic functions, neural architecture search, and molecule discovery.

heading: 7 REPRODUCIBILITY STATEMENT
text: Anonymous code is available at https://drive.google.com/drive/folders/ 1CMdg5iBdbKe3nkboIjiS998rnBEV09EB?usp=sharing. A full theoretical proof of LaMOO can be found in Appendix A.

heading: A PROOFS
text: Lemma 1. The algorithm to uniformly draw k samples in S, pick the best and return is a (1, 1)-oracle.
Proof. Consider the following simple (1, 1)-oracle for single-objective optimization: after sampling k samples, we rank them according to their function values, and split them into two k/2 smaller subsets S̃good and S̃bad. Other points are randomly assigned to either of the two subsets. Then if x∗ happens to be among the k collected samples (which happens with probability k/|S|), definitely we have x∗ ∈ Sgood. Therefore, we have:
P (x∗ ∈ Sgood|x∗ ∈ S) ≥ k
|S| ≥ 1− exp ( − k |S| ) (7)
which is an oracle with α = η = 1. The last inequality is due to ex ≥ 1 + x (and thus e−x ≥ 1− x).
Lemma 2. Define g(λ) : R+ 7→ R+ as:
g(λ) : λ 7→ T∑ t=1 wt log ( 1 + 1 λwt ) (8)
The following maximization problem
max {zt} T∑ t=1 log ( 1− e−zt ) s.t. T∑ t=1 wtzt = K (9)
has optimal solutions
z∗t = log
( 1 + 1
λwt
) , 1 ≤ t ≤ T (10)
where λ is determined by g(λ) = K. With optimal {z∗t }, the objective reaches − ∑ t log(1 + λwt).
Proof. Its Lagrange is:
J ({zt}) = T∑ t=1 log ( 1− e−zt ) − λ ( T∑ t=1 wtzt −K ) (11)
Taking derivative w.r.t. zt and we have:
∂J ∂zt =
e−zt
1− e−zt − λwt = 0.
1
1− e−zt − 1− λwt = 0
1
1− e−zt = 1 + λwt
1− e−zt = 1 1 + λwt
e−zt = 1− 1 1 + λwt = λwt 1 + λwt
zt = − log λwt
1 + λwt = log 1 + λwt λwt = log
( 1 + 1
λwt
)
(12)
Lemma 3. Both g(λ) and g−1(y) are monotonously decreasing. Furthermore, let w̄ := T (∑T
t=1 w −1 t )−1 be the Harmonic mean of {wt} and wmax := maxTt=1 wt, we have:
w̄−1
exp(w̄−1y/T )− 1 ≤ g−1(y) ≤ w
−1 max
exp(w−1maxy/T )− 1 ≤ T y . (13)
Proof. It is easy to see when λ increases, each term in g(λ) decreases and thus g(λ) is a decreasing function of λ. Therefore, its inverse mapping g−1(y) is also decreasing.
Let µ(y) := 1/g−1(y) > 0. Then we have:
y = T∑ t=1 wt log ( 1 + µ(y) wt ) (14)
It is clear that when y = 0, µ(y) = 0. Taking derivative with respect to y in both side, we have:
1 = µ′(y) T∑ t=1
1
1 + µ(y)wt
(15)
where µ′(y) = dµ(y)dy is the derivative of µ(y). Using the property of Harmonic mean, we have:
µ′(y) = ( T∑ t=1
1
1 + µ(y)wt
)−1 ≤ ∑T t=1 1 + µ(y) wt
T 2 =
1
T
( 1 + µ(y)
w̄
) (16)
This gives: µ′(y)
1 + µ(y)/w̄ ≤ 1 T
(17)
Integrate on both side starting from y = 0, we have:
w̄ log(1 + µ(y)/w̄) ∣∣∣∣∣ y
0
≤ y T ∣∣∣∣∣ y
0
(18)
Using µ(0) = 0 we thus have: w̄ log(1 + µ(y)/w̄) ≤ y
T (19) This leads to µ(y) ≤ w̄ [ exp(yw̄−1/T )− 1 ] . With g−1(y) = 1/µ(y), we arrive the final lower bound for g−1(y).
For an alternative upper bound of g−1(y), we just notice that (here wmax := maxt wt):
µ′(y) = ( T∑ t=1
1
1 + µ(y)wt
)−1 ≥ ( T
1 + µ(y)wmax
)−1 = 1
T
( 1 + µ(y)
wmax
) (20)
Using the same technique as above, we have µ(y) ≥ wmax [ exp(yw−1max/T )− 1 ] and the upper bound of g−1(y) follows.
Finally, note that ex ≥ 1 + x, we have w−1max
exp(w−1maxy/T )− 1 ≤ w
−1 max
w−1maxy/T = T y (21)
Theorem 1. Following optimal sequence, the algorithm yields a reward r∗ lower bounded by the following:
r∗ ≥ rb exp [( log 2− ηN αφ(α, T )
K
) T ] (22)
where rb := N−1 and φ(α, T ) := (1− 2−αT )/(1− 2−α).
Proof. First note that |ST | ≤ |S0|/2T and thus 1|ST | ≥ 2 T /N . So we just need to bound P (x∗ ∈ ST ), which can be written as:
P (x∗ ∈ ST ) = T∏ t=1 P (x∗ ∈ St|x∗ ∈ St−1) ≥ T∏ t=1 ( 1− exp ( − kt η|St−1|α )) (23)
Therefore we have
logP (x∗ ∈ ST ) ≥ T∑ t=1 log ( 1− exp ( − kt η|St−1|α )) (24)
We want to find the action sequence {kt} so that logP (x∗ ∈ ST ) is maximized. Let wt := η|St−1|α and zt := kt/wt, applying Lemma 2, and we know that
max {kt} logP (x∗ ∈ ST ) ≥ − T∑ t=1 log(1 + λwt) (25)
where the Lagrangian multiplier λ satisfies the equation g(λ) = K.
Now we have: T∑ t=1 log(1 + λwt) 1© ≤ T∑ t=1 log ( 1 + T K wt ) (26)
2© ≤ T∑ t=1 log ( 1 + T K η(N/2t−1)α ) (27)
3© ≤ ηTN α
K T∑ t=1
1
2α(t−1) (28)
= φ(α, T ) ηTNα
K (29)
Here 1© is due to Lemma 3 which tells that λ = g−1(K) ≤ T/K, 2© is due to wt := η|St−1|α and |St−1| ≤ N/2t−1, and 3© due to log(1 + x) ≤ x. Putting all of them together, we know that
r∗ ≥ max {kt}
1
|ST | P (x∗ ∈ ST ) ≥
2T N exp
( −φ(α, T )ηTN α
K
) (30)
Optimal action sequence {k∗t }. From the proof, we could also write down the optimal action sequence that achieves the best reward: k∗t = wt log ( 1 + 1λwt ) , where wt := η|St−1|α. Using Lemma 3, we could compute the upper and lower bound estimation of λ = g−1(K). Here w̄ :=
T (∑T
t=1 w −1 t )−1 be the Harmonic mean of {wt} and wmax := maxTt=1 wt:
w̄−1
exp(w̄−1K/T )− 1 ≤ λ ≤ w
−1 max
exp(w−1maxK/T )− 1 (31)
With λ, we could compute approximate {k∗t }. Here we make a rough estimation of {k∗t } if we terminate the algorithm when |ST | is still fairly large. This case corresponds to the setting T =
β log2N where β < 1 and all wt ∼ Nα. With K = Θ(Nα) as in semi-parametric case, w̄−1K = Θ(1), exp(w̄−1K/T )− 1 ≈ w̄−1K/T and λwt ∼ log2N 1. Since log(1 + x) ≈ x for small x, we have k∗t ≈ wt 1λwt = 1/λ, which is independent of t. Therefore, a constant amount of sampling at each stage is approximately optimal.
Observation 1. If all fj are isotropic, fj(x) = ‖x− cj‖22, then ΩP = ConvexHull(c1, . . . , cM ). Proof. Consider J(x;µ) := ∑M j=1 µjfj(x) where the weights µj ≥ 0 satisfies ∑ j µj = 1. For
brevity, we write the constraint as ∆ := {µ : µj ≥ 0, ∑ j µj = 1}.
Now consider the Pareto Set ΩP := {x : ∃µ ∈ ∆ : ∇xJ(x;µ) = 0}. We have the following:
∇xJ(x;µ) = 0 (32) ⇐⇒ ∑ j µj∇xfj(x) = 0 (33)
⇐⇒ ∑ j µj(x− cj) = 0 (34)
⇐⇒ x = ∑ j µjcj∑ j µj = ∑ j µjcj (35)
The last step is due to the fact that ∑ j µj = 1. Therefore, for any x ∈ ΩP , x is a convex combination of {c1, . . . , cM} and thus x ∈ ConvexHull(c1, . . . , cM ). Conversely, for any x ∈ ConvexHull(c1, . . . , cM ), we know ∇xJ(x;µ) = 0 and thus x ∈ ΩP .
Observation 2. If M = 2 and fj(x) = (x − cj)>Hj(x − cj) where Hj are positive definite symmetric matrices, then there exists w1 := H2(c2 − c1) and w2 := H1(c1 − c2), so that for any x ∈ ΩP , w>1 (x− c1) ≥ 0 and w>2 (x− c2) ≥ 0. Proof. Following Observation 1, similarly we have for all x ∈ ΩP , ∑ j µjHj(x− cj) = 0, which gives:
x = ∑ j µjHj −1∑ j µjHjcj (36)
Note that this is an expression of the Pareto Set ΩP . Let Aj := ( ∑ j µjHj) −1µjHj . Then ∑ j Aj = I . Note that while ∑ j µjHj and ( ∑ j µjHj)
−1 are positive definite matrix. Aj may not be.
Let M := ∑ i µiHi. Since µ ∈ ∆, M is a PD matrix. Note that we have∑
j µjHjcj = ∑ j µjHjcj − ∑ j µjHjck + ∑ j µjHjck (37)
= ∑ j 6=k µjHj(cj − ck) +Mck (38)
Using Eqn. 36, we know that x = M−1 ∑ j µjHjcj = ck +M −1∑ j 6=k µjHj(cj − ck).
For M = 2, we have x = c2 +M−1µ1H1(c1 − c2). So we have
(c1 − c2)>H1x = (c1 − c2)>H1c2 + (c1 − c2)>H1M−1H1(c1 − c2) (39) ≥ (c1 − c2)>H1c2 (40)
This is because (c1 − c2)H1M−1H1(c1 − c2) ≥ 0 since H1M−1H1 is a PSD matrix. Therefore, let w2 := H1(c1 − c2) and we have w>2 (x− c2) ≥ 0, which is independent of µ ∈ ∆. This means it holds for any x ∈ ΩP . Let w1 = H2(c2 − c1), then similarly we have w>1 (x− c1) ≥ 0 for all x ∈ ΩP .

heading: B QUALITY INDICATORS COMPARISON
text: Generational Distance(GD) (Van Veldhuizen & Lamont, 1998) measures the distance the pareto frontier of approximation samples and true pareto frontier, which requires prior knowledge of true pareto frontier and only convergence is considered. IGD (Bosman & Thierens, 2003) is improved version of GD. IGD calculates the distance the points on true pareto frontier to the closest point on pareto frontier of current samples. Inverted Generational Distance(IGD) satisfies all three evaluation metrics of QI but requires true pareto frontier which is hardly to get in real-world problem. Maximum Spread(MS) (Zitzler et al., 2000) computes the distance between the farthest two points of samples to evaluate the spread. Spacing(S) (Bandyopadhyay et al., 2004) measures how close the distribution of pareto frontier of samples is to uniform distribution. Overall Non-dominated Vector Generation and Ratio(ONVGR) is the ratio of number of samples in true pareto-frontier. The table 1 demonstrates the good characteristics of each quality indicators.

heading: C END-TO-END LAMOO PSEUDOCODE
text: Below we list the pseudocode for the end-to-end workflow of LaMOO in Algorithm 2. Specfically, it includes search space partition in Function Split. Node(promising region) selection in Function Select, and new samples generation in Function Sample.
Algorithm 2 LaMOO Pseudocode. 1: Inputs: Initial D0 from uniform sampling, sample budget T . 2: for t = 0, . . . , T do 3: Set L ← {Ωroot} (collections of regions to be split). 4: V, v, n← Split(L, Dt) 5: k ← Select(Cp, Dt) 6: Dt+1 ← Sample(k) 7: end for 8: 9: Function Split(L, Dt) 10: while L 6= ∅ do 11: Ωj ← pop_first_element(L), Dt,j ← Dt ∩ Ωj , nt,j ← |Dt,j |. 12: Compute dominance number ot,j of Dt,j using Eqn. 5 and train SVM model h(·). 13: If (Dt,j , ot,j) is splittable by SVM, then L ← L ∪ Partition(Ωj , h(·)). 14: end while 15: 16: Function Select(Cp, Dt) 17: for k = root, k is not leaf node do 18: Dt,k ← Dt ∩ Ωk, vt,k ← HyperVolume(Dt,k), nt,k ← |Dt,k|. 19: k ← arg max
c ∈ children(k) UCBt,c, where UCBt,c := vt,c + 2Cp
√ 2 log(nt,k
nt,c
20: end for 21: return k 22: 23: Function Sample(k) 24: Dt+1 ←Dt ∪Dnew, where Dnew is drawn from Ωk based on qEHVI or CMA-ES. 25: return Dt ∪Dnew
D EXPLORATION FACTOR(Cp) SETUP WITH UNKNOWN MAXIMUM HYPERVOLUME
As we mentioned in the paper, a "rule of thumb" is to set the Cp to be roughly 10% of the maximum hypervolume HVmax. If HVmax is unknown, Cp can be dynamically set to 10% of the hypervolume of current samples in each search iteration. The figures below demonstrate the difference between 10% HVmax and 10% current hypervolume in three problems(Branin-Currin, VehicleSafety, and Nasbench201 from left to right). The final performances by using 10% HVmax and 10% current hypervolume are similar.
E WALL CLOCK TIME IN DIFFERENT PROBLEMS
Fig. 10 shows the wall clock time of different search algorithms in BraninCurrin(Belakaria et al., 2019), VehicleSafefy (Liao et al., 2008) and Nasbench201 (Dong & Yang, 2020).

heading: F DETAILS OF BENCHMARK PROBLEMS
text: F.1 PROBLEM DESCRIPTION
BraninCurrin (Belakaria et al., 2019):
f (1)(x1, x2) = (15x2 − 5.1 ∗ (15x1 − 5)2
4π2 + 75x1 − 25 π − 5)2 + (10− 10 8π )) ∗ cos(15x1 − 5))
f (2)(x1, x2) = [ 1− exp ( − 1
(2x2)
)] 2300x31 + 1900x 2 1 + 2092x1 + 60
100x31 + 500x 2 1 + 4x1 + 20
where x1, x2 ∈ [0, 1]. VehicleSafefy (Liao et al., 2008):
f1(x) = 1640.2823 + 2.3573285x1 + 2.3220035x2 + 4.5688768x3 + 7.7213633x4 + 4.4559504x5
f2(x) = 6.5856 + 1.15x1 − 1.0427x2 + 0.9738x3 + 0.8364x4 − 0.3695x1x4 + 0.0861x1x5 + 0.3628x2x4 + 0.1106x 2 1 − 0.3437x23 + 0.1764x24 f3(x) = −0.0551 + 0.0181x1 + 0.1024x2 + 0.0421x3 − 0.0073x1x2 + 0.024x2x3 − 0.0118x2x4 − 0.0204x3x4 − 0.008x3x5 − 0.0241x22 + 0.0109x24
where x ∈ [1, 3]5. Nasbench201 (Dong & Yang, 2020):
In Nasbench201, the architectures are made by stacking the cells together. The difference among architectures in Nasbench201 is the design of the cells, see fig 11. Specifically, each cell contains 4 nodes, and there is a particular operation connecting to two nodes including zeroize, skip-connect, 1x1 convolution, 3x3 convolution, and 3x3 average pooling. Therefore, there are C24 = 6 edges in a cell and 56 =15625 unique architectures in Nasbench201. According to this background, Each architecture can be encoded into a 6-dimensional vector with 5 discrete numbers (i.e., 0, 1, 2, 3, 4 that corresponds to zeroize, skip-connect, 1x1 convolution, 3x3 convolution, and 3x3 average pooling).
f1(x) = Accuracy(x)
f2(x) = #FLOPs(x)
where x ∈ {0, 1, 2, 3, 4}6. DTLZ2 (Deb et al., 2002b):
f1(x) = (1 + g(xM )) cos (π 2 x1 ) · · · cos (π 2 xM−2 ) cos (π 2 xM−1 ) f2(x) = (1 + g(xM )) cos (π 2 x1 ) · · · cos (π 2 xM−2 ) sin (π 2 xM−1
) f3(x) = (1 + g(xM )) cos (π 2 x1 ) · · · sin (π 2 xM−2
) ...
fM (x) = (1 + g(xM )) sin (π 2 x1 )
where g(x) = ∑ xi∈xM (xi − 0.5)
2,x ∈ [0, 1]d, and xM represents the last d−M + 1 elements of x.
F.2 VISUALIZATION OF PARETO-FRONTIER FOR BENCHMARK PROBLEMS
F.3 REFERENCE POINTS
Table 2 elaborates the reference points in the problems throughout the paper.
F.4 MAXIMUM HYPERVOLUME OF EACH PROBLEM
Table 3 elaborates the observed maximal hypervolume in the problems throughout the paper. We used these value to calculate the log hypervolume difference in fig 3 and fig 4.

heading: G EXPERIMENTS SETUP
text: Experiment details: For small-scale problems(i.e. Branin-Currin, VehicleSafety, and Nasbench201) and DTLZ2 with 2 and 10 objectives. We randomly generate 10 samples as the initialization. For multi-objective molecule discovery, the number of initial samples is 150. In each iteration, we update 5 batched samples(q value) for all search algorithms.
Hyperparameters of LAMOO: For all problems, we leverage polynomials as the kernel type of SVM and the degree of the polynomial kernel function is set to 4. The minimum samples in the leaf of MCTS is 10. The cp is roughly set to 10% of maximum of hypervolume(i.e. Branin-Currin -> 5, VehicleSafety -> 20, Nasbench201 -> 6, DTLZ2(2 objectives) -> 0.1, DTLZ2(10 objectives) -> 0.25, molecule discovery(2 objectives) -> 0.03, molecule discovery(3 objectives) -> 0.2, molecule discovery(4 objectives) -> 0.06).
Hyperparameters of qEHVI and qParEGO: The number of q is set to 5. The acquisition function is optimized with L-BFGS-B (with a maximum of 200 iterations). In each iteration, 256 raw samples used for the initialization heuristic are generated to be selected by the acquisition function. As the same claim in Daulton et al. (2020), each generated sample is modeled with an independent Gaussian process with a Matern 5/2 ARD kernel.
H VERIFICATION OF LAMOO ON MANY-OBJECTIVE PROBLEMS
While it is theoretically hard to label the samples into good and bad based on their dominance number in many-objective problems due the the lack of dominance pressure(All samples are non-dominated with each other). If number of objective is not too large(i.e. ≤ 10), the samples can be still split by dominance number. Given the problem(DTLZ2 with 10 objectives) shown in fig 4, we randomly generate 50 samples in the search space and draw the dominance distribution of them(see fig 13). We did this experiment 5 times.
We then partition the search space by a SVM classifier based on the labeled samples into “good” and “bad”, and randomly generate 50 samples in “good region”, “bad region”, and whole space,
respectively. We did this process 5 times with different initial samples. Fig. 14 shows the range of hypervolume of the samples generated from good regions, the whole space, and bad regions. From the figure, we can see that the hypervolume of samples generated from good regions are significantly higher than others.

heading: I COMPUTATIONAL COMPLEXITY ANALYSIS OF LAMOO
text: Here is a detailed breakdown of the computational complexity of our algorithm (Alg. 1)
Line.6: Compute dominance: O(MNnode2) where Nnode is the number of samples in the node and M is the number of dimensions.
Line 7: Time complexity of SVM : O(N2) where Nnode is number of searched samples in total.
Line 10: Hypervolume: O(N M 2 + N logN)(M > 3) (Beume & Rudolph, 2006) or O(N logN)(M ≤ 3) (Beume et al., 2009), where N is number of searched samples in total and D is the number of dimensions.
HV computation is to be the dominating factor in case of M > 3, otherwise, it should be the computation of SVM.
J VARIATION OF LAMOO WITH A CHEAPER OVERHEAD
Algorithm 3 LaMOO Pseudocode with leaf based selection. 1: Inputs: Initial D0 from uniform sampling, sample budget T . 2: for t = 0, . . . , T do 3: Set L ← {Ωroot} (collections of regions to be split). 4: while L 6= ∅ do 5: Ωj ← pop_first_element(L), Dt,j ← Dt ∩ Ωj , nt,j ← |Dt,j |. 6: Compute dominance number ot,j of Dt,j using Eqn. 5 and train SVM model h(·). 7: If (Dt,j , ot,j) is splittable by SVM, then L ← L ∪ Partition(Ωj , h(·)). 8: end while 9: for k = root, k is not leaf node do 10: Dt,k ← Dt ∩ Ωk, nt,k ← |Dt,k|. 11: end for 12: for l is leaf node do 13: vt,l ← HyperVolume(Dt,l) 14: end for 15: k ← arg max
l ∈ leaf nodes UCBt,l, where UCBt,l := vt,l + 2Cp
√ 2 log(nt,l)
nt,p , where p is the parent of l.
16: Dt+1 ←Dt ∪Dnew, where Dnew is drawn from Ωk based on qEHVI or CMA-ES. 17: end for
Instead of traversing down the search tree to trace the current most promising search path, this variation of LaMOO directly select the leaf node with the highest UCB value. Algorithm. 3 illustrates the detail of this variation. Therefore, this variation avoids calculating the hypervolume in the non-leaf nodes of the tree, where hypervolume calculation is the main computational cost of LaMOO especially in many-objective problems. Figure. 15 and figure. 16 validate the variation that is able to reach similar performance of searched samples but saves lots of time. We leave the validation of others problems in the future works.

heading: K ADDITIONAL RELATED WORKS
text: (Hashimoto et al., 2018a; Kumar et al., 2018; Hashimoto et al., 2018b) indeed leverage classifiers to partition search space and draw the new samples from the good region. However, (Hashimoto et al., 2018a; Kumar et al., 2018; Hashimoto et al., 2018b) randomly sampled in selected regions without integrating existing optimizers (e.g. Bayesian optimization, evolutionary algorithms). In addition, they progressively select the good regions without a trade-off of exploration and exploitation as we did by leveraging Monte Carlo Tree Search (MCTS). (Munos, 2011a; Wang et al., 2014; Kawaguchi et al., 2015) can be seen as the first work to use MCTS to build hierarchical space partitions. But their partitions are predefined (e.g., Voronoi graph, axis-aligned partition, etc) without learning (or adapting to) observed samples so far, except for (Wang et al., 2019; 2020; Yang et al., 2021), which are learning extensions coupled with MCTS. However, they all deal with single-objective optimization.
For multi-objective optimization, (Loshchilov et al., 2010; Seah et al., 2012; Pan et al., 2019) learns to predict the dominance rank of samples, without computing them algorithmic-ally, a slow process with many previous samples, in order to speed up the MOEAs algorithms. Unlike our paper, they do not partition the search space into good/bad regions. In contrast, LaMOO computes the rank algorithmic-ally. Therefore, our contributions are complementary to theirs. We leave a combination of both as one of the future works.

Review summaries:
This work proposes a novel learning-based method called  LaMOO to partition the search space for the multi-objective optimization problem. With the learned partition, the computational budget can be allocated to the small promising regions (e.g., the region close to the Pareto frontier) rather than the whole search space. It is a direct generalization from the closely related works (e.g., LaNAS, LaMCTS, and LaP^3) to multi-objective optimization. The proposed LaMOO has promising experimental results on both synthetic functions and real-world optimization problems.

The paper develops an enhancement to multiobjective solvers so to find better Pareto solutions. The idea is to learn a proxy of the distance of samples to the Pareto frontier, and leverage such information to split the search space via a tree structure, Samples can then be extracted from promising nodes of the tree from other multiobjective algorithms. Numerical results investigate the performance of the method for both synthetic and practical benchmarks.  

This paper presents a learning space partitions-based multi-objective optimization framework by using Monte Carlo tree search and an innovatively proposed metric, i.e., dominance number. Solid theoretical analysis on single-objective optimization (SOO) and some observation on multi-objective optimization (MOO) for the space partitions are given. Extensive experiments are conducted based on synthetic functions, vehicle safety problem, Nasbench201 neural architecture search problem, and molecular design. Comparative results with other baselines show the superiority and effectiveness of the proposed LaMOO.