Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement
Authors: Samuel Daulton
Maximilian Balandat
Eytan Bakshy
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian Optimization
Gaussian Process
Multi-Objective Optimization

Abstract: Optimizing multiple competing black-box objectives is a challenging problem in many fields, including science, engineering, and machine learning. Multi-objective Bayesian optimization (MOBO) is a sample-efficient approach for identifying the optimal trade-offs between the objectives. However, many existing methods perform poorly when the observations are corrupted by noise. We propose a novel acquisition function, NEHVI, that overcomes this important practical limitation by applying a Bayesian treatment to the popular expected hypervolume improvement (EHVI) criterion and integrating over this uncertainty in the Pareto frontier. We argue that, even in the noiseless setting, generating multiple candidates in parallel is an incarnation of EHVI with uncertainty in the Pareto frontier and therefore can be addressed using the same underlying technique. Through this lens, we derive a natural parallel variant, qNEHVI, that reduces computational complexity of parallel EHVI from exponential to polynomial with respect to the batch size. qNEHVI is one-step Bayes-optimal for hypervolume maximization in both noisy and noiseless environments, and we show that it can be optimized effectively with gradient-based methods via sample average approximation. Empirically, we demonstrate not only that qNEHVI is substantially more robust to observation noise than existing MOBO approaches, but also that it achieves state-of-the-art optimization performance and competitive wall-times in large-batch environments.

Parallel Bayesian Optimization of Multiple Noisy
Objectives with Expected Hypervolume Improvement
Samuel Daulton Facebook, University of Oxford sdaulton@fb.com
Maximilian Balandat
Eytan Bakshy Facebook ebakshy@fb. com
Facebook balandat@fb.com com
Abstract
Optimizing multiple competing black-box objectives is a challenging problem in many fields, including science, engineering, and machine learning. Multi-ohjective Bayesian optimization (MOBO) is sample-efficient approach for identifying the optimal trade-offs between the objectives. However, many existing methods perform poorly when the observations acquisition function, NEHVI, that overcomes this important practical limitation by applying Bayesian treatment to the popular expected hypervolume improvement (EHVI) criterion and integrating over this uncertainty in the Pareto frontier. We argue that, even in the noiseless setting, generating multiple candidates in parallel is an incarnation of EHVI with uncertainty in the Pareto frontier and therefore can be addressed using the same underlying technique. Through this lens, we derive natural parallel variant, qNEHVI, that reduces computational complexity of parallel EHVI from exponential to polynomial with respect to the batch size. gNEHVI is one-step Bayes-optimal for hypervolume maximization in both noisy and noiseless environments, and we show that can be optimized effectively with gradeent-based methods via sample average approximation. Empirically, we demonstrate not only that NNHVVI substantially more robust to observation noise than existing MOBO approaches, but also that it achieves state-of-the-ie optimization performance and competitive mall-times in large-batcl batch environments.
corrupted by noise. We propose novel
1 Introduction
Black-box optimization problems that involve multiple competing noisy objectives are ubiquitous science and engineering. For example, real-time communications service may be interested in tuning the parameters of control policy to adapt video quality in real time in order to maximize video quality and minimize latency [10 [7]. In robotics, scientists may seck to design hardware
components that maximize locomotive speed and minimize energy expended [8] 38 In agriculture, development agencies may seek to balance crop yield and environmental impact
28 For such multi-objective optimization (MOO) problems, there typically is no single solution that is best with respect to all objectives. Rather, the goal is to identify the Pareto frontier: a set of optimal trade-offs such that improving one objective means deteriorating another. In many cases, the objectives expensive to evaluate. For instance, randomized trials used in agriculture and the internet industry may take weeks months conduct and incur opportunity costs, and manufacturing and testing hardware is both costly and time-consuming. Therefore, it is imperative to be able to identify good trade-offs with few objective evaluations as possible.
Bayesian optimization (BO), method for efficient global black-box optimization, often used to tackle such problems. BO employs probabilistic surrogate model in conjunction with acquisition function to navigate the trade-off between exploration (evaluating designs with high uncertainty) and exploitation (evaluating designs that are believed to be optimal). Although significant number of works have explored multi-objective Bayesian optimization (MOBO), most available methods
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

B 39 51, 60) do not take into account the fact that, in practice, observations are often subject to noise. For example, results of an A/B test are highly variable due to heterogeneity in the underlying user population and other factors. Agricultural trials are affected by the stochastic nature of plant growth and environmental factors such as soil composition or wind currents. In robotics, devices are subject to manufacturing tolerances, and observations of quantities such as locomotive speed and efficiency may be corrupted by measurement error from noisy sensors and environmental factors such as temperature
surface friction. While previous work has shown that a principled treatment of noisy observations can significantly improve optimization performance in the single-objective case 24 371, this issue is understudied in the multi multi-objective setting. Furthermore, many applications in which evaluations take a long time require evaluating large batches of candidates in parallel in order to achieve reasonable throughput. For example, when firms optimize systems via A/B tests, it may take several weeks to test any particular configuration. Because of this, large batches of candidate policies tested simultaneously [36)- In biochemistry and materials design, dozens of tests can be conducted parallel on a single microplate [63] Even in sophisticated high throughput chemistry
settings, these batches may take several hours days to set up and evaluate [42] Most existing
MOBO methods, however, are either designed for purely sequential optimization 3 5
or do not
scale well to large batch sizes
Contributions: In this work, we propose a novel MOBO algorithm, based on expected hypervolume improvement (EHVI), that scales to highly parallel evaluations of noisy objectives. Our approach is made possible by general- purpose, differentiable, cached box decomposition (CBD) implementation that dramatically speeds up critical computations needed to account for uncertainty introduced by noisy observations and generate new candidate points for highly parallel batch or asynchronous evaluation. In particular, our CBD-based approach solves the fundamental problem of scaling parallel EHVI-based methods to large batch sizes, reducing time and space complexity from exponential to polynomial. Our proposed algorithm, noisy expected hypervolume improvement (NEHVI), is the one- step Bayes-optimll policy for hypervolume improvement and provides state-of-the- performance across a variety of benchmarks. To our knowledge, our work provides the most extensive evaluation of noisy parallel MOBO to date. A high-quality implementation of NEHVI. as well as many of the baselines considered here, will be made available as open-source software upon publication.
2 Preliminaries
Our goal is to find the set of optimal designs æ over a bounded set X c Rd that maximize one or more objectives f(x) RM with no known analytical expression nor gradient information of f.
Multi-Objective Optimization (MOO) aims to identify the set of Pareto optimal objective trade- offs. We say a solution f(x) [x)) .... P(M) (x)) dominates another solution f(x) > f (xx) if ((m)(a)) 2 f((m) (æ') for m = I.... M and Fm E {1, .... M) s.t. ((m) (ax) >> (x") We define the Pareto frontier as P [x( x X. d E s.t. f(z')> > fx)).. and denote the set of Pareto optimal designs as X' {x f(z) E P'}. Since the Pareto fronticr (PF) is often an infinite set of points, MOO algorithms usually aim to identify finite approximate PF P. A natural measure of the quality of a PF is the hypervolume of the region of objective space that is dominated by the PF and bounded from below by reference point. Provided with the approximate PF, the decision-maker can select a particular Pareto optimal trade-off according to their preferences.
Bayesian Optimization (BO) is sample-efficient optimization method that leverages probabilistic surrogate model to make principled decisions to balance exploration and exploitation 19 50
Typically, the surrogate is Gaussian Process (GP), a flexible, parammerttticc model known for its well-calibrated predictive uncertainty [47]. To decide which points to evaluate next, BO employs an acquisition function a<-) that specifies the value of evaluating set of new points based on the surrogate's predictive distribution at . While evaluating the true black-box function f is time- consuming costly, evaluating the surrogate is cheap and relatively fast; therefore, numerical optimization can be used to find the maximizer of the acquisition function x = arg max, =xx (x(x) to evaluate next the black-box function. BO sequentially selects new points evaluate and updates the model to incorporate the new observations.
Evolutionary algorithms (EAs) such as NSGA-II 12 are popular choice for solving MOO problems (see Zitzler et al. (67 for a review of various other approaches). However, EAs generally suffer from high sample complexity, rendering them infeasible for optimizing expensive-to-evaluud black-box

---

functions. Multi-objectio Bayesian optimization (MOBO), which combines a Bayesian surrogate with an acquisition function designed for MOO, provides a much more sample-efficient alternative.
3 Related Work
Methods based on hypervolume improvement (HVT) seek to expand the volume of the objective space
dominated by the Pareto frontier. Expected hypervolume improvement (EHVI) [16] is natural
extension of the popular expected improvement (EI) [29] acquisition function to the MOO setting. Recent work has led to efficient computational paradigms using box decomposition algorithms [59]
and practical enhancements such as support for parallel candidate generation and gradient-basee acquisition optimization [1 (58). However, EHVI still suffers from some limitations, including (i)
the assumption that observations are noise-free, and (ii) the exponential scaling of its batch variant, gEHVI, in the batch size q. which precludes large-batch batch optimization. DGEMO [39] is recent method for parallel MOBO that greedily maximizes HVI while balancing the diversity of the design points being sampled. Although DGEMO scales well to large batch sizes, it does not account for noisy observations. TSEMO [5] is a Thompson sampling (TS) heuristic that can acquire batches of points by optimizing random fourier feature (RFF) (46) approximation of GP surrogate using NSGA-II and selecting a subset of points from the EA's population to sequentially greedily maximize HVI. This heuristic approach for maximizing HVI currently has theoretical guarantees and relies on zeroth-order optimization methods, which tend to be slower and exhibit worse optimization performance than gradient-based approaches.
Entropy-based methods such as PESMO [25], MESMO Bl, and PFES 51 are an alternative to EHVI. Of these three methods, PESMO is the only one that accounts for observation noise. However, PESMO involves intractable entropy computations and therefore relies on complex approximations, as well as challenging and time-consuming numerical optimization procedures (25). & Hernández-L generation. However, the authors of this work provide limited evaluation and have not provided code
[21] recently proposed an extension to PESMO that supports parallel candidate
to reproduce their results.'
MOO can also be cast into single-objective problem by applying random scalarization of the objectives. ParEGO maximizes the expected improvement using random augmented Chebyshev scalarizations (32. MOEA/D-EGO [64] extends ParEGO to the batch setting using multiple random scalarizations and the genetic algorithm MOEA/D 65 to optimize these scalarizations in parallel. Recently, gParEGO, another batch variant of ParEGO was proposed that uses compositional Monte Carlo objectives and sequential greedy candidate selection [T]]. Additionally, the authors proposed noisy variant, /NParEGO, but the empirical evaluation of that variant was limited. TS-TCH [45] combines random Chebyshev scalarizations with Thompson sampling [54], which is naturally robust to noise when the objective is scalarized. Golovin & Zhang [23] propose to
hypervolume scalarization with the property that the expected value of the scalarization over a specific distribution of weights equivalent the hypervolume indicator. The authors propose upper confidence bound algorithm using randomly sampled weights, but provide a very limited empirical evaluation.
Many prior attempts by the simulation community to handle MOO with noisy observations found that accounting for the noise did not improve optimization performance: Horn et al. (26) suggest that the best approach is to ignore noise, and Koch et al. [3 concluded that further research was needed to determine if modeling techniques such as re-interpolation could improve BO performance with noisy observations. In contrast, we find that accounting for noise does substantially improve performance in noisy settings.
Lastly, previous works have considered methods for quantifying and monitoring uncertainty in the Pareto frontiers during the optimization [4] 7.. In contrast, we provide a solution to performing MOBO in noisy settings, rather than purely reasoning about the uncertainty in the Pareto frontier.
4 Background on Expected Hypervolume Improvement
In this section, we review hypervolume, hypervolume improvement, and expected hypervolume improvement as well as efficient methods for computing these metrics using box decompositions.
We contacted the authors twice asking for code to reproduce their results, but they graciously declined.
3

---

Definition 1. The hypervolume indicator (HV) of finite approximate Pareto frontier P is the M M-dimensional Lebesgue measure AM of the space dominated by P and bounded from below by a reference point. E M HV(P)r) = AM (UepP? ml), where (r, v) denotes the hyper-rectangle bounded by vertices r and v.
As in previous work, we assume that the reference point r is known and specified by the decision maker [58].
Definition 2. The hypervolume improvement (HVI) of set points P' w.r.t. an existing approximate -
Pareto frontier P and reference point v is defined as
- HV(P)
Computing HV requires calculating the volume of a typically non-rectangular polytope and is known to have time complexity that is super-polynomial in the number of objectives [59]. An efficient approach for computing HV is to (i) decompose the region that is dominated by the Pareto frontier P and bounded from below by the reference point r into disjoint axis-aligned hyperrectangles [34. (ii) compute the volume of each hyperrectangle the decomposition, and (iii) sum over all hyperrectangles. So-called box decomposition algorithms have also been applied to partition the region that is not dominated by the Pareto frontier P, which can be used to compute the HVI from a set of new points [ 59
See Appendix
B for further details.
Expected Hypervolume Improvement: Since function values at unobserved points are unknown in black-box optimization, so is the HVI of an out-of-sample point. However, in BO the probabilistic surrogate model provides a posterior distribution p(f(2)) over the function values for each æ, which can be used to compute the expected hypervolume improvement (EHVI) acquisition function: OgnVI (P) TE [ PP] Although dENVI can be expressed analytically when (i) the objectives are assumed to be conditionally independent given a and (ii) the candidates are generated and evaluated sequentially [58], Monte Carlo (MC) integration is commonly used since it does not require either assumption 16.. The more general parallel variant using MC integration is given by
N
AgEnvi (P) = (yR (Neand (P) =
1 N
Σ
(Xmma)))))))))
(1)
where ft ~ (D) for 1 = 1, ...., N and Xaand
The same box decomposition algorithms used to compute HVI can be used to compute EHVT (either analytic or via MC) using piece-wise integration. EHVI computation is agnostic to the choice of box decomposition algorithm (and can also use approximate methods (. Similar to El in the single-objective case, EHVI is one-step Bayes-optimal algorithm for maximizing hypervolume in the MOO setting under the following assumptions: (i) only a single design will be generated and evaluated, (ii) the observations are noise-free, (iii) the final approximate Pareto frontier (and final design that will be deployed) will be drawn from the set of observed points 19.
5 Expected Hypervolume Improvement with Noisy Observations
We consider the case that frequently arises in practice where we only receive noisy observations y, = =f(x) + E,, e, ~ NNO, E.), where E, is the noise covariance. In this setting, EHVI is no longer (one-step) Bayes-optimal. This is because we can no longer compute the true Pareto frontier Pn, = (fx)) x E X,, 3 E X, s.t. f(x) > fx)) over the previously evaluated points X,, = [..]__ Simply using the observed Pareto frontier, ),m = { E Yn, Fy' E Y, s.t. y > y. y} can have strong detrimental effects on optimization performance. This is illustrated in Figure 1 which shows how EHVI is misled by noisy observations that appear to be Pareto optimal. EHVI proceeds to spend its evaluation budget trying to optimize noise, resulting in a clumped Pareto frontier that lacks diversity. Although the posterior mean could serve as a "plug-in" estimate of the true function values at the observed points and provide some regularization [61], we find that this heuristic also leads clustered Pareto frontiers (EHVI-PM) in Fig. I.. Similar patterns emerge with DGEMO (which does not account for noise), and other basclines that utilize the posterior mean rather than the observed values when computing hypervolume improvement (see Appendix HH) To our knowledge, all previous work on EHVI assumes that observations are noiseless [16 58 or imputes the unknown true function values with the posterior mean.
where Yn = {y:) 1.
For brevity omit the reference point when referring to HVI

---

Figure An illustration of the effect of noisy observations on the true noiseless Pareto frontiers identified by NEHVI (our pro- posed algorithm), EHVI, and EHVI-PM, which uses the modeled posterior mean point estimate of the true in-sample function values. All algorithms are tested on BraninCurrin synthetic prob- lem, where observations are corrupted with zero-mean, additive Gaussian noise with a standard deviation of 5% of the range of respective objective. All methods use sequential (q 1) optimiza- tion. See Appendix for details.
-3-
-4-
BHVT
-5-
EHVI-PM
Ref. Point
True PC
-10
Ubjectva
5.1 A Bayes-optimal algorithm for hypervolume maximization in noisy environments
In contrast with EHVI(-PM), we instead approach the problem of hypervolume maximization under noisy observations from a Bayesian perspective and derive a novel stepstep Bayes-optimal expected hypervolume improvement criterion that iterates the expectation over the posterior distribution (((( [Dn) of the function values at the previously evaluated points X,, given noisy observa- tions D, = (æ;; Vi, Vi, (E,) Our acquisition function, noisy expected hypervolume improvement (NEHVI), is defined
ONEIII = ff [
where Pa denotes the Pareto frontier over f(X.).
By integrating over the uncertainty in the function values at the observed points, NEHVI retains one-step Bayes-optimality noisy environments (in noiseless environments, NEHVI equivalent to EHVI). Empirically, Figure shows that NEHVI is robust to noise and identifies well-distributed Pareto frontier with no signs of clumping, even under very noisy observations."
The integral in (2) is analytically intractable, but can easily be approximated using MC integration. Let ft ~ Dn) for 1 I,...N be samples from the posterior, and let P, (fx(z) æ E Xn, fxx)) > fa(x') V xx,) be the Pareto frontier over the previously evaluated points under the sampled function fc. Then, (NFHvI(a:) & N Ei= OrEvvI(*: P.:). Using MC integration, can compute the inner expectation in оEHVI simultaneously using samples from the joint posterior xx) ~ p(f(X,, ()(,,,) over æ and X,:
âNEHVI (x)
Σ HvI(f(
(3)
See Appendix for details on computing variant of NEHVI does not require objectives be modeled independently, and supports multi-task covariance functions across correlated objectives.
3 using box decompositions. Note that this "full-MC"
5.2 Parallel Noisy Expected Hypervolume Improvement
Generating and evaluating batches candidates is imperative to achieving adequate throughput in many real-world scenarios. qNEHVI naturally be extended the parallel (asynchronous or batch) setting by evaluating HVI with respect to a batch of q points Xeand = {x;} [
1 N
(XNNE)v((Kccm)) =f (OEENII P.) SANENIII(Kennl
(4)
Since optimizing q candidates jointly difficult numerical optimization problem over gd- dimensional domain, we use sequential greedy approximation in the parallel setting and solve sequence of q simpler optimization problems with d dimensions, which been shown empirically to improve optimization performance [57]. While selecting candidates according to a "sequential
greedy" policy does not guarantee that the selected batch of candidates is maximizer of the NGEVI, the submodularity of (GGNEHVI allows us to bound the regret of this approximation to be no more than
NNEHII where OF NEHVI = max CegNEnvI (Xaana) (see Appendix
"This noise level is 5x greater than the considered by previous works that evaluate noisy MOBO 25
5

---

Efficient Evaluation with Cached Box Decompositions
Although (a) in has concise mathematical form, computing it requires determining the Pareto frontier Pe under each sample ft for 1 1, .... NN and then partitioning the region that is not dominated by Pe into disjoint hyperrectangles {Sx, } Optimizing the unbiased MC estimator of ΦNEHYI would require re- re-samlingg { at each evaluation of aNEHVI. However, computing the Pareto frontier and performing a box decomposition under each of the N samples during every evaluation of ONEHRI in the inner optimization loop (x* arg max² ONNERVI (arl (D,)) would be prohibitively expensive. This is because box decomposition algorithms have super-polynone time complexity in the number of objectives [59]. We instead propose efficient alternative computational technique for repeated evaluations of EHVI with uncertain Pareto frontiers.
Cached Box Decompositions: For repeated evaluations of the integral in we use set of fixed which allows us to compute the Pareto frontiers and box decompositions once, and cache them for the entirety of the acquisition function optimization, thereby making those two computationally intensive operations a one-time cost per BO iteration.* 4 We refer to this approach as using cacked box decompositions (CBD). The method of optimizing over fixed random samples is known as sample average approximation (SAA) [2].
samples
Conditional Posterior Sampling: Under the CBD formulation, computing (NE)VI( with joint samples from fc(Xn. x) ~ p(f(X,: a) PP,) requires sampling from the conditional distributions
f((z) ~ (f())) = D,),),
(5)
where /. = 1,.,, and (f.() are the realized samples at the previously evaluated points. For multivariate Gaussian posteriors (as is the case with GP surrogates), we can sample from p(f((,) via the reparameterization trick (30] by evaluating fa( = pnn + LA Sn.t. where Sn,t ~ (N, J.M), f4n E RRMM is the posterior mean, and I. E xgn is a lower triangular root decomposition of the posterior covariance matrix, typically Cholesky decomposition. Given T,n can obtain a root decomposition L', of the covariance matrix of the joint posterior p(f(Xnn x) (Da) by performing efficient low-rank updates [44). Given L/2 and the posterior mean of (X x) (Dn). we can sample from (5) via the reparameterization trick by augmenting the existing base samples Sn.t with M new base samples for the new point.
6.1 Efficient Sequential Greedy Batch Selection using CBD
The CBD technique addresses the general problem of inefficient repeated evaluations of EHVI with uncertain Pareto frontiers. In this section, we show that sequential greedy batch selection (with both qEHVI and gNEHVI) is an incarnation of EHVI with uncertain Pareto frontiers.
The original formulation of parallel EHVI in Daulton et al. [ uses the inclusion-exclusion principle (IEP), which involves computing the volume jointly dominated by each of the 24 nonempty subsets of points in Xaand- However, using large batch sizes is not computationally feasible under this formulation because time and space complexity are exponential in q and multiplicative in the number of hyperrectangles in the box decomposition [II] (see AppendixD] Although qEHVI is optimized using sequential greedy batch selection, the IEP is used over all candidates 2 .... 24 when selecting candidate i. Although the IEP could similarly be used to compute NE we instead leverage CBD, which yields sequential greedy approximation of the joint (noisy) EHVI I that is mathematically equivalent to the IEP formulation, but significantly reduces computational overhead. That is, the IEP and CBD approaches produce exactly the same acquisition value for a given set of points Xaand, but the IEP and the CBD approaches have exponential and polynomial time complexities in q, respectively.
feassibbllle
complexity analysis).
When selecting x; for i E (,....: g), all x, for which j < i have already been selected and are therefore held constant. Thus, we can decompose NNEHVI into the gNEHVI from the previously selected candidates T I;-1 and NEHVI from x; given the previously selected candidates
For greater efficiency, we may also prune X., to remove points that are dominated with high probability, which we estimate via MC.

---

Acgestton Optrotration (O)
Figure 2: Acquisition optimization wall time under a sequential greedy approximation using L-BFGS-B. CBD enables scaling much larger batch sizes than using the IEP and avoids running out-of-memory (OOM)
CBD (CPC)
300
CBD (GPU)
(CPU)
200
IEP (GPU)
GPU. Independent GPs are used for each outcome. The Pareto frontier of of the 2-objective, 6- dimensional DTLZ2 problem
00M
100
[K] is initialized with 20 points. Wall times were measured on a Tesla V100 SXM2 GPU (16GB RAM) and a 2x Intel Xeon 6138 CPU 2GHz (251GB RAM). See Appendix H.2 for results with more objectives.
0
40
80
100
N Σ (V((((())))
HVI(( (1; N Σ
Note that the first term on the right hand side is constant, since {a;))=1 and (f((z))) are fixed for all = I,... N. The second term is (x;), where the NEHVI is taken with respect to the Pareto frontier across f(,, 3I #I,.,,, 2;-1) and computed using the fixed samples (ff( +;....
To compute the second term when selecting candidate æ,, the N Pareto frontiers and CBDs are updated to include (fr(X,, -1) As in the sequential setting, the box decompositions are only computed and cached while selecting each candidate point. See Appendix C.2 for a derivation of (6). Although we have focused on gNEHVI in the above, the CBD formulation for qEHVI obtained by simply replacing Pe with the Pareto frontier over the observed values Vn.
1
Despite computing N box decompositions when selecting each candidate æ; for i 2, .... q. the CBD approach reduces the time and space complexity from exponential (under the IEP) to polynomial in (see Appendix [D] for details time and space complexity). FigureZ]showe the total acquisition optimization time (including box decompositions) for various batch sizes and demonstrates that using CBD allows to scale to batch sizes that are completely infeasible when using IEP.
Optimizing NEHVI
Importantly, (N) is differentiable w.r.t. x. Although determining the Pareto frontier and computing the box decompositions are non- non-differentiable operations, these operations do not involve æ, even when re-sampling from the joint posterior pff( D,)) Exact sample-pe path gradients of Vœ can easily be computed using aito-differentiation in modern computational frameworks. This enables efficient gradient-based optimization of o NEHVI.
Differentiability:
SAA Convergence Results: In addition to approximating the outer expectation over fX,,,, with fixed posterior samples, we can similarly fix the base samples used for the new candidate point æ. This approach yields a deterministic acquisition function, which enables using (quasi-) higher-order optimization methods to obtain fast convergence rates for acquisition optimization (2). Importantly, we prove that the theoretical convergence guarantees on acquisition optimization under the SAA approach proposed by Balandat et al. (2) also hold for NEHVI.
Theorem 1. Suppose X is compact and I has multi-outpul GP prior with continuously differen- tiable mean and covariance functions. Let X,, = (x denote the previously evaluated points and [ be base samples Ç ~ ((+1)M) Let ÓNEEVI denote the deterministic acquisi- tion function computed using { as á and define S = arg max (NE)vI((z) to be the set of maximizers of (N)) over X. Suppose ty E arg max xE (NEEII Then (1) N aNsuvi(ē - (NEEvI((")) almost surely, and (2) dist(Tiy, S*) ) + 0, where dist S*)
N
inf ||00 - æe|| the Euclidean distance between 4yy and the set S*.
Theorem T also holds in the parallel setting, @NEHVI enjoys the same convergence guarantees as NEHVI on acquisition optimization under the SAA. See Appendix(E]oor further details and proof.
"One can also show that the gradient of the full MC estimator âÆNERVI is an unbiased estimator of the gradient of the true joint noisy expected hypervolume improvement agNEHvI. However, this result is not necessary for our SAA approach.
7

---

8 Approximation of GNEHVI using Approximate GP Sample Paths
Although CBD yields polynomial complexity of gNEHVI with respect to q (rather than exponential complexity with the IEP), it still requires computing N box decompositions and repeatedly evaluating the joint posterior over f(X,, { { );=1) for selecting each candidate æ; for i = 1,... q. A cheaper alternative is to approximate the integral in 44) using single approximate GP sample path f. using RFFs when optimizing candidate 2;. A single-sample approximation of qNEHVI, which we refer to as gNEHVI-I, can be computed by using fü as the sampled GP in (6). Since the RFF is a deterministic model, it much less computationally expensive evaluate than the GP posterior on out-of-sample points, and exact gradients of gNEHVI-1 I with respect to current candidate I; can be computed and used for efficient multi-star start optimization of o gNEHVI- 1 using second-order gradient methods. gNEHVI-1 requires CBD for efficient sequential greedy batch selection and gradient-basse based optimization, but does not use a sample average approximation for optimizing a new candidate æ;; instead, it uses an approximate sample path. See Rahimi & Recht [46 for details on RFFs.
NEHVI-1 is related to TSEMO in that both use sequential greedy batch selection using HVI based on RFF samples. However, TSEMO does not directly maximize HVI when selecting candidate It, where i 1, ..., q; rather, relies on a heuristic approach of running NSGA-II on an RFF sample of each objective to create a discrete population of candidates and then selecting the point from the discrete population that maximizes HVI under the RFF sample. In contrast, NNEHVI-1 directly optimizes HII under the RFF using exact sample-path gradients, which leads to improved optimiza- tion performance (see Appendix HD. Furthermore, we find that gNEHVI-1 is significantly faster than TSEMO, because rather than using NSGA-II it uses second order gradient methods to optimize HVT (see Appendix HH. Gradient-based optimization only possible because CBD enables scalable, differentiable HV computation. While the primary goal of this work is to develop a principled, scalable method for parallel EHVT noisy environments, we include empirical comparisons with (NEHVI-1 1 throughout the appendix to demonstrate the generalizablility of the CBD approach and practical performance of the NEHVI-1 approximation. gNEHVI-1 achieves the fastest batch selection timesof any method tested on GPU on every problem; in many cases, this is an order of magnitude speed-up over NEHVI. Moreover, NEHVII- has a remarkable ability to scale to large batch sizes when the dimensionality of optimization problem is modest. Further investigation of gNEHVI-1 1 is needed, but we hope that the readers can recognize the ways in which qNEHVI can create broader opportunities for research into hypervolume improvement based acquisition functions.
9 Experiments
We empirically evaluate NE on a set of synthetic and real-world benchmark problems. We compare it against the following recently proposed methods from the literature: PESMO, MESMO (which we extend to the handle noisy observations using the noisy information gain from Takeno et al. (2), PFES, DGEMO, MOEA/D-EGO, TSEMO, TS-TCH, şEHVI (and qEHVI-PM-CBI which uses the posterior mean as a plug-in estimate for the function values at the in-sample points, along with CBD scale to large batch sizes), and PNrarGG. We optimize all methods using multi-start L-BFGS-B with exact gradients (except for PFES, which uses gradients approximated via finite differences), including TS- TCH where we optimize approximate function samples using RFFs with 500 basis functions. We model each outcome with an independent GP with a Matérn 5/2 ARD kernel and infer the GP hyperparameters via maximum posteriori (MAP) estimation. For all problems, we assume that the noise variances are observed (except ABR, where we infer the noise level). See Appendix G for more details on the experiments and acquisition function implementations.
We evaluate all methods using the logarithm of the difference in hypervolume between the true Pareto frontier and the approximate Pareto frontier recovered by the algorithm. Since evaluations are noisy. we compute the hypervolume dominated by the noiseless Pareto frontier across the observed points for each method.
Synthetic Problems:
We consider a noisy variants of the BraninCurrin problem (M = 2, = 2) and the DTLZ2 problem (M = 2, d 6) [13,, in which observations are corrupted with zero-mean additive Gaussian noise with standard deviation of 5% of the range of each objective for BraninCurrin and 10% for D71.72.
Adaptive Bitrate (ABR) Control Policy Optimization: ABR controllers are used for real-time communication and media streaming applications. Policies for these controllers must be tuned to
8

---

DenuinCurto
DTL22
ABB
VeludeSdityy
1.75
tegth Netrenec
1.05
0.50
0.00
3.28
4.02
4.70
0.30
6:7-
6.80
5.00
000
60x-
-1.00
500
0.30
-1.10
-1.00
723
Draluations
Dralcations
Punebion Evaluations
Evalcations
DEEMO MPSWO
MOEAID-EGG
PFES
TSEMO
(ERV-PM--CDD
@NERVL-
PRSMO
T3-TCH
gFFV1
@NEIVI
@NPwRGO
Figure 3: Sequential optimization performance. The shaded region indicates two standard errors of the mean over 100 replications (only 20 replications were feasible for PESMO due large runtimes).
deliver high quality experience with respect to multiple objectives [40]. industry settings, A/B tests with dozens of policies are tested simultaneously since each policy may take days or weeks to evaluate, producing noisy mcasurements across multiple objectives. In this experiment, we tune policies to maximize video quality (bitrate) and minimize stall time. The policy has d = 4 parameters, which are detailed in Appendix G We use the Park simulator [41] and sample a random set of 100 traces obtain noisy measurements of the objectives under given policy. For comparing the performance of different methods, we estimate the true noiseless objective using mean objectives across 300 traces. We infer homoskedastic noise level jointly with the GP hyperparameters via MAP estimation.
Vehicle Design Optimization: Optimizing the design of the frame an automobile is important to maximizing passenger safety, vehicle durability and fuel efficiency. Evaluating a vehicle design is time-consuming, since either vehicle must manufactured and crashed, or nonlinear finite element-based crash analysis must be run to simulate a collision (which can take over 20 hours per run) [62]. Hence, evaluating many designs in parallel is critical for reducing end-to-end optimization time. Observations are often noisy due to manufacturing imperfections, measurement error, or non-deterministic simulations. In this experiment, of a vehicle's s frame to minimize proxy metrics for (1) fuel consumption, (2) passenger trauma in a full frontal collison, and (3) vehicle fragility [53]. See Appendix G for details. For this demonstration, we add zero-mean Gaussian noise with a standard deviation of 1% of the objective range, which roughly corresponds to the manufacturing noise level used in previous work (62
tune the d = 5 widths of various components
9.1 Summary of Results:
We find that gNEHVI and gNEHVI-] outperform all other methods on the noisy benchmarks, both in the sequential and parallel setting. the sequential setting (Fig Bh ęNEHVI and gNEHVI-1 are followed closely by VEHVI-PM, and in some cases, even gEHVI TS-TCH is firmly in the middle of the pack, while iiformmationthhoreeti acquisition functions appear to perform the worst. This is consistent across noise levels; for experiments where we add noise to the objectives, we consider noise levels ranging from 1% to 10% of the range of each objective (these are magnitudes of the noise often seen in practice). Previous works have only evaluated MOBO algorithms with noise levels of 1 1% (25). In Appendix H we perform a study showing that NNHHVI consistently performs best with increasing noise levels up to 30% of the range of each objective.
While parallel evaluation can provide optimization speedups on order of the batch size g. these evaluations do affect the overall sample complexity of the algorithm, since less information is available within the synchronous batch setting compared with fully sequential optimization. We find that, by and large, ęNEHVI achieves the greatest typer-volums. for increasingly large batch sizes, and scales more elegantly relative to TS-TCH and the ParEGO variants (Fig 4.. @NEHVI also consistently outperforms gEHVI-PM-CBI NEHVI-I provides excellent anytime performance all values of q that we tested. We provide results on 4 additional test problems in Appendix H.. and in Appendix H.8) we demonstrate that leveraging CBD and single sample path approximation, NNEVVI-1 enables scaling to 5-objective problems, which is first for an HVI baaed method, to knowledge.
In Appendix H we observe that @NEHVI and

---

DomitaCurti
ABR
VelxleSadoy
1.22
1.25
-055
055
2.23
1.00
633
0.82
8.33
155
+3.3
4.72
-100
4.5
DG2MO
TS1
QEIVVE QERVLPXCCCD
GNELIVI
@NPar200
Figure 4: The quality of the final Pareto frontier identified by each method with increasing batch sizes given a budget of 224 function evaluations. gEHVI is only included for q 1 and 8 because the IEP scales exponential with q. DGEMO is omitted on the ABR problem because was prohibitívely slow with time-consuming ABR simulations and on the VehicleSafety problem because DGEMO consistently crashed in the graph cutting algorithm.
In our experiments, we find that QNEHVI-1 is among the top performers on relatively low- dimensional problems. Given the strong performance of qNEHVI-I, we examine its performance as the dimensionality of the search space increases Appendix H..5 We find that qNEHVI more robust than gNEHVI-I in into how the number of the Fourier basis functions affects the performance of gNEHVI-1 in high- dimensional search spaces.
search spaces, but further investigation is needed
Optimization wall time: Across all experiments, we observe competitive wall times for optimizing (NEHVI and yNEHVI-1 (all wall time comparisons are provided in Appendix HH. On a GPU, optimizing GNEHVI-1 incurs the lowest wall time of any method that we tested on every single problem and optimizing şNEHVI is faster than optimizing information-theoretii methods on all problems. Using efficient low-rank Cholesky updates, NNEVVI is often faster than the gNParEGO implementation in BoTorch on GPU.
10 Discussion
We proposed NEHVI, a novel acquisition function that provides a principled approach to parallel and noisy multi-objective Bayesian optimization. NEHVI is one-step Bayes-optimal policy for maximizing the hypervolume dominated by the Pareto frontier in noisy and noise- free settings. NEHVI is made feasible by new approach computing joint hypervolumes (CBD), and demonstrated that CBD enables scalable, parallel candidate generation with both noiseless gEHVI and N We provide theoretical results optimizing MC estimator of NEHHV using sample average approximation and demonstrate significant improvements in optimization performance over state-of-the-at MOBO algorithms.
Yet, our work has some limitations. While the information -thhorrttn-tt acquisition functions tested here perform poorly
benchmarks, they do allow for decoupled evaluations of different objectives in cases where querying one objective may be more resource-intenae Optimizing such acquisition functions is a non-trivial task, and it is possible that with improved procedures, such acquisition functions could yield improved performance and provide principled approach to selecting evaluation sources Bayesian optimization tasks, exact hypervolume computation has super-polynomial complexity the number of objectives. Combining gNEHVI I with differentiable approximate methods for computing hypervolume (e.g. Couckuyt et al. [9] Golovin & Zhang (23) could lead to further speed-ups.
than querying other objectives.
budget. Although practically fast enough for most
We hope that the core ideas presented in this work, including the CBD approach, can provide framework to support the development new computationally efficient MOBO methods.
10

---

References
[1] Asadpour, A., Nazerzadeh, H., and Saberi, A. Stochastic submodular maximization. In Papadimitriou, C. and Zhang, S. (eds.), Internet and Network Economics. Springer Berlin Heidelberg, 2008.
[2] Balandat, M., Karrer, B., Jiang, D. R., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A Framework for Efficient Monte-Carle Carlo Bayesian Optimization. Advances in Neural Information Processing Systems 33, 2020.
[3] Belakaria, S., Deshwal, A., and Doppa, J. R. Max-value entropy search for multi-objective
bayesian optimization. In Advances Neural Information Processing Systems 32, 2019.
[4] Binois, M., Ginsbourger, D., and Roustant, O. Quantifying uncertainty on pareto fronts with gaussian process conditional simulations. Eur. J. Oper. Res., 243:386-394, 2015.
[5] Bradford, E., Schweidtmann, A. M.. and Lapkin, A. Efficient multiobjective optimization employing gaussian processes, spectral sampling and a genetic algorithm. Journal of global optimization, 71 71(2):407-438 2018.
[6] Brockhoff, D., Tusar, T., Auger, A., and Hansen, N. Using well-understood single-objective functions in multiobjective black-box optimization test suites, 2019.
[7] Calandra, R. and Peters, J. Pareto front modeling for sensitivity analysis in multi-objective bayesian optimization. 2014.
[8] Calandra, R., Seyfarth, A., Peters, J., and Deisenroth, M. Bayesian optimization for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76(1):5-23 Feb 2016. ISSN 1573-7470. doi: 10. 10.10077/11472--15--220
[9] Couckuyt, I., Deschrijver, D., and Dhaene, Towards efficient multiobjective optimization: Multiobjective statistical criterions. In 2012 IEEE Congress on Evolutionury Computation, pp.
1-8, 2012.
[10] Daulton, S., Singh, S., Avadhanula, V., Dimmery, D., and Bakshy, E. Thompson sampling for contextual bandit problems with auxiliary safety constraints. In NeurlPS Workshop on Safety and Robustness Decision Making, 2019.
[11] Daulton, S., Balandat, M., and Bakshy, E. Differentiable expected hypervolume improvement for parallel multi-objective Bayesian optimization. In Advances Neural Information Processing Systems 33, NeurlPS, 2020.
[12] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2):122-197, 2002.
[13] Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. Scalable multi-objective optimization test problems. volume I, pp. 825 830, 06 2002. ISBN 0-7803-7282-4, doi: 10. 109/
TEC.2002.100703
[14] Deb, K., Gupta, S., Daum, D.,, Branke, J., Mall, A. K., and Padmanabhan, D. Reliability- optimization using evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 13(5):1054-1074, 2009. doi: 10. 21L.0//TE..2209.201444..
[15] Dächert, K., Klamroth, K., Lacour, R., and Vanderpooten, D. Efficient computation of the search region in multi-objective optimization. European Journal of Operational Research, 260 (3):841 855, 2017.
[16] Emmerich, M. M., Giannakoglou, K. C., and Naujoks, B. Single- and multiobjective evolutionary optimization assisted by gaussian random field metamodels. IEEE Transactions on Evolutionary Computation, 10(4):421-453 2006.
[17] Feng, Q., Letham, B., Bakshy, E., and Mao, H. High-Dimensional Contextual Policy Search with Unknown Context Rewards using Bayesian Optimization. Advances in Neural Information Processing Systems 33, 2020.
[18] Fisher, M. L., Nemhauser, G. L., and Wolsey, L. A. An analysis of approximations for maximizing submodular set functions- II, pp. 73-87. Springer Berlin Heidelberg, Berlin, Heidelberg, 1978.
[19] Frazier, P. I. A tutorial on bayesian optimization. arXiv preprint arXiv: 0807.08807.0281111 2018.

---

[20]
Garrido-Merchán, E. C. and Hermáneez-Lobato, D. Predictive entropy search for multi-objective bayesian optimization with constraints. Neurocompuriing. 361:50-68. 68, 2019.
[21]
E. C. and Herándezz-obbto, D. Parallel predictive entropy search for multi-objective bayesian optimization with constraints, 2020.
[22] Gelbart, M. A., Snoek, J., and Adams, R. P. Bayesian optimization with unknown constraints. In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, UAI, 2014.
[23] Golovin, D. and Zhang, Q. Random hypervolume scalarizations for provable multi-objective black box optimization, 2020.
[24] Hernández-Lobuld J. M., Hoffman, M. W., and Ghahramani, Z. Predictive entropy search for efficient global optimization of black-box functions. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1, NIPS 14, pp. 918-926, Cambridge, MA, USA, 2014. MIT Press.
[25] Hemánneez-Lobato, D., Hemándezz J. M., Shah, A., and Adams, R. P. Predictive entropy search for multi-objective bayesian optimization, 2015.
[26] Horn, D., Dagge, M., Sun, X., and Bischl, B. First investigations on noisy model-based multi- objective optimization. volume 10173, pp. 298-313, 02 2017. ISBN 978-3-319-54156-3 doi: 11.1007/978-33199554
[27] Igel, C., Hansen, N., and Roth, S. Covariance matrix adaptation for multi-objeccive optimization. Evolutionary Computation, 15(1):1-28, 2007. doi: 10. 10.1162/evco.207 20.7.15.1.11
[28] Jiang, S., Zhang, H., Cong, W., Liang, Z., Ren, Q., Wang, C., Zhang, F., and Jiao, X. Multi- objective optimization of smallholder apple production: Lessons from the bohai bay region. Sustainability. 12(16):6496, 2020.
[29] Jones, D. R., Schonlau, M., and Welch, W. J. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13:455-492, 1998.
[30] Kingma, D. P. and Welling, M. Auto-Encoding Variational Bayes. arXiv e-prints, pp. arXiv:1312.6114, Dec 2013.
[31] Klamroth, K., Lacour, R., and Vanderpooten, D. On the representation of the search region multi-objective optimization. European Journal of Operational Research, 277777 Sep 2015. ISSN 0377-2217. doi: 0011166...oo1221550..00.... URL http://dx.doi.orrg
N0.1016/j.ejor.2011 2015.03..1111011110
[32] Knowles, Parego: hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, 10(1): 50-66. 2006.
[33] Koch, P., Wagner, T., Emmerich, M. T., Back, T., and Konen, W. Efficient multi-criteria optimization on noisy machine learning problems. Appl. Soft Comput., (9 April 2015. ISSN 1568-4946. doi: 10. a0t.://..cc..21......1
URL httttts://ai...r/111...00
[34] Lacour, R., Klamroth, K., and Fonseca, C. M. A box decomposition algorithm to compute the hypervolume indicator. Computers Operations Research, 79:347 - 3600, 2017.
[35] LeCun, Y., Cortes, C., and Burges, C. Mnist handwritten digit database. ATT Labs [Online]. Available: http://aam..eccn.coom/e////t
2, 2010.
[36] Letham, B. and Bakshy, E. Bayesian optimization for policy search via online-offlinn ex- perimentation. Journal of Machine Learning Research, 20(145):1-30, 2019. URL http
wttthttr/pppppp//eeggm wvttss//200/13 18- 225.2222tt
[37] Letham, B., Karrer, B., Outoni, G., and Bakshy, E. Constrained bayesian optimization with noisy experiments. Bayesian Analysis, 14(2):495-519 06 2019, doi: 10. ----111100.
[38] Liao, T., Wang, G., Yang. B., Lee, R., Pister, K., Levine, S., and Calandra, R. Data-efficient learning of morphology and controller for a microrobot. In 2019 International Conference on Roboties and Automation (ICRA), pp. 2488 2188-4494. IEEE, 2019.
[39] Lukovie, K. M., Tian, Y., and Matusik, W. Diversity-guided multi-objective bayesian opti- mization with batch evaluations. Advances Neural Information Processing Systems, 33, 2020.
12

---

[40] Mao, H., Chen, S., Dimmery, D., Singh, S., Blaisdell, D., Tian, Y., Alizadeh, M., and Bakshy, E. Real-world video adaptation with reinforcement learning. 2019.
[41] Mao, H., Negi, P., Narayan, A., Wang. H., Yang. J., Wang, H., Marcus, R., Addanki, R., Shirkoohi, M. K., He, S., Nathan, V., Cangialosi, E,, Venkatakrishhan, S. B., Weng, W.-H., Han, S.-W., Kraska, T., and Alizadeh, M. Park: An open platform for learning-augmente computer systems. In NeurIPS, 2019.
[42] Mennen, S. M., Alhambra, C.,, Allen, C., Barberis, M., Berritt, S., Brandt, T. A., Campbell, A. D., Castañón, J., Cherney, A. H., Christensen, M., Damon, D. B., Eugenio de Diego, J., García-Cerrada, S., García-Losada, P., Haro, R., Janey, J., Leitch, D. C.,, Li, L.., Liu, F,, Lobben, P. C., MacMillan, D. W. C., Magano, J., McInturff, E., Monfette, S., Post, R. J., Schultz, D., Sitter, B. J., Stevens, J. M., Strambeanu, I. I., Twilton, J., Wang, K., and Zajac, M. A. The evolution of high- high-throughput experimentation in pharmaceutical development and perspectives on the future. Organic Process Research & Development, 23(6): 1213):2213-222, 2019. doi: http:/ac..........o
[43] Namkoong, H., Daulton, S., and Bakshy, E. Distilled thompson sampling: Practical and efficient thompson sampling via imitation learning. In NeurlPS Offline Reinforcement Learning Workshop, 2020.
[44] Osborne, M. A. Bayesian gaussian processes for sequential prediction, optimisation and quadrature. 2010.
[45] Paria, B., Kandasamy, K., and Póczos, B. A Flexible Multi-Objective Bayesian Optimization Approach using Random Scalarizations. ArXiv e-prints, May 2018.
[46] Rahimi, A. and Recht, B. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, N1PS'07, pp. 1177-1184, Red Hook, NY, USA, 2007. Curran Associates Inc. ISBN 9781605603520.
[47] Rasmussen, C. E. Gaussian Processes in Machine Learning, pp. 63-71. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
[48] Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regularized evolution for image classifier architecture search. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01): 4780-4789, Jul. 2019. doi: 10.1609/aaai 033014..3004780. URL httph:://ojs..aaa..oo index.php/ AAw.:////AA/Aaaa
4405
[49] Schuster, M. Speech recognition for mobile devices at google. In Zhang, B.-T. and Orgun,
M. A. (eds.), PRICAI 2010: Trends in Artificial Intelligence, pp. 8-10, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. ISBN 10--3-642-15246--1
[50] Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and de Freitas, N. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE,
2016. [51] Suzuki, S., Takeno, S., Tamura, T., Shitara, K., and Karasuyama, M. Multi-objective Bayesian optimization using pareto-frontics entropy. In III, H. D. and Singh, A. (eds.), Pro- ceedings of the 37th International Conference on Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pp. 9279-9288. PMLR, 13-18 Jul 2020. URL http: htttp://proceeddngss htw.oceeddnn.......eess////1999 ptt.ss/11///////// htw1///uukki222 wttp:/suuuiiiaa......mo
[52] Takeno, S., Fukuoka, H., Tsukada, Y., Koyama, T., Shiga, M., Takeuchi, I., and Karasuyama, M. Multi-fidelity Bayesian optimization with max-value entropy search and its parallelization. In III. H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pp. 9334-9345. PMLR. 13-18 Jul 2020. URL httt:://proceeeinggge mlr www.:emww........eeeeeeeemmeeeee
[53] Tanabe, R. and Ishibuchi, H. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 89: 89:1 106078, 2020. ISSN 1568-4946. doi: htnp:://doi.og//i1 1016/ j.asoc.2020. 222000.10000 106078.
[54] Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4) 1933.
[55] Touré, C., Hansen, N., Auger, A., and Brockhoff, D. Uncrowded hypervolume improvement: Como-cma-es and the sofomore framework. Proceedings of the Genetic and Evolutionary
Computation Conference, GECCO '1,, pp. 638-646, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361 118. doi: 10.1145/3321107..322 7772177777 URL.
https: /tt:://doooioe wwt.i/orr/111111111.. /tte//1.111///11777771122222
13

---

[56] Wang, R., Xiong, J., Ishibuchi, H., Wu, G., and Zhang, T. On the effect of reference point in moea/d for multi-objective optimizationn. Applied Soft Computing. 58:25-34 -34, 2017. ISSN 1568-4946. doi:
201.70000..000220.0.000.00..... URL https www.://ccccciccccc.occ.ceeeeeeea
[57] Wilson, J., Hutter, F., and Deisenroth, M. Maximizing acquisition functions for bayesian optimization. In Advances in Neural Information Processing Systems 31, pp. 9905-9916. 2018.
[58] Yang, K., Emmerich, M., Deutz, A., and Bäck, T. Multi-objecctive bayesian global optimization using expected hypervolume improvement gradient. Swarm and Evolutionary Computation, 44: 945 956, 2019. ISSN 2210-6502. doi: https://doi..rr http////ooor/////// /wwo//..weev.20000 2018. 1..00077.
[59] Yang. K., Emmerich, M., Deutz, A. H., and Bäck, T. Efficient computation of expected hypervolume improvement using box decomposition algorithms. CoRR, 0bs//194.12661 2019.
[60] Yang, K., Palar, P., Emmerich, M., Shimoyama, K., and Bäck, T. A multi-point mechanism of expected hypervolume improvement for parallel multi-objective bayesian global optimization. pp. 656-663, 07 2019. doi: 10. 10.11455/22/77773337788.
[61] Yang, K., Palar, P. S., Emmerich, M., Shimoyama, K., and Bäck, T. multi-point mech- anism of expected hypervolume improvement for parallel multi-objective bayesian global optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 19, pp. 656-663, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 44406111618 doi: 10. 10.1145/33217077 2101:/3317777.3222 737.1227744 URL /tRlittts://Boi.rrr///00.
3321107.3321784
[62] Youn, B. D., Choi, K., Yang. R.-J., and Gu, L. Reliability- design optimization for crashworthiness of vehicle side impact. Structural and Multidisciplinary Optimization, 26:
272-283, 02 2004. doi: 10. 10.1000000008-000 158-003-0345-0.
[63] Zhang, G. and Block, D. E. Using highly efficient nonlinear experimental design methods for optimization of lactococcus lactis fermentation chemically defined media. Biotechnology progress, 1587-1557775977 2009.
[64] Zhang, Q. Liu, W., Tsang, E., and Virginas, B. Expensive multiobjective optimization by moea/d with gaussian process model. IEEE Transactions on Evolutionary Computation, 14(3): 456-474, 2010. doi: 10. 109/TEVC.2009 1.33.1
[65] Zhou, A., Zhang, Q.. and Zhang, G. A multiobjective evolutionary algorithm based on decom- position and probability model. In 2012 IEEE Congress Evolutionary Computation, pp. 1-8, 2012. doi: 10. 10910/CCC22212 2.552994.
[66] Zitzler, E., Deb, K., and Thicle, L. Comparison of multiobjective evolutionary algorithms: Empirical results. Evol. Comput.. 8(2):173-19) 195, June 2000. ISSN 1063-6560. doi: 10.1162/ 106365600568202. URL/https:
[67] Zitzler, F., Deb, K., and Thiele, Comparison of multiohjectiie evolutionary algorithms: Empirical results. Evolutionary computation, 8(2):173-195, 2000.
14


Reviews:
[{"review_id": "tcU7fTYlcQy", "reviewer": "Reviewer_6KXs", "summary": "The paper focuses on the setting of multi-objective Bayesian Optimization (BO), when observations are corrupted by noise. Existing approaches only consider the uncertainty in the new point where the function is being evaluated, but consider the Pareto front from prior observations to be fixed. This work, on the other hand, additionally assumes uncertainty in the Pareto front - this is a natural assumption when observations contain noise. The authors introduce a new acquisition function, NEHVI, which extends the classical expected hypervolume improvement (EHVI) criterion. They also derive a new parallel variant with polynomial complexity, qNEHVI, which can replace the more complex qEHVI variant; this is made possible by re-using cached box decompositions. Various experiments demonstrate strong performance and competitive wall-times.", "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 of this work\n- The work is very well motivated. Assuming uncertainty in the Pareto front is not just desirable but also required, in the standard BO setting where observations contain noise.\n- The idea of caching the box decompositions is a central contribution of this work. This idea allows the efficient (polynomial) computation of qNEHVI (or qEHVI), which would otherwise be intractable (exponential) is we use the standard inclusion-exclusion principle (IEP).\n- The experiments are quite comprehensive, in the sense that they include several competitors from prior literature and a number of synthetic and real benchmarks. qNEHVI with cached box decompositions performs consistently well in terms of Pareto front quality and wall time.\n- The CBD-based algorithm offers very visible benefits in terms of execution time compared to the IEP-based algorithm. The latter cannot even handle batch sizes beyond a certain size (e.g., 16 or 32).\n- The work seems to be technically sound, and it contains a rigorous sample average approximation convergence result for NEHVI.\n- The paper is well written.\n\nConcerns about this work\n- My major concern is that this work is more or less an extension of (Daulton, Balandat and Bakshy 2020). That work already introduces some important concepts: (i) the q-expected hypervolume improvement (qEHVI), (ii) box decompositions for the computation of hypervolume improvement, (iii) computing q-HVI with the inclusion-exclusion principle, (iv) (quasi-)MC methods for computing qEHVI, (v) differentiability of the MC-estimator qEHVI, and (vi) sample average approximation convergence results for qEHVI. The major contributions of the current work compared to (Daulton, Balandat and Bakshy 2020) are in my view:\n  - Assuming noise/uncertainty in the Pareto front when computing the expected hypervolume improvement.\n  - Caching the box decompositions to avoid computing the Pareto front and performing an expensive box decomposition every time we draw new samples (this is a very central idea in this work).\n  - Algorithm for efficient sequential greedy batch selection using cached box decompositions (polynomial complexity versus exponential with inclusion-exclusion principle). \n\nThe idea of caching the box decompositions is certainly interesting and has the potential to improve efficiency, but overall the novelty is not very strong. To me, this work seems to be mostly about efficient computation of  qEHVI (or the more general qNEHVI).\n- Related to the point above, the convergence result is very reminiscent of the convergence proof in (Daulton, Balandat and Bakshy 2020).\n- The scope of this work is a bit unclear. On the one hand, this work is about extending EHVI or qEHVI with noise. But on the other hand, it is about efficient computation of both the noiseless and noisy variants. The efficient batch selection algorithm could even be applicable in the original noiseless setting.\n- The asymptotic complexities for CBDs or IEP depend exponentially on the number of objectives. This means that even with the efficient algorithm proposed in this work, multi-objective BO over several objectives could be prohibitively expensive. On the other hand, for up to 4 objectives approaches based on trust regions (e.g., (Eriksson et al. 2019) or (Eriksson and Poloczek 2021)) might be able to handle high-D inputs and multiple constraints better. Furthermore, Thompson sampling for evaluation of candidate points could lead to high efficiency. It is not clear how this line of work compares to such approaches in terms of solution quality or efficiency.\n\nAdditional questions to authors\n- Are there new technical elements in the convergence proof compared to the convergence result in (Daulton, Balandat and Bakshy 2020)?\n- Have the authors tried experiments with more than 4 objectives? Could the CBD-based algorithm handle several objectives?\n- At what noise levels (e.g., in terms of std) does it start to make a difference whether we use EHVI or NEHVI? Are small noise levels still able to lead to visible errors when using EHVI?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss openly the limitations of their work in Section 8 (Discussion Section).\nThe authors discuss the potential societal impact of their work in detail in Appendix A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Ua6KgDdH-l", "reviewer": "Reviewer_dGcJ", "summary": "The authors describe an BO algorihm for multi-objective optimization using hypervolume improvement. The main contribution is the incorporation of noise into the estimation of the improvement measure. The algorithm is evaluated on four functions and theoretical analysis is performed. In the experiments, the algorithm performed best on the set of functions.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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- Straight forward idea that is easy to understand\n- Theoretical and empirical analysis\n\nweaknesses\n- The evaluation section features significantly more algorithms than objective functions that are evaluated.\n- Some of the literature/contributions in ES-based MOO are missing\n- In parts the paper feels like it is using much too much text to present a small(but neat!) idea.\n\nDetails:\n- I would have liked to see some more functions to evaluate. An easy target would have been parts of the BBOB-biobj benchmark (with and w/o artificial simulated noise). The noise-free version would give an indication of how well the algorithm is positioned within the overall segment and would enable comparisons to strong noise-free baselines like the UP-MO-CMA-ES. This would also give strong indications of how more difficult the functions become under the chosen level of noise.\n\n- The idea of doing greedy optimization for hypervolume improvement in section 5.1 is not new. The MO-CMA-ES is doing that (under the name hypervolume contribution, see[*]) to select which subsets of point to keep in the pareto front. Otherwise the adaptation to the noisy case seems to follow straight forward from the approach. \n\n- I feel that the presentation could be improved and shortened a lot. e.g. the rhs of (3) feels unnecessary since it just spells out how the HVI is computed by the algorithm. The paragraph \"Conditional Posterior Sampling\" reads like standard optimization techniques used to acquire GP samples and has nothing to do with CBD. 5.1 similarly seems to be completely independent of CBD and any algorithm for computing the HVI could be inserted here. Moreover, it feels like the novel core of 5.1 is just a short addendum to 4.2. This is a bit of a shame because some of the \"meat\" of the paper has been moved to the appendix to make space for these computational basics which do not serve the presentation of the core idea.\n\nI do think the idea is good and if i have not missed any important prior work, it does present a good contribution to the field (even though I am not an expert in the BO side of MOO). But I think, the authors should take some time to add a few more results and to slightly clean up the paper to make the core idea more prominent.\n\nNote: Contrary to what the checklist states, i could not find any mention of compute time spent on the experiments. There is a statement of higher efficiency i have found, but no measurement of approximate compute resources required to repeat the experiments. If I missed it, maybe the authors can provide me a hint to where it is written.\n\n[*]Thomas Voß, Nikolaus Hansen, Christian Igel: Improved Step Size Adaptation for the MO-CMA-ES\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "limitations are discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "OMm3LjZLQfK", "reviewer": "Reviewer_35tW", "summary": "The paper proposes a novel method to perform multi-objective BO based on Expected HyperVolume Improvement. Specifically, the authors argue that taking into account noisy observations and dealing with that noise improves the optimisation as they introduce a new acquisition function NEHVI. They moreover introduce a parallelisation framework enabling scalable batch acquisition in their novel acquisition function. This paper is well written. The ability to use EHVI in a noisy environment is useful in practice and in my opinion, the improvement in scalability is important for the community. However, I would have liked to see experiments led with varying numbers of objectives as it is known that it’s a main bottleneck of EHVI in practice.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "1) The authors interestingly avoid having to decompose their hypervolumes at each iteration using a cache mechanism. I think this is a good direction and really relevant. What is not clear to me, however, is what order of error is introduced using the above mechanism? Can the authors please elaborate a bit on this in their rebuttal? \n\n2) Is the decomposition fixed for each BO step? If so, what is the impact on estimating (2)? It would be interesting to see such an analysis.\n\n3) It is mentioned by the authors that IEP and CBD are mathematically equivalent but can CBD - while producing the exact same acquisition value for a set of points, is significantly cheaper – scale to as many objectives and what is the cost of using CBD over IEP in practice, maybe in terms of convergence of the acquisition optimisation apart from purely memory & wall-time?\n\n4) Related to the above, Theorem 1 relates to NEHVI but not qNEHVI. What is the cost of SAA in that case on the convergence during the acqusition Optimisation?\n\n5) There are many benchmarks in this paper which is great. However, I would really like to see the performance as a function of an increase in the number of objectives as well as in terms of higher dimensions. Can the authors perform such an analysis?\n\nRelated Work: \nI think the paper covers the most relevant related work. I do, however, think include and benchmarking against the following can aid in further improving the paper: \n1. http://proceedings.mlr.press/v80/lyu18a/lyu18a.pdf\n2. https://arxiv.org/pdf/2012.03826.pdf\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "CxJYQ5llhfX", "reviewer": "Reviewer_LnaP", "summary": "The authors propose a version of a parallel Expected Hypervolume Improvement acquisition function for multi-objective Bayesian optimization. They show improved scaling over existing methods on a variety of benchmarks.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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 technical contribution is incremental but solid. Some claims must be clarified, as well as highlighting when simplifications are done for speeding up computations (e.g., not just in appendix). The empirical results are strong.  \n\nDetailed comments\n\nIn the abstract, the authors “argue that, even in the noiseless setting, the problem of generating multiple candidates in parallel can be reduced to that of handling uncertainty in the Pareto frontier.” but the meaning is unclear in the rest. Note that there are works on quantifying the uncertainty in the Pareto front, see e.g., \n- Calandra, R., Peters, J., & Deisenrothy, M. (2014). Pareto front modeling for sensitivity analysis in multi-objective bayesian optimization. In NIPS Workshop on Bayesian Optimization (Vol. 5).\n- Binois, M., Ginsbourger, D., & Roustant, O. (2015). Quantifying uncertainty on Pareto fronts with Gaussian process conditional simulations. European journal of operational research, 243(2), 386-394.\nIn addition, this is seemingly in contradiction with the beginning of Section 5 where sampled Pareto fronts are not updated based on the batch points (in the noisy case).\n\nIt is referred several times to the “exponential” complexity of the batch variant, presumably related only to the method in [7]. This should be clarified.\n\nIn section 4, it is written “To our knowledge, all previous work on EHVI assumes that observations are noiseless” while there is a dedicated paragraph starting line 128, and just below, line 182, is the obvious fix. Note that reinterpolation is another commonly used option in practice, see, e.g., Forrester, A., Sobester, A., & Keane, A. (2008). Engineering design via surrogate modelling: a practical guide. John Wiley & Sons.\n \n\nMinor points:\n- Figure 1: Add true Pareto front and reference point\n- Page 1, line 66: what is a “high-quality implementation”?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for the additional clarifications provided in their rebuttal. All reviewers agreed that this work is of practical importance and made solid contributions by building on top of prior work, addressing an issue overlooked in the literature (namely the uncertainty residing in the Pareto front). The authors conducted an extensive set of experiments. They pre-dominantly focus on BO methods; including multi-objective approaches not relying on the BO paradigm could strengthen the paper. It was is also surprising the author missed to include the following reference/baseline:

Daniel Golovin and Qiuyi Zhang. Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization. 2020.
Decision: Accept (Poster)