Covering Multiple Objectives with a Small Set of Solutions Using Bayesian Optimization
Authors: Natalie Maus
Kyurae Kim
Yimeng Zeng
Haydn Thomas Jones
Fangping Wan
Marcelo Der Torossian Torres
Cesar de la Fuente-Nunez
Jacob R. Gardner
Venue: NeurIPS 2025 poster ()
Keywords: Bayesian optimization
coverage optimization
high-dimensional black-box optimization
multi-objective Bayesian optimization
drug design
Primary area: probabilistic_methods

Abstract: In multi-objective black-box optimization, the goal is typically to find solutions that optimize a set of $T$ black-box objective functions, $f_1, \ldots f_T$, simultaneously. Traditional approaches often seek a single Pareto-optimal set that balances trade-offs among all objectives. In contrast, we consider a problem setting that departs from this paradigm: finding a small set of $K < T$ solutions, that collectively "cover" the $T$ objectives. A set of solutions is defined as "covering" if, for each objective $f_1, \ldots f_T$, there is at least one good solution. A motivating example for this problem setting occurs in drug design. For example, we may have $T$ pathogens and aim to identify a set of $K < T$ antibiotics such that at least one antibiotic can be used to treat each pathogen. This problem, known as coverage optimization, has yet to be tackled with the Bayesian optimization (BO) framework. To fill this void, we develop Multi-Objective Coverage Bayesian Optimization (MOCOBO), a BO algorithm for solving coverage optimization. Our approach is based on a new acquisition function reminiscent of expected improvement in the vanilla BO setup. We demonstrate the performance of our method on high-dimensional black-box optimization tasks, including applications in peptide and molecular design. Results show that the coverage of the $K < T$ solutions found by MOCOBO matches or nearly matches the coverage of $T$ solutions obtained by optimizing each objective individually. Furthermore, in *in vitro* experiments, the peptides found by MOCOBO exhibited high potency against drug-resistant pathogens, further demonstrating the potential of MOCOBO for drug discovery. All of our code is publicly available at the following link: https://github.com/nataliemaus/mocobo.

Multi-Objective Coverage Bayesian Optimization
(MOCOBO)
Natalie Maus' Kyurae Kim
Yimeng Zeng
Haydn Thomas Jones
Fangping Wan
Marcelo Der Torossian Torres
Cesar de la Fuente-Nunez Jacob R. Gardner
University of Pennsylvania Philadelphia. PA, USA
Abstract
In multi mujti--bjeectvv black-box optimization, the goal is typically to find solutions that optimize set of I' black-box objective functions, fi.... fr. simultaneously. Traditional approaches often seek single Pareto-optimal set that balances trade- offs among all objectives. In contrast, we consider a problem setting that departs from this paradigm: finding small set of K < T solutions, that collectively "cover" the objectives. A set of solutions is defined as "covering" if, for each objective fI.... Jr. there is at least one good solution. A motivating example for this problem setting occurs in drug design. For example, we may have T pathogens and aim to identify a set of K < T antibiotics such that at least one antibiotic can used to treat each pathogen. This problem, known as coverage optimization, has yet to be tackled with the Bayesian optimization (BO) framework. To fill this void, we develop Multi- ObjeiiO Coverage Bayesian Optimization (MOCOBO), a BO algorithm for solving coverage optimization. Our approach is based on new acquisition function reminiscent of expected improvement the vanilla BO setup. We demonstrate the performance of our method nigh-dimensional black-box optimization tasks, including applications in peptide and molecular design. Results show that the coverage of the K < T solutions found by MOCOBO matches nearly matches the coverage of T solutions obtained by optimizing each objective individually. Furthermore, in in vitro experiments, the peptides found by MOCOBO exhibited high potency against drug-resistant pathogens, further demonstrating the potential of MOCOBO for drug discovery. All of our code publicly available at the following link:
com/ www.cottaaaa/c/eeec nwwalaaaallliaaaa ewaus/mocom
1 Introduction
DOVUTS fi
DONEIS fa. J/3
Olojertive value
Bayesian optimization (BO; (13) general framework for sample-efficient optimization of black-box functions. By using probabilis- tic surrogate model, such a Gaussian pro- cess (GP: 4), Bayesian optimization balances exploration and exploitation to identify high- performing solutions with a limited number of function evaluations. BO has been successfully applied in a wide range of domains, including 77.
-30
Dousikt
Cooor wil (Roward: -8)
point [Renard:
Figure 1: Traditional multi-objective optimization for T objectives might select any point along the Pareto frontier, but in some situations like this any Pareto optimal point performs poorly at least one objective. In situations where multiple T solutions allowed we can sometimes optimize all objectives well. Note that this is a simplified schematic meant illustrate intuition.
hy perparameter tuning [5] 6 A/B testing
chemical engineering [8] drug discovery and more.
9
<
*Corresooddence to: Immaus @ upenn.u
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

For application domains such as drug discovery, however, the setup assumed by vanilla BO, where there is only one clear objective, is often insufficient. Consider the example of designing antibodies for treating a broad spectrum of pathogens. Here, the activity against each individual pathogen serves as an objective, each equally important. Ideally, one would seek to optimize all objectives simultaneously by obtaining single broad-spectrum antibiotic. When this is not possible, however, we should seek antibiotics that are potent against a large enough group of pathogens. By identifying a set of such solutions a covering ser-we would obtain set of drugs that are together lethal against the set of pathogens.
At first, this setup may be reminiscent of the black-box, setup via multi-objective BO (MOBO; [0)) These methods search for Pareto- optimal solutions that balance the trade-offs between the individual objectives, enabling practitioners to post hoc select single solution lying on the Pareto front based on their preferences. In cases where some objectives are completely incompatible with each other, however, selecting single solution on the Pareto front cannot simultaneously satisfy performance requirements across those objectives. This is illustrated in Figure | where no individual solution can provide acceptable performance across all objectives due to the extreme trade-offss between objectives.
optimization, which has been tackled under
Instead, our problem is distinctly described as the coverage optimization problem. More formally, consider a set of T distinct objectives. Our goal is to obtain a set-valued solution of size K T, where the set "covers" the I objectives: For each objective, this K -leemenn covering set should contain at least one solution that performs similarly to the maximizer of that objective. In the context of drug design, this translates to identifying K drugs such that each of the T pathogens is effectively addressed by at least one drug in the set. This setting particularly relevant to applications where the size of K is associated with downstream cost. For instance, in drug discovery, the number of compounds that can be synthesized is fundamentally constrained by the capacity of the facility.
Previously, the coverage optimization problem has been tackled in [17119] through gradient-based algorithms, while for the black-box setup, Liu et al. 20 proposed an evolutionary algorithm. Over the years, variants of BO have demonstrated superior performance over evolutionary algorithms in sigh-dimensional [15 21 22 and multi-objeccive problems (14), which has been instrumental for its success in drug discovery 12 25). Therefore, it is natural to ask how we could harness the strengths and flexibility of BO to attack the coverage optimization problem.
In this work, we develop Multi-Objective Coverage Bayesian Optimization (MOCOBO)-a BO-based method for solving the coverage optimization problem with high-dimensional black-box objectives. MOCOBO primarily consists of a coverage-optimization analog of the celebrated expected improve- ment (EI; (26) acquisition function, where the covering set is greedily constructed via submodular optimization (27). We evaluate the resulting algorithm on realistic optimization tasks: drug discovery over molecules and peptides, and tuning of image processing pipelines. Baselines include the method of [20] and MOBO.
Our contributions are summarized follows:
We propose MOCOBO, coverage optimization algorithm for black-box objectives that can deal with structured, -igh-dimensional search spaces, and scale large numbers of function evaluations.
We experimenaally validate MOCOBO on challenging, high- high-dimensional optimization tasks including structured drug discovery over molecules and peptides, demonstrating its ability to consistently outperform state-of-the-art BO methods in identifying high-performing covering sets of solutions.
We demonstrate empirically that the small sets of K < T solutions found by MOCOBO consistently nearly match the performance of a larger set of T solutions individually optimized for each task.
We demonstrate the potential of MOCOBD for drug discovery using an in vitro experiment showing it produces potent antimicrobial peptides that cover out of 11 drug resistant or otherwise challenging to kill pathogens, with moderate activity on 1 out of 11.
2 Background
Bayesian Optimization. To solve the black-box optimization problem, BO operates by iteratively selecting query according to certain search policy 3 and observing the objective value on the query. The observations that have been obtained up to iteration n 2 0 are collected into a dataset D,, to form surrogate model, typically GP, which supplies information to the policy. Most policies are

---

chosen to maximize a function known as acquisition query x found as
3 such that, at each step n 2 0, the
X arg max a (x: Dr.)
(I)
XEx
where EI (26] is a popular example of an acquisition function. In our case, the optimization problem over covering sets. Naturally, acquisition function for this setting is needed.
Trust Region Bayesian Optimization (TuRBO), For high-dimensional problems, the basic scheme of solving Equation (T) is no longer effective. Local BO methods (21) address this issue by restricting the search space to a trust region that is adjusted adaptively. This simple modification has been shown be effective and has been employed in various setups. In high-dimensional MOBO problems specifically, a variant of TuRBO [21] referred to as TuRBO-M has been shown to be effective [14, 28) TuRBO-M works by running M parallel local optimization runs, each maintaining its own dataset D; and surrogate model. Each local optimizer proposes candidates within hyper-rectangular trust region Tú. which is taken be a rectangular subset of the space X centered on the incumbent x," The side of each T, is chosen to have length & [emin- mmax]. If an optimizer improves the incumbent for Psuce consecutive iterations, l expands to min(26,, mmax). If not improved Ptail iterations, & is halved. Optimizers are restarted if é; drops below Emin- We will later incorporate this scheme for solving the coverage optimization problem.
3 Multi-Objective Coverage Bayesian Optimization
3.1 Coverage Optimization
Consider T > 1 objectives fI..... Jr. each defined as Se X' - R for each / = 1....,? T, all sharing 1}. consider the
the same input domain X. For some user-defined parameter K (1...., task of finding set of K solutions S* = (xi...., } that "covers" the T objectives {feht=t..... Specifically, the set 5 S X "covers" the T objectives if, for each objective ft ff frrh there least one solution x E S* for which f. is well optimized by x We evaluate how well a set of K points (x)..... xx) "covers" the T objectives using the following "coverage score" Formally,
c((xi,.... xk)) Σ
K max (xx). k=1
Formally, we seek set St = [x]...., xxk such that:
S arg max ([X1,...,,K?
(x (x....R) JCX
The coverage score in (2) only credits single solution for each objective. If, for example, Se is maximized by one of the in the solution set, improving the value of ft on some other Xj becomes irrelevant so long as f((x) 2 f((x)). In the setting where K the coverage score collapses into a trivial linearization of the objectives, and true multi-objecctve BO methods should be preferred. In the setting where K = the coverage score is trivially optimized by maximizing each objective independently. This problem has previously been formulated in 17-20), where we will proceed by developing a new BO-based solution.
3.2 Multi-Objective Coverage Bayesian Optimization (MOCOBO)
In this section, propose MOCOBO an algorithm which extends Bayesian optimization to the problem setting above. On each step of optimization 8, we use our current set of all data evaluated so
far D, (x), (Xn, yn)} to define the best covering set Sū, {x, (s)
(s) Dz} ...., ......X''............
found so far. Here y, = (fi (x:), .... frx);) and is the number of data points evaluated so far at step 8. Following Equation (3), we define Sh, as follows:
Sp. Xx)
arg max
e((x)
xx))
arg max [XL....XX]]
Σ max
fx(x).
(4)
Here, c(S) denotes the best coverage score found by the optimizer after optimization step s.
3

---

3.2.1 Candidate Selection with Expected Coverage Improvement (ECI)
Given Sp., our surrogate model's predictive posterior p(y D) induces posterior belief about the improvement in coverage score achievable by choosing to evaluate at x next. We naturally extend the typical expected improvement (EI; (26) acquisition function to the coverage optimization setting by defining expected coverage improvement (ECI):
ECI(x)= = D) clS c(S -(S,,
(5)
Here c(Sb,) ) is the coverage score of the best possible covering from among all data observed D. as we shall see, constructing this set SD. will be our primary challenge. c(Sp,..((xx))) ) is the coverage score of the best possible covering set after adding the observation (x, y). Thus, ECI gives the expected improvement in the coverage score after making observation at point x. We aim to select points during acquisition that maximize ECL. Note that the name ECI is shared with a method proposed by Malkomes et al. [29) for multi-objective experimental design, but their method targets an entirely different notion of "coverage." " (See Section for more details.)
We estimate ECI using& a Monte Carlo (MC) approximation. To select single candidate x, we sample m points P = (P1, P2, .... pm]- For each sampled point Pý, we sample realization y, = (fi (P:)...., (r(p)) from the GP surrogate model posterior. We leverage these samples to ; compute an MC approximation the ECI of each Py:
Cl(p;) max(0, mnax(O,c(Sbbuuu clS..
d(b.))).
(6)
is the approximation of the coverage score of the new best covering set if we choose to evaluate candidate pj. assuming the candidate point will have the sampled objective values Yj. We select and evaluate the candidate Pj with the largest expected coverage improvement.
Here, ((P((P,
{;))
3.2.2 Greedy Approximation of Best Observed Covering Set
The candidate acquisition method in Sec- tion 3.2.1 utilizes the best covering set of K points among all data collected so far, Sh On each step of optimization MOCOBO must there- fore construct Sp, from all observed data D., Sh may change each step of optimiza- tion after new data is added to Dz-
Algorithm Greedy (1 ( -Approximation for Finding SD. (Incremental Strategy)
Require: Dataset D,, observed values f((x) for all t E {l...., Th and x E D,, set size K. Initialize A + 0. (Start with an empty set.) Compute the initial coverage score for A: c(A) + 0.
Lemma 3.1 (NP-hardness of Optimal Covering Set). Let T, K be finite positive integers such that K < T. Let fi....,f fr be real valued functions. Let D. (1) ..., (Xn: yn) be a dataset of n. real valued data points such that for all x; y; (x4)),,...., (x:)). Let SD, be the optimal covering set of size K in D. as defined in Equation (4. Then, constructing SD, is NP-hard.
for k = to K do Initialize Xhest <- None and Anea <- -cc. for D2 \ do Compute marginal coverage of adding x to A:
T
Ac +
Σ max max (xxx)x))(3) -c(A) -c(A).
xEA
t=1
Proof. The proof is in Appendix !
if Ac > Abeat then
Xbest + and Abeat + Ac.
Since constructing Si, is NP-hard, we use an approximate construction of Sp, each step of optimization s. We present Algorithm D which is based on greedy submodular optimiza- tion (27). that provides (1-1 aapproximation of Sp, after an execution time of OnKTT).
end if
end for
Update +- AU (Xheu), c(A) &- c(A) +
Anea-
end for Output: Ab. + A.
Theorem 3.2. The set Ab, output by Algo- rithm 7 satisfies ol c(Ab,) 2 2) c.S),) ((S)))
Proof. The proof is in Appendix

---

The algorithm iterates K times to construct the covering set. In each iteration, it evaluates at most n candidate points, and for each candidate, it computes the incremental coverage score by iterating over 7 objectives. The execution time complexity is thus O(K.n. n. T). For practical applications where we can assume relatively small K and T, the execution time is approximately (n)). For an empirical evaluation of the execution time, see Appendix B.3
Time Complexity of Algorithm 1
Corollary 3.3 (Algorithm D is the best possible approximation of Sb, ). There is no polynomial execution time algorithm that provides better approximation ratio unless P NP.
This follows from the fact that we reduced from Max k-cover, for which a better approximation ratio is not practically achievable unless P NP 130
Proof.
3.2.3
Extending ECI to the Batch Acquisition Setting (q-ECI)
In batch acquisition, we select batch of q >> 1 candidates for evaluation. Following recent work on batch EI 31 32 we define q-ECI, natural extension of ECI to the batch setting:
xxECI(X): = Ep(Y(X.)) max {0, max r=I....
c( -(DD. ( }}.
(7)
q-ECI gives the expected improvement in coverage score after simultaneously observing the batch of ........,, .x., X. However, the resulting Monte Carlo expectation would require O(q x m) evaluations of Algorithm We therefore adopt more approximate batching strategy for practical use with large q (see Appendix for details).
q points = fxi.....
3.2.4 MOCOBO with Trust Regions
In order to find a set of K solutions, as explained in Section 2 MOCOBO follows the TuRBO-M principle. That is, it maintains K simultaneous local optimization runs using K individual trust regions. Each local run desired set S* As in the original TuRBO paper, trust regions rectangular regions of the search space T& S X' defined solely by their size and center point. We center the K trust regions on the best covering set of solutions observed so far during optimization. In particular, each optimization step 8, we construct an approximation of SD, using Algorithm T and center each trust region Tk
fl....,AA ..)...,,) K} aims to find a single solution x which together form the
on the corresponding point x in Sp. = {xi q-ECI when g 1) acquisition function to select g candidates for evaluation from within each trust region. The MC approximation of ECI described Section .3.2.on33.2.Ijcaa.
(x)) xx }. We then use our proposed ECI (or
be straightforwardly applied to select candidates in trust region T% by sampling the m discrete points from within the rectangular bounds of Tg. Since we select and evaluate q candidates from each of the K trust regions, the total number of observed data points algorithm, each trust region Te has success and failure counters that dictate the size of the trust region. For MOCOBO, count success for trust region Te whenever Te proposes candidate on step s that improves upon the best coverage score and is included in SD.41"
step of MOCOBO is
x K x q. As in the original TuRBO
Experiments
We evaluate MOCOBD on four high- digh-diiensional,, multi-objectivv BO tasks for which finding a set of K < T solutions to cover the T objectives is desirable. Detailed descriptions of each task are in Section 4.1 Two tasks involve continuous search spaces, allowing direct application of MOCOBO, while the other two involve structured spaces (molecules and peptides), requiring an extension for structured optimization.
Implementation details and hyperparameters. We implement MOCOBO using BoTorch [33 and GPyTorch [34]. Code to reproduce MOCOBO results on all tasks considered is available on GitHub: https:://p /i thub. wwwmnatal iet.ttalllemmm//moooobao We use an acquisition batch size of 20 for all tasks and across all BO methods compared. Since we consider challenging high-dimensional tasks that require a large number of function evaluations, we use approximate GP surrogate models, specifically PPGPR 335 Further implementation details are provided in Appendix G
5

---

Rover with 12 Oboitacle Courses
Rover with Eight Ohstacle Courses www.aaaee
Rover with Four Ohstnele Courses
Ranolazine MPO Molecule Design
Mean Best Coverage Score Found
5.0
20
-40
4,5
100
50000
leb
Image Mupping
Image Mapping
Template Peptide Design
Template Peptide Design
4.60
100
4.1
-200
-300
4.0
4.45
-300
400
3.9
4.40
-400
2,5000
50000
25000
50000
01
2500000
S00000
Number Oracle Calls
leh
MOCOBO (Ours)
Random Sampling
ROBOT 2023)
Individuslly Optimized
CluSO al., 2024)
2021)
TuRBO (Eriksson 2019)
2022)
Figure 2: Coverage optimization results on all tasks considered.
Structured Search Spaces. Some of our optimization tasks operate on structured search spaces that are not Euclidean. For this, it is typical to employ a generative model-suee such as a variational autoencoder (VAE; 36 37)-to convert structured inputs into continuous latent space for BO (8) 40.48), resulting in an algorithm known as latent space BO. Naturally, for problems with structured search spaces, we apply MOCOBO to the latent space of pre-trained VAE on which perform regular end-to-end updates with the surrogate model during optimization 47
Plots. In Figure we plot the best coverage score Equation (2) obtained by the K best covering
solutions found far after a certain number of function evaluations on each task. Since BO baseline methods are not designed to optimize coverage directly, instead aiming to find single solution or set of solutions optimize the T objectives, we plot the best coverage score e obtained by the K best covering solutions found by the method. All plots show mean coverage scores averaged over 20 replications of each method, and show standard errors.
Baselines. In all plots, we compare MOCOBO against ClusO, TuRBO, ROBOT, and MORBO 14 20
28 While MORBO is not designed to optimize coverage, the MOBO setting is closely related to problem setting, and MORBO represents a strong baseline among existing MOBO techniques. We also compare sampling uniformly at random in the search space. For each method, compare the performance of the best set K solutions found.
Extending baselines to the structured BO setting. In the case of the two structured optimization tasks (molecule and peptide design), we apply LOL-BO and ROBOT as described by design for these problem settings. For MORBO and CluSO, we take the straightforward approach of applying the methods directly the continuous latent space the VAE model without other adaptations. The same pre-trained VAE model is used across methods compared.
Table Best set of K peptides found by one run MOCOBO for the "template free" peptide
design task. We provide the APEX model's predicted MIC for each sequence on each of the 11 target pathogenic bacteria. The target pathogenic bacteria B1, Bl...., B11 are listed in Table H.3 (-) and (+) indicate Gram negative and Gram positive pathogenic bacteria respectively. The best/lowest MIC achieved for each pathogenic bacteria
bold in each column. See row "TF1" " Figure and
Figure B.I for in vitro MICs for this set of K = 4 peptides. See Table B. for analogous result on "template constrained" peptide design task.
Peptide Amino Acid Sequence
B1(-)
B2(-)
B3(-)
B4(-)
B5(-)
BGi-)
B7(-)
BS(+)
[9(+))
B10(+)
BI+
1.393
IFHLKILIKILALC
0.999
15,565
1,860
1.952
404.254
486.860
406.034
1.233
1.318
7.359
0.981
2.654
3.268
3.113
4.854
4.923
12.967
14.610
22.631
29.685
254.306
3.947
0.939
0.906
1.124
1.310
10.909
1.384
1.711
12.776
32.884
434,193
1.037

---

Extending baselines to the coverage optimization setting, As TuRBO, LOL-BO, and ROBOT target single-objective optimization, we conduct T independent runs to optimize each of the T objectives for the multi-objective task. We use all solutions gathered from the T runs to compute the best covering set of K solutions found by each method. Unlike LOL-BO and TuRBO, which seek a single best solution for given objective, single run of ROBOT seeks set of M solutions that are pairwise diverse. We run ROBOT with M = K so that each independent run of ROBOT seeks M = K diverse solutions. The aggregate result of the '' independent runs for ROBOT is thus K diverse solutions for each of the T objectives. We compare to the best covering K solutions from among those K T solutions. See Appendix G.4 for more details the diversity constraints used by ROBOT and the associated hyperparameters. MORBO is a multi-objeectiv optimization method and can thus be applied directly to each multi- covering set of K solutions found among all solutions proposed by the run. For CluSO, no extension is needed this method is designed for coverage optimization. We run CluSO with the same K used by MOCOBO, and all other hyperparameters set to CluSO defaults.
optimization task. For each run of MORBO, we compare to the best
As far we are aware, CluSO is the only existing method that tries to solve the black-box coverage optimization problem directly. We note that other adapted baselines are included not to criticize, but to underscore the importance of explicitly addressing this problem class.
T individually optimized solutions baseline. We also compare to brute-force method involving T' separate single-objective optimizations for each of the T objectives. using TuRBO for each run or LOL-BO for molecule and peptide design. This is not an alternative for finding K < T covering solutions, but instead identifies T solutions, one per objective, approximating a ceiling we can achieve on performance without the limit of K < T solutions. Approaching the performance of this baseline implies that we can find K solutions that do nearly as well as if we were allowed T solutions instead.
4.1 Tasks
Peptide design. In the peptide design task, we explore amino acid sequences to minimize the MIC (minimum inhibitory concentration, measured in pmml L L") for each of T = 11 target drug resistant strains or otherwise challenging to kill bacteria (B1-B7 Gram negative, B8-B11 Gram positive). Table H lists our target bacteria in this study. Briefly, MIC indicates the concentration of peptide needed to inhibit bacterial growth (see
and Dudek-Wicher/ 49). We evaluate MIC for a given peptide sequence and bacteria using the APEX 1.1 model proposed by Wan et al. [50]. To frame the problem as maximization, we optimize -MCC We seek K = 4 peptides that together form a potent set of antibiotics for all T 11 bacteria. To enable optimization over peptides, we use the VAE model pre-trained on 4.5 million amino acid sequences from Torres et al. (33 to map the peptide sequence search space continuous 256 dimensional space.
Template free vs template constrained peptide design. We evaluate MOCOBO on two variations of the peptide design task: "template free" (TF) and "template constrained (TC). For TF, we allow the optimizer to propose any sequence of amino acids. For TC, we add a constraint that any sequence proposed by the optimizer must have a minimum of 75 percent sequence similarity to at least one of the 10 template amino acid sequences in Table H.4) These 10 templates were mined from extinct organisms and selected by Wan et al. [50]. The motivation of the template constrained task is to design peptides specifically likely evade antibiotic resistance by producing "extinct-like" peptides that bacteria have not encountered in nature in thousands of years. For MOCOBO and all BO baselines (TuRBO, LOL-BO, ROBOT, and MORBO), we handle the optimization constraint by adapting techniques from SCBO [11] For CluSO and random sampling, we handle the constraint with rejection sampling.
Ranolazine MPO molecule design. Ranolazine a drug used to treat chest pain. The original Ranolazine MPO task from the Guacamol benchmark suite of molecular design tasks (52) aims to design an alternative to this drug: a molecule with a high fingerprint similarity to Ranolazine that includes fluorine. We extend this task to the multi-objective optimization setting by searching for alternatives to Ranolazine that include T = reactive nonmetal elements not found in Ranolazine: fluorine, chlorine, bromine, selenium, sulfur, and phosphorus. We aim to cover the T 6 objectives
with K = molecules. We use the SELFIES- VAE introduced by Maus et al. 47 to map the molecular space a continuous 256 dimensional space.
The rover optimization task introduced by Wang et al. 153 consists of finding 60- dimensional policy that allows a rover to move along some trajectory while avoiding fixed set of obstacles. To frame this as a multi-objective optimization task, we design T unique obstacle courses
Rover.
7

---

TF1
2
0.25
64
60
MIC (umol L:3
40
TC1
2
16
32
32
TC2
32
16
64
16
81 (-)
82
83
B4
(-)
B5
86 (-)
87
88 (+)
89 (+)
B10 B11 (4)
(+)
Figure In vitro results for the two best "template free" (TFI, TF2) and two best "template constrained" (TCI, TC2) runs of MOCOBO for the peptide design task. Columns are the best/lowest in peptides found by MOCOBO for each target pathogenic bacteria Bl,.... B11 listed in Table H3 (-) and (+) indicate Gram negative and Gram positive respectively. TFI and TC1 correspond to the single runs of MOCOBO shown in Table I and Table B.1 respectively. Methods
vitro MIC among the K
used to obtain in vitro MICs provided in Appendix
Menn Best Coverage Score Found
Rover with Four Obstaele Courses
Rapolazine MPO Molecule Design
Template Free Peptide Design
5.5
-50
-100
5
-150
200
-250
50000
2
250000
500000
Number of Oracle Calls
MOCOBO (Ours)
K Solutions, Each Individually Optimized for One Predetermined Subset the T Objectives
Figure 4: Ablation study comparing MOCOBO optimization performance where a known "good" partitioning of the I' objectives into K subsets is available in advance. We individually optimize K solutions, one for each partition.
for the rover to navigate. The obstacle courses are designed such that no single policy can successfully navigate all courses. We seek K < T' policies that least one policy enables the rover to avoid obstacles in each course. We evaluate on three unique instances with varying numbers of obstacle courses. For the instances of this task with T and 8, we seek to cover the objectives with K solutions. For the T = 12 instance, we seek to cover the objectives with K = solutions.
Image tone mapping. In high dynamic range (HDR) images, some pixels (often associated with light sources) can dominate overall contrast, requiring adjustments to reveal detail in low-contrast areas, problem known as tone mapping tunable parameters, resulting in high-dimensional optimization problem of subjectively perceived quality. We seek a covering set of K = 4 solutions to optimize a set of T = 7 image aesthetic (IAA) and quality (IQA) assessment metrics from the pyiqa library (55) (see metrics listed Table H. Our practical goal is that, while we do not know priori which metric is best for a particular image, covering all metrics may result in at least one high quality image. We optimize over the 13-dimensional parameter space of an established tone mapping pipeline to tone-map the "Stanford Memorial Church" " [56) and "desk lamp" [57] benchmark images. See Appendix H. for details.
[54] Section 6]. Tone mapping algorithms involve various
4.2 Optimization Results
In Figure 2 we provide optimization results comparing MOCOBO to the baselines discussed above on all tasks. The results show that MOCOBO finds sets of K solutions that achieve higher coverage scores across tasks. The "T Individually Optimized Solutions" baseline appears as horizontal dotted line in all plots of Figure 2 representing the average coverage score of T individually optimized solutions, serving as an approximation of the best possible performance without the constraint of limited K < T solution set. Results in Figure demonstrate that the smaller set of K < T solutions identified by MOCOBO nearly equals the performance of the complete set of individually optimized solutions, This result depends using domain knowledge to choose K large enough to achieve it.

---

Results in Figure show that matching the performance of T optimized solutions is possible with some values of K < T.
Although CluSO exhibits substantially lower performance than other baselines across the tasks we ionsider-inchudingg baselines not explicitly designed for the coverage problem-this should not be viewed as a criticism of the method. Rather, it reflects that CluSO was developed for low-dimensional black-box problems and does not scale effectively the high-dimensional and structured optimization settings we study, further motivating the need for our scalable MOCOBO approach.
of MOCOBD for the template free (TF) peptide design task. For each peptide, we provide the the APEX 1.1 model's predicted MIC for each of the 11 target bacteria. MIC values 16 p. are considered to be "highly active" " against the target pathogenic bacteria [50]. We highlight in Table T the comparison between the second peptide with the other three peptides. B1-B7 Gram negative (GN) bacteria, while B8-B1 are Gram positive (GP). Peptide 2 specialized to the GP bacteria (B8-B11 scores predicted highly active compared to the other peptides) the expense of broad spectrum activity for the GN bacteria (B5, B6, B7 predicted inactive). By specializing its solutions to GN and GP bacteria separately, MOCOBO achieves low MIC across the target bacteria with only K peptides. A similar table of results is also provided for the template constrained (TC) peptide design task (see Table B.1
Peptide design results. In Table [ provide the K 4 peptides found by
Figure 5: T 4 varied obstacle courses as multiple objectives for the rover task and K 2 covering trajectories (blue, magenta) found by MOCOBO. The first trajectory (magenta) successfully navigates obstacle courses and 3 (second and third panels from the left). The second trajectory (blue) navigates obstacle courses I and 4 (first and fourth panels from the left).
Figure 6: (Leftmost Panel) Initial hdr desk image for the desk variation of the "image tone mapping" task. (Four Rightmost Panels) Images obtained by transforming the hdr desk image using the best covering set of K solutions found by single run of MOCOBD.
In Figure we provide in vitro results for the best TF and two best TC runs of MOCOBO for the peptide design task. Here, "best" means runs that achieved highest coverage scores according to the APEX 1.1 model. For each run, Figure provides the best/lowest in vitro MIC among the K- 4 peptides found by MOCOBO for each target bacteria. Results demonstrate that solutions found by MOCOBO optimizing against the in-silico APEX 1.1 model achieve good coverage of the 11 target pathogenic bacteria in vitro. In Figure we provide the full set of in vitro results for each these runs MOCOBO, with MIC values obtained by each of the K 4 peptides found for each target bacteria. Methods used to obtain in vitro MICs are provided in Appendix
Molecule design results. In Table B.2 we provide results for the K = 3 molecules found by one run of MOCOBO for the molecule design task. Each the target elements is successfully present in one of the K molecules in the best covering These three molecules therefore effectively cover the T = objectives, with each objective having max score > 0.9.
Rover results. In Figure 5 we depict the varied obstacle courses used for the T 4 variation of the rover task and K = covering trajectories found by a single run of MOCOBO. In Figure B.3 and B.4 we provide analogous figures for the T and T 12 variations. In each example, the MOCOBO optimized set of trajectories covers all obstacle courses such that all obstacles are avoided.
Image tone mapping results. In Figure 6 and Figure B.2 we provide the original HDR images and the images obtained by the K = solutions found by single run MOCOBO for the church and desk test images, respectively. In both variations, three of the four solutions result in adequately

---

tone-mapped images, while one results in a poor-quality image (see the middle-right church image and the rightmost desk image). The poor quality images were each generated by the one solution that MOCOBO used to cover metrics 5 and 6 (see metric Il) numbers in Table H..I). This indicates that metrics and 6 are poor indicators of true image quality this setting. This result highlights a useful application of MOCOBO: By dedicating one of the K solutions to maximizing the misleading metrics (5 and 6), the other three solutions to can focus on the remaining subjectively better metrics.
4.3 Ablation study
A challenging aspect of our problem setting is that we do not know priori the best way(s) to divide the T objectives into K subsets such that good coverage can be obtained. In this section, we seek to answer the question: what is the efficiency lost by MOCOBO due not knowing efficient partitioning of the objectives in advance? To construct a proxy "efficient" partition to measure this, we first run MOCOBO completion
task, and then consider optimization if we had known the partitioning of objectives found at the end in advance.
With such an "oracle" partitioning in hand ahead of time, we can efficiently optimize by running K independent optimization runs: one to find a single solution for each subset in the fixed, given partition. With fixed partition, the coverage score in reduces to optimizing the sum of objectives in each relevant subset independently. In Figure we compare this strategy directly to MOCOBO on three optimization tasks. We plot the best coverage score obtained by K independent runs of TuRBO/LOL- on the fixed oracle K partiiiooning of the objectives by combining their solutions into a single set. MOCOBO achieves the same average best coverage scores with minimal loss in optimization efficiency despite having to discover an efficient partitioning during optimization. See Appendix [B.2 for additional ablation studies.
5 Related Works
The coverage optimization problem setting considered in this paper has not been previously explored in the Bayesian optimization literature. However, similar problem settings [7H191 have been studied in the context of gradient- multi-objective optimization. For instance, Ding et al. [17 demonstrated that the coverage problem generalizes various clustering methods, including k-means clustering, and proposed an algorithm that extends k-means++ [58] and Lloyd's algorithm [59] to efficiently solve the coverage problem using gradient descent. Li et al. [18] introduced Many- objective Multi-solution Transport (MosT), a novel framework that scales multi cujtti-bbeective gradient- based optimization large number of objectives. MosT uses optimal transport establish balanced assignment between objectives and solutions, allowing each solution to focus on a specific subset of objectives and ensuring that the collective set of solutions covers all objectives. Lin et al. [9 introduced novel Tehebycheff set (TCH-Set) scalarization approach for covering multiple conflicting objectives using a small set of collaborative solutions. They further propose a smooth Tehebycheff set (STCH-Set) scalarization method to handle non- non-smoothness in TCH-Set scalarization. The reliance on gradients makes these previous approaches inapplicable to the black-box setting.
For the black-box setting, Liu et al. (20) was the first to consider the coverage problem. They propose an analogous formalization of the coverage problem in the context of multi-objective blx optimization, along with a clustering-based swarm optimization algorithm (CluSO) designed to solve it. In Section 4 we provide empirical results demonstrating that our Bayesian optimization approach (MOCOBO) consistently outperforms CluSO by a large margin across all tasks considered.
Lastly, we note that Malkomes et al. 229 proposed method with the same name as the ECI we defined in Section 3 which was later extended in [60). The resemblance is only in the name, as their work addresses a fundamentally different notion of coverage. Mainly, they attempt to cover the input space by identifying a diverse set of feasible solutions that span a subspace defined by known threshold constraints each objective. In contrast, attempt to "cover" the different objectives.
Conclusions
By bridging the gap between traditional multi-objective Bayesian optimization (BO) and practical coverage requirements, MOCOBO offers an effective approach to tackle critical problems in drug design and beyond. This framework extends the reach of Bayesian optimization into new domains, providing a robust solution to the challenges posed by extreme trade-offs and the need for specialized, collaborative solutions. See Appendix D for additional discussion and limitations of MOCOBO.
10

---

Acknowledgments and Disclosure of Funding
N. Maus supported by the National Science Foundation Graduate Research Fellowship: K. Kim was supported by gift from AWS AI to Penn Engineering's 's ASSET Center for Trustworthy AI; J. R. Gardner supported by NSF awards IIS-2145644 and DBI-2400135; C. de la Fuente-
Nunez was supported by NIH grant 335GM138201 and Defense Threat Reduction Agency grants HDTRAI1810041, HDTRAI-21-
and IIDTRAI-23---000
References
[1] Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-492, 1998.
[2] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104
(1):148-175, 2015.
[3] Roman Garnett. Bayesian Optimization. Cambridge University Press, 2023.
[4] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, November 2005.
[5] Jasper Snoek, Hugo Larochelle, and Ryan Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems, volume 25, pages 2951-2959. Curran Associates, Inc., 2012.
[6] Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Eero Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020. In Proceediiggs of the NeurlPS 2020 Competition and Demonstration Track, volume 133 of PMLR, pages 3-26, 2021.
[7] Benjamin Letham, Brian Karrer, Guilherme Ottoni, and Eytan Bakshy. Constrained Bayesian optimization with noisy experiments. Bayesian Analysix, 14(2):495-519, 2019.
[8] José Miguel HernándezzLooato, James Requeima, Edward O Pyzer-Knapp. and Alán Aspuru- Guzik. Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space. In Proceedings of the International Conference on Machine Learning. volume 70 of PMLR, pages 1470-1479. JMLR, 2017.
[9] Diana M Negoescu, Peter I Frazier, and Warren B Powell. The knowledge-gradien algorithm for sequencing experiments drug discovery. INFORMS Journal on Computing, 2011.
[10] Daniel Kernández-Lobato José Miguel Hernández-Lobate. Amar Shah, and Ryan P. Adams. Predictive entropy search for multi multi-objective Bayesian optimization. In Proceedings of the International Conference on Machine Learning., volume 48 of PMIR, pages 149--1501.JML 2016.
[11] Syrine Belakaria, Aryan Deshwal, and Janardhan Rao Doppa. Max-value entropy search for multi-objective Bayesian optimization. In Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[12] Matteo Turchetta, Andreas Krause, and Sebastian Trimpe. Robust model-free reinforcement learning with multi-objective Bayesian optimization. In Proceedings of the IEFE International Conference on Robotics and Automation. IEEE, 2020.
[13] Mina Konakovic Lukovic, Yunsheng Tian, and Wojeiech Matusik. Diversity-guided multi- objective Bayesian optimization with batch evaluations. In Advances in Neural Information Processing Systems, volume 33, pages 17708-17720 Curran Associates, Inc., 2020.
[14] Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Multi-objective Bayesian optimization over high-dimensional search spaces. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, volume 180 of PMLR, pages 507-517. JMLR, 2021.
[15] Samuel Stanton, Wesley Maddox, Nate Gruver, Phillip Maffettone, Emily Delaney, Peyton Greenside, and Andrew Gordon Wilson. Accelerating Bayesian optimization for biological sequence design with denoising autoencoders. In Proceedings of the International Conference on Machine Learning, volume 162 of PMLR, pages 20459-20478 JMLR, 2022.
11

---

[16] Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, and Janardhan Rao Doppa. Uncertainty-awee aware search framework for multi-objective Bayesian optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30. AAAI Press, 2020.
[17] Lisang Ding, Ziang Chen, Xinshang Wang, and Wotao Yin. Efficient algorithms for sum-of- minimum optimization. In Proceedings of the International Conference on Machine Learning. volume 235 of PMLR, pages 10927-10959, JMLR, 2024.
[18) Ziyue Li, Tian Li, Virginia Smith, Jeff Bilmes, and Tianyi Zhou. Many-objective multi-solution transport. In Proceedings of International Conference on Learning Representations, 2025.
[19] Xi Lin, Yilu Liu, Xiaoyuan Zhang, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Few for many. Tehebycheff set scalarization for many-objective optimization. In Proceedings of International Conference Learning Representations, 2025.
[20] Yilu Liu, Chengyu Lu, Xi Lin, and Qingfu Zhang. Many-objectiie cover problem: Discovering few solutions to cover many objectives. In Parallel Problem Solving from Nature PPSN XVIII. volume 15151 of LNCS, page 68-82. Peringer-Verlage 2024.
[21] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Advances in Neural Information Processing Systems, volume 32, pages 5496-5507. Curran Associates, Inc., 2019.
[22] Miguel González-Duque, Richard Michael, Simon Bartels, Yevgen Zainchkovskyy, Sø ren Hauberg, and Wouter Boomsma. A survey and benchmark of high- -igeedimensi bayesian optimization of discrete sequences. In Advances in Neural Information Processing Systems, volume 37, pages 140478-140508. Curran Associates, Inc., 2024.
[23] Marcelo D. T. Torres Yimeng Zeng, Fangping Wan, Natalie Maus, Jacob Gardner, and Cesar de la Fuente-Nunez. A generative artificial intelligence approach for antibiotic optimization. bioRxiv Preprint
bioRxiv, 2024.
[24] Di Wu, Natalie Maus, Anupama Jha, Kevin Yang. Benjamin D Wales-MeGrath, San Jewell, Anna Tangiyan, Peter Choi, Jacob R Gardner, and Yoseph Barash. Generative modeling for RNA splicing predictions and design. March 2025.
[25] Asif Khan, Alexander I. Cowen-
Antoine Grosnit, Derrick-Goke Goh-Xin Deik, Philippe A. Robert, Victor Greiff, Eva Smorodina, Puneet Rawat, Rahmad Akbar, Kamil Dreczkowski, Rasul Tutunov, Dany Bou-Ammar, Jun Wang, Amos Storkey, and Haitham Bou-Ammar. Toward real-world automated antibody design with combinatorial Bayesian optimization. Cell Reports Methods, 3(1), 2023.
[26] Jonas Mockus. The Bayesian approach to global optimization. In System Modeling and Optimization, pages 473-481. Springer, 1982.
[27] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming, 14:265-294, 1978.
[28] Natalie Maus, Kaiwen Wu, David Eriksson, and Jacob Gardner. Discovering many diverse solutions with Bayesian optimization. In Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 206 of PMLR, pages 1779-1798. JMLR, April 2023.
[29] Gustavo Malkomes, Bolong Cheng, Eric H Lee, and Mike Mccourt, Beyond the pareto efficient frontier: Constraint active search for multiobjective experimental design. In Proceedings of the International Conference on Machine Learning, volume 139 of PMLR, pages 7423-7434 JMLR, 2021.
[30] Uriel Feige. A threshold of Inn n for approximating set cover. Journal of the ACM, 45(4): 634-652, July 1998.
[31] James Wilson, Frank Hutter, and Marc Deisenroth. Maximizing acquisition functions for Bayesian optimization. In Advances in Neural Information Processing Systems, pages 9884- 9895. Curran Associates, Inc., 2018.
[32] Jialei Wang, Scott C. Clark, Eric Liu, and Peter I. Frazier. Parallel Bayesian global optimization of expensive functions. Operations Research, 1850)11855 2020.
[33] Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, Andrew Gordon Wilson, and Eytan Bakshy. BoTorch: A framework for efficient Monte-Carlo
12

---

Bayesian optimization. In Advances in Neural Information Processing Systems, volume 33, pages 21524-215333 Curran Associates, Inc., 2020.
[34] Jacob Gardner, Geoff Pleiss, Kilian Q. Weinberger, David Bindel, and Andrew G. Wilson. GPyTorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration. In Advances in Neural Information Processing Systems, volume 31, pages 7576-7586. Curran Associates, Inc., 2018.
[35] Martin Jankowiak, Geoff Pleiss, and Jacob R. Gardner. Parametric Gaussian process regressors. In Proceedings of the International Conference Machine Learning, volume 119 of PMLR, pages 4702-4712. JMLR, 2020.
[36] Diederik P. Kingma and Max Welling. Auto-encoding variational Bayes. In Proceedings of the International Conference on Learning Representations, Banff, AB, Canada, April 2014.
[37] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In Proceedings of the International Conference Machine Learning, volume 32 of PMLR, pages 1278-1286. JMLR, June 2014.
[38] Stephan Eissman, Daniel Levy, Rui Shu, Stefan Bartzsch, and Stefano Ermon. Bayesian optimization and attribute adjustment. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2018.
[39] Pascal Notin, José Miguel Hrrnández-Lobateee and Yarin Gal. Improving black-box optimization in vae latent space using decoder uncertainty. In Advances in Neural Information Processing Systems, volume 34, pages 802 814. Curran Associates, Inc., 2021.
[40] Seunghun Lee, Jaewon Chu, Sihyeon Kim, Juyeon Ko, and Hyunwoo Kim. Advancing
bayesian optimization via learning correlated latent space. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors. Advances in Neural Information Processing Systems, volume 36, pages 48906-48917, Curran Associates, Inc., 2023.
[41] Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In Proceedings of the International Conference on Machine Learning, volume 70 of PMLR, pages 1945-1954. PMLR, 2017.
[42] Xiaoyu Lu, Javier Gonzalez, Zhenwen Dai, and Neil Lawrence. Structured variationally auto- encoded optimization. In Proceedings of the International Conference on Machine Learning. volume 80 of PMLR, pages 3267-3275. JMLR, 10-15 Jul 2018.
[43] Austin Tripp, Erik A. Daxberger, and José Miguel Hernández-Lobatt Sample-efficient opti- mization in the latent space of deep generative models via weighted retraining. In Advances in Neural Information Processing Systems 33. Curran Associates, Inc., 2020.
[44] Antoine Grosnit, Rasul Tutunov, Alexandre Max Maraval, Ryan-Rhys Griffiths, Alexan- der Imani Cowen-Rivers, Lin Yang, Lin Zhu, Wenlong Lyu, Zhitang Chen, Jun Wang, Jan Peters, and Haitham Bou-Ammar. High-dimensional Bayesian optimisation with variational autoencoders and deep metric learning. arXiv Preprint Wtwi:::20660330000 arXiv, 2021.
[45] Eero Siivola, Andrei Paleyes, Javier González, and Aki Vehtari. Good practices for Bayesian optimization of high dimensional structured spaces. Applied Al Letters, 2(2):e24, 2021.
[46] Wengong Jin, Regina Barzilay, and Tommi S. Jaakkola. Junction tree variational autoencoder for molecular graph generation. Proceedings of the International Conference on Machine Learning, volume 80, pages
JMLR, 2018
[47] Natalie Maus, Haydn Jones, Juston Moore, Matt J. Kusner, John Bradshaw, and Jacob Gard- ner. Local latent space Bayesian optimization over structured inputs. In Advances in Neural Information Processing Systems, volume 35, pages 34505-345 18, December 2022.
[48] Seunghun Lee, Jinyoung Park, Jaewon Chu, Minseo Yoon, and Hyunwoo J. Kim. Latent Bayesian optimization via autoregressive normalizing flows. In Proceedings of the International Conference on Learning Representations, 2025.
[49] Beata Kowalska- Krochmal and Ruth Dudek- Wicher. The minimum inhibitory concentration of antibiotics: Methods, interpretation, clinical relevance. Pathogens, 10(2):165, 2021.
[50] Fangping Wan, Marcelo D. T. Torres, Jacqueline Peng, and Cesar de la Fuente-Nunez. Deep- learning-enabled antibiotic discovery through molecular de-extinction. Nature Biomedical Engineering, 8(7):854-87 17 Jul 2024.
13

---

[51] David Eriksson and Matthias Poloczek.
Scalable constrained Bayesian optimization. In Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 130 of PMLR, pages 730-738. JMLR, 2021.
[52] Nathan Brown, Marco Fiscato, Marwin H.S. Segler, and Alain C. Vaucher. Guacamol: Bench- marking models for de novo molecular design. Journal of Chemical Information and Modeling, 59(3): 108, Mar 2019.
[53] Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanic Jegelka. Batched large-scale Bayesian optimization in high-dimensional spaces. In Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 84 of PMLR, pages 745-754. JMLR, March 2018.
[54] Erik Reinhard, Greg Ward, Sumanta Pattanaik, and Paul Debevec. High Dynamic Range Imaging: Acquisition, Display, and image-Based Lighting (The Morgan Kaufmann Series in Computer Graphics). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005.
[55] Chaofeng Chen and Jiadi Mo. IQA-PyTorch: Pytorch toolbox for image quality assessment. [Online]. Available: pettps://githue www httm//caooffgggeg wwwpeeeeee//AAAPOOoooe
2022.
[56] Paul E. Debevec and Jitendra Malik. Recovering high dynamic range radiance maps from photographs. In Proceedings of the Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '97, page 369-378. ACM Press/Addison- Wesley Publishing Co., 1997.
[57] Martin Čadík. Perceptually Based Image Quality Assessment and Image Transformations. Ph.D. thesis, Department of Computer Science and Engineering. Faculty of Electrical Engineering, cz/
Czech Technical University in Prague, January 2008. URL httpttttt///aikk...pp. diss/|
[58] David Arthur and Sergei Vassilvitskii. K-Means++: The advantages of careful seeding. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA '07, page 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics.
[59] S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2): 129-137, 1982.
[60] Eric Hans Lee, Bolong Cheng, and Michael McCourt. Achieving diversity in objective space for sample-efficient search of multiobjective optimization problems. In Proceedings of the Winter Simulation Conference, WSC '22 page 3146-3153 IEEE, 2023.
[61] Angela Cesaro, Marcelo Der Torossian Torres, and Cesar de la Fuente-Nunez. Methods for the design and characterization of peptide antibiotics. In Leslie M. Hicks, editor, Antimicrobial Peptides, volume 663 of Methods in Enzymology, chapter 13, pages 303-326. Academic Press, 2022.
[62] David Weininger. SMILES, a chemical language and information system. 1. introduction to methodology and encoding rules. Journal of Chemical Information and Computer Sciences, 28 (1):31-36, 1988.
[63] Carl Hvarfner, Erik Orm Hellsten, and Luigi Nardi. Vanilla bayesian optimization performs great in high dimensions. In Proceedings of the International Conference Machine Learning, volume 235 of PMLR, pages 20793-20811 17 JMLR, 2024.
[64] Miguel González-Dugue Hauberg, and Wouter Boomsma. A survey and benchmark of high-dimensional bayesian optimization of discrete sequences. In Advances in Neural Information Processing Systems (Track on Database and Benchmarks), volume 37, pages Inc., 2024.
Richard Michael, Simon Bartels, Yevgen Zainchkovskyy, Søren
Curran Associates,
[65] Fabio Urbina, Filippa Lentzos, Cédric Invernizzi, and Sean Ekins. Dual use of artificial- intelligence- powneeed drug discovery. Nature Machine Intelligence, 4:189-191, 2020.
[66] Andrew G Wilson, Zhiting Hu, Russ R Salakhutdinov, and Eric P Xing. Stochastic variational deep kernel learning. In Advances in Neural Information Processing Systems, volume 29, pages 2586-2594. Curran Associates, Inc., 2016.
[67] Xinwei Jiang, Junbin Gao, Xiaobo Liu, Zhihua Cai, Dongmei Zhang, and Yuanxing Liu. Shared deep kernel learning for dimensionality reduction. In Advances in Knowledge Discovery and Data Mining, pages 297-308, Cham, 2018. Springer International Publishing.
14

---

[68] Massimiliano Patacchiola, Jack Tumnr, Elliot J. Crowley, Michael O' Boyle, and Amos J Storkey. Bayesian meta-learning for the few-shot setting via deep kernels. In Advances in Neural Information Processing Systems, volume 33, pages (6108-16111 18. Curran Associates, Inc., 2020.
[69] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Representations, 2015.
[70] Hossein Talebi and Peyman Milanfar. NIMA: Neural image assessment. IEEE Transactions on Image Processing, 27(8):3998 3998-4119 2018.
[71] Naila Murray, Luca Marchesotti, and Florent Perronnin. AVA: A large-scale database for aesthetic visual analysis. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2012.
[72] Chaofeng Chen, Jiadi Mo, Jingwen Hou, Haoning Wu, Liang Liao, Wenxiu Sun, Qiong Yan, and Weisi Lin. TOPIQ: A top-down approach from semantics distortions for image quality assessment. IEEE Transactions on Image Processing, 33:2404-2418 2024.
[73] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaezmarczyk, and Jenia Jitsev. LAION-SB: An open large-scale dataset for training next generation image-text models. In Advances in Neural Information Processing Systems, volume 35, pages 25278-25294, Curran Associates, Inc., 2022.
[74] Shaolin Su, Qingsen Yan, Yu Zhu, Cheng Zhang, Xin Ge, Jinqiu Sun, and Yanning Zhang. Blindly assess image quality in the wild guided by self-adaptive hyper network. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 2020.
[75] S. Alireza Golestaneh, Saba Dadsetan, and Kris M. Kitani. No-reference image quality assess- ment via transformers, relative ranking, and self-consistency. In Proceedings of the IEEF/CVF Winter Conference on Applications of Computer Vision, pages 1220-1230, January 2022.
[76] Weixia Zhang, Guangtao Zhai, Ying Wei, Xiaokang Yang, and Kede Ma. Blind image quality assessment via dasion-language correspondence: A multitask learning perspective. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14071-14081, June 2023.
[77] Dani Lischinski, Zeev Farbman, Matt Uyttendaele, and Richard Szeliski. Interactive local adjustment of tonal values. ACM Transactions Graphics, 25(3):646-653, July 2006.
[78] Yuki Koyama, Issei Sato, Daisuke Sakamoto, and Takeo Igarashi. Sequential line search for efficient visual design optimization by crowds. ACM Transations on Graphics, 36(4), July 2017.
[79] Yuki Koyama, Issei Sato, and Masataka Goto. Sequential gallery for interactive visual design optimization. ACM Transactions on Graphics, 39(4), August 2020.
[80] Jack Tumblin and Greg Turk. LCIS: A boundary hierarchy for detail-preserving contrast reduction. In Proceedings of the Annual Conference on Computer Graphics and Interactive Techniques, page 83-90, USA, 1999, ACM Press//Adison-WVee
Publishing Co.
[81] Frédo Durand and Julie Dorsey. Fast bilateral filtering for the display of higg-dyynaiccrannge images. In Proceedings of the 29th Annual Conference Computer Graphics and Interactive Techniques, SIGGRAPH '02, page 257-266, New York, NY, USA, 2002. Association for Computing Machinery.
[82] Yuanzhen Li, Lavanya Sharan, and Edward H. Adelson. Compressing and companding high dynamic range images with subband architectures. ACM Transactions on Graphics, 24(3): 836-844, July 2005.
[83] Kaiming He, Jian Sun, and Xiaoou Tang. Guided image filtering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(6))1397-1400) 2013.
[84] Zeev Farbman, Raanan Fattal, Dani Lischinski, and Richard Szeliski. bldee-preservig decom- positions for multi-scale tone and detail manipulation. ACM Transactions on Graphics, 27(3):
1-10, August 2008
[85] G. Bradski. The OpenCV Library. Dr. Dobb's Journal of Software Tools, 2000.
15

---

Contents
Introduction
2
Background
Multi-Objective Coverage Bayesian Optimization
3.1
Coverage Optimization
3.2
Multi-Objective Coverage Bayesian Optimization (MOCOBO)
3.2.1
Candidate Selection with Expected Coverage Improvement (ECI)
3.2.2
Greedy Approximation of Best Observed Covering Set
3.2.3
Extending ECI to the Batch Acquisition Setting (q-ECI)
3.2.4
MOCOBO with Trust Regions
4
Experiments
Tasks
Optimization Results
4.3
Ablation study
10
5
Related Works
10
6
Conclusions
10
Obtaining In Vitro Minimal Inhibitory Concentration (MIC) Data
18
Additional Results
19
B.I
Additional Covering Sets of Solutions Found by MOCUBO
19
2
Additional Ablation Studies
20
B.2.1
Ablation: Settings Where All Objectives are Highly Conflicting
20
B.2.2
Ablation: MOCOBD Covering Set Size
22
B.2.3
Ablation: MOCOBO Surrogate Model Quality
23
B.2.4
Ablation: MOCOBD Batch Size
23
B.2.5
Ablation: MOCOBO Trust Regions
23
B.2.6
Ablation: MOCOBO Expected Coverage Improvement (ECI) Acquisition Function
25
B.3
Execution Time of Greedy Approximation Algorithm
25
Batch Acquisition with Expected Coverage Improvement (ECI)
27
Limitations and Future Works
28
Broader Impact
28
Compute Resources
29
Additional Implementation Details
30
16

---

G.1
Trust Region Hyperparameters
30
G.2
Surrogate Model
30
Initialization Data
30
G.4
Diversity Constraints and Associated Hyperparameters for the ROBOT Baseline
31
Additional Task Details
32
HDR Image Tone Mapping
32
H.2 Peptide Design
33
Proof that Finding the Best Observed Covering Set is NP-hard
34
Approximation Proof for Greedy Algorithm
36
17

---

A Obtaining In Vitro Minimal Inhibitory Concentration (MIC) Data
In this section, we provide the methods used to produce all vitro minimal inhibitory concentration (MIC) values reported in this paper.
Peptide synthesis. All peptides were synthesized by solid-phase peptide synthesis using the Fmoc strategy and purchased from AAPPTèc.
Bacterial strains and growth conditions used in the experiments. The following Gram- -egatteea bacteria were used in our study: Acinetobacter baumannii ATCC 19606, Escherichia coli ATCC 11775, coli AIC221 (E. coli MG1635 phnE2::FRT) E. coli AIC222 (E. coli MG1655 pmrA53 phn Fb:: (colistin resistant)). Klebsiella pneumoniae ATCC I 13883, Pseudomonas aeruginosa PAO1, and P. aeruginosa PA14. The following Gram-positive bacteria were also used in our study: Staphylococcus aureus ATCC 12600, S. aureus ATCC BAA-1556 imethicillin-reiistanl strain), Enetrococcuss faecalis ATCC 700802 (vancomycin- resssssttn strain) and E. faecium ATCC 700221 (vancomyyin--rsiistaat strain). Bacteria (LB) or Pseudomonas isolation agar plates (P. aeruginosa strains) and incubated overnight at 37 C. After the incubation period, single colony were incubated overnight (16 h) at 37 OC. The following day, an inoculum was prepared by diluting the overnight cultures 1 100 in mL of the respective media and incubating them at 37 C until bacteria reached logarithmic phase (OD = 0.3 0.5).
grown from frozen stocks and plated
Auria-Bertani
transferred to 6 mL of LB medium, and cultures
Antibacterial assays. The in vitro antimicrobial activity of the peptides was assessed by using the broth microdilution assay [6T] Minimal inhibitory concentration (MIC) values of the peptides were determined with an initial inoculum of x 10 cells mL in LB in microtiter 96-well flat-bottom transparent plates. Aqueous solutions the peptides were added to the plate at concentrations ranging from 0.0625 64 pmolT.-1 The lowest concentration of peptide that inhibited 100 percent of the visible growth bacteria was established as the MIC value in an experiment of 20 of exposure 37 C. The optical density of the plates was measured 600 nm using spectrophotometer. All assays were done as three biological replicates.
18

---

B Additional Results
In this section, we provide all additional empirical results not included in the main text.
B.1 Additional Covering Sets of Solutions Found by MOCOBO
In this section, we provide additional examples of covering sets of solutions found by MOCOBO for various tasks from Section 1
0.25
8.0
2.0
8.0
60
5.0
2.0
4.0
2.0
16.0
5.0
1.0
2.0
64.0
TF2
1.0
5.0
0.5
0:25
8.0
2.0
4.0
16.0
TF3
4.0
64.0
7.0
64.
TF2-4
2.0
64.0
2.0
66.0
8.0
64.0
32.0
TC2-2
64.0
TCP
2.0
37.0
8.0
16.0
IC2-4
(1
82
84
85
86
80
(+)
810 (+) (+)
Figure B.1: vitro results for the two best "template free" (TF1, TF2) and two best "template constrained" (TC1, TC2) runs of MOCOBO for the peptide design task. Here, "best" means runs that achieved highest coverage scores according to the APEX 1.1 model. Each row is single peptide found by run of MOCOBO. Row TFi-j indicates template free run i, peptide j. Similarly, TCi-j indicates template constrained run peptide j. Columns are the vitro MICs for each target pathogenic bacteria B1, B11 listed in Table H. (-) and (+) indicate Gram negative and Gram positive respectively. TFI and TCI correspond to the single runs MOCOBO shown in Table and
Table B. respectively. Methods used to obtain in vitro MICs are provided in Appendix A
provide In vitro results for the two best "template free" and two best "template constrained" runs of MOCOBO for the peptide design task. Here, "best" means runs that achieved highest coverage scores according to the APEX 1.1 model. [igure/B.Iprovidee provides in vitro MICs for each of the K = peptides found by each of these runs of MOCOBO, for each of the 11 target pathogenic bacteria. Methods used obtain in vitro MICs provided in Appendix
In Figure B.1
Table B.1: The best set of K = peptide sequences found by one run of MOCOBO for the "template free" peptide design task described in Section 4.1 For each of the four sequences, we provide the MIC according to the APEX model for each of the I1 target pathogenic bacteria. The target pathogenic bacteria B1, ...... B1l are listed in Table H.3 (-) and (+) indicate Gram negative and Gram positive
pathogenic bacteria respectively. The best/lowest MIC achieved for each pathogenic bacteria is in
bold each column. See row "TC1" in Figure 3 and Figure B.1 for vitro MICs for this set of
K 4 peptides.
Peptide Amnino Acid Sequenee
B1(-)
B2(-)
B3(-)
B8(-)
B5(-)
BB(-)
B3(-)
B8(+)
B9(+)
B10X+)
B11(+)
KXLK11BLLFK
18.594
17.067
4.278
5.352
13.460
50.442
24.543
456.831
431.276
441.292
20.305
VATROL ATN..ST
20.358
14.644
10.477
65.172
97.4114
59.195
19.846
33.459
237 697.667
7.708
4,589
11.444
19.150
75.588
BAT7TAFFRI T
225.260
346.589
56.583
58.32 253
45% 963
475.616
538 552
293.852
338.447
34.230
22.153
In Table B. we provide an example of a covering set of peptides found by MOCOBO for the "template constrained variation of the peptide design task.
In Figure B.2 we provide the original HDR image (leftmost panel), and K images produced
using the K 4 solutions found by single run of MOCOBO for the church image variation of the
19

---

image tone mapping task. An analogous result for the desk image variation of the image tone mapping task can be found the main text in Figure 6 A notable apparent limitation of the existing IAA/IQA metrics we used for the image tone mapping tasks is that they all favored monochromatic images for both the church and desk images. As such, the conemmppeed images obtained appear less colorful than their hand-tuned counterparts reported in prior work.
we provide an example of covering set of K molecules found by MOCOBO for the molecule design task. As mentioned in Section 4 these three molecules effectively cover the 7 = objectives, as evidenced by the presence of all 7 target elements in one of the designed by MOCOBO.
In Table B.2
molecules
In Figure B.3 and Figure B.4 provide examples of covering set of trajectories found for the = and 7 12 variations of the rover task respectively. In each figure, a panel is shown for each of the T obstacles courses, with obstacles colored in red. The required starting point for the rover is a green point in the bottom left of each panel. The "goal" end point that the rover aims to reach without hitting any obstacles is the red point in the top right of each panel. Each panel also shows the best among the K trajectories found by a run of MOCOBO for navigating each obstacle course. An analogous plot for the T = 4 variation of the rover optimization task is provided in the main text in Figure 5
Figure B.2: (Leftmost Panel) Image obtained by naively compressing the dynamic range of the HDR church image in the "image tone mapping" task. (Four Rightmost Panels) Images obtained by applying tone mapping to the church image using the best covering set of 4 solutions found by single run of MOCOBO.
Table B.2: The best set of 3 molecules found by one run of MOCOBO for the Ranolazine MPO multiple element molecule design task described in Section 4.1 For each of the three molecules, we provide the objective value obtained for each of the T 6 objectives. The best/highest objective value is in bold in each column. Each objective aims to add different target element to Ranolazine (F, CI, Br, Se, S, and P). The T target elements are bold and colored blue in the SMILES string representation of each molecule.
62
Molecule (SMILES String)
Obj (odd F)
Obj (add CI)
Obj 3 (add Br)
Obj 4 (add Se)
Obj 5 (add S)
Obj 6 (add P)
-c0 000000 (Se) oc (--0)))1------000-0000
0.8038
0.8038
0,8038
0.9108
0.8038
0.8038
0.8043
0.9114
0.8043
0.8043
0.9114
0.8043
apwecpptteee-ppprooeeeooooooooe -00-020F00000000000coo0 (C) [NHL]] ooP
0.8028
B.2
Additional Ablation Studies
In this section, we provide additional ablation studies not included in the main text.
B.2.1 Ablation: Settings Where All Objectives are Highly Conflicting
MOCOBO designed for cases where some, but not all, of the objectives are highly conflicting, and
this is the case for all of the tasks considered in Section 4 The conflicting pairs of the objectives prevent single solution from optimizing all objectives well. The fact that not all pairs objectives completely conflicting, is the reason why it is possible cover all T objectives with small set of
20

---

Figure B.3: The panels depict the 8 obstacle courses that the rover must navigate for the T
variation of the rover task, with obstacles colored in red. The required starting point for the rover is green point in the bottom left each panel. The "goal" end point that the rover aims to reach without hitting any obstacles is the red point in the top right of each panel. The line in each panel shows the best trajectory for navigating the obstacle course from among the K = 2 covering trajectories found by single of MOCOBO. The first trajectory in the covering set is shown in magenta and successfully navigates obstacle courses 5, 6, 7, and 8 (Bottom Row). The second is shown in blue and 4 (Top Row)
and successfully navigates obstacle courses
Figure B.4: The 12 panels depict the 12 obstacle courses that the rover must navigate for the T = 12 variation of the rover task, with obstacles colored in red. The required starting point for the rover is green point in the bottom left of each panel. The "goal" end point that the rover aims to reach without hitting any obstacles the point in the top right of each panel. The line in each panel shows the best trajectory for navigating each obstacle course from among the K = 4 covering trajectories found by a run of MOCOBO. The first trajectory in the covering set is shown magenta and successfully navigates obstacle courses 6 and 7 (Middle Row: Center Left and Center Right Panels). The second is shown in blue and successfully navigates obstacle courses 2 and 8 (Top Row: Center Left Panel, Middle Row: Rightmost Panel). The third is shown in purple and successfully navigates obstacle courses 4, 5, and 11 (Top Row: Rightmost Panel, Middle Row: Leftmost Panel, and Bottom Row: Center Right Panel). The fourth trajectory shown in orange and successfully navigates obstacle courses 1, 9, 10, and 12 (Top Row: Leftmost Panel and Center Right Panel, Bottom Row: Leftmost, Center Left, and Rightmost Panels).
solutions. all pairs of the objectives are highly conflicting, there by definition no possible set of K < T solutions such that all objectives are well optimized. In this case, it's best to use T individually optimized solutions if your goal to find at least one solution that well optimizes each objective. However, it is still interesting to consider the performance of MOCOBO in the setting of
21

---

T objectives that are pairwise highly conflicting, To investigate this, we construct a new variation of the multi-objective rover task described in Section 4.1] We design T=3 obstacle courses such that it is impossible for the rover to take any single path that avoids all obstacles in any pair of the obstacle courses. This results in T=3 objectives that are pairwise highly conflicting. We then run 20 replications of MOCOBO on this problem with K=2, asking MOCOBO to design K=2 solutions that cover the T=3 pairwise highly confictiigg objectives. For this task, MOCOBO got an average coverage score of 2.932, while T individually optimized solutions got average coverage score of 12.899. It is unsurprising that T individually optimized solutions achieved better coverage here since all three objectives are pairwise highly conflicting, However, this result demonstrates that MOCOBO is able to design sets of K=2 solutions that still achieve fairly high coverage scores.
Figure B.5: The three panels depict the T=3 obstacle courses that the rover must navigate for the ablation variation of the rover task where all T=3 objectives pairwise highly conflicting. Obstacles are colored red. The three obstacle courses are designed such that any single path that successfully avoids all obstacles in one obstacle course, must hit some obstacles in both of the other obstacle courses. The required starting point for the rover is a green point in the bottom left of each panel. The "goal" end point that the rover aims to reach without hitting any obstacles is the red point in the top right of each panel. The line in each panel shows the best trajectory for navigating the obstacle course from among the K=2 covering trajectories found by a single run of MOCOBO. The first trajectory in the covering set is shown in magenta and is the best trajectory for navigating obstacle courses 2 and 3 (Middle Panel and Rightmost Panels). The second is shown in blue and successfully navigates obstacle course (Leftmost Panel).
Figure B.5 provides diagram of the T=3 pairwise highly conflicting obstacle courses, and example of one of the covering sets K=2 trajectories found by a single run of MOCOBO. One optimized trajectory (shown in blue) is designed by MOCOBO such that it specializes to navigate the first obstacle course, navigating it without hitting any obstacles (Leftmost Panel). The other optimized trajectory (shown in magenta) is designed by MOCOBO such that it avoids all obstacles in the third obstacle course (Rightmost Panel), while also minimizing total amount of impact with the obstacles in the second obstacle course (Middle Panel). Since it is by-design impossible to avoid all obstacles in all T=3 obstacle courses with only K=2 solutions, Figure B.5 demonstrates that MOCOBO was able to successfully balance trade-offss among the objectives, designing a set of K=2 solutions that minimized the total amount of obstacle impact across the three obstacle courses.
B.2.2 Ablation: MOCOBO Covering Set Size
In this section, we ablate K, the user-specified hyperparameter that dictates of size of the set that MOCOBO designs to cover the objectives. For this ablation, we use the rover task with obstacle courses as defined in Section 4.1] Note that in the main text we provide results comparing MOCOBO to bascline methods using K = 2 for this task. In Figure B.6 we provide results from running MOCOBO with each of K 1, 3, and 4. With the ability to more than solutions to cover the T objectives (K = 3, 4), the optimization problem becomes easier and MOCOBO is able to converge more quickly. However, the loss in optimization efficiency inured by using the smaller covering set size of K = 2, rather than a higher value of K, is marginal, highlighting MOCOBD's ability of efficiency design smaller sets of high performing solutions.
With only one solution (K 1), by definition not possible to cover all T = 4 objectives since several pairs of the obstacle courses are specifically designed to be completely conflicting (no one trajectory can successfully avoid the obstacles in all T obstacle courses). MOCOBO with K = therefore obtains substantially lower final coverage score.
22

---

Rover with Four Obstacle Courses
MOCOBO K-]
MOCOBO K-2
Mean Best Covcrage Score Found
MOCOBO K-3
MOCOBO K-4
Individually Optimized Solutions
0
-10
20000
40000
60000
80000
Number of Oracle Calls
Figure B.6: Ablating the hyperparameter K used to run MOCOBO on the rover task with T obstacle courses (see task definition in Section 4.1)
B.2.3 Ablation: MOCOBO Surrogate Model Quality
In this section, we ablate the quality of the surrogate model used by MOCOBO, To run MOCOBO with surrogate models of varying quality, vary the MOCOBO hyperparameter m: the number of inducing points used to define the approximate Gaussian process (GP) surrogate model (see surrogate model details in Appendix G)). It well established in the literature that approximate GP models perform better with larger number of inducing points, as the inducing point approximation used by the model is improved. However, there is inherent trade-off as the computational cost of training the model increases with the number of inducing points. In practice, we therefore often to select the smallest possible value of maximize computational efficiency) such that we don't incur any significant performance degradation.
For this ablation, Figure B.7 we provide results from running MOCOBO with each of m 4, 16, 64, 256, 1024, and 4096. In all other experiments in this paper, choice of m = 1024 as results demonstrate that no significant performance improvement is gained by using the larger value of 4096, and that performance starts degrade with smaller values of m < 256.
the rover task with T = 4 obstacle courses defined in Section 4.1 In
1024. Results in Figure B.7 support
B.2.4 Ablation: MOCOBO Batch Size
In this section, we ablate the MOCOBO hyperparameter q, the acquisition batch size which dictates how many points are selected for evaluation from each trust region each iteration of MOCOBO. For this ablation, we use the rover task with = 4 obstacle courses as defined Section 4.1 In Figure B.& we provide results from rumning MOCOBO with each of 1, 5, 10, 20, and 40. In all other experiments in this paper, we use 20. Results in Figure B.8 demonstrate the robustness MOCOBO changes in q, there is little no significant change in the performance of MOCOBO with different the values of
B.2.5 Ablation: MOCOBO Trust Regions
In this section, we ablate the use of trust regions in MOCOBO. For this ablation, we use the rover task with 7 = 4 obstacle courses defined in Section 4.1 To ablate the use of trust regions, we compare to MOCOBO (as defined in Section 3 with trust regions), to running MOCOBO without trust regions. Results in Figure B.9 demonstrate that MOCOBO performs significantly better with the use of trust regions. This result confirms that trust regions significantly improve performance in the high-dimensional settings consider.
23

---

Rover with Four Obstacle Courses
17.5
MOCOBO -4
MOCOBO --- 166
Mcan Best Coverage Score Found
MOCOBO 66
15.0
MOCOBO 256
MOCOBO -0024
MOCOBO 14-9
Individually Optimized Solutions
2.5
0.0
10000
Number of Oracle
Figure B.7: Ablating the MOCOBO hyperparameter m (the number of inducing points used by the surrogate model) on the rover task with T = 4 obstacle courses (see task definition in Section 4.1 Lower values of correspond to lower surrogate model quality.
Rover with Four Obstacle Courses
17.5
q
q
Mcan Best Coverage Score Found
15.0
q 5
1-10
MOCOBO
12.5
MOCOBO
Individually Optimized Solutions
10.0
7.5
5.0
0
20000
40000
60000
S0000
Number of Oracle Calls
Figure B.8: Ablating the MOCOBD hyperparameter (the number of points selected for evaluation during the acquisition step on each iteration) on the rover task with T 4 obstacle courses (see task definition in Section 4.1
Why trust regions has been well-established in the Bayesian optimization (BO) literature that standard BO (without trust regions other high-dimensional adaptations) performs poorly in high dimensions. Eriksson et [2 introduced trust regions principled way to improve performance of high-dimensinn sonh-dmmensionll BO. Since then, trust regions have become standard tool for any high-dimensional BO task. Since all of the tasks we consider in this paper are high-dimensional, this precisely why we adopt trust regions. We note that recent work has proposed alternative approaches to improve high-dimensional BO without trust regions (e.g., 63
However, there remain concerns about the applicability of these approaches structured domains (c.g., [64)).

---

Rover with Four Obstacle Courses
MOCOBO (Ouss
MOCOBO-EIT
Mcan Best Covcrage Soore Found
MOCOBO Withour Trust Regions
Individually Optimized Solutions
0
-10
-30
-50
20000
40000
60000
80000
Number of Oracle Calls
Figure B.9: Ablation comparing MOCOBO as defined in Section 3 to two variations each removing a different component of MOCOBO. To ablate the use of trust regions in MOCOBO, compare MOCOBO without trust regions. To ablate our proposed ECI acquisition function, we additionally compare to MOCOBO-EIT variation of MOCOBO where select candidates in acquisition by taking the maximum of standard EI for each of the 7' objectives individually (EIT), rather than using ECI as described in Section 3 We provide optimization results for MOCOBO and these variations on the rover task obstacle courses (see task definition in Section 4.1b
with T
B.2.6 Ablation: MOCOBO Expected Coverage Improvement (ECT) Acquisition Function
In this section, we ablate our proposed expected coverage improvement (ECI) acquisition function. For this ablation, we use the rover task with T obstacle courses as defined in Section 4.1 To ablate the use of ECI, we compare to MOCOBO (as defined in Section with ECI), to MOCOBO EIT: a variation of MOCOBO where on each iteration, we instead select points for evaluation by taking the maximum of the standard expected improvement (EI) acquisition function for each of the T objectives individually. Results in Figure demoonssteeete that MOCOBO performs significantly better with our proposed ECI acquisition function, demonstrating the importance of ECI to the performance of MOCOBO. Additionally, MOCOBO-EIT still performed fairly well, outperforming all other baseline methods considered in the paper (e.g., all baselines in Figure 2}. This highlights the importance of other aspects MOCOBO.
B.3 Execution Time of Greedy Approximation Algorithm
In Table B.3 we provide an empirical evaluation of the average wall-clock runtime of Algorithm 1 with different values of N (the number of data points), (the covering set size), and T (the number of objectives). We provide average run times with N = 20, 200, 2000, 20000, 200000, and 2000000 for each combination of K and 7' that we ran MOCOBO on in Section 4 To improve the speed of Algorithm [ in experiments, we compute the inner for loop (lines 5-6 Algorithm I parallel. This involves simply computing the marginal coverage of adding all N data points at once in parallel, and then updating A with the point that achieved maximum marginal converge improvement. Parallel computation of the marginal coverage improvement of the N points is straightforward to implement using PoTch. In Table B.3] the "Runtime" column gives the average runtime of Algorithm with this parallel computation of the of the inner for loop, and the "Runtime No Parallelization" column gives the average runtime without the parallel computation. Notice that as N grows large, this parallel computation becomes essential to achieve the reasonably fast run times of Algorithm I needed to run MOCOBO. Average run times reported Table B.3 are computed by running Algorithm) T on NVIDIA RTX A5000 GPU and averaging over 10 runs.
25

---

Table B.3: Average wall-clock runtime of Algorithm for different values N (the number of data points), K (the covering set size), and T (the number of objectives). The "Runtime" column gives the average runtime of Algorithm [ with parallel computation of the of the marginal coverage of adding the N data points (parallel computation of lines 5-6). The "Runtime No Parallelization" column gives the average runtime of Algorithm| [ without this parallelization of the inner for loop. Average run times are computed by running Algorithm on NVIDIA RTX A5000 GPU and averaging over 10 runs. Standard errors over the 10 runs are also provided.
T Runtime No Parsllelization (scondds)
Rostine (scconds))
70
0.00005 0.00385
0.00804
C.000995
280
0.0230 - 0.00091
0.00801 0.00022
2000
0,194 0,00388
0,00850 6.00781
20000
2,0523 0 0.0250
0,00852:1 6.00780
200000
201.845 0.04466
I100872 0.001736
2000000
195.740 0.114
0,00825
20
OUDHISON
0,000IG C.U0SH
200
0,02222
0,00185
0,00894 0.00S0S
2000
0.00794
200000
0.08664 0.00789
200000
2000000
0.0:600
0.00821
4,503
200000
0.10178
2000000
0.00772
20
0.000772
2800
0.314 0.00055
0.00897
00817
20000
2,912 0.00418
0,00872
0.00785
200000
28. 732 0.0156
D 0.00862
DIFTS
2000000
312 525 1: 203
0,00085 00790
20
0.00765 0,003TO
0,00880 DIPIG
200
2000
0,412 0.80252
BLOGEST & BUTTI
20000
3,917 0.80461
B,00882 & 00189
280000
38 0032 0.042
B,00880 + 00P91
2100000
380 272 + 588
DLOTIGG 0.00SORI
20
11
OLD6772 0.00577
D.008155 + DUSSS
200
11
0.0-22 =: 0,00085
0.00655 1 00775
2000
11
0.387 0. 0.00082
0.00551 2 00S37
20000
11
4.155 0.007/56
0.00867 + 00792
200000
11
41 800 0,0005
0,00880 1 0.00TTT
2000000
11
381 315 0.199
0.0114 1 0.0080
Algorithm I could also be made more efficient by pruning the points in D3 with zero marginal coverage improvement after each outer-loop, since these points will continue have zero marginal coverage improvement on subsequent loops. future work, we plan to explore this and any other tricks that might allow us to further improve the efficiency of Algorithm [
Efficiency of Algorithm 1
26

---

C Batch Acquisition with Expected Coverage Improvement (ECT)
In batch acquisition, we select a batch of q > candidates for evaluation. In Equation 7
define q-ECI, a natural extension of the ECI acquisition function defined in Equation (5) to the batch acquisition setting. q-ECI gives the expected improvement the coverage score after simultaneously
observing the batch of points X = (x........ X² When using batch acquisition, we aim to select batch of points that maximize q-ECI.
We will first discuss how one would estimate q-ECI using a Monte Carlo (MC) approximation. To select batch of candidates X. we sample m batches of points B = {B B2, Bm Here B; batch of q sampled points B, [b.1...... bjg}- For each batch B,, we sample realization
Y; = ff........ Jzy from the GP surrogate model posterior. We leverage these samples to compute an MC approximation to the q-ECI of each By:
q-CI(B,) max(0, max ((D)).((())))))))))) -(S))))))))) r=1p000
(8)
the approximation the coverage score of the new best covering set we choose to evaluate candidate bjr. assuming the candidate point will have the sampled objective values Yjr- We would like to select and evaluate the batch of candidates B, with the largest q-CI.
Here, c(S (i,(,, (x))) ))))))
Evaluating q-CI for a single candidate batch requires evaluations of cSS ( evaluation of ((b,,,
Each
requires call to Algorithm 1 to first construct S (b,.(((;...,,>>>)
Thus, batch acquisition with a full MC approximation q-ECI requires O x m)) calls of Algorithm Assuming sufficiently large to achieve reliable MC approximation, this can become expensive for large batch sizes We therefore propose a faster approximation of batch ECI for practical use with large q-
Instead of sampling m batches of candidates, we sample m individual data points P {P1, P2...., pm For each sampled point Рy. we sample a realization ý, = (p)), (P) the sampled realizations y, to compute an approximate coverage im- provement (P) as defined in Equation (6) for each point Pj. To obtain a batch of candidates, then greedily select the points Pj E P with the q largest expected coverage improvements, Note that this strategy does not involve sequential optimization of the points, as the batch of q points is selected simultaneously the points with the top-q expected coverage improvements.
As in Section 3.2. I
27

---

D Limitations and Future Works
Choosing K. A primary limitation of MOCOBO is that the choice of the hyperparameter K (the covering set size) may not always be straightforward. For example, as we mention in Section 4 it may require domain knowledge to choose K < T that is large enough that achieving good coverage is possible despite multiple conflicting objectives. In many practical applications, we prefer the smallest possible set size K such that good coverage can still be achieved. explore methods for simultaneously optimizing both the solutions in the covering set, and the size of the covering set, balancing the trade-off between minimizing the number of solutions needed and maximizing overall coverage.
future work, we plan to
Unsupervised generative model pre-training for structured domains. We note that applying MOCOBO to structured domains requires pre-trained generative model, such Variational Au- toencoder (VAE), to embed the discrete input space into a continuous latent space where MOCOBO can be directly applied. Training such generative models typically demands significant computa- tional resources and a large corpus of unlabeled data, which may not always available in new domains. For the two structured tasks considered in this aaper-molccule and peptide design- we leverage publicly available pre-trained VAEs from prior work. In contrast, MOCOBO does not require generative model for continuous input spaces, where optimization is performed directly in the original domain. This distinction highlights a key practical limitation: deploying MOCOBO in new structured domains would necessitate pre-training new generative model, which may be barrier in resource-constraincl settings.
Exploring lazy greedy evaluation approaches to improve computational efficiency. Another av- enue for future work is improving the computational efficiency of Algorithm by using a lazy greedy evaluation strategy. Commonly employed in submodular maximization, lazy greedy approaches maintain a priority queue of marginal gains and only recompute them when necessary, avoiding redundant evaluations and reducing total computational cost.
Threshold-based coverage. The coverage optimization problem we consider in this paper provides principled way to pose the goal of finding small set of К solutions such that each of the T objectives is optimized as much as possible by at least one solution in the set. This captures the setting we care about, for example, discovering K antibiotics such that each pathogen is targeted as effectively possible, not just adequately. In contrast, threshold- based coverage constitutes fundamentally different problem: it assumes that we know, a priori, threshold value for each objective beyond which we do not care to improve performance further. This setting is not aligned with the domains we focus on this paper where better objective values are always desirable and thresholds are typically unknown unhelpful. However, threshold-based coverage is a meaningful formulation for many other domains, such as drug toxicity screening, where desired minimum performance thresholds are known ahead of time. To address such domains, we plan to explore this alternative problem setting of threshold-basee coverage optimization in future work.
E
Broader Impact
This research includes applications in molecule and peptide design. While Al-driven biological design holds great promise for benefiting society, it crucial to acknowledge its dual-use potential. Specifically, Al techniques designed for drug discovery could be misused to create harmful biological agents [65]
Our goal is to accelerate drug development by identifying promising candidates, but it is imperative that experts maintain oversight, that all potential therapeutics undergo thorough testing and clinical trials, and that strict regulatory frameworks governing drug development and approval are followed.
28

---

Compute Resources
In this section, we provide all details about the compute resources used to produce all results in this paper.
Table F.1:
Setup of internal cluster used to run experiments.
Type
Specifications
System Topology
20 nodes with 2 sockets each with 24 logical threads (total 48 threads)
Processor
1 Intel Xeon Silver 4310, 2.1 GHz (maximum 3.3 GHz) per socket
Cache
1.1 MiB L.1, 30 MiB L.2, and 36 MiB L.3
Memory
250 GiB RAM
Accelerator
NVIDIA RTX A5000 per node, 2 GHZ, 24GB RAM
Compute specifications (type and memory). We use GPU works to run all experiments and produce all empirical results provided in this paper. A single GPU was used per run of each method compared on each task. Each each run uses approximately 12-18 GB of the GPU memory. Most experiments executed on internal cluster of NVIDIA RTX A5000 GPUs (see internal cluster compute details in Table (.T). We also used cloud compute resources for two weeks to complete additional replications of some experiments. We used total of eight RTX 4090 GPU workers from runpod. io, each with approximately 24 GB of GPU memory.
Execution time. For the relatively inexpensive rover task, each optimization run takes approxi- mately day of execution time. For all other tasks considered, each optimization run takes approx- imately 3 days of execution time. To create all coverage optimization plots, ran all methods compared 20 times each. Completing all of the runs needed to produce all of the results in this paper required roughly 64000 total GPU hours.
Compute resources for preliminary experiments. Preliminary experiments refer to the initial experiments for e.g. method development that are not included results in the paper. All preliminary experiments were run on our internal cluster of NVIDIA RTX A5000 GPUs (see internal cluster compute details in Table M We spent approximately 2000 hours of GPU time preliminary experiments.
29

---

G Additional Implementation Details
In this section, provide additional implementation details for MOCOBO. We also refer readers
the MOCOBO codebase for the full-extent implementation details and experimental setup needed to reproduce results provided (ttideddhttts... bttt:p://github.b.. com /atalaaaaallaa wtwp///aaaaaaa/mmooommmoo
G.1 Trust Region Hyperparameters
For all trust region methods, the trust region hyperparameters are set to the TuRBO defaults used by Eriksson al. 21
G.2 Surrogate Model
Since the tasks considered in this paper are challenging, high-dimensional tasks requiring large number of function evaluations, we use approximate Gaussian process (GP) surrogate models. In particular,
Parametric Gaussian Process Regressor (PPGPR) [35] surrogate models with constant mean, standard RBF kernel, and 1024 inducing points. Additionally, we use a deep kernel (several fully connected layers between the search space and the GP kernel) [66]. We use two fully connected layers with D nodes each, where D is the dimensionality of the search space.
We use the same PPGPR model(s) with the same configuration for MOCOBO, TuRBO, LOL-BO, and ROBOT. For MOCOBO, model the T-dimensional output space, we use T PPGPR models, one to approximate each objective fi....: Sr. To allow information sharing between the models, we use shared deep kernel (the T PPGPR models share the same two-layer deep kernel)
Unlike the other methods compared, MORBO was designed for use with an exact GP model rather than an approximate GP surrogate model. For fair comparison, we therefore run MORBO with exact GP using all default hyperparameters and the official codebase provided by Daulton et al. [14]
We train the PPGPR surrogate model(s) on data collected during optimization using the Adam optimizer [69] with a learning rate of 0.001 and a mini-batch size of 256. On each step of optimization, update the model on collected data until we stop making progress (loss stops decreasing for 3 consecutive epochs), or exceed 30 epochs. Since we collect a large amount of data for each optimization (e.g., many 2e6 data points in single run for the "template constrained" peptide design task), we avoid updating the model on all data collected at once. On each step of optimization, update the current surrogate model only points. This subset is constructed from the data that has obtained the highest objective values so far, along with the most recent batch of data collected. By always updating on the most recent batch of data collected, we ensure that the surrogate model is conditioned on every data point collected at some point during the optimization run.
subset of 1000 of the collected data
G.3 Initialization Data
In this section, we provide details regarding the data used to initialize all optimization runs for all
tasks in Section 4
To initialize optimization for the molecule design task, we take a random subset 10000 molecules from the standardized unlabeled dataset of 1.27M molecules from the Guacamol benchmark software
[52]. We generate labels for these 10000 molecules once, and then use the labeled data to initialize optimization for all methods compared.
To initialize optimization for the peptide design tasks, we generate a set of 20000 peptide sequences by making random edits (insertions, deletions, and mutations) to the 10 template peptide sequences Table H.4 We generate labels for these 20000 peptides once, and then use the labeled data to initialize optimization for all methods compared.
For all other tasks, we initialize optimization with 2000 points sampled uniformly at random from the search space.
30

---

G.4 Diversity Constraints and Associated Hyperparameters for the ROBOT Baseline
M solutions, requiring that the solutions have minimum pairwise diversity according to the user specified diversity function ó. Since Maus al. [28] also consider rover and molecule design tasks, we use the same diversity function d and diversity threshold used by Maus et al. (28) for these two tasks. For the peptide design tasks, we define á to be the edit distance between peptide sequences, and use a diversity threshold of
For single objective, ROBOT seeks a diverse
edits. For the image optimization task, since there is no obvious semantically meaningful measure of diversity between two sets of input parameters, solutions, and use
define ó to the Euclidean distance between 1.45, the approximate average Euclidean distance between randomly selected pair of points in the search space.
31

---

H
Additional Task Details
In this section we provide additional details for the chosen set of tasks provide results for in Section
H.1 HDR Image Tone Mapping
Table H.I: pyiqa metric ID strings used identify the T 7 target image quality metrics used for image tone mapping. Each metric a no-reference image aesthetic (IAA) or quality (IQA) assessment metric obtained from the pyiqa library [55].
Objective ID
Pyiqa Metric ID
Reference
1
nima
70
2
nima-vgg16-ayy
70
71
3
topiq-iaa-res50
72
4
laion-aes
73
5
hyperiqa
74
6
tres
75
7
liqe
76
In Table H.1 we list the names of the 7 image quality metrics used for the image tone mapping tasks described in Section
Target metries. The target image quality (Image Quality Assessment, IQA) and aesthetic (Image Aesthetic Assessment, IAA) metrics are organized in Table H..T where all except nima are IA metrics, while nima is IQA metric. For detailed information about each metric and their corresponding datasets, please refer to their original references.
Benchmark images. We use two benchmark images. The first is the "Stanford Memorial Church" image obtained from hittps://wee hwtp:/wwwwwww.ww...pppp htwp:/debbeeec.o//RReeeeeeee haam/Reeearcc/HDR//UUP by courtesy of Paul E, Debevec [56]. The second is the "desk lamp" image obtained from https: //cpsi:///aakk.. cadik. ctt.ca......etteeeeeeeeee cz/ tmo/ by courtesy of Martin Čadík (57). Because commonly used metrics are only correlated with subjective image quality, prior work on tuning parameters for these and related benchmarks has been done by trial and eтror and human-in -n-the-loop type schemes 777. including preferential BO-based approaches 78 799
Imaging pipeline. We consider tone mapping pipeline consisting of multi-layer detail decom- position [20 using the guided filter by He et al. 83 (3 detail layers and base layer), followed by gamma correction [54] Section 2.9], resulting in /3-dimensional optimization problem. The complete image processing pipeline is very similar to the classic approach proposed by Tumblin and Turk [80], where the main difference is that, similarly to Farbman al. [84), we replace the diffusion smoothing filter with more recent edge-preserving detail smoothing filter, the guided filter, by He al. [83]. First, given an HDR image in the RGB color space I (T,, Te, Ib)), where 7, the red channel, 1, is the blue channel, and Lg is the green channel, we compute the luminance according to
A 0. 2989, + 0.587I, 0.114I,
(The constants were taken from the code of Farbman et al. 84) The luminance image L is then logarithmically compressed and then decomposed into three detail layers and one base layer by applying the guided filter three times. each with different radius parameter F; and smoothing parameter e; for = 1.....3. 3. Then, we amplify or attenuate each channel with a corresponding 1, ...... for the detail and Obase for the base layers. The image is then reconstructed by adding all the layers, including the colors. Following Tumblin and Turk [80], we also apply a gain, Icolor, the color channels. Finally, the resulting image applied an overall gain Jout and then gamma-corrected [54] Section 2.9] with an exponent of 1 1/y. The parameters for this pipeline are organized Table H.2 The implementation uses OpenCV [85], particular, the guided filter implementation in the extended image processing (ximgproc) submodule.
gain coefficient Idetall,
32

---

Table H.2: pyiqa metric ID strings used identify the T target image quality metrics used for the image tone mapping task.
Parameter
Description
Domain
radius of the guided filter for generating the ith detailed layer
(3..... 32]
6/
of the guided filter for generating the ith detailed layer
0.01, 10]
I
Gain of the ith detail layer
0,
Ghose
Gain of the ith detail layer
0,
Jcolor
Gain of the color layer
0.5, 1.5
Jout
Gain of tone-mane cone-mapped output
0.2, 2.0)
Gamma correction inverse exponent
[1, 5]
Optimization problem setup. For optimization, we map the parameters
x (r1, 72, r3, C1 62 63. Idetail,1 Idetail. Idetail,3 Ibase Icolor: Sout 7)
to the unit hypercube [0. 1] In particular, the mapped values on the unit interval [0, 1] linearly interpolate the domain of each parameter shown Table For the radius parameters r1, 72: P3- which are categorical, we naively quantize the domain by rounding the output of the interpolation to the nearest integer.
H.2 Peptide Design
Table H.3:
Names of the T 11 target bacteria used for the peptide design task. The first seven
bacteria are Gram negative (IDs B1-B7) and the last four (IDs B8-B11) are Gram positive.
B1 Objective ID
Target Pathogenic Bacteria
baumannii ATCC 19606
coli ATCC 11775
coli AIC221
E. coli AIC222-CRE
K. pneumoniae ATCC 13883
B6
P. aeruginosa PAO1
B7
P. aeruginosa PA14
B8
S. aureus ATCC 12600
B9
S. aureus ATCC BAA-1556-
B10
E. faecalis ATCC 200802-VRE
B11
E. faecium ATCC 700221-VRE
Table H.4: Template amino acid sequences used for the "template constrained" peptide design task.
Template Amino Acid Sequenecs
BACIHAARSTAALRRRRUEPVVVOOO.....
KTLKITRULF
XRKRGLXLAAALLLLIIEEE
STYKKLSTTPPTTLTTRR SETTPPPTTTTRTPPPXXKPTP PKVKFFK
AVARMLVRYYOCLKKKKYY
RILVRYVQGI EEKRVVVVPVVGGGPPATTI
CVLLPSQLPAVVA
CHLLIHLIGKATEO
ROKUEGILPP
HNTTINTIRI.SSSKKT
specifies the T = 11 target bacteria used for the peptide design task from Section The first seven bacteria are Gram negative bacteria (Objective IDs B1-B7) and the last four (Objective IDs B8-B11) are Gram positive. Table H.4 gives the 10 template amino acid sequences used for the "template constrained" variation of the peptide design task from Section
Table H.3
33

---

I Proof that Finding the Best Observed Covering Set is NP-hard
In this section, we prove Theorem 3.1 that finding Sh, is NP-Hard.
Proof. We prove Theorem 3.1 by reduction from the well-known Maximum Coverage Problem
(MCP), which is NP-Hard.
Definition 1.1 (Maximum Coverage Problem (MCP). In the Maximum Coverage Problem, given:
A universe U = {ei, , Cm of m elements.
A collection of n subsets S = {A1, A An), where A; S U.
An integer K, the number of subsets we can select.
The objective is find collection of K subsets 8 C S such that the total number of elements covered, UAES A, is maximized.
Proposition 1.2 (MCP is NP-Hard). The Maximum Coverage Problem NP-Haard.
Reduction from MCP to Finding Sb. We reduce instance of MCP to the problem of finding ST, as follows:
1. Let the universe U fei, c Cm) correspond to the objectives f1.2...., T) in the optimal covering set problem, i.e., set T m.
2. Let each subset A, E S correspond to point E D..
3. Define each objective f:: + 1). and set fx;) = if subset A; contains element et, and fx(x;) otherwise. Intuitively, this means that each point x; "covers" objective ft if it achieves value 1 under that objective. While the design points are not literal subsets, they induce coverage behavior that mirrors the structure of MCP through their binary function values across the objectives.
4. Under this mapping, coverage score c(S) = Et= maxxes f((x) is the total number of objectives "covered" (i.e., the number of objectives for which at least one of the selected points has value 1). It follows that the goal of the Maximum Coverage Problem (selecting "subsets" to maximize coverage) corresponds exactly to selecting K points X; E D, to maximize the coverage score e(S).
Correctness of the Reduction: The reduction ensures that:
Each subset A, E S is encoded by design point x; D, via its binary-valued outputs over the objectives.
Each element e mapped to objective ft. and is considered "covered" if some selected point S satisfies f((x) 1. In particular, if subset A; covers/contains element ez, then fx(x,) 1; otherwise, fx(x,)
The MCP objective (maximize number of covered elements) is equivalent to maximizing the coverage score e(S), which counts how many objectives covered by the selected set S.
Thus, solving the optimal covering set problem is equivalent solving MCP.
Implications: Since MCP is NP-Hard (Proposition) 1.2 and we have reduced MCP to the problem of finding Sb, in polynomial time, it follows that finding 5%, is also NP-Hard.
34

---

Proof significance We do not claim the above proof of Theorem 3.1 as a novel contribution of this work, as follows straightforwardly from the fact that the well-known Maximum Coverage Problem is NP-hard. Note that proving Theorem 3.1 would also follow straightforwardly from the work of Ding et al. [7] who demonstrate that the coverage optimization problem generalizes k-means clustering. Rather than providing additional novel contribution, the above proof of Theorem 3.1 serves to justify our use of a greedy approximation algorithm (Algorithm to approximate Sb, on each iteration of MOCOBO.
35

---

J Approximation Proof for Greedy Algorithm
In this section, we prove Theorem 3.2 that Algorithm is (1 -)-Approximation.
Definition J.1 (Coverage Score). The coverage score of set Ds. denoted c(S), is defined as:
c(
Σ max f((x),
XES
where ft(x) is the observed value of objective at point x.
Definition J.2 (Optimal Covering Set). Let Sb. S D. denote the optimal covering set of size K:
SD. arg max c(S). SCD.,1$==K
Its coverage score given by c(Sb,).
Definition J.3 (Contribution of Objective Function Se to Coverage Score), Given covering set S Da, we denote the contribution of objective St E {11, 12....,,r to the overall coverage score c(S) (S()) where
9e(S) = max f((x). XES
It follows that from Theorem
J3 that:
T ((S) Σ (s)
Lemma J.4 (Monotonicity). The coverage score c(S) as defined in Theorem J.1 is monotone, i.e., for any S C S' C Da, we have:
c(S) S c(S').
Proof. Adding more points can only increase or maintain the maximum values of fo for each objective t, since for each objective:
Se(S") max (s) ()) 2 (S)).
Hence, c(S) is monotone.
Lemma J.5 (Submodularity). The coverage score c(S) as defined in Theorem J.1 is submodular iee. for any C C D. and any x* D, S', we have:
((SU(x))) c(S) 2 U(x
Proof. The marginal improvement of adding x to is:
(SU(F')) c(S) = Σ (S((U 9c(S))
max
(e(
Σ [f((xt) - (S) f((x)) (S)
otherwise
Likewise, for S' this is:
Σ fi(xt)- - ((") fi(x*) ((("))
((S'(((1)))(ss)
otherwise
Now, noting that for each term
9: (:()) max g. S)) 2 (c()),
36

---

we know then that fi(x") g5( I f((x)) (e(),, and further that fo(x*) > (r(" implies that
fi(x*) > (e)).. Taken together, these imply that:
00 f -i((")) f(xx) > g((5))
T f - -g((5) f((x*) > gr(S)
otherwise
0
otherwise
and therefore:
U (x*}) 2
-(s)
c(S").
Lemma J.6 (Greedy Achieves a (1- Approxxmmmtioon for Monotone Submodular Functions).
For any monotone submodular function, the greedy submodular optimization strategy provides (1 ) approxxmmaainn
Proof. This is well-known result about monotone submodular functions shown, for example, by Nemhauser et al. 27
Proof. Proof of Theorem 3.2 From Theorem J.4 and Theorem J.4 know that c(S) monotone submodular.
and
Since c(S) is monotone submodular, and Algorithm approximates Ab. using greedy submodular optimization, it follows from Theorem J.6 that Algorthm achieves:
c(Ab)) 2 1 c(S.)).
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All stated claims are backed-up with results in Section and the stated focus/scope of the paper accurately reflects what is discussed throughout the rest of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix for discussion of limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer: [Yes]
Justification: All theoretical claims can be found in Section 3.2.2 and full proofs of each claim are provided in Section 3.2.2 Appendix far as we are aware, each proof is complete and correct.
All sets of assumptions
I and Appendix g As
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide detailed explanation of how our method works in Section and all additional required details to reproduce results in Section f and Appendix G Additionally, we provide link public GitHub repository containing the source code used to method and produce results provided this paper. This GitHub repository contains orga- nized code that will allow any reader to MOCOBO on all tasks in this paper. Additionally, the README in the repository provides detailed instructions to make setting up the proper environment and running the code easy for users.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
39

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide link to a public GitHub repository containing the source code used to method and produce results provided in this paper. This GitHub repository contains organized code that will allow any reader to run MOCOBO on all tasks this paper. Additionally, the README in the repository provides detailed instructions to make setting up the proper environment and running the code easy for users.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
poollc/guiies/// Cooeeuumisssioooooooo...oo Policiyyooo for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /nips.cc///p wwwpc//ccwcpcp.c..e.eee.
http://eeeuummiiiioooooooo.o for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All chosen hyper- pareeerrrsmetrrs and implementation details are stated in ssection 4] and Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
40

---

Justification: On all plots, we plot the mean taken over 20 random runs and include error bars show the standard error over the runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All compute details are provided Appendix F
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp:///rp....cp/aa/////aaaaaaaa www.lliieeEhhhcciieeelliiii
Answer: [Yes]
Justification: We have made adhere the NeurIPS Code of Ethics in all aspects of our research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
41

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See discussion of broader societal impacts in Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release new data models with potential societal concerns.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Creators of all assets used to produce all results in this paper are cited in Section All assets used are open source software or models.
Guidelines:
42

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce any new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The work does not involve any human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The work does not involve any living participants.
43

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This work does not use LLMs in any way.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy for what should or should not be described.
44


Reviews:
[{"review_id": "ciDeLdobtF", "reviewer": "Reviewer_wMNa", "summary": "The paper introduces a novel formulation for multi-objective optimization, aiming to select $K < T$ points that maximize the sum of the highest values across $T$ objectives, while only selecting $K$ points. To tackle this problem, the authors propose a greedy algorithm with a $(1 - 1/e)$ approximation guarantee. I did not verify the proofs in detail, but the theoretical analysis follow standard techniques. Empirically, the method performs well on the proposed metric, demonstrating its practical effectiveness.", "questions": "- Have you considered using a *lazy greedy* approach for maximizing the marginal gains? This technique is often used in submodular maximization to improve computational efficiency. Incorporating this could strengthen the practical side of the contribution since that typically speeds up the algorithm in practice quite a bit. \n\n- Are you doing 20k function evaluations? Are you training gps on that scale? I'm very confuse about this setup.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nI appreciate creative formulations that aim to address real-world challenges, and this paper makes a compelling case for the relevance of the proposed black-box optimization framework in domains like drug discovery and materials science. Demonstrating that the method provided tangible benefits in in vitro experiments is a strong and valuable contribution.\n\nAdditionally, the proposed formulation and method are reasonable and conceptually sound. My main concerns are a few aspects of the presentation, as well as the assumption that one must select $K < T$ points. While this constraint may be practical in scenarios such as manufacturing a limited number of designs — where fewer is better — the justification is not clearly articulated in the paper. I believe the authors could strengthen the paper by providing a more explicit rationale for this design choice.\n\n\n\n**Points to Improve**\n\n**Unclear Motivation:**. The paper would benefit from a clearer problem definition and better motivation. From the wording in the abstract to the example in Figure 1, I think the formulation selling point needs to improve. \n\n- I found the example in the introduction somewhat difficult to follow. Could you clarify the statement:\n\n> \"we may have T pathogens and aim to identify a set of K < T antibiotics such that at least one antibiotic can be used to treat each pathogen\" \n\nIt seems you may be suggesting that a single antibiotic could potentially treat all pathogens -- when using the “each pathogen” words. This is different than the example in Figure 1, in which it appears that the first square point does not contribute meaningfully to covering function $f_3$, while the second point might serve as an acceptable proxy for both $f_2$ and $f_3$. A revision on the abstract and in the introduction is critical to improve this paper.\n\nIn Line 67, Contribution 1 offers a better definition of the problem, though it still feels a bit imprecise. As I understand it, the goal is to identify suboptimal solutions that are “good enough” across multiple objectives — this idea should be precisely defined to avoid confusion. \n\n- The illustrative example in Figure 1 seems somewhat misleading. If I interpret it correctly, the same set of points (the square points) could be found by performing a local search over the Pareto frontier to maximize objective (2). Additionally, in a standard Pareto setting, one would typically select multiple points and the example implies that only one is selected, so the example might not accurately reflect the standard use of multi-objective methods.\n\n\n**Related Work**\n\n* Paper \\[1]: *\"Beyond the Pareto Efficient Frontier: Constraint Active Search for Multiobjective Experimental Design\"*\n  Gustavo Malkomes, Bolong Cheng, Eric H Lee, Mike McCourt. *Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7423–7434, 2021.*\n\nThis paper discusses a different type of coverage problem, but I believe it is still relevant to include in the related work section — particularly since it also proposes an *Expected Coverage Improvement* acquisition function. However, note that the concept of coverage in that paper refers to the **input space**, rather than the **objective space**, as in the current work.\n\nI also found this other recent work from the same authors that discuss a different formulation for the metric space:\n\n* Achieving Diversity in Objective Space for Sample-efficient Search of Multiobjective Optimization Problems.\nEric Hans Lee, Bolong Cheng, Michael McCourt\n\n**Minor Comments**\n\n* **Figure 2**: The x-axis is missing a label in both the figure and the caption.\n* **Line 2**: Consider clarifying what is meant by “a single set” in *\"seek a single Pareto-optimal set.\"* since a set would typically mean multiple points. \n* **Line 7**: Consider elaborating on what qualifies as “a good solution.”\n* **Line 48**: The phrase *“While it is very true”* is informal — consider rephrasing for a more academic tone.\n* **Line 70**:\n  Original: *“first work in the Bayesian optimization (BO) literature to consider the coverage optimization problem setting.”*\n  Suggested: *“first work to consider this problem setting,”*\n  since the formulation is distinct from standard Bayesian Optimization, and paper \\[1] also addresses a form of “coverage” — albeit with a different definition.\n* **Line 209**:\n  *“adopt a more approximate batching”* → consider revising to *“adopt a different approximation scheme.”*\n* **Line 70**: Typo — *“?.”* → replace with *“?”*", "was_revised": true, "final_justification": "My main concern with this paper was the clarity of the presentation, but I think the authors can improve after all the suggestions. I appreciate the detail answer about the motivation and I'm bumping my score.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. Below we address all points raised:\n# Justification for K < T\nThank you for highlighting this point. We agree that the constraint K < T deserves more discussion. This constraint reflects many real-world scenarios with strict evaluation or deployment budgets, such as: 1) In drug discovery, where only a small number of compounds can be synthesized or tested, 2) In materials design, where the cost of fabricating each candidate is high, 3) In robotics or system design, where one might only be able to deploy a handful of control policies, etc. In settings such as these, K < T encodes a practical resource constraint: the user cannot afford to optimize each objective independently and must instead find a small set of solutions with broad utility. We will expand our discussion of the problem setting to clearly articulate this point and further justify the K<T constraint with concrete examples. \n# Problem Motivation and Presentation\nWe appreciate the reviewer’s request for greater clarity in the problem framing and example. We note that our problem definition is defined in precise, mathematical terms in the Method’s section (see equation 2). However, we agree with the reviewer that the explanation of the problem setting in the abstract and introduction (text preceding this precise mathematical definition) can be improved to more clearly define the problem in words. For the camera ready version, we will revise the abstract and introduction to more clearly define the goal: namely, to identify a set of K < T solutions that collectively provide strong coverage over all T objectives, such that each objective is well-optimized by at least one solution in the set. This differs from the standard Pareto setting, which typically emphasizes trade-offs at the level of individual solutions, rather than coverage across objectives via a set. \n\nWe will revise all relevant text to provide a clearer explanation of the problem definition and to clarify that we are not assuming a single solution can cover all objectives equally well. Rather, the goal is to find a small set of solutions such that each objective is well-optimized by at least one member of the set. For example, as you rightly point out, the original wording of the statement “we may have T pathogens and aim to identify a set of K < T antibiotics such that at least one antibiotic can be used to treat each pathogen” is potentially misleading. To more accurately convey our intent, we plan to replace this with a revised version such as:\n\n“In drug discovery, we may be faced with the challenge of designing antibiotics for T different pathogens. Developing T individual antibiotics (a separate antibiotic specifically designed to treat each pathogen) is not ideal, as synthesizing and testing each antibiotic is highly expensive (a smaller number of antibiotics is ideal). However, we still want to design more than one antibiotic, as a single antibiotic is highly unlikely to be able to treat all T pathogens effectively. We therefore aim to identify a smaller set of K < T antibiotics, such that each pathogen can be effectively treated by at least one of the K selected antibiotics. The goal is not for every antibiotic to treat every pathogen, but for the set of K antibiotics as a whole to provide ‘coverage’ of the T pathogens, such that if we encounter any one of the T pathogens, we will be able to treat it with at least one of the antibiotics in the optimized set.”\n# Clarification of Figure 1\nWe appreciate the feedback that the illustrative example in Figure 1 could be clearer. You are absolutely right that in this simple 2D example with K = 2 and T = 3, the two square points that yield good coverage could indeed be recovered by searching over the Pareto frontier for a pair that maximizes the coverage score. However, in the real-world tasks we consider, where the objectives are high-dimensional, black-box, and highly non-convex, identifying such a set of K coverage-maximizing points is non-trivial and likely cannot be accomplished by naïvely sampling the Pareto frontier. \n\nAdditionally, as you note, many standard multi-objective methods do output multiple Pareto-optimal points. However, these points are typically meant to serve as alternative trade-off options, from which a practitioner selects one solution to apply, depending on their preferences. The methods do not aim to maximize the combined utility of the full set; instead, they ensure that each individual point lies on the Pareto frontier. In contrast, our formulation explicitly seeks a set of solutions that work together: the goal is to maximize aggregate coverage across all objectives, not to offer mutually exclusive alternatives.\n\nThe star point in Figure 1 is meant to illustrate the limitations of single-solution approaches, namely, that no individual solution can provide high performance across all objectives when trade-offs are extreme. This motivates the need for multiple jointly selected solutions, each covering different subsets of objectives.\n\nWe will revise the text to clarify this distinction, explicitly explain how coverage optimization differs from Pareto-based approaches (even those that return multiple points), and emphasize that Figure 1 is a simplified schematic meant to illustrate intuition, not a literal depiction of how Pareto methods operate.\n# Related Work\nThank you for pointing us to Malkomes et al. (ICML 2021) [1] and the related diversity-in-objective-space paper. We agree that while their definition of “coverage” differs from ours (input vs. objective space), their use of an Expected Coverage Improvement (ECI) acquisition function is relevant and valuable to acknowledge. We will update the Related Work section to include discussion of these papers. \n# Minor Comments\nThank you for the detailed comments on writing and presentation. These comments will be very helpful in polishing the camera-ready version.  \n# Questions\n### Q1: Have you considered using a lazy greedy approach to accelerate selection? \nWhile we did not use a lazy greedy approach in this version of MOCOBO, we plan to explore this in future work. Thank you for the suggestion! \n### Q2: Are you really doing 20k function evaluations? Are you training GPs on that scale? \nTo clarify: while some of our large-scale tasks involve collecting up to tens or even hundreds of thousands of data points (e.g., the peptide design task), we do not train exact Gaussian processes on the full dataset, as this would be computationally infeasible.\n\nInstead, as described in Appendix A.7.2, we use PPGPR, a scalable approximate GP surrogate model. This setup allows us to handle large datasets efficiently while maintaining strong predictive performance. Additionally, at each step of optimization, we update the surrogate using only a small subset of 1000 data points: this includes the most recent batch of observations and the highest-performing points collected so far. This ensures that the model remains up to date without retraining on the full history on each step. Full details can be found in Appendix A.7.2."}, {"review_id": "fLfO0pGIKR", "reviewer": "Reviewer_UDrb", "summary": "&nbsp;\n\nThe authors introduce Multi-Objective Coverage Bayesian Optimization (MOCOBO) a framework for computing the optimal \"covering set\" of K points for $T > K$ black-box objective functions in a multi-objective optimization setting. The problem setting appears to be practically grounded although further references on e.g. the coverage optimization problem as related to drug design would help strengthen the case. The MOCOBO algorithm appears to be principled with practical approximations developed to account for the NP-Hard problem of finding the optimal covering set. The empirical results are strong and I, in particular, commend the authors for validating their approach with in vitro experiments which is rare to see at ML conferences such as NeurIPS. Furthermore, the writing and presentation of the paper are excellent. Overall I think the paper is an excellent contribution to NeurIPS yet I am somewhat disappointed to see that the authors have not released their code with the submission yielding concerns about the reproduciblity of the results. If this concern can be addressed, I will be willing to upgrade my score to Accept/Strong Accept.\n\n&nbsp;", "questions": "&nbsp;\n\n1. Could the authors describe how the reward is computed in Figure 1? Are the three curves intended to be different objective functions defined in the same space? If so, is the Pareto frontier given by the black dotted line accurate?\n\n2. The authors introduce the expected coverage improvement (ECI) acquisition function. Given that the logEI acquisition function of [12] improves the numerical stability of EI do the authors think there is potential for a logEI variant to be integrated in future work?\n\n3. In Section A.9 of the appendix, the authors define the elements of the universe U to be the T objectives ${f_1, ..., f_T}$, the collection of n subsets comprise elements $\\mathbf{x}_i$ which are no longer a subset of U as in the Maximum Coverage Problem. As such, it is not clear what point 3 means, specifically what does it mean for a subset $A_i$ to cover the objective? It might be worth elaborating on the assumed mapping between points in the design space $\\mathbf{x}_i$ and the objectives $f_t$ in relation to the MCP.\n\n4. In Section 4, when describing the baselines, the authors state that they computed the best covering set of K solutions found by each method with a run per objective. Given that the baselines (TuRBO, LOL-BO, and ROBOT) have been advantaged in some sense as the covering set is computed from T simpler single objective problems, I don't quite understand why MOCOBO still outperforms the baselines? It seems as though the optimization problem for the baselines is easier? On second thought I'm guessing my comment would be expected to be correct if K=T, but with K < T the comparison is less clear? On third thought, I can see that this is clarified in the section entitled \"T individually optimized solutions baseline\".\n\n5. For the rover task, in what practical settings would a rover be required to find a covering set of trajectories for different obstacle courses?\n\n&nbsp;", "limitations": "&nbsp;\n\n1. The practical limitations of the method are acknowledged by the authors, namely that it may be challenging to select an appropriate value of $K$ a priori. \n\n&nbsp;", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "&nbsp;\n\nThe paper presents a practical method for a relevant class of black-box multi-objective optimization problems. An important strength to highlight is that the algorithm was validated in in vitro experiments on peptide design which is rare to see in ML conferences. Specifically, I believe such experiments go a long way in highlighting the practical capabilities of the MOCOBO approach. Below I detail my major concern with the release of the code as well as some minor issues the authors may wish to consider.\n\n&nbsp;\n\n**__MAJOR POINTS__**\n\n&nbsp;\n\n1. The authors responded \"Yes\" when asked in the paper checklist whether they had released the data and code for the paper. However, they have not released either which raises concerns about the reproducibility of the work. As mentioned in the summary, if the authors can release their code I will have no hesitation in upgrading my score to Accept/Strong Accept.\n\n&nbsp;\n\n**__MINOR POINTS__**\n\n&nbsp;\n\n1. Abstract, typo, \"cover\" the T objectives.\n\n2. For clarity in the abstract, it may be worth elaborating briefly on what constitutes a \"good\" solution.\n\n3. Reference 4 was published at AAAI [1].\n\n4. Although, overall much attention to detail has been given to the references, there are just a couple of missing capitalizations such as \"bayesian\" and \"gaussian\".\n\n5. It would be great if the references appeared in numbered order when cited in the text.\n\n6. When introducing Bayesian optimisation in the opening line of the introduction, it would be worth citing the originating papers for the methodology [2,3] as discussed in [4].\n\n7. When citing Gomez-Bombarelli et al. chemical engineering is a bit of a misnomer for the molecule generation tasks considered. Chemical engineering is typically taken to mean the study of large scale chemical processes or chemical plants. I would suggest citing the paper under drug discovery since the QED and penalized logP metrics could loosely be interpreted as being related to drug discovery.\n\n8. Figure 1 is slightly unclear, could the authors describe how the reward is computed?\n\n9. In the introduction, when discussing the drug design example could the authors supply some references so that the interested reader may learn more about the problem?\n\n10. In terms of the related work on Bayesian optimization over structured search spaces it is worth mentioning the early works [5-8] as well as more recent efforts [9, 10]. In particular the authors of [10] use normalizing flows in place of a VAE which broadens the range of architectures for Bayesian optimization over structured inputs.\n\n11. In terms of the related work on Bayesian optimization over structured search spaces it would also be worth emphasizing that a VAE is not necessary to perform Bayesian optimization over molecular representations [11]. In [11], the authors introduce bespoke GP kernels for molecular representations and amino acid sequences. The VAE/normalizing flow approach, however, is required for situations in which you want to perform BO over an open-ended space by generating novel molecules. It would be worth making this distinction.\n\n12. Missing full stop at the end of Equation 1 of Equation 2.\n\n13. The notation in Equation 1 might be cleaner is simply \"k\" was kept under the max function. The definition in Section A.10 of the appendix is somewhat clearer for the reader because it involves abstracting the K points as a set.\n\n14. The design space $\\chi$ is not defined in Equation 2. This may be important for clarity seeing as all objectives are assumed to share the same design space and bounds.\n\n15. Missing full stop at the end of Equation 3. It is also considered poor style to begin a sentence with mathematical notation as in line 151.\n\n16. Missing full stop at the end of Equation 4.\n\n17. It would be worth clarifying Equation 5, for example what does CI mean? Coverage improvement? The coverage score of the dataset together with the (repeatedly) sampled point $\\mathbf{p}_j$ is taken by averaging the m samples at $\\mathbf{p}_j$ over all objectives?\n\n18. In Section 3.1 it would be worth stating whether or not K is some hyperparameter chosen before optimization.\n\n19. Typo, line 879, \"this by reduction\".\n\n20. Missing full stops in equations on lines 922 and 923.\n\n21. Missing full stop line 947.\n\n22. Missing full stop Equation 6.\n\n23. Line 721, typo, \"batch of candidates\".\n\n24. Missing full stop Equation 7.\n\n25. I understand that space was probably a limitation but it would be good to specify the number of random trials and how the errorbars were computed in the caption of Figure 2 (20 replicates with standard errors).\n\n26. Line 296, typo, \"Ranolaize\"?\n\n27. Line 357, typo, capitalization of HDR.\n\n28. Line 646, typo, capitalization of HDR.\n\n29. Line 671, typo, K<T.\n\n30. In Table A.2, SMILES should be capitalized in both the table and caption.\n\n31. Line 774, typo, \"done our\".\n\n32. Line 794, typo, double use of \"share\".\n\n33. The Adam optimizer should be cited given that it is used [13].\n\n34. Line 802, typo, \"in a single\".\n\n35. Line 805, typo, \"from the data\" rather than \"of the data\".\n\n36. There is an inconsistent comma delimiter for the numerical figures referenced e.g. 64000 GPU hours vs. 20,000 peptides.\n\n37. Line 829, typo, Euclidean should be capitalized.\n\n38. On line 838, what do the acronyms IQA and IAA stand for? I don't immediately see what the second A stands for. It seems to be \"assessment\"?\n\n&nbsp;\n\n**__REFERENCES__**\n\n&nbsp;\n\n[1] Belakaria, S., Deshwal, A., Jayakodi, N.K. and Doppa, J.R., 2020, April. [Uncertainty-aware search framework for multi-objective Bayesian optimization](https://ojs.aaai.org/index.php/AAAI/article/view/6561). In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 06, pp. 10044-10052).\n\n[2] H.J. Kushner (1962). [A Versatile Stochastic Model of a Function of Unknown and Time Varying Form. Journal of Mathematical Analysis and Applications](https://www.sciencedirect.com/science/article/pii/0022247X62900112) 5(1):150–167.\n\n[3] H.J. Kushner (1964). [A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise.](https://asmedigitalcollection.asme.org/fluidsengineering/article-abstract/86/1/97/392213/A-New-Method-of-Locating-the-Maximum-Point-of-an?redirectedFrom=fulltext) Journal of Basic Engineering 86(1):97–106.\n\n[4] Garnett, R., [Bayesian optimization](https://bayesoptbook.com/). Cambridge University Press. 2023.\n\n[5] Notin, P., Hernández-Lobato, J.M. and Gal, Y., 2021. [Improving black-box optimization in VAE latent space using decoder uncertainty](https://proceedings.neurips.cc/paper/2021/hash/06fe1c234519f6812fc4c1baae25d6af-Abstract.html). Advances in Neural Information Processing Systems, 34, pp.802-814.\n\n[6] Griffiths, R.R. and Hernández-Lobato, J.M., 2020. [Constrained Bayesian optimization for automatic chemical design using variational autoencoders](https://pubs.rsc.org/en/content/articlehtml/2019/sc/c9sc04026a). Chemical Science, 11(2), pp.577-586.\n\n[7] Kusner, M.J., Paige, B. and Hernández-Lobato, J.M., 2017, July. [Grammar variational autoencoder](https://proceedings.mlr.press/v70/kusner17a.html?ref=https://githubhelp.com). In International Conference on Machine Learning (pp. 1945-1954). PMLR.\n\n[8] Lu, X., Gonzalez, J., Dai, Z. and Lawrence, N.D., 2018, July. [Structured variationally auto-encoded optimization](https://proceedings.mlr.press/v80/lu18c.html). In International Conference on Machine Learning (pp. 3267-3275). PMLR.\n\n[9] Lee et al. [Latent Bayesian Optimization via Autoregressive Normalizing Flows](https://openreview.net/forum?id=ZCOwwRAaEl). ICLR 2025 (oral).\n\n[10] Lee, S., Chu, J., Kim, S., Ko, J. and Kim, H.J., 2023. [Advancing Bayesian optimization via learning correlated latent space](https://proceedings.neurips.cc/paper_files/paper/2023/hash/98e967164ae2f6811b975d686dece3eb-Abstract-Conference.html). Advances in Neural Information Processing Systems, 36, pp.48906-48917.\n\n[11] Griffiths, R.R., Klarner, L., Moss, H., Ravuri, A., Truong, S., Du, Y., Stanton, S., Tom, G., Rankovic, B., Jamasb, A. and Deshwal, A., 2023. [GAUCHE: a library for Gaussian processes in chemistry](https://proceedings.neurips.cc/paper_files/paper/2023/hash/f2b1b2e974fa5ea622dd87f22815f423-Abstract-Conference.html). Advances in Neural Information Processing Systems, 36, pp.76923-76946.\n\n[12] Ament, S., Daulton, S., Eriksson, D., Balandat, M. and Bakshy, E., 2023. [Unexpected improvements to expected improvement for Bayesian optimization](https://proceedings.neurips.cc/paper/2023/hash/419f72cbd568ad62183f8132a3605a2a-Abstract-Conference.html). Advances in Neural Information Processing Systems, 36, pp.20577-20612.\n\n[13] Kingma and Ba, [Adam: A method for Stochastic Optimization](https://arxiv.org/abs/1412.6980), ICLR 2015.\n\n&nbsp;", "was_revised": true, "final_justification": "&nbsp;\n\nI am maintaining my rating of borderline acceptance. Unfortunately, due to the rules of the NeurIPS conference this year, the authors were unable to provide their code during the rebuttal phase. If the authors had been allowed to provide their code my rating would be a strong accept. Nonetheless, I am happy to recommend acceptance overall.\n\n&nbsp;", "rebuttal": "We thank the reviewer for the thoughtful and encouraging feedback. We appreciate the recognition of MOCOBO’s practical relevance, principled design, strong empirical performance, and in vitro validation. We respond to each point below:\n# MAJOR POINT: Code Release and Reproducibility\nWe fully agree that releasing code is essential for reproducibility and for supporting the community. While the code was not public at submission time, we want to clarify that we have a complete GitHub repository that includes all code to reproduce all MOCOBO results on all tasks in the paper. We also recognize the importance of accessibility and usability. To that end, we’ve included a detailed README and environment setup to make it easy for others to run MOCOBO and apply it to new problems. We have invested significant effort in this because we care deeply about making our method practical and usable by the broader research and practitioner community.\n\nOur plan is to make this repository fully public upon paper acceptance, and we will include the link in the camera-ready version of the paper.\n\nOrdinarily, we would have liked to share an anonymous version of the repository during the review process so that reviewers could verify results without compromising anonymity. However, due to new NeurIPS rules this year, we are unfortunately not allowed to include links of any kind (even anonymized) in the author rebuttal. We appreciate your understanding and assure you that full code release is planned and prioritized.\n# MINOR POINTS\nThank you for your detailed proofreading suggestions, and in particular, for catching numerous typos, missing capitalizations, and formatting inconsistencies. These comments will be very helpful in polishing the camera-ready version. \n# QUESTIONS\n### Q1: How is the reward computed in Figure 1? \nYes, each curve represents an objective function over the same domain. The “reward” in this case is actually just the coverage score as defined in equation 1. For the single pareto optimal point (the star), the coverage score is just the sum over the three objective function values for that single point. For the covering set of K=2 points (the two black squares), this coverage score is the sum of the higher objective value obtained between the two points for each one of the three objective functions. We decided to use “reward” in Figure 1 rather than “coverage score” just because Figure 1 is discussed at the start of the paper before the “coverage score” is formally introduced. We do think that the “pareto frontier” given by the black dotted line is accurate in the sense that if we move along the x-axis in any direction away from this dotted line, all objective function values decrease, and if we move towards the black dotted line, all objective function values increase. When moving between any pair of x-axis points that are both along the dotted line, some objective functions increase while others decrease. To our knowledge, this defines the black dotted line as the pareto frontier for the three objective functions. Please let us know if that answers your question, we are happy to discuss this with you further. \n### Q2: Could a logEI version of ECI improve performance? \nIndeed using logEI has been shown to lead to substantial improvements in BO over using standard EI. It therefore worth investigating whether some version of logECI could be used instead of ECI to improve MOCOBO similarly. Thank you for the suggestion, this is an exciting direction for future work! \n### Q3: Clarify mapping between design points and objectives in relation to the MCP\nThank you for this insightful question. We agree that this portion of Appendix A9 would benefit from clearer explanation. \n\nTo clarify: in our reduction from the Maximum Coverage Problem (MCP), the connection between a subset $A_i$ and a design point $x_i \\in D_s$ is encoded via the binary function values $f_t(x_i) \\in$ {$0,1$}. That is, each objective $f_t$ plays the role of an element $e_t \\in U$, and each design point $x_i$ corresponds to a subset $A_i \\subseteq U$, where an element $e_t$ is “covered” by $A_i$ if and only if $f_t(x_i) = 1$.\n\nThis construction ensures that while the design points are not literally subsets, the induced binary coverage behavior matches the structure of the MCP instance. The design point $x_i$ “covers” objective $f_t$ if it achieves a value of 1 under that objective. Thus, the coverage score $c(S)$ counts how many objectives are covered (i.e., attain a value of 1 for at least one point in S), just like MCP counts how many elements are covered by a set of subsets.\n\nWe have revised Appendix A9 to more clearly explain this mapping, especially the fact that the “subsets” in our reduction are represented functionally via binary-valued objectives over points in $D_s$, rather than via explicit set membership.\n### Q4: Why does MOCOBO outperform baselines even when they solve easier sub-problems? \nIndeed, the baselines (TuRBO, LOL-BO, ROBOT) are run independently per objective, so they produce T solutions total (one solution specifically designed to optimize each of the T objectives). The best K-covering subset is then selected from those. While this does provide an advantage in terms of raw objective optimization, it lacks joint optimization: the T solutions are optimized independently, so coverage suffers when we select only the best K<T from among those T solutions. In contrast, MOCOBO jointly selects K diverse solutions to maximize total objective coverage. Indeed your comment would be correct if K=T, but when K<T, there is a need to design the small set of K solutions specifically such that some solutions in the set of K are good optimizers for more than one of the T objectives, in order to obtain a set of K<T solutions that together provide at least one good optimizer for each of the T objectives. Please let us know if this answers your question, we are happy to discuss this with you further. \n### Q5: Practical use case for the rover task?\nThe rover task is a well-established high-dimensional benchmark in BO. While our adaptation to multi-objective coverage is synthetic, it is intended as a proof-of-concept for settings where agents must be robust to diverse terrain types, e.g., autonomous vehicles navigating multiple environments. \nThank you! \nWe thank the reviewer again for their detailed, constructive feedback. We are excited to make our code public and are grateful for your thoughtful review."}, {"review_id": "aDv7K8XUnm", "reviewer": "Reviewer_SYMT", "summary": "The paper proposes MOCOBO, a Bayesian optimization (BO) method for coverage optimization. MOCOBO finds a small set of solutions where each objective is well-addressed by at least one solution. The work critiques traditional Pareto-front approaches for failing in extreme trade-off scenarios (e.g., drug discovery) and combines a novel Expected Coverage Improvement (ECI) acquisition function with trust-region BO. Experiments show MOCOBO matches or nears the performance of individually optimizing all objectives, outperforming adapted baselines.", "questions": "See also the weaknesses section above.\n- Can the authors validate ECI's contribution compared to standard EI or entropy-based methods? Does it provide better acquisition behavior than those standard alternatives?\n- Can the authors comment on the wall-clock time of the greedy cover construction vs. baselines such as MORBO or TurBO? \n- CluSO is the true competitor of MOCOBO, as the other methods (TuRBO, MORBO, ROBOT) are not specifically designed for coverage, making the comparison unfair. However, more emphasis on comparison against CluSO could have been provided. Why does CluSO underperform (poor scalability, bad hyperparameters)?\n- Are the trust regions necessary for MOCOBO? Or is MOCOBO just TuRBO with a coverage objective?", "limitations": "Yes, limitations, mainly the design choice of K, are discussed in Appendix A4. However, an additional discussion on computational scalability and domain-specific tuning (e.g., VAEs in structured domains) could have been placed.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper addresses a practically motivated problem which has strong relevance in domains with hard-to-satisfy trade-offs (e.g., pathogen-specific drug development).\n- Experiments are conducted on a diverse set of tasks, considering different baselines.\n- Empirical results show that MOCOBO consistently achieves near-optimal coverage, often matching the performance of T individually optimized solutions, compared to baselines.\n\nWeaknesses:\n- There is a lack of justification for some key design choices.\n- - A justification on the design of the coverage score could have been provided. Specifically, no ablation is done over this key design. Alternative coverage metrics (e.g., threshold-based coverage) would have revealed whether MOCOBO's gains depend heavily on this definition, also given the fact that some of the baselines (e.g., MORBO) are not directly designed for the coverage problem but adapted for empirical evaluation.\n- - Ablation comparing MOCOBO with/without trust regions to isolate the impact of trust regions.\n\t\t\n- There are some missing ablations which have strengthened the analysis of the proposed method.  \n- - Batch size (q) ablation: How would the performance of the MOCOBO change compared to baselines, under various batch sizes? How do the performance and runtime scale with q?\n- -  K ablation: It’s unclear how robust MOCOBO is to the choice of K, or how performance degrades when K is poorly chosen. The discussion on the ablation of K is provided in Section 4.3. However, since it is essential to the proposed approach, I think it would have been supported significantly better if experiments under different K values for a specific problem domain had been provided in the main text.\n- -  Effectiveness of ECI against alternative acquisition functions could have supported the benefit of the proposed approach better. Ablating the proposed ECI acquisition against, e.g. maximum of standard EI per objective acquisition function, would clarify how much ECI contributes to performance vs. the trust-region or greedy cover construction.\n- -  In structured tasks, the results heavily depend on VAE quality. Ablating the surrogate model quality (e.g., varying initial data size) would have clarified the benefits of MOCOBO from the embedding quality.\n\n-  The problem domains cover continuous and structured search spaces. However, to clarify the generalizability of the proposed approach, experiments on a problem domain involving a mixed search space could have been provided.\n\n- I think the novelty is overly stated. As provided with related works, similar ideas exist in clustering, gradient-based multi-objective optimization, and CluSO, which is proposed for black-box coverage.\n- - Algorithm 1 is standard, specifically, a greedy algorithm for submodular maximization is textbook material (Nemhauser et al. 1978).\n- - Instead, clearly motivating the idea with extreme objective conflict settings would highlight the contribution.\n\n- No regret bounds or convergence guarantees are provided, unlike classic BO.\n\t\nMinor:\n- Typo in line 23, should be corrected as \"optimization\".\n- In terms of writing, it is a bit repetitive. Particularly, the coverage problem is redefined excessively.\n\n> Nemhauser, G.L., Wolsey, L.A. & Fisher, M.L. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming 14, 265–294 (1978).", "was_revised": true, "final_justification": "I finalized my score to weak reject because (i) I still have unclarified concerns, and (ii) I think that the current version of the manuscript requires \"major revision\" considering NeurIPS standards. Namely, the sensitivity of the method to batch size and initialization dataset size is left as future work. Importantly, the robustness of MOCOBO to the choice of K, which is an essential decision for the proposed approach, is not clarified to me. There is no regret-bound discussion that would help the theoretical understanding of the method. Instead of providing a small discussion, the authors rebut, stating that \"recent popular works do not include bounds\", which is not an effective way of clarifying a concern. Furthermore, as also raised by other reviewers, in terms of the writing, the problem definition and motivation require major revision to improve the clarity.", "rebuttal": "We thank the reviewer for their thoughtful feedback and for highlighting the practical relevance and strong empirical performance of MOCOBO. We respond to each point below:\n# 1. Coverage Score\nWe appreciate the reviewer’s suggestion to examine alternative definitions of coverage. However, we respectfully clarify that our coverage score is **not a design choice**, but rather the **problem definition itself**, grounded in prior work. Specifically, the continuous coverage score we use was originally formalized in the CluSO paper and is a principled way to pose the goal of finding a small set of K solutions such that **each of the T objectives is optimized as much as possible** by at least one solution in the set. This captures the setting we care about, for example, discovering K antibiotics such that each pathogen is targeted as effectively as possible, not just adequately. By contrast, threshold-based coverage is indeed a meaningful formulation for some domains but it constitutes a fundamentally different problem: it assumes that we know, a priori, a threshold value for each objective beyond which we do not care to improve performance further. This makes sense in some safety-critical settings (e.g., drug toxicity screening), but is not aligned with the domains we focus on where **better objective values are always desirable** and thresholds are typically unknown or unhelpful. For these reasons, we adopted the coverage formulation from CluSO and did not include threshold-based comparisons. That said, we appreciate this point and now explicitly clarify in the paper that the problem definition we adopt is the same as has been used in the black-box coverage literature (CluSO), and we better motivate its relevance to our domains of interest. We also agree with the reviewer that methods like MORBO are not designed for coverage, and we will further emphasize in the main text that these are adapted baselines used to highlight that off-the-shelf BO methods do not trivially solve the coverage problem. We include them not to criticize, but to underscore the importance of explicitly addressing this problem class. We do directly compare to CluSO, which is the only existing method we are aware of that does try to solve the black-box coverage optimization problem directly.\n# 2. Trust Regions (TRs)\nThank you for raising this point. We have added an ablation study comparing MOCOBO with and without trust regions (TRs) on the rover task with 4 obstacle courses, and on the template free peptide design task. As expected, MOCOBO performs substantially better with TRs, confirming that TRs significantly improve performance in the high-dimensional settings we consider. We have added plots and discussion of this to the appendix. We report below the average coverage score achieved by MOCOBO with and without TRs after N function evaluations (higher is better). \n### Rover Task\n* N=40K, with TRs: $17.52  \\pm 0.32$, without TRs: $-6.95  \\pm 0.92$. \n* N=80K, with TRs: $17.76  \\pm 0.31$, without TRs: $-4.64  \\pm 0.69$.\n### Peptide Task\n* N=300K, with TRs: $-45.30  \\pm 6.38$, without TRs: $-242.53  \\pm 11.56$. \n* N=600K, with TRs: $-39.50  \\pm 5.74$, without TRs: $-225.84  \\pm 13.30$.\n\nTo clarify the motivation for using TRs: it is well-established in the BO literature that standard BO (without TRs or other high-dim adaptations) performs poorly in high dims. [1] originally introduced TRs as a principled way to improve performance of high-dim BO. Since then, TRs have become a standard tool for any high-dim BO task. Since all of the tasks we consider are high-dimensional, this precisely why we adopt TRs. We note that recent work has proposed alternative approaches to improve high-dim BO without TRs [2]. However, there remain concerns about the applicability of these approaches to structured domains (e.g., see Table 2 in [3], results show that [2] performs surprisingly poorly on structured tasks). \n# 3. Additional Ablations\nWe added an ablation comparing to “MOCOBO-EIT\": MOCOBO with the reviewer’s suggested \"maximum of standard EI per objective\" acquisition function. We ran this ablation on the rover task with 4 obstacle courses and on the template free peptide design task. We have added plots and discussion of this to the appendix. We report below the average coverage score achieved by MOCOBO (as proposed with ECI), and by MOCOBO-EIT, after N function evaluations (higher is better). \n### Rover Task\n* N=40K, MOCOBO: $17.52  \\pm 0.32$, MOCOBO-EIT: $12.33  \\pm 0.92$. \n* N=80K, MOCOBO: $17.76  \\pm 0.31$, MOCOBO-EIT: $16.00 \\pm 1.07$.\n### Peptide Task\n* N=300K, MOCOBO: $-45.30  \\pm 6.38$, MOCOBO-EIT: $-180.32 \\pm 5.44$. \n* N=600K, MOCOBO: $-39.50  \\pm 5.74$, MOCOBO-EIT: $-175.71  \\pm 4.88$.\n\nMOCOBO with our proposed ECI acquisition function performed significantly better on both tasks, demonstrating the importance of ECI to the performance of MOCOBO. Additionally, MOCOBO-EIT still performed fairly well, outperforming ALL other baseline methods considered in the paper after the full budget of 80K function evaluations on the rover task. This highlights the importance of other aspects MOCOBO.\n\nAdditionally, we agree that ablations of q (batch size), initialization dataset size, and K, will further strengthen the paper. We plan to run each of these and add results to the camera ready version.\n# 4. Novelty\nWe appreciate the reviewer’s concerns regarding novelty and the opportunity to better clarify our contributions. We agree that Algorithm 1 is based on classic submodular maximization (e.g., Nemhauser et al. 1978), and will certainly clarify in the paper that we did not invent submodular optimization! Our novelty lies not in the greedy algorithm itself, but in how it is integrated with other components of MOCOBO to form a practical, scalable solution to black-box coverage optimization. Additionally, we have revised the intro and related work sections to **better position MOCOBO as the first method for coverage optimization that is scalable to high-dimensional and structured domains**. While CluSO addresses the same problem formulation, it was not designed for high-dimensional or structured input spaces. In fact, as our experiments show, CluSO performs poorly, consistently worse than baselines not designed for coverage, on all of the domains we consider. This is not a criticism of CluSO, but rather a reflection of its limitations in structured or high-dimensional domains. In contrast, MOCOBO is designed with scalability in mind and supports **structured and high-dimensional inputs**, making it, to our knowledge, **the first black-box coverage optimization method applicable to real-world domains like protein and molecular design**. We have revised the manuscript to better emphasize this contribution and to clearly differentiate our method from prior work.\n# 5. Convergence Guarantees\nWe agree that regret bounds for MOCOBO would be interesting and we plan on investigating this in future work. We do kindly note that a lot of recent popular BO papers do not include regret bounds (e.g., [6-15]) or include ones that reduce to proving convergence via running random search as a subsequence (e.g., [4,5]). \n# 6. Other\nWe have corrected the typo, revised writing to reduce redundancy in coverage definition, fixed caption formatting, and added discussion of limitations regarding computation required to pre-train domain specific VAEs. We thank the reviewer for pointing out that a mixed search space domain could be interesting to add, this is something we will consider for future work.\n# Q1\nAddressed above via new ablation study.\n# Q2\nMOCOBO’s greedy covering set construction does lead to longer overhead time compared to baseline approaches. MOCOBO overhead takes approximately 1.4 times longer than TuRBO and MORBO and approximately 1.2 times longer to run than ROBOT (ROBOT is slower than other baselines due to additional time needed to compute diversity constraints between observations on each iteration). However, the overall additional computation time required by a run of MOCOBO is negligible when optimizing moderately expensive black-box functions, where black-box function evaluation time dominates overall computational cost. \n# Q3\nAs we mentioned above, CluSO performs poorly on the tasks considered in this paper because it was not designed to scale to high-dimensional or structured input spaces. We have added discussion of this to the paper. \n# Q4\nSee section 2 above.\n# Cites\n[1] “Scalable Global Optimization via Local Bayesian Optimization” Eriksson et al. NeurIPS 2019.\n[2] “Vanilla Bayesian Optimization Performs Great in High Dimensions” Hvarfner et al. ICML 2024.\n[3] “A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences” González-Duque et al. NeurIPS 2024.\n[4] “Scalable Constrained Bayesian Optimization” Eriksson et al. AISTATS 2021.\n[5] “Discovering Many Diverse Solutions with Bayesian Optimization” Maus et al. AISTATS 2023.\n[6] “Bayesian optimization and attribute adjustment” Eismann et al. UAI 2018.\n[7] “Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining” Tripp et al. NeurIPS 2020.\n[8] “Max-value Entropy Search for Multi-Objective Bayesian Optimization with Constraints” Belakaria et al. NeurIPS 2020.\n[9] “High-dimensional Bayesian optimization with sparse axis-aligned subspaces” Eriksson et al. UAI 2021.\n[10] “Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces” Deshwal et al. NeurIPS 2021.\n[11] “Local Latent Space Bayesian Optimization over Structured Inputs” Maus et al. NeurIPS 2022.\n[12] “Advancing Bayesian Optimization via Learning Correlated Latent Space” Lee et al. NeurIPS 2023.\n[13] “Joint Composite Latent Space Bayesian Optimization” Maus et al. ICML 2024.\n[14] “Approximation-Aware Bayesian Optimization” Maus et al. NeurIPS 2024.\n[15] “Latent Bayesian Optimization via Autoregressive Normalizing Flows” Lee et al. ICLR 2025."}, {"review_id": "FHuHAPwl8d", "reviewer": "Reviewer_9SUK", "summary": "This paper proposes a BO-inspired algorithm to do multi-objective covering optimization. The authors define a \"coverage\" success metric\n\n$$c({x_1, \\ldots, x_K}) = \\sum_{t=1}^T\\max_{k=1}^K f_t(x_k)$$\n\nand their proposed algorithm is essentially expected improvement of coverage, estimating the expectation using Monte Carlo and maximizing over subsets using a submodular greedy approach which should achieve $(1-1/e)$ accuracy.\n\nThe authors perform a variety of experiments, _including one with real in-vitro results_!", "questions": "1: batch extension\n\nThis is described in the text as ECI after simultaneously observing the batch. However, shouldn't that quantity be $c(S^*_{D_s \\cup_{i=1}^q(x_i, y_i)})$ instead of what is in equation 6? (a maximum over elements in the batch). The objective in equation 6 seems to be \"ECI if you simultaneously observe labels and are then allowed to choose 1 element to keep\"\n\n2: Redundancy in ECI equation\n\nIn equation 4 you write:\n\n$$\\max(0, c(S_{D \\cup (x,y)}) - c(S_{D}))$$\n\nBecause $c$ is submodular, doesn't that imply that this quantity is always greater than 0? Therefore the max is not necessary. Since $c(S_{D})$ does not depend on $y$ it can also be moved outside the expectation. This would reduce the expression to just \"expected coverage score\" - a constant. Does that make sense? And does that suggest that the algorithm might under-explore?\n\n3: Single-objective baselines\n\nI don't understand how the comparison to TurBO / other single-objective BO methods was done. You stated that $T$ separate rounds of optimization were performed. How is sample efficiency measured for plotting in figure 2? Are you assuming a meta-algorithm where which cycles through taking one step for each objective?", "limitations": "I think the limitations are adequately mentioned and addressed in the paper.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Overall this is a really strong paper.\n\n- Paper is very well-written and well-presented\n- Algorithm proposed is novel, interesting, and technically sensible\n- Good theoretical justification for greedy approximation\n- Extensive experiments on a variety of tasks in different domains, including actual in-vitro lab experiments.\n\nThe only \"weaknesses\" I can see are fairly minor:\n\n- I'm not super convinced about the practicality of this problem in drug discovery: the broad-spectrum antibiotic example makes sense in principle, but medicines are not usually developed _jointly_ like this, instead each program usually wants _one_ solution for _one_ objective. I don't see this being applied in a real-world company for that reason. That's nothing against the algorithm itself though.\n- As with anything in BO, experimental comparisons are overshadowed by dependence on a large number of obscure hyperparameters and may not generalize, so no guarantees that this difference will translate to other settings. I'm not holding that against this paper too much because that is a more widespread issue in the field.\n- Batch extension does not make a ton of sense (see question below)", "was_revised": true, "final_justification": "My initial assessment was positive (highest possible score), and comments from the other reviewers have not convinced me to lower my score.", "rebuttal": "We sincerely thank the reviewer for the thoughtful feedback. We especially appreciate your recognition of the real-world *in-vitro* results. Below, we respond to each of your questions:\n# Q1: Batch Extension and Equation 6\nYou’re absolutely right to flag this subtlety. The form in Equation 6 approximates the marginal gain in coverage under the simplifying assumption that only the best point in the batch contributes to coverage, rather than the full set. This is computationally much simpler to optimize in practice, but as you point out, it does not fully reflect the potential joint contribution of all q points. Your suggested form would indeed capture the “true” expected joint gain more faithfully. We chose the current formulation as a practical approximation. That said, exploring more accurate batch ECI objectives, like the one you suggest, is a very interesting direction for future work.\n# Q2: Redundancy in the ECI Expression\nThank you for this insightful question. You’re correct that, in theory, the “max(0, …)” term in the ECI expression may not be strictly necessary, since the coverage score can only be increased or remain the same after a new data point is added. Similarly, since the baseline coverage value (before adding the new point) is fixed, one could factor it out of the expectation and simplify the expression.\nWe kept the original form primarily for consistency with standard Expected Improvement-style notation and to make the marginal gain in coverage explicit. In practice, the predictive distribution over objective values still introduces enough variability that the expectation continues to provide a meaningful acquisition signal, so we haven’t observed any under-exploration behavior due to this formulation. That said, your observation is well-taken, and this is something we plan to explore further in future work. \n# Q3: Single-Objective Baselines and Figure 2\nThank you for asking for clarification here. For each baseline (e.g., TuRBO), we perform T independent runs, one per objective, each with its own budget. To ensure a fair comparison on sample efficiency, we combine the results from these T runs by selecting the best K solutions (among the T collected ones) that maximize coverage. We then report the cumulative number of queries across all objectives (i.e., total function evaluations across the T runs) on the x-axis of Figure 2. So, there is no meta-algorithm cycling through objectives in a round-robin fashion. Instead, we assume access to T independent runs and aggregate the solutions post hoc to compute coverage, essentially giving the baselines every possible advantage while still showing that MOCOBO outperforms them.\n# Formatting and SI Units\nThank you for pointing out the SI unit formatting issues and appendix structure. We’ll take your suggestions into account when preparing the camera-ready version, including exploring the use of the siunitx package and reorganizing the appendix for improved readability."}]

Author rebuttal:

Meta-review: This paper considers the problem of computing the optimal covering set of $K$ input designs for optimizing multiple expensive-to-evaluate objective functions. This problem is motivated by real-world deployment of experimental design methods. The paper defines a "coverage" success criterion and adapts the principles of Bayesian optimization (BO) to optimize it: expected improvement of coverage where the expectation is performed using Monte Carlo sampling and maximization over subsets using a submodular greedy approach with known (1-1/e) approximation guarantee. The experimental results are good and actual in-vitro lab experiments for peptide design is a noteworthy contribution.

All the reviewers' appreciated the paper's contributions but also raised several good questions. The author response addressed most of these questions. Three out of four reviewers' recommend accepting the paper and also added their perspective to counter the two concerns of the reviewer with a negative opinion. Overall, this is a good paper: methods are introduced to solve a real science/engineering problem. I recommend accepting the paper and strongly encourage the authors' to incorporate all the discussion into the final paper and make the following changes:
1. Release the code without fail as promised.
2. Sensitivity analysis on the choice of "K".
3. Increase the clarity of the paper (mentioned by two reviewers) and incorporate all the comments/references from Reviewers UDrb and wMNa.
Decision: Accept (poster)