Beyond Grids: Multi-objective Bayesian Optimization With Adaptive Discretization
Authors: Andi Nika
Sepehr Elahi
Cagin Ararat
Cem Tekin
Venue: Accepted by TMLR ()

Abstract: We consider the problem of optimizing a vector-valued objective function $\boldsymbol{f}$ sampled from a Gaussian Process (GP) whose index set is a well-behaved, compact metric space $(\mathcal{X},d)$ of designs. We assume that $\boldsymbol{f}$ is not known beforehand and that evaluating $\boldsymbol{f}$ at design $x$ results in a noisy observation of $\boldsymbol{f}(x)$. Since identifying the Pareto optimal designs via exhaustive search is infeasible when the cardinality of $\mathcal{X}$ is large, we propose an algorithm, called Adaptive $\boldsymbol{\epsilon}$-PAL, that exploits the smoothness of the GP-sampled function and the structure of $(\mathcal{X},d)$ to learn fast. In essence, Adaptive $\boldsymbol{\epsilon}$-PAL employs a tree-based adaptive discretization technique to identify an $\boldsymbol{\epsilon}$-accurate Pareto set of designs in as few evaluations as possible. We provide both information-type and metric dimension-type bounds on the sample complexity of $\boldsymbol{\epsilon}$-accurate Pareto set identification. We also experimentally show that our algorithm outperforms other Pareto set identification methods.

Published in Transactions on Machine Learning Research (08/2025)
Beyond Grids: Multi-objective Bayesian Optimization With Adaptive Discretization
Andi Nikal
mudinikampii-sun
Maz. Planck Institute for Software Systems
Germany
Sepehr Elahi!
sepehr.elahi@epf..oo
Deportment of Compuler and Communiicatin Sciences
EPFL Switzerland
Çağın Ararat
cararat@bilkent.ccll
Deportment of Industrial Engineering
Bilkent University
Turkey
Cem Tekin
cemtekin@eer. bilkenii.b...... edu.
Department of Electrical and Electronics Engineering
Bilkent University
Turkey
Reviewed on OpenReview: https: // openreview. net/ forum? Wg10HRREE
Abstract
We consider the problem of optimizing vector-valued objective function f sampled from a Gaussian Process (GP) whose index set is a well-behaved, compact metric space (X, d) of designs. We assume that f not known beforehand and that evaluating f at design results in noisy observation of f(x). Since identifying the Pareto optimal designs via exhaustive search is infeasible when the cardinality of X is large, we propose algorithm, called Adaptive e-PAL, that exploits the smoothness of the Ga-ssmpledd function and the structure of (X, d) to learn fast. In essence, Adaptive c-PAL employs tree-based adaptive discrelization technique to identify an 6-accurate Pareto set of designs in as few evaluations as possible. We provide both information sample complexity e-accurate Pareto set identification. We also experimentally show that our algorithm outperforms other Pareto identification methods.
and metric dimension-typp bounds on the
1 Introduction
Many complex scientific problems require the optimization of multi-dimennionall (m-variate) performance metrics (objectives) under uncertainty. When developing new drug, scientists need to identify the optimal therapeutic doses that maximize benefit and tolerability (Scmidt, 1988). When designing new hardware, engineers need identify the optimal designs that minimize energy consumption and runtime (Almer et al., 2011). In general, there is no design that can simultaneously optimize all objectives, and hence, one seeks identify the of Pareto optimal designs. Moreover, design evaluations are costly, and thus, the optimal designs should be identified with few evaluations as possible. In practice, this formidable task for at least. two reasons: design evaluations only provide noisy feedback about ground truth objective values, and the set of designs to explore is usually very large (even infinite). Luckily, in practice one only needs to identify the
Work done while authors Bilkent University.

---

Published in Transactions on Machine Learning Research (08/2025)
set of Pareto optimal designs up to a desired level of accuracy. Within this context, a practically achievable goal is to identify an e-accurate Pareto set of designs whose objective values form an 6-approximation of the true Pareto front for a given E e= =[='...,,E'!! E RT (Zuluaga et al., 2016).
There has been a considerable amount of interest in the Pareto set identification problem with a finite design space (Kone et al., 2023; Zuluaga et al., 2013; 2016), where individual designs are compared based on their vector values, according to multi-objective domination criteria. However, in many multi-objective problems of interest, such the accurate tuning of particle accelcrators (Roussel et al., 2021), robotic systems control (Ariizumi et al., 2014), the design space is not necessarily finite. For these examples, naive application of methods that are suitable for finite spaces might not yield the desired level of efficiency, due to the lack of rigorous theoretical foundations. Motivated by these observations, in this paper, we consider the Pareto set identification problem assuming a compact design space.
Specifically, we model the identification of an c-accurate Parcto set of designs as an active learning problem. We assume that the designs lie in well-behaved, compact metrie space (X, d), where the set of designs X' might be very large. The valuue objective function f = "f"'...., fT1 defined over (X, is unknown at the beginning of the experiment. The learner is given prior information about f, which states that it is a sample from a multi-output GP with known mean and covariance functions. Then, the learner soquentially chooses designs to evaluate, where evaluating f at design x immediately yields a noisy observation of (x)- The learner uses data from its past evaluations in order to decide which design to evaluate next until it can confidently identify an e-accurate Pareto set of designs.
Main contribution. We propose a new learning algorithm, called Adaptive e-PAL, that solves the Pareto active learning (PAL) problem described above, by performing as few design evaluations as possible. Our algorithm employs free-based adaptive discretization strategy to dynamically partition X. It uses the GP posterior on f to decide which regions of designs in the partition of X' to discard or to declare as a member of the 6-accurate Pareto set of designs. On termination, Adaptive c-PAL guarantees that the returned set of designs forms an e-accurate Pareto set with a high probability. To the best of our knowledge, Adaptive e-PAL is the first algorithm that employs an adaptive discretization strategy in the context of PAL, which turns out be very effective when dealing with large X.
We prove information-type and metric dimension-type upper bounds the sample complexity of Adaptive e-PAL. (Theorem 1). Our information-type bound yields a sample complexity upper bound of Ö(g(t) where = minge', g(e) = minff 2 1: VTr/T= < e), and ?r is the maximum information gain after T evaluations. To the best of our knowledge, this is the first information type bound for dependent objectives in the context of PAL. In addition, our metric dimension-tyre bound yields sample complexity of ((E-(B+2)) for all D> D1, where D2 represents the metric dimension of (X, d) and a E (0, 1] represents the Hölder exponent of the metric induced by the GP on X. As far as we know, this is the first metric dimension-tyee bound in the context of PAL. Our bounds complement each other: as we show in the appendix, neither of them dominates the other for all possible GP kernels. Specifically, we provide an example (Proposition 1) under which the information- type bound can be very loose compared to the metric dimension-type bound. Besides theory, we also show via simulations on multi-objective functions that Adaptive e-PAL significantly improves over its competitors in terms of accuracy. Furthermore, we point out the key challenges that necessitate novel a algorithmic design and techniques as follows:
First, due to the nature of the problem, we need to properly define novel confidence hyper-rectangle objects which are designed to capture uncertainty, not only over individual designs, but over whole regions. This requires integrating information and metric-type components into our hyper-rectangle definitions.
Second, the refining, evaluating and discarding steps of our procedure are substantially different from their analogues in c-PAL (Zuluaga et al., 2016). Again, this is due to the large space of designs to consider. Here, we need to be confident about regions of space, rather than individual points, and choose whether to discard them or maintain them.
Third, in addition to the Pareto front identification problem, inherent in e-PAL, our formulation also introduces the problem of efficiently expanding the search tree in promising directions (note that the
2

---

Published in Transactions on Machine Learning Research (08/2025)
tree is not uniformly explored). Thus, we need additional analysis which involve cntemmatioo-thhoretee and geometric components integrated into threshold condition.
Finally, all of the above necessitate new additional results which involve algebraic and analytic arguments to carry through the analysis. Specifically, results such as Lemma 8 (which requires a careful step-by-step analysis applicable only to our setting), Lemma. 10, Lemma 12 and Lemma 16, are all results which require non-trivial and novel reasoning steps necessary for our setting.
Organization. We provide detailed comparison with related work in Section 2. We explain the properties of the function to be optimized and the structure of the design space in Scction 3. This is followed by the description of Adaptive e-PAL in Section 4. We give sample complexity bounds for Adaptive e-PAL in Section 5, discuss the main aspects of computational complexity analysis in Section 6. We devote Section to the computational experiments, followed by conclusions in Section 8, We present the proof of the main theorem separately in Section B, the appendix. At the end of the paper, we include table for the frequently used notation.
2
Related Work
This section provides a detailed discussion of related work on several lines of research.
2.1
Multi-objective optimization
Learning the Pareto optimal set of designs and the Pareto front has received considerable attention in recent. years (Belakaria et al., 2024; Auer et al., 2016; Zuluaga et al., 2013; 2016; Mernández-Lobate et al., 2016; Shah & Ghahramani, 2016; Paria et al., 2020; Belakaria Deshwal, 2019; Belakaria ct al., 2020; Daulton et al., 2020; Alizadeh et al., 2024; Mukherjee et al., 2024).
Auer et al. (2016) consider a finite set of designs and formulate the identification of the Pareto front as pure exploration multi-armed bandit (MAB) problem in the fixed confidence setting. Under the assumption that the centered outcomes are I-subGaussian and independent, they provide gap-dependent bounds on its sample complexity, which, in the single objective case, yield the well-known gap-dependent sample-complexity bounds for pure exploration in the MAB setting (Mannor & Tsitsiklis, 2004). Other works on Multi-objective MAB include (Xu & Klabjan, 2023; Dusa-Fekete et al., 2017: Öner et al., 2018). As opposed to their frequentist approach, our approach is Bayesian, which imposes Gaussian process prior to the latent function of interest.
Knowles (2006) and Ponweiser et al. (2008) study the multi-objective optimization problem using the paradigm of Efficient Global Optimization (EGO) algorithm (Jones et al., 1998), a GP-based supervised learning approach used to tackle optimization problems with expensive evaluations. Knowles (2006) proposes ParEGO, which is an adaptation of EGO in the m-objective case. The author takes a scalarization approach to the problem, where the used acquisition function is the augmented Tchebycheff function, thus essentially reducing the problem to the single-objective one. Such an acquisition function was also used recently by Lin al. (2022) for Parcto set learning. They extend previous approaches by identifying an approximate Pareto set of (potentially) infinitely many designs, opposed to stopping with only finite number of designs. In contrast, we take direct Pareto set identification approach, in which we utilize the structure of the partial ordering relation between values of evaluated designs, while simultaneously integrating the GP posterior into the selection conditions of our method.
The second application of FGO, SMS-EGO (Ponweiser et al., 2008), does not reduce the problem to a single-objective one, but instead maximizes the gain in hypervolume from optimistic estimates based on GP model. Having optimistically estimated the GP-based value vectors of their predicted Pareto set, they compute the hypervolume of the gain of choosing such design points. The hypervolume approach to Pareto learning is further exploited by Shah & Ghahramani (2016) and Daulton et al. (2020). In Shah & Ghahramani (2016), the Pareto hypervolume is defined in lerms of an arbitrarily chosen reference point which is known to be suboptimal, and the current Pareto frontier. What makes their method attractive its efficient implementation and computation, which relies on the approximation The computational complexity of computing the expected hypervolume gain is improved by extending the problem to the parallel constrained evaluation setting in Daulton et al. (2020). However, no one of these
multi-dimensional integral.
3

---

Published in Transactions on Machine Learning Research (08/2025)
Table 1:
Comparison with related works. Both the algorithm and the performance analysis take into
account dependence between the objectives.
Work
Design
Function
Dep.
Sample complex.
Adaptive
space
bounds
discret.
Auer et al. (2016)
Finite
Arbitrary
No
Gap-dependent
Not used
Zuluaga al. (2013)
Finite
GP sample
No
Inf-type
Not used
Zuluaga et al. (2016)
Finite
RKHS element
No
Inf-ttype
Not used
Lemández-Lobato et al. (2016)
Bounded
GP sample
No
No bound
Not used
Shah & Ghahramani (2016)
Bounded
GP sample
Yes
No bound
Not used
Paria et al. (2020)
Compact
GP sample
No
Bayes Regret
Not used
Belakaria & Deshwal (2019)
General
GP sample
No
Regret norm
Not used
Belakaria al. (2020)
Continuous
GP sample
No
Regret norm
Not used
Daulton et al. (2020)
Bounded
GP samule
No
Exp. Hypervol.
Not used
Ours
Compact
GP sample
Yes
Inf. & dim.-type
Used
methods come with theoretical convergence guaranlees, while we provide a comprehensive best-of-both-world type of convergence guarantees under minimal assumptions.
Furthermore, Hernández-Lobate et al. (2016) consider (possibly infinite) bounded design space X' and assume that the individual objectives are samples from independent GPs. Their algorithm, Predictive Entropy Search for Multi-objective Optimization (PESMO), sequentially queries designs that maximize the acquisition function defined as the expected reduction in the entropy of the posterior distribution over the predicted Pareto set, given the previously sampled data. They provide comprehensive experimental comparisons between PESMO and other multi-objective optimization methods over various objectives and dimensions, both noisy and noiseless cases. The comparison is done with respect to the relative difference between the hypervolume of the predicted set and the maximum such hypervolume for the given number of evaluations. Although their setup is similar to ours, take different approach to the Pareto set identification and provide thcoretical guarantees for our method. Recently, Tu et al. (2022) extend the Predictive Entropy Search paradigm to that of Joint Entropy Search (JES), which takes into account the informativeness coming from both the Pareto set designs and their outcome vectors in their acquisition function.
Apart from Pareto front identification, several works consider identifying designs that satisfy certain perfor- mance criteria. For instance, Katz-Samuels & Scott (2018) consider the problem of identifying designs whose objective values lie in given polyhedron in the fixed confidence setting. On the other hand, Locatelli et al. (2016) consider the problem of identifying designs whose objective values are above given threshold in the fixed budget setting. In addition, Gotovos (2013) consider level set identification when f is sample from a GP. There also exists a plethora of works developing algorithms for best arm identification in the context. of single-objective pure-exploration MAB problems such as the ones by Mannor & Tsitsiklis (2004); Bubeck et al. (2009); Gabillon et al. (2012).
2.2 Adaptive discretization
Adaptive discretization is a technique that mainly used in regret minimization in MAB problems on metric spaces (Kleinberg et al., 2008; Bubeck al., 2011), including contextual MAB problems (Shekhar al., 2018), when dealing with large arm and context sets. It consists of adaptively partitioning the ground set along a tree structure into smaller and smaller regions, until, theoretically, the regions converge to single point (under uniqueness assumptions in the single-objective case). Different from other upper confidence bound-based methods, here, the usual upper confidence bound of a given point x (in both frequentist and Bayesian approaches) is inflated with factor times the diameter of the region containing so that the uncertainty coming from the variation of the function values inside the region is also captured. A key efficacy of adaptive discretization comes from the fact that does not blindly sample the space without first exhaustively partitioning it long as it is certain. This certainty formalized by comparing the sample uncertainty diameter with the region diameter. If the latter exceeds the former, then the algorithm decides
4

---

Published in Transactions on Machine Learning Research (08/2025)
to partition the given region into smaller sub-regions. It is known that adaptive discretization can result in much smaller regret compared to uniform discretization. However, this is significantly different from employing adaptive discretization in the context of PAL. While the regret can be minimized by quickly identifying one design that yiclds the highest expected reward, PAL requires identifying all designs that can form an e-Pareto front. together, while at the same time discarding all designs that are far from being Pareto optimal. Table compares our approach with the related work.
2.3 <-Pareto active learning
The line of work on which our method builds is that of Zuluaga et al. (2013; 2016). Zuluaga et al. (2016) consider a finite design space and assume that cach objective is a sample from an independent GP. We briefly describe the rationale of their algorithm, since it will also be used later on. Their algorithm, e-Pareto Active Learning (c-PAL), is confidence bound-based method. It partitions the design space into three subsets: the set of undecided designs, that of predicted Pareto-optinal designs, and that of predicted suboptimal designs. The procedure is composed of four main phases. In the first phase, the algorithm uses the posterior estimates in order to compute the confidence hyper-rectangles of designs that are still up for selection. In the second phase, cach design is associated with an uncertainty region, dependent on all previous confidence hypee-rectangles, and then checked whether it is safe to discard it The third phase consists of deciding whether there are any designs that can be safely predicted to be Pareto optimal. In the final phase, e-PAL decides whether not to evaluate the design of maximal uncertainty.
The algorithm propose utilizes similar rationale to that of e-PL.. However, such an extension, although seemingly natural, also brings with it several challenges and key differences, which necessitate novel ways of solving the problem. We summarize these differences in the following.
First, e-PAL iterates through all designs, maintaining relevant statistics of them which uses to decide whether they are reasonable candidates for Pareto optimality, or whether they can be safely discarded. In our case, this would be futile attempt, since the design space is potentially infinite. Therefore, we use adaptive discretization techniques (Bubeck al., 2011) in order to tackle the problem. Next, the application of adaptive discretization in the context of PAI. introduces additional technical intricacies: instead of working over individual designs, our method maintains statisties over nodes (centers) of design regions with similar values, and, as a result, with similar levels of confidence. Thus, we design novel bonus terms for each node, which simultaneously take into account both the rectanglctangula uncertainty and the structural relationship of "ncarby"" nodes.
On the algorithmic front, the successful integration of adaptive discretization into the PAT, setting implies new evaluation procedure. We part from the e-PAL evaluation subroutine and introduce new condition, which captures the uncertainty over a given region and implics that the algorithm will evaluate a design from the region only when it is absolutely necessary, thus optimizing the sample complexity of the overall procedure. On the theoretical front, on top of the information-type sample complexity bounds provided by Zuluaga et al. (2016), we additionally provide dimension-type bounds, thus yielding best-of-both-worldd bounds. We do this motivated by examples in which the information-type bounds might actually be loose (see Proposition 1). To make our theoretical analysis rigorous, we prove several additional results that allow for comprehensive understanding of our bounds. To the best of our knowledge, such a full comprehensive analysis for both types of bounds, while simullaneously accounting for adaplive discretization in the context of PAL.
the first to provide
3 Background and formulation
Throughout the paper, let us fix positive integer m 2 2 and a compact metric space (X,d). We denote by T the m-dimensional Euclidean space and by RT the set of all vectors in RT with nonnegative components. We write [m] = m.) Given a function f: X + Rm and a set S c X, we denote by f(8) = (f()) x E S) the image of under f. Given x E X and r 2 0, B(x,r) = (v E X: y(x,y) S r)
We assume a tree structure defined over the design space, where parent-child relationships are properly defined between relevant nodes. See Definition 10.
5

---

Published in Transactions on Machine Learning Research (08/2025)
denotes the closed ball centered at with radius r. For non-empty set S S R", let as denote its boundary. II another non-empty set S' S IRm is given, then we define the Minkowski sum and difference of S and S' as 8 + S' = {u+ + μl: μ E S n E 8 S - S' = {u - μl: T:me MES, E E'),, respectively. For a vector μ² E IR",, we define μa + + {
3.1 Multi-objective optimization
A multi-objective optimization problem is an optimization problem that involves multiple objective functions (Hwang & Masud, 2012). Formally, letting f :X' - be a function for every j [mm], we write
maximize [f (.)) f"),, (x)]" subject to x x x
where m 2 2 is the number objectives and X' is the set of designs. We refer to the vector of all objectives evaluated at design
X as f(x) (z)....; f ('(())]T The objective space is given as f(X) S R. In order to define set of Pareto optimal designs in X, we first describe several order relations on R
Definition 1. For μt, uz E R" we soy that: (1) a is weakly dominated by pt, written μ 3 p', if p S u for every j E [m]. (2) μ is dominated by pl, written as μ < ,', if j I pt and there exists j E [m] with W,
Py < 14-- (3) For e E IR4, p is e-dominated by pt, written as μA Ie pt, , if la I pt + (4) pa is incomparable with pt, written as a || p', if neither f - pl nor p' x u holds.
Based on Definition 1, we define the following induced relations on X. Definition 2. For designs I, E X, we say that: (1) x is weakly dominated by y. written as 3 y, if f(x) 3 f(y). (2) x is dominated by y, written as x - if f(x) - fv)) (3) For e E 14,, x is e-dominated by y, written as x 3e y. if f(z)= Ze f(v). (4) x is incomporable with y, written as x || y, if f(x) II fly).
Note that, while the relation I on Rd (Definition 1) is a partial order, the induced relation 3 on X (Definition 2) is only preorder since it does not satisfy antisymmetry in general. If design X is not dominated by any other design, then we say that is Pareto optimal. The set of all Pareto optimal designs is called the Pareto set and is denoted by (())) The Pareto front is defined as Z(X) = ((f(Ox))) - -RT).
We assume that f is not known beforchand and formalize the goal of identifying O(Y) as a sequential decision-making problem. In particular, we assume that evaluating f at design æ results a noisy observation of f(x). The exact identification of the Pareto set and the Pareto front using a small number of evaluations is, in general, not possible under this setup, especially when the cardinality of X' is infinite or very large finite number. A rcalistic goal is to idontify the Parcto set and the Pareto front in approximate sense, given desired level of accuracy that can be specified as an input Therefore, our goal in this paper is to identify an e-accurate Pareto set (see Definition 5) that contains a set of near-Pareto optimal designs by using as few evaluations as possible. Next, we define the c-Parcto front and 6-accurate Parcto set associated with X.
Definition 3. Given e RT, the set (x)) = (f (O)))) RT) (f((())) - 2c RT) is called the c- c-Poreto front of X.
Roughly speaking, the c-Parcto front can be thought of as the slab of points of width 2e in R" adjoined to the lower side of the Pareto front.
Definition 4. Given e E I.m and S C Rm, a non-emply subset C of S is called an e-covering of if for every μ S, there ezists μt C such that ş Ie n². Definition 5. Given RT, subset Oe of X is called an e-accurate Pareto set if f(O,) is E-covering of (X))
Note that the front associated with an e-accurate Pareto set is a subset of the e- e-Pareto front As mentioned in (Zuluaga et al., 2016), an e-accurate Pareto set natural substitute of the Parcto set since any c-accurate Pareto design is guaranteed to be no worse than 2e of any Pareto optimal design.
3.2 Prior knowledge on
We model the vector f lf' ..... fT] mean, i.e., (xx) = 0 for all x E X, and some positive definite covariance function k.
T of objective functions as a realization of an m-output GP with zero
6

---

Published in Transactions on Machine Learning Research (08/2025)
Definition 6. An m-output GP with inder set X is collection (f(x)) of m-ddimensional random vectors which solisfies the properly that (f (xn)) ) is Gaussian random veclor for all (II,...,Zn) S X and n E N. The probability law of an m-output GP (f(x))xxx is uniquely specified by its (vector-valued) mean function x + p((x) = [x]( E R" and its (matriz-valued) covariance function (x1, + k(21, x2) [[([(=1) - ((x1))((((2)) -p(2)))) E Rmxm.
Functions generated from a GP naturally satisfy smoothness conditions which are very useful while working with metric spaces, as indicated by the following remark.
Remark 1. Let g be a zero-mean, single-output GP with inder set and covariance function k. The metric 1 induced by the GP on X is defined as x2) (E((o(z1) I 1/2 (k(x1, k 32) (((x).)2))) This gives us the following tail bound for æi, 22 E X, and 2 0: P((g(()) (x2)) ) 2 a) S 2exp (-a² (21,
Let us fix an integer 2 1. We consider a finite sequence "m = [_ Ør|" of designs with the corresponding vector f(rj = vector y/r] = [yI...... "y.....,7... yrl of observations, where
of unobserved objective values and the (mT-dimmenionaal
yr f(Ø+) + R2T
is the observation that corresponds to 3, and Kr = [Kt] m is the noise vector that corresponds to this particular evaluation for each T E [T].
The posterior distribution of f given V(r) is that of an m-output GP with mean function pr and covariance function ky given by
(T(x) (2) Emr) V
and
kr(x, x') k(0, kip (x) (Krr pry + Epr)) (2))
for all H, x' E N, where (x)((x) = [k(,,, (1,, .... k( xr) E Ruxmr
k(01, 81), .... k( HT)
2 Im
Oms
Om
K K[m]=
[ =
E mTTTT
k(Tr, T1).
k(ār, FT)
Ons
O
r² Im
In denotes the m m-dimensional identity matrix, and Om is the m x m-dimensional zero matrix. Note that this posterior distribution captures the uncertainty in f (x) for all x X. In particular, the posterior distribution of f(x) is (ur(()), (r.x, and for each j [m]. the posterior distribution of f'(x) is (( (x)))) where (x))² kel (I Moreover, the distribution of the corresponding observation y is (z)((z), kr x) + Im))
3.3 Information gain
Since we aim at finding an e-accurate Pareto set in few evaluations possible, need to learn the most informative designs. In order to do that, we will make use of the notion of information gain. Our sample complexity result in Theorem depends on the maximum information gain.
In Bayesian experimental design, the informativeness of a finite sequence क.r of designs is quantified by I(ym) fIr) Hym)) H Hymml)m)) where H(-) denotes the entropy of a random vector and H-Iff)) denotes the conditional entropy of a random vector with respect to fir) This measure is called the information gain, which gives us the decrease of entropy of f(r) given the observations ymr)- We define the marimumm information gain as 7r maxym (3 f(n))
7

---

Published in Transactions on Machine Learning Research (08/2025)
4 Adaptive c-PAL algorithm
In this section, we introduce our algorithm, Adaptive c-Pareto Active Learning (PAL), which builds on the e-PAL algorithm of Zuluaga et al. (2016) and utilizes adaptive discretization techniques to enable an efficient navigation of the continuous search space. The algorithm is largely technical, thus we divide the description of each of its phases into more comprehensible subsections.
Intuition On a high level, our algorithm's rationale can be explained as follows. First, Adaptive e-PAL maintains an adaptively changing resolution over the design space, structured along so-called nodes of a tree. That is, starting from the center of the space (the center node), we only 'zoom in' (thus expanding the tree) points that are of potential interest. In every iteration of the algorithm, we are given the current set of active nodes in our based partition of the space. These nodes serve as proxies for regions of points in the design space which they inhabit. Now, the goal of the algorithm is to return a set of nodes (and, as a consequence, their associated regions) that form an approximate Pareto front with high probability. In order to do that, the algorithm maintains confidence region for every active node. Applying worst-case arguments over these confidence regions, the algorithm decides which points to discard in every iteration, and which points to maintain potentially optimal (in the Pareto sense). Next, we move points about which we are confident enough to a predicted Pareto set. Basically, we keep shrinking the set of points about which we are undecided, and we keep growing the set of points which we believe are approximately optimal. Finally, if enough information is obtained on the most uncertain active node, then we decide to expand it into children nodes, since there is enough reason to believe that more relevant information will be obtained from those new nodes.
The system operates in rounds 2 In each round I, the algorithm picks a design 2, E X, and assuming that it already had evaluations, it subsequently decides whether or not to obtain the + 1st noisy observation yr+1 = [w-..... of the latent function f at zt. At the end, our algorithm returns subset f of X which is guaranteed to be an e-accurate Pareto set with high probability and the associated set P of nodes which we will define later. The pseudocode is given in Algorithm 1.
4.1 Modeling
We maintain two sets of time indices, one counting the total number of iterations, denoted by i, and the other counting only the evaluation rounds, denoted by r. The algorithm evaluates a design only in some rounds. For this reason, we also define the following auxiliary time variables which help us understand the chronological connection between the values of t and т. We let represent the nunber of evaluations before round t 2 1 and let t, denote the round when evaluation t 2 0 is made, with the convention to = 0. The sequence (fx )=20 is an increasing sequence of stopping times. Note that we have TI, +1 = for each E N.
Iteration over individual designs may not be feasible when the cardinality of the design space very large. Thus, we consider partitioning the space into regions of similar designs, ie., two designs in X which are at a close distance have similar outcomes in each objective. This is natural property of GP-sampled functions as discussed in Remark 1.
Since iteration over individual designs is not possible in large spaces, we will instead iterate over 'regions' of interest. Here, we focus on a compact subset X' of the Euclidean space Rm" for some m' E N. However, we do this purcly for simplicity of presentation. In Appendix, we show that our analysis holds when X' is any general 'well-behaved' metric space.? For such a metric space, one can easily partition the design space along a tree structure, each level h of which is associated with a partition of X into No equal-sized regions Xn.s. centered at node Th,i, for all < i < Nh, where N NEW N.
At each round t N, the algorithm maintains set S, of undecided nodes and set Pe of decided nodes. For an undecided node in St, its associated cell consists of designs for which we are undecided about including in the e-accurate Pareto set. Similarly, for a decided node in Pt, its associated cell consists of designs that we decide to include in the e-accurate Pareto set. At the beginning of round t = (initialization), we set
2Sco Scction A for detailed definitions.
8

---

Published in Transactions on Machine Learning Research (08/2025)
S1 ( and Pi 0. Within each round & N, the sets Pe and S are updated during the discarding, 6-covering and vefining/evaluaiie
phases of the round; at the end of round their finalized contents are set as Pr+1 and S,+1, respectively, as a preparation for round ++ 1. For each t E N, the algorithm performs round t as long as S + at the beginning of round t; otherwise, it terminates and returns P Pt-
In addition to the sets of undecided and decided nodes, the algorithm maintains set A, of active nodes, which is defined as the union S, Pr the beginning of each round E N. While the sets St and Pa are updated within round t as described above, the set A, is kept fixed throughout the round with its initial content. Note that A }
At round & E N, the algorithm considers each active node This E Ac. Let j E [m]] We define the lower inder of tn, in the jth objective (2 (xn,s) - Vn, where (xn,s) is high probability lower bound the jth objective value at Inii and is defined as
(xn,)) max (xn.s) - B112 (mNS), m2, (p((x.)) - 31. (p(2a,)) - Vn-1)
Here, Br O(log(T2/0) and Vn Ö(pah) is a high probability upper bound on the maximum variation of the objective j inside region Xn.s. Similarly, we define the upper index of Th,i in the jth objective as Uy (mn,)) B/ (IN.s) + Vn, where Bj (m),)) is a high probability upper bound the jth objective value at ThZi and is defined as
(F = min (In))) + 0112 o2 (mra)) me, (p((n,)) + 31120 (p(xn.))) Vn-1)
We denote by L. (L), ................................ LT" (x),))) the lower indez vector of the node Tn,i at round t and similarly by (Z(.)) = (zn,)).... U." (x),))) the corresponding upper inder vector. We also let V,, denote the m-dimensional vector with all entries being equal to Vn. Next, we define the confidence hyper-rectangle of node Z at round as
Qc(xn.) (y RT: (z y y U((nn,))
which captures the uncertainty in the learner's prediction of the objective values. Then, the posterior mean vector Mr, (mn,)) [nt, (I.,,))...., (z),))) and the variance vector o,, (xn,)) = [o (x..))...., (FT..))) are computed by using the GP inference outlined in Section 3. We define the cunulative confidence hyper-rectangle of Th,s at round as
Rd (x R (1n.))
(1)
assuming that (xn, is well-defined at round t - 1 (the case 2 2) or using the convention that 10(20.1) = =" since A = { } (the case t = 1). The well-definedness assumption will be verified in the phase below.
4.2 Discarding phase
In order to correctly identify designs to be discarded under uncertainty, we need to compare the pessimistic and optimistic outcomes of designs. First, we define dominance under uncertainty.
Definition 7. Let t E N and let x, E As be two nodes with + We say that x is e-dominated by y under uncertainty al round if max (x)) Se min( (y)), where we define max max(Ra (R())) as the unique vector v E Ro(x) such that v 2 2 for every j E [m] and = (z),...,2?) in a similar fashion.
...,,))) E Re(x), and we define min (a((R))))
If a node x E A₁ is e-dominated by any other node in Ae under uncertainty, then the algorithm is confident enough discard it. Basically, the condition of Definition 7 implies that, if the best possible value that x can have is still approximately dominated by the worst possible value that y can have, then we can conclude that y dominates x with overwhelming probability. To check this, the algorithm compares x with all of the pessimistic available points as introduced next.
SSe Theorem 1 for exact definitions.
9

---

Published in Transactions on Machine Learning Research (08/2025)
Definition 8. (Pessimistic Pareto set) Let t called the pessimistic Pareto set of D at round 1, as the set of all nodes E D for which there is no other node E D \ } such that mi)(R((z) x my)( We call design in Ppeses( a pessimistic Pareto design of D at round t.
and let D S As be set of nodes. We define Ppess, (D),
Here we are interested in finding the nodes, say H, which are Parelo optimal in the most pessimistic scenario when their objective values turn out to be min R, (z). We do this in order to identify which nodes (and their associated cells) to discard with overwhelming probability. More prociscly, the algorithm calculates P Prese.t Ppeas, (At) first. For each Th,s Si Peepsss it checks max(R, (xn,))) Ze min(R, for some P Press.t In this case, node Th,i is discarded, that is, is removed from St, and will not be considered in the rest of the algorithm; otherwise change is made in S..
4.3 e-Covering phase
The overall aim of the learner is emply the set St of undecided nodes as fast as possible. A node Th2 E St is moved to the decided set P, if it is determined that the associated cell X1,s belongs to an e-accurate Pareto set O₂ with high probability. To check this, the notion in the next definition is useful. Let us denote by W. the union P. U. at the end of the discarding phase. Note that W. C A, but the two sets do not coincide in general due to the discarding phase.
ViNi C A
Modeling
if ia S. Pyeu
Discarding
covering
t21 T T21 1 S,, Precss
Mr [+(aas)) (sa(r)))
max R2 (za,,) 5, [2(x) for some Preees
min (R, (cras) + + (a)a Wi
do
do
((M))) Re-((au)) (((a))
5, S, (Rui) SUU
& =, (aud P. P, Ufraed
Figure 1: This is an illustration of the modeling, discarding, and e-covering phases.
Definition 9. Let Whht E St. We say that the cell Xb,t associated to node TnZ belongs to an O. with high probability if there is no x We such that min (x,,)))
max (x)))
For each Th, E St, the algorithm checks if X belongs to an O₂ with high probability view Definition 9. In this case, Th,s removed from the set S, of undecided nodes and is moved the set Pe of decided nodes; otherwise, be returned by the algorithm part of the set P at termination. Intuitively, this step determines which points can be safely predicted to be in the approximately accurate Pareto set if there is no other active node which approximately dominates it in the worst case possible, In the appendix, we show that the union P=U Xn,; of the colls is an 6-accurate Pareto cover, according to Definition 5, with high probability. Note that while the sets S,, Pe can be modified during this phase, the set W; does not change. The modeling, discarding, and e-covering phases of the algorithm are illustrated in Figure 1.
change is made. The nodes in P, are
removed from this set; hence, they will
4.4 Refining phase
While S, * 0, the algorithm seleets a design Z, = Thy.i E We that corresponds to node with depth h, and index i,, according to the following rule. First, for a given node Thss E We, we define
(x(,))))
max V.V E. (WA..)
lV 3
(2)
which is the diameter of its cumulative confidence hyper-rectangle in RT The algorithm picks the most uncertain node for evaluation in order to decrease uncertainty. Hence, among the available points in W,, the node The.s with the maximum such diameter is chosen by the algorithm. We denote the diameter of the cumulative confidence hyper-rectangle associated with the selected node by 4, and formally define it W. max ew, or (xn.))) Since the learner not sure about discarding The or moving to Pt, he decides
10

---

Published in Transactions on Machine Learning Research (08/2025)
SamplingEvvaluating Evaluating
FA. c St
& (oo Ilss [Va
Refine FrLA and children &
P+1 = Pt
FA.A argmax (F(u)
do,4 o (or-(aaalll [V,lla
Refine Ri,,, and add children P.
S41 = S
t=t+1
Obaerve [(thha)) +
Figure 2: This is an illustration of the sampling and refining phase.
whether refine the associated region Xn or evaluating the objective function at the current node based the following rule.
Refine: Tf 2 ||a, (Fr 1l S [|V,, then They expanded, i.e., the N children nodes (16,+1,5; N(4 +)+15] S in] of Thide are generated. If Thes E St, then these newly generated nodes are added to S, while The.i is removed from S.. An analogous operation is performed if 2h., E P.. In cach case, for each j with Níi confidence hyper-rectange of its parent node Phi,i E Ar as calculated by equation 1, that is, we define Re( = R2 (T = Re-1(wn,,i) n Qr(T), This way, for every node E Pt U St at the end refining, the cumulative confidence hyper-rectangles up to round are well-defined and we have Ro(x:) 2 R, (x)) 2 .... (x). In particular, the well-definedness assumption for equation is verified for round t 1 since Ar+1 is defined as P. U.S, the end of this phase.
+ j S it, the newly generated node 2h.-1, inherits the cumulative
Evaluate: If G2/2 l|o (Zh,,)))l2 [[V 2l. then the objective function is evaluated at the point Thade i.e., we obsorve the noisy sample yr, and update the posterior statistics of Ih,,,- No change made in St and P..
This phase of the algorithm is illustrated in Figure 2. The evolution of the partitioning of the design space is illustrated in Figure 3.
Ri(au) Re Re-s(
f(aex)
Pareto front
flar
Xaa May Xx
Xxx
Xxy
Xxx
flass
7%
Figure 3: This is illustration of the structural way of partitioning the design space. In this example we take X = =0, m = and e = O. On the left, we can see the partition of X' at the beginning of round t. Note x4,8 that S; = (1,,,7 3 and P: = { 23,s), while ø2,1 and Ø3,3 have been discarded in some prior round. On the right, we see the corrosponding confidence hyper-rectangles I, prior to the modeling phase, the hyper-rectangle of node Th, is R4-1(#p.)) Note that, the discarding phase, node 21,8 will be discarded since max( R2 (x1,)) Ze min (R, (z1,7)). Thus, 24,7 will be removed from S, by the end of the phase. Furthermore, note that more than one Pareto optimal designs take values in reper-rec This is because the node of region containing Pareto optimal points is not necessarily of these points. For example, we have & E X2, and f() E R2(223)-
these nodos. At the beginning of round
11

---

Published in Transactions on Machine Learning Research (08/2025)
2
6.)
X
112
X
X2.2
X1,
X2.1
X
X3
X1,2
3/2
fe
[c
2(3,3))))
R₁t (2,22
R
R,11(12,11
0
Y1
Figure 4: A depiction of three refining ilerations of our algorithu logether with the associated discarding and e-covering phases. The first row reflects the structural changes in the design space. The second row reflects the changes in the objective space. The green color in the region bars denotes predicted Pareto region, the orange color denotes an undecided region, while the gray color discarded region. At time nodes 21,1 and 11,2 that partition X. The region X1,2 is already predicted Pareto set, while X1,1 is still undecided. This is also reflected in the first figure (from the left) on the second row. Here, we can visually see that æ1,1 is e-dominated by F1,2 under uncertainty. Since there are no more nodes, we proceed to assign X1,2 a predicted Pareto set. In the next iteration, we first refine #1,1 further because the uncertainty level is already below the threshold. Then, upon examination, we discard region X2,1 Again, the corresponding changes in the objective space are reflected in the second row. In the next iteration, we further refine 22.2 and include one of its children regions to the predicted Pareto set. Note that we have not included evaluation steps for simplicity of presentation.
have two
4.5 Termination
If S, = at the beginning of round t, then the algorithm terminates. We show the appendix that at the latest, the algorithm terminates when w, < miny e!. Upon termination, it returns a non-empty set P. of decided nodes together with the corresponding e-accurate Pareto set P P= P XA,i which the union of the cells corresponding to the nodes in P. The full procedure is given in Algorithm 1.
5 Sample complexity bounds
We state the main result in this section. Its proof is composed of a sequence of lemmas which are given in the appendix. We first state the necessary assumptions (Assumption 1) on the metric and the kernel under which the result holds. Then, we provide a skotch of its proof and subsequently give an example of an m-output GP for which the maximum information gain is linear in T.
12

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm Adaptive e-PAL
Input: X, (Ka)a20: (V/ 122; 6, 6, (87)z21; GP prior P μ4, kn k
Initialize: P1= 0, S1 = (Iu,1): Ro( Rm
0.
2: while S: do
3: A, = Pp Ppess, Ppess,
for Th,i E Ar do
Modeling
Obtain (Tna)) and or (2n,i) by GP inference.
6: (x( = RA ( n (r(an)).
7:
end for
for Thes E E \
Ppess, do if Rr E Presstt max (R.(()))),) 3a min(R.(1:) then
Discarding
10:
S {Zn,i).
11:
end if
12:
end for
13:
W: = S, UP..
14:
for Ih.s E St do
b e-Covering
15:
if 7rr E Wt min (xn.))) + 6 max(R,(x)) then
16:
S, \ fxn,) Pi P, U (xn.).
17:
end if end for
18:
19:
if S; * 0 then
>
20:
Select node Thate argmax,,,, ,. EEW (zn,s). if 3. (xhiti)) 1VV AND Thisk E S₁ then S ) S, S; U fam N(i. +)+11 Nij. Re(FN(41,1) = Re( for each with N(1, - 11 Nig
21:
22:
23:
24:
else if 3 (10
V/Vrell2 AND Thes E P. then
25:
P. = P. (Ihesshi Pe = Pe U (#h+t1,1: N(4, - 1) < i N4.. (e( = RE( for each with N(i - -) Ni.
26:
27:
clsc
28:
Evaluate design x; Thase and observe y, = f( + Ky.
29:
-
30:
end if
31:
end if
32:
P++1 = Pri S.+1 St.
33:
t t=
34: end while
35: return P = Pt and P = Up,,ER, Xn.i-
13

---

Published in Transactions on Machine Learning Research (08/2025)
Assumption 1. The class K. of covariance functions to which we restrict our focus satisfies the following crileria for any & E K. (1) For any æ,y E X and j E [m]; we have 15(x, v) I Cad(ar y)a, for suilable Ck > 0 and 0 <<< a 1. Here, 1 is the natural metric induced on X' by the jth component of the GP in Definition 6 as given in Remark 1 with covariance function kJ. (2) We assume bounded variance, that is, for any x E X and j E [ml; we have k5 x)) 1.
Em] be given with minzelm] e 0. Let 6 E (0,1) and D> D2. For each Theorem 1. Let == h 2 0, let
Vn = 4CC(U110)
(Ca+
2h2x2m 66
+ hlogg N +
-4D1 (-a log (Ca(eiot)e) + +Ca)
for some strictly positive constants C2 and C3, where x+ := max for x E R. Moreover, for each T E N, define B, = 2 log(2m7² N +1)
When we run Adaptive e- E-PAL with prior GP(0, k) and noise N(0, o²), the following holds with probability at least 1:
An e-accurate Pareto set can be found with at most T function evaluations, where T is the smallest natural number satisfying
-(D+a) D42a + K2T D42a
CBT T
min K1 T D420 (log T)
(log T)Daza
Deza
<c,
where C and K1 are constants that are defined in the appendir and do not depend on T, K2 is logorithmic in T, and Pr is the mazimam information gaān which depends on the choice of k.
Sketch of the proof of Theorem 1: We divide the proof of Theorem 1 into three essential parts. First, we prove that the algorithm terminates in finite time, and examine the events that necessitate and the ones that follow termination. Here, it is important to note that the largest uncertainty diameter in a given round is less than or equal to e, then the algorithm terminates. This introduces a way on how to proceed on upper bounding sample complexity, namely, we can upper bound the sum of these uncertainty diameters over all rounds. Then, by observing that i) the term V, decays to 0 as h grows indefinitely, which means that the algorithm refines up until finite number of tree levels, and that ii) node cannot be refined more than a finite number of times before expansion, we can conclude that the algorithm terminates in finite time. After this point we prove, using Hoeffding bounds, that the true function values live inside the uncertainty hyper-rectangles with high probability. We then proceed on first proving the dimension-type sample complexity bounds and then the information-typpe bounds. We use the aforementioned termination condition and upper bound the sum of the uncertainty diameters over all rounds. We use Cauchy-Schwan inequality to manipulate the expression as we desire and then upper bound it in terms of information gain using an already established result in the paper. For the dimension-type bounds, we consider expressing the over rounds as a over levels h of the tree of partitions and upper bound it using the notion of metric dimension. We take the minimum of the two bounds, thus achieving the bound stated in Theorem 1.
Remark 2. Note that we minimize over two different bounds in Theorem 1. The term that involves TT corresponnss to the information-type bound, while the other term corresponds to the metric dimension-bype bound. Equivalently, we can express our information-tuy and our metric dimension-type bound as ((+) for any D D1. For certain kernels, such as squared exponential and Malérn kernels, "Tt can be upper bounded by a sublinear function of (see Srinivas el al. (2012)). Our information type-bound is of the same form as in Zubuaga et al. (2016). When X is finite subset of the Euclidean space, we have D2 = 0, and thus, our metric-dimensee type bound becomes mear-O(1/2)) which is along the same lines with the almost optimal, yap-dependent ((1r-O(1ggpp)) bound for Parelo front identification in Auer el al. (2016).
bound as Ö(g(c)) where g(c) = min (T 2 1: VTr/TT < cf
In order to prove the bounds in Theorem 1, even for infinite X, we propose a novel way of defining the confidence hyper-rectangles and refining them. Since Adaptive c-PAL discards, c-covers and refines/evalle /evaluates in ways different than e-PAL in Zuluaga et al. (2016), we use different arguments in the proof to show when the algorithm converges and what it returns when it converges. In particular, for the information-type bound,
14

---

Published in Transactions on Machine Learning Research (08/2025)
exploit the dependence structure between the objectives. Moreover, having two different bounds allows to use the best of both, as it is known that for certain kernels, the metric dimension-type bound can be tighter than the information-type bound. That is the implication of our next result. The proof is mainly technical, thus we defer it to the Appendix.
Proposition 1. There evists a ouulti- GP f, with covariance function satisfying Assumption and a sequence of T noisy observations made on f, such that we have [y]m f(r) 2 Q(T)..
6 Computational complexity analysis
The most significant. subroutines of Adaptive e-PAL in terms of computational complexity the modeling, discarding, and e-covering phases. Below, inspect the computational complexity of these three phases separately.
Modeling. In the modeling phase, mean and variance values of the GP surrogate are computed for every node point in the leaf set. This results in a complexity of O + n7²), where T is the number of evaluations and n is the number of node points at a particular round. Note that the bound on n depends on the maximum depth of the search tree.
Discarding. This phase can be further separated into two substeps. In the first substep, the pessimistic Pareto front is determined by choosing the leaf nodes whose lower confidence bounds are not dominated by any other point in the leaf set. In the second phase, the leaf points whose upper confidence bounds are e-dominated by pessimistic Pareto set points are discarded. If done naively by comparing each point with all the other points, both of the phases can result in Onn²) complexity. However, there are efficient methods that achieve lower computational complexity. In our implementation, we adopt Algorithm 3.1 of Kung el al. (1975) to reduce computational complexity On when m or m 3. For 3, one can use Algorithm 4.1 of Kung et al. (1975) to achieve O(n(logn)m* m)m-)) complexity.
e-Covering. Tn the e-covering phase, the algorithm moves the nodes that are not dominated by any other node to P. Similar to the discarding phase, when implemented naively, the e-covering phase results in O(n)) complexity. An adaptation of Kung et al. (1975) algorithm can be implemented as in the case of discarding phase to achieve sub-quadratic complexity which results in O(n logn) for m = and m = and OOnooo n mm log n) for m 3.
In general, we observed that the number of evaluations was much smaller than the number of nodes throughout run. Therefore our implementation which scale sub-quadratically with the number of points.
say that discarding and e-covering phases are the main bottlenecks in
7 Experiments
This section empirically evaluates Adaptive c-PAL, comparing its performance and efficioncy against other multi-objective Bayesian optimization (MOBO) methods. We focus on validating the effectiveness of the adaptive discretization strategy and assessing the algorithm's ability to find an e-accurate Pareto set sample- efficiently.
7.1 Performance metrics
We use a combination of three performance metrics: c-accuracy ratio, c-coverage ratio, and average mean- squared error (MSE). Since the objective functions tested are continuous, the true Pareto front contains infinitely many points. To compute the metrics, we approximate the true Pareto front by sampling 10, 000 points uniformly from the input space, evaluating the objective function at these points, and identifying the Pareto optimal designs among them.
e-accuracy ratio. This metric measures the quality of the predicted Pareto set P. It is computed as the ratio of predicted points fx) (with P) that fall within the c-Pareto front Zz(X') to the total number of points in P. Operationally, we check if a predicted point is e-dominated by some point on the approximated true Pareto front, or equivalently, if it is at most 2e away (in the sense of 32c) from the closest true Pareto
15

---

Published in Transactions on Machine Learning Research (08/2025)
point. While high e-aceuracy is desirable, it does not guarantee that the entire Pareto front is well-represented. We also need to assess how well the predicted set covers the true front, which is measured by the e-coverage metric.
e-coverage ratio. This metric measures how well the predicted set P covers the true Pareto front. is computed as the ratio of true Pareto points (from the discretized approximation) that are e-dominated by at least one point in f(P) to the total number of true Pareto points. Equivalently, we check if a true Pareto point is within 2e (in the sense of =2e)) of the closest predicted point.
Average mean-squared error (MSE). This metric complements e-coverage by quantifying the average closeness of the predicted front to the true front. It is computed by averaging the squared Euclidean distance between each true Parelo point (in the objective space) and the closest predicted Pareto point in J(P). Ideally, we seek high values for both accuracy and coverage, and a low value for MSE.
7.2 Multi-objective Bayesian optimization algorithms
We compare Adaptive -PAL, with four state-of-the-art MOBO methods: PESMO (Heraáneez-Lobato et al., 2016), ParEGO (Knowles, 2006), USeMO (Belakaria et al., 2020), and qNEHVI (Daulton et al., 2021). The latter is a hypervolume-based method specifically designed to handle noisy observations by integrating over the posterior uncertainty of the true Pareto front. Since PESMO, ParEGO, USeMO, and qNEHVI require a pre-specified evaluation budget, while Adaptive -PAL terminates based on its confidence criteria, we set the budget for the competitors to be at least as large as the number of evaluations performed by Adaptive -PAL upon termination in our experiments. This ensures competitors have access to at least much information. We used the implementations for PESMO and ParEGO from the Spearmint Bayesian optimization library", for USeMO from the authors' open-source code", and for qNEHVI from the BoTorch library. 6
For completeness, we also attempted to benchmark against the original c-PAL, algorithm (Zuluaga et al., 2016). However, we encountered difficulties achieving termination when running both the authors' publicly available code and our own implementation based on the published pscudocode. As we were unable to obtain completed runs, we have excluded e-PAL from the presented results.
7.3 Simulation setup & results
We first sampled 10 distinct objective functions from the specified GP prior (detailed below). For each of these functions, we then ran each algorithm 5 times, using different random seeds for each run to vary the observation noise and any internal randomness within the algorithms.
Setup. We simulate a problem with a 1-dimensional input space X' = [0. 1] and a 2-dimensional objective space (m = 2). The objective function f is sampled from a GP with a zero mcan function and independent squared exponential kernels for each objective: (2,,))) = 0.5 (m=x2²) and k² (² x') 0.1 0.1 exp( 2x0.067 Observation noise is Gaussian with o = 0.01 (variance o² = 10 ))
(m-=x')²
Adaptive c-PAL. We run Adaptive c-PAL with a target accuracy c= (0.05, 0.05) and confidence 8 = 0.05. The tree parameters were set to N 2, p = 1/2, and ei = 02 1. To investigate the impact of the maximum tree depth, we tested three settings for hmax- The first setting used the theoretically derived value hmax 24, calculated using Lemma 4 based on the target c. The other two settings used practical, reduced depths of Amax = 10 and hmax = 9 to evaluate the trade-off between computational cost and performance. When using these practical depth limits, refinement beyond /max was prevented by setting V,, = 0 for all h 2 1 In this specific experimental run, Adaptive E-PAL terminated after approximately 50 evaluations for hmax = 24, 40 evaluations for hmax = 10, and 35 evaluations for hmax 9.
PESMO and ParEGO. We run PFSMO and ParEGO for 100 iterations (exceeding Adaptive e-PAL's evaluations). We use the same d = 0.05 where applicable. The acquisition function optimization starts from the best point on a grid of size 1000, followed by L-BFGS optimization.
"nttps://github.. www/bee http//elaaaaiaaaa / http:///ttorcc.oooo///o/////////
16

---

Published in Transactions on Machine Learning Research (08/2025)
Table 2: Average of the e-aceuracy and coverage ratios (as percentages, mean + 99% interval) for different evaluation thresholds c' (c','). Highest mean value in each row is bolded. Target accuracy for Adaptive e-PAL was (0.05, 0.05).
Adaptive e-PAL (hmax = 24)
Adaptive e- GAL
Adaptive cPAA (Arar 9)
(hense = 10)
PESMO
ParEGO
USeMO
QNEHVI
0.050
98 2
99 =
99 +
9
94
92 =
99 + 1
0.010
97 2
98 2
97 1
9
94
74 +
96 +
0.005
97 +
97 +
90 +
90
84 +
60 +
95 +
0.001
78
+
42
54
56 +
26 =
60
Table 3: Average mean-squared error (MSE) and total rumning time (hh:mmras) of the algorithms. Lowest MSE and runtime are bolded.
Adaptive e-PAL (Amax = 24)
Adaptive e-PAL
Adaptive e-PAL (frmee = 9)
Metric
(Imax = 10)
PESMO
ParEGO
USeMO
NEHVV
MSE (x10-9)
8
40
4500
10
Runtime
15:16:24
00:01:00
00:00:27
00:09:20
00:07:30
00:23:40
00:00:40
USeMO. We run USeMO for 100 iterations. Expected Improvement (EI) is used as the acquisition function, aggregated using the Tehebycheff scalarization as recommended by the authors.
qNEHVI. We run the Noisy Expected Hypervolume Improvement (qNEHVT) algorithm for 100 itcrations. We use the sequential setting (batch size q 1) and the official implementation in Borch.. The acquisition function is optimized using multi-start L-BFGS-B, consistent with the other baselines.
Results. We evaluate the predicted Pareto front points returned by each algorithm using the metrics defined above. Table shows the average of the e-accuracy and e-coverage ratios, calculated for different evaluation thresholds c'. Using smaller c' values provides a stricter assessment.
Adaptive eAL with its theoretical parameters (Imax 24) achieves high performance (99% average becuracy/cowee coverage) when evaluated at its target e' (0.05, 0.05). This aligns well with the theoretical expectation of producing a valid c-accurate Pareto set with high probability. The slight deviation from 100% can be attributed to the probabilistic nature of the guarantees (6 = 0.05) and the approximations involved in discretizing the true Pareto front for metric caleulation. Notably, reducing 1max to 10 or 9 maintains excellent. performance at the target é' = 0.05. However, as expected, using a smaller hmax affects the performance at stricter evaluation thresholds (e' 0.05), as the algorithm has less resolution to preciscly delincate the Pareto front.
Comparing with competitors, Adaptive e-PAL (even with Amax 10) achieves superior combined accuracy and coverage across most evaluation thresholds. qNEHVI matches the best performance at e' = 0.05 and significantly outperforms all other baselines at stricter thresholds. Nonetheless, Adaptive e-PAL with its theoretical parameters (Amax = 24) still achieves the highest accuracy at the most stringent thresholds of e' < 0.005. USeMO shows good accuracy for = 0.05 but degrades quickly, likely due to returning sparse set of points. PESMO and ParEGO offer reasonable performance but are consistently outperformed by both qNEHVT and Adaptive c-PAL.
Table 3 presents the average MSE and total running time. The MSE results corroborate the accuracy soorracyy/oveaagee findings: Adaptive e- e-LAL with /max = 24 achieves the lowest MSE, indicating its predicted front is closest to the true front on average. The qNEHVI and Adaptive e-PAL (Amax = 10) runs yield the next-best MSE values, significantly outperforming other competitors. USeMO has a notably high MSE, consistent with its poor coverage. Observing the running times reveals the practical benefit of tuning /maax Reducing /max from 24 to 10 or decreased the runtime dramatically while preserving strong performance. qNEHVI also
17

---

Published in Transactions on Machine Learning Research (08/2025)
highly efficient, with runtime of just 40 seconds, faster than all baselines except the highly-tuned Adaptive e-PAT. (Amax = 9). This demonstrates that Adaptive e-PAT, can be made exceptionally fast by selecting a practical tree depth limit, while still offering an accuracy-advantee
over state-of-the-art methods.
Observing the running times reveals the practical benefit of tuning Amax. Reducing Amax from 24 to 10 decreased the runtime dramatically (by over 900 times this instance) while preserving performance at the target e = 0.05. This demonstrates that Adaptive e-PAL can be made computationally efficient by selecting practical tree depth limit, while still offering significant accuracy-advantage over the baseline methods tested.
8 Conclusion
In this paper, we proposed new algorithm for PAL in large design spaces. Our algorithm learns e-accurate Parcto set of designs in as few evaluations as possible by combining an adaptive discretization strategy with GP inference of the objective values. We proved both information-lype and metric-dimension lype bounds on the sample complexity our algorithm. To the best of our knowledge, this is the first sample complexity result for PAL that (i) involves an information gain term, which captures the dependence between objectives and (ii) explains how sample complexity depends on the metric dimension of the design space.
Acknowledgments
This work was supported by the Scientific and Technological Research Council of Türkiye (TÜBiTAK) under Grant 215E342. The work of C. Tekin was supported by the BAGEP Award of the Science Academy; by the Turkish Academy of Sciences Distinguished Young Scientist Award Program (TÜBA-GEBiP-2222 by TUBITAK 2024 Incentive Award.
References
Shima Alizadeh, Aniruddha Bhargava, Karthick Gopalswamy, Lalit Jain, Branislav Kveton, and Ge Liu. Pessimistic off-policy multi-objective optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2980 2988. PMLR, 2024.
Oscar Almer, Nigel Topham, and Björn Franke. A learning-based approach to the automated design of mpsoc networks. In International Conference on Archilecture of Computing Systems, pp. 243 258. Springer, 2011.
Ryo Ariizumi, Matthew Tesch, Howie Choset, and Fumitoshi Matsuno. Expensive multiobjective optimization for robotics with consideration of heteroscedastic noise. In 2014 IEEE/RSJ International Conference
Intelligent Robots and Systems, pp. 2230-2238 IEEE, 2014.
Peter Auer, Chao-Kai Chiang, Ronald Ortner, and Madalina Drugan. Pareto front identification from stochastic bandit feedback. In Artificial intelligence and statistics, pp. 939 947. PMLR, 2016.
Syrine Belakaria and Aryan Deshwal. Max-value entropy search for multi-objective bayesian optimization. In International Conference on Neural Information Processing Systems (NeurIPS). 2019.
Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, and Janardhan Rao Doppa. Uncertainty- aware search framework for multi-objective bayesian optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10044 10052, 2020.
Syrine Belakaria, Alalch Ahmadianshalchi, Barbara Engelhardt, Stefano Ermon, and Janardhan Rao Doppa. Non-myypic multi-objective bayesian optimization. arXiv preprinl arXiv:24 12. 08085, 2024.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pp. 23 37. Springer, 2009.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(May):1655-1099 1695, 2011.
18

---

Annual Conference on Newral Published in Transactions on Machine Learning Research (08/2025)
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-objective bandits: Opthmizing the generalized gini index. In International Conference on Machine Learning, pp- PML.R 2017.
Samuel Daulton, Maximilian Balandal, and Eylan Bakshy. Disferentiable expected hypervolume improvement for parallel multi-objective bayesian optimization. arXiv preprint arXiv:2006. (44:0000600078, 2020.
Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Parallel bayesian optimization of multiple noisy objectives with expected hypervolume improvement. Advances in Neural Information Processing Systems, 34:2187-2200, 2021.
Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Information Processing Systems, 2012.
Alkis Golovos. Active learning for level set estimation. Master's thesis, Eidgenössischee Technische Hochschule Zürich, Department of Computer Science, 2013.
Daniel Hernández-Lobato, Jose Bernandez-Lobate. Amar Shah, and Ryan Adams. Predictive entropy search for multi-objective bayesian optimization. In International Conference on Machine Learning, pp. 1492-1500 PMLR, 2016.
C-L, Hwang and Abu Syed Md Masud. Multiple objective decision Bectinngmethods and applications: a state-of-the-ars survey, volume 164. Springer Science Business Media, 2012.
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.
Julian Katz-Samuels and Clay Scott. Feasible arm identification. In International Conference on Machine Learning, pp. 2545-2543. PMLR, 2018.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the sortieth anneall ACM symposium on Theory of computing, pp. 681 690, 2008.
Joshua Knowles. Parego: A hybrid algorithm with on-line landscape approximation for expensive multiobjec- tive optimization problems. IEEE Transactions on Evolutionary Computation, 10(1):50-66, 2006.
Cyrille Kone, Emilie Kaufmann, and Laura Richert. Adaptive algorithus for relaxed pareto set identification. Advances in Neural Information Processing Systems, (6:35190-35201, 2023.
H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set vectors. Journal of the ACM, 22:469 476, 1975.
Xi Lin, Zhiyuan Yang, Xiaoyuan Zhang, and Qingfu Zhang, Pareto set learning for expensive multi-objective optimization. Advances in Neural Information Processing Systems, 35:19231-19247 2022.
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In International Conference on Machine Learning, pp. 1690-1698. PMLR, 2016.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jum):623 648, 2004.
Subhojyoti Mukherjee, Anusha Lalitha, Sailik Sengupta, Aniket Deshmukh, and Branislav Kveton. Multi- objective alignment of large language models through hypervolume maximization. arXw preprint arXiv:2412.05469, 2024.
Doruk Öner, Altuğ Karakurt, Atilla Eryilmaz, and Cem Tekin. Combinatorial multi-objective multi-armed bandit problem. arXiv preprint arXiv:1803.04039 2018.
Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. ficxible framework for multi-objective bayesian optimization using random scalarizations. In Uncertainty in Artificial Intelligence, pp. 766-776. PMLRR 2020.
19

---

Published in Transactions on Machine Learning Research (08/2025)
Wolfgang Ponweiser, Tobias Wagner, Dirk Biermann, and Markus Vineze. Multiobjective optimization a limited budget of evaluations using model-assisted S-metric selection. In International Conference Porallel Problem Solving from Nature, pp. 784 794. Springer, 2008.
Ryan Roussel, Adi Hanuka, and Auralee Edelen. Multiobjective bayesian optimization for online accelerator tuning. Physical Review Accelerators and Beams, 24(6):062801, 2021.
R Scmidt. Dose-finding studies in clinical drug development. European journal of climical pharmacology, 34 (1):15-19, 1988.
Amar Shah and Zoubin Ghahramani. Pareto frontier learning with expensive correlated objectives. In International Conference on Machine Learning, pp. 1919 1927. PMLR, 2016.
Shubhanshu Shekhar, Tara Javidi, et al. Gaussian process bandits with adaptive discrctization. Electronic Journal of Slatislics, 12(2):3829 3874,, 2018.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger. Information--heorelic regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, (88(5)32200-32) 2012.
Ben Tu, Axel Gandy, Nikolas Kantas, and Behrang Shafei. Joint entropy search for multi-objective bayesian optimization. Advances in Neural Information Processing Systems, 35:9922 9938, 2022.
Mengfan Xu and Diego Klabjan. Pareto regret analyses in multi-objective multi-armed bandit. In International Conference on Machine Learning, pp. 38499 38517. PMLR, 2023.
Marcela Zuluaga, Guillaume Sergent, Andreas Krause, and Markus Püschel. Active learning for multi-objective optimization. In International Conference Machine Learning, pp. 462-470 PMLR, 2013.
Marcela Zuluaga, Andreas Krause, and Markus Püschel. 8-pal: an active learning approach the multi- objective optimization problem. The Journal of Machine Learning Research, 17(1):3619 3650, 2016.
20

---

Published in Transactions on Machine Learning Research (08/2025)
Appendix
Table of Contents
Structure and dimensionality of the design space
B The proof of Theorem 1
22
B.1 Preliminary results
22
B.2 Termination condition
24
B.3 Guarantees on the termination of Adaptive e-PAT.
25
B.4 Two "good" events under which the sample complexity will be bounded
27
B.5 Key results that hold under the "good" events.
29
B.6 Derivation of the information-type sample complexity bound
31
B.7 Derivation of the dimension-Lype sample complexity bound
37
B.8 The final step of the proof Theorem
40
B.9 Proof of Proposition 2
40
B.10 Determination of a and Cx for Squared Exponential type kernels
42
The proof of Proposition 1
42
A Structure and dimensionality of the design space
Before we initiate our theoretical analysis, we first provide some technical definitions to be used throughout We begin by defining well- bellvee metric spaces. Our results will hold under any well-behaved metric space. Definition 10. (Well-behaved metric space (Bubeck et al., 2011)) The compact metric space (X, d) is said to be well-behaved if there exists sequence (Ar)220 of subsets of X satisfying the following properties:
1. There enists N E N such that for each 2 0, the set 2n, has N elements. We write N₁ = (In,s: 1 i s N²} and to each element Th,s is associated a cell Xn, = {o E:: Vj # fi: d(x, xn,s) S d(x, xna)).
2. For all h 2 0 and S i < Nh, we have X = Ns -j=N(--1)-1 XAtIj- The nodes Ih+1,5 for - Si Ni are called the children of Th,i, which in turn is referred to as the parent of these modes. We wrile p( Tb, for every 1) 1sjsj Ni.
9. We assume that the cells have geometrically decayjngg radāi, i.e., there exist 0 < < and 0 < 02 S
1 I such that we have B(In,i, e2p") C Xn,i C B(anis v1p²)) for every h 2 0. Note that we have 20zpa & (in.) I 201p", where diam(Xn.)) = suPayeXx, d(x,y).
The first property implies that, for every h 2 0, the cells Xn.., SsiS h partition X. This can be observed trivially by reductio ad absurdum. The second property inluitively means that, h grows, we get a more refined partition. The third property implies that the nodes ž4,4 evenly spread out in the space.
Additionally, we make use of notion of dimensionality intrinsic to the design space, namely, the metric dimension.
Definition 11. (Packing, Covering and Metric Dimension (Shekhar et al., 2018)) Let r 2 0.
subset Xi of X is called an r-packing of X if for every v. y E X1 such that x. + y, we have d(x, y) > r. The largest cardinality of such a set is called the r-packing number of with respect to d, and is denoted by M M(Xr. r.
21

---

Published in Transactions on Machine Learning Research (08/2025)
A subset X2 of X is colled an r-covering' of X if for every x E X, there erists y E X2 such that d(x,y) rr. The smallest cardinality of such set is called the r-cowering number of X with respect to d, and is denoted by N (X),.)).
The metric dimension D1 of (R.d) is defined as D1 = inf(a 2 0: 3C 2 vr > 0 (g,(N(Xrr,d)) S C - a log(r))-
This dimension coincides with the usual dimension of the space when X is a subspace of a finite-iimensional Euclidean space. We will upper bound the sample complexity of the algorithm using the metric dimension of (K,
B
The proof of Theorem 1
The proof of Theorem 1 is composed of a series of sophisticated steps, and is divided into multiple subsections. First, we describe Section B.1 set of preliminary results that will be utilized in obtaining dimension-type and information-type bounds on the sample complexity. Then, in Section B.2, we prove a key result that provides a sufficient condition for the termination of Adaptive e-PAL. We also show in this section that Adaptive e-PAL returns an e-accurate Pareto set when it terminates and bounds the maximum depth node that can be created by the algorithm before it terminates. In the proof, Ts represents the number of evaluations performed by the algorithm until termination and t, represents the round (iteration) at which the algorithm terminates. Throughout the proof, for given we let e = minj e², and assume that is such that e >> 0. Unless noted otherwise, all inequalities that involve random variables hold with probability one.
B.1 Preliminary results
We start by formulating the relationship between packing number, covering number, and metric dimension, which will help us obtain dimension-type bounds on the sample complexity. Recall that (X, d) compact well-behaved metric space with metric dimension D2 < +00.
Lemma 1. For every constant 0, we have
2r, S r(),r.d).
Moreover, for every D > D1, there erists Q > 0 such that
M(X, 2r, d) S N(X, S Qr-
Proof. We argue by contradiction. Suppose that we have a 2r-packing (21....,Ix.) and an r-covering (yn...., .BM} of X such that M 2 1. Then, by the pigeon-hole principle, we must have that both x; and zy lie in the same ball B),,, for some * j and some k, meaning that d(z;,,,) S r, which contradicts the definition of r-packing. Thus, the size of any 2r-packing is less than equal to the size of any r-covering and the first claim of the lemma follows. The second claim is immediate consequence of Definition 11 and the fact that D2 < +00.
Our next result gives a relation between the metric dimension of X' with respect to d and the one of X' with respect to the metrics induced by the GP, which holds under Assumption 1.
Lemma 2. Purt of Assumplion implies that if (X,d) d) has a finile metric dimension D1, then (X,4z) has a metric dimension DŞ such that DJ < Di/a.
Proof. We will proceed in two steps.
We first claim that N(X r2 S (Z) d). In order to show this, let X be an ( of (X'd). Then, it is an r-covering of (x) Indeed, let x E X. Then, there exists E X, such that
d(x.y) <
Cx
Not be confused with e-covering Definition where e Rm.. The meaning will be clear from the context.
22

---

Published in Transactions on Machine Learning Research (08/202))
Table Notation.
Symbol
Description
x
The design space
The latent function drawn from an m-output GP Accuracy level given as imput the algorillm The Pareto front X
(())
(x(
The e-Pareto front of X rth noisy observation of f Vector that represents the first noisy observations The node with index i depth h of the tree The cell associated with node Th.. Parent of node æn; The posterior after evaluations of wa, with jth component je (ma,s) The posterior variance after evaluations of the with jth component of (21.s) The confidence term
y. f(x.) +
M(rl
th,s
Xa.
p(an,i)
Mr (1)
o (ax..)
B,
The covariance function of the GP
d
The metric associated with the design space
The metric on X' induced by the jth component the GP
P: and Pa
The predicted e-accurate Pareto sets nodes and regions, respectively, at round The undecided sets nodes and regions, respectively, at round The e-accurate Pareto set of nodes returned by Algorithm 1 The union of sets S, and P. at the beginning of round The union of sets S, and Pa at end the discarding phase round The lower and upper vector-valued indices of node Hh, at time t, whose jih components are L/ (=n,)) and U/ (ra,s)
S. and S,
P
A
Le(on.s) and (z(as)
(Fn.)) and (ana)
The auxiliary indices of the lower and upper index of node Th,i at time
The me-dimensional vector with components are equal Vh, which appears in high probability bounds on the variation of f
The confidence hyper-rectangle associated with node Ta,s at round
Ra(aa))
The cumulative confidence hyper-rectangle associated with node øh, round
The diameter of the cumulative confidence hyper-rectaugle of ra, round The maximum wi (x),)) over all active nodes at round
we
Dr
The metric dimension of X
rr
The maximum information gain in evaluations of The number evaluations performed by the algorithm until termination The round in which the algorithm terminates
To
l.
Thus, 1f(2,1) v) S Cad(a, v)º s r, which implies that X is an r-covering of (X,4)). By the definition of the covering number, we have
N(2rr;1)) (8),
23

---

Published in Transactions on Machine Learning Research (08/2025)
and since this holds for any a of (Kt d), conclude that
N(X.),)) NN (x, Cr (1)))))))))
Next, we will show that D4 Di/a. For this, is enough show that Df S Di /a for every Dj > D1. By r,
Lemma. 1, there exists a constant Q 2 such that (K,, d) z Qir for all r > 0. In particular, for
every r > O, we have
-0-
(x)) S X. (x d
SQ
a
S
Q1 Di/a
D1/0
CK
(Ck))-D//a
For all r r> 0, assuming Cs 2 1, we have
log (X, T, ,r,4) 1)) S log Qi + (DD//allo((Aa, - (Di/a) (D),/a))))))))ll)))))))))))))))) log(r)
Therefore, there exists Q2 > 0, such that for all r > O, we have log ((', S Q2 (Di-////))ogg logr, with Q2 = log Q1 + (Di/a) log(Ck). Hence, we conclude that DJ S Di/a.
Next, we state a proposition that relates the information gain with the posterior variance the GP after each evaluation. This proposition will help us obtaining information-type bounds on the sample complexity. Since its proof is lengthy, we defer it to Section B.9.
Proposition 2. Let T N and कtr [ā1,.... " be the finite sequence of designs that are evaluated. Consider the corresponding vector fim = [f ..... ..... V|T] = "vl,...,y7] of noisy observations. Then, we have
T(T of unobserved objective values and the vector
T ΣΣ
Σ
log(1 to (0
2m
1=1
B.2 Termination condition
In this section, we derive sufficient condition under which Adaptive c-PAL terminates. We also give upper bound on the maximum depth node that can be created by Adaplive e-PAL until it terminates.
In the lemma given below, we show that the algorithm terminates at latest when the diameter of the most uncertain node has fallen below min, el.
Lemma 3. (Termination condition for Adaptive c-PAL) Let c = m el > 0, where c." = e. When runming Adaplive e-PAL, if we < holds al vound L, then the algorithm terminales without further sampling.
Proof. Since Adaptive e-PAL updates S and Pa at the end of discarding and e-covering phases, contents of these sets might change within round t. Thus, we let St,0 (Pro), St, (Pt,)) and St,2 (Pt,2) represent the elements in S, (Pt) at the end of modeling, discarding and covering phases, respectively. These sets are related in the following ways: St,0 2 Sr.1 2 Sr,,, Pt,0 = Pt. Pt.2 and Sr,1 UPr. = S1, U
Next, we state a claim from which termination immediately follows.
Claim 1. If Wf <e holds at ileration i, then for all In, S Pe,2, we have Inis $ St.
If Claim 1 holds, then any Th,s E St,0 Pi.2 must be discarded by the end of the discarding phase of Adaptive e-PAL. This implies that any Th,i E St,0 is either discarded moved to Pra by the end of the e-covering phase of round t, thereby completing the proof.
Next, we prove Claim 1. Note that W. is an upper bound on ||max (2(T,))) min( R2 (R,(2) for all Thi E Sr,2 U P22- For each Tha E St,2 U Pr,2 define
Wh,t max R2 (vn,)) min( min(RR (Fn.))
24

---

Published in Transactions on Machine Learning Research (08/2025)
We have |ww,ill2 S We < e, which implies that Wh; < e since w/,5 S "===(whe <esé for all j E [m].
We will show that if Th, E St, \ Pt,2 holds, then Th, cannot belong to St,1- To prove this, assume that Thi E 1t,1- Since Th,i $ Pr,,; then by the e-covering rule of Adaptive e-PAL specified in line 15 of Algorithm 1, there exists some y" E St, Ue,, for which
min(RR(Enn))) + E 3 max(Rx(y))
(3)
Since Sr,1 UPr,1 St U Pe,2, we have, for all y E St, UP,1 that
max max(R.())) - min(R.())) <c.
(4)
Combining equation 3 and equation 4, we obtain
max(R((FI.a) = min (R + wh.t < min (zn,,) +E
3 max ()()) min [r(y")) +
(5)
An immediate consequence of equation that
min (xL,))) < min(R.
(6)
Since y² & Pr.. by Definition 8 and equation 6, we conclude that Fbis & Press.s- Thus, we must have Th,s E Suo \ Peees... Finally, we claim that max( (xn,))) Se equation 5 implies that the condition max (xxx,))) Se min( (v"))) is satisfied, then, if y" EP Peesss. can simply set y** = =y" Else if y" P Pesss,, then this will imply by Definition 8 existence of y" E &ppeent such that min (R(vv)) < min( Ry()")), which in turn together with equation 5 implics that max(Ra(Tn,)) Xe min( R2 ()))).. Then, by the discarding rule of Adaptive 6-PAL specified in line of Algorithm 1, we must have F discarded by the end of the discarding phase, which implies that Ths cannot be in Stn- This proves that all Fhis St,0 \ Pr,2 must be discarded.
for some y** PPeess. Since
We will prove information toooe and dimension- type sample complexity bounds by making use of the termination condition given in Lemma 3.
B.3 Guarantees on the termination of Adaptive c-PAL
We start by stating a bound on the maximum depth node that can be created by Adaptive c-PAL before it terminates for given e. This result will be used in defining "good" events that hold with high probability under which f (zn,)) lies in the confidence hyper-rectangle of 2h, formed by Adaptive e-PAL, for all possible nodes that can be created by the algorithm (sce Section B.4). Our bounds on sample complexity will hold given that these "good" events happen.
Lemma 4. Given e, there crists hmax E N (dependent on E) such that Adaplive e-PAL slops refining at level hmaz.
Proof. By Lemma 3, at the latest, the algorithm terminates at round t for which we C, i.c., wf < 2. By definition, at a refining round we have
w/
11v 2'112
max
v.y² A.yEQQia (ai
UU (Zha.i)) - Le Le
((((eeete)) - Li (((het)))) 2
==1
B (xhh.i))) - BB (x + +2Vn.)
2
25

---

Published in Transactions on Machine Learning Research (08/2025)
2 of (Ihi,ie) ) + =V
me
m2
3r. (ot, (Therie)) )) +8 Σ
Vha 31/2 oy (Dharie) + Σ (Vhn)?
j=1
5=1
j=1
1/2
1/2
m
m
m
m
<
Σ j=1
(Vr.) )2 +8
(Vr))
Σ
(Vr,)) )2
>
(Vn.) )2
(7)
j=l
16m ha
where equation 7 follows from the fact that we refine at round t and from the Cauchy-Schwarz incquality. Thus, if at round i, we have
16mV/ <²,
then we guarantee termination of the algorithm. Recall that we have defined
1/2 = 4CCCC(( (VCa (2og(2h2>mmm) + h log N + max (0,-4(D///) (TDD//a)og(CG(()))))))) + C3
for positive constants C2 and C3 defined in Corollary 1. Obviously, Va, decays to 0 exponentially in h. Thus, by letting hmaz = (f) to be the smallest h 2 0, for which 16mV2 algorithm stops refining at level hmar-
hmar <ea holds, it is observed that the
Our next result gives an upper bound on the maximum number of times node can be evaluated before it is expanded.
Lemma 5. Let h 2 0 and E [N*) Let be the namber of evaluations performed by Adaptive c-PAL until lermination. Any aclive mode Thi may be evaluated no more than qu times before il is expanded, where
o² Br
9h
V2
Furthermore, we have
o² d²Br. g(viph)PCs
4h -
Proof. The proof is similar to the proof of (Shekhar al., 2018, Lemma 1). Fix 1. By definition, the vector Ur, denotes the ovaluations made prior to round t. Let yes,, be the vector that represents the subset of evaluations in V[r) made at node Th,s prior to round and let ne(22,) represent the number of evaluations in Yza.:- Similarly, let yus,, be the vector that represents the subset of evaluations in V[r.] made at nodes other than node Th,s prior to round t. For any j E [m], by non-nigativity of the information gain, we have
(( yr IV...) H( (xn.)
H( (la V Ven.)) 0.
Furthermore, let Va.. be the vector of evaluations that corresponds to the jth objective at node 2hii and Tha.: be the vector of evaluations that corresponds to the jth objective at nodes other than node Th,a prior to round I. Since condit ioning on more variables reduces the entropy, we have H H( (ln,)))mmnd S (f and thus,
H( (rn,,))) (() Bon. V.n.)) 2 0.
Using the definition of conditional entropy for Gaussian random variables, after a short algebraic calculation, we get
(I + (I
2
)
log
log( (o (1), 2 0.
2
(Kh.s, [h,)))
26

---

Published in Transactions on Machine Learning Research (08/2025)
Since k(En,,, 2h.a) is positive definite, we have ki (Dh, In.a) > O, and result obtain the following.
(ot, ne(2n,))
(x o²
o²
Thus, we have that (ot, (In, v 0² ////ne( If the algorithm has not yet refined, then it mcans that we have
m
mVn Br,
Σ
(ot))2 S 3r,mo mo² /n((nn))
j=1
Therefore, we obtain
I²Br.
me(Dns) S
V
The second statement of the result follows from the trivial observation that
o²Br
o²Br
V2
g(viph)2Cs
Next, show that Adaptive e-PAL terminates in finite time.
Proposition 3. Given such that miny el 0, Adaptive e-PAL terminates in finite time.
Proof. By Lemma 4, the algorithm refines no deeper than (e) until termination. Moreover, the algorithm cannot evaluate a node Th,i indefinitely, since there must exist some finite Tr for which B1/² ||a (2%,4)l2 S [VVl,, holds. This observation a consequence of the fact that (of, (Im,,))² < o² (xn,)))) given in the proof of Lemma 5, where ny (x),)) represents the number of evaluations made at node Th, prior to round t. Let t² be the round that comes just after the round in which evaluations made at node 2h,i- Since
(ot, (In,))) < o²/ o²/s, we conclude by observing that there exists N such that $1/2 oo (2n.s)
[V
holds.
B.4 Two "good" events under which the sample complexity will be bounded
First, show that the indices of all possible nodes that could be created by Adaptive e-PAL do not deviate too much from the true mean objective values in all objectives, and that similar designs yield similar outcomes with high probability. To that end let us denote by Theas the set of all nodes that can be created until the level Amaas where kmax comes from Lemma Note that we have
Thmas -M Xr.
Lemma 6. (The first "good" event) For any 5 E (0, 1), the probability of the following event is at least - 5/2:
F = [4j [m], VT 2 O, Vr E Thmes (2f(x) (x) 3,/20?1
where 3, 2 (lmgg2mmm Noman (T + 1)² /366) with hmaz being the deepest level of the tree before termination.
Proof. We have:
1 1-F(F) = E [1j E [m], 3r 2 0, E Thmes 1ff(x) (+(x)))((x))) > 84/2 (
< E
ΣΣ
(1F((()) x1(x0) 8. -3/2o((1))
x Timaz
27

---

Published in Transactions on Machine Learning Research (08/2025)
ΣE
E T (P((s)
(IPt)) - -x of)2 [-1-1]
(8)
10 TTTmaxx
B - 22
j=1 220
2012
(9)
Flr20 #200EE7mman
< Nnmar +1
-212
(10)
T20
2 Bmart +1
(2 N Nhmur (T 1)2/1(3))
+20
5 6
8 2
(T 1)+
2 R
where equation uses the tower rule and linearity of expectation; equation 9 uses Gaussian tail bounds (note that ((x) ~ (ie,, (x), (x)) conditioned on Vi-,)) and equation 10 uses the fact that for any 1, the cardinality of Th..... is 1 N + Nhhmu = (Nhmur+1 1)/(N- - S Nhmart1, since N 2 2.
Next, we introduce bound on the maximum variation of the function inside region. First, state result taken from Shekhar et al. (2018) which this bound is based. Suppose {g(z); X} is a separable zero mean single output Gaussian Process GP(O, k) and let / be the GP-induced metric on X. Let DJ be the metric dimension of X with respect to I. By Lemma 1, we have that if D' < 0o, then there exists a positive constant C1 depending on 2D' such that for any z I diam(X)) we have N(Y, 2,1) S C2 - -2% Let m = Em21 (n-1) Vlogn, n, 1/2 = Σnzi 2- (n-1) Vn, and define
C₂ = 2 log log( /6) and C2 1n 122 221 log
Lemma 7. (Proposition 1, Section 6, Shekhar et al. (2018)) Let xo X and B( b, X be I-ball of mdiius b > 0, where I is the GP Ciiinduced metric on X. Then, we have for anyy u >> 0
lø(x) - g(00)l w(b) ] Sen
P
sup (E)(
where w(b) = 4b (VCo+
+2u 2u (0, 4D' log(1 (o((1))))3 + Co3) C2).
Remark 3. Note that by Remark 1, for every j E [m]] the covariance function (x,2x) is continuous with respect to the metric li, and thus, the process (x); E X} sepurable.
Corollary 1. (The second "good" event) For any E (0,1), the probability of the following event is at lenst 8/2:
F2 = {Th 0,Vi [N [m]
1f((x) - (P(=))P(ann))) S Vn)
sup Baa
where
Vn = 1C:CCuupp"" (VC2 + +222 2log(2h772m/66)) + h log.N N + max(0,,4(D))))) -4(D:/a) (og(()))))(((C( + Cs}
and C2 and C3 are the positive constants defined below which depend on the metric dimension D of X with respect to metric d.
Proof. Let Dj be the metric dimension of X with respect to d. By Lemmna 2, we have that Dj < Di/a, where
DJ is the metric dimension of X with respect to Ij, for all j E [m]. We also have constants Of associated
28

---

Published in Transactions on Machine Learning Research (08/2025)
with Dj, such that N d) N(X,r,1)) < Cir2P, Let C1 max, C.. Also, let
C = 2 2ogg(2( /6) and C3 = 7h1 + 72 722 log
Using Lemma 7 and Remark 2 we lct
w(b) 4b (V02 + 2u + max 4D, log( (1/6} + C2s
Now let 1 logg d + logm + -log.N N 2 /6). We have
BE [f(x)) ((((n,)) > (CCa(on))))
1- P(F2) = PP
3h 2 0, EiE
J 3j E [m]
sup
Σ
Σ
P
sup
(x) f (I (C(((upp()))
420 Is
DE B(
Σ
Σ
sup Wc Cu
(f(()) - (((n))) > ((Cu(1np()))
(11)
A201SigNA
mN M (m/*)) 8
Σ
1201SISN
A20
where for equation 11 we argue as follows. Note that by Assumption 1, given x, E X' and j E [m], we have 15(x, y) & Ckd(a, y)a. In particular, letting y be any design which is viph away from Thes under d, we have 15( y) S Cnd(an,,, w) = ))( This implies that B r,4y) C B( Cs (x(op")) ,4),, where = =15(#n,,,3)) Note that we have B(T,s, 1,, = B( mip",al d). The result follows from observing that the probability that the variation of the function exceeds w (()())))))) is higher in B(IR, (")))p")",d then in B(I,, U2p", d), since B(I U1p", d) [ B( Cu(upp") yo, .1)).
B.5
Key results that hold under the "good" events
Our next result shows that the objective values of all designs X belong to the uncertainty hyper-roctangles of the nodes associated to the regions containing them in given round. To that end, let us denote by (x(x) the node associated to the cell Cz(x) containing at the beginning of round t. Also, let denote by hz(x) the depth of the tree where ca(x)) is located.
Lemma 8. Under events Fi and F2, for any round t 2 before Adaptive e- e-PAL terminates and for any E X, we have
f(x) E R((c((x))
Proof. First, let denote by so < 81 < < 8n the sequence of stopping times up to round t in which the original node containing design was refined into children nodes, so that we have C S C.,, ( _... C Co(r). By the definition of the cumulative confidence hyper-rectangle, for cop (x), we have
Ro, (I)) = Ra, (Cao (C (x)) n Qr (Cop (x))
22 (x)) n Qu -1 (Cto (x)) n Q., (x)
Ro (z)) Q sm (Coo (x)) n Q (Cep (I:)
and since Ro(c,o (x)) Rm we obtain
81 Q. (c,, (x))
RS, (x))
s=1
29

---

Published in Transactions on Machine Learning Research (08/2025)
Similarly, for Css (z) we have
Reg(Css (x)) R (c,, (2)) (cx
Ray (Ca, (x)) (x)) (cg
where
Rsy (Css (2)) R.,, (p(Cs, (x))) Ro, (Cao (x))
Thus, we obtain
81 ( n Co(ca((1))
(ñ #=i1+1
n
52
R2, (Ca (x))
Note that (z(2) = Cs, (x) for all such that 8; s S 81+1 for each i E (O...., 1}; and cx(x) Coa (x) for all such that Sn+1 t. Thus, continuing above, we can write
(Ó n 8=8
Re(c((x)) = (n(coco))) n...n
Qa(Cen (1)) n
(c(c
==1
n (c)(
Based on the above display, to prove that f(x) (x))) it is enough to show that f(x) Qe(c(())), for all 8 & t. Next, we prove that this is indeed the case, by showing that for any & and j [m], it holds that
[x(c(())) = (x) - Va, s ((x)
+ (( = (z(c(()))
(12)
To show this, first note that by definition
(c(((())) max (cx(z)) 33/202 of, (ca(x)), pe, (p(c,(x))) 01 (plc.(x))) (n)
and
(=(c,(z)) minfrl, (c,(x)) + 22/20 (c.( ml, (p(c.(x))) 2 (p(c,(x))) V
Hence, we nced consider four cases: two cases for (x)( and cases for (c,(,)))) Let j e [m].
Note that under events F1 and F2, we have
# (cx(z)) - 81/2 of (c.(x)) S ((((())) S pl, (c.(z)) + $1.2 (c.(z))
(13)
and
((e(())) - Vhn(2) S
Vir(s)
(14)
The following inequalities hold under Fj and Fz.
Case 1: If we have Lg(cs(z)) = μ4 (c)(x)) - 82, 0f (c.(z)) - Vnn(z): then
(c(((x)) = (c,(co - B1/20 (co(z)) - Vhn(x)
< ((c((t) - Vh.
$ (x)
where the first inequality follows from equation 13 and the second inequality follows from equation 14.
30

---

Published in Transactions on Machine Learning Research (08/2025)
Case 2: If we have [f(c)(x)) m (v(c(()))) 3h. 0g (p(c,()))) Vh,(=)-1 Vha(x); then
[[(cc(=)) = p²t (p(c)(z))) o4.304 (p(c.(x))) (n) Vx,(x)
S (x)(c(()))) (1, (a)(())
- {c((x)) - (x)
{x)
where the first inequality follows from equation 13; for the second inequality use the fact that (x belongs to the cell associated to (x), and thus we have that (((((c(x))) ((c(())) + (a)- the third incquality follows from equation 14.
Case 3: If we have (c((())) = (c,()) P..20 (c.(x)) Vn,( then (()) s ((c)(t)) + Vn,(a)
S (c,(t)) 31/2 0f, (c.(z)) Vh,(w) = (z)(
where the first inequality follows from equation 14 and the second inequality follows from equation 13. Case 4: If we have (3(c)(x)) = p2, (p(c. + 3y.² og, (p(c)(x))) + (1) Vh,(s), then
((x < (z)( + Vnn(z)
s ((((cc(=)) + + (n) (a)(a)
s m (p(cc(()))) of (p(c.(x))) + (h)(t)-1 + Vhr(z)
= Uc(((())
The analysis of this case follows the same argument as the one of Case 2. This proves that equation 12 holds, and thus, the result follows.
Our next result ensures that Adaptive c-PAL does not return 'bad' nodes.
Lemma Let x E X. Under events Fi and F2, if fxx) & (x))), then E P.
Proof. Suppose that f(x) & (x) Then, by Definition 3, we have f(x) E f(O(x)) - 22 -RT, that is, there exists x² E O(2) such that we have
f(x) + 2E 3 f(x").
(15)
To get a contradiction, let us assume that x E P.. This implies that there exists 2 such that (x) is added to P, by line 16 of the algorithm pscudocode. Thus, by the e-Pareto front covering rule in line 15 of the algorithm pseudocode, for each Thii E Wr, we have
min(R.(c.(z)) +e e f max (Rx
(16)
In particular, we have that min min(Re(ci (Re(c:(T)) + e A max (R (cx((()(("")) (note that we may even have cx(x) = c (x*)
and this would yield the same result), which, together with Lemma 8, implies that f(x) A f(x"). This contradicts equation 15.
Now since have I, x, Cr(x), must have (c)()(((())) f(x) and f(**) 3 (cx((((c:: by Lemma 8, which implies that f(z) 1 f(x"), thereby contradicting equation 15.
Next, let us assume that (xx)) ) & Wr. This means that there exists round 81 I t at which C2 (x*) is discarded. By line of the Algorithm 1, there exists y/1 E Ppeesss, such that we have
max(R,, (x*))) - 3 min R,, (v1))
(17)
Assume that the child node (x(1)) of y1 at round (due to possible refining in the middle rounds) is still not discarded by round i, i.c. c+(11) E W.. Then, by equation 16, we have
min(R.(c(())) A max (ee((((()))))
31

---

Published in Transactions on Machine Learning Research (08/2025)
which implics that
(in(R(((c()))) + f min(B((c(n))))
which in return implies that
min min(R((c((z)) + (in (v1))
due to the fact that min(R,, (v1)) = min(R,, (c((v) min (R, (cr(a))) Thus, by equation 17, we obtain
min(R.(c((z)) + max (Cos (x )]) c,
or equivalently,
min(R((c((z)) + 2e f max max (Ca, (x
By Lemma 8, this implies that f(x) 2E $ f (xx". contradicting equation 15. Hence, remains to consider the case cx(1)) & W/-
In general, let the finite sequence of nodes |i ,/, V2....... ...] meaning that, for each i E [n 1], the node y, stopped being part of P Press,acs1 at some round 8,41 by satisfying
T be such that all the nodes y1 to In-1 are discarded,
min Re (Copn (Ui))) x ( (16+1))-
Suppose that (y)) is active round t, meaning that (um)) E We (note that we can always find such an n since the algorithm terminates and that we choose the sequence such that it satisfies that condition; furthermore, we have $1 < 82 .... Sn S t). Since we have (vn)) We by equation 16, we obtain
min (c(((()))) E max max(RR(c((ux)))
(18)
Note that equation 17 implics
max (Ro, (c,, (x*))) - 3 min R., (21)) < min( Ryg (Cog (31 x min( Rx, (32)) x min R.y (U2)))
- min Re,, (wn)) - (c
which in turn implies that
max Ro, (cr, (x"))) < min min(R.(((((w))) 1 max (C
This, combined with equation 18 implies
min (in(R((c(())) + max max(Ru, (Cap (x*)))
Thus, in all cases we have that f(z)+ 2e A f(**), contradicting our assumption. We conclude that x & P.
Next, we show that Adaptive e-PAL returns an e-accurate Pareto set when it terminates.
Lemma 10. (Adaptive c-PAL returns an e-accurate Pareto set) Under events F, and F2, the set P returned by Adaptive e-PAL an e-accurate Pareto set.
Proof. Let x E O()). We claim that there exists z E P such that f(x) Ie f()). Note that a E P, then the claim holds trivially. Let us assume that x & P. Then, there cxists some round 81 at which Adaptive e-PAL discards the node c, (x). By line 9 of the algorithm pseudocode, there exists node z P Press.sy such that
max (Ro (Ca, (z))) 3 min (21)) te.
32

---

Published in Transactions on Machine Learning Research (08/2025)
By Lemma we have
f(x) max (ax (Ce, (z))) min (R,, (21) +e f(21) te.
(19)
Hence, 21 E P, then the claim holds with =
Now, suppose that 21 & P. Hence, at some round 82 2 $1. the node Ce2 (21) associated with 21 must be discarded by Adaptive e-PAL. By line 8 of the algorithm pseudocode, we know that a node in Pesss,s cannot be discarded round 82. Hence, (x2(2)) $ Peess,22 Then, by Definition 8, there exists node 22 As such that
min Rog (Cag (21))) < min min(Rsp (22))
which, by equation 19, implies that
f(x) 3 min( (,,, (z1)) +
min Roy (Ces (21 ]]]
min( Rxg (Cag (2n) )) +
min R (2)())) +
3 (22) +
Here, the equality the follows since the child node inherits the cumulative confidence hyper-rectangles of its parents at prior rounds (see refining/ewe evaluating phase in Section 4), and the second inequality follows from the fact that the cumulative confidence reper-rectangles shrink with time. Hence, f(x) Ze f(2)). If 22 E P, then the claim holds with == 22
Suppose that & P.. Then, the above process continues in similar fashion. Suppose that the process never yields node in P. Since the algorithm is guaranteed to terminate by Lemma 3, the process stops and yields finite sequence [zI, of designs such that & P...., 2n $ P. For each i E [n 1], let 8;41 E N be the round at which Co. (2,) discarded; by the above process, we have
f(z) = min (Baus (2i+1)) te.
In particular, fx) I min( (zn)) + e. Since 2n $ P, there exists a round 8n41 2 8n which the node C (zn) is discarded. Consequently, the node Cs., (Zn) Ppess,.. This implies that the condition of Definition 8 is violated at round 8n+1, that is, there exists 2n-1 Asnts such that
min min(R (Cruts (zn))) min
(R min(R.444
(zn+1))
(20)
At this point, important to clarify that zot1 cannot belong to the sequence [Zi...., znl of designs. Note that, by assumption, we have
f(x) z min(R,, (21) c N min (c,, (21))) +
min, (22)) 3 min Reg (Cog (22)))
min(R (2n)) + E - min min(R.... Ro (Cenen (2n))) +
< <inn (ni((R....22441)) (2n+1)) +
Due to the strict domination relation between the nodes in the sequence (which is determined by Definition 8), no two nodes can have identical confidence rectanles at the time of removal from Ppess,s: for (si...., sa+1). ). Moreover, such a condition implies a strict ordering nodes in the above sense, which implies that 2n+1 & (2,,..,,,, 3x}. Hence, equation 20 and the earlier inequalities imply that
f(x) 3 min R (2n)) te min Rs,, (Comes (zn))) +
33

---

and ej is the jth unit vector in R This completes the Published in Transactions on Machine Learning Research (08/2025)
3 min Re (Csm1((2n))) +
< min Re (Rx+1)) +
3 (=n+1) +
where we have again used the shrinking property of the cumulative confidence hyper-rectangles in the second inequality. This means that 2x+1 is another node that e-lominates æ but it is not in the finite sequence [Z...... =n]". This contradicts our assumption that the process stops after finding n designs. Hence, at least one of the designs in .n T is in P; let us call it This completes the proof of the claim.
Next, let 1e E {(O())) T... Then, there exist ((2) and p' E TRT such that p f(x) p². By the above claim, there exists 2 E P such that f(x) = f (2) + e. Hence,
1 3 μa + p = (xx 3 f(z) +
This shows that for every μ E f(O(Z)) RT, there exists E such that 1e 3e f(z). By Definition 3, we have Zx(x)) f(O R... Hence, for every 1a E (x),), there exists μ² E S(P) such that / Ie p². On the other hand, since we work under F1 F2,2, Lemma 9 implics that f(P) S Ze()). Therefore, f(P) an e-covering (x( (Definition 4 ), that is, is an 6-acourate Pareto set. (Definition 5).
B.6 Derivation of the information-type sample complexity bound
In this section, we provide sample complexity upper bounds that depend on the maximum information gain from observing the evaluated designs.
We begin with an auxiliary lemma whose statement is straightforward for the case
Lemma 11. Let T 1, x E X. The matrices K Kir + Enr and kypy (x) K [r] + E kizy are symmelric and positive definite. In particular, (x) + (mm))))) > 0 for each j E [m].
Proof. Note that Kinj is the covariance matrix of the random vector f [f f (āT) ((rr) it is symmetric and positive semidefinite. Being a diagonal matrix with positive entries, Ejr is symmetric and positive definite. Hence, K(r) + E(r] symmetric and positive definito; and so (K[r) E(r))= The latter implies that (2) + E (Ty) (x) is symmetric and that
hence,
w (K
Enn kir (x) (1:r((2) w) 12 + Eprr (Nir
( (z) ww) >
for every w E Rm with w # 0. Therefore, a (z) (K) + Eny) M (x) is positive definite. Let A(1) > 0 be its minimum eigenvalue. Let j [m]. By the variational characterization of minimum eigenvalue, we have
d0 e)
min wERm: ||
T aww A(1) >
where aهd (kim)())) + proof.
Recall from equation 2 that, for each t 2 1 such that S, + 0, w. we(Iheete) denotes the diameter of the selected node Thei E A, at round t.
Lemma 12. Let 8 (0. 1). We have
Σ wr, S V (168,, o²0m),
where C C=--²/logg /lg((1 + 22 and Yr, is the marimum information gain in T, evaluations defined at the end of Section 3.
34

---

Published in Transactions on Machine Learning Research (08/2025)
Proof. Let T [Ta] and j E [m]. Note that the rth evaluation is made at round t, and we have 72 1. Hence, we have
By (The, se, Bi, (Dhee Se,)
mminnfh (Iher de, B otc, (Ihe, se, ) the (p(#m), de, )) 3113//100 (p(zke, de, )) + Vhe, -1}
-max(w2, (ohe B/,,2 02 (Ther ) Hh, (p(ater (e, 31,32 o2 (p(oter (ir Vhep -13 dn )) B 10 (1 diy + Vni, -1}
=
- der ), -
3/ 12 2/12 - (The, de,) 12 (p(The, ( (e,) Vne -13
(Fhe,
- -max(pi-1(The,
We can bound this difference in two ways, so that we can use information-type bounds and dimension-type bounds. In this result, we focus on the information-type bounds and write
Bi, (The, v., B₁, (Ihe,
S / (5hee, )1,) B7 00-10-- 1 (3 12 (10, 3/2 1
/ /2 o (T.))
(21)
Since the diagonal distance of the hyper-rectangle Q₁ (Fheerder) is the largest distance between any two points in the hyper-rectangle, we have
By - 1/ 1
max U.v/ E R2 (T mey)
11y 1/112
U. L.V'EQi, (sree, se,
Ut, (2he, Se,
LT (Thee sr, )1(
m
UP (Thee Ll, (Ihee
Bi, (Zher Bi, (2 + 2Vmer
(22)
2/ 1 ( + 2Vher)
(23)
Σ 8 (K ( +2 m
m
m
V V
(Th )+ + > (V
5=1
m
<4 4
Σ 3, 1,,
1=1
1/2
1/2
m
m
+
(Viec )2
Σ
3r 10 (20h)
+
Σ (Vnn.)
(24)
1=1
==1
m
<4
Σ
3 10
(Ihher see ))2 +2 >
B, 1,-1007_1(0ee ))2
r=1
1=1
1=1
+
Σ
3 10 ))?
(25)
]=1
35

---

Published in Transactions on Machine Learning Research (08/2025)
Ta T7
S 16
7 (Th ))²
(26)
j=1
T,
m
163,, _²
2 1 (The, ))
$ 163,, o²c
log(1 1 + (0- ))2)
(27)
$ 163, o² (m.
(28)
$ 163,, 163,, J2
(29)
where -==0"//og(( + -). In this caleulation, equation 22 follows by definitions; equation 23 follows by equation 21; equation 24 follows from Cauchy-Schwarz inequality; equation 25 follows from the fact that we make evaluation at round 6, so that we have
2/3 1 fe. )11 = 1/ (Ihe )l1 > Vine, ll2
by the structure of the algorithmm; equation holds since 3, is monotonically non-decreasing in t (see the definition of By in Theorem 1); equation 27 follows from the fact that S C'log11 s) for all S and that we have
(o- (Iher ))
(K55 (1 dey the (o (K 1/r-11) kir- ( )T,
(e. )oo)
S 205 (1h Thiri))
00-
thanks to Lemma 11 and Assumption 1; equation 28 follows from Proposition 2; and equation 29 follows from definition of the maximum information gain.
Finally, by Cauchy-Schwarz inequality, have
Wer
<
Wt
S (163,, o²Cmy..)
T=1
which completes the proof.
Lemma 13. Running Adaptive e-PAL with (Br)reN as defined in Lemma 6, we have
163,, 163r,02Cm77.
Wt, S
Proof. First we show that the sequence (Wi)ee is a monotonically non-increasing sequence. To that end, note that by the principle of selection have that (I S Wr-1- On the other hand, for every X, we have (x) S (z) since R, (z) C (x). Thus, Wi (xlhaa)))) I w (zh...)) So obtain Wa S W1-1
By above and by Lemma 12, we have
Σr We
163,, o² Cm
We, <
To
To
Finally, ready to state the information-type bound on the sample complexity.
36

---

Published in Transactions on Machine Learning Research (08/2025)
,t""". be given with = minje[m] e > O. Let å E (0.1) and D D1. For each 2 0, let Vn. be defined as in Corollary 1; for each E N, let Br be defined as in Lemaaa 6. When we run Adaptice E-PAL with prior GP(O, k) and noise N(0, o2), the following holds with probability at least 1- An E-accurate Pareto set can be found with at most T function evaluations, where T is the smallest natural number salisfying
Proposition 4.
16 <E
T
In the ubove expression, C represents the constant defined in Lemma 12.
Proof. According to Lemma 3, we have Wt, <e In addition, Lemma 13 says that
S We 163, o²Cmi,.
We use these two facts to find an upper bound on T, that holds with probability one. Let
163,0"Cm7r < E
T mimin min TEN:N
Since the event {r, = } implies that (w < e), we have PI(t, > T) = 0.
B.7 Derivation of the dimension-type sample complexity bound
In order to bound the diameter, we make use of the following observation. Remark 4. We have
V4 < N1 := a
h+1
The next lemma bounds diameters of confidence hyper-rectangles of the nodes in A, for all rounds t. Lemma 14. In any round 2 1 before Adaptive c-PAL terminates, we have
up S L.V
where L = (4N7 + 4N7(2N1 + 2) (2N; 2)
Proof. We have
J/ = w/( (Itheete)
=
max
1/8 v2(l2)
E.
11l 11y-~'11 -u'l)) "- -(1Ui(2nent))) Le Le(an..)))l)) Σ
(xhr.tee) - B (2 + 2V )
max n. (Qh()))))))
202 of, (p(xh, (2N1 + +2)Vo.) )²
(30)
31/2 of (p( + (2N, + 2)² m
48,
( (p( (p(2 4(2N; + +2)
Σ (Vn.. )²
m
m
< 4
(V 4(2N1 + 2)
Σ
/ of (p(ah) V), + (2N1 + +22
Σ (Vh.))
(31)
te
j=1
1=1
1/2
< 4
(Vh,-1)² 4(2N1 +2)
Σ
3r, (o (p(ch..))))
Σ (Vrr,) 2
+ (2N1 + +2)²
Σ
(Vr.)² (32)
1=1
1=1
==1
37

---

Published in Transactions on Machine Learning Research (08/2025)
m 4 4 (Vn,-1)* + 1(N1 + 2 ==1
m Σ
m
m
(Vh
(1
Σ
(Vh,))
+ +2N1 + 2)²
Σ (Vr.)*
(33)
y=1
S m (4NP + (2N + + + 2) ==
(34)
In the above expression, equation 30 follows from the fact that for j E [m]] and 2 1
(Thr, By (Threte)
= min( (Dhnnh)) + 32/202, (Inerses ub, (p( + -/2/204, o (p(Zie, in) + Vnr-13
max(us (Itande) - -2120 ot, (Ihene) ph (p(Ibee))) / 0z (p(2ir,tt) Vo--13
S me, (plamente)) + 31/2 of, (p(xnese)) + V ue, (p( + 31120 (p(xn, + Vha-1
< 2011204 ot (p(In)n))) + 2
s 2/ og (p((k,,))) + 2N, Vh
(35)
where equation 35 follows from Remark 4. equation 31 obtained by observing that the node p(ara, has been refined, and hence, it holds that 8 ||o (p(Zn,,))))l S I|Va,-1l2- equation 32 follows from application of the Cauchy-Schwarz incquality. equation 33 follows again from the fact that 2 ||o (p()nn...))) S |VV lla and equation 34 follows from Remark 4.
Let denote the set of rounds in which Adaptive e-PAL performs design evaluations. Note that |8| = T. Let t, denote the round in which the algorithm terminates. Next, use Lemma together with Lemma 14 to upper bound Wt, as function of the number evaluations until termination.
Lemma 15. Let 8 E (0, 1) and D > D1. Running Adaplive e e-PAL with 3, defined in Lemma 6, there exists constant Q > 0 such that the following event holds almost surely.
-10+a)
Wr, SKIT, D+20 (log
D420
+ K2T, D+2a (log T,) D-2a
where
VLQO Br. K1 CLufU (0- -00((0)) -1)
K2 = AVICku
(C22 + 2log(2H2 + log + max(0, -4(D//a) log( log(C((v1p"))0)} + Css
log T, - log Tx)
log(1/p)(D 2a)
Proof. We have
Wi, Eieg We
VI Vh,
(36)
To
Ts
where the first inequality follows from the fact that W, S w for all 2 and the second inequality is the result of Lemma 14. We will bound Eiee Vh, and use it to obtain bound for equation 36. First, we define
S = Σ Vh. and Sg = Σ Vha
LEE: heSH
IEE: h.2H
and write Eiee Vn, S1 + S2. We have
S = Σ ET
Vr, 11,1--1000 -NT(LE)
E1
S2ANC
38

---

Published in Transactions on Machine Learning Research (08/2025)
ΣΣ hCH
VA, I1, - E)
Σ Vil((220") -a
(37)
hCH
VnQ(u2p") DO2 3T
(38)
hCH
o²
Σ Q(02p")) WEH
(39)
Cx(Vip²)a
Qo
Qr p DD40a]
Σ p p-(D+ajh Cheftuz U2
(40)
Ckufup p (D
In the above display, to obtain equation 37, we note that for a fixed the cells X are disjoint, a ball of radius u2p should be able to fit in each cell, and thus, the number of depth h cells is upper bounded by the number of radius v2p" balls (X, 202p", d). The rest follows from Lemma 1, which states that there exists positive constant Q, such that M(,, 20zp", d) N(X, u2p", d) S ((2ppt)- For equation 38, upper bound qa using Lemma 5, and equation 39 follows by observing that Vn, Ca(vip")).
pack in (X,d), which is in turn upper bounded by
Since V₁, is decreasing in h, the remainder of the sum can be bounded as
S2 Σ Vr, E
Σ
Vn Vn (K2/ HaaapHa
(41)
3EE
Combining equation 40 and equation 41, we obtain
Σ Vn, < Q0?Pr. p-(D+a)H
Croffay p p-(D+a) -1 + (K2/ V D
(42)
AEE
Since
log - logglog Ta)
D12a
H
loog log T
log(1/p)(D+ 2a)
we have
p ((D)aa)
S Ta D+
D+a
(log Te)
D+
(Bia)
and TeP Ha < p. 1- Di20 (Log T.) D-20
HapHa
Finally, we use the values found above to upper bound equation 42, and then use this upper bound in equation 36, which gives us
wr, SVT..
Q0² Cuufu (p (D++)) -1)
Ts D+20
(log Ts)
-(0m) D4z0
+ (K2/ (K2/VT)TT D+za (log Ts Diza
Finally, ready to state the metric dimension-type bound on the sample complexity. Proposition 5. Let e = (e each 2 0, let Vú, be defined as in Corollary 1; for each r E N, let 3 be defined as in Lemma 6. When we run Adaptive e-PAL with prior GP(O, k) and noise N(00 the following holds with probability at least 5.
be given with e = minjeim] e¹ > 0. Let ô E (0, and > D1. For
An e-accurale Parelo set can be found with at most T function evaluations, where T is the smallest natural number satisfying
(B+a)
6420 (log T)
6420
+ KKT (log T') Dizo <E,
where K1 and K2 are the constants defined in Lemma 15.
39

---

Published in Transactions on Machine Learning Research (08/2025)
Proof. According to Lemma 3, have wi, < In addition, Lemma 15 says that
((+t) B-20
1 SKIT, 6-20 (log Tx)
+ K2T, 6+ (2) ntan
We use these two facts to find an upper bound on T that holds with probability one. Let
-10 r ::N: KIT D+30 (logT)
+ K2T D420 (log 7) pi20 < c)
T = min
0420
Since the event {T, = T implies that t < <c), we have Pr(r, > T) = 0.
B.8
The final step of the proof of Theorem 1
We take the minimum over the two bounds presented in Proposition and Proposition 5 to obtain the result in Theorem 1.
B.9 Proof of Proposition 2
First, let review some well-known facts about entropies. For an m-dimensional Gaussian random vector g with distribution ((a, b) with E R= Rmxm the entropy of is calculated by
H = H(V(a, b)) log [2teb].
More generally, if is another random variable (with arbitrary measurable state space H) and the regular conditional distribution of given h is (N(ah),, b(h)) for some measurable functions H RM and
b: H + mmm, then the conditional entropy of given h is calculated by
(ighh
E [log 2Teb(h)])
2
Lemma 16. We have
1 log Im + -2k
(wmii Σ
where (a(ā1, = 1((21,
Proof. We have
[yym) (ym) - (ymllf
H(y,, H(yr-yr-1) H (yrr(fp))
= H ((rrlurr-)) + (vp--1) - H (wr))
Re-iterating this calculation inductively, obtain
(ymifm) = Σ
H(y (z)1) (ypr))
T=2
since 9/1 = y1- Note that
T
T
Hyrrlfm = H((()) + +6,,...,f(ān)) +er(fm) = Σ H(E,) = log 22tea I
2
r=1
On the other hand, the conditional distribution of yr given V---1 (( k; (#r, Rr) + o² I²Im) and the distribution of yı is ((2,, + Im).. Hence,
T
(y f(n) = Σ H( B (1) + H(y) - H H(mlfr)
2
40

---

Published in Transactions on Machine Learning Research (08/2025)
T
1 log (2 + I² 2
2 log 2 + I2mm]] +
log 2 I
2
T log 12mee 2 mm
log ( FT) + 0² mm)
2
T
log |2 2 In (o 1 [mm]
log |2Tee m
2
2
T
log 12Teo² mm
log la Tx) + Im) - log [2Tea" Iml
2
T
log la -k,, (k,, + mm
[T)
7=1
Lemma 17. Let a = (ai))ss(m) be a symmetric positive definite m x m-matriz. Then,
a + Im 2 max (1 + azz)-
jE|m]
Proof. Let 0 < X(1) ... S A(m) be the ordered eigenvalues of a. It is easy to check that À E is an eigenvalue of and only if an eigenvalue of + I In particular, + A(m) the largest eigenvalue of Im so that
II (1+) = II (1 -101) (1 (1+ A(m)) 2 (1 + A(m))
a + ml
(43)
jE[m]
jEim-1]
On the other hand, thanks to the variational characterization of the maximum eigenvalue A(m), we have
(m)
mERm max x aax e, ee,e Ajj
(44)
||=||=1
for each j E [m]] where ej is the 8th unit vector in R The claim of the lemma follows by combining equation and equation 44.
Next, we will make use of the lemmas derived above to complete the proof. Note that
T
[ym: f(m) =
log Im + - ē7)
max log (1 + o jelm m
22tl 1--1 (ă, i+))
max log + o ( (}² J
1
Σ
log(1 + 0 (o,
2m
jE[m]
where the first equality is by Lemma 16 and the first inequality is by Lemma 17. Hence, the claim of the proposition follows.
41

---

Published in Transactions on Machine Learning Research (08/2025)
B.10
Determination of and CK for Squared Exponential type kernels
For Squared Exponential lype kernels, the covariance function of objective can be written as:
kr) ve
where | yl and L and the length-scale and variance typer-paramelat of the jth objective.
Hence, by Remark 1, the metric by induced by the jth objective of the GP on & is given by:
- 2k(()) - 2h(0)e i2 = 22 e -a) 2 (1x,8) =
L
Thus, we can set C = 22u
L and a = in Assumption
C The proof of Proposition 1
In this section, we provide a constructive proof of Proposition 1, which is an extension of Example 1 in Shekhar et al. (2018) to the multi-output GP set setting. We restate the proposition here for convenience.
Statement. There exists multi-outpe GP f, with covariance function satisfying Assumption 1 and sequence of noisy obscrvations made on f, such that we have
[yr,, f(n) 2 S(T)
Proof. We provide constructive proof, which is an extension of Example 1 in Shekhar et al. (2018) to the multi-output GP setting. First, let X' = [0. 1]. Let j E [m], x X, and let us define
(()) Σ Xi (33'z 1)(2 3'r) L.) (3'x 23 3'x)((( R&))
where, for cach E [m], (a:y) a non-incrcasing sequence of positive real numbers with āi S 1; (Xig)=ii))1 sequence of independent and identically distributed standard Gaussian random variables;
and we let L, = 13-1,2.3-7 for all 2 1, Rs = 12.3 for all i 2 2, and Rg = -2-33 1,-,3--- for = Note that we have
X U (L.UR.)
and moreover, LA, Ri, Lz, R2,... do not overlap, thus they partition X. Therefore, for any x X, there exists i(x) such that E Li(a) U Ri(a) and & Li U RG for any ( So we have
(x)) = Xij ((3100) - 1)(2 - 31(x) Iuww) (3)(x) x -) 30(2) xI)x) E Ra(w)))
Let x' E X and j. [m]. We define f(x)= = Moreover, we let k(x, denote the covariance matrix of the m-output GP (f))))xx. Note that we have
(f (x)..., f=m)) Note that we have E[f(x) O
(() 0, for #1.
due to independence of X,, across objectives which implies that
1u11 (,,))))))))))))))))) x))
k(xx, x))
0
mm (x)
42

---

Published in Transactions on Machine Learning Research (08/2025)
Now let A (app) [. E R be square matrix such that ||,l|2 = 1, for all E [mm, where A, denotes
the jth row of A. Furthermore, let us define fz) Af. Let be the covariance function associated with the m-output GP (f(x))=exx Assume that T designs of the form x; 1/33 + 1/(2 3*) are selected for evaluation and subsequently the noisy observations y, are obtained, for i T. Note that in this case have i(z,) i. Now we explicitly calculate the variances of these evaluated points at all objectives. Let I m and S T. We have
( x.) = B[(AS ((AA()))) = (,),,,)))) = Σ nad (a,,
where the third equality follows from the fact that k(z, is diagonal. Now we have
(xx)) = Xis ((3'z
1) (2 3'x) I(x E L.) (3'x - 2) (3 3'x) I(x E R:))
= Xai 3r 2 2.
1
1
1)
32
(1 3
-213) )) 4ā, Xij = aiy X1g
Therefore, we have that kM (x;, = El( (x:)) am, from which we obtain
1 (I),
ci S 11411 =1
(45)
using the assumptions on the sequence (āa) and the matrix A. The observations at different designs are uncorrelated, hence independent, by the choice of the designs, and this implies that the posterior distribution is the same as the prior distribution. This, together with Proposition 2 implies
T
T
rr 2 Tyyrrs
2
log
(o
=
log (1 + o 2
m
i=1 j=1
T
ar o²
002/0²
1 2m
07
log
1+
T
T
2m
2m
/
d + 0
where in the third inequality we have used the fact. that the sequence (a:j) is decreasing and in the fourth inequality we use the fact that log(1 + x) 2 x/(1+ (1+++)0) z). Thus, we obtain TT = ST(T). By Theorem 1, we see that the information-type quantity VC3rmr/22 /T increases logarithmically in and the metric dimension-type
K2T D420 (log T) dizz decreases exponentially in T, for any choice of -(D+o)
quantity K K D=2a (log T) D > Di and 0 < 11
D+20
On the other hand, for a suitably chosen metric d, the first part of Assumption 1 holds. Similar to equation 45, it can also be checked that k3d (x. S 1 for all x E X. Hence, the second part of Assumption holds as well.
43


Reviews:
[{"review_id": "1h4cZWndpx", "reviewer": "Reviewer_E2JZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- While long and technically dense, the submission is generally carefully written and some care has been taken to make the rather complex algorithm comprehensible.\n- The approach adopted appears technically sound and well-adapted to the problem at hand. To the best of my knowledge, it is novel. \n- The authors provide a rigorous sample complexity analysis that includes both metric-dimension-based and information theoretic bounds. I cannot comment on the novelty or correctness of these bounds, as I have not gone through them in any detail.\n- The algorithm performs well in a (rather limited) empirical evaluation.\n\nWeaknesses:\n- While the submission is generally carefully written, I believe readability could still be improved. I would suggest that the authors focus their main exposition on the core components of their algorithm and relegate more of the details to the appendix. For example, while it is a strength that the algorithm is applicable to well-behaved compact metric spaces, the various complications that go with the generalization beyond, say, a euclidean input space (introducing metric dimension etc) significantly complicate the exposition and do little to illuminate the core ideas of the algorithm. I believe a streamlined exposition could make it much easier for readers to digest the core ideas. For example: \"While we have assumed in the above a euclidean input space, in fact our algorithm immediately generalizes to well-behaved compact metric spaces; for details see Appendix XXX.\" This is but one possible example. I believe the broader theme of focusing on core ideas could be profitably applied to the manuscript as a whole.\n- The empirical evaluation is quite limited. In particular it only considers: i) objectives drawn from a known GP kernel and doesn't consider the realistic case of kernel mis-specification; ii) only considers the nearly deterministic low function noise scenario; iii) only considers one-dimensional inputs X and two-component objectives.\n- Due to the limited empirical evaluation, it is largely unclear how well the algorithm would perform in practice. Unless the function noise is known to be small or the input space is of low dimension (such that isotropic length scales can be a reasonably good assumption) good performance from GP surrogates is generally expected to require fitting kernel hyperparameters one way or another (e.g. by maximizing the marginal likelihood). Granted that a version of the algorithm that chooses kernel hyperparameters adaptively would be much harder to analyze theoretically, so limiting the theoretical analysis to that setting is understandable. However, I myself would be much more likely to consider implementing and testing out the proposed algorithm if I had some confidence that it might work in more realistic settings. Absent that, I view the contribution of this submission as largely theoretical. To gain some confidence in the broader applicability of the proposed algorithm, at a minimum I would like to see empirical evaluation that considers noisy functions $f$, higher dimensional input spaces, and $m > 2$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of identifying (approximate) Pareto sets for a multi-objective optimization problem where the objectives to be optimized are uncertain and need be learned from data. To deal with function uncertainty, the authors use Gaussian Process surrogates to model each objective. To deal with the large (and possibly infinite) cardinality of the input space X, the authors use a tree-based adaptive discretization approach to progressively partition input space and refine the putative Pareto set. The authors provide rigorous bounds on the sample complexity of their Pareto set identification algorithm (Adaptive $\\epsilon$-PAL) and provide an empirical comparison to a few baseline methods. The main contribution of the submission would appear to be its construction of an appropriate adaptive discretization strategy that is appropriate to large/infinite input spaces and that admits a rigorous termination and sample complexity analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Points of clarification that I think need to be addressed:\n- You assume a shrinking \"cumulative confidence hyper-rectangle\" (eqn 1). This may make sense in a world with a fixed kernel, but probably doesn't make much sense if the kernel hyperparameters are chosen adaptively. Do you see this assumption as crucial to the construction of the algorithm per se, or is this more of a convenience for the theoretical analysis? Similarly, this seems to be related to the fact that (as I understand it) that once points are added to $\\mathcal{P}$ they are never removed. Can you please comment on this? More broadly, given the many choices made in designing the algorithm, I would love to see a discussion of which choices in the algorithm are largely driven by a desire to simplify the theoretical analysis, as opposed to choices that are thought to be important for good performance.\n- I'm a bit confused on the nature of $V_h$, which we are told is a \"high probability upper bound on the maximum variation of the objective\". But it is also described as an input to Algorithm 1. What is this quantity exactly and what role does it play? On a related noted, what is the nature of the assumption on $V_h$ in Thm 1? Why is this a reasonable assumption or, more broadly, what does this assumption assume/imply?\n- I'm confused how quantities like $\\mu(x_{h,i})$ are defined and computed, since to my understanding $x_{h,i}$ is a cell and not a particular point in the input space. Can you please specify more clearly how and when you move back and forth between cells and points in the input space?\n\nPoints of clarification that I think should/could be addressed:\n- How would you modify the algorithm if the user doesn't want to explore the full Pareto front and is only interested, e.g., in the Pareto front within some hyperrectangle?\n- You briefly mention that you \"adopt an efficient algorithm in Kung\". I'm assuming this is a novel algorithm. As such it would be worth describing in the appendix. Otherwise it would appear to be difficult for a reader to reproduce your results.\n- While you have some helpful figures that illustrate what the algorithm is doing, given the complexity of the algorithm I would love to see a more complete walkthrough of ~3 iterations of the algorithm in a toy setting. Such a walkthrough could do wonders to help ground the reader in the core ideas of the algorithm. Perhaps it would be sufficient to expand Figure 3 and its caption.\n- I would love to get more intuition about some of your particular algorithmic choices, e.g. the notion of \"pessimistic\" you adopt and why this might be expected to perform better than some other choices. Similarly, it would be great to see some of these choices ablated in the empirical evaluation.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZblqTKCvAX", "reviewer": "Reviewer_hZSi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper is well written. I found the related work section describing the multiobjective blackobx optimization literature well.\n\n- The paper is mostly a straightforward but sound synthesis of two existing ideas from black-box optimization: extending multiobjective pareto-active learning (PAL) with HOO/BamSOO ([1,2,3]) style tree adaptive discretization. \n\n- The key novel step in PAL algorithm to this multiobjective setting is in the discard phase (section 4.2). The paper uses the idea to discard a cell when the best corner of the rectangle formed by its points is \\epsilon-dominated by the worst corner of some pessimistic rectangle (definition 9). This \"rectangular dominance\" idea is known to be very conservative ([4,5]) and ignores any correlation between objectives. The second new step in the paper is to use the norm of the objective vector in refininig/evaluating phase.\n\n- The paper also mentions noisy observations in the beginning but it is not clear how is that captured in the theoretical analysis. Please mention if I missed something. \n\n[1] Wang, Ziyu, et al. \"Bayesian multi-scale optimistic optimization.\" Artificial Intelligence and Statistics. PMLR, 2014.\n\n[2] Shekhar, Shubhanshu, and Tara Javidi. \"Gaussian process bandits with adaptive discretization.\" (2018): 3829-3874.\n\n[3] Zuluaga, Marcela, et al. \"Active learning for multi-objective optimization.\" International conference on machine learning. PMLR, 2013.\n\n[4] Suzuki, Shinya, et al. \"Multi-objective Bayesian optimization using Pareto-frontier entropy.\" International conference on machine learning. PMLR, 2020. \n\n[5] Zhang, Richard, and Daniel Golovin. \"Random hypervolume scalarizations for provable multi-objective black box optimization.\" International conference on machine learning. PMLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The problem considers the problem of black-box optimization of multiple objectives. The key idea is to use a tree adaptive discretization with Pareto active learning (PAL). The paper provides two sample-complexity bounds: information-type and metric-dimension type. Experiments are shown on 1D synthetic objective functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I encourage explicitly writing the key innovations that were involved in extending the existing ideas to multiobjective settings and what are the challenges of the extension.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aL4j2Yi7cF", "reviewer": "Reviewer_vHvi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The writing is quite disappointing, especially for a journal submission.\nAt its current stage, the proposed method is vague and hard to understand.\nIn particular, Section 4 is somewhat unreadable due to the poor writing.\nI am still quite lost after spending quite some time reading the paper (and I am familiar with relevant tools used in the paper).\nThe following are some suggestions for improving the writing.\n    - Deferred definitions / undefined symbols.\n    Many symbols are not defined at their first appearance, e.g., \\\\(\\beta_\\tau\\\\) and \\\\(V_h\\\\) at the top of page 9.\n    Some notations are not defined at all throughout the main paper, e.g., \\\\(\\bar D\\\\) in Theorem 1.\n    - Unnecessary definitions.\n    The notions of covering and packing numbers in Definition 7 are never used in the main paper.\n    There is no point defining a notation but never use it.\n    They should be deferred to the appendix.\n    Otherwise, they are merely a distraction to the readers.\n    - Please include a pseudo code in the main paper to describe the **entire** algorithm, along with a **detailed caption**.\n    The main components of the proposed algorithm are described in three subsections 4.1, 4.2, and 4.3.\n    However, this is not enough to clearly describe the proposed algorithm.\n    - Please include a text description every time a symbol appears (or at least do so as often as possible).\n    Taking section 5.1 as an example, instead of writing \"if \\\\(\\mathcal{S}_t = \\emptyset\\\\) at the begining of round \\\\(t\\\\), ...\", write it as \"if the *undecided nodes* \\\\(\\mathcal{S}_t = \\emptyset\\\\) at the begining of round \\\\(t\\\\), ...\".\n    Without a text description of the symbol, the readers often need to go back looking for its definition every time a symbol appears.\n\n1. Weak experiment.\n    - The only experiment is based on GP sample paths.\n    Please consider include more objective functions.\n    - Please consider include a few more recent baselines, e.g., Daulton et al. (2021).\n\n1. Not necessarily a weakness, but a question.\nThe acquisition function is based on querying the point with the largest radius of its confidence hyper-rectangle, as shown in Eq (2).\nHowever, it appears that this is a pure exploration strategy.\nHow does it balance exploration and exploitation, as is often crucial in Bayesian optimization?\n\nDaulton, M. Balandat, and E. Bakshy. Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement. Advances in Neural Information Processing Systems 34, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a multi-objective Bayesian optimization method that finds the \\\\(\\epsilon\\\\)-accurate Pareto set.\nThe proposed method is based on a tree-based adaptive discretization and an extension of the \\\\(\\epsilon\\\\)-PAL algorithm proposed by Zuluaga et al. (2016).\nThe authors prove a regret bound of the proposed method and show that it outperforms existing methods empirically on GP sample paths.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Restructure and rewrite Section 4.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)