Active Set Ordering
Authors: Quoc Phong Nguyen
Sunil Gupta
Svetha Venkatesh
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2024 poster (2024)
Keywords: active learning
Bayesian optimization
top-k set
contour line
Primary area: active_learning
TL;DR: This paper addresses the active set ordering problem, discovering set rankings through costly black-box evaluations.

Abstract: In this paper, we formalize the active set ordering problem, which involves actively discovering a set of inputs based on their orderings determined by expensive evaluations of a blackbox function. We then propose the mean prediction (MP) algorithm and theoretically analyze it  in terms of the regret of predicted pairwise orderings between inputs. Notably, as a special case of this framework, we can cast Bayesian optimization as an active set ordering problem by recognizing that maximizers can be identified solely by comparison rather than by precisely estimating the function evaluations. As a result, we are able to construct the popular Gaussian process upper confidence bound (GP-UCB) algorithm through the lens of ordering with several nuanced insights. We empirically validate the performance of our proposed solution using various synthetic functions and real-world datasets.

Active Set Ordering
Quoc Phong Nguyen' Sunil Gupta', Svetha Venkatesh', Bryan Kian Hsiang Low², Patrick Jaillet Applied Artificial Intelligence Institute, Deakin University, Australia School of Computing, National University of Singapore, Singapore 'LIDS and EECS, Massachusetts Institute of Technology. USA qphongmp@gmail com, sunil. guptaddeakin eew.iiiiieedd.a........ euu svetha. wenkateshhdeakinnnnnn edu. lowkh&comp. nus edu. jai jaillettmit. edu
Abstract
In this paper, formalize the active ordering problem, which involves actively discovering a set of inputs based on their orderings determined by expensive evalua- tions of a blackbox function. We then propose the mean prediction (MP) algorithm and theoretically analyze it in terms of the regret of predicted pairwise orderings between inputs. Notably,
special case of this framework, we cast Bayesian optimization as an active set ordering problem by recognizing that maximizers can be identified solely by comparison rather than by precisely estimating the function evaluations. As result, we are able to construct the popular Gaussian process upper confidence bound (GP-UCB) algorithm through the lens of ordering with several nuanced insights. We empirically validate the performance of our proposed solution using various synthetic functions and real-world datasets.
Introduction
In real-world applications, we often encounter the problem of estimating an unknown function, known as a blackbox function, (i.e., those without closed-form expressions or derivatives) using their expensive and noisy evaluations. Under these circumstances, an efficient sequential process of evaluating the function is desired. On extreme, experimental design (ED) aims to estimate the function in its entire input domain, e.g., by decreasing the uncertainty of the function globally in On the other extreme, the renowned Bayesian optimization (BO) targets inputs with the extreme function values such as the maximizers and the minimizers 2 6.
Bayesian ED 4 18
While the connection between ED and BO is studied in the classic work of [19]. we still lack problem formulation that strikes a balance between the prohibitively expensive process of estimating the entire function globally in ED and the lack of information about the function away from extreme locations in BO. One may consider a related problem, called level set estimation (LSFE), which focuses on estimating inputs with function evaluations above or below given (or implicit) threshold [ g [4]. However, without domain knowledge of the blackbox function, it is easy to set a threshold that leads to undesirably large or small level sets.
Let us consider an environmental monitoring problem of estimating a chemical concentration in field. The blackbox function is the mapping from locations of the field to the chemical concentration measurement. It can be of greater interest estimate the maximizers, the minimizers, the top-k locations (with the highest chemical concentration) and the bottom-k locations. On one hand, these estimates provide more information about the blackbox function than just the maximizers or minimizers in BO. On the other hand, they may require less resource (i.e., evaluations of the blackbox function) than estimating the entire function ED. Besides, as the top-k locations consist of exactly locations in the field, it circumvents the issue of undesirably large small level sets in LSE.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our main contribution in this paper is to formulate the above challenge and resolve it with a theoretically grounded solution. Specifically, we propose the active set ordering problem to capture the ahove scenario (Sec. 2.1 It aims to estimate subsets of the input domain that are defined based on pairwise comparisonssorrderigss between the blackbox function evaluations TT These subsets include the maximizers, the minimizers, and the top-k inputs with the highest function evaluations. Like Bayesian ED, BO, and LSE, we adopt the pool-based active learning setting [8] in constructing a solution that sequentially selects sampling input from the domain at each iteration. The knowledge from observing function evaluations at the sampling inputs helps predicting the subsets of interest and directs the algorithm to select the next sampling input. To facilitate the presentation of our method, we begin with the building block of our sedering-based problem: pairwise comparison/ordentt between function evaluations in Sec. 3 Specifically, we propose a new kind of regret to quantify the
loss of a pairwise ordering (Sec. [Sec.B.11. p. a prediction of the top-k inputs based on only the posterior mean (Sec. 3.2, and sampling strategy that is equipped with theoretical performance guarantee for the proposed prediction (Sec. (.3). Subsequently, these concepts of the regret, the prediction, and the sampling strategy are extended to orderings between sets, which ultimately addresses the active set ordering problem in Sec. 4 Notably, the regret simplifies to the well-known regret in BO (Remark 4.1.. Hence, we recover both the theoretical analysis and the GP-UCB algorithm [99 when considering a special case of our problem setting (Remark (.5). In Sec. S we empirically validate the performance of our solution using several synthetic functions and real-world datasets.
Preliminaries and Problem Statement
2.1 Top-k set
Adopting an assumption in existing level set estimation (LSE) works I 8 we consider a blackbox
function f X' + E. where the domain X' is a finite set of n elements in Rd Let S A X' \ S denote the complement of any subset S C X. In this paper, the ordering between inputs are determined with respect to their corresponding blackbox function evaluations. Hence, we use the term "the ordering between x and x"" and "the ordering between fxx) and f fxx')" interchangeably.
Definition 2.1 (Top-k set). The top-k set, denoted as S(k), is the set of inputs with the highest function evaluations. Specifically, [S(k) = k and Vx E Sk)), Vx E (k), f(x) 2 f(x).
In this work, we propose the active set ordering problem to estimate the top-k set S(k) of blackbox function f by efficiently gathering noisy function evaluations in a sequential manner. Furthermore, it includes the Bayesian optimization (BO) problem when because the top-1 set S(1) contains a maximizer of f.
2.2 Gaussian Process
The noisy function evaluation mentioned in the previous section is denoted as y(x) & f(x + c(x) where the noise e(x) (O, ) is a Gaussian random variable with a known (or estimated) variance og- To obtain the posterior distribution of the unknown function / given these noisy evaluations, we model f using Gaussian process (GP), that is, every subset of (f(x)) follows multivariate Gaussian distribution [6]. A GP is fully specified by its prior mean and its kernel xx.xx & (x), (x')) which measures the covariance between function values. Let Dd denote the set of sampling inputs in the first t iterations. Then, given YD. & (y(x))xED, the predictive distribution of any function evaluation (xx follows a Gaussian distribution with the following mean and variance:
[x(x) (x) KK +
of A k(xxx)
(x) T TK, + -I
where (x) (')x, K, A (k(x, x') x),x ED. and I is the identity matrix [6].
Assuming f belongs to reproducing kernel Hilbert space with its norm bounded by B > 0. due to [5), we have the following confidence bound of f(x)
'Existing research on best-k arm identification in the multi-armed bandit literature poses similar problem. but it often focuses on the pure exploration setting and assumes independent arms which are inadequate for modelling blackbox functions 12)
Alternatively, may consider using the confidence bounds established in 19

---

Lemma 2.2. Pick E (0. 1) and set Be = (B + nn / 2(1-1++11 log 1/6))². Then, the following
event happens with probability of least 6.
EXEX, V2 1, (x(x S f(x) S (x(x)
where lx(x)
pe(x) B. (x)), ux(x)
(r(x) + By 3 ox(). and 7-1
Aa I(yA: 1 is the maximum information gain of fA - (f(x))xeA through ob- serving A all subsets A C X of size |A| 1.
To ease notational clutter, we denote the above confidence interval of f(x) as Cx(x) - [l(xx), (x)) and its length as [Cx(x) _ (x(x - lx(x.
Active Pairwise Ordering: n =
pairwise orderings (or pairwise comparisons) are the building blocks of our active set ordering problem. Hence, to facilitate the exposition of the key ideas, let us begin with a simplistic setting where the input domain X' consists of only n = inputs, i.e., X' = {x, x and f(x) + f(x). The problem is to determine the top-1 set S(1), i.e., the maximizer of (equivalently, the minimizer of f). essence, the goal to check if ((x) >> f(x') by strategically collecting noisy evaluations y(x) and yxx).. In particular, at iteration t, the algorithm proposes sampling input x; E to obtain a noisy evaluation yxx)). Then, the GP posterior distribution f is updated and used to construct predicted ordering between x and x (i.c., the ordering between f(x) and f (x')). The problem boils down to the strategy of selecting the sampling input x2 such that performance metric of the predicted ordering between section, we introduce regret definition to serve as a performance metric.
From Definition 2.1
f(x) and f(x) is satisfactory. In the next
3.1 Regret
Let us denote the (unknown) true ordering between & and x' according to the evaluations of the blackbox function f aasm.. m.:
T. (Xx A ((8)2((8)
(1)
where the indicator function (()2)((*) 1 if f(x) f(x) and 0 otherwise. For any ordering π {(x, x3) + {0, 1}, we define the following regret of (T( x)):
(x(2x))) A max (0, (2m(5x - 1) f(x)))
(2)
In particular, 7x (x(xx"==11= = max(0, f(x) f(x)) and (=())=)== = max(0. f(x)). The rationale is to ensure poor performance leads to large regret: The regret is [ f(x') (which increases as the gap between f(x) and f((x') increases) if the ordering क does not align with the true ordering, i.e., (x, x') # T (x, x'). On the contrary, the regret 0 (i.e., the best performance) if (x, = T. (x)
However, the blackbox function f renders the evaluation of (=(x,*) impossible. Thus, we resort to relying on the GP posterior distribution of f at iteration & to construct an upper bound of the above regret in the following lemma (proof in Appendix Ap.
Lemma 3.1. For all 2 let us define
max ue vx(x') (())) max 1(x')) if*(x, 0.
ff((, =
(0)
(3)
(*()x)))
Then, P=(x,3)) is an upper confidence bound of the regret (x(2,,1)) i.e.
P P(V T=(2,8)) S (1) ( 2 1-6
where 8 is as defined in Lemma 2.2
3

---

3.2 Prediction
Definition 3.2 (Predicted pairwise ordering Tpp) Given the above upper bound (4)
(=(x,))) of the regret,
we would like to make a prediction Tpe that minimizes (t)
(x.88))) Therefore, THe is defined as follows
pi (x, x) A argmin (0) (x(x,))==a"
(E(0,1)
As result, the upper confidence bound of the regret in (3) is minimized at o(x,, x') Tu, (X. and its minimum value is
x)
P (R,) max (0, (i'( 4 (x), (x) (xxx))
(5)
We note that the upper confidence bound of the regret can be interpreted as a measure of the approximation quality or the uncertainty reduction discussed in the following two remarks.
Remark 3.3 (Approximation quality). Since P (R.81) ",,,(,,8) for all 2 1 with probabil- ity at least 1 - 6, the regret incurred by the ordering THe cannot exceed the worst-case re- gret ( (8,5*) shown in Fig. la. Hence, if [f(x) - f(x') > Prue (8.8')) T (x, is the true ordering, i.e, Tpp (x, x²) = T. (x, ") with probability of at least 5.
(8) Remark 3.4 (Minimum uncertainty reduction). In Fig. 10, one can interpret P (8.8)) the minimum amount that the confidence intervals (x) and C, (x') (representing the uncertainty) reduce so that xx,,( (8.8) 0 with probability of at least 1 5.
Moreover, the prediction Tu, can be obtained using only the GP posterior mean (proof in Appendix B which explains the name of our approach: mean prediction (MP) and the notation Tp.
Lemma 3.5 (Mean prediction). The predicted ordering THe defined in (4) can be determined from the GP posterior mean
THi (x,x) 1 (x)())2m)0))
(6)
(1) PTpy (8,8))
worst-case regret
((() 24 (x))
4(x))
{.......... ut (x()x)
(x)
(x)
(xx))
Ut (x)
2 (8,81)
worst-case regret
(a) (1)
(2, is the worst-case regret happening when f(x) = (xx) and f(x') ux)).
Prui (8
P (8.80
(x())
(x)
(x())
We (x)
(xx)
Uy x
4(x')
24 (x')
4(x)
ue (x))
ui (x))
2/f (xx)
(b) Top, (8.87) when (u,, 4)) are refined (u4, 4)) following an observation, i.c., the reduction in the uncertainty represented as the sum of the two red dashed segments is at least FT (x.8²)
(6)
(1) Figure 1: Interpretations of the upper bound P (8.8)) when TTe, (x,8)) = 1.
3.3 Sampling Strategy
Given the regret in Sec. 3.1 and the predicted ordering Ty, (x, x') in Sec. 3.2 we would like to select
sampling imput x, &, x') such that the regret C' (8.2)) of the predicted ordering Ty, (x, x') reduces quickly.

---

While ra, (2.80) is unknown, it is bounded by (0)
Pr (8.8) with probability of at least 1 - 6. Hence, to reduce T (8.x), we aim to reduce PTyy (x,,())))) (2.82) It is also noted that observing yxx) decreases the confidence interval (x+)). Hence, to induce the reduction in the regret TT,, (2,8)) through ob-
serving y(xx), select x; such that its confidence interval |C+ (x+)l (1 (8.8) (which guarantees that [C,(x, ) 2 "x,,, (8.8) with probability of at least 6). For instance, choosing X = X in the left plot of Fig. D satisfies this condition, but it does the right plot of Fig. D In the following
lemma, we show that the following 4 choices of the sampling input satisfy the proposed condition (see Appendix C
Lemma 3.6.
Let 2 & (XV X
A x' denote a se of inputs at iteration t where
X V X A argmna oe (x)
X A argmin ((x)
xE(
xE(x,x)
& V A argmax [x)
XAX A
argmin [C(()) xE(87X(8XX)
xE(X,8))
For any Xx E 2t [Cx(x)) 2 (8.8
Theorem 3.7. By sampling the input xs following Lemmal 3.6
we obtain the following regret bound
T II 1=1
T
) 21-6
P VT v(x) E Qr
& R
Tap (8 $ O SO(VTBrm))
where Br, Yr, and ó are as defined in Lemma 2.2
Remark 3.8 (Sublinear cumulative regret). If yr sublinear, our average cumulative regret is sublinear. This requirement is similar to most BO and LSE algorithms. It is noted that YT is sublinear for the squared exponential (SE) kernel as discussed in 19]. In this case, our cumulative regret bound Rg I O (v TTooo 2) is the same that of GP-UCB [99 (where (-) denotes asymptotic expressions up to dimension- dimension-independeer logarithmic factors and is the dimension of the input).
for many popular kernels. For instance, "T O ((log
T) ((logT))+t
We defer the pseudocode to the next section when n 2 2.
Active Set Ordering: n 2 2
In this section, we utilize the results in Sec. 3 present the mean prediction (MP) algorithm for the active set ordering problem with n 2 2.
4.1 Regret
When X' consists of inputs, there are multiple pairwise orderings between inputs in X.. We overload the ordering notation T. of the true pairwise ordering between 2 inputs in (T) to the ordering between 2 sets as follows: for any subsets X, C and X1 C 26.
T. (No, = [ vf E No, Vx E X1, (x,x)) =1
if E No, Vx E X1, (x,'') = =0
is noted that T. (x X1 remains undefined if the cases above are not satisfied. However, this situation does not arise in our solution. We define the regret of a set ordering (i.e., multiple pairwise orderings) as the maximum regret of all pairwise orderings:
(x.x Xxxx "=(xx')= Vi (0.1)
max
where (x( is defined in and Xo x Ri the Cartesian product of X, and X1 i.c.
max (J(x') ((x)))(xx)) Vi (0, 1}. (= max (0, (2i Xxx')XxxX
(8)
For convenience, allow duplicate elements in Qc.
5

---

Remark 4.1. It is noted that X)) coincides with the well-known regret in BO when we consider
the problem of predicting maximizer of f. In particularly, predicting &, as a maximizer of equivalent to predicting the set ordering t ( J. (&.)) Its regret is (a((2. ). [[=1)1=11111
maxxex f(x) - f())) as shown in Appendix E.1
Following the upper confidence bound of the regret of pairwise orderings in 3 we show in Ap- pendix F that with probability of at least 1 6, for all 2 and for all subsets No C X, Xi C
26. (1) S P X1)
where
(1) (r( (xxx) (=(xxx))=((x)11)))
4.2 Prediction
In this section, we generalize the prediction in Sec. 3.2 to set orderings. From Lemma 3.5
there is
contradiction in the pairwise orderings Ju, (x, x') (defined in 4 for all (x,x') X
In other
words, the transitivity property holds for the binary relation THe as shown in Appendix
Definition 4.2 (Predicted top-k set Sn, (l))). Let Sp, (k)(k) be a subset of &' such that
sS, (1:) = k
(Sp S2, (k)) =1
where the set ordering Tu. (S,,, (k),, St, (A)) is obtained by substituting n, with the pairwise order- ing TH, (see Definition 3.2) (7). From Lemma 3.5 Sp, (k) is basically the set of inputs with the highest GP posterior mean values.
As nu. (S,, (k)) S (+)) = implies that Tu, (x, x') = for all (x, x') E Sn, (k) x Sp (k)), the upper confidence bound of the regret is
Th (Sp, (k), (b),,
max (x.x)) (b) x5, (R) (xx())))
(10)
4.3 Sampling Strategy
Like in Sec. 3.3 our key idea is to select x, such that the length (x,) of its confidence interval
p bounds p(t) (Sp. (A), (k)) (in (10). Since Par, (Sp, (k), ss, (k)) is the maximum upper confidence
bound of the regret of all pairwise orderings involved in defining Sp. (k), first determine the input
pair &x, x)) that incurs the maximum upper confidence bound of the regret. This is also the input
pair that Tye most likely makes mistake, following the intuition from [12]
[x, x))
argmax (xx,x) (x,,") ( (k)
P PTy (x.x')
(()
(11)
It is noted that (Xe, x() constructed from an input in the predicted top-k set S,,, (k) and an input in its complement S (k)) As the estimation of the top-k set improves, we expect these 2 inputs to be at both sides of the boundary of the top-k set: inside the top-k set vs. outside the top-k set.
Then, extended from Lemma 3.6 the following lemma shows that the above desirable property satisfied by choosing the sampling input x, from any inputs in the set 2, & {x, V X/ X A x,, 8, V X N4 A X (defined in Lemma 3.6).
(8) Lemma 4.3, For any E Q., [C,(x,)) 2 Px (8,, (R))
The proof shown in Appendix H Lemma 4.3 is bounded in the following theorem (proof in Appendix I
As a result, the cumulative regret incurred by choosing X; in
Theorem 4.4. By sampling x, following Lemma
4.3
we obtain the following cumulative regret bound
T o
P VT > 1, ((x)
Ri
4
Tope (S (8).. S O0VTTBm)) 21-6
E=1
where Br, Yr, and 8 are defined in Lemma
2.2

---

Algorithm 1 Mean Prediction (MP) for Active Set Ordering
Require: X, Do. k, T
1: for t= to T do
2: Update GP posterior belief: {1((x))xxx xxx for (x)
3: Construct Sy, (k) as top-k inputs with the highest values of pa.
D Prediction
4: (xt; = arggma (x.x)) Sp (1) P (x,x)
(t)
5: Select X₁ {&, V X X, & V X X x
D Sampling input
6: (r,D)) - y(D (b(x))
7: end for
8: Update GP posterior belief: {uT+I (x) bxxx, (oT+ (xxx
9: Construct Spr. (k) as top-k inputs with the highest values of pT+11
10:
return Sp (k).
We call the algorithm that makes prediction using the GP posterior mean and selects the sampling input x, following Lemma 4.3 the mean prediction (MP) algorithm. Its pseudocode is shown in Algorithm]] [ Theorem 4.4 indicates that MP incurs a sublinear cumulative regret for several
commonly used kernels with sublinear 7T [9
Remark 4.5 (Bayesian optimization as an active set ordering problem with = 1). We show in Appendix E.2 that when k = 1, & V X E argmax ux(x), which is the sampling input in the GP-UCB aggorihhm [19]. Additionally, as discussed Sec. [.1 the regret r ((()) the well- known regret in BO. Hence, we recover both the GP-UCB algorithm and its regret bound when k = 1 (although we consider the regret of the prediction rather than that of the sampling input). Moreover, this new construction of GP-UCB leads to some subtle insights. Firstly, while the GP posterior mean has been used in computing the inference regret of entropy search methods [9,21, there has not been any theoretical justification for using the posterior mean. In contrast, the theoretical analysis in work justifies the use of the maximizer of the GP posterior mean as an estimate of the maximizer of f. Secondly, by predicting the maximizer using the GP posterior mean, X V x is not the only sampling input that achieves a sublinear cumulative regret. In fact, there are other choices of the sampling input as shown in Lemma 4.3 Similarly, we note that the LCB algorithm to find the minimizer of blackhox function can be recovered by setting = n - and x, = X X'X
Remark 4.6 (Lower bound of active set ordering problem). Let the lower bound of the active set ordering problem be the lower bound of the cumulative regret of the worst-case problem instance over all possible values of k. Then, it should be at least large the lower bound of the special case where 1, which the BO problem according to Remark 445 Furthermore, BO has known lower bounds for several common kernels, e.g., for the SE kernel, the lower bound of the cumulative regret is 22( 22(VT(log 2///2 [17. Hence, the lower bound of the active set ordering problem is at least 2 (Tog T)222) Additionally, similar to Remark 3.8 the cumulative regret of our solution in Theorem bounded by Rí < O (VT((log 2) Hence, it matches the lower bound up to the replacement of d/2 by 2d + O(1.
Remark 4.7. Updating the GP posterior belief incurs O + r=)") (including ( 1*) for training and (nn for prediction). Given the GP posterior belief, Algorithm involves the following 2 major steps. First, in line 3 of Algorithm [ it takes O(n log to find the top-k inputs S,,, (k)) by using a max heap of size and scanning through the GP posterior mean of all n inputs. Second, in line 4 of Algorithm [ it takes ((k(n-k) k)) to scan through the elements in S,, (k) x St. (k). Therefore, an iteration of Algorithm takes O(D,, + na DD, 12 + n. no k + k(n k)). Remark 4.8 (Active multiple set ordering). Let consider the problem of estimating m top-k simultaneously (motivated in Sec. []. This problem is analogous to finding k contour lines of blackbox function, where each contour line represents the boundary between S(k)) and its complement (ks).. . To solve this problem, we define the following input pair
sets: S(k)), ((k)),, S(km)
argmax (X (K,, (k.)
110 (xxx')
(12)
In other words, we aim to reduce the maximum regret incurred by the predicted pairwise orderings in all m top-k sets. Given x)) in (T2) MP proceeds by sampling the input x, according to
Lemma 4.3 i.c., X, (Xt, V X A X X
X Xx A x.). The approach is claborated in Appendix J
7

---

Iteration
Iteration
Blackbox function
15
GP mean
10
Upper bound
0.-
Lower bound
Correct Predicted Teg-k
0.5
Incorrect Predicted Top-k
-1.0
Missing Top
Comparison Pair
-15
Current Observation
-20
Past Observation
(a) MP: X₃ X2 A X,
(b) Var: X2 = argmaxxxx of (x).
Figure 2: Plot of sampling inputs, GP posterior distribution, and the performance of (a) MP and (b) Var in estimating S(20) of a synthetic function. The comparison pair is (R,, x.) in (II. The histogram on the horizontal axis shows the frequency of sampling imputs in 40 iterations.
We also note that active multiple ordering is able find both maximizers S(1) and minimizers (n - 1) simultancously, problem has not been studied in GP-UCB [1)].
5
Experiments
5.1 Active Set Ordering
In this section, we validate the empirical performance of our MP algorithm with different choices of the sampling input in Lemma 4.3 &, V X,, &, A x, V X and X, A X by comparing with baselines: an uncertainty sampling approach, called Var, that selects the sampling input with the highest GP posterior variance, i.e., X2 E argmaxxex* of (x), and baseline, called Rand, that selects the sampling input at random. The regret "x,,, (S,, (F, (k)) is used to measure the performance of each algorithm, i.e., the prediction of the top-k set consists of the & inputs with the highest GP posterior mean.
To begin with, we visualize sampling inputs and the accuracy of S (20) that come from our MP algorithm with x; X, A x and the Var algorithm in Fig. 2 In Fig. 2b. the histogram shows that the sampling imputs are at the boundary of S(20). This is highly desirable as it is challenging to decide if an input at the boundary belongs S(20). Similarly, the input pair in (II) also consists of inputs around this boundary (depicted as vertical orange lines). On the other hand, precisely estimating the function evaluations of inputs far from the boundary, e.g., inputs around x 0.85 (in S(20)) and inputs around x = 0.1 (not part of S(20) is unnecessary. We observe that the uncertainty of the GP posterior distribution these inputs high in Fig. 22. Hence, our MP algorithm is able to efficiently concentrate its sampling budget on important inputs at the boundary of the top-k set. Interestingly, this boundary serves as a contour line of the blackbox function, indicating that our solution could potentially be applied to estimate the contour line by specifying the proportion of the input domain where function evaluations exceed this contour. Regarding the Var algorithm (i.e., uncertainty sampling) in Fig. 2p. the histogram shows that sampling inputs are distributed evenly across the input domain. It is because Var aims to reduce the uncertainty the function evaluation throughout the input domain without considering the current predicted S,,, (20). For example, it observed that the estimation of function evaluations the boundary of S(20) using Var is more uncertain than that using the MP algorithm given the same number of sampling inputs. This results in erroneously predicting certain inputs in S(20) (depicted red dots) and overlooking several inputs in S(20) (depicted as black dots)
inefficient to select sampling inputs far away from the boundary of S(20).
We numerically report the performance using the proposed regret Tx,, (S,, (k).S,, (k)) The experi- ments are conducted 4 synthetic functions: function sampled from a GP, Branin-Ho function, Goldstein -Pice function with a noise of or, = 0.1, and Hartmann-6D function with a nosie of Tn 0.01 20 For the first three synthetic functions, the input domain is discretized into a set of 100 points, whereas for the Hartmann-6D function, it is discretized into a set of 1000 points. Motivated by environmental monitoring problems, we generate 3 active set ordering problems that
'The complete animation available in the supplementary materials.
8

---

estimate the top-5 set using the dataset of NO; concentration in the Lake Zurich (downloaded from hoomattps:://iii //tlbb/wwbbbb//// ilec. or Letp///eeEER---R (atiao00ddaaaallise httpp/////EEEE-////aaaaaaa--- the dataset of the phosphorus con- centration in the Brooms Barn ) and the dataset of the humidity in the Intel Lab (downloaded from https://db. csail mim http//laadttaaaadatttt .html. The environment field dis- cretized into a set of 100 locations in the experiments with the NO; and humidity datasets and 400 locations the experiment with the phosphorus dataset. The experiments are repeated 15 times to account for the randomness in the generation of the observations. Further details are provided in Appendix K] The average and the standard error of the regret are shown in Figs, 3p.- There not any significant difference in the performance of MP with different sampling inputs in Lemma 4.33 Nevertheless, the MP algorithm with any choice of the sampling input in Q. outperforms the baselines by converging lower regret.
-/-- Rand
A.AR
-1--
107
10a
10'
10'
100
Rogret
6xx10"
100
1000
10000
10-2
10-1
10
30000
10
Iteration
Iteration
Iteratioon
Iteration
(s:a) GP sample
(s:b) Branin-Hoo
(s:c) Moldstein-Price
(s:d) Hartmann-61
10"
101
10a
10
102
Regret
Regret
Regret
100
10c
20a
10-1
50
100
0
25
50
75
100
20
40
0
20
40
Iteration
Iteration
Iteration
Iteration
(s:c) NO₃
(s:f) Phosphorus
(s:g) Humidity
(m:a) GP sample
107
102
107
Recret
10A
Regret
x ==100*
Resret
10a
10
10-1
10a
75
50
75
heration
Itoration
Iteration
Iteratioon
(m:b) Branin-Hoo
(m:c) Goldstein-Price
(m:d) Hartmann-6l1
(m:e) NO;
10*
10
102
10a
10'
Itoration
Iooaatio
(m:f) Phosphorus
(m:g) Humidity
Figure Plots of the regret against the iteration in estimating (sta-f) the top-5 set S(5) and (m:a-f) multiple top-k sets: S(1), S(10), and S(20).
5.2 Active Multiple Set Ordering
To empirically validate the performance of our MP algorithm in solving the problem of estimat- ing multiple top-k sets, we consider the problem estimating S(1) (i.e., maximizers), S(10), and S(20) simultancously, i.c., K1 1, 10, k3 20 in Remark 4.8 We utilize the same set

---

EI
-/--
Pl
MES
RAK
x. X.
a
k.
10a
10a
100
10'
10"1
10-3
109
10"
10a²
10-3
10a
Iteratio
iteration
heeration
Iterationn
(a) Branin-Hoo
(b) NO;
(c) Phosphorus
(d) Humidity
Figure 4: Plots of the regret of the predicted maximizer against the iteration.
of synthetic functions and real-world environmental datasets in the previous section to compare the performance of MP with Var and Rand. The plot of the average and standard error the maximum regret m11.g(1.10220) (Trp, (S, (k), (k)) over 15 repeated experiments are shown in Figs. 3 3m:a-g. The MP algorithm outperforms the other 2 baselines by converging to lower regret. In some active multiple set ordering experiments (e.g., in Figs. moss. mm.., the performance gaps between MP and Var smaller than those in the previous active set ordering experiments (e.g., Figs. Baas :cc)) It is
because estimating multiple top-k sets requires more observations, which makes the performance of MP tend towards that of Var which estimates the entire function.
5.3 Bayesian Optimization
When & = 1. the active set ordering problem reduces to the BO problem and sampling input of MP algorithm, i.e., X₂ X2 VX,, , is the same that of GP-UCB [19]. Therefore, this section empirically demonstrates the performance MP with different sampling inputs (x, E {&, v X, X, A X,, X2 V X X2 A x()) ) in solving BO. Our aim is not to show that MP achieves the state-of-theear performance as a BO solver, but rather to demonstrate that it performs comparably to the well-known GP-UCB algorithm. In addition to comparing with GP-UCB (equivalently, MP with
x, XxX)), we also compare with 3 classical BO solutions: probability of improvement (PI) [33 expected improvement (EI) 15 and max-value entropy search (MES) 21 The average and the standard
of the regret me (Sp, (1),5, (1)) over 15 repeated experiments are shown in Fig, 4 We observe that
MP performs comparably with the well-known GP-UCB algorithm (labelled x, Vx,). Expectedly, El and MES outperform GP-UCB (and hence, MP) in some experiments such as in Figs. and 4
Conclusion
This paper presents a new problem formulation, namely active set ordering, that aims to balance between the expensive estimation of the entire function in ED and that of only the maximizers in BO. We propose the mean prediction (MP) algorithm address this problem with a theoretical no-regret guarantee. Interestingly, BO can be framed as special instance of active set ordering, which leads to several new subtle understandings regarding the predicted maximizer and other alternative sampling inputs. Last, the performance of MP is empirically evaluated using various synthetic functions and real-world datasets.
Acknowledgments and Disclosure of Funding
This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2020-018,
DesCartes: this research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
This research was partially supported by the Australian Government through the Australian Research Council's 's Discovery Projects funding scheme (project DP210102798). The views expressed herein are those the authors and are not necessarily those the Australian Government Australian Research Council.
10

---

References
[T] I. Bogunovic, J. Scarlett, A. Krause, and Cevher. Truncated variance reduction: A unified approach to Bayesian optimization and level-set estimation. In Proc. NIPS, pages 1507-1515, 2016.
[2] E. Brochu, V. M. Cora, and N. De Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: /012.259, 2010.
[3] B. Bryan, R. C. Nichol, C. R. Genovese, J. Schneider, C. J. Miller, and L. Wasserman. Active learning for identifying function threshold boundaries. Proc. NeurlPS, 18, 2005.
[4] K. Chaloner and I. Verdinelli. Bayesian experimental design: A review. Statistical science, pages 273-304, 1995.
[5] S. R. Chowdhury and A. Gopalan. On kerneiized multi-armed bandits. In Proc. ICML, pages 844-853, 2017.
[6] Frazier. A tutorial on Bayesian optimization. arXiv preprint arXiv:1807.0281 2018.
[7] Roman Garnett. Bayesian Optimization. Cambridge University Press, 2022.
[8] A. Gotovos, N. Casati, G. Hitz, and A. Krause. Active learning for level set estimation. In Proc. IJCAI, 2013.
[9] J. M. Hernández-Lobato, M. W. Hoffman, and Z. Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Proc. NIPS, pages 918-926, 2014.
[10] H. Jiang, Li, and M. Qiao. Practical algorithms for best-k identification in multi-armed bandits. arXiv preprint 1rXXv:1705.06844 2017.
[11] S. Kalyanakrishnan and P. Stone. Efficient selection of multiple bandit arms: Theory and practice. In Proc. ICML, volume 10, pages 51 1-18,, 2010.
[12] S. Kalyanakrishman, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi-armed bandits. In Proc. ICML, volume 12, pages 655-662, 2012.
[13] H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of basic engineering, 86(1):97-106, 1964.
[14] B. Mason, R. Camilleri, S. Mukherjee, K. Jamieson, R. Nowak, and L. Jain. Nearly optimal algorithms for level set estimation. In Proc. AISTATS, 2022.
[15] Močkus. The Bayesian approach to global optimization. In System Modeling and Optimization, volume 38, pages 473-481, 1982.
[16] C. E. Rasmussen and C. K. I. Williams. Gaussian processes for machine learning. MIT Press, 2006.
[17] Scarlett, I. Bogunovic, and V. Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Conference on Learning Theory, pages 1723-1742, 2017.
[18] Burr Settles. Active learning literature survey. 2009.
[19] N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. Proc. ICML, pages 1015-1022, 2010.
[20] Surjanovic and D. Bingham. Virtual library of simulation experiments: Test functions and datasets. Retrieved May 21, 2024, from http:///ww/ sfu, ca/ wawtssuraaaasaaasaa "ssurjand
[21] Z. Wang and S. Jegelka. Max- value entropy search for efficient Bayesian optimization. In Proc. JCML, pages 3627-3633 2017.
[22] R. Webster and M. A. Oliver. Geostatistics for environmental scientists. John Wiley Sons, 2007.

---

A Proof of Lemma 3.1
We will show that (1)
(x) is an upper confidence bound of the regret (=()))))))))) i.c.
P P (x(2,8)) 2 P Pa(x.89) 21-6.
The regret ((( is defined as follows
(x( max (0, (2T(X, x) - 1)(f(x)) f(x)))
Furthermore, from Lemma 2.2 with probability of least 1 6, for all t 2 1,
1((x) S f(x) 1 4x(x)
4(x')= S f(x') S ur(x')
Hence, with probability of at least 1 - 6, for all t 2 1,
f(x) f(x') 1 ux(3) ((xx))
f(x') f(x) I ux(3x) (xx)
Multiplying both sides with (2T(x, 1), we obtain
(2T(X, -)(x))))))(())/-((1))))) - f()) < [4((X) (x(x)
if xxx 0 (1)
(xx)x') - (xx)
if x(xx)) -=(2,8))
Therefore, with probability of at least 1 - 8, for all t 2 1.
mmax(0, mx(x) - ((x'))
if =(, = 0
(=( max (0, (2T(X, 1)(((x))))))))))))))))))())))))) - f(x))) <
max(0, vx(xx) ((x))
if -xxxx 11
B Proof of Lemma 3.5
We note that 1 px())2x,(8)
happens when
Me (x) (x(x')
(x) + (xx)
(x') + (xx)
2
2
+ ux(x 1((X) 2 u, (x') - (x(x)
+ max(0, (x) (x')) 2 max(0, un (x') - (x))
+ P (=( (2
Therefore,
1 12((8)2m188) = (1)
P=(2_8')-0 20 20
argmin P (=xxx'==a = = (x, =xp,
ae(0.1)
C Proof of Lemma 3.6
We will show that (0)
PRa, (8.8)) S (x:)) when x, is taken from the set Q A (&VX
X', X AAX' 8').
Case 1: X4 = X XV mngmaxxe(xxx)) Us (x)
(1)
ma (4 (x') 1(xx, (x(x)) 4x())) (xx2)
Pxu (x.8")
max(0, min (u, V x') (x). u, x
(13)
S max(0, (x v x') - ( V x)))
(14)
u,(8 v x') - (x v x')
(15)
= Cx V x')
(16)
12

---

where 13 is because x V x argmax (x (x),)
14 is because & V E
x 15 is
because Me (X x) 1 X V x 2 0.
Case 2: X XAX argmin ( (xx)
PTpy (x.x'
= max(0, min un (x') (x)). (x) - 4(1)))
(17)
I max(0, min u (x²) 4x ux(x) - 4(xAx)))
(18)
I max(0, 4n (x - 1e (
(19)
(((A (XAX)
(20)
(21)
where 18 is because X A X
x (8.8)) (x),,, 19 is because & & X E (8,8).
20 is
because Wr (XAX)) (x ( 0.
Case 3: x2 x V ف argmax x ( (x(x)).iee..
max [x(())
(22)
xE({,X))
2 (x(xx))
(23)
2 P Pap, (8.8)
(2)
(24)
where 23 is because & &A&'S E {xt X'),
24 is from the above proof case 2 (1
Case 4: X2 = XAX argminlee v x sas)) [x())) From (66) and 21 it follows that [C, A
x) Pap (8,81))
(1)
D Proof of Theorem 3.7
By choosing x, following Lemma 3.6 with probability of at least 6, for 2 1,
Tan (8.x') S (t)
Ta, (K.8)) I (c,(xx)) 2,3///2 (x.))
Hence, with probability of at least 8, for all N 1,
T
T mp (xxx - Σ
23//2 (x:)
1=1
Since 3r non-decreasing sequence, Br S Br for all S T. Therefore, with probability of least 1 - 8, for all T 2 1,
T
T
Σ Tan (x,2) S 2, Σ (xi) t=1
From Lemma 5)
Σ (x)(x) V 2) (
Hence, with probability of at least 1 - 8, for all T > 1,
T
TTu (8.8) S (3
1=1
i.c.
T
PT
Tu (8.2) 5 SO(VTBTTT)
1=1
13

---

E
Bayesian Optimization as Active Set Ordering with t: = 1
E.1
Regret
For predicted top-1 set Sy, (1), Tu, (Sn, (1), expressed as follows.
(1), Sr (1)) = 1. Hence, the regret for predicting Sp, (1)
f(x) 1(x) 5(x))
Tr (Sp) (1),8%,, max
0g (xxx)) (1)
max
Let S,, { and x, E argmax f(x).
0, max (f(x) - -((2.) xESE,
(S,, max
max f(x) -((2.))
max
0,
xeSe (1)
Since X' = (1) U., (1), there are 2 cases
. IIfx, S (1), then maxxes, (1) f(x) = [(x.) 2 ((x.) and
Yun (Se, (1), (1)) = max (0, (x..) - -((x.) = -(x.) - f(xx).
xf, Sn (1), i.., x. = xx, then maxxes (1) fxx) f(x.) and
(S,, = = f(x.) f(x.)
E.2 Sampling Input
We will show that
N X argmax u. ux(x).
xEx
When 1, due to the definition of Sp, (k) in Definition 4.2
X₁ E argmax (c(x).
XEX
Let
& E argmax (x)).
xeX
We consider the following 2 cases: Case 1: If (X,,) (x,),, then
& V X E argmax (x))
XEX
Case 2: If ue (x,,) o (x.) which implies that & E St (k) and (x())) > ue (xe)),. then we prove
that un (&t)= = (x.)) by contradiction. Assuming that
ue (xx,) up (x))
(25)
Let us consider the following upper confidence bounds of pairwise orderings:
Po (Xecke) = max(O, ux()) lxxx)) = ux (x.) - 4, (xx,) > 0
Nny (Re)))) max(0, (x.)) (xx)))
14

---

Furthermore, from the choice of X;) in 111 and & S/ (k),
Pape (K)) 2 P (t)
(K..8.))
Hence,
max(O, us (x() - (x()) 2 max(0, ux(e)) - 1((x))) (8())) - (xx)) > 0
un (x,) - (xx)) We (Xx) 4, (Xtr)
U4 (x()) 2 24 (x,)
which contradicts to the assumption
25
Therefore, (x,)) ue (x() and
X X E argmax (x).
XEX
F Upper Confidence Bound of the Regret (1)
(G))
max (x,x')EEX X (xxx,x)))xxxxx211
With probability of least 1 - 8, for all t 2 1 and for all {x,x'} C X, T=(xx))= $
(xxxx)= Therefore, with probability of at least 1 - 6, for all 2 1 and for all (x,x) C N.
( (xxx")xaxx x ( & (t) (1)
(1( S
max
G Transitivity of Pairwise Orderings
The transitivity property of the binary relation Aa, follows directly from its connection to the GP posterior mean in Lemma 3.5 In particular, would like to show that if
I (x, x')
=1
Tue (x, x")
(26)
then
Tue xx) = =1 the premise (6 implies that
From Lemma 3.5
(x) 2 Hx(x') mx(x)) 2 me(x"")
which implies that
(x(x)= me(x")
Applying Lemma
3.5 again, we conclude
Mu (x,x") =1
H
Proof of Lemma 4.3
Applying Lemma 3.6 the input pair (x,, x(), by selecting x, E &
(x,()
PTu, (x.,
(t)
Furthermore, from the choice of (xx, x() in 11
(x.x')es,, Se (x.x) = (1)
Pap (2),2()
max
P (S,,
Therefore,
(x((x) 2 (9)
(S,, (K)
15

---

Algorithm 2 Mean Prediction (MP) for Active Multiple Set Ordering
Require: X, Do. {ki, , T
I: for t- = to T do
2: Update GP posterior belief: (4x(x) /xEx (x)(x))xxx)
3: Construct {S (k:) as the collection of m top-k sets predicted using pa. (8)
Prediction
4: (Re, x1) - argmax (E. Say (k) (lx) Pn (x.x)
5: Select X, {& V & & V & & A 82).
Sampling input
6: yr(D,) t (
7: end for
8: Update GP posterior belief: {uT+1 xxEX, for+1 [xEx-
9: Construct (S (k:) the collection of top-k sets predicted using pT+1-
10: return (Spria (ks) /er
I Proof of Theorem 4.4
By choosing x2 following Lemma
4.3
with probability of at least 8, for all 2 1,
Ta (Sn, (k), (8)) S Px (Sn, (N), (l)) S [Cx(x.) = / (x()))
Furthermore, from the non-decreasing property the sequence (Be))==
E Ta (S,, (8),, (1))), (K))
- 23 (x1) s 2 Σ ox())
By utilizing the result from
5 like Appendix
D we can obtain
T
Σ (x)) - ((TTT)).
Therefore, with probability of at least 1 - 8, for all T 2
T
28 ox()) s (3(TT))))
i.e.
RT. A
Tan (S,, (0),8, S O ((VTBmT))
Active Multiple Set Ordering
The pseudocode of MP algorithm for the active multiple set ordering problem is shown in Algorithm 2 In the rest this section, we prove the cumulative regret bound Algorithm
We recall that in
(xc, x A
(t) PF (xxx))
argmax (x x (k:))
Therefore,
max Vi E (1,,,..., m,,, PTo (2), ((x))s(())))
(4)
P Pru (x,x))
(t)
P (kr,,, (ki))
Furthermore, applying Lemma 3.6 to the input pair (X,, R)), for any x; E (3x v & X, A 2
[c((x))] 2 P (R.))))
(8)
16

---

Therefore,
W (1,
C [((xx)) 2 PF (8mg (Hi),,2,
(4)
Hence, with probability of at least 1 - 8, for all t 2 1,
Vi E (1,2,...,,A m), 1m (S,, (1:)) As result, with probability of at least 1 - 6, for all T 7211
Pax (S (Hi), $ (c((x))
(1)
T
T
E E f1, m). Ry.k. where the last inequality comes from Appendix
Σ
(S
S (Spe (Hs).
(((x)) SO(VTBrM)
1=1
K
Experiments
All experiments were conducted on computer equipped with an AMD Ryzen 7 6800HS processor and 16GB of RAM.
To generate a function sampled from a GP, we randomly generate 3 observations {(x,, 3xx))) } and fit GP model to these observations. Then, we sample function evaluations at all inputs the domain from the GP posterior distribution. These function evaluations are considered the evaluations of the blackbox function. To generate an observation at a sampling input, we add a Gaussian noise (of o, 0.1) to the evaluations of the blackbox function at the sampling input.
The expressions for the Branin-Hoo and Goldstein-Price functions are described [20 We transform the input domain of these functions to [o, 1J2 and standardize the function evaluations. The input domain is discretized into 100 points randomly selected in the domain [0, 1|2 The noise is chosen with n, 0.1.
To perform experiments with the NO₃ dataset from Lake Zurich (available at htttt::///ss //wldbb ilec or jp/Laee/ EUR 06/ (osdatalist), we standardize the NO₃ measurements, Then, a GP model is trained on the standardized dataset to generate the noisy evaluations of the blackbox function over n = 100 randomly chosen locations.
We use the logarithmic values of the phosphorus measurements in the soy survey of Brooms Barn 22 to construct blackbox function. The locations are normalized to the range [0, 1]2 and the logarithmic values of the phosphorus measurements are standardized. Then, we train GP model to generate the noisy evaluations of the blackbox function over n 400 randomly chosen locations.
To perform experiments with the humidity dataset, we extract the humidity measurements at different locations with the same mote id of 31167 from the Intel Lab data (available at htttp:://db. csail mit.
aatisaaaaaaaaaaaaaaaaaaa htmml. html). The humidity measurements are standardized. Then, a GP model trained this extracted dataset to generate the noisy evaluations of the blackbox function over n 100 randomly chosen locations.
To remove the potential inefficiency due to repeated sampling in Rand and Var, we provide additional experiments by replacing the Rand and Var baselines with RandNoRepl and VarNoRepl, which do not allow repeated sampling. This modification potentially gives RandNoRepl (random sampling without replacement across different iterations) and VarNoRepl (uncertainty sampling without replacement across different iterations) an additional advantage over our solutions which allow repeated sampling. By avoiding repeated sampling. RandNoRepl and VarNoRepl can sample the input domain more uniformly, whereas our methods might re-sample certain input regions. However, as shown in Figure 5] RandNoRepl and VarNoRepl still do not outperform our solutions. The justification for the efficiency of our solutions is in the nature of noisy observations: With a noise standard deviation of on = 0.1, a single observation at each input may not suffice to accurately determine the ordering with its neighboring inputs in terms of the function value. Hence, spreading the sampling budget across the whole input domain may not perform well. In contrast, our approach allocates more sampling inputs to the boundary the top-k set, where is particularly challenging to check if inputs belong to the top-k set (see Figure
17

---

Rand
RandNoRepl
Var
VarNoRepl
A
R.V
R
% x
102
102
10º
10a
Regret
Regret
100
10c
10
10-1
10-2
50
100
50
100
Iteration
Iteration
(a) Branin-Hoo
(b) Goldstein-Prine
Figure 5: Plots of the regret against the iteration in estimating the top-5 set S(t).
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Our contributions include introducing the active set ordering problem, design- ing novel solution with theoretical performance guarantee, and investigating a connection to Bayesian optimization. The experiments are performed environmental monitoring datasets which aligns with the motivation in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations are elaborated as assumptions the paper including: a finite input domain of the blackbox function (see Sec. 2.T and the blackbox function belonging to a reproducing kernel Hilbert space with bounded norm (see Sec.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
18

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have provided the proofs for all theoretical results in the appendix of the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have described the experiments and provided the code and datasets for reproducing the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same
19

---

dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-sonnee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided the source code, datasets, and scripts to reproduce the experiment results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co public/guides/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nniss /mipsscc/pptlee httpscccccpcbgcueeeeeeeeeeeeeeee httpc//gguuieee/eoouuuubibibbiia ssioooolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
20

---

Justification: We have provided the URLs where datasets are downloaded and described parameters used in the experiments such as the size of the input domain and the noise variance. Other parameters such as the random seed are configured in the submitted code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have repeated the experiments with different random seeds and reported the average and standard error of the experiment results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the computer resources in Appendix K
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
21

---

Question:
Does the research conducted in the paper conform, in every respect, with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We ensure that the research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work proposes a general active learning problem that does not have any direct path to any negative applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
22

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the sources and/or provided the URLs to all public datasets used in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, hatpssttss.pprssttttt. paperswi thcode. com com/datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "NNZcqms765", "reviewer": "Reviewer_gNpn", "summary": "This paper introduces the \"active set ordering\" problem, which aims at recovering the top-k actions in a set by strategically sampling actions. The authors formally define the problem in the regret minimization setting and propose an algorithm for that. They authors upper bound the regret and run experiments the test the proposed algorithm.", "questions": "See comments above.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors introduced the problem of recovering top-k actions in the regret minimization setting, and developed an algorithm for that. The authors theoretically show their algorithm enjoys a \\sqrt{T} type of regret (after ignoring some problem dependent quantities). Experimental results show the proposed algorithm has good performance.", "weaknesses": "1. The authors didn't explicitly quantify some problem-dependent quantities in their regret bound, e.g., \\gamma_T and \\beta_T. How large these quantities are in different settings? \n2. A lower bound analysis is missing, which make it even harder to know if the upper bound is tight or not.\n3. While I understand the studied setting is slightly different from top-k arm identification, the proposed algorithm is actually quite similar to algorithms proposed in top-k arm identification: I believe some appropriate acknowledgement is missing in the paper.\n4. The wording \"set ordering\" in misleading: the goal of this paper is not to recover the set ordering but simply identifying the top-k actions in the regret minimization setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for dedicating their time and effort to reviewing our paper and for recognizing the regret analysis and the experimental results. Additionally, we would like to draw your attention to two other contributions: multiple top-$k$ sets, and the new perspective of ordering for BO in the global response. We will address your remaining concerns as follows.\n\n> 1. The authors didn't explicitly quantify some problem-dependent quantities in their regret bound.\n\nWe follow most of the works in the BO and LSE literature (e.g., [8,18]) to demonstrate a desirable asymptotic property of the algorithm: sublinear cumulative regret, i.e., $\\lim_{T \\rightarrow \\infty} R_T / T = 0$. It implies the convergence of the algorithm as $\\\\min\\_{t \\\\le T} r\\_{ \\\\pi\\_{\\\\mu\\_t}( \\\\mathcal{S}\\_{\\\\mu\\_t}(k), \\\\mathcal{S}^c\\_{\\\\mu\\_t}(k) ) } \\\\le R\\_T / T$, i.e., vanishing per-round regret.\n\nIn this line of work (from [18]), the cumulative regret bound is often expressed in terms of problem-independent quantities $\\beta_T$ and $\\gamma_T$, which depend on the kernel.\nThe work of [18] discusses the values of $\\gamma_T$ for several common kernels (which are referred to in lines 151 and 200). We will clearly state the value of $\\gamma_T$ in the revised paper. For example, $\\gamma_T = \\mathcal{O}((\\log T)^{d+1})$ for the squared exponential (SE) kernel (this kernel is used in our paper). The value of $\\beta_T$ is elaborated in Lemma 2.2. Hence, by substituting $\\gamma_T$ and $\\beta_T$ into the cumulative regret bound and simplifying, we can obtain $R_T \\le \\mathcal{O}^*(\\sqrt{T (\\log T)^{2d}})$ (where $\\mathcal{O}^*(\\cdot)$ denotes asymptotic expressions up to dimension-independent logarithmic factors and $d$ is the dimension of the input).\nThis is the same as the cumulative regret bound of GP-UCB that is known to match the lower bound of the Bayesian optimization (BO) problem for the SE kernel. We will rely on this result to discuss how tight our cumulative regret bound is relative to the lower bound of the active set ordering problem in the following paragraphs.\n\n> 2. A lower bound analysis is missing.\n\nLet the lower bound of the active set ordering problem be the lower bound of the cumulative regret of the worst-case problem instance over all possible values of $k$. Then it should be at least as large as the lower bound of the special case where $k = 1$. This special active set ordering problem with $k=1$ is the Bayesian optimization (BO) problem, according to our Remarks 4.1 and 4.5. Furthermore, BO has known lower bounds for several common kernels: for example, for the SE kernel, the lower bound of the cumulative regret is $\\Omega(\\sqrt{T(\\log T)^{d/2}})$, (from the paper \"Lower bounds on regret for noisy Gaussian process bandit optimization\" by Scarlett et al., 2018). Hence, the lower bound of the active set ordering problem is at least $\\Omega(\\sqrt{T(\\log T)^{d/2}})$. Therefore, for the SE kernel, the cumulative regret bound $R_T \\le \\mathcal{O}^*(\\sqrt{T (\\log T)^{2d}})$ of our algorithm matches the lower bound up to the replacement of $d/2$ by $2d + O(1)$.\n\nWe have discussed the lower bound of the problem by considering the worst-case problem instance over all values of $k \\ge 1$, rather than the lower bound of the problem for a specific value of $k \\ge 1$. Thus, one may wonder if finding the top-$k$ set for a specific value of $k > 1$ is easier than solving it for $k = 1$ (BO problem). Regarding this question, we suspect that finding the top-$k$ set in active set ordering for a specific value of $k > 1$ is at least as hard as finding the top-$1$ set, i.e., the Bayesian optimization (BO) problem, for the following reasons.\n\n+ By intuition, suppose the $f$ is known. Finding the top-$k$ set requires $\\mathcal{O}(n\\log k)$ time complexity, while finding the top-$1$ set only requires $\\mathcal{O}(n)$ time complexity where $n = |\\mathcal{X}|$ is the size of the input domain.\n\n\n+ Moreover, BO is reducible to the problem of finding a top-$k$ set for any $k \\ge 1$. Let us consider a value of $k > 1$ and a BO problem instance defined by a function $f(x)$ where $x$ belongs to a finite input domain $\\\\mathcal{X}\\_f$. Suppose we know an upper bound $U$ of $f(x)$, i.e., $U > \\\\max\\_{x \\\\in \\\\mathcal{X}\\_f} f(x)$ (this upper bound need not be strict).\nWe can create a new function $g$ defined on $\\\\mathcal{X}\\_f \\\\cup \\\\mathcal{X}\\_g$ where $|\\\\mathcal{X}\\_g| = k-1$ such that:\n    + For all $x \\in \\mathcal{X}_f$, $g(x) = f(x)$\n    + For all $x' \\\\in \\\\mathcal{X}\\_g$, $g(x') = U > \\\\max\\_{x \\\\in \\\\mathcal{X}\\_f} f(x)$.\n\nThen, both the maximizer $x\\_*$ of $f$ and $\\mathcal{X}\\_g$ are part of the top-$k$ set $\\\\mathcal{S}(k)$ of $g$.\n\nAs $|\\mathcal{X}\\_g| = k - 1$, we have $\\\\{x\\_*\\\\} = \\\\mathcal{S}(k) \\\\setminus \\\\mathcal{X}\\_g$.\n\nTherefore, the problem of maximizing $f$ is reducible to the problem of finding a top-$k$ set of $g$, i.e., finding the top-$k$ set is as least as difficult as solving BO. Hence, the lower bound of the active set ordering problem is at least that of BO problem.\n\n> 3. I believe some appropriate acknowledgement (of top-k arm identification) is missing in the paper.\n\nAs you may have noticed, we discussed the difference between our work and the best-$k$ arm identification problem in *the footnote* on page 2. We also acknowledged the similarity with best-$k$ arm identification [12] in the intuition of choosing the input pair in *line 185*. Yet, our approach is different in several ways:\n\n+ The choice of sampling input (Lemma 3.6).\n+ The regret bound based on the maximum information gain.\n+ The justification of mean prediction (Sec. 3.2).\n+ Multiple top-$k$ sets (Remark 4.6).\n+ A new perspective on the well-known BO solution.\n\n---\n\nThank you for your patience in reading our response. We sincerely hope that the above clarifications have improved your opinion of our paper. We will carefully incorporate your valuable feedback and the points discussed above into the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WkLnqrKbxl", "reviewer": "Reviewer_2jNL", "summary": "This paper generalizes the best $k$-arm identification problem to Gaussian processes with the goal to estimate the set of the best $k$ function evaluations $f(x)$ on a finite domain $X$, where $k=1$ corresponds to standard Bayesian optimization. The proposed regret notion is a natural adaptation of the common regret $f(x*)-f(x_t)$ in Gaussian process bandits.\n\nThe paper is accompanied by some first experiments on benchmark datasets.", "questions": "What is the computational complexity/runtime of your approach? Is the runtime exponential in $k$?\n\nHow does your work relate to Gaussian bandit papers with correlated/dependent arms (e.g., Gupta et al. 2021, Pandrey et al 2007)\n\nHow does the results here relate to e.g., the \"Interactive submodular bandit\" by Chen et al. [ICML, 2017] (and related), where a submodular function is maximized in a similar fashion (in a GP-style context). Can your $k$ best selection problem be cast as a submodular (or even simply modular) set optimization problem? Are the two regret variants comparable?", "limitations": "The finiteness assumption on $X$ seems rather restrictive. Can $X$ be countable, or even say a compact subset / interval? Standard work on Gaussian processes with regret bounds (Srinivas et al., etc.) does not have this restrictions. For finite $X$ less assumptions might be possible, see e.g., Theorem 1 by Krause & Ong (NeurIPS 2011) (for example, no explicit assumptions on the rkhs norm as you do in Lemma 2.2, which they only require for arbitrary domains $X$).\n\nAlso in general the related work is not discussed sufficiently well, see questions.\n\nPlease, also see the questions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Interesting problem.\n\n---- rebuttal ----\nchanged from 5 to 6.", "weaknesses": "Finiteness assumption seems rather strong and limits this work. Also, the significance of the results (Thm 3.7 and 4.4) is not fully clear to me, as the paper seems to be mostly relying on known techniques (for kernelized bandits, and Gaussian process bandits), while the related work is not sufficiently well discussed (see questions and limitations).\n\nAm happy to raise my score, if my concerns are addressed. Specifically about the comparison to previous and related literature.\n\nThe definition of $\\pi_*(X_0,X_1)$ seems only partial, i.e., what if there exists some $x_0$ that are larger than some $x_1$ and some $x_0'$ that are smaller than some $x_1'$\n\nMinor comments:\n* The notation is a bit convoluted. E.g., do you really need double bars and dashes for $x$. Even just tilde&dash is not great. E.g., in the beginning of section 3 you could just do $x,x'$ without the tilde (or you use $y$ etc.).\n* Please do not mix definitions (in particular of important notation) and lemmas (e.g., Lemma 3.6, 3.1, ...).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and for appreciating our interesting research problem. We will address the questions and concerns raised by the reviewer as follows.\n\n> the significance of the results is not fully clear to me, as the paper seems to be mostly relying on known techniques\n\nTheorems 3.7 and 4.4 are to show that the cumulative regret of our proposed solution is sublinear. This is a desirable property for BO solutions ([18]) ensuring that the simple regret approaches 0. While the techniques are mainly drawn from the BO literature, it is noted that\n\n+ Many existing BO works also employ similar techniques to demonstrate sublinear cumulative regret, with their novelty often lying in new problems. Similarly, our paper makes a unique contribution by addressing the problem of active (multiple) set ordering.\n\n+ While we build on established techniques, our paper works with a new notion of regret (pairwise and set ordering) that differs from those in the existing BO literature.\n\n+ To the best of our knowledge, we are the first to investigate BO from this pairwise ordering perspective.\n\n> Is the runtime exponential in $k$?\n\nIn line 3 of Algo 1, it takes $\\mathcal{O}(n \\log k)$ to find the top-$k$ inputs by using a max heap of size $k$ and scanning through the GP posterior mean of all inputs. In line 4 of Algo 1, we need to scan through the elements in $\\\\mathcal{S}\\_{\\\\mu\\_t}(k) \\\\times \\\\mathcal{S}^c\\_{\\\\mu\\_t}(k)$, so it takes $\\\\mathcal{O}(k (n - k))$. Together with the updating of GP, the runtime of an iteration is $\\mathcal{O}(m_t^3 + n m_t^2 + n \\log k + k (n - k))$, which is not exponential in $k$. Specifically, it is linear in $k$ as the last term is bounded by $k(n-k) < k n$. Due to lack of space, please refer to our response to reviewer Qpjm for a detailed derivation of the complexity.\n\n> How does the results here relate to e.g., the \"Interactive submodular bandit\" by Chen et al. [ICML, 2017]?\n\nOur results are different from those in Chen et al. (ICML, 2017):\n\n+ First, Chen et al. (2017) model the utility function as *a set function* that takes a set of inputs. Hence, the submodular property is utilized to avoid the exponential nature of the combinatorial problem. In our problem, the utility function (the black-box function) is *defined for each individual input* in the domain, which is equivalent to an additive set function. Our goal is to find the set of $k$ inputs with the highest function evaluations. This is simpler than the general submodular set function, as it *does not incur exponential time complexity for exact solution*.\n\n+ Second, the set of interest $S_j$ (using the notation of Chen et al. 2017) is *built sequentially through interaction*, meaning $S_j$ is the set of all sampling inputs up to that point. However, in our problem setting, the top-$k$ set is estimated as the set of top $k$ inputs with the highest GP posterior mean, denoted as $\\mathcal{S}_{\\mu_t}(k)$. The inputs in this set are *not necessarily those that have been sampled*.\n\n+ Third, the optimal set of interest $S^*_j$ is defined as the set having a cardinality of *at most* $T_j$ elements, where *$T_j$ depends on the sampling procedure* (refer to Equation (2) in Chen et al., 2017). This differs from from our optimal (and estimated) top-$k$ set which has a cardinality of *exactly* $k$ where *$k$ is specified before the sampling procedure*.\n\nTherefore, the notion of regret used by Chen et al. (2017) relies on a different concept of optimal set that does not apply to our context. Additionally, it is also noted that the regret definition in Chen et al. (2017) is not based on pairwise ordering, which is the building block of our regret.\n\n> How does your work relate to Gaussian bandit papers with correlated/dependent arms\n\nWe assume that Gupta et al. 2021 refers to the paper titled \"A unified approach to translate classical bandit algorithms to the structured bandit setting\" and Pandrey et al. 2007 refers to the paper titled \"Multi-armed bandit problem with dependent arms\". These two papers are different from our work as follows.\n\n+ The problem: Both Gupta et al. (2021) and Pandrey et al. (2007) are interested in the arm with the maximum reward, while our work focuses on the top-$k$ set.\n\n+ Model of dependent arms: Gupta et al. (2021) assumes parametric models for the mean rewards, while Pandrey et al. (2007) assumes that the arms are grouped into known clusters and that the rewards of arms are described by a known generative model with unknown param. In contrast, our work uses a GP (non-parametric) without any assumptions about input clusters.\n\nGiven the rich literature, we selected the most relevant works in the kernelized bandit and BO literature (modeling the dependency with GP) [1, 5, 8, 14, 18]. Still, our work differs from them: *the goal of finding top-$k$ set(s)*, *the regret definition based on pairwise ordering*, and *the prediction based on GP posterior mean*.\n\n> The finiteness assumption on $X$ seems rather restrictive.\n\n+ The top-$k$ set is undefined for continuous domain. E.g., take $f(x) = -x^2$ with $x \\in [-1,1]$. While $x = 0$ is the maximizer, pinpointing the input with the 2nd highest function value is impossible (i.e., defining a top-$2$ set is problematic). Thus, finiteness is critical for solving the problem of finding the top-$k$ set.\n\n+ The finiteness assumption is also common in environment monitoring applications (our motivation) such as in [8].\n\n> assumptions on the rkhs norm ... only require for arbitrary domains $X$\n\nThank you for the insightful comment regarding the RKHS norm. We will revise the paper to include this additional consideration as an alternative.\n\n---\nThank you for taking the time to read our response. We sincerely hope that the explanations provided above address your concerns and enhance your perception of our paper. We will incorporate your additional suggestions regarding the notation into the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8NmEQhj9Fk", "reviewer": "Reviewer_Qpjm", "summary": "The paper poses a novel active learning problem formulation of active set ordering, in which we aim to identify the data points that yield the top- and bottom-$k$ values via a given objective function.\nThis active learning goal serves as a compromise between Bayesian experimental design which focuses solely on learning and Bayesian optimization targeting optimization, and poses as an alternative to level-set estimation, especially in scenarios where a level-set threshold is not easily determined.\nThe authors first define an appropriate metric of regret, propose using the mean prediction of the surrogate Gaussian process to generate an ordering of the data points to recommend to the user, and finally develop an acquisition function that aims to reduce an approximation of the regret resulting from that posterior predictive ordering.\nThe paper presents various theoretical results bounding the regret of the proposed algorithm, and experiments are conducted to illustrate the empirical effectiveness of the algorithm.", "questions": "- The search space sizes in the experiments are quite small.\nDoes the algorithm scale well to large search spaces?\nWhat’s the computational complexity?\nDoes it take quadratic time with respect to search space size (because we need to iterate over all pairs)?\n- Any insights on how the different variants behave and which should be preferred in which situations?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I find active set ordering to be an interesting active learning problem that is related to other common active learning problems (experimental design, level-set estimation, Bayesian optimization).\nThe various algorithmic choices made throughout the paper are reasonable and well-motivated by theoretical insights.\nThe experiments include a wide range of synthetic and real-world tasks, and do a good job showing that the proposed strategy yields competitive performance against baselines.", "weaknesses": "- The presentation of Sections 3 and 4 is a bit hard to follow.\nI understand Section 3 serves as the base case where we develop the core tools which are then further extended in Section 4, but the narrative has a jumping-back-and-forth feel that I find somewhat confusing.\n- The claims the authors make in Section 1 to motivate the problem might be too strong.\nI would say something along the lines of, this work presents an alternative to LSE when setting the threshold is difficult (as opposed to that it should replace it, since sometimes a desirable threshold is known, in which case LSE should be preferred).\n- I would include LSE acquisition functions (e.g., STRADDLE) among the baselines in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for dedicating their time to review our paper and for acknowledging the interesting research problem situated at the intersection of experimental design, level set estimation, and Bayesian optimization. We are delighted to learn that the reviewer finds our paper to be theoretically sound, well-motivated, and supported by a wide range of experimental results. We would like to address and clarify the remaining concerns as follows.\n\n> I would include LSE acquisition functions (e.g., STRADDLE) among the baselines in the experiments.\n\nAs LSE requires a known (or implicit) threshold, which is absent in our problem setting, including their acquisition functions (e.g., STRADDLE) among the baselines in the experiments is not immediately obvious to us.\n\n\n> The search space sizes in the experiments are quite small. Does the algorithm scale well to large search spaces? What’s the computational complexity? Does it take quadratic time with respect to search space size (because we need to iterate over all pairs)?\n\nUpdating the GP posterior belief incurs $\\mathcal{O}(m_t^3 + n m_t^2)$ computational complexity (including $\\mathcal{O}(m_t^3)$ for training and $\\mathcal{O}(n m_t^2)$ for prediction, where $m_t$ is the number of observations at iteration $t$ as we use the exact GP model). This complexity can also be reduced using sparse GP approximation. Given the GP posterior belief, our algorithm involves the following major steps outlined in Algorithm 1:\n\n+ Line 3: Constructing $\\mathcal{S}_{\\mu_t}(k)$ takes $\\mathcal{O}(n \\log k)$ to find the top-$k$ inputs by using a max heap of size $k$ and scanning through the GP posterior mean of all inputs.\n\n+ Line 4: We need to scan through the elements in $\\\\mathcal{S}\\_{\\\\mu\\_t}(k) \\\\times \\\\mathcal{S}^c\\_{\\\\mu\\_t}(k)$, so it takes $\\\\mathcal{O}(k (n - k))$.\n\nTherefore, the runtime of each iteration is $\\mathcal{O}(m_t^3 + n m_t^2 + n \\log k + k (n - k))$ which is not quadratic in the search space size ($n$). Specifically, it is linear in $n$.\n\nTo further strengthen our experimental results, we have included additional experiments featuring a larger search space, $|\\mathcal{X}| = 1000$, and an increased input dimension, $d=6$. They can be found in the attached PDF file of the general response.\n\n> Any insights on how the different variants behave and which should be preferred in which situations?\n\nBased on the cumulative regret bound, we do not have a preference for any particular variant since they all result in the same sublinear cumulative regret bound. However, when $k = 1$, we prefer $\\\\bar{x}\\_t \\\\triangledown \\\\bar{x}'\\_t$ because it is equivalent to $\\\\text{arg}\\\\max\\_{x \\\\in \\\\mathcal{X}} u\\_t(x)$, which can be computed in $\\\\mathcal{O}(n)$ time without the need to find the pair $(\\\\bar{x}\\_t, \\\\bar{x}'\\_t)$ (Remark 4.5). \nWhen $k = n - 1$, we prefer $\\\\bar{x}\\_t \\\\vartriangle \\\\bar{x}'\\_t$ because it is equivalent to $\\\\text{arg}\\\\min\\_{x \\\\in \\\\mathcal{X}} l\\_t(x)$, which can also be computed in $\\\\mathcal{O}(n)$ time without the necessity of identifying the pair $(\\\\bar{x}\\_t, \\\\bar{x}'\\_t)$ (Remark 4.5).\n\n---\n\nWe will revise the paper to incorporate the additional comments on the flow between Sections 3 and 4 as well as the motivation of the problem. We appreciate your patience in reading our response and sincerely hope that the above clarifications, along with the additional experimental results, address your remaining concerns and enhance your perspective on our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s5cZkatSdn", "reviewer": "Reviewer_i8Rj", "summary": "This submission proposes a novel Mean Prediction (MP) method for active set ordering problem. MP selects pre-defined k inputs with highest Gaussian Process posterior mean values through a novel sampling strategy. Theoretical analysis on the regret, the prediction and the sampling strategy of proposed method is discussed in details, and experiments on synthetic functions and real-life application prove the effectiveness of MP for ordering sets of inputs based on expensive evaluation on black-box function. The submission includes GP-UCB Bayesian optimization as a special case of active set ordering problem.", "questions": "1.  I'm not very convinced by the experiment design. For example the experiment on Goldstein-Price function (lines 248-251), the input domain is discretized into 100 points and a top-5 set based on posterior mean is sampled at each of the 100 iterations. Even repeated sampling is allowed in this paper, I still feel like almost the whole space which only consists 100 points has been sampled by doing so. How do the authors justify the efficiency compared to brute force sampling over the whole sample space?\n\n2.  In all experiment settings, the 100/400 points that represent the input domain $\\mathbf{X}$ are randomly sampled from normalized domain $[0, 1]^2$. If I understand correctly, each $\\mathbf{X}$ of the 15 repeated experiments is different, which lead to 15 different $S_{\\mu_t}(5)$ at the end of iterations. How do the authors decide which one of the $S_{\\mu_t}(5)$ is the true top-5 set for the objective black-box problem? (e.g. which 5 locations are the top-5 with highest $NO_3$ concentration in Lake Zurich?)\n\n3.  Could the authors explain how $S_{\\mu_t}(k)$ is constructed in line 3 of Algorithm 1? Are the posterior mean of all the points in $\\mathbf{X}$ evaluated? Similar for $(\\mathbf{\\bar{x}_t}, \\mathbf{\\bar{x}'_t})$ (line 4), are all possible pairs in $S_{\\mu_t}(k)$ evaluated?", "limitations": "See above for limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.  The paper presents adequate theoretical justification for their proposed method. The motivation for studying the active set ordering problem is clearly stated and the proofs on regret bound, prediction and sampling strategy seem valid to me.\n\n2.  The idea of formulating black-box function optimization into set ordering problem presents novelty to some extend. It provides some alternative sampling strategy by proposing the input set $Q_t$ in lines 145-146, which can be more informative than traditional metric such as sampling based on maximizing GP variance.", "weaknesses": "1.  My first concern regards the dimensionality of the problem setting. The theoretical justification of MP seems valid for any value of $d$ where $d$ is the dimension of the black-box function. However, in the Experiments section all the problems are 2-dimensional, which is insufficient to show how practical the proposed MP method could be in applications. \n\n2.  This sampling-based method only works on discrete space problems to me. The authors use classic GP model on continuous space as the surrogate model to compute posterior mean, but then sample on the discretized space during inference. This could be one of the major limitations of MP method because a lot of probabilistic information has been missed during the discretization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and for acknowledging the theoretical justification, motivation, and sampling strategy. We will now address the remaining concerns as follows.\n\n> 1. My first concern regards the dimensionality of the problem setting. \n\nWe have conducted additional experiments using the Hartmann-6D function to demonstrate the empirical performance of our algorithm in higher-dimensional spaces. Specifically, the input domain consists of $1000$ points, and the input dimension is $6$.\nThe results are shown in the attached PDF of the global response.\nThey show that our methods consistently outperform other baselines in identifying the top-$50$ set (illustrated in Figure 1b) and in simultaneously finding the maximizer, the top-$100$, and the top-$200$ sets (an active multiple set ordering problem, as illustrated in Figure 1c).\n\nFurthermore, we would like to highlight the practical applications of our problem. As discussed in the introduction, one such application is environmental monitoring, where the input domain is typically two-dimensional, like a geographical area. This focus aligns with several experiments based on real-world datasets presented in our paper.\n\n\n> 2. This sampling-based method only works on discrete space problems to me... This could be one of the major limitations of MP method because a lot of probabilistic information has been missed during the discretization.\n\nOur assumption is that the input domain is a discrete space, and we use an exact Gaussian Process (GP) model to represent the black-box function. According to the marginalization property of GPs, the function values at any finite subset of inputs (including the discrete input domain) follow a multivariate Gaussian distribution. Since we focus solely on function evaluations within this discrete domain and our observations are acquired exclusively from this discrete domain, we believe that no probabilistic information has been lost.\n\nTherefore, we would appreciate any guidance the reviewer can provide regarding the probabilistic information that might have been overlooked.\n\n> 1. I'm not very convinced by the experiment design... How do the authors justify the efficiency compared to brute force sampling over the whole sample space?\n\nThank you for your careful observation regarding the Goldstein-Price experiment (lines 248-251).\n\nWe have revised the experiment by replacing the Rand and Var baselines with RandNoRepl and VarNoRepl, which do not allow repeated sampling. The results are included in the attached PDF file of the global response. This modification potentially gives RandNoRepl (random sampling without replacement across different iterations) and VarNoRepl (uncertainty sampling without replacement across different iterations) an additional advantage over our solutions, which allow repeated sampling. By avoiding repeated sampling, RandNoRepl and VarNoRepl can sample the input domain more uniformly, whereas our methods might re-sample certain input regions.\nHowever, as shown in Figure 1a of the attached PDF, RandNoRepl and VarNoRepl still do not outperform our solutions.\n\nThe justification for the efficiency of our solutions is in the nature of noisy observations: With a noise standard deviation of $\\sigma_n = 0.1$, a single observation at each input may not suffice to accurately determine the ordering with its neighboring inputs in terms of the function value. Hence, spreading the sampling budget across the whole input domain may not perform well. In contrast, our approach allocates more sampling inputs to the boundary of the top-$k$ set, where it is particularly challenging to check if inputs belong to the top-$k$ set.\n\nThis rationale is also evident in the animation video included in the supplementary materials. Although the uncertainty sampling in the video allows repeated sampling, it distributes samples across the input domain quite evenly (as its goal is to reduce uncertainty throughout the entire input domain).\n\n\n> 2. How do the authors decide which one of the $S_{\\mu_t}(5)$ is the true top-5 set for the objective black-box problem?\n\nFor each repeated experiment, the set $\\\\mathcal{S}\\_{\\\\mu\\_t}(5)$ and the true top-5 set $\\\\mathcal{S}(5)$ are computed independently from those in other experiments. The regret for each experiment is calculated using only its own $\\\\mathcal{S}\\_{\\\\mu\\_t}(5)$ and $\\\\mathcal{S}(5)$. Therefore, it is unnecessary to identify a single set $\\\\mathcal{S}(5)$ for all repeated experiments, as the regret for each one is computed independently. The plot displays the average and standard error of the regrets across all repeated experiments.\n\n> 3. Could the authors explain how $S_{\\mu_t}(k)$ is constructed in line 3 of Algorithm 1?\n\nTo construct $\\mathcal{S}_{\\mu_t}(k)$, the posterior mean values of all inputs in $\\mathcal{X}$ are evaluated in $\\mathcal{O}(n m_t^2)$ time (time complexity for GP prediction), where $m_t$ is the number of observations at iteration $t$. Subsequently, it takes $\\mathcal{O}(n \\log k)$ time to identify the top $k$ inputs by using a max heap of size $k$ and scanning through the GP posterior mean of all inputs. It is worth noting that evaluating the posterior mean (and variance) of all inputs in $\\mathcal{X}$ is often necessary when $\\mathcal{X}$ is finite, as demonstrated in [8] and in cases of finite input domains described in [1,18].\n\nTo find $(\\\\bar{\\\\mathbf{x}}\\_t, \\\\bar{\\\\mathbf{x}}'\\_t)$ (Equation 11), we iterate through elements in $\\\\mathcal{S}\\_{\\\\mu\\_t}(k) \\\\times \\\\mathcal{S}^c\\_{\\\\mu\\_t}(k)$, which takes $\\\\mathcal{O}(k (n - k))$ time (linear in $n$).\n\n---\n\nThank you for patiently reading our response. We sincerely hope that the above clarifications address your concerns regarding the algorithm and our experimental results, and hence, improving your opinion on our paper. We will thoroughly incorporate your valuable feedback, along with the additional experiments, into the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their time and effort in reading and evaluating our paper. We are encouraged by the positive feedback and appreciation of our work regarding its novelty (reviewers Qpjm and i8Rj), theoretical soundness (reviewers Qpjm and i8Rj), and experimental results (reviewers gNpn and Qpjm).

---

We are pleased to summarize our contributions as follows.

+ We address the problem of estimating the top-$k$ set of a black-box function modeled by a Gaussian process. Specifically, we propose novel regret notions of pairwise ordering and set ordering. Then, we analyse the regret to justify our prediction and sampling strategy.

+ We extend our solution to accommodate the estimation of multiple top-$k$ sets, as discussed in Remark 4.6 and Section 5.2, driven by practical motivation in environmental monitoring applications.

+ We offer a novel perspective on the well-known GP-UCB algorithm through the lens of ordering (that has not been previously explored in Bayesian Optimization literature), which yields several nuanced insights (Remark 4.5).

---

In our response to the reviewers, we have provided additional clarifications, including:

+ Discussion on the lower bound of the proposed problem (reviewer gNpn).

+ Comparison between our work and existing studies (reviewer 2jNL).


+ The linear time complexity in the input domain size and linear time complexity in $k$ (reviewers 2jNL and Qpjm).

+ Additional experiments involving a 6-dimensional input domain in the PDF file attached in this response (reviewer i8Rj).

---

We genuinely hope that our response effectively addresses the reviewers' concerns and enhances their opinion of our paper. Your feedback is invaluable to us, and we are eager to incorporate it to further improve our work.

Meta-review: The reviewers generally agreed that this was an interesting problem, and the algorithmic tools were solid. The top-k problem clearly has lots of applications. While some reviewers were lukewarm about the work, we had a followup discussion with them and generally all reviewers were ok with accepting the paper for NeurIPS. I want to commend the authors for doing a good job in the discussion. But I want to recommend that particular care is taking in preparing the camera-ready, especially in incorporating the feedback received throughout this review process.
Decision: Accept (poster)