Multi-objective Optimization by Learning Space Partition
Authors: Yiyang Zhao
Linnan Wang
Kevin Yang
Tianjun Zhang
Tian Guo
Yuandong Tian
Venue: ICLR 2022 Poster (2022)
Keywords: Optimization
Machine Learning

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.

Published as a conference paper at ICLR 2022
MULTI-OBJECTIVE OPTIMIZATION BY LEARNING
SPACE PARTITIONS
Yiyang Zhao
Linnan Wang Brown University
Kevin Yang UC Berkeley
Tianjun Zhang UC Berkeley
Worcester Polytechnic Institute
Tian Guo
Yuandong Tian Facebook Al Research
Worcester Polytechnic Institute
ABSTRACT
In contrast to single-objective optimization (SOO), multi-objective optimization (MOO) requires optimizer to find the Pareto frontier, a subset of feasible solu- tions that are not dominated by other feasible solutions. In this paper, we propose LaMOO, novel multi-objective optimizer that learns model from observed samples to partition the search space and then focus on promising regions that are likely contain 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 Volume (HV) benchmark, popular MOO metric, LaMOO substantially outperforms strong baselines on multiple real-world MOO tasks, by up to 225% sample efficiency for neural architecture search on Nasbench201, and up to 10% for molecular design.
INTRODUCTION
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 portfolio that maximizes the expected return while minimizing risk.
Mathematically, in MOO optimize M objectives f(x) [x), f2(x), ..... fM E R
min (x()
s.t.
x E
While we could set arbitrary weights for each objective to turn into a single-objective optimization (SO0) 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 solutions (see Fig. for illustration). The Pareto frontier yields global picture of optimal solution structures rather than focusing one specific weighted combination of objectives.
As result, MOO is fundamentally different from SOO. Instead of focusing solution, a strong MOO optimizer should cover the search space broadly to explore the Pareto frontier. Popular quality indicators in MOO, such hypervolume (HV), capture this aspect by computing the volume of the currently estimated frontier. Specifically, given a reference point R E RM as shown in Fig. a)), the hypervolume of a finite approximate Pareto
single optimal
is the M-dimensional
Herre we define dominance < f((x) < fi(y) for all functions ft. and exists at least one i s.t. fx(x fily), < Sis S. M. That is, solution x is always better than solution regardless of how the M objectives weighted.

---

Published as a conference paper at ICLR 2022
MOO methods
Sampling Method
Objectives>3
MOEA/D Zhang & 1
2007
X
CMA-ES Tgel et al
Evolation
NSGA-11 Deb
NAGA-II [Deb & Jun
2014
11gh-023
PARBGO (Koo
Bayesian optimization
qEHHV (Duilion et al.
2020
Ft
Otjecine Spac
Search Space
LaMOO (our approaach
Space partition
(a)
(b)
Figure 1: Left: A basic setting in Multi-objective Optimization (MOO), optimizing M = 2 objectives in Eqn. (a) depicts the objective space (f1. f2) and (b) shows the search space x E 52. In (a). P denotes the Pareto frontier, is the reference point, the hypervolume HV is the space of the shaded area, and o(x) are the dominance numbers. In (b), once few samples are collected within Q LaMOO learns to partition the search space ! into sub-regions (i.c. Qgood and Rbad) according to the dominance numher in objective space, and then focuses future sampling on the good regions that are close to the Pareto Frontier. This procedure can be repeated further partition Sggond and Unad. Right: A table shows the properties of MOO methods used in experiments.
Lebesgue measure AM of the space dominated by P and bounded from below by R. That is, HV,P, P,PP R) Am ( wil), where [R, yil denotes the hyper-rectangle bounded by reference point R and yv- Consequently, the optimizer must consider the diversity of solutions in addition to their optimality.
While several previous works have proposed approaches to capture this diversity trade-off (Deb et al. 2002a Knowles 2006 Igel et al. 2007 Deb & Jain 2014, Daulton et al.) 2020). in this paper, we take 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 Qp, defined as the region of input vectors that corresponds to the Pareto frontier.
One way to focus samples on 2 is to gradually narrow the full search space down to the subregion containing Q2 via partitioning. For example, in the case of quadratic objective functions, Spp can be separated from the non-optimal set 0700p via simple linear classifiers (see Observation I [2 Motivated by these observations, we thus design LaMOO, novel MOO meta-optimizer that progres- sively 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 a meta-algorithm.
Unlike cutting-plane methods (Loganathan & Sherali 1987 Hinder 2018 Vieira & Lisboa 2019)
that leverage the (sub)-gradient of convex objectives 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-guadiieee gradients is needed. LaMOO is a multi-objective extension of recent works (Wang et al. 2020 Yang et al.) 202T) 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- multi-objecctiv black-box optimization, and real-world objet-ob problems like neural architecture search (NAS) (Cai et al., 2019: 2020) and molecule design. For example, as meta-algorithm, LaMOO combined with CMA-ES as an inner routine requires only 62.5% 5%, 8%, and 29% many samples to reach the same hypervolume 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 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.
RELATED WORK
Bayesian Optimization (BO) (Zitzler et al. 2003 Knowles, 2006 Ponweiser et al., 2008 Couckuyt et al. 2014 Paria et al. 2018 Yang et al. Daulton et al. 2020) a popular family methods to optimize black-box single and multi-obeectives. Using observed samples. BO learns surrogate model f(x), search for new promising candidates based acquisition function built on f(x,, and query the quality of these candidates with the ground truth black-bor objective(s). In multi-objective Bayesian optimization (MOBO), most approaches leverage Expected Hypervolume Improvement
2

---

Published as a conference paper at ICLR 2022
(EHVI) their acquisition function (Zitzler et al. 2003 Couckuyt et al. 2014 Yang al. 2019).
since finding the Pareto frontier is equivalent to maximizing the hypervolume given a finite search space (Fleischer 2003). There are methods (Knowles | Ponweiser et al., 2008 Paria et al. 2018)
that use different acquisition functions like expected improvement (Jones et al. 1998) and l'hompson
sampling [Thompson] 1933). EVHI is computationally expensive: its cost increases exponentially with the number of objectives. To address this problem, qEHVI (Daulton et al. (020) accelerates optimization by computing EHVI in parallel, and has become the state-of-the-an MOBO algorithm. In this paper, we leverage qEHVI as candidate inner solver in our proposed LaMOO algorithm.
Evolutionary algorithms (EAs) (Deb et al., 2002a Lgel al., 2007a; Zhang & Li 2007 Beume
it al. 2007] |Fng et al.) 2011)) are also popular methods for MOO tasks. One category of MOO-
EAs SSiiniaas & Deb 1994, Deb et al. 2002a Deb Jain 2014) leverages Pareto dominance to simultaneously optimize all objectives. A second category (e.g.. (Zhang & Li, (007)) decomposes a multi-objective optimization problem into a number of single-objective sub-problems, converting difficult MOO into several SOOs. Another category is quality indicator-based methods, such as (Beume et al. 2007) and [Ieel et al. 2007a). They scalarize the current Pareto frontier using quality indicators (e.g., HV) and transfer MOO to 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.] (2022)) easily gets stuck in a dominance resistant solution (Pang et al., 2020) which far from the true Pareto frontier. while MOEA/D perform better in MOO but how to specifyy the weight vector for problems with unknown Pareto front is the main challenge (Deb & Jain 2014). In addition, A* search based algorithms are also considered to be extended 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 (003) for evaluating sample quality, which can be used to scalarize the MOO to SOO. The performance of 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. Hyper Volume 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 evaluate the optimization performance of different algorithms.
3 LEARNING SPACE PARTITIONS: A THEORETICAL UNDERSTANDING
Searching in high-dimensional space to find the optimal solution to 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 "coarse-to-fine" approach: partition the search space and then focusing on promising regions. Traditionally, manually defined criteria are used, e.g., axis-aligned parti- tions (Munos] [b] Voronoi diagrams (Kim al., 2020). etc. Recently, (Wang et al. 2019 2020 Yang et al.] (202T) learn space partitions based on the data collected thus far, and show strong performance in NeurlPS 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 formal theoretical analysis on why learning plays an important role in ppace-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.
3.1 PROBLEM SETTING
Intuitively, learning space partitionn 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 So 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 subset ST C So after T
3

---

Published as a conference paper at ICLR 2022
steps, so that (1) x" Sy and (2) |Sy] is small possible. More formally, define the reward function r as the probability that we get x" by randomly sampling from the resulting subset Sy:
P(x" E ST)
(2)
is clear that S 1, 7 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 No instead of discrete set So) to future work. Note N could be large. here we consider it infeasible to enumerate Sy to find x". However, sampling from So, as well as comparing the quality of sampled solutions are allowed. An obvious baseline to simply set ST == Sg. then Tb -N Now the
question is: can we do better? Here we seek help from the following oracle:
Definition ((a, 17) -rr-leec.) Given subset S that contains x", after taking k samples from S, the oracle can find good subset S Sgood with |Sgoodl S |S|/2 and
(~
K
P P(x* E &good x E 2
exp
(3)
Lemma 1. The algorithm to uniformly draw k samples in S, pick the best and return is a (1, 1)-oralle.
See Appendix for proof. Note that a (1, 1o-occl is very weak, and is of little use in obtaining higher reward r. We typically hope for an oracle with smaller and 17 (i.e., both smaller than 1). Intuitively, such oracles are more sample-efficiene region containing the optimal solution x" with high probability.
with few samples, they can narrow down the
Note that a < corresponds to semi-puue parametrie models. these cases, the oracle has generalization property: with substantially fewer samples than N (i.e., on the order of No), the oracle is able to put the optimal solution x" on the right side. its extreme case when a = 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 independent of its size. For example, if the function to optimized is linear, then with d + 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 fx( is available, then can set Suudd
fx (xx)) (x x,) I 0, x E So). T (x xo) f(x)) and
since for any
So \ Sgood. convexity gives fxx 2 fx,) + (xx,) thus x is not better than current Xp- However, the cutting plane method relies on certain function properties like convexity. In contrast, learning space partition
leverage knowledge about the function forms, combined with observed samples so far, to better partition the space.
3.2 REWARDS UNDER OPTIMAL ACTION SEQUENCE
We now consider applying the (a. or)-le iteratively for T steps, by drawing ky samples from S and setting S, := Sgood,t-1. We assume total sample budget K, so Σt= k K. Note that T < log, N since we halve the set size with each iteration. Now the question is twofold. (1) How determine the action sequences } in order to maximize the total reward r? (2) Following the optimal action sequences (ki²) ). can r" be better than the baseline Tb = N-1? The answer is yes.
Theorem 1. The algorithm yields a reward r" lower bounded by the following:
r 2 rb exp (1082- 7.NoM(a, T K
(4)
where = N-1 and b(o, T) = (1 11-2-a7 2- - 2-a).
Remarks. Following Theorem
key condition to make r" > rb is to ensure log > nN "N" M(,,T)
K
This holds if when )(, 0. Note that since T logz N, the final reward r* is upper bounded by (rather than goes to + cc). We consider some common practical scenarios below.
K
Non-parametric models (a 1). In this case, 6(a, T) < 2 and the condition becomes 1 log 2 > 7N/K K. This happens when the total sample budget K = ( [J. i.c., on the same order of N, which means that the partitioning algorithm obtains little advantage exhaustive search.
4

---

Published as a conference paper at ICLR 2022
Semi- pani-paraeettrc models (a: 1). In this case, Φ(a, T) I 1/(112 and the condition becomes (1 - 2 2-) log >> nN" This happens when the total sample budget K = =((N). In this case, could use many fewer samples than exhaustive search to achieve better reward, thanks to the generalization property of the oracle.
Parametric models (a = 0). Now ((a,T) = T and the condition becomes log > vf T & loga N, the total sample budget can be set to be K = (log N). Intuitively, the algorithm performs iterative halving (or binary search) to narrow down the search toward promising regions.
K. Since
3.3 EXTENSION TO MULTI- OULTI-ORIECTIVE OPTIMIZATION
Given our understanding of space partitioning, we now extend this idea to MOO. Intuitively, we want "good" regions be always picked by the space partition. For SOO, is possible since the optimal solution is single point. How about MOO?
Unlike SOO, in MOO we aim for a continuous region, the Pareto optimal set 0p := {x Ax's * x f(x) < f.x)). A key variable is the regularity of S2p: if it is highly non-regular and not captured by a simple partition boundary (ideally parametric boundary), then learning a space partition would be difficult. Interestingly, the shape of S2p can be characterized for quadratic objectives:
Observation 1. If all f are isotropic, fx(x) ||x c, then Qp ConvexHuul(cI,.... C.y.
Observation 2. If M = and [x) = - (x-c,) HH cÿ) where Hj are positive definite symmetric mafrices, then there exists W1 = H2( - 01) and W2 H2 C2), so that for any
X E Qp. w| (x c1) 2 0 and w (x - (2) 20.
In both cases, Stp can be separated from non-Pareto regions 02 via a linear hyperplane. Empir- ically, Sp only occupies small region of the entire search space (Sec. 4. and quickly focusing samples on the promising regions critical for high sample efficiency.
In the general case, characterizing Ωp is analytically hard and requires domain knowledge about the objectives (Li et. 2014). However, for MOO algorithms in practice, knowing that 22p can be separated from 127,2pp 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.
4 LAMOO: LATENT ACTION MULTI-OBJECTIVE OPTIMIZATION
In Sec. 3. for convenience, we only analyze a greedy approach, which makes decisions 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 't identified with few samples. In practice, we want to keep the decision softer: while exploiting the promising region,
also explore regions that are currently believed to be sub-optimal given limited samples. It possible that these regions turn out to contain good solutions when more samples are available, and the oracle then make 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) (Koesis & Szepesvári] 2006) and propose our algorithm LaMOO. As shown in Alg. [ LaMOO has four steps: (1) learn to partition the search space given previous observed data points Dr, which are collected (x;, f(x:)) from iterations 0 to f. (2) With this information, we partition the region into promising and non-promising regions, and learn a classifier fi(-) to separate them. (3) We select the region sample from, based on the UCB value of each node. (4) We sample selected regions to obtain future data points D++1-
Learning Space Partitions. We construct the partition oracle using the dominance number. Let D. be the collected samples up to iteration t and Dr.; == D, 7 Ω2 be the samples within the region Qy we want to partition. For each sample x Drj. its dominance number ot.j (x) iteration is defined as the number of samples in S2, that dominate (here [[-] is the indicator function):
Org Org(x) (x)
Σ xiED,,
I xp Xi, x x *xxi x:)
(5)
While naive computation requires O( operations, we use Maxima Set Kung et al. which runs in O(Dr..) log Drgl)) For x E Pp, o(x) =
1975
5

---

Published as a conference paper at ICLR 2022
Algorithm LaMOO Pseudocode.
1: Inputs: Initial Do from uniform sampling, sample budget T.
2: for t= = O..... . do
3: Set L {f2root (collections of regions to be split).
while L + do
2, 6- pop__orst__lleeeeee first_element((), Dr.g f- D, n2, ReJ. t D
6:
Compute dominance number ot.j of Dr.j using Eqn. and train SVM model A(-).
7:
If (D..j. is splittable by SVM, then C +- C Partition(S,, h())-
8:
end while
rool. not leaf node do D t D. n.nB Qs: Vt,k +- HlyperVolume(D.. n4, <- 1Da,kl-
10:
(logg(ee,
h: ara max children(k)
UCBr,e, where UCB Ve,0 + 20py
12:
end for
13:
DE+1 + D, Dnew, where Dnew is drawn from Sg based on qEHVI or CMA-ES.
14: end for
Leaenned spacee purtition
Learned
()
PD
HV e'
D'RREE
Ug
Only samples from fg based sample methods
UCRe=
fDp
Search Space
UGB
UCB
Leamm partition
Expand the tree
fg
fc
Low o(x)
High o(x)
Split
Select
Sample
Figure 2: (a) The leaf nodes that correspond to non-splittable space Up Qg- (b). The node selection procedure based on the UCB value. (c). The new samples generation from the selected space 2g for bayesian optimization.
For each Di.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 he positive while others are negative. Based on the labeled samples, a classifier (e.g., Support Vector Machine (SVM)) trained to learn 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.
Exploration Using Upper Confidence Mounds(UCB), As shown in Fig. LaMOO selects the final leaf node by always choosing the child node with larger UCB value. The UCB value for node is defined as UCB, by + 2Cp / log pjrcntt) n1,, where ny is the number of samples in node j. Cp is tunable hyperparameter which controls the degree exploration, and vy is the hypervolume of the samples in node j. The selected leaf corresponds the partitioned region Ω2 as shown in Alg.
Sampling Search Region. We use existing algorithms qEHVI (Daulton et al., 2020) and CMA-ES (Igel et al.) (007a). Therefore, LaMOO can be regarded as meta-algorithm, applicable to any existing SOO/MO0 solver to boost its performance.
sampling strategy leaf node, e.g..
LaMOO with qEHVI. As a multi-objective solver, qEHVI finds data points maximize a parallel version Expected Hypervolume Improvement (EHVT) via Bayesian Optimization (BO). To incorpo- rate qEHVI into LaMOO's is sampling step, 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 single- objective optimization. As leaf sampler, CMA-ES used to pick a sample that maximizes the dominance number o(x) within the leaf. Since oxx) changes over iterations, at iteration t, first update or (x) of all previous samples at < to or (x), then use CMA-ES, Similar to the qEHVI case, constrain our search to be within the leaf region.

---

Published as a conference paper at ICLR 2022
Once a set of new samples D is obtained (as well as its multiple function values f(Dnew)) )), update all partitions along its path and the entire procedure is repeated.
5 EXPERIMENTS
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 molccule 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.
5.1 SMALL-SCALE PROBLEMS
Synthetic Functions.
Branin-Currin (Belakaria et al. 2019) is a function with 2-dimensional input and 2 objectives. DTLZ2 (Deb et al. 2002b) is 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 public benchmark to evaluate NAS algorithms (Dong & Yang 2020). There are 15625 architectures in Nasbench201, with groundtruth #FLOPs and accuracy in Cl- FAR10 (Krizhevsky 2009). Our goal is to minimize #FL.Oss and maximize accuracy in this search space. We normalized #FLOPs to range [-1, 1,0 0j and accuracy to [0, 1].
Log Hypervoume Dir
1.5
dt
0.0
Log Hypervoume
1.5
Hypervolume
1.0
-02
0.5
-0.4
0.55
-0.6
20
40
60
80
100
20
40
60
80
100
100
Samples
Samples
Samples
Log Hypervalume DIf
1.5
(PARS
2.0
CHCPS
hypervalume Diff
0.00
CPAAS
Log Hypervoluma
1.-
-0.25
2.0
-0 50
0.5
14
0.75
1.00
0.0-
-1.25
100
200
400
600 Samples
800
1000
0
200
400
600
800
1000
0
200
400
600
800
1000
Samples
Samples
Figure 3: Left: Bramin-Currin with 2 dimensions and 2 objectives. Middle: VehicleSafety with 5 dimensions and 3 objectives. Right: Nasbench201 with 6 dimensions and 2 objectives. We ran each algorithm 7 times (shaded area is + std of the mean). Top: Bayesian Optimization w/o LaMOO. Bottom: evolutionary algorithms w/o LaMOO. Note the two algorithm families show very different sample efficiency in MOO tasks.
We compare LaMOO with 4 classical evolutionary algorithms (CMA-ES (Igel et al., 2007a). MOEA/D ihhag & Li 2007). NSGA-II (Deb et al. 2002a), and NSGA-III (Deb & Jain (0144) and 2 state-of th-the-art BO methods (qEHVI (Daulton et al. 2020) and qParego (Knowles] (0066).
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):
HVog := log(HVnss HVear)
(6)
where HV.ur 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 H VVoog_diff dift-
7

---

Published as a conference paper at ICLR 2022
0.23
5-075
0:43
0.00
0:31
-150
0:32
-175
20
:00
150
220
30
302
136
200
55
-02
250
220
50
200
150
200
Figure 4: DTLZ2 with many objectives, We ran cach algorithm 7 times (shaded area is + std of the mean). From left right: BO with objectives; EA with 2 objectives; BO with 10 objectives; EA with 10 objectives.
Evolutionary algorithms rely mutation and crossover of previous samples to generate new ones, and may be trapped into local optima. Thanks MCTS, LaMOO also considers exploration and greatly improves upon vanilla CMA-ES over three different tasks with 1000/200 samples in small- scale /many objective problems. In addition, by plugging BO, LaMOO+ 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 nigh-dimenniinal problems on Sec. 5.2 and visualize Pareto frontier in Fig. T2
Optimization of Many Objectives. While NSGA-II and NSGA-III perform well in the two-objective problems, all evolutionary-baat 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 CMA-ES, LaMOO helps it escape the initial region to focus smaller promising region by space partitioning.
5.2
MULTI-OBIECTIVE MOLECULE DISCOVERY
0.30
2.2
0.6
2.0
0.4
0.15
1.8
0.10
0.2
0.05
Sceap
1.4
1902
0.0
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Samples
Samples
Samples
Figure 5: Molecule Discovery: Left: Molecule discovery with two objectives DISK3B+JNK3 Middle: Molecule discovery with three objectives (QED+SA+SARS) Right: Molecule Discovery with four objectives (GSK35+INKK+OEDSSA)), We each algorithm times (shaded area is std of the mean).
Next, we tackle the practical problem of multi-objective molecular generation, which is a high- dimensional problem (search space is 32-dimensional). Molecular generation models are 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 lab (Vamathevan al. 2019). However, one commonly requires the generated molecule to satisfy multiple constraints: for example, new drugs should generally be non-toxic and ideally casy-to-synthesize. in addition 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.) (220bb) Yang al., 202T): (1) activity against biological targets GSK3,8 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 pre- trained 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+gEHVI outperforms all baselines by up to 10% on various combinations of objectives. While EA struggles to optimize these high- digehdimensional problems due to the limitations mentioned in Sec. LaMOO helps them (e.g., CMA-ES) to perform much better.
5.3 ABLATION STUDIES
Visualization of LaMOO. To understand how LaMOO works, we visualize its optimization pro- cedure for Branin-Currin. First, the Pareto optimal set 2p is estimated from 10 random samples
8

---

Published as a conference paper at ICLR 2022
-2.
0.5
0.0
roda
Qluesive
0.4
0.4
0.6
08
10
Olpextte:
The structure of Monte- Carlo Tree at the final search iteration.
samples SVM split region of leaf node the tree in the scarch space.
(c) The selected region in
(d) The samples the ohjective
selected path of the tre..
space different search iterations.
Figure 6: Visualization of selected region different search iterations and nodes. (a) The Monte-Carlo tree with colored leaves. Selected path is marked in red. (b) Visualization of the regions({2,, Qx S2,, RR. S2p, Sta) that are consistent with leaves in (a) in the search space. (c) Visualization of selected path at final iteration. (d) Visualization of samples during search; bottom left is the Pareto frontier estimated from one million samples.
(marked as black stars), as shown in both search and objective space (Fig. b)) and bottom left of oj). Over several iterations, LaMOO progressively prunes away unpromising regions so that the remaning regions approach 2p (Fig 6 c)). Olg shows the final tree structure. The color of each leaf node corresponds a region in the search space (Fig The selected region is recursively bounded by SVM classifiers corresponding to nodes on the selected path (red arrow in Fig (())). The new samples are only generated from the most promising region Ω2 improving sample efficiency.
Dif
2.0
Log Hyparvolume Dift
2.0
62
505 mAL
DKT
2.0
coraal
COTE: ody
1.5
1.8
1.5
1.0
1.6
1.0
singt C19--3
0.0
maddrr
40
60
80
100
100
200
300
40
6.0
80
100
Samples
Samples
Samples
Figure 7: Ablation studies on hyperparameters and sampling methods in LaMOO. Left: Sampling without
Bayesian/CMA-ES Middle: Sampling with different Cp. Right: Partitioning with different svm kernels
Ablation of Design Choices. We show how different hyperparameters and sampling methods play role the performance. We perform the study in VehicleSafety below.
Sampling methods. LaMOO be integrated with different sample methods, including Bayesian Optimization (e.g., qEHVI) and evolutionary algorithms (e.g.. CMA-ES). Fig. (7left) shows that compared to random sampling, qEHVI improves 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. [7middde), greedy search (C,, 0) leads to worse performance compared a proper C, 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, "rule of thumb" to set the Cp to be roughly 10% of the maximum hypervolume HVmax. When HV Vaa is unknown, Cp can be set empirically.
SVM kernels. As shown in Fig. 7 rrigh)), 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 linear one.
CONCLUSION
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., (021)) 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 CMA-ES.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENT
This work was supported in part by NSF Grants #1815619 and #2105564, a VMWare grant, and computational resources supported by the Academic & Research Computing group at Worcester Polytechnic Institute.
REFERENCES
Sanghamitra Bandyopadhyay, Sankar K Pal, and B Aruna. Multiobjective gas, quantitative in- dices, and pattern classification. IEEE Transactions on Systems, Man, and Cybernetics, Part (Cyberneticx), (115)))088-0999 2004.
Syrine Belakaria, Aryan Deshwal, and Janardhan Rao Doppa. Max-value entropy search for multi- objective bayesian optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL /ttpppsss/prrocceiiigns neur pss cc/paper/2019/ Tllee/2aa 82edc5c9e222 0356 77647744888 64144486644448888 646444444444333 Pappeeo0o00PPppppppppp..
Nicola Beume and Günter Rudolph. Faster s-metric calculation by considering dominated hypervol- ume as klee's 's measure problem, 2006.
Nicola Beume, Boris Naujoks, and Michael Emmerich. Sms-emoa: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181 (31(3))1653-166 2007. ISSN 0377-2217. doi: /ttp://////////t//////////////00 sci sciencedi com http://rrrrrceeeeiie/////////aia
008.. URL https: www
Nicola Beume, Carlos M. Fonseca, Manuel Lopez-Ibanez, Lufs Paquete, and Jan Vahrenhold. On the complexity of computing the hypervolume indicator. IEEE Transactions on Evolutionary Computation, 13(5):1075-1088 2009. doi: 10. 109/1EVC.2009.2005555
Peter AN Bosman and Dirk Thierens. The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE transactions on evolutionary computation, 1(2):174-188, 2003.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In International Conference on Learning Representations, 2019. URL
httpp://arxiv/ wttp:o/gggp/ppooooooteo http://dd111120323....
Han Cai, Chuang Gan, Tianzh Wang, Zhekai Zhang, and Song Han. Once for all: Train one network and specialize for efficient deployment. In International Conference on Learning Representations, 2020. URL http::::: /ttp::://////v.v/a wttp:///ttpptpppttpp.optopptt wwt.:////pppp..../////// 1908. 09791. pdf
Kuang- Hua Chang. Chapter 5 multiobjective optimization and advanced topics. In
Kuang-Hus Chang (ed.), Design Theory and Methods Using CAD/CAE, pp. 325-406. Aca- demic Press, Boston, 2015. ISBN 978-0-12-398512-5..
doi: http:///di..rr/10..000
arriclee/s1//37772238888222
Ivo Couckuyt, Dirk Deschrijver, and Tom Dhaene. Fast calculation of multiohjective probability of improvement and expected improvement criteria for pareto optimization. Journal of Global Optimization, 60(3):575-594, 2014.
Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hypervolume improvement for parallel multi-objective bayesian optimization. arXiv preprint wxXvv22006.0507.. 2020.
J. L. P erez De la Cruz, J. L. P' erez De la Cruz, L. Mandow, and L. Mandow, A new approach to multiobjective search. Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI'05, pp. 218 223, 2005.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2):182-1)) 187-197, 2002a. doi: 10.1 109/ 4235.996017
10

---

Published as a conference paper at ICLR 2022
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable multi-objectivve optimization test problems. In Proceedings of the 2002 Congress on Evolutionary Computation, CEC' (Cat. No.02TH8600), volume 1, pp. 825 830 vol.1, 2002b. doi: 10.1009/CEEC2002.0007033
Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference--ointee point-basedd nondominated sorting approach, part i: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4):577-601, 2014. doi: 1091 /IEVC.2013.2281533.
Guoqiang Deng, Zhangcan Huang, and Min Tang. Research in the performance assessment of multi-objective optimization evolutionary algorithms. In 2007 International Conference Com- munications, Circuits and Systems, pp. 915-918. IEEE, 2007.
Xuanyi Dong and Yi Yang. Nas-bench-200 201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations (ICIR), 2020. URL https?
//openreview.o net. forum? (oooummm1--HHXy2333KK..
Xi Fang, Wenwen Wang, Lang He, Zhangcan Huang, Yang Liu, and Liang Zhang. Research on improved nsga-ii algorithm and its application in emergency management. Research on Improved NSGA-II Algorithm and Its Application in Emergency Management, 2018. doi: 10.1155/2018 1306341.
M. Fleischer. The measure of pareto optima applications to multi-objective metaheuristics. In Carlos M. Fonseca, Peter J. Fleming, Eckart Zitzler, Lothar Thiele, and Kalyanmoy Deb (eds.), Evolutionary Multi-Criterion Optimization, pp. 519-533, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
Nyoman Gunantara. A review of multi-objective optimization: Methods and its applications. Cogent Engineering, 5(1):1502242, 2018. doi: 191.:223311911.118..1811
Tatsunori Hashimoto, Steve Yadlowsky, and John Duchi. Derivative free optimization via repeated classification. In International Conference on Artificial Intelligence and Statistics, pp. 2027-2036.
PMLR, 2018a.
Tatsunori Hashimoto, Steve Yadlowsky, and John Duchi. Derivative free optimization via repeated classification. In International Conference on Artificial Intelligence and Statiticss, pp. 2027-2036. PMLR, 2018b.
Oliver Hinder. Cutting plane methods can be extended into nonconvex optimization. In Conference On Learning Theory, pp. 1451-1454. PMLR, 2018.
Christian Igel, Nikolaus Hansen, and Stefan Roth. Covariance matrix adaptation for multi multi-objective optimization. Evolutionary Compulation, 15(1):1-28, 2007, doi: 10. 20.11662vvoo22007.555.22
Christian Igel, Thorsten Suttorp, and Nikolaus Hansen. Steady-state selection and efficient covariance matrix update in the multi-objective ema-es. In Shigeru Obayashi, Kalyanmoy Deb, Carlo Poloni, Tomoyuki Hiroyasu, and Tadahiko Murata (eds.), Evolutionary Multi-Criterion Optimization, pp. 171-185, Berlin, Heidelberg. 2007a. Springer Berlin Heidelberg.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference Machine Learning, pp. 1839-48448 PMLR, 2020a.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Multi-objective molecule generation using interpretable substructures. In International Conference on Machine Learning, pp. 4859-4859. PMLR, 2020b.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimizaation, 13(4):455-492 1998.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Tomás Lozano-Pérez Bayesian optimization with exponential convergence. 2015.
11

---

Published as a conference paper at ICLR 2022
Beomjoon Kim, Kyungjae Lee, Sungbin Lim, Leslie Kaelbling, and Tomás Lozano-Péree Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 901999996999999 19149924, 2020.
Tachyeon Kim, Jaeyeon Ahn, Nakyil Kim, and Seyoung Yun. Adaptive local bayesian optimiza- tion over multiple discrete variables. URL http:p/://vaaooaccciiireoeooeeee www.erddd.bol.....o core pdf.
wi ndows wwt.:/ttppp.peeeeeeeeeee
Knowles. Parego: a hybrid algorithm with on-line landscape approximation for expensive multiob- jective optimization problems. IEEE Transactions Evolutionary Computation, 10(1):50 66,
2006. doi: 10.1109/TEV..2200...8 127.7444...
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), Machine Learning: ECML 2006, pp. 282-293, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-44056-5.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Manoj Kumar, George E. Dahl, Vijay Vasudevan, and Mohammad Norouzi. Parallel architecture and hyperparameter search via successive halving and classification. CoRR, abs/ abs/1805.1000 1001110055.55 201 8.
URL htttp:////axii org/ aws/1805. 10255
H. T. Kung. Luccio, and F. P. Preparata. On finding the maxima of a set vectors. J. ACM, 22(4) 476, October 1975. ISSN 0004-5411. doi: 10. 10.1145//21906.321990 URL https
0/col.org/100.1115/22150000 321910
Miqing Li, Shengxiang Yang. and Xiaohui Liu. Diversity comparison of pareto front approximations in many-objective optimization. IEEE Transactions on Cyhernetics, 44(12):2568 2584, 2014.
Xingtao Liao, Qing Li, Xujing Yang, Weigang Zhang, and Wei Li. Multiobjective optimization for crash safety design of vehicles using stepwise regression model. Structural and multidissiplinary optimization, 35(6):561-569) 2008.
GV Loganathan and Hanif D Sherali. A convergent interactive tetting-plane algorithm for multiob- jective optimization. Operations Research, 3553)336 1987.
Ilya Loshchilov, Mare Schoenauer, and Michèle Sebag. A mono surrogate for multiobjective optimization. In Proceedings of the 12th Annual Conference Genetic and Evolutionary
Computation, GECCO '10, pp. 471-478, New York, NY, USA, 2010. Association for Com- puting Machinery. ISBN 9781450300728. doi: 10. 80.1445/1
URL https
//dei.org/ 1ttp://1...115113553311222
Rémi Munos. Optimistic optimization of deterministic function without the knowledge of Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Wein- berger (eds.). Advances in Neural Information Processing Systems, volume 24. Curran Asso- ciates, Inc., 201 la. URL 7e889fb7 1erfft6660007cc11720 113.0000771333355522626622-3-333 2
its smoothness.
www.iinnnnnneuurrneeeee nwwrips wttprr/iss.cpppppe/////////////e
Rémi Munos. Optimistic optimization of a deterministic function without the knowledge of its smoothness. Advances in neural information processing systems, 24:783-791, 20.
Linqiang Pan, Cheng He, Ye Tian, Handing Wang, Xingyi Zhang, and Yaochu Jin. A classification- based surrogate-assister evolutionary algorithm for expensive mbje-objective optimization. IEEE Transactions Evolutionary Computation, 23(1):74 88, 2019. 2802784.
doi: 10.1109/TEVC.2013
Lie Meng Pang. Hisao Ishibuchi, and Ke Shang. Nsga-ii with simple modification works well on a wide variety of many-objective problems. IEEE Access, 8:190240-190253 2020. doi: 10.1 10/110//ACEESS.20 2.0.0.0350000000332220
Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible multi-objective bayesian optimization approach using random scalarizations. CoRR, abs/18055.1 12168, 2018. URL http:
//axxiv. wttpxiiorrgaab///o 805. 121
12

---

Published as a conference paper at ICLR 2022
Wolfgang Ponweiser, Tobias Wagner, Dirk Biermann, and Markus Vineze. Multiobjective optimiza- tion on a limited budget of evaluations using model-assisted -astttttddmmttie selection. In Günter Rudolph, Thomas Jansen, Nicola Beume. Simon Lucas, and Carlo Poloni (eds.), Parallel Problem Solving from Nature - PPSN X, pp. 784-794, Berlin, Heidelherg, 2008. Springer Berlin Heidelberg.
Mikita Sazanovich, Anastasiya Nikolskaya, Yury Belousov, and Aleksei Shpilman. Solving black-box optimization challenge via learning search space partition for local bayesian opti- mization. URL/https: va oha chi rpprod. blob. core. w ndows. net.papers/ jetbrains.pon
Chun-Wei Seah, Yew-Soon Ong, Ivor W. Tsang, and Siwei Jiang. Pareto rank learning in multi- objective evolutionary algorithms. 2012 IEEE Congress on Evolutionary Computation, pp. 1-8, 2012. doi: 10.1109/CEC:220222222565
Nidamarthi Srinivas and Kalyanmoy Deb. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary computation, 2(3):221 -24-288, 1994.
Bradley S. Stewart and Chelsea C. White. Multiobjective a* J. MM oct 1991. ISSN 0004-5411. doi: 10.1145/1 15234.1136333 URL httpss///b....rrg11111155511//// 116368
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-22 2944 1933.
Chi Tung Tung and Kim Lin Chew. A multicriteria pareto-optimal path algorithm. European Journal of Operational Research, 62(2):203-20)) 1992. ISSN 0377-2217. doi: https:/doi.org 10.1016/037--2117099990444 8. URL http::ttt////t wwwp:wwwwwwww.wwwwwww.w... rect wwt..cccmccc.eeeee science/ atticle/p.1/03372111222222
Jessica Vamathevan, Dominic Clark, Paul Czodrowski, Ian Dunham, Edgardo Ferran, George Lee, Bin Li, Anant Madabhushi, Parantu Shah, Michaela Spitzer, et al. Applications of machine learning in drug discovery and development. Nature Reviews Drug Discovery, 1866):463-477, 2019.
David A Van Veldhuizen and Gary B Lamont, Evolutionary computation and convergence to a pareto front. In Late breaking papers at the genetic programming 1998 conference, pp. 221-222124 Citeseer, 1998.
Douglas AG Vieira and Adriano Chaves Lisboa. A cutting- planee method nonsmooth multiobjective optimization problems. European Journal of Operational Research, 275(3):822-829, 2019.
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning action space. CoRR, abs/1906.06832, 2019. URL http?
//axiv.org/absa /9066 06832
Linnan Wang, Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using monte carlo tree search. arXiv preprint arXiv:2007.00708, 2020.
Ziyu Wang, Babak Shakibi, Lin Jin, and Nando Freitas. Bayesian multi-scale optimistic optimization. In Artificial Intelligence and Statisties, pp. 1014-1014 PMLR, 2014.
Kaifeng Yang, Michael Emmerich, André Deutz, and Thomas Bäck. Multi-objective bayesian global optimization using expected hypervolume improvement gradient. Swarm and Evolu- tionary Computation, 44:945- 2019. ISSN 2210-6502. doi: https://doi.rr//0.0016/// 2wevo.2018.10.000 URL httpt::///// wwww://www///./////////////ww//w sci encedi rect contt.com/sae www..////ciine/aattiiioc.om p11/2221065011737188
Kevin Yang, Tianjun Zhang, Chris Cummins, Brandon Cui, Benoit Steiner, Linnan Wang, Joseph E. Gonzalez, Dan Klein, and Yuandong Tian. Learning space partitions for path planning. CoRR, abs/2106. 10544, 2021. URL /ttps::////xvv wrg. /216 10544
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint arXiv: /902/990220048 2019.
2019.
13

---

Published as a conference paper at ICLR 2022
Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712-71,, 2007. doi: 10.1109/TEVC.2000. 892759.
E. Zitzler, L. Thiele, M. Laumanns, C.M. Fonseca, and V.G. da Fonseca. Performance assess- ment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117-132, 2003. doi: 10.1 100.7
Eckart Zitzler, Kalyanmoy Deb, and Lothar Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary computation, 802):173-195, 2000.
14

---

Published as a conference paper at ICLR 2022
A PROOFS
Lemma 1. The algorithm to uniformly draw k samples S, pick the best and return is (1, 1) -raale..
Proof. Consider the following simple (1. 1) -racle 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 Sgoud and Stad- Other points are randomly assigned to either of the two subsets. Then if x" happens to be among the & collected samples (which happens with probability k/|S)), definitely we have x E Sgood Therefore, we have:
(-
A
P [xx E Sgood x
E EE
2
exp
[S|]
which an oracle with = 1. The last inequality due to e 2 + x (and thus
1 - x.)..
Lemma 2. Define (A) IR + 12t as:
(( : + Σ we log
1+ 1
(8)
Away
The following maximization problem
T
T
max [x
log (1 e
s.t. Σ
Wizt =
(9)
1=1
1=1
has optimal solutions
27 = log 1+ (+11)
IsTST
(10)
Awa
where X is determined by g(A) K. With optimal
{2t}, the objective reaches E, log(1 + Auxa).
Proof. Its Lagrange is:
T
T WiZt K
J ((z+)) = Σ log (1 - -2) -
-
Σ
(1I)
t=1
1=1
Taking derivative w.r.t. 2, and we have:
0J
e 21
AW = 0.
02
e -
Aw = 0
- 2
1
+ Aw
1- 1-e 2
(12)
1 1- 1-e
1 + Awa Aw
1
+ Awa
I + Awa
Aw
1 + Aw;
1 Awa
= - loog
log
log
1+
1 Aw,
XW,
Lemma 3. Both g(A) and g (2) are monotonously decreasing. Furthermore, let w -1
T (2t w, wi²) be the Harmonic mean of {we} and Wmax == max Wes we have:
max < T exp(WmixJ//T)
exp( p exp(w-ly/1l) L - S ( S
(13)
y
15

---

Published as a conference paper at ICLR 2022
Bounds of gy) (large span)
Bounds of (y) (small span)
upper
upper
lower bound
lower bound
1-
1-
1og
0-
-1-
-2
-2
Figure 8: Upper and lower bounds of (v) with different {wi}. Left: wi 2luuspace -001,,1)) Right: w, 2linspace(2.5), Small {wi} span leads to better bounds.
Proof. It is easy when À increases, each term in (A) decreases and thus g(A) is a decreasing function A. Therefore, its inverse mapping 9 (z/ is also decreasing.
Let μ(y) == 1/g (v) O. Then have:
T We log 1+
m(y)
(14)
WGr
t=1
It is clear that when 0, p(y) = 0. Taking derivative with respect to in both side, we have:
= (1(y))
(15)
w(v)
where p'(y)= du(v) dy
the derivative of ply). Using the property of Harmonic mean, we have:
m(y)
(1 1
ju(y)
(1())
Σ
(16)
p(v)
We
This gives:
(1)
1
(17)
mLy)/u
T
Integrate on both side starting from = 0, we have;
"
w logg(1 + p(y)/0)
y
(18)
Using (0) = 0 thus have:
y
1 logg111 (1 + u(y)/w) 1)) <
(19)
T
This leads to ply) S w [exp(ynū (ifiino-1/T) 1/T) -1 With (2) = 1/p(v), we arrive the final lower bound for (y). For an alternative upper bound of g (y), we just notice that (here Wmax max wy):
T
T
p(v)
(1())
(20)
pivl
T
Wmax
Wanax
Using the same technique above, have u(y) bound of g (v) follows.
Wmax
[exp(yr
(appywmmax/TT /T) 1] and the upper
Finally, note that ex 2 1 + x, we have
W max
W Wmax T
(21)
exp Wimax
Wmnxx
y
n
16

---

Published as a conference paper at ICLR 2022
Theorem 1. Following optimal sequence, the algorithm yields reward r" lower bounded by the following:
logg2 1,N"0(a, T)
r" Σ rb exp
T
(22)
K
where TO = N and b(a, T) ; (1 - a azl - (1-2-a).
Proof. First note that [ST] |5ol/2 and thus
|3 2 2
/N. So we just need to bound P(x" ST),
which can be written as:
T
T
(-
P(x" E ST)
II
P(x* E S SS-)) 2
II t=1
1 - exp
(23)
S1)SS-11
Therefore we have
T
(- his
log P(x E ST) 2
Σ log 1 1-exp
exp
(24)
S
We want to find the action sequence {kie so that log P(x" E ST) is maximized. Let wy = 10=nn/S.2 and know that
S/St-110
and 24 = //, applying Lemma 2
T Σ
max log P(x* ST) (kr)
log(1 + Xw))
(25)
where the Lagrangian multiplier À satisfies the equation g(A) K.
Now we have:
T 1 1+
Σ
log(1 + Awn)
log
Wi
(26)
K
t=1
T
log
1 K
1222
(27)
Na
(28)
K
2a(t-1)
NTNa
o(a, T)
(29)
K
Here ! due to Lemma 3 which tells that = (K) S ST/K, 2 due uy = St -1 1a and
:
|St-1 S N N/2 and 3 due to log(1 + z) I
Putting all of them together, we know that
2 exp (o((a, TIN
2 max (ka)
ST P(x E ST)
(30)
Optimal action sequence (k))- From the proof, we could also write down the optimal action
sequence that achieves the best reward: ky = we log + Aw: where wi = S1 Using
Lemma 3 we could compute the upper and lower bound estimation of X = - (K). Here : =
T DT w5²)
be the Harmonic mean of {we) and Wmax max Wy:
exp( xxp()= SAS
max
(31)
K/T)
With X, we could compute approximate {kr). Here we make a rough estimation of {kz} we terminate the algorithm when |Sr| is still fairly large. This case corresponds to the setting T
17

---

Published as a conference paper at ICLR 2022
8log2 N where 3 < 1 and all we ~ No. With K = (NN)) as in semi-parametric case, -0 K (1), exp(@" (xp((w-K/TT) K/T)- - - = w a- K/T and Aw, ~ log, > 1. Since log(1 + z) = æ for small æ,
we have ky ss W/ Xwy 1/A, which is independent of Therefore, constant amount of sampling at each stage is approximately optimal.
Observation 1. If all fa are isotropic, fx(x) | c,llă. then Qp ConvexHuullcu,..... CMM)
Proof. Consider J(x; p)) = Σド=1 Hj (x) (x) where the weights Pi 2 satisfies Σj My 1. For
brevity, we write the constraint as A = {u μjj 2 O, E5 M4 = 1}.
Now consider the Pareto Set Qpp = fx 3u A VxJ(x: (2) = 0}. We have the following:
vx =0
(32)
E My [x)x =0
(33)
Σ [1sx -0)=0 =0
(34)
Σ, Ej 14 -
Σ mye
(35)
The last step is due to the fact that Ej Mj 1. Therefore, for any Ωp, x is convex combination of (ci,-..,CAM, } and thus x (annee. CI, we know [x; (1) and thus x E S2p.
Conversely, for any
Observation 2. If 2 and fx(x) (x- - T H2 c₁) where H2 are positive definite
symmetric matrices, then there exists W1 == H22 - -i) and w2 == Hi(c1 C2), so that for any
X E Qp, wi (x c1) and w (x c2) 20
Proof. Following Observation I similarly we have for all x E Sp, E, Hy cạ) = 0. which gives:
x= [
Σn,H
(36)
Note that this an expression of the Pareto Set 2tp.
Let A, == (2 H. Then E, Aj I. Note that while E, My Hj and (y, are positive definite matrix. A, may not be.
Let M E, H, Since μ E A, M is matrix. Note that we have
Eu,H,e = Σu,H,c, - EM,H,, + EugH,co
(37)
ΣnjH,(c - -ct) + +Mcx
(38)
jfk
Using Eqn. 36 we know that x = M E, Mij H,C, = cs + - Ejth CogkHyHHii MgH - cc).
For M 2, have x c2 M 11H | (C: -c2). So we have
(c1- 02) Hix = (c) c2) T HiC₂ + (c1 - -2 HHM - C2)
(39)
(c) 02) HiC₂
(40)
This is because (c1 - 022 H H1 (c, C2) 2 0 since H is a PSD matrix. Therefore.
let wa == Hi (c) C2) and we have w (x C2) O. which is independent of μ A. This means it holds for any x 6 S2p.
Let w H2(C2 c1), then similarly have wI (x c1) 2 0 for all x E sp..
18

---

Published as a conference paper at ICLR 2022
B QUALITY INDICATORS COMPARISON
Table 1: The review of different scalarizing methods.
Quality Indicator
Convergence
Uniformity
Spread
No reference required
HyperVolume Volume
GD
IGD
MS
ONVGR
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 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 hardly to get in real- world problem. Maximum SMS) (Zitzler et al. (0000) computes the distance between the farthest two points of samples to evaluate the spread. (pacing(S) (Bandyopadhyay et al. (004)) 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 Tooleedenme demonstrates the good characteristics of each quality indicators.
C END-TO-END LAMOO PSEUDOCODE
Below we list the pseudocode for the end-to-end workflow of LaMOO in Algorithm 2 Specfically, 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.
I: Inputs: Initial Do from uniform sampling, sample budget T,
for ==t==o ..... do
3: Set C + {Rroot (collections of regions to be split).
4:
V,u,n +- Split(C. D2)
5:
A - Select(C,, D,)
6:
D.+1 Sample(k)
end for
8:
9:
Function Split(C, D.)
10:
while L # 9 do
11:
Q2 + prop_irst_eles ciist_element()), Dr.5 + Dr n Rey + DD.pl-
12:
Compute dominance number or,, of Di., using Eqn. 5l train SVM model (()).
(Dr,j, is splittable by SVM, then L + Lu Partition((I, (())).
end while
15:
16:
Function Select(Cp. D2)
17:
for &s = root, is not leaf node de
18: D D. n.no Ue U1. Hyper Volume())) nu. De
1: + ara max UCBr,, where UCBr,c = ve.c + 20p / /2log(me.
19:
children(k)
20: end for
21: return k
22:
23:
Function Sample(k)
24:
DEa +- D, Dnow. where Dnew drawn Qh based on gEHVI or CMA-ES.
25:
return D; U Dnew
19

---

Published as a conference paper at ICLR 2022
D EXPLORATION FACTOR(CC) SETUP WITH UNKNOWN MAXIMUM HYPERVOLUME
2.0
9.13%
Log Hypervolame Difr
Log typervolrme
1.5
0.2
10
0.5
0.5
0.0
00.6
100
60 Samples
20
60
100
Samples
Semples
(a) BraninCurrin
(b) VehicleSafety
(c) Nasbench201
Figure Sampling with static Cp(10% of HVmaz) and dynamic Cp((10% of HV (Veurrent))
As we mentioned in the paper, "rule of thumb" is to set the Cp to be roughly 10% of the maximum hypervolume HVmax. If HVmax 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 three problems Cerrannn-Curinn, 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
1.5
M500-11
OHAES
2.0
CMAES 1956
6200
2004
CMAS5
Loq Popervolume
WHOZAD
Log topervolume
CHASSH
1000.00
Log Hyparcolume
DRAES
19055D
1.0
-0.5
0.5
1.0
0.0
-1.0-
0.0
-1.5
1000
200
400
600
Average Cumulative Wall Clock Timels)
Average Cumulative Wall Clock Timels!
Average Cumulative Wall Clock Timels)
(a) BraninCurrin
(b) VehicleSafety
(c) Nashench201
Figure 10: Wall clock time in different problems
Fig. 10 shows the wall clock time different search algorithms in BraninCurrin Belakaria et al. 2019). VehicleSafefy (Liao et al. 2008) and Nasbench201 (Dong & Yang 2020).
F DETAILS OF BENCHMARK PROBLEMS
F.1 PROBLEM DESCRIPTION
BraninCurrin (Belakaria et al.
2019):
5.1 * (15x1
5)2
75x 25
10
(x1,
(15rr²
-5)² (10
cos (0111x 5)
4
8
2300x + 1900xz?
2092x + 60
((2 1 exp
(2xr2)
100x + 500x + 4x +
20

---

Published as a conference paper at ICLR 2022
where 22, E [0, 1].
VehicleSafefy LLio et al.
2008):
(x) 1640.2823 + 2.35732852 + 2.32200552, 4.568776822 + 7.72136332 + 4.45595042;
fz(x:) 6.5856 1.152; + 0.9738m 0.8364r, 0.36952, + 0.08612143
+ 0.3628.2244 -
fa(x) = -0.0551 + 0 +0042 0..073
+ 0.024r243 0.0118x244
0.0204r²34 - 0.008r325 0.0241x3 0.0109
where E [1.3]
Nasbench201 (Dong & Yang 2020):
zeroize
2
skip-connect
1x1 convolution
3x3 convolution
3x3 average pool
Figure 11: A general architecture of Nasbench201
In Nasbench201, the architectures are made by stacking the cells together. The difference among architectures in Nasbench201 the design of the cells, see fig [T Specifically, each cell contains nodes, and there is particular operation connecting to two nodes including zeroize, skip-connect, 1x1 convolution, 3x3 convolution, and 3x3 average pooling. Therefore, there are C² = 6 edges in cell and 5 =15225 unique architectures in Nasbench201. According this background, Each architecture can be encoded into a 6-dimensional vector with discrete numbers (i.e., 0, 1, 2, 3, 4 that corresponds to zeroize, skip-connect, 1x1 convolution, 3x3 convolution, and 3x3 average pooling).
f1( Accuracy(2 x)) fa(x) = #FLOPs(x)
where x E 1,,1,2,3,44 4
DTLZ2 (Deb et al. 2002b):
(x) = + g( 008
01 000
M-
FM
008
(2TMM -M1)
( TM
2
π
f2(2) = (1 + g( m)) co8
21 ... cos
2
22)
sin
2 xM
fs(#) = (1 + g x M co8
- #1) ... sin
( M -2)
π fx)(x) = (1+ g(xm)) sin x1)
where g(x) Emeery (x; - (05)2. x E [0, 1jd, and æw represents the last d - + 1 elements of
21

---

Published as a conference paper at ICLR 2022
F.2
VISUALIZATION OF PREETO-RRONTERR FOR BENCHMARK PROBLEMS
sumpo a pawts-fartee
contororter
-0.05
011
-35
-3
2022 20 2002019925577 e2er
10
-20
-50
-00
F200 (b) VehicleSafety
(a) BraninCurrin
(c) Nasbench201
Figure 12: Visualization of Pareto-fromtier BraninCurrin, VehicleSafety as well as Nashemch201.
F.3 REFERENCE POINTS
t: M represents the number of objectives.
Problem
Reference Point
BraninCurrin
(18.0, 6.0)
VehicleSafety
(1864.72022, 11.81 11.81993945, 0.2903999384)
Nasbench201
(-3.0, -6.0)
DTLZ2
(1.1, ... 1.1) E R
(0.0, .... 0.0) E RM
Molucule Discovery
Table 2: The reference points for all problems in this work.
The reference point R E R is defined to measure the hypervolume of a problem. Different reference point would result in different hypervolume. The details can be found at see Table claborates the reference points in the problems throughout the paper.
F.4 MAXIMUM HYPERVOLUME OF EACH PROBLEM
Problem
Maximum Hypervolume
BraninCurrin
59.3601 1874867746
VehicleSafety
146.8160708 1 187002
Nasbench201
8.06987476348877
DTT.Z2(2 objectives)
1. 1.44601659331551778
DTLZ2(I0 objectives)
2.5912520655298055
Molucule Discovery
N/A
Table 3: The maximum hypervolume for all problems this work.
Table 3 elaborates the observed maximal hypervolume the problems throughout the paper. We used these value to calculate the log hypervolume difference in fig 3 and fig 4
G EXPERIMENTS SETUP
Experiment details: For small-scale problems(i.e. Branin-Currin, VehicleSafety, and Nasbench201) and DTL.22 with 2 and 10 objectives. We randomly generate 10 samples the initialization. For
22

---

Published as a conference paper at ICLR 2022
multi-objective molecule discovery, the number of initial samples is 150. In each iteration, update 5 batched samples(q value) for search algorithms.
Hyperparameters of LAMOO: For all problems, leverage polynomials the kernel type of SVM and the degree the polynomial kernel function is set to 4. The minimum samples in the leaf of MCTS is 10. The ep is roughly set to 10% of maximum of hypervolume(i.. 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 5. The acquisition function is optimized with L-BFGS-B B (with maximum of 200 iterations). In each iteration, 256 raw samples used for the initialization heuristic are generated be selected by the acquisition function. In original work Daulton et al. 2020), they used 1024 raw samples but we decrease this number to 256 to sample budget of all methods for comparison. which speeds up the search but may lead to lower performance such as vehiclesafty problem in fig. 3 As the same claim in Daulton et al. (2020), each generated sample modeled with an independent Gaussian process with Matern 5/2 ARD kernel.
H VERIFICATION OF LAMOO ON MANY-OBIECTIVE PROBLEMS
11
Figure 13: Dominance number distribution with 50 random samples on DTLL22(11 objectives)
Hyparoolume
0.2
whole selected region
Figure 14: The range of hypervolume for 50 samples randomly generated from different regions in DTL.22(10 objectives). We generate 25 times of 50 samples in total.
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). number of objective is not too large(i.e. M < 10), the samples can be still split by dominance number. Given the problem(DTLZ2 with 10 objectives) shown in fig 4 randomly generate 50 samples in the search space and draw the dominance distribution of them 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. [4]shows the range of hypervolume of the samples generated from good regions, the whole space, and bad regions. From
23

---

Published as a conference paper at ICLR 2022
the figure, we that the hypervolume of samples generated from good regions are significantly higher than others.
COMPUTATIONAL COMPLEXITY ANALYSIS OF LAMOO
Here detailed breakdown of the computational complexity of our algorithm (Alg.
Line.6: Compute dominance: O(MNnode 2) where Nnode is the number of samples in the node and M is the number dimensions.
Line 7: Time complexity of SVM: O 3) where Noode the number of samples in the node.
Line 10: Hypervolume: O(N M N log N)M 3) (Beume Rudolph 2006) or O(N log (NM S. 3) (Beume et al. 2009), where N is number of searched samples in total and D is the number of dimensions.
Total time complexity: Ei= O(N, (M < 3), where t is the total number of nodes. Σ'= O(N 4 N₁ log N,) (M 3), where is the total number of nodes.
When there are more than 3 objectives (M 3), HV computation is the dominant factor. When M S 3, the optimization cost of SVM the dominant factor.
J VARIATION OF LAMOO WITH CHEAPER OVERHEAD
Algorithm 3 LaMOO Pseudocode with leaf based selection.
1: Inputs: Initial Do from uniform sampling, sample budget T'
2: for ft= ......TTT do
3: Set C {S2root (collections of regions to be split).
while L # do
5:
2, 5 hop_firs__elemnntte
Dr.5 + Dr nΩ2, Ba. + -D,l-- Compute dominance number or, of Dr.; using Eqn. 5lnd train SVM model A(-).
6:
7:
If (D..,. is splittable by SVM, then L +- fU Partition(((,,A())))
8:
end while
9:
for & root, is not leaf node do
10:
D., + D. 2.n6 S4. Pe.k + DD.
11:
end for
12:
for l is leaf node do V4. Hyper Volume)
14:
end for
UCB,,, where UCB., = Ve,1 + 2Cpp 20 where p is the parent of (. 16: De-1 D, U Drew, where Dnew is drawn from S2 based QEHVI CMA-ES.
15: Is <- arg
max
LE leaf nodes
end for
Lanoo
2.0
Log Hypervoluee Dift
1.5
Log Hypervolume Diff
0.0
Hypervolune
1.5
1.0
-0.2
1.0
-0.4
0.5
-0.6
20
40
100
60 Samples
20
40
60
80
100
Samples
Samples
(a) BraninCurrin
(b) VehicleSafety
(c) Nasbench201
Figure 15: Search progress with sample
24

---

Published as a conference paper at ICLR 2022
2.0
Log Hynervelumc Dff
2.5
Log Hypervolume Diff
0.0
Log Hypersolums
1.0
-0.2
1.0-
0.5
-0.4
-0.6
50
100
200
250 Timels)
1000 Average Cumulaaiie Timets)
100
200
300
400
Average
Average Cumulative
Time(s)
(a) BraninCurrin
(b) VehicleSafety
(c) Nasbench201
Figure 16: Search progress with time
Instead 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. iillustraees the detail 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. Figure.[15andd figure. 16] validate the variation that is able reach similar performance of searched samples but saves lots of time. We leave the validation of others problems in the future works.
K
ADDITIONAL RELATED WORKS
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
(Hashimoto et al. 201 Sa
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 1a Wang al. 2014; Kawaguchi et al. 2015) can be seen the first work to use MCTS to build hierarchical space partitions. But their partitions are predefined (e.g.. Voronoi graph, axis-aligned partition, ctc) without learning (or adapting to) observed samples far, except for (Wang et al. 22199 2020 Yang al. (02
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 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.
LaMOO V.S. LaMCTS/LaNAS: First, the mechanism of the partitioning of the search space is different. LaMOO uses dominance rank to separate good from bad regions, while LaMCTS uses k-mean for region separation. LaNAS is even more simple: it uses the median from the single objectives of currently collected samples and a linear classifier to separate regions.
LaMOO V.S. LaP3; LAP3 is planning algorithm tailored to RL with a single objective function. LAP also utilizes the representation learning for the partition space and planning space, while our LaMOO doesn't.
25


Reviews:
[{"review_id": "x2975YHbTqk", "reviewer": "Reviewer_vdwH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths.\n- The proposed method uses an interesting combination of algorithms.\n- The results are compelling.\n- The paper is well written. It is easy to understand, well-organized, and the illustrations help understand the behavior of the algorithm.\n\nWeaknesses.\n- It is possible to criticize that it is a combination of existing techniques\n(which is not a serious issue, in my opinion).\n- Some papers propose Multi-Objective optimization using A* search.\nI think the related work section should mention these.\nThe following short paper covers some of such papers as of 2011.\nhttps://www.ijcai.org/Proceedings/11/Papers/483.pdf\n- A part of the algorithm that \"updating all previous samples\" may take a long time for larger-scale problems because the time will be O(N^2) to the sample size N.", "summary_of_the_paper": "This paper proposes to use MCTS to enhance existing algorithms for Multi-Objective Optimization problems.\nExperimental results on a wide range of benchmark problems show the improving performance of the proposed method, LaMOO.\n", "summary_of_the_review": "In my opinion, the significant improvement in performance with a simple method is highly valuable.\nThe idea is simple, well-explained, and the results are promising.\nThis paper should be valuable for many applications.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "aQsYZ4xdqzm", "reviewer": "Reviewer_Vetj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper seems to be the first work by extending the space-partition approach for SOO to MOO. The metric of dominance number is reasonable and easy-to-follow. This paper is well organized, with good background understanding and proper motivations. Sufficient theoretical analysis and experimental demonstration are provided.\nHowever, this paper still suffers from the issue of insufficient presentation. Some revisions are need to further improve the quality of the paper, listed as:\n1.\tThe full name of UCT should be given.\n2.\tIn Algorithm 1, the sample budget T is used as the termination condition. But it is unclear how to set it in the experiments.\n3.\tThe computational overhead of LaMOO is not very clear. It is better to give a time complexity analysis for LaMOO.\n4.\tIn LaMOO with CMA-ES, the generated solution is constrained to be within the leaf region, but how? In addition, if such a constrain is frequently implemented, does it deteriorate the search efficiency?\n5.\tIt is unclear why the optimization dimension of Nasbench201 is 6. More interpretations are needed.\n6.\tIn page 8, the authors said there are 1000 samples given for three different tasks. But in Fig. 4, only 200 samples are shown. Why?\n7.\tHow to set Cp when HV_max is unknown?\n8.\tPlease have your submission proof-read for English style and grammar issues. For example, there are syntax errors in “LaMOO+qEHVI achieve”, “Thanks to MCTS, LaMOO also considers …are given 1000 samples”, “LaMOO help”, “to performs”, just mention a few. \n9.\tThe paper “Learning space partitions for path planning” was cited twice. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "A good paper with clear motivation, interesting idea, solid theoretical and experimental demonstration, but some presentations are not very clear. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NIs_QrJ3lA", "reviewer": "Reviewer_2MfT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n\n+ This work is well-organized and generally well-written.\n\n+ The studied problem, multi-objective optimization, is important and could be useful for many real-world applications. \n\n+ The proposed LaMOO method is a reasonable generalization from LaMCTS to multi-objective optimization.\n\n**Weakness:**\n\n*Method:*\n\n**1. Novelty:** \n\n- **Incremental Contribution:** The proposed LaMOO is a direct generalization from the LaMCTS method to multi-objective optimization (MOO). The novel part is to use dominance number as criteria for search space partition and hypervolume for promising region selection. These are all straightforward generalizations for MOO. The contribution of this work is somewhat incremental along the line of LaNAS, LaMCTS, and LaP^3. \n\n- **Missing Closely Related Approaches:** This work claims the proposed approach to learn the promising region is *fundamentally different* from the previous works. However, many classification-based search space partition methods have been proposed in the machine learning community, see [1][2][3] (classification + random sampling). (Tree-based) space partition methods have been widely used for black-box optimization [4][5][6]. In addition, there are also different works on classification-based MOO [7] (SVM + NSGA-II/MO-CMA-ES) [8] (Ordinal SVM + NSGA-II) [9]. \n\n\n**2. Theoretical Analysis:**\n\nA large part of this work is on the theoretical understanding for space partition and LaMCTS. However, the analysis is mostly for single-objective optimization, and the extension to multi-objective optimization is much less promising.\n\n**3. Why LaMOO Works:** \n\nFurther discussions are needed to clearly clarify the properties of LaMOO.\n\n- **Dominance-based Approach for Many Objective Optimization:** LaMOO uses the dominance number as the split criteria to train the SVM models and partition the search space. However, the dominance-based method is typically not good for many objective optimization due to the lack of dominance pressure (e.g., all solutions are non-dominated with each other, and all have the same dominated number). Why is LaMOO still good for many objective optimization? \n\n- **Combination with Multi-Objective Bayesian Optimization (MOBO):** It is straightforward to see the benefit of using LaMOO with model-free optimization (e.g., NSGA-II and MO-CMA-ES). However, it is not so clear to understand why it also works for MOBO (e.g., qEHVI). The qEHVI approach already builds (global) Gaussian process models to approximate each objective function, and uses hypervolume-based criteria to select the most promising solution(s) (e.g., maximizing the expected hypervolume improvement) for evaluation. Therefore, its selected solution(s) should be already on the approximate Pareto front without the LaMOO approach.  Is the good performance due to only use solutions in the promising region to build the models (but I think GP would work well with all data as in the setting considered in this work)? Or because LaMOO restricts the search in the region close to the current best non-dominated solutions (then what is the relation to the trust-region approach [10])?\n \n- **Exploitation v.s. Exploration:** With LaMOO, the solutions can only be selected from the most promising region (e.g., around the current Pareto front), which is good for exploitation. However, will this approach lead to worse overall performance due to the lack of exploration (e.g., cannot find more diverse Pareto solutions far from the current Pareto front)?\n\n**4. Time Complexity:**\n\nWhat is the time complexity of the proposed algorithm? In each step of LaMOO, it has to repeatedly calculate the hypervolume of different regions for promising region selection. However, the computation of hypervolume could be time-consuming, especially for problems with many objectives (e.g., >3). Would it make LaMOO impractical for those problems?\n\n**5. Inaccurate Description for MOO Methods:**\n\n- **CMA-ES:** CMA-ES is a widely-used single objective optimization algorithm [11]. The multi-objective version proposed in (Igel et al., 2007a) is usually called MO-CMA-ES. It is also confusing why most citation for the MO-CMA-ES (in the main paper and Table 1) is for the steady-state updated version (Igel et al., 2007b) but not for the original paper (Igel et al., 2007a).\n\n- **ParEGO:** The seminal algorithm proposed in Knowles (2006) is called ParEGO and the qParEGO is a parallel extension recently proposed in Daulton et al. (2020). It is not suitable to refer the algorithm in Knowles (2006) as qParEGO in Table 1 and the main text.\n\n- **MOEA/D:** In my understanding, MOEA/D is suitable for many objective optimization (objectives > 3), see its performance in the NSGA-III paper (Deb & Jain, 2014), while the main challenge is how to specify the weight vector for a new problem with unknown Pareto front as correctly pointed out in this work. \n\n- **Hypervolume-based Method:** This work indicates the indicator-based method is better for many objective optimization. However, the time complexity and expensive calculation could make the hypervolume-based method impractical for many-objective optimization.\n\n*Experiment:*\n\n**6. Missing Experimental Setting:** \n\nMany important experiment settings are missing in this work, such as the number of initial solutions for MOBO (and its generation method), the number of batched solutions for MOBO (e.g., q), the reference point for hypervolume (during the optimization, and for the final evaluation), the ground truth Pareto front used for calculating the log hypervolume difference for real-world problems (e.g., Nasbench 201).\n\n**7. Comparison to Model-Free Evolutionary Algorithm:**\n\nIt is reasonable that LaMOO can improve the MO-CMA-ES performance since it builds extra models to allocate computation to the most promising region. However, in my understanding, the model-free evolutionary algorithms are not designed for expensive optimization, and their typical use case is with a large number of cheap evaluations with a fast run time. It is more interesting to directly compare LaMOO with other model-based methods (e.g., MO-CMA-ES with GP models).  \n\n**8. MOBO Performance:** \n\nWhat are the hyperparameters for qEHVI? It seems its performance on VehicleSafty problem is worse than those reported in the original paper Daulton et al. (2020). \n\n**9. Wall Clock Run Time:** \n\nPlease report the wall clock run time for both LaMOO and other model-free/model-based algorithms, as in Daulton et al. (2020). \n\n\n**Minor Issues:**\n\nWhen citing multiple works, please put them in chronological order.\n\n**Reference:**\n\n[1] Hashimoto, Tatsunori, Steve Yadlowsky, and John Duchi. Derivative free optimization via repeated classification. AISTATS 2018.\n\n[2] Kumar, Manoj, George E. Dahl, Vijay Vasudevan, and Mohammad Norouzi. Parallel architecture and hyperparameter search via successive halving and classification. arXiv:1805.10255.\n\n[3] Yu, Yang, Hong Qian, and Yi-Qi Hu. Derivative-free optimization via classification. AAAI 2016.\n\n[4] Munos, Rémi. Optimistic optimization of a deterministic function without the knowledge of its smoothness. NeurIPS 2011.\n\n[5] Ziyu Wang, Babak Shakibi, Lin Jin, and Nando de Freitas. Bayesian multi-scale optimistic optimization. AISTATS 2014.\n\n[6] Kenji Kawaguchi, Leslie Pack Kaelbling, and Tomas Lozano-Perez. Bayesian optimization with exponential convergence. NeurIPS 2015.\n\n[7] Loshchilov, Ilya, Marc Schoenauer, and Michèle Sebag. A mono surrogate for multiobjective optimization. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, 2010.\n\n[8] Seah, Chun-Wei, Yew-Soon Ong, Ivor W. Tsang, and Siwei Jiang. Pareto rank learning in multi-objective evolutionary algorithms. In 2012 IEEE Congress on Evolutionary Computation, 2012.\n\n[9] Pan, Linqiang, Cheng He, Ye Tian, Handing Wang, Xingyi Zhang, and Yaochu Jin. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization. IEEE Transactions on Evolutionary Computation 2018.\n\n[10] Daulton, Samuel, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces. arXiv:2109.10964, 2021.\n\n[11] Hansen, Nikolaus, and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 2001.\n\n[12] Ishibuchi, Hisao, Yu Setoguchi, Hiroyuki Masuda, and Yusuke Nojima. Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Transactions on Evolutionary Computation 21, no. 2 (2016): 169-190.\n\n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This work tackles an important research problem that could be useful for different partitioners in the community (e.g., multi-objective optimization, Bayesian optimization, and NAS). The proposed method is a reasonable generalization from the LaMCTS method. However, due to the concerns listed above on both the method and the experimental results, I cannot give a clear acceptance to the current manuscript.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-V7pAyCx62o", "reviewer": "Reviewer_xfNd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and, in my view, it offers a simple but effective \"meta\" perspective for multiobjective programming. In particular, it resembles many criterion-search space techniques that split the objective space for strategic exploration. However, here authors use the dominance metric to partition the primal space, which leads to interesting properties and a tree encoding.\n\nI also appreciate the theoretical aspects investigated by the authors, which are sound to the best of my analysis and give a more concrete justification to the results we observe in the numerical setting. \n\nMy major concern, however, is that it is somewhat unclear when the proposed meta-algorithm is applicable or more beneficial. In particular:\n\n(a) Are there (combinatorial) problems where the tree would need to be significantly large to ensure high-quality points are actually found? I was somewhat confused as to how the tree may grow depending on the underlying structure of the problem.\n\n(b) What are the properties that a multiobjective algorithm would need to satisfy to apply the split partition? For example, suppose one is using a multiobjective mixed-integer linear program to enumerate the frontier. Is it possible to represent complex splits in a way that they encode true partitions? It seems that broader split definitions, for instance in larger-dimension criteria space, could be high non-linear (or perhaps I misunderstood some concept?).\n\n(c) What are the guidelines to set the exploration factor C_p empirically? It seems that it is highly optimized for the numerical experiments that were performed in the paper", "summary_of_the_paper": "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.\n\n", "summary_of_the_review": "A well-written paper that provides an interesting and relevant contribution to multiobjective optimization. One of the key benefits of the method is its generality, in that it can be incorporated into existing multiobjective solvers, and simple implementation. Numerical results suggest significant improvements with little implementation work. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Multi-objective learning is an increasingly important topic. This paper presents a method for better finding parts of the Pareto frontier through a new method to estimate the distance to the frontier and use this proxy to refine the state space partition.  The reviewers found this paper interesting and compelling and generally well written. The reviewers also thought the work could be further improved by better clarifying in the text where the proposed approach might fail, and what properties of the domain are needed, and also to better situate this paper within the related work, potentially including additional experimental comparisons. The authors provided detailed responses to the proposed questions and the authors are encouraged to ensure that these suggestions and discussions are well represented in the revised version.
Decision: Accept (Poster)