Contextual Active Model Selection
Authors: Xuefeng Liu
Fangfang Xia
Rick L. Stevens
Yuxin Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: model selection
active learning
online learning
Primary area: online_learning

Abstract: While training models and labeling data are resource-intensive, a wealth of pre-trained models and unlabeled data exists. To effectively utilize these resources, we present an approach to actively select pre-trained models while minimizing labeling costs. We frame this as an online contextual active model selection problem: At each round, the learner receives an unlabeled data point as a context. The objective is to adaptively select the best model to make a prediction while limiting label requests. To tackle this problem, we propose CAMS, a contextual active model selection algorithm that relies on two novel components: (1) a contextual model selection mechanism, which leverages context information to make informed decisions about which model is likely to perform best for a given context, and (2)
an active query component, which strategically chooses when to request labels for data points, minimizing the overall labeling cost. We provide rigorous theoretical analysis for the regret and query complexity under both adversarial and stochastic settings. Furthermore, we demonstrate the effectiveness of our algorithm on a diverse collection of benchmark classification tasks. Notably, CAMS requires substantially less labeling effort (less than 10%) compared to existing methods on CIFAR10 and DRIFT benchmarks, while achieving similar or better accuracy.

Contextual Active Model Selection
Xuefeng Liu'; Fangfang Xia², Rick L. Stevens Yuxin Chen'
Department of Computer Science, University of Chicago 2 PArgonne National Laboratory
Abstract
While training models and labeling data are resource-intensive a wealth of pre- trained models and unlabeled data exists. To effectively utilize these resources, we present an approach to actively select pre-trained models while minimizing labeling costs. We frame this as online contextual active model selection problem: At each round, the learner receives an unlabeled data point as a context. The objective is adaptively select the best model make prediction while limiting label requests. To tackle this problem, we propose CAMS, a contextual active model selection algorithm that relies on two novel components: (1) contextual model selection mechanism, which leverages context information to make informed decisions about which model likely to perform best for given context, and (2) active query component, which strategically chooses when to request labels for data points, minimizing the overall labeling cost. We provide rigorous theoretical analysis for the regret and query complexity under both adversarial and stochastic settings. Furthermore, we demonstrate the effectiveness of our algorithm on a diverse collection of benchmark classification tasks. Notably, CAMS requires substantially less labeling effort (less than 10%) compared to existing methods on CIFARIO and DRIFT benchmarks, while achieving similar or better accuracy.
Introduction
As pre-trained models become increasingly prevalent in a variety of real-world machine learning applications [2. 11, 53], there is a growing demand for label-efficient approaches for model selection, especially when facing varying data distributions and contexts run time. Oftentimes, no single pre-trained model achieves the best performance for every context, and a proper approach is to construct policy for adaptively selecting models for specific contexts [48]. For instance, in medical diagnosis and drug discovery, accurate predictions are of paramount importance. The diagnosis of diseases through pathologist or the determination compound chemical properties through lab testing can be costly and time-consuming Different models may excel in analyzing different types of pathological images [1, 23] or chemical compounds [17, 32, 46). Furthermore, in many real-world applications, the collection of labels for model evaluation can be expensive and data instances may arrive as a stream rather than all at once. This scenario necessitates cost- cesteeffcctive and robust online algorithms capable of determining the most efficient model selection policy even when faced with a limited supply of labels, a scenario not fully addressed by previous works that typically assume access to all labels [6, 2,,7,555 54].
Recently, the problem of online model selection with the consideration of label acquisition costs was studied in a contexi-free setting by Karimi et al. [39]. However, this approach doesn't ' fully capture the dynamics of data contexts that are essential in many applications. Recognizing this gap, this paper, we consider a more general problem setting that incorporates context information for adaptive model selection. We introduce CAMS, an algorithm for active model selection that dynamically adapts to the data context to choose the most suitable models for arbitrary data stream. As highlighted in
Correspondence to: Xuefeng Liu <xuefeng @uchicago.edus.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Sctup
Algorithm
bugging
[54]
Online hugging"
[27]
online learning
Hedge
P1 bundit
[7]
EXP4
contextual bundits
[65]
active learning
Query by Committee
model selection
[39]
MadelPicker
(ours)
(ours)
model selection
to iinfrorrrnnn
queries
conrexs-ane awarre
x
We regand "arms" as "models" when comparing CAMS against handit algurihhms, euch as EXPMEXP4
Online exsemble learning build composite model by aggrepating miltiple models than selecting the best model (for given context).
Table 1: Comparing CAMS against related work in terms of problem setup.
Table I, CAMS aims to address the need for adaptive and effective model selection, by bridging the gap between contextual bandits, online learning, and active learning.
Our key contributions are summarized as follows:
We investigate novel problem which we refer to as contextual active model selection, and introduce a novel principled algorithm that features two key technical components: (1) contextual online model selection procedure, designed to handle both stochastic and adversarial settings, and (2) an active query strategy. The proposed algorithm is designed to be robust to heterogeneous data streams, accommodating both stochastic and adversarial online data streaming scenarios.
We provide rigorous theoretical analysis on the regret and query complexity of the proposed algorithms. We establish regret upper bounds for both adversarial and stochastic data streams under limited label costs. Our regret upper bounds are within constant factors of the existing lower bounds for online learning problems with expert advice under the full information setting.
Empirically, we demonstrate the effectiveness and robustness of our approach on a variety of online model selection tasks spanning different application domains (from generic ML benchmarks such as CIFARIO to domain-speciff tasks in biomedical analysis), data scales (ranging from 80 to 10K), data modalities (i.e., tabular, image, and graph- based data), and label types (binary or multiclass labels). For the tasks evaluated, (1) CAMS outperforms all competing baselines by significant margin. (2) Asymptotically, CAMS performs no worse than the best single model. (3) CAMS is not only robust to adversarial data streams but also can efficiently recover from "malicious experts" (i.e. inferior pre- areitrained models).
2 Related Work
Contextual bandits. Classical bandit algorithms (e.g., [6, 7J) aim to find the best arm(s) through a sequence of actions. When side information (e.g., user profile for recommender systems or environmental context for experimental design) is available, many bandit algorithms can be lifted to the contextual setting: For example, EXP4 [7, 9, 52] considers the bandit setting with expert advice: At each round, experts announce their predictions of which actions are the most promising for the given context, and the goal is to construct a expect selection policy that competes with the best expert from hindsight. In bandit problems, the learner only gets to observe the reward for each an
action taken. In contrast, for the online model selection problem considered in this incoming data point-we we get
action corresponds to choosing model make prediction the loss/reward of all models on the labeled data point. By utilizing the information from unchosen arms, it could significantly reduce the cumulative regret. In this regard, this work aligns more closely with online learning with full information setting, where the learner has access to the loss of all the arms at each round (e.g. as considered in the Hedge algorithm [13, 14, 27, 36)).
Online learning with full information. A clear distinction between our work and online learning that we assume the labels of the online data stream are not readily available but can be acquired at each round with a cost. In addition, the learner only observes the loss incurred by all models on data point when decides to query its label. In contrast, in the canonical online learning setting, labels arrive with the data and one gets to observe the loss of all candidate models at each round. Similar setting also applies to other online learning problems, such as online boosting or bagging. A related work to ours is online learning with learning algorithm with matching upper and lower bounds on the regret. However, they consider a fixed query probability that leads to a linear query complexity. Our algorithm, inspired by uncertainty sampling in active learning, achieves an improved query complexity with the adaptive query strategy while maintaining comparable regret.
prediction [16], which proposes an online
2

---

Stream-based Active learning. Active learning aims to achieve a target learning performance with fewer training examples [64]. The active learning framework closest to our setting is query. by-committee (QBC) [65]. in particular under the stream-based setting [35, 47]. QBC maintains a committee of hypotheses; each committee member votes on the label of an instance, and the instances with the maximal disagreement among the committee are considered the most informative labels. Note that existing stream- based QBC algorithms are designed and analyzed assuming i.i.d. data streams. In comparison, our work uses different query strategy well as a novel model recommendation strategy, which also applies to the adversarial setting.
Active model selection. Active model selection captures a broad class of problems where model evaluations are expensive, either due to (1) the cost of evaluating (or "probing") a model, or (2) the cost of annotating a training example. Existing works under the former setting [49, 59] and
online setting [21, 66] often ignore context information and data annotation cost, and only consider partial feedback on the models being evaluated/ probed on i.i.d. data. The goal is to identify the best model with as few model probes as possible. This is quite different from our problem setting which considers the full information setting as well as non-negligible data annotation cost. [71] proposes that the optimal model choice is influenced by the sample size rather than any individual sample feature. [44] addresses the active model selection problem, however both works do not adopt a stream-based approach. For the later, apart from Karimi et al. [39], an online contextual-free model selection work, as shown in Table 1, most existing works assume pool-based setting where the learner can choose among the pool of unlabeled data [4, 29, 43, 49, 60, 61, 68, 76]. and the goal is to identify the best model with a minimal set of labels.
Problem Statement
Notations. Let X' be the input domain and y = (0,.... (O.....c-1)) be the set of e possible class labels for each input instance. Let F = (f...... f&e be a set of k pre-trained classifiers over X' x V. A model selection policy π : X' + A maps any input instance x E X to a distribution over the pre-trained classifiers F. specifying the probability x (xx of selecting each classifier under input x. 2 0}. One can interpret a policy т as an "expert" that suggests which model to select for given context x.
Here, A denotes the k-dimensional probability simplex {w R* w
Let 11 be collection of model selection policies. In this paper, we propose an extended policy set II := 11U {
= which also includes constant policies that always suggest a fixed model. Here, (.) == ej. and e, E A k-1 denotes the canonical basis vector with = 1. Unless otherwise specified, we assume is finite with [1I| = n, and [II*| S n + k. As a special case, when II = 6. our problem reduces to the contextual- free setting.
The contextual active model selection protocol. Assume that the learner knows the set of classifiers F as well as the set of model selection policies II. At round I, the learner receives a data instance x, E as the context for the current round, and computes the predicted label ft.. = J (xx) for each pre-trained classifier indexed by j E [K]. Denote the vector of predicted labels by all & models by :=:= l... xr,x T. Based on previous observations, the learner identifies model/classifier fj. and makes a prediction It,5, for the instance x₁. Meanwhile, the learner can obtain the true label ye only if it decides to query Xt- Upon observing yt, the leamer incurs a query cost, and receives a (full) loss vector l, = (,.) where the jth entry f,.j == ( corresponds to the 0-1 loss for model j E [K] at round t. The learner can then use the queried labels to adjust its model selection criterion for future rounds.
Performance metric. If If', is misclassified by the model je selected by learner at round t, i.c. Ut.j # yt, it will be counted towards the cumulative loss of the learner, regardless of the learner making a query. Otherwise, no loss will be incurred for that round. For learning algorithm A, its cumulative loss over T rounds defined as L := -E= 6,,..
In practice, the choice of model j, at round by the learner A could be random: For stochastic data streams where (x, y) arrives i.i.d., the learerr may choose different models for different random realizations of (xt, ).). For the adversarial setting where the data stream {(x,, (xx),)))) )+)) is chosen by an adversary before each round, the learner may randomize its choice of model to avoid a constant
loss at each round [33]. Therefore, due to the randomness of L consider the expected cumulative loss E [ as key performance measure of the learner A. To characterize the progress of A, we
3

---

consider the regret- formally fogmally defined as follows- as the difference between the cumulative loss received by the learner and the loss the learner selects the "best policy" x² E II in hindsight.
For stochastic data streams, we assume that each policy recommends the most probable model w.r.t. (x,xx) for ,, We use maxind(w)) := arg max E Wy to denote the index of the maximal- value entry" of w. Since (x, y) are drawn ii.d., we define μ4; + Σ Br.. (<n,m (x..)) This leads to the pseudo-regret for the stochastic setting over T rounds, defined as
RT (A) E E T min iE[[TT1]]
14.
In an adversarial setting, since the data stream (and hence the loss vector) is determined by an adversary, we consider the reference best policy to be the that minimizes the loss the adversarial data stream, and the expected regret
Rr (A) = =E
min Σ 4,a. 1E|
where le,s := (TT, (xx) .() denotes the expected loss if the learner commits to policy T,, randomizes and selects je (xx) (and receives loss Lt,s,) round t. Our goal is to devise a principled online active model selection strategy to minimize the regret as defined in (1) or (2), while maintaining a low total query cost. For convenience, we refer the readers to App. B for summary of the notations used in this paper.
4 Contextual Active Model Selection
In this section, we introduce our main algorithm for both stochastic and ad adversarial data streams.
1: Input: Models F. policies II, frounds T. budget b
Initialize loss La 6- O: query cost Co <-
21:
procedure
m))
3: Set II" II (Tpae .... m according to Eq. (3)
22:
IfSTCCHASTIC then
for == 1,,,...,
23:
12: Inm
Receive
Th < SETRATE(F, II*))
24:
end
25:
if ADVERSARIAL then
wus & exp (- Vi II])
26: Set as in adversarial setting section Inm
4 RECOMMEND(X...
27:
7t V vt clac
Output it.. ~ fr.. as the prediction for x
10:
Compute: 2, Eq. (4)
28: end
11:
Sample U. Ber (er(=:)
29: return
12:
if U. = 1 and C, S b then
30:
end prucedure
13:
Query lahel ye C. Cr-1 +
14:
29:
procedure RECOMMENDÚX, 4.) if STOCHAASIIC then
15:
Compute & Ea = (Bo. o uc) Vi [[=]]
30:
16:
Estimate model loss: f. f6. [F]]
31:
W; = Eiem- (x.))
17:
Update 2; b, - (x((x,), &.). [[T]]]]
32:
maxind(w.)
18:
L = 1
34:
33:
if ADVERSARIAL then
end
20:
19:
else
L L-11
35:
36:
d: end
jr mi (Xx)
21:
C. Ct-1
37:
22:
end
38:
return
23:
39:
end procedure
Figure 1: The Contextual Active Model Selection (CAMS) algorithm
Contextual model selection. Our key insight underlying the contextual model selection strategy extends from the online learning with expert advice framework [13, 27]. We start by appending the constant policies that always pick single pre-trained models to form the extended policy set the best model. Then, at each round, CAMS maintains a probability distribution over the (extended) policy set II", and updates those according to the observed loss for each policy. We use 4, := (qt.)keinni to denote the probability distribution over IIe at Specifically, the probability 4r,s computed based on
II (Line 3, in Fig. 1). This allows CAMS to be at least competitive
exponentially weighted cumulative loss, i.e. Gr,i x exp (-1teLr-1,) where L,, := E denotes the cumulative loss of policy i.
Assume ties are broken randomly.

---

For adversarial data streams, it is natural for both the online learner and the model selection policies to randomize their actions to avoid linear regret [33]. Following this insight, CAMS randomly samples a policy is i,. and-based on the current context x, Samples a classifier J: ~ Tú, (xx) to recommend round t.
Under the stochastic setting, CAMS adopts a weighted majority strategy [45] when selecting models. The vector of each model's weighted votes from the policies, w; Lig[T-] (t,eT: ) is interpreted as a distribution induced by the weighted policy. The model Jr = maxind(w:) which receives the highest probability becomes the recommended model at round t. This deterministic model selection strategy is commonly used in stochastic online optimization [33]. An alternative strategy to approach
in the adversarial setting, take a Follow-the- [42] and go with the most probable model recommended by the most probable policy (i.e. use W; maxinnd(, (xz)) ).As shown in experimental results section and further discussed in Appendix (outperformance over the best policy/expert section). CAMS outperforms these policies wide range of practical applications. The model selection steps are detailed in Line 5-9 in Fig. 1.
take randomized approach
Active queries. Under a limited budget, we intend to query the labels of those instances that exhibit significant disagreement among the pre-trained models F. To achieve this goal, we design adaptive query strategy with query probability 2, Concretely, given context X;. model predictions y, and model distribution w;, denote by 2 ;= (w., 11 (i. * y}) the expected loss if the true label is y. We characterize the model disagreement as
1 Σ
C (p. We) :=
loge e
(3)
DE
Intuitively, when ? is close to 0 or 1, there is little disagreement among the models in labeling x as y. otherwise there is significant disagreement. We capture this insight with function h(z) -r log
Since the label y/, is unknown upfront when receiving x,, we iterate through all the possible labels y y and take the average value in Eq. (3). Note that é takes similar algebraic form to the entropy function, although it does not inherit the information-theorrticc interpretation.
With the model disagreement term defined above, we consider an adaptive query probability
2 max 8% E w:)).
(4)
where 8/ - - E (0, 1] an adaptive lower bound on the query probability to encourage exploration at an early stage. The query strategy is summarized in Line 10-14 in Fig. 1.
Vi
Model updates. Now define U, ~ Ber (x, as a binary query indicator that is sampled from a Bernoulli distribution parametrized by z1. Upon querying the label yt, one can calculate the loss for each model /j E F as fx,, = II (ūr.j # }. Since CAMS does not query all the i.i.d. examples, we introduce unbiased loss estimator for the models, defined as Ea,j 4..i Ut. The unbiased loss z1
of policy E II* can then be computed as E {nT; (xx,, lej). In the end, CAMS computes the (unbiased) cumulative loss of policy म, as Tor, = Σ le,.. which is used to update the policy probability distribution in next round. Pseudocode for the model update steps is summarized in Line 15-21 in Fig. 1.
Remark. CAMS runs efficiently with time complexity O (nk) per round and space complexity O ((n + k)- k). At each round, each model selection policy specifies a probability distribution over the models for the given context. When these distributions correspond to constant Dirac delta distributions (regardless of the context), the problem reduces to the context-free problem investigated by Karimi et al. [39].
5 Theoretical Analysis
We now present theoretical bounds on the regret (defined in Eq. (1) and Eq. (2), respectively) and the query complexity of CAMS for both the stochastic and the adversarial settings.
For convenience of discussion, we assume that those rounds where all policies in 11* select the same models all models F make the same predictions removed precondition.
5

---

5.1 Stochastic setting
Under the stochastic setting, the cumulative loss of CAMS over T rounds specified by the RecoMMEnd procedure- L. = Σi= (,,maxin((ws) where recall we Eieju- (x is the probability distribution over FF induced by the weighted policy.
Let i" = arg min:e[[[[]]] [4: be the index of the best policy (14 denotes the expected loss of policy i, defined in problem statement section. The cumulative expected loss of policy i" is pu-- therefore the expected pseudo-regret (Eq. (1)) is Rr (CAMS) E
Σー= t=1 (w. - pus-
Define A := minger (1 pi-) ) as the minimal sub-optimality gap" in terms of the expected loss against the best policy i", Furthermore, let w == πT- (Ire) be probability distribution over J induced by policy i" at round t. We define 7 == minx, {max Wi max Ewi, sifmaxxiiii)) "i (5) as the minimal probability gap between the most probable model and the rest (assuming no ties) induced by the best policy i*. We further define = Pmin log, (1/Pmin), where Pmin = mins,5 ग (x.) denotes the minimal model selection probability by any policy". As our first main theoretical result, we show that, without exhaustively querying the labels of the stochastic stream, CAMS achieves constant expected regret.
Theorem 1. (Regret) In the stochastic environment, with probability least 8, CAMS achieves
constant expected pseudo regret Rr (CAMS)= [[r + +VIn [T-|-262 In
2
Vin JMT-AA
Note that in the stochastic setting, lower bound of (log IT*) /A) was shown in Mourtada and Gaïtfas [50] for online learning problems with expert advice under the full information setting (i.e. assuming labels are given for all data points in the stochastic stream). To establish the proof of Theorem I, we consider novel procedure to connect the weighted policy by CAMS to the best policy π... Conceptually, we would like to show that, after a constant number of rounds Teonss, with high probability, the model selected by CAMS (Line 32) will be the same as the selected by the best policy i". In that way, the expected pseudo regret will be dominated by the maximal cumulative loss up Teonst- Toward this goal, we first bound the weight of the best policy W4,5 by choosing a proper learning rate (CAMS, Line 23). Then, we identify constant threshold Teonst- beyond which CAMS exhibits the same behavior π;- with high probability. Finally, obtain the regret bound by inspecting the regret at the two stages separately. The formal statement of Theorem 1 and the detailed proof are deferred to App. E.I.
function of t,
Next, we provide an upper bound on the query complexity the stochastic setting.
Theorem 2. (Query Complexity). For c-class classification problems, with probability at least 1 - 8, the expected number of queries made by CAMS over T rounds is upper bounded by
[n! -1 +/In 11111122
2
+ +Tpp
Vla A
ciuc
Theorem 2 is built upon Theorem 1, where the the key idea behind the proof is to relate the number of updates to the regret. When T44- Lr,, are regarded constants (given by oracle), the query-complexity bound is then sub-linear w.t.. T. Note that the number class labels e affects the quality of the query complexity bound. The intuition behind this result is, with larger number of classes, each query may carry more information upon observation. For instance, in an extreme case where only expert always recommends the best model and others gives random recommendations of models (and predicts random labels), having more classes lowers the chance of a model making the correct guess, and therefore helps "filter out" those suboptimal experts in fewer rounds-hence being more query efficient. We defer the proof of Theorem 2 to App. E.2.
5.2 Adversarial setting
Now we consider the adversarial setting. Let Ī.T == min ΣT= le, be the cumulative loss of the best policy. The expected regret (Eq. (2)) for CAMS equals to Rr (CAMS) =
'w.loo.g assume there a single best policy, and thus > O.
'We assume Pmiin > 0 per the policy regularization criterion in Appendix C.3. (cf. Algorithm on "Regularized policy * )"".

---

R5
Crecle
QBC
INAL
MP
COBC
OWAL
CAMS
Curmllatve Jons
50
302
1000
2200
Query cost
Query cost
Query cost
Query cost
(a) CIFARIO
(b) DRIFT
(c) VERTEBRAL
(d) HIV
Figure 2: Main results. Comparison of CAMS with baselines across 4 diverse benchmarks in
terms of cost effectiveness. We plot the cumulative loss we increase the query cost for fixed number of rounds T and maximal query cost B (from left to right: ''' 10000, 3000, S0, 4000, and B 1200, 2000, 80, 2000). CAMS outperforms all baselines. Algorithms: contextual (Oracle, CQBC, CIWAL, CAMS) and 4 non-contextual baselines (RS, QBC, IWAL, MP) are included (see Section 90% confident interval are indicated in shades.
We show that under the adversarial setting, CAMS achieves sub-linear regret in 7 without accessing all labels.
E|Ei=1 (g. Lr...
Theorem (Regret) Let be the number of classes and Pt be specified as Line 26-27 in the SETRATE procedure. Under the adversarial setting, the expected regret of CAMS is bounded by
20 In c/c/ma//rr VI/T}- Tlog 111).
The proof is provided in App. F.I. Assuming Pr. to be a constant, our regret upper bound in Theorem 3 matches (up to constants) the lower bound of Ω (TTln [II*] for online learning problems with expert advice under the full information setting [15, 63] (i.e. assuming labels are given for all data points). Hereby, the decaying learning rate π)t as specified in Line 27 is based on two parameters, where 1/ vl corresponds to the lower bound 63 on the query probability, and max+ (w,, f yr } (6) is a (data-dependent) term that is chosen to reduce the impact of the randomized query strategy on the regret bound (especially when is large). Intuitively, Pe relates to the skewness of the policy where the max term corresponds to the maximal probability of most probable mispredicted label over rounds. Note that theory Pt can be small (e.g. CAMS may choose constant policy go E II" that mispredict the label for X,, which leads to P. 0); in such cases, result still translates Furthermore, in practice, we consider to "regularize" the policies (App. D.4) to ensure that probability policy selecting any model is bounded away from
sublinear regret bound of (ce/loge T /log [TT*))
Finally, the following theorem (proof in App. F2) establishes a query complexity bound of CAMS. Theorem 4. (Query Complexity). Under the adversarial setting, the expected query complexity over rounds is T
(V
Tlog/ll + +Ir,.
max (PX/TT
6 Experiments
Datasets. We evaluate our approach using five datasets: (1) CIFARIO [41] contains 60,000 images from 10 different balanced classes. (2) DRIFT [73] is a tabular dataset with 128-dimensional features, based on 13,910 chemical sensor measurements of 6 types of gases at various concentration levels. (3) VERTEBRAL [5] is a biomedical tabular dataset which classifies 310 patients into three classes (Normal, Spondylolisthesis, Disk Hernia) based on 6 attributes. (4) HIV [74] contains over 40,000 compounds annotated with molecular graph features and binary labels (active, inactive) indicating their ability to inhibit HIV replication. (5) CovType [24] has 580K samples and contains details including slope, aspect, elevation, measurements of area, and type of forest cover.
Policy sets. We construct the policy sets II for each dataset following a procedure similar to Meta-selector [48]. In this approach, a set of recommender algorithms considered, and Meta-selector assigns varying ratings to these algorithms based on the specific user. Concretely, we first construct set of models trained on different subsamples from each dataset. We then construct set of policies, which include malicious, normal, random, and biased policy types for each dataset
7

---

4016
1200
10020
3020
3020
9430
queeree
1000
200
IWAL
R5
3500
3:00
Cumulative loss
8030
6030
rest dassifier
3236
2000
Number
000
CGBC
CANS
5400
3200
6030
5030
2020
3200
4020
2430
2000
0
2003
1003
630
8500
1036
2000
0330
2003
aito
1052
232
410
100
193
1005
1291
50
100
155 201
350 103 395 100
Query cost
Round
Query cost
Query cost
(a) Query stralegy ablation study
(b) Query complexity study
(c) Context free environment
(d) Robust in pure adversarial set
182
50080
h5
17c
best palcyy CAMS
Cumulative 1022
Crack
2:0
QBC
320
150
(MX)
IARL
HP
250
Co3c
OWAL
COBC
CINAL
220
OWAL
con:
130
30000
CAMS
CAMS
130
CAPS
116
1300
2005
2008
4030
$930
130
105
30
X1
a03
900
X0 100 307
Query cost
Query cost
Query cost
Query
(e) Lurge datasel (COVTYPE)
(f) Adjust prub. (VERTEBRAL)
(g) Adjust probubility (IIIV)
(h) CAMS vs best policy (IIIV)
Figure 3: Ablation studies. (a) Comparing three query strategies (CAMS, variance- based, random}
under same model selection policy. (b) Comparing the increasing rate of CAMS' query cost over other baselines. (c) Comparing CAMS with MP in context-free environment. (d) Evaluating the
performance of CAMS under a pure adversarial setting. (e) Large dataset. (f.g) Adjustable query
probability. (h) CAMS outperforms the best single policy. The ablation study (a)-(d) conducted on CI.ARIO. For additional results on other benchmarks, please refer to the supplemental material.
based on different models and features. Details on the classifiers and policies are provided in the supplemental materials. The malicious policy provides contrary advice; the random policy provides random advice; the biased policy provides biased advice by training on biased distribution for classifying specific classes. The normal policy gives reasonable advice, being trained under a standard process on the training set. We represent the output of the ith policy as (xx). indicating the rewards distribution of all the base classifiers on Xe. In total, we create 80, 10, 6, 4 classifiers and 85, 11, 17, 20 policies for CIFAR10, DRIFT, VERTEBRAL, and HIV, respectively.
Baselines. We evaluate CAMS against both contextual and non-contextual active model selection baselines. We consider four non-contextual baselines: (1) Random Query Strategy (RS) which queries the instance label with a fixed probability 4: (2) Model Picker (MP) [39] that employs variance-
based active sampling with a coin-flip query probability max {ur (f. Wt) ; }. where the variance
term is defined as v (6.. we) = maxyey P4 (1 f:): (3) Query by Committee (QBC) implementing committee boame sampling [22]; and (4) Importance Weighted Active Learning (IWAL) [8] that calculates query probability based on labeling disagreements of surviving classifiers. Since no contextual baselines exist yet, we propose contextual versions of QBC and IWAL as (5) CQBC and (6) CIWAL Both extensions maintain their respective original query strategies but incorporate the context into the cumulative rewards. For model selection, CAMS, MP, CQBC, and CIWAL recommend the classifier with the highest probability. The other baselines use Follow-the-Leade (FTL), recommending the model with the minimum cumulative loss for past queried instances. Finally, we add (7) Oracle to represent the best single policy with the minimum cumulative loss, with the same query strategy as CAMS.
6.1 Main results
Fig. 2 visualizes the cost effectiveness of CAMS and the baselines. Here, we define cost effectiveness as the measure of how quickly the cumulative loss decreases in response to an increase in query cost, Fig. demonstrates that CAMS outperforms all the comparison methods across all benchmarks. Remarkably, it outperforms even the oracle on the VERTEBRAL (Fig. 2c) and HIV (Fig. 2d) bench- marks with fewer than 10 and 20 queries, respectively. In the case of the VERTEBRAL benchmark, CAMS outperforms the best baseline in query cost by a margin of 20%, despite the fact that 11 out of the 17 experts provided malicious or random advice. This level of performance attained by utilizing an active query strategy to retrieve highly informative data, thereby maximizing the differentiation between models and policies within the constraints of a limited budget. Additionally, the model selection strategy allows for effectively combining the expertise among the experts.
8

---

6.2 Ablation studies
Effectiveness of active querying. In Fig. 3a and Fig. 3b, perform ablation studies to demonstrate the effectiveness of our active query strategy. We fix the model recommendation strategy as the one used by CAMS, and compare three query strategies: (1) CAMS, (2) the state-of-the-art variance- based query strategy from Model Picker [39] (referred to as "variance"), and (3) random query strategy. Figure 3a demonstrates that CAMS has the fastest convergence rate in terms of cumulative loss on CIFAR I0, implying effective use of queried labels. Furthermore, CAMS not only achieves the minimum cumulative loss but also incurs significantly lower query costs, with reductions of 71% and 95% compared to the variance and random strategies respectively as showed in Fig. 3b. This suggests that CAMS selectively queries data to optimize policy improvement, whereas the other strategies may query unnecessary labels, including potentially noisy or uninformative ones, which impede policy improvement and convergence.
Robustness. In Fig. 2, 3c, 3d,3e, 3f, and 3g. CAMS exhibits robustness in a variety of environmental settings. Firstly, As shown in Fig. 2, CAMS outshines other methods in a contextual environment, whereas in Fig. 3c, a non-contextual (no experts) environment, it achieves comparable performance to the state-of-the-an Model Picker in identifying the best classifier. Secondly, CAMS is robust in both stochastic and adversarial environments. As demonstrated in Fig. 2, CAMS surpasses other methods in stochastic environment. Additionally, as illustrated in Fig. 3d, in a worst-case adversarial environment, CAMS effectively recovers from adversarial actions and approaches the performance of the best classifier (see App. G.5). We further observe that CAMS demonstrates robustness to varying scales of data, where the online stream sizes range from 80 to 10K (Fig. 2) to 100K (Fig. 3e, where we randomly sample 100K samples from the Type dataset [24]).
In Fig. 2, we assume that the stream length I is hidden and not used as input to CAMS. Under the stochastic setting, however, knowing 7' can provide additional information that one can leverage to optimize the query probability, thereby giving an advantage to some of the baseline algorithms (e.g. random). As an ablation study, in Fig. 3f and Fig. 3g, we assume the stochastic setting where the total length T of the online stream is given. Given the stream length T and query budget b, we may optimize each algorithm by scaling their query probabilities, so that each algorithm allocates its query budget to the top b informative labels in the entire online stream based on its own query criterion. CAMS still ourperform the baselines under the setting.
Improvement over the best classifier and policy. Fig. 3h demonstrates that when provided with good policies, CAMS formulates a stronger policy which incurs no regret. CAMS has the potential to outperform an oracle, especially in rounds where the oracle does not make the optimal recom- mendation. For instance, in the stochastic version of CAMS (as shown in lines 22-23 and 30-32 of Fig. 1). CAMS recommends a model using a weighted majority vote among all policies, enabling the formation of new policy in each round by amalgamating the strengths of each sub-optimal policy. This adaptive strategy can potentially outperform any single policy. Moreover, in most real- wooldd scenarios and conducted experiments (as depicted in App. G.6), data streams may not be strictly stochastic, and therefore no single policy consistently performs the best. In such cases, CAMS's 's weighted policy may find an enhanced combination of "advices", leading to improved performance.
7 Conclusion
We introduced CAMS, an online contextual active model selection framework based on a novel model selection and active query strategy. The algorithm was motivated by many real-world use cases that need to make decision by taking both contextual information and the cost into consideration. We have demonstrated CAMS's compelling performance of using the minimum query cost to learn the optimal contextual model selection policy on several diverse online model selection tasks. In addition to the promising empirical performance, we also provided rigorous theoretical guarantees on the regret and query complexity for both stochastic and adversarial settings. We hope our work can inspire future works to handle more complex real-world model selection tasks (e.g. beyond classification or non- con-uniform loss functions, etc. where our analysis does not readily apply).

---

Acknowledgements
This work is supported in part by the RadBio-AI project (DE-AC02-06CH111377 U.S. Depart- ment of Energy Office of Science, Office of Biological and Environment Research, the IMPROVE DE-AC02-06- 4-742244442 DE-ACC05-00222225) the Laboratory Directed Research and Development (LDRD) funding from Argonne National Laboratory provided by the Director, Office of Science, of the U.S. Department of Energy under Contract No. DE-ACO2-0CCHI, 1357, the Exascale Computing Project (17-SC-20-SC), collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration, the University of Chicago Joint Task Force Initiative, the Al-Assisted Hybrid Renewable Energy, Nutrient, and Water Recovery project (DOE DE-EE0009505), and the National Science Foundation under Grant No. IIS 2313131 and IIS 2332475.
project under contract (75N91019F001 75N91019D00024, 8923321
CH11357,
References
[1] Mahmoud Khaled Abd-Ellah, Ali Ismail Awad, Ashraf AM Khalaf, and Hesham FA Hamed. Two-phase multi-model automatic brain tumour diagnosis system from magnetic resonance images using convolutional neural networks. EURASIP Journal on Image and Video Processing, 201 2018(1):1-10, 2018.
[2] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.088. 08774, 2023.
[3] Ravi Aggarwal, Viknesh Sounderajah, Guy Martin, Daniel SW Ting, Alan Karthikesalingam. Dominic King, Hutan Ashrafian, and Ara Darzi. Diagnostic accuracy of deep learning in medical imaging: systematic review and meta-analysis. NPJ digital medicine, 4(1):65, 2021.
[4] Alnur Ali, Rich Caruana, and Ashish Kapoor. Active learning with model selection. In Proceedings of the AAAI conference on artificial intelligence, volume 28, 2014.
[5] Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
[6] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[7] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-777 77, 2002.
[8] Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of the 26th annual international conference on machine learning, pages 49-56, 2009.
[9] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proccedings, 2011.
[10] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33: 13:1877-1901, 2020.
[12] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1::1-122, 2012.
[13] Giuseppe Burtini, Jason Loeppky, and Ramon Lawrence. A survey of online experiment design with the stochastic multi-armin bandit. arXiv preprint arXiv:1510.00757 2015.
[14] Nicolo Resa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[15] Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred Warmuth, How use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
10

---

[16]
Nicolo Cesa-Biance Gábor Lugosi, and Gilles Stoltz. Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51(6): 2162, 2005.
[17] Austin Clyde, Xucfeng Liu, Thomas Brettin, Hyunseung Yoo, Alexander Partin, Yadu Babuji, Ben Blaiszik, Jamaludin Mohd-Yusof, Andre Merzky, Matteo Turilli, et al. Ai-accelerated protein-ligand docking for sars-cov-2 is 100-fold faster with no significant change in detection. Scientific Reports, 13(1):2105, 2023.
[18] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3): 273-297, 1995.
[19] Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions information theory, 13(1):21-27, 1967.
[20] Jan Salomon Cramer. The origins of logistic regression. 2002.
[21] Ashok Cutkosky, Christoph Dann, Abhimanyu Das, Claudio Gentile, Aldo Pacchiano, and Manish Purohit. Dynamic balancing for model selection in bandits and rl. In International Conference Machine Learning, pages 2276-2285 PMLR, 2021.
[22] Ido Dagan and Sean P Engelson. Committee- based sampling for training probabilistic classifiers. In Machine Learning Proceedings 1995, pages 150-157. Elsevier, 1995.
[23] Jiao Du, Weisheng Li, Ke Lu, and Bin Xiao. An overview of multi-modal medical image fusion. Neurocomputing, 215:3-20, 2016.
[24] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:///://r
ics. uci edu/ml.
[25] Joseph I. Durant, Burton A Leland, Douglas R Henry, and James G Nourse. Reoptimization of mdl keys for use in drug discovery. Journal of chemical information and computer sciences, 42
(6):1273-2280, 2002.
[26] Ronald Fisher. The statistical utilization of multiple measurements. Annals of eugenics, 8(4): 376-386, 1938.
[27] Yoav Freund and Robert Schapire. A deciisonn-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):1 19-1119199999 139, 1997.
[28] Yoav Freund, Robert Schapire, and Naoki Abe. A short introduction boosting. Journal- Japanese Society For Artificial Intelligence, (11771-780):11)) 1999.
[29] Jacob R Gardner, Gustavo Malkomes, Roman Garnett, Kilian Q Weinberger, Dennis Barbour, and John P Cunningham. Bayesian active model selection with an application automated audiometry. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 2, pages 2386-2394, 2015.
[30] Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3-42, 2006.
[31] David Hand and Keming Yu. Idiot's bayes-not so stupid after all? International statistical review, 69(3):385-33) 398, 2001.
[32] Katja Hansen, Franziska Biegler, Raghunathan Ramakrishnan, Wiktor Pronobis, O Anatole Von Lilienfeld, Claus-Robert Muller, and Alexandre Tkatchenko. Machine learning predictions of molecular properties: Accurate many-body potentials and nonlocality in chemical space. The journal of physical chemistry letters, 6 6(12):2326-2) 22332333333331222222 2015.
[33] Elad Hazan. Introduction to online convex optimization. arXiv preprint 2019.
[34] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[35] Shen-Shyang Ho and Harry Wechsler. Query by transduction. JEEE transactions on patlern analysis and machine intelligence, 30(9):1557-1571 2008.
[36] Steven CH Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: comprehensive survey, Neurocomputing, 459:249-2888 2021.

---

[37] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint 17Xv::/74..4861,, 2017.
[38] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEKE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
[39] Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlaš, Johannes Rausch, Ce Zhang, and Andreas Krause. Online active model selection for pre-trained classifiers. In International Conference on Artificial Intelligence and Statistics, pages 307-315. PMLR, 2021.
[40] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609.022000000 2016.
[41] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[42] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020,
[43] Rui Leite and Pavel Brazdil. Active testing strategy to predict the best classification algorithm via sampling and metalearning. In ECAI, pages (09-314,7 2010.
[44] Weizhi Li, Gautam Dasarathy, Karthikeyan Natesan Ramamurthy, and Visar Berisha. Finding the homology of decision boundaries with active learning. Advances in Neural Information Processing Systems, 33:8355-8365, 2020.
[45] Nick Liutlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2)2122261,, 1994.
[46] Ying-tao Liu, Yi Li, Zi-fu Huang, Zhi-jian Xu, Zhuo Yang. Zhu-xi Chen, Kai-xian Chen, Ji-ye Shi, and Wei-liang Zhu. Multi-algorithm and multi-model based drug target prediction and web server. Acta Pharmacologica Sinica, 35(3):419-43) 2014.
[47] Chen Change Loy, Timothy M Hospedales, Tao Xiang, and Shaogang Gong. Stream-based joint expploaaaiioneeeellotaaooon active learning. In 20/2 IEEE Conference on Computer Vision and Pattern Recognition, pages 1560-1567. IEEE, 2012.
[48] Mi Luo, Fei Chen, Pengxiang Cheng, Zhenhua Dong, Xiuqiang He, Jiashi Feng, and Zhenguo Li. Metaselector: Meta-learning for recommendation with user-level adaptive model selection. In Proceedings of The Web Conference 2020, pages 2507-2513, 2020.
[49] Omid Madani, Daniel Lizotte, and Russell Greiner. Active model selection. arXiv preprint arXiv:1207.4133: 2012.
[50] Jaouad Mourtada and Stéphane Gaïffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
[51] Mohamad T Musavi, Wahid Ahmed, Khue Hiang Chan, Kathleen B Faris, and Donald M Hummels. On the training of radial basis function classifiers. Neural nenworks, 5(4):595-603, 1992.
[52] Gergely Neu. Explore no more: Improved probbbbiyyyi regret bounds for non-stochastic bandits. arXiv preprint arXiv:
2015.
[53] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744, 2022.
[54] Nikunj C Oza and Stuart J Russell. Online bagging and boosting. In International Workshop on Artificial Intelligence and Statistics, pages 229-236. PMLR, 2001.
[55] J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81-106, 1986.
[56] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning. pages 63-71. Springer, 2003.
[57] Ryan M Rifkin and Ross A Lippert. Notes on regularized least squares. 2007.
[58] David Rogers and Mathew Hahn. Extended-coonectivvn fingerprints. Journal of chemical information and modeling, 50(5):742-754, 2010.
12

---

[59] Marlesson RO Santana, Luckeciano C Melo, Fernando HF Camargo, Bruno Brandão, Anderson Soares, Renan M Oliveira, and Sandor Cactano. Contextual meta-bandit for recommender systems selection. In Fourteenth ACM Conference on Recommender Systems, pages 444 449, 2020.
[60]
Christoph Sawade, Niels Landwehr, Steffen Bickel, and Tobias Scheffer. Active risk estimation. In ICML, 2010.
[61] Christoph Sawade, Niels Landwehr, and Tobias Scheffer. Active comparison of prediction models. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[62] Nick Schneider, Florian Piewak, Christoph Stiller, and Uwe Franke. Regnet: Multimodal sensor registration using deep neural networks. In 2017 IEEE intelligent vehicles symposium (IV), pages 1803-1810. IEEE, 2017.
[63] Yevgeny Seldin and Gābor Lugosi. A lower bound for multi-armed bandits with expert advice. In 13th European Workshop on Reinforcement Learning (EWRL), 2016.
[64] Burr Settles. Active learning literature survey. 2009.
[65] Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In Pro- ceedings of the fifth annual workshop on Computational learning theory, pages 287-294, 1992.
[66] Naman Shukla, Arinbjöm Kolbeinsson, Lavanya Marla, and Kartik Yellepeddi. Adaptive model selection framework: An application to airline pricing. arXiv preprint arXiv:1905.08874, 2019,
[67] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 2014.
[68] Masashi Sugiyama and Neil Rubens. A batch ensemble approach to active learning with model selection. Neural Networks, 21 2008.
[69] Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1 1-9, 2015.
[70] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pages 6105-6114 14. PMLR, 2019.
[71] Stéphanie Van Der Pas and Peter Grünwald. Almost the best of three worlds: Risk, consistency and optional stopping for the switch criterion in nested model selection. Statistica Sinica, pages 229 253, 2018.
[72] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17:X:v:7110.10000 10903, 2017.
[73] Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta. Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actuators B: Chemical, 166:320-329, 2012.
[74] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9():5133-530 2018.
[75] Zhaoping Xiong, Dingyan Wang, Xiaohong Liu, Feisheng Zhong, Xiaozhe Wan, Xutong Li, Zhaojun Li, Xiaomin Luo, Kaixian Chen, Hualiang Jiang, et al. Pushing the boundaries of molecular representation for drug discovery with the graph attention mechanism. Journal of medicinal chemistry, 63(16)8779-8760 2019.
[76] Chicheng Zhang and Kamalika Chaudhuri. Beyond disagreement based agnostic active learning. Advances in Neural Information Processing Systems, 27:442-45 4500 2014.
13

---

A Impact Statements
This paper introduces novel framework for adaptive model selection in label-efficient learning. By integrating robust online learning with active query strategies, algorithm effectively adapts to varying data contexts and minimizes labeling efforts, crucial in domains requiring swift and accurate decisions, such as disease identification and financial predictions. Ethically, the framework's design promotes efficient and context-awart model selection, reducing potential biases associated with context-ignorant model selections. No major ethical concerns anticipated, given the algorithm's generality and focus on solving practical problems.
B
Table of Notations Defined in the Main Paper
notation
meaning
Problem Statement
X
ingut demain
inpur
5 T
index round, total number rounds
index of policies, modelslclassifiers
number of policies
E
number of classitions
3
{0..... set possible class labels each input instance
number
labels. 3/
A A--1
k-dimensional probability simplex (w
1,,
single pre-trained classiffer (model)
UI.... Juh. act of pre-trained classifiers over x.
1 probability selecting classifier inpuix A denetes the canonical busis vector with ey 1 collectionn model selection policies
selection policy (expert)
araan()) (+) =
TT (> ....nn""" " extended policy act including coustant policies that always suggost fixed model
11" (n (n)
policy
I (x.). predicted label for in pre-trained classifier at round è lahel of
Bel Bra " predicted labels by all & models at round
Aou. 0-1 loss for model j = [b] round
f
Ay. loss vector upon observing St the leamer
A
LA
EL &ai.s cumulative loss over I' rounds for a learning algorithm .4 (v. (Kz) (i), expected loss kaunerr commits to policy a, and take random selection round jay ex index of maximal value entry of
maxind((e)
+ ET Ex.gi (1
R. (.4). (.4)
expected regret adversarial setting. pscudo-regret for stochastic setting
E Fil.
91.... E
Algorithm
9.
(grahejun probability distribution
FT"=1 cumalative loss of policy
Aeeejur (t,,,((,) distribution induced by weighted policy the label
(w. n)), expected
((...w))
model disagreement function
log
46
1.
lower bound of query probubility
max (4), @ (G., Me]) adaptive query probahility
U
query indicatoe
adaptive learning
max-ejt-111 (W.. (F, s+}) query budget
(R..) vEle)
unbiased estimate of classifier loss
2.
(Z..) vetel
unbiased estimate of policy loss vector
unbiased cumulative loss of classifions, policics
Analysis
Pr.y
ESeR [fi, y) uy total prohahility classifiers predicts label y
minger A; minges- (J4 Pe sub-ontimality gup
7
mine, (mas,, cvl. my mat (fmointie) myy sub-optimslity model probability gap of EfR, E. upimalii gap immediate regret palicy
the cumolative loss oracle at round
Table 2: Notations used in the main paper
14

---

C
Summary of Regret and Query Complexity Bounds
We summarize the regret and query complexity bounds (if applicable) of related algorithms in Table 3.
Algorithm
Regret
Query Complexity
Exp3
2/Thlog
[42]
Expd.p
6.15//7'ogg
[12]
Exp4
V27 log
[42]
Exp4.p
6. 1./TTay Iu
[9]
Model Pickerysctaniic
[39]
A minsetMe 13/0)
62 max; A (X k)
V27 +-4
Model Pickeradvensaial
2 log
TyTlog K+ 2Lr,,
[39]
CAMS SOOHASTIC
in 1i / p1 in
Tpp
In
Vin itI
Viu [II la
CAMS
20y In m/mx//prr 1/T)
log [II
o
Tlog TT
Lyy
(la
Table 3: Regret and query complexity bounds. For the notations in this table: i is the model with the highest expected accuracy; 02 = IP [e.,, + c..-] is the probability that exactly one of and i" correctly classifies a sample; and pT are defined in Eq. (5) and (6), respectively. = Pmin loge (1/Pmin), where Pmin ming, (xx,) denotes the minimal model selection probability by any policy.
Remark When Tip- LTp are regarded as constants (given by an oracle), the query- complextyyyy bound is then sub-linear w.r.f. T.
Remark 6. Note that the number of class labels e affects the quality of the query complexity bound. The intuition behind this result is, with larger number of classes, each query may carry more information upon observation. For instance, in an extreme case where only one expert always recommends the best model and others gives random recommendations of models (and predicts random labels), having more classes lowers the chance of model making the correct guess, and therefore helps to "filter out" those suboptimal experts in fewer rounds-hend being more query efficient.
Remark 7. To prove the practical feasibility of CAMS, we have analyzed its time and space complexity. Our analysis shows that CAMS has time complexity O (Tnk) in total O(nk) per round (due to the RECOMMEND procedure under the stochastic setting), and space complexity of O ((n + k) k). Here, refers to the online horizon, n denotes the number of policies, and & denotes the number of models. Taking into account these complexities, we can confirm that CAMS is practically feasible.
D Supplemental Materials on Experimental Setup
D.1
Baselines
Model Picker (MP) Model Picker [39] is a context-free online active model selection method inspired by EXP3. Model Picker aims to find the best classifier in hindsight while making small number of queries. For query strategy, it uses a variance-based active learning sampling method select the most informative label to query to differentiate a pool of models, where the variance is defined as v (.) max L (1 ( e.) The coin-flip query probability is defined as max {v (p,, w:), 17. when v (f,, w.) * 0, or 0 otherwise. For model recommendation, it uses an exponential weight algorithm to recommend the model with minimal exponential cumulative loss based on the past queried labels at each round.
Query by Committee (QBC) For query strategy, we have adapted the method of [22] as disagreement-basee selective sampling query strategy for online streaming data. We treat each classifier committee member and compute the query probability by measuring disagreement between models for each instance. The query function is coin-flip by vote entropy probability
(k. E. V(c.x) log Vic.z) where V (c, z)) stands for the number of committee members assigning a class for input context and k is the number of committee. For the model recommen- dation part, we use the method of Follow-the -te--heedee (FTL.) [42], which greedily recommends the model with the minimum cumulative loss for past queried instances.
15

---

Importance Weighted Active Learning (IWAL) We have implemented [8] as the IWAL baseline. For the query strategy part, IWAL computes an adaptive rejection threshold for each instance and assigns an importance weight to each classifier in the hypothesis space Hz- IWAL retains the classifiers in the hypothesis space according to their weighted error versus the current best classifier's weighted error at round t. The query probability is calculated based on labeling disagreements of surviving classifiers through function ma (4)) ela) For model recommendation, we also adopt the Follow-the-Leade thadee (FTL) strategy.
Random Query Strategy (RS) The RS method queries the label of incoming instances by the b. coin-flip fixed probability 7. It also uses the FTL strategy based on queried instances for model recommendation.
Contextual Query by Committee (CQBC) We have created contextual variant of QBC termed CQBC, which has the same entropy query strategy as the original QBC. For model recommendation, combine two model selection strategies. The first strategy calculates the cumulative reward of each classifier based on past queries and normalizes it as probability simplex vector. We also adopt Exp4's recommending vector to contextual information. Finally, compute the element-wise product of the two vectors and normalize it to be CQBC's model recommendation vector. At each round, CQBC would recommend the top model based on the classifiers' historical performance on queried instances and the online advice matrix for streaming data.
Contextual Importance Weighted Active Learning (CIWAL) We have created a variant version weighted active learning. Similar to CQBC, CIWAL adopts the query strategy from IWAL and converts the model selection strategy be contextual. For model selection, Exp4's 's arm recommendation strategy based on the side-information advice matrix and each classifier's historical performance according to queried instances. We compute the element-wise product of the two vectors as the model selection vector of CTWAL and normalize it as a weighted vector. Finally, CIWAL recommends the classifier with the highest weight.
of importance- aupoorance-weighteedde
incorporate
Oracle: Among all the given policies, oracle represents the best single policy that achieves the minimum cumulative loss, and has the same query strategy as CAMS.
D.2 Details policies and classifiers
We constructed different expert-model configurations to reflect the cases in real-world applications This section lists the collection policies and models used in our experiments.
We have constructed 80 diversified classifiers based on VGG [67], ResNet [34], DenseNet [38], GoogLeNet [69]. We have also used EfficientNet [70], MobileNets [37], RegNet [62], and ResNet to construct 85 diversified policies.
CIFAR10:
We have constructed ten classifiers using Decision Tree [55]. SVM [18], AdaBoost [28], Logistic Regression [20], KNN [19] models. We have also created 8 diversified policies with multilayer perceptron (MLP) models of different layer configurations: (128, 30, 10); (128, 60, 30, 10); (128, 120, 30, 10); (128, 240, 120, 30, 10).
DRIFT:
We have built six classifiers using Random Forest [10], Gaussian Process [56], linear discriminant analysis [26], Naive Bayes [31] algorithms. We have constructed policies by using standard scikit-lean built-in models including Random Forest Classifier, Extra Trees Classifier [30], Decision Tree Classifier, Radius Neighbors Classifier [51], Ridge Classifier [57] and K-Nearest- Neighbor classifiers.
VERTEBRAL:
"To list a few other scenarios beyond the ones used in the paper: In healthcare, models could be the treatments, experts could be the doctors and the context could be the condition of a patient. For any patient (context), doctors (experts) will have their own advice on the treatment (model) recommendation for this patient based on their past experience. In the finance domain, models could be trading strategies, experts could be portfolio managers, and the context could be the stock/equity. Some trading strategies (models) might work well technology sector, and some other models might work well for the energy sector, so depending on the sector of stock (context), different portfolio managers (experts) might have their own advice on different trading strategies (models) based their past trading experience.
information
16

---

HIV:
We have used graph convolutional networks (GCN) [40], Graph Attention Networks (GAT) [72], AttentiveFP [75], and Random Forest to construct 4 classifiers. We have also used various feature representations of molecules such as MACCS key [25], ECFP2, ECFP4, and HCFP6 [58] molecular fingerprints to build MLP-hased policies, respectively.
We have built 6 classifiers using Random Forest, Gaussian Process, linear discriminant analysis, Naive Bayes algorithms. We have constructed 17 policies by using standard scikit-learn built-in models including Random Forest Classifier, Extra Trees Classifier, Decision Tree Classifier, Radius Neighbors Classifier, Ridge Classifier and K-Nearest-Neighhor classifiers.
CovType:
D.3 Implementation details
We build our evaluation pipeline on top of prior work [39] around the four benchmark datasets. Specifically.
Context x; is the raw context of the data (e.g., the 32x32 image for CIFARIOO 10).
Predictions ý; contain the predicted label vector of all the classifiers' predictions according to the online context Zt-
Oracle contains the true label y xf.
Advice matrix contains all policies' probability distribution X over all the classifiers on context It.
To adapt to an online setting, we sequentially draw random T' i..dd instances x1T from the test pool and define as realization. For fair comparison, all algorithms receive data instances in the same order within the same realization.
Algorithm 1 Regularized policy के (x,)
1: Input: context xx, Models F, policy II"
2: 1) 2==1 (1 (x=)), 1
3: return ((()))+ 1+
D.4 Regularized policy
As discussed adversarial section, we wish ensure that the probability policy selecting any model is bounded away from 0 so that the regret bound in Theorem 3 is non vacuous. In our experiments, we achieve this goal by applying a regularized policy as shown in Algorithm 1.
D.5
Summary of datasets and models
We summarize the attributes of datasets, the models, and the model selection policies as follows.
dataset
classification
total instances
test set
stream size
classifier
policy
CIFAR10
10
60000
10000
10000
80
85
DRIFT
13910
3060
3000
10
VERTEBRAL
310
127
80
6
17
HIV
40000
4113
4000
4
20
CovType
55
580000
100000
100000
6
17
Table 4: Attributes of benchmark datasets
D.6 Hyperparameters
We performed our experiments on a Linux server with 80 Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz and total 528 Gigabyte memory.
By considering the resource of server, We 100 realizations and 3000 stream-size for DRIFT, 20 realizations and 10000 stream-size for CIFARIO. 10, 200 realizations and 4000 stream size for HIV.
17

---

300 realization and 80 stream-size for VERTEBRAL. In each realization, we randomly selected stream-size aligned data from testing-set and make it as online streaming data which the input of each algorithm. Thus, we got independent result for each realization.
A small realization number would increase the variance of the results due the randomness of stream order. A large realization number would make the result be more stable but at the cost of increasing computational cost (time, memory, etc.). We chose the realization number by balancing both aspects.
E Proofs for the Stochastic Setting
In this section, we focus on the stochastic setting. We first prove the regret bound presented in Theorem and then prove the query complexity presented in Theorem 2 for Algorithm 1.
E.1 Proof of Theorem
Before providing the proof of Theorem 1, first introduce the following lemma.
Lemma 8. Fix T E (0, 1). Let qt,i- be the probability of the optimal policy i' maintained by Algorithm at and let b Pmin loge (1/Pmin), where Puain ming, π (xx)) denotes the minimal
(1n*) 11r
model selection probability by any policy'. When 2
with probability
Vl 111
A
252
least 8, it holds that qt 2
Proof of Lemma 8. W.l.o.g, we assume p1 S #2 S
.n.
Recall that we define A
- and is the policy with the minimal expected loss.
mingze A U22 11
Define
2 1,-1,
where /' e arg min L, denotes the index of the best empirical policy up other than Therefore for i 2 2, it holds that
L--1-- - L1-1,
6, S 0.
s=1
exp( Mble 1.1)
We have qr
qt,1
!1' exp( (ele-11.)
the weight optimal expert at round
Therefore
exp
- -
4t.1
|II+
-Te -TitTa-1,))
i=1 cxp
exp
(-mpIe-1,1 + me mele--1)))
(a)
Σ
i=1 exp
III
(-mpter- 11e Te-be-111
exp 176 Σi=1 8,)
(6)
1/1 Eو= 5.) + 2i=2 |11-1
exp -1pTia
+ n t (1
exp
exp
n1 E'= 8,)
exp Et= 8,) + |II+1-1
(8)
where step (a) is by dividing the cumulative loss of sub-optimal policy my and step (b) is by the definition of 6, in Equation (7).
We assume Puain > 0 per the policy regularization criterion in Appendix C.3. (cf. Algorithm on "Regularized policy * (xx.))"
18

---

exp("t Ei= 6,)
V [--
Let E (0, 1), such that o, 2
exp(n Disi -1111111-1 2
Plugging in ?
and define
5, = Ex= dg. we get
exp [1 vt.)))
27
exp (Inlllliv Vt 6z)
1111
Therefore, obtain exp (Vln [111 Sitliitoj. σ.)
----- 1-T
Rearranging the terms, we get
In [|I - Ur In II
t t2
Next, we seek a high probability upper bound on ög. Denote A - pr - for E I...., [I1*) We know
( P(.. -2 P(oe S Dr c) P( 82
(b)
Do S E) Se
Here, step (9a) is by the fact that 2 minize 1 A; S Ar, and step (9b) is by Hoeffding' inequality where denotes the upper bound on 15.]. Further note that
U (x,) T: (x.)),, # yal)
8s+1 = Lav 1,,1
(Tr (x,) ), 10, v333)
2s
Eq.(4) (4)
(Tr (X.) ) 1$ + vo3)
U EveD (W,, 1l (6, F 4}) loge (m.. サw))
Given Pmin
ming,r (xx), we obtain 8p+1 Pruin log, (1/ pmonn) and similarly, ds+1 2
We hence conclude that 16, < b.
Pari (1/Peii
122 Let 2e 252 = 5. Therefore, when / 2
In [-1"
1-r
it holds
/n ((A
/nn |T-|
A
26 In
that or.r 2 r with probability at least 1
Lemma 9. At round 6, when > In
In III" 26
it holds that the arm chosen by the best policy it will be the arm chosen by Algorithu with probability at least 1 6. That is, EieliTe (xx))(())) arg max { (x))).
Vin [IITA
arg max
Proof of Lemma 9. At round Σ/= 11 arg max EEegprnn icy in's top weight arm jr,s'' probability max (Nzz (xx)) is at least 1. The second rank probability of nH- (xx) is max, [m;-- (mo)iii (xe))- Let us define
for Algorithm 1. leg. Let -1,t
have loss
At round t, the best pol-
7 min
max Wy myeW
max
Wj
(10)
wy Ewg. J (w
max (ग. (xx) max [ ( (rx))
19

---

as the minimal gap in model distribution space of best policy. The arm recommended by the best policy of CAMS will dominate CAMS's selection, when we have
41,5 max (xx)) 2 (1 (6,5-)) ) + 91,5- max (T-- (x (mx))l)maxind(s
(1I)
Rearranging the terms, and by
9 Fq. (10)
max ( (xx)] - max (T.. (xx) smnnlllnas (xx))) ) 2 -0,i))
qr,i*
Therefore, we get T. (7) (1 -1)- and thus 2 7+I
Set r 2 + By Lemma 8, we get
In
[TT -T--1/F
2
12
In
II-
(A
c)
[11
2
In
In
III (A c)
In |11-11
W
In IT A
In |IT
26a In
where the last step is by applying 2e
202
5, thus,
262 In V
Dividing both sides by
|
(4)
In II+ tA
In II+
26 In
1
In (IIT*)
2 5
In
vi
In (|
212 In
7
In
|1|
+
In [T||| 26 In
t z
In I
So, when [B Ia |11-|:266 1:26 In o
2
it holds that arg max (e
In |1
arg max (Te- (xx)).
Proof of Theorem 1. Therefore, with probability at least we get constant regret In |n In |16 In
In 11 A
Furthermore, with probability most d, the regret is upper bounded by T. Thus, we have
2
In |||-1 In |11 26t In
R (T)
(1
8)
+ 8T
In II A
T )
1
[n ||'-1 by
In IT (2 21
+1 1
In II
In ب
blnT
=
+
2
/
/
20

---

where step (a) by setting T and where y in Eq. (10) is the min gap.
E.2 Proof of Theorem 2
In this section, we analyze the query complexity of CAMS in the stochastic setting, where we take similar approach proposed by Karimi et al. [39] for the context-free model selection problem. Our main idea is to derive from query indicator Uz and query probability 2t- We first used Lemma 10 to bound the expected number of queries Σt=1 U, by the sum of query probability as Ex 0g + E é (f.: wt). Then used Lemma 11 bound the first item (which corresponds the lower bound of query probability over I'' rounds) and applied Lemma 12 to bound the second term (which characterizes the model disagreement). Finally, we combined the upper bounds on the two parts to reach the desired result.
Lemma 10. The query complexity of Algorithm I is upper bounded by
EvEr (we, l() log (we.e))
E
Σ
1
(12)
[
Proof. Now have model disagreement defined in Eq. (3), the query probability defined in Eq. (4), and the query indicator U. Let us assume, at each round, we have query probability 2; > 0, which indicates will not process the instance that all the models' prediction are the same.
At round from query probability Eq. (4), we have
2, max {6) w)),
<6 (p. We).
where the inequality by applying that AA, B 0, max (, B) A B. Thus, in total round T, we could get the following equation as the cumulative query cost,
Evey (we, Cr logiy [we.epi
E
Σ U
<
(13)
VE
Y
where the inequality is by inputting % Vi
1 and Eq. (3).
Lemma 11. Et v7 < 2VT.
Proof. We can bound the LHS as follows:
T Σ
Σ Vi
1=1
t=[vT]+1
S VT
Σ
+=|+T|+
-V (T-
J
2VV..
Lemma 12. Denote the true label at round by Uts and define pt, == Ejelo 1l (ur. = y) Wg.
Further define Rs == E, Pt.m as the expected cunulative loss of Algorithm I at t. Then
I Ever e") logiyi (w.ee7 S
RI
(108))
(111111)
17
|/]
|
21

---

Proof of Lemma 12. Suppose at round t. the true label is vt. Σ Pt.y = 1 Pt.ge 1
(Eeeny (T, rt.
Epey(we, logis (welet)
(1 Pt.ye loBiyl T-P
+ Evtur (1 - Pt.y)
log I-Pt.8
|2/|
|
(1 Pr.m log I-Pr.
(1-Pt.ve) 131-1
log
31-1
+ +(D) -
I-
[
|
Pt.ze logio/
(1 Pt.ye logiy/ 1-Pe.se
D-111
1-Pt.at
(1
pt,ee logiy/
21-1
(1-pa,0t)
(b) rr log
D
"
D
where step (a) by applying Jensen's 's inequality and using 1 Pr.y
1-Pra and step (b) is by 1y--1
replacing the expected loss 1 Pt.y by its short-hand notation Tt-
Recall that we define the expected cumulative loss as Ry = Σt= rt. Since when ra E [0,1],
r. loR yo 7 is concave, get
31
Evey(Wes ( logiyt (weeer)
T
Σ ri T
log
y/
D1-1 L
Rr
(oog|i T
12,
|
|
[3]]
(14)
Since Rr the cumulative loss up round T, T"s incremental rate no less than Ry's ' incremental T.
rate. Thus, Rr S T and
s
T So we get Eq. (14). R
R.
Now we are ready to prove Theorem 2.
Proof of Theorem 2. From Lemma 10, we get the following equation as the cumulative query cost
T
T
Eyey (w,, (,,,e") (ogg>> e.)
E
U
E
+
D
Let us assume the expected total loss of best policy is T Tu.- From Theorem 1, we get
In
In 11+ 26 In 2
RT
Ft
S
Tpr
In I
Plugging this result into the query complexity bound given by Lemma 11 and Lemma 12, have
22

---

In 111 1-26 In
+ Tp:
In |TI' A
T2 (131-1)
-
E
U2
< 22T
logpyl
D
|
In ||| 1-26 In
2
TTe
In [TT
|1T-| In
(10%,1) (TI)1)
Tw:
In IA
[39]
26 In
Tu-
ln(T)
In IIT
D In D/
+ In II
26 In 3
2
+ Tus (T)
In
IT-|A
clnc
where 7 is defined as Eq. (10) and step (a) by applying = (1)
Proofs for the Adversarial Setting
In this section, we first prove the regret bound presented in Theorem and then prove the query complexity bound presented in Theorem 4 for Algorithm in the adversarial setting. Lemma 13 builds upon the proof of the hedge algorithm [27], but with adaptive learning rate.
F.1 Proof of Theorem 3
Lemma 13. Consider the setting of Algorithm 1, Let define her = exp (-mpLe1aa vi [II*] as exponential cumulative loss of policy i, Th the adaptive learning rate and q, the probability distribution of policies, then
Eier me l1+11.
m1
2
log
Eieginn bis
T1
Le,s
Proof. We first bound the following term
EiElIr 1 Met13
beLLs
Eie(iTon har
Eielinen he,
t exp (-nples)
(Tee) 2
[1'
4t,i
1 1-
2
i=1
T16
Σ
Ee,8 2
+
2
1=1
where the inequality is by applying that for S 0, we have ex 11 2
23

---

By taking log on both side, we get
Exelin-11 Met1l
IT'
11
log
S log
-
T)
Uille
+
Σ
Ex,2
Ei Ne,i
2
i=l
iml
111
I11
(a)
118
gt,
1/2
Σ
qts
(1,b
2
where step (a) is by applying that log (1 +x) xr when 2 -. Now summing over = yields:
Eigl 11-l AT+1,
Ege n-ll Mtiss
log
Σ log
Σielin11 h2
Σ Exelu-n hi,
I11"
1/
111
Σ M1
9t.i
(e,i
i=1
Lemma 14. Consider the setting of Algorithm 1. Let Pt.y = Ejem Kūc. = y) wy. The query
probability 2, satisfies
2x
Ii (pt. P. + Pe, (1 p(,s)), Vy + yt.
Proof. We first bound the query probability term
Σs = max {6/= & (Fes we))
maxfoh
1
Σ
(we, et) logis' ew)
|
1
max
(1 pt,y) In - In |2
D
Pt.y
VEY
(a)
1
max
(1 Pt.y) PEE In | }
|
NEY
1
ma
(1 Pt.s.) Pe.
DI
In D
DEV
[ In y (pr. (1 Pt.ge) pt,y (1 pt.s))) Vy yrs
where step (a) is by applying In (1 + x)) 2 Ltx
for x > 11,
ps.
In (1 1+
Pt,y
1 P-PLv
In
Pt,y
Pt.y
1 - Pi.y
1 -PP..
and where step (b) is by applying Va, b TR, max {a, b) 2 a.
Proof of Theorem 3. By applying Lemma 13, we got
Exeling hT+1, T
m
T
11'
log Eie(mn bis
Σ
m
9t
Ec,i
2
1=1
1=1
im1
24

---

For any policy 8, we have a lower bound
Eie[in-- II
104+1,
hT+1.
log
2 log
Eie(in j hiss
Lie hig
(4)
1T++1.
log
[T|*'
- log (n + -)p
4,50
(15)
where step (a) in Eq. (15) is by initializing Lo = 0, E and Eie[[n-1 hi = c((ndo)) = ||T
Thus, we have
2 2 log (n + k:)
Th
Gr
E
|1T"1
T
|T|"|
T
T
1TT
Er, S log (n + +
2t
2
tm
t=1
i=1
T
T
(b) Ee, S log (n kk)
T
ITT
2
g
1/T
WT
4
2
1m1
i=1
Ge Σ
E
(c) log 111
+
1
Σ
T
Σ
(1,s
2
7/T
Y/T
2
where step (b) is by applying
MT
g WT
Σ
nh
1/T
2
and step (c) is by dividing 1/r on both side.
Because we have
Er
9
(e,s)
27
= Er
(Te (xx)) (xx))-2)²
le
90,6
P(U:= =1)
Tsss (xx)
+P( -001=0)-1
21
Pi 2
gr.
21
Ti (xx)
( (xx) -2)²
21
4t.1
(xx) e,
Hta (IT (xx) C,),
it leads to
25

---

1
log IIo
1
1/1
q1.
( (xx) La)
1/T
2
2t
(d)
log [TT*|
T
1/
(We,
+
7/2'
1T
2
24
t=1
where step (d) is by applying Ei [T4 So have,
(m .e) = (we, Le).
m
T
log
III*
1
T
WE
(We,
Le)
1/T
1/1
2
21
1=1
log [TT*
2
2
Pt.y
T/
1/2
2t
t=1
log I
1
T
412
Pr.ye
T/
1/1
2
Yu ((1 Pt Pt.ve + (1 Pt.u) PL.v)
log III*
T
v
Y/T
1/r 1=1
2
Vo
Pt.y +
1 1-pra P-Pe. Pt,y
where step (e) by using (w,, Pt.ys and step (f) by using Lemma 14 and get lower bound of 2, 1 In D (Pt. (1 Pt.ya) ) Pi,y pt.y)) and applying in Vo.
If Pt.ee 2 D
Pt.y
Pt.e + 1 Pr,te
pt,
2
|>
Pt.y
< 1
By Pt,y
+ 1, 8f maxy, Pr.y-
Let Pt.g
max, Pt.y Thus, we have
wg DDT
and
1 PL.M Pr.m
8 Pt.ve
1 8
57 |>]]
Pt.t.
PLy 2 Pt.y. + wg
2 0
|
Therefore
1 Pt.y
if Pt.. 2 17
max(pr.y + PL.v Pt.y+
if Pt.s
[
DT
26

---

So we have
T mT
log [11*
2
ΣΣ Ual
l,,
==1
mm
1/T
1/
1m1
2
Vo
1-pr,ve pl.y
1-wy
(g) log [TT*
1
T
71
1
V/
2
max ( 139- %)
[=1
log [11*]
7E
|>/2 (
1/7
max 07 6/ In DJ
(h)
log [Io
1 In |
1/T
1/T
2
1=1
log
[II*
1D/ In (31/
1h
1/r
8
+
56
1/1 In |
1=1
where step (g) is by getting the lower bound of 24 as applying max B} 2
4 1
88
S
oi and step (h) is by
D
1-
A+B
2
Let us define Pr - min 87 =1
maxx,reld pl.y
We get
log IIo
1
1
2 log
[I*
E7 RTl
log IIo
TJT
1T
T
f
Let 1)t
Pc P DJ
log |II
we obtain
2 2 111 VT Vp In D
ET [T]
PP + 5f 2 In D
Th [V]] log IT-
< <2D')
max(pr, VI/T}
where the last inequality is due to the fact that
Pr + 12 In D' > max 6% max(pr, vI/T)
which completes the proof.
F.2
Proof of Theorem
Proof of Theorem 4.
From Lemma 10, we get the following equation as the cumulative query cost
1 VE
Enev et)
logi>ı (werep)
E
U
<
E
[D]]
Let us assume the expected total loss of best policy is LT,.. Thus, from Theorem 3, we get the expected cumulative loss
Thn y log [IT*| max(pr, v1/T)
[TT]
E
Tt
< 211
+ LT...
27

---

Now plugging the regret bound Rr proved in Theorem 3 into the query complexity bound given by Lemma 12, we have
2/2%
Thn log ITT moxx(pr.////)
+ LT.,)
1088511
7 11
T E (we, e log (m.ee
Th (V] _n by.
was (or (pr.v' vI7T)
[3]
2
Tin ( log III
+ Esp,,
(108)>) T(D1)
max (pr, v 1/T3
[3']
Thn ( log ITT*| 2/2%
Er,,, ) (105)D1) T T+
max(pr. (1/T/
[D]
Finally, by applying query complexity upper bound of Lemma 11, we got
2
Thn 1 log ITT
ToT..)
(108/1) T+11
maxipr masipr..Vin v1/33
E
Σ Up
<2VT
[
Since the second term on the RHS dominates the upper bound, we have
max (PT-IT)// VITT) + LI.,) (In
Tlog [1-1
T
1)
( 00
(( VI/T) + LI,, (nrr)
T
Tlog [TT*1
E
Σ
Up
((n1))))
where step (a) is obtained by suppressing constant coefficients involving | into the notation.
28

---

G Additional Experiments
In this section, we further evaluate CAMS and provide additional experimental results (complemen- lary to the main results presented in Fig. 2) under the following scenarios:
1. In App. G.I, we demonstrate that CAMS outperforms the baselines on large scale dataset as well.
2. In App. G.2, we perform ablation study of three query strategies CAMS (entropy), variance and random strategy. CAMS (Entropy) achieves the minimum cumulative loss for CIFARIO. DRIFT, and VERTEBRAL under the same query cost and outperform the other query strategies.
3. In mixture of experts environment, CAMS converges the best policy and outperforms all others (App. G.3);
4. In non-contextual (no experts) environment, CAMS has approximately equal performance as Model Picker to reach the best classifier effectively (App. G.4);
5. In adversarial environment, CAMS efficiently recover from the adversary and approach the performance of the best classifier (App. G.5);
6. In complete sub-optimal expert environment, variant of the CAMS algorithm, namely CAMS-MAX, which deterministically picks the most probable policy and selects the most probable model, outperforms selects the most probable model (App. G.7 & App. G.8). However, CAMS-MAX at most approaches the performance of the best policy. In contrast, perhaps surprisingly, CAMS is able to outperform the best policy on both VERTEBRAL and HIV (App. G.6).
which randomly samples a policy and
7. In App. G.9, we summarize the maximum query cost under fixed number of realizations with its associated cumulative loss for all baselines (exclude oracle) on all benchmarks in experiment section.
8. In App. 1.10, we compare the query complexity of each baselines and demonstrate that CAMS has the lowest query cost increasing rate on CIFARIO, DRIFT and VERTEBRAL dataset.
9. In previous studies, we assume that the data comes in an online format. In App. G.II, we assume we know the data stream length ahead and applying the scaling parameter to each algorithm to query their top data points from hindsight. CAMS still outperforms all the baselines.
10. In App. G.12, we compare CAMS with AAMS-nonactive. a greedy version (query label for each incoming data point). Although CAMS query much less data, it still performs equally well or even better than the greedy version.
11. In App. G.13, we demonstrates that CAMS can achieve negative RCL on all benchmarks, which means it outperforms any algorithms that chase the best classifier where the horizontal O line represents the performance benchmark of best classifier.
G.1 Performance of CAMS at scale: Experimental results on CovType
We scaled up our experiments on a larger dataset, CovType [24]. The CovType dataset offers details about different types of forest cover in the United States. It contains details including slope, aspect, elevation, measurements of the wilderness area, and the type of forest cover. CovType has 580K samples, of which 100K instances were chosen at random as online stream for testing. Fig. 4 demonstrated that CAMS outperforms all baselines which is consistent with the existing results in experiment section.
G.2
Query strategies ablation comparison
Using the same CAMS model recommendation section, we compare three query strategies: the adaptive model diddell-iaggrement-beee based query strategy in Line 10-14 of Fig. 1 (referred to as entropy in the following), the variance-barr based query strategy from Model Picker [39] (referred as variance), and random query strategy. Fig. 5 shows that CAMS's ' adaptive query strategy has the sharpest converge rate on cumulative loss, which demonstrates the effectiveness of the queried labels. Moreover, entropy achieves the minimum cumulative loss for CIFARIO 10, DRIFT, and VERTEBRAL under the same query cost. For the HIV dataset, there no clear winner between entropy and variance since the mean of their performance lie within the error bar of each other for the most part.
29

---

R5
Gracle QRC
INAL
COBC
OWAL
CAMS
Relutive cumnuaative loss
-290
30493
Number of queries
Cumulaatve loss.
100
-6000
-8000
10890
Round
Round
Query cost
(a) Relative Cumulative Loss
(b) Cost
(c) Cumulative Loss VS Cost
Figure 4: Comparing CAMS with 7 baselines on CovType in terms of relative cumulative loss, query complexity, and cost effectiveness. CAMS outperforms all baselines. (Left) Performance measured by relative cumulative loss (i.e. loss against the best classifier) under a fixed query cost B (where = 1000). (Middle) Number of queries and (Right) Performance of cumulative loss by increasing the query cost, for fixed number of rounds 7 (where 7 = 100, 000) and maximal 5000 ). Algorithms: 4 contextual (Oracle, CQBC, CIWAL, CAMS) J and non-contextual baselines (RS, QBC, IWAL, MP) are included (see Section ). 90% confident interval are indicated in shades.
query cost (where
varlance
random
383
300
203 1083
190
140
Cumsiliive
140
312
104
248
253
100 120
30
181
Query
130
150 16
#1 3 (c) VERTEBRAL
350 500
1008
300 IHE
(a) CIFARIO
(b) DRIFT
(d) HIV
Figure 5: Ablation study of three query strategies (entropy, variance, random) for 4 diverse bench- marks based on the same model recommendation strategy. Under the same query cost constraint, CAMS's 's entropy-basel strategy exceeds the performance of the other two strategies non-binary benchmarks terms query cost and cumulative lost. 90% confident intervals are indicated in shades.
G.3 Comparing CAMS with each individual expert
We evaluate CAMS by comparing it with all the policies available in various benchmarks. The policies in each benchmark are summarized in App. D.2 and Table D.5. The empirical results in Fig, demonstrate that CAMS could efficiently outperform all policies and converge to the performance of the best policy with only slight increase in query cost in all benchmarks. In particular, on the VERTEBRAL and HIV benchmarks. CAMS even outperforms the best policy.
G.4 Comparing CAMS against Model Picker in context-free environment
CAMS outperforms Model Picker in Fig. 2, by leveraging the context information for adaptive model selection. In context-free environment, II {0) ) so II { ..... o 3. where T. g.5mms()) (.) := ej represents a policy that only recommends a fixed model. In this case, selecting the best policy to CAMS equals selecting the best single model. Fig. demonstrates that the mean of CAMS and Model Picker lies the shades of each other, which means CAMS has approximately the performance as model picker considering the randomness all benchmarks.
G.5 Robustness against malicious experts in adversarial environments
When given only malicious and random advice policies, the conventional contextual online learning from experts advice framework will be trapped in the malicious or random advice. In contrast, CAMS could efficiently identify these policies and avoid taking advice from them. Meanwhile, also successfully identifies the best classifier to learn to reach its best performance.
30

---

best policy
top sub-optiima policies
CAMS
100
140
240
160
Cunulaaivv
120
2.00
255
20 VERTEBRAL
Query cost
cost
(a) CIFARIO
(b) DRIFT
(d) HIV
Figure 6: Comparing CAMS with every single policy (only plotted top performance policies in Figure). CAMS could approach the best expert and exceed all others with limited queries. In particular, on VERTEBRAL and HIV Benchmarks, CAMS outperforms the best expert. 90%
confident intervals are indicated shades.
optimal
Grnd
200
250
Cunabltiv loss
100
0.0
1000
615
360
000
200
734
Outry con:
100
Query
Oeayy
(a) CIFAR10
(b) DRIFT
(c) VERTEBRAL
(d) HIV
Figure 7: Comparing the model selection strategy of CAMS and Model Picker baseline based on the same variance- query strategy in a context-free environment. CAMS has approximately the same performance Model Picker on all the benchmarks. 90% confident intervals are indicated in
shades.
The novelty in CAMS that enables this robustness is that we add the constant policies [rfoasst ...... 2 const into the policy II to form the new set II. To illustrate the performance difference, we have created a variant of CAMS by adapting to the conventional approach (named CAMSScconventional) Fig. 8 demonstrates that CAMS could outperform all the malicious and random policies and converge to the performance of the best classifier. CA CAMCcoovnntional: We create the CAMSS-conventioaa algorithm the CAMS using policy set II, not TT".
best classifier
top zub optimal policies
CAMS
CAMS conventional
1000
2351
1:00
1.00
383
1200
X100
Curulaaive
1.00
230
400
240
12
183 De
CIFARIO
(b) DRIFT
(c) VERTEBRAL
(d) HIV
Figure 8: Evaluating the robustness of CAMS compared to the conventional learning from experts' advice C.AMS-conventionall in a complete malicious and random policies environment. When no good policy is available, CAMS could recover from malicious advice and successfully approach the performance the best classifier. In contrast, the conventional approach will be trapped in malicious advice. 90% confident intervals are indicated in shades.
31

---

G.6 Outperformance over the best policy/expert
We also observe that CAMS does stop approaching the best policy classifier performance. Sometimes, it even outperforms all the policies and classifiers, and Fig. 9 demonstrates such a case. To demonstrate the advantage of CAMS, we create two variant versions of CAMS: (1) CAMS-MAX SallS-Rando-PPee use
(App. G.7), (2) CAMS-Random-PP Policy (App. G.8). CAMS-MAX and the same algorithm as CAMS in adversarial settings but have different model selection strategies for ablation study in the stochastic settings.
We evaluate the three algorithms VERTEBRAL and HIV benchmarks in terms of (a) normal policies (Fig. 9 Left), (b) classifiers (Fig. 9 Middle), and (c) malicious and random policies (Fig. Right). In the normal policies column, only compare the policies with regular policies giving helpful advice. In the classifier column, we compare them with the performance of classifiers only. In the malicious and random policies column, we compare them with unreasonable policies only.
Fig. 9 demonstrates that all three algorithms could outperform the malicious/random policies. How- ever, M-SSS--nndm-Poooio Policy does not outperform the best classifier while both CAMS and CAMS- MAX can on both benchmarks. CAMS-MA does not outperform the best policy on both benchmarks. Finally, perhaps surprisingly, CAMS outperforms the best policy (Oracle) on both benchmarks and continues to approach the hypothetical, optimal policy (with 0 cumulative loss).
approaches the performance of the best policy but
This surprising factor contributed by the adaptive weighted policy of CAMS, which adaptively creates a better policy by combining the advantage of each sub-optimal policy and classifier to reach the performance of the hypothetical, optimal policy (defined as E -=1 minie(n +]] la.i). The second reason could be that the benchmark we created, or any real-world cases, will not be strictly in a stochastic setting (in which single policy outperforms all others has lower μ in every round). The weight policy strategy can make a better combination of advice for this case.
best dlassifier
best policy
CAMS MAX
CAMS
tap suboptimal policieycllessffers
Cummuaaivve
25
VERTEBRAL
28
15
18
10
13
13
25
30
15
13
20
38
15 10
20
25
33
130
Curulaaivve
2.00
340
320
330
100
203
200
350
400 Query
530
600
783
030
330
208
430
600
060
1000
3200 3460
10.02
RED 1006 1368 1200
Query cost
Query
(a) normal policies
(b) classifiers
(c) malicious and random policies
Figure 9: Comparing CAMS, CAMS- MAX and SAASS-RANDMM-POLLE with top policies and classifiers in the VERTEBRA and HIV benchmarks. They outperform all the malicious/random policies. Moreover, CAMS and CAMS- even exceeds the best policy (Oracle) in both benchmarks and continues approaching the hypothetical, optimal policy (0 cumulative loss). 90% confident intervals are indicated in shades.
outperform the best classifier. Finally, only CAMS
32

---

G.7 The CAMS-MAX algorithm
CAMS-MAX is variant of CAMS. In adversarial setting, they share the same algorithm. However, in a stochastic setting, CAMS-MAX gets the index i" of max value in the probability distribution of policy q, and selects the model with the max value in Ti- (xx) recommendation. The difference is marked as blue color in Fig. 10.
1: Input: Models F, policies II", #rounds T, budget
2: Initialize loss Lg t- query Co
procedure SETRATI((, if STOCHASTIC then
3: for t 2... do
4: Receive
23:
Inm
Ve SETRATE(L, II
24:
end if
6: Set 9t, exp (TpLi-1a) Wi I
25:
if ADVERSARIAL then
7:
Je + RECOMMEND(X,,
26:
Set Pt as in adversarial section
8:
Output fr.,, ~ ft.,, as the prediction for x;
1/:
Zine
9:
Compute 2 in Eq. (4)
10:
Sample U, Ber (2x)
28:
11:
if U0 = and C S b then
29: return ft
12:
Query the label Nt
30:
procedure
13:
C₁ + Ct-1 +
14:
Compute 4: l,, ((r # Mc) Vj e [[F]]
29:
procedure RECOMMEND(X, q:)
15:
Estimate model loss: las fed Vj E [[]]]]
30:
if STOCHASTIC then
16:
&; 4, - (xe),, (ax)),es))) ( Vi [I]]]]
31:
32:
maxind(q) qq))
maxind (T. (xx))
L, L, 1
33:
end if
else
34: if ADVERSARIAL then
19:
L, 14-1
35:
q:
C: + Cr-1
36:
we, (xx)
21:
end
37:
end if
22:
end for
38:
return
39:
end procedure
Figure 10: The CAMS-MAX Algorithm
G.8 The CAMS--andom-PPllcc algorithm
1: Input: Models F, policies II", Hrounds T. budget
2: Initialize loss Lg +- query Co
21:
procedure SETRATE(L, STOCHASTIC then
3: for 1.2. do
Receive
Ti SETRATE(,, [II*])
23:
1/:
24:
end if
6: Set gt, exp -TpLL-11 Vi Wi [I])
25:
if ADVERSARIAL then
7:
d: + RECOMMEND(X;,C 4t)
26: Set Pt as in adversarial section
8:
Output Bt.5, ~ fej, as the prediction for x,
27:
1/:
VE amn
9:
Compute 2, in Eq. (4)
10:
Sample U, ~ Ber (2.)
28:
11:
if U. = and C, S b then
29: return Vj
12:
Query the lahel
30:
end procedure
13:
Ce + Ct-1+ +
14:
Compute l: b2,) = (Ūrs # ycl h Kj e [[-]]]
29:
procedure RECOMMEND 4:)
15:
Estimate model loss: las fid vi e [[F]]
30:
if STOCHASTIC then
16:
l; tee t- (x.))) C.).V. Vi [IM]]]
31:
4: maxind( (xx))
32:
17:
L. L, +l,
33:
end if
clse
34: if ADVERSARIAL then
19:
L, = L.-1
35:
q: Ni, (x.)
20:
C: + Ct
36:
21:
end
end
22:
end for
return je procedure
Figure 11: The Rando-ocdom Algorithm
AASSSRandom-PPlle is a variant of CAMS. shares the same algorithm with CAMS in an adversarial environment. However, it uses random sampling policy method in stochastic setting.
33

---

It randomly samples the policy from the probability distribution of policy q. and selects the model with max value in πT- (x,) recommendation. The difference marked as blue color in Fig. 11.
G.9 Maximal queries from experiments
Table 6 this section summarizes the maximum query cost for given data stream (of fixed total size), with its associated cumulative loss for all baselines (exclude Oracle) on all benchmarks in experiment section. The result in this table is slightly different from the query complexity curves of Fig. (Middle). The curve in Fig. 2 (Middle) takes the average value, while the table takes the maximal value from fixed number of simulations. CAMS wins over all baselines (other than Oracle) in terms of query cost on CIFARIO, DRIFT, and VERTEBRAL benchmarks. CAMS outperforms all baselines in terms of cumulative loss on DRIFT, VERTEBRAL, and HIV benchmarks. In particular, CAMS outperforms both cumulative loss and query cost on the DRIFT and VERTEBRAL benchmarks.
Algorithm
CIFAR10
DRIFT
VERTEBRAL
HIV
Max queries, Cumulative loss
1200, 10000
2000, 3000
80, 80
2000, 4000
RS
1200, 2916
2000, 766
80, 19
2000, 143
QBC
1200, 2857
1904, 771
72, 20
2000, 139
IWAL
1200, 2854
2000, 760
80, 19
690, 140
MP
1200, 2885
493, 803
33, 25
153, 148
CQBC
1200, 2284
1900, 744
68, 13
2000, 124
CIWAL
1200, 2316
2000, 746
80, 12
690, 124
CAMS
348, 2348
251, 710
32, 11
782, 112
Table 5: Maximal queries from experiments
G.10 Query complexity
To achieve the same level of prediction accuracy (measured by average cumulative loss over fixed number of rounds). CAMS incurs less than 10% of the label cost of the best competing baselines on CIFAR10 10 (10K examples), and 68% the cost VERTEBRAL (see Fig. 12); Fig. 12 and Table 6 also demonstrate the compelling effectiveness of CAMS's query strategy outperforming all baselines in terms of query cost in VERTEBRAL, DRIFT, and CIFAR10 benchmarks, which is consistent with our query complexity bound in Theorem 2.
Cracle
QBC
INAL
Number queries
180
69
2008
100
CIFARIO
DRIFT
VERTEBRAL
(d) HIV
Figure 12: Comparing CAMS with 7 baselines on 4 diverse benchmarks in terms of query complexity
(Number of queries). CAMS outperforms all baselines for fixed number of rounds T (where T 10000, 3000, 80, 4000 from left to right) and maximal query cost B (where B 1200, 2000, 80, 2000 from left right). Algorithms: 4 contextual (Oracle, CQBC, CIWAL, CAMS) and 4 non-contextual baselines (RS, QBC, IWAL, MP) are included (see Section 90% confident interval are indicated in shades.
G.11 Fine-tuning the query probabilities for stochastic streams
For the experimental results reported in the main paper, we consider streaming setting where the data arrives online an arbitrary order and arbitrary length. Therefore, for both CAMS and
*e also consider variants for each algorithm (other than Random and Oracle) where we scale the query probabilities based on the early-phase performance and observe similar behavior. See App. G.11 for the corresponding results.
34

---

the baselines, we used the exact fff-the-shelf query criteria as described in experiment setup section without fine tuning the query probabilities, which could be otherwise desirable in certain scenarios (e.g. for stochastic streams, where the query probability can be further optimized).
In this section, consider such scenarios, and conduct additional set of experiments further demonstrate the performance of CAMS assuming stochastic data streams. Given the stream length T' and query budget b, we may optimize each algorithm by scaling their query probabilities, so that each algorithm allocates its query budget to the top b informative labels in the entire online stream based on its own query criterion. Note that in practice, finding the exact scaling parameter is infeasible, as we do not know the online performance unless we observe the entire data stream. While it is challenging determine the scaling factor for each algorithm under the adversarial setting, one can effectively estimate the scaling factor for stochastic streams, where the context arrives i...d.
the early budget decide the scaling parameter in following evaluation: Firstly, we use small fraction (i.e. 7/10) of the online stream and see how much queries hearly each algorithm consumed. Then we calculate the scaling parameter
Concretely,
(b-h.v)) I/10 and multiply the Deayy
T-T/10
scaling factor with the query probability of each algorithm for the remaining TO rounds. The results in Fig. 13 demonstrate that CA still outperforms all the baselines (excluding Oracle) when all algorithms select the top data of the whole online stream query. The improvement of CAMS over the baseline approaches does not differ much between the two versions (with or without scaling) of the experiments shown in the bottom plots of Fig. 2 and Fig. 13.
For a head-to- ho-dtt comparison between the bottom plots of Fig. 2 and Fig. 13, note that the total number of rounds stays the same for DRIFT (T 3000), VERTEBRAL (T 80), and HIV (T 4000); while we used half the rounds and half the maximal budget for CIFARIO (T = 5000) for the version with scaling. Roughly speaking, the cumulative regret plots for the baselines were "streched out" to cover the full allocated budget after scaling, but we do not observe a significant difference in terms of the absolute gain in terms of the cumulative loss. Another way read the difference between the two plots is to compare the cumulative losses at the budget range where all algorithms were not cut off early: e.g., for DRIFT, when Query Cost is 250, the cumulative losses for the competing algorithm stay roughly the same under the two evaluation scenarios.
211
180
Curnulative
A00
250
L00
300
150
2054
720
100
Quary COO
Query
Query
Query
(a) CIFARIO
(b) DRIFT
(c) VERTEBRAL
(d) HIV
Figure 13: Comparing CAMS with 7 model selection baselines on 4 diverse benchmarks in terms of cost effectiveness after applying the scaling parameter to each algorithm. CAMS outperforms all baselines (excluding Oracle). Performance of cunulative loss by increasing the query cost, for a fixed number of rounds T' (where T' = 5000, 3000, 80, 4000 from left to right) and maximal query cost B (where B 600, 800, 60, 600 from left right). Algorithms: 4 contextual (Oracle, CQBC, CIWAL, CAMS) and 4 non-contextual baselines (RS, QBC, IWAL, MP) are included (see Section ) 90% confident interval are indicated in shades.
G.12 Ablation study on the active query strategy
In this section, we compare the performance of CAMS and its non-active variant which queries the label for each incoming data point. As shown in Fig. 14, CAMS performs equally well or better than R'AM--nonacion the DRIFT dataset, CAMS significantly outperforms "'AMS-nonactive even when using less than 10 percent of the query budget (Fig. 14b). This demonstrates that CAMS selectively choose the data to query to maximal optimize policy improvement, while CAMS queries all data points, regardless of their usefulness or noise, which hampers policy improvement and convergence.
even though it queries significantly less data. Surprisingly, on
35

---

CARS
CAMS-nonactive
Number
Rounnd
Round
Rounn
Round
2000
120
Cumulative
1400
1909
Querry
2008 Quurry code
J3 3003
Querr 064t
36a
Query 220 309 JXC
(a) CIFARIO
(b) DRIFT
(c) VERTEBRAL.
(d) HIV
Figure 14: Comparing CAMS (in red) with LAMS--onactie (in blue) on 4 diverse benchmarks
in terms of query complexity, and cost effectiveness. CAMS outperforms or performs equally well to CAMS nonactive with much less queried labels for all benchmarks. (Top) Number of queries and (Bottom) Performance of cumulative loss by increasing the query cost, for a fixed number of rounds T (where T 5000, 3000, 80, 4000 from left to right) and maximal query cost B (where B = T = 5000, 3000, 80, 4000 from left to right). 90% confident interval are indicated in shades.
G.13 Relative Cumulative Loss
Relative cumulative loss (RCL), At round I, we define RCL as Lrg, - Lr,5", where Lagj" stands for the cumulative loss (CL) of the policy always selecting the best classifier, and Lt.j. stands for the CL of policy
R5
Oracle
QBC
INAL
MP
EQBC
OWAL
CAMS
Relative cumolative
28
Round
Bound
found
Hound
(a) CIFARIO
(b) DRIFT
(c) VERTEBRAL
(d) HIV
Figure 15: Comparing CAMS with 7 baselines on 4 diverse benchmarks in terms of loss trajectory.
CAMS outperforms all baselines. Performance measured by relative cumulative loss (i.e. loss against the best classifier) under a fixed query cost B (where B 200, 400, 30, 400 from left right). Algorithms: 4 contextual (Oracle, CQBC, CIWAL, CAMS) and non-contextual baselines (RS, QBC, IWAL, MP) are included (see Section 90% confident interval are indicated in shades.
The RCL under the same query cost for all baselines is shown in Fig. 15. The loss trajectory demonstrates that CAMS efficiently adapts to the best policy after only few rounds and outperforms all baselines in all benchmarks. The result also demonstrates that CAMS can achieve negative RCL on all benchmarks, which means it outperforms any algorithms that chase the best classifier, the horizontal 0 line represents the performance benchmark of best classifier. This empirical result aligns with Theorem I that, in the worst scenario, if the best classifier is the best policy, CAMS will achieve its performance. Otherwise, CAMS will reach a better policy and incurs no regret.
CAMS could achieve such performance because when an Oracle fails to achieve 0 loss over all instances and contexts, CAMS has the opportunity to outperform the Oracle those rounds Orucle does not make the best recommendation. For instance, the stochastic version of CAMS (Line 22-23; Line 30-32 Fig. 1) may achieve this by recommending model using the weighted majority vote among all policies. Therefore, one view CAMS adaptively constructing new policy each
36

---

round by combining the advantages of each sub-optiman policy, which may outperform any single expert/policy. Furthermore, for the experiments we ran (or in most real-world scenarios), the data streams are not strictly in stochastic setting (in which single policy outperforms all others or has lower expected loss in every round). The weighted policy strategy may find a better combination of "advices" in such cases (see Fig. 2 and App. G.6).
Global Rebuttal Response
H Experiments on ImageNet
600
RS
Cumulative loss
500
Oracle
QBC
400
IWAL
300
CQBC
CIWAL
200
CAMS
500
1000
1500
2000
2500
Query cost
(a) IMAGENET
Figure 16: Comparison of CAMS with 7 baselines on IMAGENET benchmark in terms of cost effectiveness. We plot the cumulative loss as increase the query cost for fixed number of rounds T and maximal query cost B (T 3000, and = 2500). CAMS outperforms all baselines. Algorithms: 4 contextual (Oracle, CQBC, CIWAL, CAMS) and non-contextual baselines (RS, QBC, IWAL, MP) are included. 90% confident interval are indicated shades.
I Comparing CAMS against recent works in active learning
Active Learning Setting Algorithms
Coreset
Batch-BALD
VAAL; ClusterMargin
BADGE;
BALANCE: GLISTER
VeSSAL
Model Picker
CAMS
Streaming, veguential
x
Streaming, buich
Poot-buved, batch
Table 6: Selective comparison against recent works in active learning. Among these algorithms, Coreset (Sener & Savarese, 2017) is diversity sampling strategy for deep active learning; Batch- BALD is uncertainty sampling strategy; BADGE (Ash et al., 2019), VAAL (Sinha et al., 2019) ClusterMargin (Citovsky et al., 2021), and VeSSAL (Saran et al., 2023) represent strategies that combine both; GLISTER (Killamsetty al., 2020) and BALANCE (Zhang et al., 2023) represent decision-theorett approaches that directly optimize the utility of queries.
37

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We list the paper's contribution and scope clearly at the last paragraph of Section
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed our limitation at Section 7 future direction. summarizes the limitations of our approach and we hope to address in the future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that 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.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex- system might not be used reliably to provide closed captions for online lectures because it fails 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, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer: [Yes]
Justification: We have listed all the details of modeling approaches, proof assumptions, and complete proofs in Section 5, and Appendix E, F.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the code and data in the supplementary material with a readme txt for reproducing the results. Experiment details are listed in Section 6 and Appendix G, D.6.
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 be 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 to 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 a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility 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, other means that appropriate to the research performed.
also be provided via detailed
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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to 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 or verifying the results.
5. Open access to data and code
39

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code and data in the supplementary material with readme. for reproducing the results. Experiment details are listed in Section 6 and Appendix G, D.6.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips...
caasssinnollyyyy icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wwtppbcccc///cccccccccccccccclct gwtpc//gg/e//////eeo /Code//omdSsbmii /tt.e/euumissisnooooooooooo. sswssnoliccooooooooo 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 proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment details are listed in Section and Appendix G, D.6. In addition, we provide the code and data in the supplementary material with readme.txt for reproducing the results.
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 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 provide standard deviation tables and confidence interval in figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
40

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: can be found at the supplementary Appendix D.6.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp::///eeup.peeee http:/cccpbbcccbcheeeeeee htt.c//clle//ihhhcccicciieeeeee.
Answer: [Yes]
Justification: The codes are anonymous as well.
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 (e.g., there a special consid- eration due to laws 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: [Yes]
Justification: has been discussed at Abstract and Section 1.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
41

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that 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.
If 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does 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 use in package should be provided. For popular datasets, paperswi thcode. com aamdaatseess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
42

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to 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:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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.
43


Reviews:
[{"review_id": "cK3gyRMZUu", "reviewer": "Reviewer_jCcC", "summary": "The paper proposes an online active model selection strategy where at each round the learner receives an unlabeled data point as a context to adaptively select the best model to predict while limiting the label requests.", "questions": "Please refer to the weaknesses section.", "limitations": "The paper is somewhat difficult to read due to its proposal’s components explained in disconnected sections. The framework is not exactly flexible to be applied to regression or segmentation problems.  As reported, this is primarily applicable to classification problems.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1.\tThe paper introduces a model selection procedure that is designed to handle both stochastic and adversarial settings. Apart from that it includes an adaptive query strategy that considers the disagreement among the pre-trained models.\n\n2.\tThe framework is cost-effective through its adaptive query strategy and performs significantly well compared to all the contextual and non-contextual baselines.", "weaknesses": "1.\tMainstream large-scale datasets such as ImageNet, MS COCO etc. will be ideal to validate the all-around performance of the proposed CAMS framework, especially in the query cost and complexity studies.\n\n2.\tIt will be interesting to check with some of the popular and more recent baselines such as CoreSet[1], BatchBALD[2], BADGE[3] on any of the large datasets mentioned in 1.\n\n\n[1] Sener, O., & Savarese, S. (2017). Active Learning for Convolutional Neural Networks: A Core-Set Approach. ArXiv. /abs/1708.00489\n\n[2] Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. 2019. BatchBALD: efficient and diverse batch acquisition for deep Bayesian active learning. Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA, Article 631, 7026–7037.\n\n[3] Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., & Agarwal, A. (2019). Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds. ArXiv. /abs/1906.03671", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our work! Below, you will find our detailed responses to your questions.\n\n---\n>***Q1:*** \"Mainstream large-scale datasets such as ImageNet, MS COCO etc. will be ideal to validate the all-around performance of the proposed CAMS framework, especially in the query cost and complexity studies.\"\n\n***A:*** Thanks for raising the question! To address your concerns, we conducted additional experiments using a more recent and complex large-scale dataset, the ImageNet dataset with 1000 categories. We also incorporated six more recent pretrained models, including CLIP, Inception V4, VGG19, and PNASNet. In Fig. 16 of the attached global response PDF, we present our studies on cost-effective query experiments with the ImageNet dataset using these newer pretrained models. The results are consistent with our previous findings, demonstrating that CAMS outperforms all baselines. CAMS not only shows significant superiority over both contextual and non-contextual baselines but also achieves the lowest label query cost compared to existing baselines and the current state-of-the-art, ModelPicker [1].\nIn addition to ImageNet, we also conducted a cost-effective experiment on a relatively large dataset, Covtype (580K instances), shown in Fig. 3(e) and Fig. 4 in the main paper.\n\n[1] Online Active Model Selection for Pre-trained Classifiers, AISTATS 2021\n>***Q2:*** \"It will be interesting to check with some of the popular and more recent baselines such as CoreSet[1], BatchBALD[2], BADGE[3] on any of the large datasets mentioned in 1.\"\n\n***A:*** Please note that CAMS (ModelPicker and the other AL criteria adopted in the paper) is developed under the streaming setting, where data arrives sequentially or online, and the model decides which label to query. Although one can make multiple passes over the data stream, the decision of whether to query a label is dependent only on the collection of existing models (or hypotheses).\n\nOn the other hand, CoreSet, BADGE, and (Batch-)BALD are all designed as pool-based active learning baselines (where CoreSet represents a diversity sampling strategy, BatchBALD being uncertainty sampling, and BADGE representation a combination of both). The active query strategy that CAMS relies on can be viewed as a customized variant of entropy sampling, applied to the streaming setting. This in principle aligns with BALD, with a key difference in that BALD is designed for the pool-based setting as a greedy uncertainty sampling strategy. However, one cannot readily apply diversity sampling under our (streaming) problem setup. \n\n\n| **Active Learning Setting \\ Algorithms** | **Coreset (2017)** | **Batch-BALD (2019)** | **BADGE (2019); VAAL (2019); ClusterMargin (2021)** | **BALANCE (2023); GLISTER (2020)** | **VeSSAL (2023)** | **Model Picker (2021)** | **CAMS** |\n|-------------------------------------------|-------------|----------------|-------------------------------|----------------------|------------|------------------|----------|\n| *Streaming, sequential*                   | ×           | ×              | ×                             | ×                    | ×          | ✔️               | ✔️       |\n| *Streaming, batch*                        | ×           | ×              | ×                             | ×                    | ✔️         | ×                | ×        |\n| *Pool-based, batch*                       | ✔️          | ✔️             | ✔️                            | ✔️                   | ×          | ×                | ×        |\n\n\nWe also will modify section 2(related works) to address this concern.\n\n---\nWe hope our response has addressed your concerns. If you have any further inquiries, please let us know. Thank you!", "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": "GjpJ0Lowce", "reviewer": "Reviewer_PzjT", "summary": "This paper proposes a Contextual Active Model Selection (CAMS) method for addressing the problem in the online setting by selecting the optimal pre-trained model for given data points while minimizing labeling costs. CAMS utilizes contextual information to make informed model selection decisions and employs an adaptive query strategy to determine when to request labels, thereby reducing overall labeling efforts.", "questions": "The author should carefully check if typos exist in the manuscript, e.g., the caption of Table 3, \"Eq. (??)\".", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper provides very rigorous theoretical guarantees, demonstrating the algorithm's effectiveness through regret and query complexity bounds.\n\n- Compared with existing active learning approaches, CAMS's ability to efficiently handle various data distributions/scenarios and contexts makes it particularly useful for real-life applications.", "weaknesses": "- The effectiveness of CAMS heavily relies on the pre-trained models. CAMS may not perform well if the pre-trained models are diverse or representative enough or have a large domain gap with the target task.\n\n- The theoretical guarantee of regret bounds and query complexity in this manuscript, are derived under strong assumptions like stochastic, adversarial settings.\n\n- The authors use the cumulative loss as the evaluation metric, it is indeed an overall measure of performance but the normal evaluation metrics like accuracy, precision, and recall should also be considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review of our work! We greatly appreciate your recognition of the rigorous theoretical guarantees provided in this paper, both in terms of regret and query complexity bounds. We are also thankful for your acknowledgment of CAMS as particularly useful for real-life applications, filling the gap in current active learning settings.  Below, please find our detailed responses to your questions.\n\n> ***Q1:*** \"The effectiveness of CAMS heavily relies on the pre-trained models. CAMS may not perform well if the pre-trained models are diverse or representative enough or have a large domain gap with the target task.\"\n\n***A:*** CAMS will generally benefit from the diversity of pretrained models; however, when all the models present a large domain gap with the target task, CAMS will be limited by the combinational optimal performance of current models and policies. To address such concern in the worst case scenario, our adversarial setting provides a worst case performance guarantee when all models have a large domain gap with the target task.\n\n> ***Q2:*** \"The theoretical guarantee of regret bounds and query complexity in this manuscript, are derived under strong assumptions like stochastic, adversarial settings.\"\n\n***A:*** Thanks for raising the question! Yes, we provide theoretical guarantees of regret bounds and query complexity in both stochastic and adversarial settings. These settings are more like a general setting, not considered to be a strong assumption setting. \n* *Stochastic Settings* deal with inherent randomness and probabilistic outcomes, suitable for applications involving natural variability and uncertainty. These models are essential in various real-world applications due to the inherent randomness in many systems. Such as economic forecasting, chemical reaction, and biological population dynamics. \n* *Adversarial Settings* involve deliberate attempts to disrupt or manipulate systems, requiring strategies to anticipate and counteract adversarial actions. This paradigm is often used in contexts where there is a deliberate effort to deceive or hinder operations. Real-World applications of adversarial settings: such as recommendation systems etc. \n\n\n> ***Q3:*** \"The authors use the cumulative loss as the evaluation metric, it is indeed an overall measure of performance but the normal evaluation metrics like accuracy, precision, and recall should also be considered.\"\n\n***A:*** Thanks for the question! In this work, we follow the online learning literature to report the cumulative loss (as a proxy of the cumulative regret). As the reviewer rightfully suggested, employing other metrics could convey additional information. We would like to note that the cumulative loss is linear to Accuracy, i.e., Cumulative loss = T*(1-Accuracy), where T is the total number of queries seen by the algorithm. We further considered additional metrics such as the relative cumulative loss (Fig.4(a)), and query complexity (Fig.3(b)). We will make this clear in the revision.\n\n> ***Q4:*** \"The author should carefully check if typos exist in the manuscript, e.g., the caption of Table 3, Eq. (??).\"\n\n***A:*** Thank you for pointing out the typo. We have fixed it and will update it in the camera-ready version.\n\n\n---\nWe hope our response has addressed your concerns. If you have any further inquiries, please let us know. Thank you!\n\n----", "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": "99B0AfD0KO", "reviewer": "Reviewer_FX2o", "summary": "The paper introduces CAMS, an algorithm designed for online contextual active model selection. CAMS minimizes labeling costs by selecting the most appropriate pre-trained models for given contexts and strategically querying labels. The paper provides theoretical analysis of regret and query complexity in both adversarial and stochastic settings. Empirical evaluations on benchmark tasks such as CIFAR10 and DRIFT show that CAMS reduces labeling effort significantly while maintaining or improving accuracy.", "questions": "- How does CAMS handle scenarios where the set of pre-trained classifiers is not fixed or continuously updated?\n- Can more details be provided on the selection and construction of the policy set used in experiments?\n- How does the method perform when applied to tasks beyond classification, such as regression or ranking problems?", "limitations": "The author mentions the limited focus on classification and non-uniform loss functions in this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The integration of a contextual model selection mechanism with an active query strategy is a novel approach that effectively addresses the challenge of selecting the best model for varying data contexts while minimizing labeling costs.\n- The paper offers a robust theoretical foundation, with detailed proofs and analyses of regret and query complexity.\n- The empirical results are strong, showing that CAMS significantly reduces labeling effort while maintaining or improving accuracy across various benchmarks, including CIFAR10 and DRIFT.", "weaknesses": "-  The method does not discuss how it handles dynamic updates to the set of classifiers or policies. In practical applications, the set of available models may change over time. The lack of a mechanism to incorporate such updates limits the robustness and adaptability of the proposed solution.\n- While the datasets chosen provide a range of scenarios, the empirical evaluation could benefit from more recent and complex datasets to better demonstrate CAMS' capabilities. Additionally, the comparisons are primarily with older methods or basic variants, and a broader set of state-of-the-art methods, including recent advances in contextual bandits and active learning, are not fully explored.\n- Some of the mathematical notations and their explanations are dense and could be clarified further. For instance, the derivation and intuition behind the exponential weighting and the specific choice of ηt could be more thoroughly explained to improve understanding.\n- The paper does not discuss the stability of empirical results across multiple runs. Given that the evaluation relies on certain stochastic processes, it would be beneficial to report the variance or standard deviation of the results to provide a clearer picture of the method's reliability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our work! We greatly appreciate your recognition of the novelty of our approach, the robust and thorough theoretical foundation, and the strong empirical results of CAMS. Below, you will find our detailed responses to your questions.\n\n---\n\n> ***Q1:*** \"The method does not discuss how it handles dynamic updates to the set of classifiers or policies. In practical applications, the set of available models may change over time. The lack of a mechanism to incorporate such updates limits the robustness and adaptability of the proposed solution.\"\n\n***A:*** Thanks for raising the question! Yes, this is an interesting setting. In this work, we only consider the scenario of having access to pretrained models. However, in our adversarial setting, the regret bound and query complexity could address your concern and provide performance guarantees for worst-case scenarios, including cases where the available models change over time.\n\n> ***Q2:*** \"While the datasets chosen provide a range of scenarios, the empirical evaluation could benefit from more recent and complex datasets to better demonstrate CAMS' capabilities. Additionally, the comparisons are primarily with older methods or basic variants, and a broader set of state-of-the-art methods, including recent advances in contextual bandits and active learning, are not fully explored.\"\n\n***A:*** Thanks for raising the question! To address your concerns, we conducted additional experiments using a more recent and complex large-scale dataset, the ImageNet dataset with 1000 categories. We also incorporated six more recent pretrained models, including CLIP, Inception V4, VGG19, and PNASNet. In Figure 16 of the attached global response PDF, we present our studies on cost-effective query experiments with the ImageNet dataset using these newer pretrained models. The results are consistent with our previous findings, demonstrating that CAMS outperforms all baselines. CAMS not only shows significant superiority over both contextual and non-contextual baselines but also achieves the lowest label query cost compared to existing baselines and the current state-of-the-art, ModelPicker [1].\n\nIn addition, by comparing our approach with a broader set of state-of-the-art active learning methods, as shown in the following table, we illustrate that the most recent baseline with a setting closest to CAMS is ModelPicker [1].\n\n\n\n| **Active Learning Setting \\ Algorithms** | **Coreset (2017)** | **Batch-BALD (2019)** | **BADGE (2019); VAAL (2019); ClusterMargin (2021)** | **BALANCE (2023); GLISTER (2020)** | **VeSSAL (2023)** | **Model Picker (2021)** | **CAMS** |\n|-------------------------------------------|-------------|----------------|-------------------------------|----------------------|------------|------------------|----------|\n| *Streaming, sequential*                   | ×           | ×              | ×                             | ×                    | ×          | ✔️               | ✔️       |\n| *Streaming, batch*                        | ×           | ×              | ×                             | ×                    | ✔️         | ×                | ×        |\n| *Pool-based, batch*                       | ✔️          | ✔️             | ✔️                            | ✔️                   | ×          | ×                | ×        |\n\n\n[1] Online Active Model Selection for Pre-trained Classifiers, AISTATS 2021\n\n\n> ***Q3:*** \"Some of the mathematical notations and their explanations are dense and could be clarified further. For instance, the derivation and intuition behind the exponential weighting and the specific choice of ηt could be more thoroughly explained to improve understanding.\"\n\n***A:*** The derivation and intuition behind exponential weighting is: 1.Bias towards Better Predictions and effective penalty for poor predictions: It increases the weight of consistently accurate experts, quickly focusing on the best performers and improving overall performance. It significantly reduces the weight of poor predictors, minimizing their influence and maintaining robust decision-making. 2. Balancing Exploration and Exploitation: It balances exploration and exploitation by occasionally giving higher weights to less-explored actions, preventing premature convergence to suboptimal choices. 3. Mathematical Convenience: The exponential function ensures positive, normalized weights and efficient updates, making the algorithm scalable and practical for real-time applications.\nThe specific choice of ηt is a decaying lower bound on query probability to encourage exploration at an early stage, to reveal the true label more often at an early stage to differentiate the different policies and models regardless how different they present the agreement on the label. The choice of exact value of ηt is guided by our theoretical analysis. Our empirical results further validate the effectiveness of ηt.\n\n\n> ***Q4:*** \"The paper does not discuss the stability of empirical results across multiple runs. Given that the evaluation relies on certain stochastic processes, it would be beneficial to report the variance or standard deviation of the results to provide a clearer picture of the method's reliability.\"\n\n***A:*** Thank you for the comments. In our experiments, we indeed ran multiple trials for each dataset. Specifically, for the DRIFT dataset, we conducted 100 trials; for the HIV dataset, we conducted 200 trials; for the VERTEBRAL dataset, we conducted 300 trials; for the CIFAR10 dataset, we conducted 10 trials; and for the COVTYPE dataset, we conducted 6 trials. We visualized the results in each plot with a 90% confidence interval (if we approximate the outcomes over multiple trials with a Gaussian distribution, then the confidence interval is approximately proportional to the standard deviation). We will clarify this in the revised manuscript.", "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": "Ide5DvAnyh", "reviewer": "Reviewer_E9VN", "summary": "This paper focuses on the online contextual active model selection problem. Specifically, the learner receives an unlabeled data point as a context at each round, and the objective is to adaptively select the best model to predict while limiting label requests. To address this problem, the authors proposed a CAMS method that contains a contextual active model selection algorithm and an active query component. Theoretical results about regret in both adversarial and stochastic settings are provided.", "questions": "As discussed above.", "limitations": "No", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1) The problem setting that we need to do a model selection at each around is novel and interesting.\n\n2) Theoretical analysis on both adversarial and stochastic settings is provided.", "weaknesses": "About the problem setting, I have some concerns and questions:\n\n1) In different tasks, such as image classification, and tabular data, we may have many different pre-trained models. For example, in the image classification tasks, we may choose the deep neural network trained on the ImageNet, or we can also adopt the CLIP model. How to construct the candidate model pool? \n\n2) Given a model pool, in the first round, we have already selected a model. How do we decide whether we need to choose a new model or continue using the previous one?\n\n3) In the proposal, given a new instance, the algorithm needs to run each candidate model on the instance, which requires a lot of computation cost. There are also some methods proposed to assign each model a specification to describe its functionality[1]. Can these methods be combined with the proposal?\n\n4) In many cases, we may need to ensemble multiple models, can the proposal be extended to multiple model selection?\n\n[1] Lan-Zhe Guo, Zhi Zhou, Yu-Feng Li, Zhi-Hua Zhou. Identifying Useful Learnwares for Heterogeneous Label Spaces. In: Proceedings of the 40th International Conference on Machine Learning (ICML 2023), Hawaii, 2023. Page: 12122-12131.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback on our work! Below please find our detailed responses to your questions.\n\n---\n> ***Q1:*** \"In different tasks, such as image classification, and tabular data, we may have many different pre-trained models. For example, in the image classification tasks, we may choose the deep neural network trained on the ImageNet, or we can also adopt the CLIP model. How to construct the candidate model pool?\"\n\n***A:*** Thanks for letting us know your confusion. Ideally, it is beneficial to have diverse models, such as pretrained models with different structures or access to varied data distributions during the pre-training stage. CAMS learns to leverage the unique strengths of these black-box models through an online process, actively querying labels and policies. This approach tailors the queries to different contexts to distinguish the capabilities of the various policies and models.\nTo further address your concerns, we conducted additional experiments using a more recent and complex large-scale dataset, the ImageNet dataset with 1000 categories. We also incorporated six more recent pretrained models, including CLIP, Inception V4, VGG19, and PNASNet. In Fig.16 of the attached global response PDF, we present our studies on cost-effective query experiments with the ImageNet dataset using these newer pretrained models. The results are consistent with our previous findings, demonstrating that CAMS outperforms all baselines. CAMS not only shows significant superiority over both contextual and non-contextual baselines but also achieves the lowest label query cost compared to existing baselines and the current state-of-the-art, ModelPicker [1].\n\n[1] Online Active Model Selection for Pre-trained Classifiers, AISTATS 2021\n\n> ***Q2:*** \"Given a model pool, in the first round, we have already selected a model. How do we decide whether we need to choose a new model or continue using the previous one?\"\n\n***A:*** Thank you for the question. This selection process will be determined by the CAMS algorithm, which is quite dynamic. In each round, CAMS will select a model by considering policy advice regarding the model's performance in the current context. It will choose the model with the highest probability by leveraging advice from multiple experts in a stochastic setting. In an adversarial setting, it will first sample a policy based on the policies' exponential cumulative loss and then sample the model according to the policy's advice distribution.\n\n\n> ***Q3:*** \"In the proposal, given a new instance, the algorithm needs to run each candidate model on the instance, which requires a lot of computation cost. There are also some methods proposed to assign each model a specification to describe its functionality[1]. Can these methods be combined with the proposal?\"\n\n***A:*** Thanks for raising the question. Our work is quite different from the Learnware [1] setting. The main differences include the following:\n* We treat models and policies as black boxes, whereas Learnware requires assigning a specification SSS to each model, which involves parameters of the reduced model.\n* CAMS focuses on active querying and cost-effectiveness, which Learnware does not.\n* We assume that these pretrained black-box models are for the same task but with different expertise, aiming to combine their complementary expertise. In contrast, Learnware assumes models are for different tasks.\n\nTherefore, they operate in quite different settings, making it challenging to combine these methods.\n\n[1] Identifying Useful Learnwares for Heterogeneous Label Spaces. ICML 2023\n\n\n> ***Q4:*** \"In many cases, we may need to ensemble multiple models, can the proposal be extended to multiple model selection?\"\n\n***A:*** Thanks for the question. This approach can be adapted for multiple model selection scenarios by modifying the RECOMMEND part (Fig 1, lines 29-39) of the CAMS algorithm. Rather than selecting the top-ranking model for a given instance to query in a stochastic setting, we could simply select a few top candidate models to ensemble the models' predictions.\n\n\n---\n\nWe hope these responses adequately address your concerns. We appreciate your feedback and look forward to further discussions. Thank you!", "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 would like to thank all reviewers for their effort in assessing our work and for their helpful comments and questions.

We will respond separately to each reviewer concerning their individual questions. However, we would like to address one overarching theme from the reviews upfront: the performance and scalability of CAMS on large datasets and our choice of baselines. Our response is as follows:

1. **Scalability and robustness of CAMS**: To further demonstrate the scalability and robustness of CAMS, we conducted additional experiments on ImageNet and incorporated six more recent pretrained models, including CLIP, Inception V4, VGG19, and PNASNet. The results were consistent with those reported in our original submission, and the new results are provided in the attached PDF.

2. **Problem setting and baseline selection**: As shown in Table 1, the problem setting of contextual active model selection significantly differs from classical contextual bandits and active learning problems. Therefore, we focused on demonstrating that a novel combination of classical algorithmic components, namely EXP4 (for contextual bandits) and uncertainty sampling (for streaming queries), can elegantly solve this new problem. This problem is practically relevant, as pointed out by several reviewers.

3. **Comparison against recent studies in active learning**: In addition to Table 1 of our original submission, which showcases the novelty of our problem, we have added another table in the attached PDF to highlight the differences between the active model selection problem and recent studies that explicitly focus on active learning. We hope this justifies our choice of baselines as a fair selection for a well-rounded evaluation framework.

We will gladly incorporate all of these aspects in our revised manuscript.

Meta-review: This paper poses and solves an important and interesting practical problem well, and we think this paper will be impactful. While the reviewers raised a number of interesting questions, there were no fundamental concerns, and most of the questions really just point to possible extensions, such as how to train good models given the proposed process, or how to adapt to changing models.
Decision: Accept (poster)