Algorithm Selection for Deep Active Learning with Imbalanced Datasets
Authors: Jifan Zhang
Shuai Shao
saurabh verma
Robert D Nowak
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep Learning
Active Learning

Abstract: Label efficiency has become an increasingly important objective in deep learning applications. Active learning aims to reduce the number of labeled examples needed to train deep networks, but the empirical performance of active learning algorithms can vary dramatically across datasets and applications. It is difficult to know in advance which active learning strategy will perform well or best in a given application. To address this, we propose the first adaptive algorithm selection strategy for deep active learning. For any unlabeled dataset, our (meta) algorithm TAILOR (Thompson ActIve Learning algORithm selection) iteratively and adaptively chooses among a set of candidate active learning algorithms. TAILOR uses novel reward functions aimed at gathering class-balanced examples. Extensive experiments in multi-class and multi-label applications demonstrate TAILOR's effectiveness in achieving accuracy comparable or better than that of the best of the candidate algorithms. Our implementation of TAILOR is open-sourced at https://github.com/jifanz/TAILOR.

Algorithm Selection for Deep Active Learning with Imbalanced Datasets
Jifan Zhang
Shuai Shao Meta Inc. Menlo Park, CA 94025 sshao@meta.c com
Saurabh Verma Meta Inc. Menlo Park, CA 94025
University of Wisconsin Madison
Madison, WI 53715 j sifanecs... wisc.edu
saurabh08@meta.com com
Robert Nowak
University Wisconsin Madison Madison, WI 53715 rdnowakOwisc. edu
Abstract
Label efficiency has become an increasingly important objective in deep learning applications. Active learning aims to reduce the number of labeled examples needed to train deep networks, but the empirical performance of active learning algorithms vary dramatically across datasets and applications. It is difficult to know in advance which active learning strategy will perform well or best in a given application. To address this, propose the first adaptive algorithm selection strategy for deep active learning. For any unlabeled dataset, our (meta) algorithm TAILOR (Thompson ActIve Learning algORithm selection) iteratively and adap- tively chooses among a set of candidate active learning algorithms. TAILOR uses novel reward functions aimed gathering class-balanced examples. Extensive experiments in multi-class and multi-label applications demonstrate TAILOR 's effectiveness in achieving accuracy comparable better than that of the best of the candidate algorithms. Our implementation of TAILOR is open-sourced at htttp:://gtthu. wwt.ccommaaa..eeeee jjm///aan/TAALLO
Introduction
Active learning (AL) aims to reduce data labeling cost by iteratively and adaptively finding informative unlabeled examples for annotation. Label-effiiiency increasingly crucial deep learning models require large amount of labeled training data. recent years, numerous new algorithms have been
proposed for deep active learning [Sener and Savarese 2017 Gal al. 2017 Ash et al. 2019)
Kothawade et al. 2021 Citovsky et 202 Zhang et al. 12022 Relative label efficiencies among algorithms, however, vary significantly across datasets and applications (Beck et al. 202 Zhan et al. 2022]. When it comes to choosing the best algorithm for a novel dataset or application, practitioners have mostly been relying on educated guesses and subjective preferences. Prior work Baram et al. 2004 Hsu and Lin 2015 Pang et al. 2018) have studied the online choice of active learning algoritmms for linear models, but these methods become ineffective in deep learning settings (see Section 2). In this paper, we present the first principled approach for automatically selecting effective deep AI. algorithms for novel, unlabeled datasets.
We reduce the algorithm selection task to a multi-armed bandit problem. As shown in Figure T the idea may be viewed meta algorithm adaptively choosing among a set of candidate AL algorithms (arms). The objective of the meta algorithm is to maximize the cumulative reward incurred from running the chosen candidate algorithms. In Section 4 propose reward functions that encourage
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the collection of proposed maximize different notions of informativeness. As result, by utilizing our algorithm selection strategy TAILOR, we annotate examples that are both informative and class-diverse.
labeled set. As mentioned above, deep AL algorithms are generally
To highlight some of our results, as shown in Figure f the CelebA dataset, TAILOR outperforms all candidate deep AL algorithms and collects the least amount of labels while reaching the same accuracy level. TAILOR achieves this by running combination of candidate algorithms (see Appendix B to yield an informative and class-diverse set of labeled examples (see Figure ()).
Algorttim
0.22
Midia
0.48
Meta Algorithvm choose
0.44
Crie 0 Candidate Algorithin
Di O O
0.34
Uncutsiily 140
GALACY (40 aigel
Algoritim
Candiditt Algorithm/
Select unlabeled
esample x
Annotata for yo y
0.82
Ranker Hite 21. agp
Figure Adaptive active learning algorithm selection frame- work for batch size 1. Our framework proposed in Section 3.2 is a batched version that chooses multiple candidate algo- rithms and unlabeled examples in every iteration. Labels and rewards are revealed all at once at the end of the iteration.
0.28
AUD aloo
23000
60000
50600 Number of Labe's
30000
3r0050
Figure Mean Average Precision, CelebA
Our key contributions
follows:
To our knowledge, we propose the first adaptive algorithm selection strategy for deep active learning. Our algorithm TAILOR works particularly well on the challenging and prevalent class- imbalance settings [Kohawade et al. 2021 Emam et al. 2021 Zhang et al. 2022]. Our framework is general purpose for both multi-label and multi-class classification. Active learning is especially helpful for multi-label classification due to the high annotation cost of obtaining multiple labels for each example.
TAILOR can choose among large number (e.g. hundreds) of candidate deep AL algorithms even under limited (10 or 20) rounds of interaction. This is particularly important since limiting the number of model retraining steps and training batches is essential in large-scale deep active learning [iitovsky et al.) (022T.
In Section 5 we provide regret analysis of TAILOR. Although TAILOR can be viewed as a sort of contextual bandit problem, regret bound is better than that obtained by naive reduction to linear contextual bandit reduction [Russo and Van Roy 2014).
We provide extensive experiments on four multi-label and six multi-class image classification datasets (Section 6p. Our results show that TAILOR obtains accuracies comparable or better than the best candidate strategy for nine out of the ten datasets. On all of the ten datasets, TAILOR succeeds in collecting datasets as class-balance balanced as the best candidate algorithm. Moreover, with a slightly different reward function designed for active search, TAILOR performs the best in finding the highest number of positive class labels on all multi-label datasets.
2 Related Work
Adaptive Algorithm Selection in Active Learning. Several past works have studied the adaptive selection of active learning algorithms for linear models. [Dommez et al. (2007) studied the limited setting of switching between two specific strategies balance between uncertainty and diversity. To choose among off-the-shelf AL algorithms, Baram et al. [2004] first proposed a framework that reduced the AL algorithm selectino task multi-armed bandit problem. That approach aims to maximize the cumulative reward in a Classification Entropy Maximization score, which measures the blas--balancedness of predictions on unlabeled examples, after training on each newly labeled example. However, this becomes computationally intractable for large datasets with computationally expensive models. To remedy this problem, Hsu and Lin| (2015) and Pang et al. [2018) proposed the use of importance weighted training accuracy scores for each newly labeled example. The training accuracy, however, is almost always 100% for deep learning models due to their universal approximation capability, which makes the reward signals less effective. Moreover, Hsu and Lin

---

2013] reduced their problem to an adversarial multi- aame bandit problem while Pang et al. (0118) also studied the non-stationarity of rewards over time.
Lastly, we would like to distinguish the goal of our paper from the line of Learning Active Learning literature KKonuuskoova et al. 2017 (Sha et al. 2219 (Zhang et al. [020 Gonsior al. 2021 Löffler and Mutschler] 2022], where they learn single paramtereized policy model from offline datasets. These policies can nonetheless serve as individual candidate algorithms, while TAILOR aims to select the best subsets that are adapted for novel dataset instances.
Multi-label Deep Active Learning. Many active learning algorithms for multi-label classification based on linear models have been proposed [Wu et al.] 2020], but few for deep learning. Multi- label active learning algorithms are proposed for two types of annotation, example-base based where all associated labels for an example are annotated, and crumple-label-assed where annotator assigns a binary label indicating whether the example is positive for the specific label class.
While Citovsky et al. 2021]. Min et al. [022 both propose deep active learning algorithms for example-label-bsed labels, we focus on example-based annotation in this paper. To this end, Ranganathan et al. [0188) propose an uncertainty sampling algorithm that chooses examples with the lowest average cross entropy losses after trained with weak supervision. We find the EMAL algorithm by Wu et al. 2014] effective on several datasets, despite being proposed for linear models. EMAL is based on simple uncertainty metric where one averages over binary margin scores for each class. Lastly, a multi-label task can be seen as individual single-label binary classification tasks for each class [Boutell al. 2004). By adopting this view, one can randomly interleave the above-mentioned AI. algorithms for every class. In this paper, we include baselines derived from least confidence sampling [Settles| 2009). GALAXY (Zhang et al. [022] and most likely positive sampling WWarmuth et al. 2001] 2003 Jiang et al. 2018).
Balanced Multi-class Deep Active Learning. Traditional uncertainty sampling algorithms have been adopted for deep active learning. These algorithms select uncertain examples based on scores derived from likelihood softmax scores, such margin, least confidence and entropy [Tong and Koller 2001 Settles] 2009 Balcan et al., 2006 Kremer et al.] [014]. The latter approaches leverage properties specific to neural networks by measuring uncertainty through dropout [Gal et al. 2017]. adversarial examples (Ducotfe and Precioso 2018) and neural network ensembles [Beluch et al. 2018). Diversity sampling algorithms label examples that most different from each other, based on similarity metrics such as distances in penultimate layer representations [Sener and Savarese
2017 Geifman and Yaniv 2017] Citovsky al., [021]] discriminator networks [Gissin and Shalev-Shwartz/ 2019). Lastly, gradient embeddings, which encode both softmax likelihood and penultimate layer representation, have become widely adopted in recent approaches (Ash et al. 2019
202T Wang et al. 2021 Elenter et al. 2022 Mohamadi et al. 2022]. As an example, AAsh et al.
2019 uses k-means++ to query a diverse set of examples in the gradient embedding space.
Unbalanced Multi-class Deep Active Learning. More general and prevalent scenarios, such as unbalanced deep active classification, have received increasing attention in recent years KKthawade
et al. 2021 Emam et al. 2021 Zhang et al. [202 Coleman et al.) 2022 Jin et al. 2022 Aggar
wal al.] 2020 Cai 2022]. For instance, Kothawade et al. [2021] label examples with gradient
embeddings that are most similar to previously collected rare examples while most dissimilar to
out-ff-disrrbution ones. Zhang al. [2022) create linear one-vs-rest graphs based on margin scores.
To collect a more class-diverse labeled set, GALAXY discovers and labels around the optimal uncertainty thresholds through bisection procedure shortest shortest paths.
3 Problem Statement
3.1 Notation
In pool based active learning, one starts with large pool of N unlabeled examples X {#1, f2,, #N} with corresponding ground truth labels Y {y1, 12,18/,.0 ...,.... ...yy]] initially unknown to the learner. Let K denote the total number of classes. In multi-label classification, each label y, is denoted as y; E {0, 1}K with each element V/., representing the binary association between class j and example xi. On the other hand, in multi-class problem, each label yi {ej}sE[K] is denoted by canonical one-hot vector, where e, is the j-th canonical vector representing the j-th class. Furthermore, at any time, we denote labeled and unlabeled examples by L, U X correspondingly.
3

---

where LNU- = 0. We let Lo C X denote a small seed set of labeled examples and Uo = X Lo denote the initial unlabeled set. Lastly, an active learning algorithm A takes as imput pair of labeled and unlabeled sets (7, U) and returns an unlabeled example A(T, U) E U.
3.2 Adaptive Algorithm Selection Framework
In this section, we describe a generic framework that encompasses the online algorithm selection settings in Baram et al. 22044] Hsu and Lin (2015) Pang et al. (2018). As shown in Algorithm [ the meta algorithm has access to M candidate algorithms. At the beginning of any round f, a multi-set of B algorithms are chosen, where the same algorithm can be chosen multiple times. One example is selected by each algorithm in the multiset sequentially, resulting in a total of unique examples. The batch of examples are then labeled all at once. At the end of the round, their corresponding rewards are observed based on the newly annotated examples {(x*), y selected by the algorithms. The model is also retrained on labeled examples before proceeding to the next round.
j=1
Overall, the meta algorithm aims to maximize the future cumulative reward based on noisy past reward observations of each candidate algorithm. Th reward function r X x Y - IR is measured based on an algorithm's 's selected examples and corresponding labels. There are two key components to this framework: the choice of reward function and bandit strategy that optimizes future rewards. Our particular design will be presented in Section 4
Algorithm 1 General Meta Active Learning Framework for Baram et al. [2004] Hsu and Lin 2015
Pang et al. [0088]
Define: M candidate algorithms A = [Ai pool X, total number of rounds T, batch size B. Initialize: Labeled seed set Lo C X, unlabeled set Un = X\Lo and initial policy IT²
for 1 = 1, I,...? T do
Meta algorithm IT' chooses multiset of algorithms Aa, Aar, 21 Aa, where indexes
Oc,1. B, E [M]. Initialize selection set S; +
for j I,.., B do
Run algorithm to select unlabeled example x == Aa., (L1-1,U--11) that is unselected. Insert the example '..; S. +- St U (x."))
end for
Annotate {x²²} 1==1 and observe labels { -ررر Update sets L, +- L--1US, U, + U--1 Observe reward قوار r(a"., vd for each algorithm Aay,. where j [B].
Update policy statistics based on x²d, y and phs to obtain IT and retrain model on L,. end for
Objective: Maximize cumulative reward ET= ΣØ= r...
We make the following two crucial assumptions for our framework:
Assumption 3.1. Any candidate batch active learning algorithm can be decomposed into an iterative selection procedure A that returns one unlabeled example at time.
The assumption has been inherently made by our framework above where deep active learning algorithm returns one unlabeled example at a time. It entails that rumning A once to collect batch of B examples is equivalent with running the itcrative algorithm for B times. As noted in Appendix A.I most existing deep active learning algorithms can be decomposed into iterative procedures and thus can serve as candidate algorithms in our framework.
Assumption 3.2. For each round E [T]. we assume there exist ground truth reward distributions Pr, .... Pr.Mr for each candidate algorithm. Furthermore, for each element E [B] in the batch, we make the iid assumption that reward yf.j Irr,,,s is sampled from the distribution of the corresponding selected algorithm.
The iid assumption is made for theoretical simplicity by all of Baram et al. 2004 Hsu and Lin
(2055] Pang et al. (2018). We say the distributions are non-stationary if for any E MM. Pt, varies with respect to time T. Both this paper and |aag et al. [2018) study non-stationary scenarios, whereas
Baram et al. 20004 and Hsu and Lin 2015] assume the distributions are stationary across time.

---

Thompson Active Learning Algorithm Selection
In this section, we present the two key components of our design, reward function and bandit strategy. In Section 4.1 we first present a class of reward functions designed for deep active learning under class imbalance. In Section 4.2 by leveraging the structure of such reward functions, we reduce the adaptive algorithm selection framework from Section 3.2 into novel bandit setting. In Section 4.3 we then propose our algorithm TAILOR which is specifically designed for this setting. When using TAILOR on top of deep AL algorithms, the annotated examples are informative and class-diverse.
4.1 Reward F Function
We propose reward functions that encourage selecting examples so that every class is well represented in the labeled dataset, idcally equally represented or "class-balanced.. Our reward function works well even under practical scenarios such as limited number rounds and large batch sizes [Citovsky
ct al.
2021]. The rewards propose can be efficiently computed example wise opposed to
Baram et al. [2004) and are more informative and generalizable than Hsu and Lin [2015) and Pang rewards especially effective for datasets with underlying class imbalance. Recall y E {0. 1). for multi-label classification and E {e for multi-class classification. We define the following types of reward functions.
al. 2018 Our class- basss-bllace-baar
Class Diversity: To encourage better class diversity, we propose a reward that inversely weights each class by the number of examples already collected. For each round i E (T).
K
1 K
r'di (z, v)
max(1, COUNT Ua =: (Udivs v)
where COUNT' (i) denotes the number of examples in class after t rounds and y:a denotes the i-th element y. We let uyg denote the inverse weighting vector.
Multi-label Search: As shown in Table multi-label classification datasets naturally tend to have sparse labels (more O's than I's in y). Therefore, it often important to search for positive labels.
To encourage this, we define stationary reward function for multi-label classification:
K
T Teearch (I, v)
Ui =: (Upos y) where Upos K I.
K
Lastly, we would like to note that domain experts can define specialized weighting vectors of different classes v'tom E k KK that are adjusted over time t. The reward function simply takes the form rdom (x,y) = (c/ (olom y). As an example of multi-label classification of car information, thus weighting each class differently. They can also adjust the weights over time based on needs.
Domain Specific:
may prioritize classes of car brands over classes of car types,
4.2 Novel Bandit Setting
We now present a novel bandit reduction that mirrors the adaptive algorithm selection framework under this novel class of rewards. In this setup, V, - stationary. On the other hand, for each candidate algorithm A, E A, we assume the labels are sampled iid from a stationary assumption in Pos and the iid assumption are made for simplicity of our theoretical analysis only. We will describe our implementation to overcome the con-stationarity in Pg. in Section 6.1 Although we make the iid assumption analogous to Assumption 3.2, we demonstrate the effectiveness of our algorithm Section 6 through extensive experiments. Additionally, note that 6 e [0, 1]K for lulti-label classification and 6 E A (K-1) takes value in the dimensional probability simplex for multi-class classification. In our bandit reduction, at each round 1,
K R K is arbitrarily chosen and non-
distribution Pp. with mean 6'. Both the stationary
1. Nature reveals weighting vector v':
2. Meta algorithm chooses algorithms " ..... t.B which sequentially select unlabeled examples;
3. Observe batch of labels "',,...,, ..., B.B B at once, where ydd sid Poress
4. Objective: maximize rewards defined as n = (v", vr.d).
5

---

This setting bears resemblance to a linear contextual bandit problem. Indeed, one can formulate such a problem close our setting by constructing arms of vec(u'e,,
R K 1KM Here, vec(-)
vectorizes the outer product between of and the i-th canonical vector e₁. A contextual bandit algorithm observes reward r = { 8*) + after pulling arm i, where H* vec( (0) 0² ... )*]] E [0, 1 1]KM
and is some Gaussan random noise. However, this contextual bandit formulation does not take into account the observations of { f==1 at each round, which are direct realizations of 0² 034
In fact, standard contextual bandit algorithms usually rely on least squares estimates of 01 0M based on the reward signals [Russo and Van Royl [014]. As will be shown in Proposition 5.1
standard Bayesian regret upper bound from Russo and Van Roy (014)] is of order Ô(BM K VT).
Our algorithm TAILOR, on the other hand, leverages the observations of y ~ P. gotss and has regret
upper bounded by O(BVMT) (Theorem 5.2 similar to stochastic multi-armed bandit.
Algorithm 2 TAILOR: Thompson Active Learning Algorithm Selection
Input: M candidate algorithms A (Ai) pool X, total number of rounds T, batch size B. Initialize: For each E [M], at = b' = TT *
for I l,..., 7 do
Nature reveals of E K.
- 1
Choose candidate algorithms:
for 1, B do
For each E [M], sample 0 Beta(a b') for multi-label 0² Dir(a") for multi-class.
Choose a² < arg max (v", 8*).
end for
Run chosen algorithms to collect batch: for j = L..j=..... B do
Run algorithm Aqtis to select unlabeled example w/-/ and insert into St.
end for
Annotate examples in S, to observe y²y for each j E [B].
Update posterior distributions:
For each algorithm E [M]: a" +- a² +
y²1, 1' + b Es y²d).
Retrain neural network to inform next round.
end for
4.3 TAILOR
We are now ready to present TAILOR, Thompson Sampling [Thompson] 1933] style meta algorithm for adaptively selecting active learning algorithms. The key idea is to maintain posterior distributions for 01, ..., 0ad As shown in Algorithm 2 the beginning utilize uniform priors Unif(S2) over the support 22 where Ω = A (t-1) and [0, 1 respectively for multi-label and multi-class classification. We note that the choice of uniform prior is made so that it is general purpose for any dataset. In practice, one may design more task-specific priors.
Over time, we keep an posterior distribution over each ground truth mean 0 for each algorithm i E [M]. With uniform prior, the posterior distribution is an instance of either element wise Beta distributior for multi-label classification or Dirichlet distribution for multi-class classification. During each round
draw samples from the posteriors, which are then used to choose the best action (i.e., candidate algorithm) that has the largest predicted reward. After the batch of B candidate algorithms chosen, then sequentially run each algorithm to collect the batch of unlabeled examples. Upon receiving the batch of annotations, we then update the posterior distribution for each algorithm. Lastly, the neural network model is retrained on all labeled examples thus far.
5 Analysis
In this section, we present regret upper bound of TAILOR and compare against a linear contextual bandit upper bound from Russo and Van Roy 2014). Our time complexity analysis is in Appendix [.1
For [0, 1JSh and a, b z say z Beta(a, b) if for each [c],. Beta(o,, bz).

---

Given an algorithm the expected regrer measures the difference between the expected cumulative reward of the optimal action and the algorithm's ''s action. Formally for any fixed instance with @ = (0), ..., 0²), the expected regret is defined as
B
max (v', 0r - gatit iE[M]
R(T, θ) = R
where the expectation is over the randomness of the algorithm, e.g. posterior sampling in TAILOR. Bayesian regret simply measures the average of expected regret over different instances
BR(T) == ( R[TT, (0))))))
where S2 denotes the support of each 0³ and (S2) denotes the prior. Recall Q [0, 1] for multi-
label classification and = (K) for multi-class classification. While TAILOR is proposed based on uniform priors (o() uniform({)).
analysis in this section holds for arbitrary Po as long as the prior and posterior updates are modified accordingly in TAILOR
First, we would like to mention a Bayesian regret upper bound for the contextual bandit formulation mentioned in 4.2 This provides one upper bound for TAILOR As mentioned, the reduction contextual bandit is valid, but is only based on observing rewards and ignores the fact that TAILOR observes rewards and the full realizations yd of ga that generate them. So one anticipates that this bound may be loose.
2014)). Let Teontert be the posterior sampling algorithm for linear contextual bandit presented in Russo and Van Roy [2014), the Bayesian regret is bounded by
Proposition 5.1 (Russo and Van Roy
BR (Toottent) S Õ(BM K3 log TVT)
where B is the batch size, M is the number of candidate algorithms, is the number of classes, and T is the number of rounds.
We omit the proof in this paper and would like to point the readers section 6.2.1 Russo and Van Roy (2014) for the proof sketch. As mentioned in the paper, detailed confidence ellipsoid of least squares estimate and ellipsoid radius upper bound can be recovered from pages 14-15 of
Abbasi-Yadkond et al. [2011].
We present upper bound the Bayesian regret of TAILOR, which utilizes standard sub- Gaussian tail bounds based on observations of yd instead of confidence ellipsoids derived from only observing reward signals of ndo
Theorem 5.2 (Proof in Appendix B). The Bayesian regret of TAILOR is bounded by
BR(TAIL S
log M))
where B is the batch size, M is the number of candidate algorithms and I'' is total number of rounds.
We delay our complete proof to Appendix B To highlight the key difference of our analysis from Russo and Van Roy [2014), their algorithm only rely on observations of مور for each round E [T] and element E [B] in a batch. To estimate 0¹ ...., 8M, they use the least squares estimator to form confidence ellipsoids. In our analysis, we utilize observations of y's up to round I and form confidence intervals directly around each of (v', 02), ... (v', (00 by unbiased estimates {(v v)-
5.1 Time Complexity
Let Ntrain denote the total neural network training. The time complexity of collecting each batch for each active learning algorithm A; can be separated into P. and Qi which are the computa- tion complexity for preprocessing and selection of each example respectively. As examples of preprocessing, BADGE [Ash et al., 2019) computes gradient embeddings, SIMILAR [Kothawade] al. 202T] further also compute similarity kernels, GALAXY [Zhang et al. 2022 constructs linear graphs, etc. The selection complexities are the complexities of each iteration of K-means++
BADGE, greedy submodular optimization in SIMILAR, and shortest shortest path computa-
tion in GALAXY. Therefore, for any individual algorithm A,, the computation complexity is then
7

---

CLASS IMB
BINARY 1MB
DATASET
K
N
RATIO
RATIO
CELEBA
LIU ET AL.
2018
40
162770
.0733
.2257
COCO
LINET ET AL.
2014
80
82081
.0228
.0367
VOC
EVERINGHAM ET
2010
20
10000
.0749
.0721
CAR KRAUSE ET
2013
12948
.1722
.1200
IMAGENET
DENG ET AL.
2009
1000
1281167
.6311
KUZUSHUI-
CLANUWAT ET AL..
2018
49
23236
.0545
CALTECH256
GRIFFIN ET AL..
2007
256
24486
.0761
IMB CIFAR-ID
10
JrTKKR KRIZHEVSKY
2009
2
50000
.1111
IMB CIFAR- 100 KRIZHEVSKY ET AL.
2009
50000
.0110
IMB SVHN NETTZER ET AL. 2011
2
73257
.0724
Table Details for multi-label and multi-class classification datasets. K and N denote the number of classes and pool size respectively. Class Imbalance Ratio represents the class imbalance ratio between the smallest and the largest class. We also report Binary Imbalance Ratio for multi-label datasets, which is defined as the average positive ratio over classes, i.e., K [NE(K((N(/N) where N; denotes the number of examples in class i.
ONNrran + TPP + TBQ:) where T' the total number of rounds and B the batch size. When running TAILOR, as we do not know which algorithms are selected, we provide a worst case upper bound of O(Nerain T. (Σ P:) + TB max,e[M] Qi). where the preprocesingg is done for every candidate algorithm. practice, some the preprocessing operations such as gradient embedding computation could be shared among multiple algorithms,, thus only need to be computed once. As practical note all of our experiments, TAILOR is more than 20% faster than the slowest candidate algorithm it selects diverse set of candidate algorithms instead of running single algorithm the entire time. Also, the most significant time complexity in practice often lies in neural network retraining. The retraining time dominates the running time of all algorithms including reward and Thompson sampling complexities.
6 Experiments
In this section, we present results of TAILOR in terms of classification accuracy, class-balance of collected labels, and total number of positive examples for multi-label active search. Motivated by the observations, we also propose some future directions at the end.
6.1 Setup
Datasets. Our experiments span ten datasets with class-imbalance as shown in Table T For multi- label experiments, experiment four datasets including CelebA, COCO, VOC and Stanford Car datasets. While the Stanford Car dataset is multi-class classification dataset, we transform it into multi-label dataset as detailed in Appendix A.3 For multi-class classification datasets, ImageNet, Kuzushiji-49 and Caltech256 are naturally unbalanced datasets, while CIFAR-10 with 2 classes, derived from the original dataset following Zhang et al. [2022). Specifically. we keep the first K -1 classes from the original dataset and treat the of the images as a large out-of -idittribbttion K-th class.
CIFAR-100 with 10 classes and SVHN with 2 classes
Implementation Details. We conduct experiments on varying batch sizes anywhere from B 500 to B 10000. To mirror limited training budget [Citovsky al. 2021] Emam al. 2021 allow 10 or 20 batches in total for each dataset, making it extra challenging for our adaptive al algorithm selection due the limited rounds of interaction.
Moreover, we assumed observations of y are sampled from stationary distributions "i.,,...,P..... PaM in our analysis. However, these distributions could be dynamically changing. In implementation, use a simple trick to discount the past observations, where we change the posterior update in Algorithm 2 to a' +- ya' + Σ Σjar"=x and 6² <- >b' + EEjart y' We set the discounting factor y be .9 across all experiments. As will be discussed in Section 6.3 find non-stationarity in

---

(To= | an interesting future direction to study. Lastly, we refer the readers to Appendix A for additional implementation details.
Baseline Algorithms. In our experiments, we choose a representative and popular subset of the deep AL. algorithms and active search algorithms discussed in Section 2 as our baselines. To demonstrate the ability of TAILOR, number of candidate algorithms M ranges from tens to hundreds for different datasets. The baselines can be divided into three categories:
We include off-the-shelf active learning and active search algorithms such as EMAL (Wu et al. 2014] and Weak Supervision [Ranganathan et al. 2018 for multi-label classification and Confi- dence sampling [Settles] 2009 BADGE [Ash et al. 2019]. Modified Submodular optimization motivated by Kothawade et al. [2021] for multi-class classification. More implementation details
can be found in Appendices A. and A.2
per-class decomposition (Boutell al. 2004). For most likely positive sampling [Warmuth et al. [001]] [003]] Jiang et al. [2018). an active search strategy and abbreviated as MLP, we obtain K algorithms where the i-th algorithm selects examples most likely to be in the i-th class.
We derive individual candidate algorithms based
For multi-label classification, we also include K individual GALAXY algorithms (Zhang et al. [022] and K Uncertainty sampling algorithms. To further elaborate, the original GALAXY work by Zhang et al. [2022] construct K one-vs-rest linear graphs, one for each class. GALAXY requires finding the shortest shortest path among all K graphs, an operation whose computation scales linearly in K. When K is large, this becomes computationally prohibitive to run. Therefore,
we instead include K separate GALAXY algorithms, each only bisecting on one of the one-vs-rest graphs. This equivalent with running K GALAXY algorithms, one for each binary classification task between class i E [K] and the rest.
For Uncertainty sampling in multi-label settings, we similarly have K individual uncertainty sampling algorithms, where the i-th algorithm samples the most uncertain example based only on the binary classification task of class i.
As baselines for each type of algorithms above, we simply interleave the set of K algorithms uniformly at random.
We compare against other adaptive meta selection algorithms, including Random Meta which chooses candidate algorithms uniform at random and ALBL Sampling [Hsu and Lin 2015)) The candidate algorithms include all of the active learning baselines. In Appendix [ we also provide an additional study of including active search baselines as candidate algorithms.
AAMEY LL GALARY HE en!
BMN It
Nandom aaga
ALD. Pies 131.
3.55
S4DCE 1L agg
34BG2 11:0g
TAL00 rur 101
V00
5000 USbc 2i63o 28833 roice 2000 addo ex0s
32:00
6230
Mumber
600c
22004
42ice
of
8200
(a) Balanced Accuracy, CIFAR-10, classes
(b) Balanced Accuracy. Kuzushiji-49
(c) #Labels in Rarest Class, CelebA
Figure 3: Performance of TAILOR against baselines selected settings. (a) and (b) shows accuracy metries of the algorithms. (c) shows class balaacceenss of labeled examples, All performances are averaged over four trials with standard error plotted for each algorithm. The curves are smoothed with a sliding window of size 3.
6.2 Results
Multi-class and Multi-label Classification. For evaluation, we focus on TAILOR's comparisons against both existing meta algorithms and the best baseline respectively. In all classification experi- ments, TAILOR uses the class diversity reward Section 4.1 For accuracy metries, we utilize mean average precision for multi-label classification and balanced accuracy for multi-class classification.
As class diversity metric, we look at the size of the smallest class based on collected labels. All experiments measured based on active annotation performance over the pool [Zhang et al. 2022

---

As shown in Figures 2 and Appendix D when comparing against existing meta algorithms, TAILOR performs better on all datasets terms both accuracy and class diversity metrics. ALBL sampling performs similar to Random Meta in all datasets, suggesting the ineffectiveness of training accuracy based rewards proposed in Hss and Lin [2015) and Pang et al. [018]. When comparing against the best baseline algorithm, TAILOR, performs on par with the best baseline algorithm on nine out of ten datasets in terms of accuracy and on all datasets in terms of class diversity. On the CelebA dataset, TAILOR even outperforms the best baseline by significant margin in accuracy. As discussed in Appendix L TAILOR achieves this by selecting a combination of other candidate algorithm instead of choosing only the best baseline. On four out of the ten datasets, TAILOR outperforms the best baseline in class diversity. Collectively, this shows the power of TAILOR in identifying the best candidate algorithms over different dataset scenarios. Moreover in Appendix D.4, we conduct an ablation study of the accuracy of the rarest class (determined by the ground truth class distribution). TAILOR significantly outperform baselines suggesting its advantage in improving the accuracy on all classes. Lastly, shown in Appendix [ we also find TAILOR selects algorithms more aggressively than existing meta algorithms. The most frequent algorithms also align with the best baselines.
On the other hand for the Caltech256 dataset shown in Figure 16 TAILOR under-performs confidence sampling in terms of accu- racy. We conjecture this is because the larger classes may not have sufficient examples and have much space for improvement be- fore learning the smaller classes. Nevertheless, TAILOR was able to successfully collect much more class-diverse dataset while staying competitive to other baseline methods.
Bandom ngi
030000
GALANN (S)
DONA
Sus
630000
530000
Pel (322 a0d0
Multi-label Search. We use the multi-label search reward pro- posed in Section[4.]] As shown in Figure Appendix [D.3 on three of the four datasets, TAILOR performs better than the best baseline algorithm in terms of total collected positive labels. On the fourth dataset, TAILOR performs second to and on par with the best baseline. This shows TAILOR's s ability in choosing the best candidate algorithms for active search.
230000
390000
20099
4000
66300
100900
Figure 4: Total positive labels for active search, CelebA
6.3
Future Work
While our experiments focus on class-imbalanced settings, TAILOR's effectiveness on balanced datasets warrants future study through further experiments and alternative reward design. We also find studying non-stationarity in label distributes (Po, MM an interesting next step.
7 Choosing Candidate Algorithms
Our paper proposes an adaptive selection procedure over candidate deep AL algorithms. When judging individual deep AL algorithms, current standards in the research community tend to focus on whether an algorithm performs well on all dataset and application instances. However, we see value in AL algorithms that perform well only in certain instances. Consider, for example, an AL algorithm that performs well on 25% of previous applications, but poorly on the other 75%. One may wish to include this algorithm in TAILOR because the new application might be similar to those where performs well. From the perspective of TAILOR, "good" AL algorithm need not perform well on all or even most of a range of datasets, just needs to perform well on a significant number of datasets.
On the other hand, as suggested by our regret bound that scales with M, one should not include too many algorithms. In fact, there are exponential number possible AL. algorihmms, which could easily surpass our labeling budget and overwhelm the meta selection algorithm. In practice, one could leverage extra information such as labeling budget, batch size and model architecture to choose proper set of candidate algorithms to target their settings.
10

---

Acknowledgement
We would like to thank Aude Hofleitner and Shawndra Hill for the support of this research project, and Kevin Jamieson, Yifang Chen and Andrew Wagenmaker for insightful discussions. Robert Nowak would like to thank the support of NSF Award 2112471.

---

References
Yasin Yadkori, Dávid Päl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Umang Aggarwal, Adrian Popescu, and Céline Hudelot. Active learning for imbalanced datasets. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1428-1437, 2020.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34:8927- 8939, 2021.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint (rXivv1906.03677 2019.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceed- ings of the 23rd international conference on Machine learning, pages 65-72, 2006.
Yoram Baram, Ran El Yaniv, and Kobi Luz. Online choice of active learning algorithms. Journal of Machine Learning Research, 5(Mar):255-291, 2004.
Nathan Beck, Durga Sivasubramanian, Apurva Dani, Ganesh Ramakrishnan, and Rishabh Iyer. Effective evaluation of deep active learning on image classification tasks. arXiv preprini arXiv:2/06. 15324, 2021.
William H Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning in image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9368-9377, 2018.
Matthew Boutell, Jiebo Luo, Xipeng Shen, and Christopher M Brown. Learning multi-label scene classification. Pattern recognition, 379))1157-1171,, 2004.
Xinmeng Cai. Active learning for imbalanced data: The difficulty and proportions of class matter. Wireless Communications and Mobile Computing. 2022, 2022.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch active learning at scale. Advances in Neural Information Processing Systems, 34:1 14111993--1144 2021.
Tarin Clanuwat, Mikel Bober-Irizat Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. arXiv preprint arXiv: 2018.
Cody Coleman, Edward Chou, Julian Katz-Samuels, Sean Culatana, Peter Bailis, Alexander C Berg, Robert Nowak, Roshan Sumbaly, Matei Zaharia, and I Zeki Yalniz. Similarity search for efficient active learning and search of rare concepts. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6402 6410, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages
Ieee, 2009.
Pinar Donmez, Jaime G Carbonell, and Paul Bennett. Dual strategy active learning. European Conference on Machine Leurning, pages 116-127. Springer, 2007.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint arXiv: 108400 2018.
Juan Elenter, Navid NaderiAlizadehi and Alejandro Ribeiro. lagrangian duality approach to active learning. arXiv preprint arXiv:2202.04 008 2022.
Zeyad Ali Sami Emam, Mong-Min Chu, Ping-Yeh Chiang, Wojeiech Czaja, Richard Leapman,
Micah Goldblum, and Tom Goldstein. Active learning the imagenet scale. arXiv preprint a1Xi::2111.12880, 2021.
12

---

Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International journal of computer vision, 88(2): 303-338, 2010.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pages 118--1192. PMLR, 2017.
Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprini arXiv:1711.00911, 2017.
Daniel Gissin and Shai Shalev-Shwart Discriminative active learning. arXiv preprint arXiv: 2019.
Julius Gonsior, Maik Thiele, and Wolfgang Lehner. Imital: Learning active learning strategies from synthetic data, arXiv preprint arXiv:2108.07670 2021.
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
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.
Wei-Ning Hsu and Hsuan-Tice Lin. Active learning by learning. In Twenty-Ninth AAAI conference on artificial intelligence, 2015.
Shali Jiang, Gustavo Malkomes, Matthew Abbott, Benjamin Moseley, and Roman Garnett. Efficient nonmyopic batch active search. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), 2018.
Qiuye Jin, Mingzhi Yuan, Haoran Wang, Manning Wang, and Zhijian Song. Deep active learning models for imbalanced image classification. Snowledge-Baseee Systems, 257:109817, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11Xix:1412.6980, 2014.
Ksenia Konyushkova, Raphael Sznitman, and Pascal Fua. Learning active learning from data. Advances in neural information processing systems, 30, 2017.
Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer. Similar: Submodular information measures based active learning in realistic scenarios. Advances in Neural Information Processing Systems, 34: 18885-18697, 2021.
Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. object representations for fine- fine-graing graigrained categorization. In Proceedings of the IEEE international conference on computer vision workshops, pages 554-561, 2013.
Jan Kremer, Kim Steenstrup Pedersen, and Christian Igel. Active learning with support vector machines. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 4(4):313-326, 2014.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Tor Lattimore and Csaha Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pages 740-755. Springer, 2014.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Large-scale celebfaces attributes (celeba) dataset. Retrieved August, 15(2018):11 2018.
Christoffer Löffler and Christopher Mutschler. Iale: Imitating active learner ensembles. Journal of Machine Learning Research, 23(107):1-2, 2022.
13

---

Xue- Yang Min, Kun Qian, Ben-Wor Wen Zhang, Guojie Song, and Fan Min. Multi-label active learning through sarial-parallel neural networks. Knowledge-Ban Based Systems, 251:109226, 2022.
Mohamad Amin Mohamadi, Wonho Bae, and Danica Sutherland. Making look-ahead active learning strategies feasible with neural tangent kernlss. arXiv preprini arXiv:2206. 220.::2200../569,, 2022.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Kunkun Pang, Mingzhi Dong, Yang Wu, and Timothy M Hospedales. Dynamic ensemble active learning: non-stationary bandit with expert advice. In 2018 24th International Conference on Pattern Recognition (ICPR), pages 2269-2276. IEEE, 2018.
Hiranmayi Ranganathan, Hemanth Venkateswara, Shayok Chakraborty, and Sethuraman Pan- chanathan. Multi-label deep active learning with label correlation. In 2018 25th IEEE International Conference on Image Processing (ICIP), pages 3418-3422. IEEF, 8.18.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-12433, 2014.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprini urXiv:1708. 00489, 2017.
Burr Settles, Active learning literature survey. 2009.
Jingyu Shao, Qing Wang, and Fangbing Liu. Learning to sample: an active learning framework. In 2019 IEEE International Conference Data Mining (ICDM), pages 538-547, IEBE, 2019.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-2944 1933.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45 66, 2001.
Haonan Wang, Wei Huang, Andrew Margenot, Hanghang Tong, and Jingrui He. Deep active learning by leveraging training dynamics. arXiv preprint 20..:::2100.066111 2021.
Manfred K Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, and Christian Lemmen. Active learning in the drug discovery process. In NIPS, pages 1449-1456, 2001.
Manfred K Warmuth, Jun Liao, Gunnar Rätsch, Michael Mathieson, Santosh Putta, and Christian Lemmen. Active learning with support vector machines in the drug discovery process. Journal of chemical information and computer sciences, 43(2):667-667, 2003.
Jian Wu, Victor S Sheng. Jing Zhang, Pengpeng Zhao, and Zhiming Cui. Multi-label active learning for image classification. In 2014 IEEE international conference on image processing (ICIP), pages 5227-5231. IEEE, 2014.
Jian Wu, Victor S Sheng, Jing Zhang, Hua Li, Tetiana Dadakova, Christine Leon Swisher, Zhiming Cui, and Pengpeng Zhao. Multi-label active learning algorithms for image classification: Overview and future promise. ACM Computing Surveys (CSUR), 53(2):1-35, 2020.
Xueying Zhan, Qingzhong Wang, Kuan-hao Huang, Haoyi Xiong, Dejing Dou, and Antoni B Chan. A comparative survey of deep active learning. arXiv preprint arXiv:2203. 2022.
Jifan Zhang, Lalit Jain, and Kevin Jamicson. Learning to actively learn: A robust approach. arXiv preprint arXiv:2010.15388 2020.
Jifan Zhang, Julian Katz-Samuels, and Robert Nowak. Galaxy: Graph-based active learning the extreme. arXiv preprint arXiv:2202.01400; 2022.
14

---

A Implementation Details
A.1 Deep Active Learning Decomposition
For any uncertainty sampling algorithm, picking the top- most uncertain examples can easily decomposed into an iterative procedure that picks the most uncertain example. Next, for diversity based deep active learning algorithms, one usually rely on a greedy iterative procedure to collect batch, e.g. K-means++ for BADGE [Ash al. 2019) and greedy K-centers for Coreset (Sener and Savarese 2017]. Lastly, deep active learning algorithms such as Cluster-Margin [Citovsky 1021] and GALAXY [Zhang et al. 2022 have already proposed their algorithms iterative procedures that select unlabeled examples sequentially.
A.2 Implementation Modified Submodular
Instead of requiring access to balanced holdout set [Kothawade et al., 2021 we construct the balanced set using training examples. We use the Submodular Mutual Information function FLQMI suggested by Table of Kothawade al. 202 I The proposed greedy submodular optimization is itself an iterative procedure that selects one example at a time. While SIMILAR usually performs well, our modification that discards the holdout set is unfortunately ineffective in experiments. This is primarily due to the lack of the holdout examples, which may often happen in practical scenarios.
A.3 Stanford Car Multi-label Dataset
We transform the original labels into 10 binary classes of
If the brand is "Audi".
2. If the brand is "BMW".
3. If the brand is "Chevrolet".
4. If the brand is "Dodge".
5. If the brand is "Ford".
6. If the car type is "Convertible".
7. If the car type is "Coupe".
8. If the car type is "SUV".
9. If the car type is "Van".
10. If the car made in before 2009.
A.4 Negative Weighting for Common Classes
For multi-label classifications, for some classes, there could more positive associations (label of 1s) than negative associations (label of Os). Therefore, in those classes, the rarer labels are negative. In class diverse reward (o y) in Section 4.1 we implement an additional weighting of [frr * Gdius where * denotes an elementwise multiplication. Here, each element 1 Fare, E {1, -13 takes value
-1 when COUNT' (f) is larger than half the size of labeled set. This negative weighting can been seen as upsampling negative class associations when positive associations are the majority.
A.5 Model Training
All of our experiments conducted using the ResNet-18 architecture [He et al. 2016 pretrained on ImageNet. We use the Adam optimizer [Kingma and Ba 2014 with learning rate of Te-4 and weight decay of 5e-5.
B Proof of Theorem 5.2
Our proof follows a similar procedure from regret analysis for Thompson Sampling of the stochastic multi-armed bandit problem [Lattimore and Szepesvári, 2020). Let a' == {a' JB and y²
15

---

{v'") 1j=1 denote the actions and observations from the i-th round. We define the history up to t as
H, {a", ",""""""""""" v""..... a''''''''a , Moreover, for each E [M], we define Hr,, - {v/ J E H₁ a = i} as the history of all observations made by choosing the i-th arm (algorithm).
Now analyze reward estimates at each round t. When given history H;, and arm i E [M]] each observation y E H is an unbiased estimate of 6* as y ~ Pg.. Therefore, for any fixed v², (u", y) is an unbiased estimate the expected reward (v", ,0). which we denote by n
For each arm i, we can then obtain empirical reward estimate z7 of the true expected reward n by /² Iv| EyeH... (u', (e', y) where 77 if |Ht, = O. Since expected rewards and reward estimates are bounded by [-1, 11, by standard sub-Gaussian tail bounds, we can then construct confidence interval,
P (vi E [M],4 e (T), 1a n d 2 -1-7 1
where d'
(log(MT3) Iv
Additionally, define upper confidence bound as U
clipp-1.11 (it + dl.t).
At each iteration t, have the posterior distribution P(O -IH,) of the ground truth θ {0' ) = M is sampled from this posterior. Consider i = arg max (v', 0¹) and a = arg max ar (v", 8"). The distribution of it, is determined by the posterior P(O = -H,,). The distribution of a. is determined by the distribution of θ which is also P(e H2). Therefore, it and a are identically distributed. Furthermore, since the upper confidence bounds are deterministic functions of when given H,, then have E(U H.] = E Hc]-
As result, we upper bound the Bayesian regret by
T B
BR(TAILOR)
=
T
ii U + (Uttat p phaats))
=E
Now, note that since ju E [-1, 1] we have - (atht + d'it) - (1th + d' where only the upper clip takes effect. Based on the sub-Gaussian confidence intervals
(Vi E [M]te e (T). 17 ا S d 2 1
1. we can derive the following two confidence
T.
bounds:
P(vi [M], [T), ph: U P(Vi E [M], [T]. > (ipp-1,(("" + +d
= TP(Vi E [M], E (T), 1 > fz + dd since julit $
P(V e [M], E [T], Rd pzd d(tt) 1
2T
F(Vi E [M], E UT) - 1/d 2d = PP e [M],
(1I² + d
11 > 2d
<P(V e [M], pT) + th - -1²it 2d
= TPVV E [M], 1 [T), th - 1, > dz..) S 2T
Now with the decomposition,
BR(TAILOR) E
B
B
=E
UAA
+
Utal's aais
16

---

we can bound the two expectations individually.
U. we note that n² U is negative with high probability. Also, the maximum value this can take bounded by as n U E [-1, Therefore, we have
First, to bound E
Ef= p p
E
1 U
Σ Σ 0.
P(
<= <= + 12.P(p Uhitt) 2TB
2T B.
Next, bound E
E E Uhar
we decompose it similar the above:
T
B Σ
E
Utaa"
Σ
2IP(U
pataa > 2nh
2d
j=1
i=1
32 log( (TT( 1 He
B
where recall that [M4, is the number of samples collected using algorithm in rounds I t. To bound the summation, utilize the fact that TV He.l
B for each k E [|edd |H since
HH111 H4, S B. As a result, we get
32 (og
1 Hea
Hrd
32 52log(M77) B
M
$ ((v B(log + log M)
Hr.:l)
O(v B(logT + log M)) O(VBMT) / log M))
where last two inequalities follow from simple algebra and the fact that ΣM |IT,i TB. Finally, combine all of the bounds above, we get BR(TAILOR) I + O(B /MB + log M)) = O(B / MT((log + log M)).
17

---

C Study of Candidate Algorithms
We compare the performance when we the following two sets of candidate algorithms:
1. Active learning algorithms only:
Uncertainty sampling, GALAXY and EMAL for multi- label classification; Uncertainty sampling, GALAXY and BADGE for multi-class classifica- tion.
2. Active learning and search algorithms: Uncertainty sampling, GALAXY, MLP. EMAL and Weak Sup for multi-label classification; Uncertainty sampling, GALAXY, MLP, BADGE and Modified Submodular for multi-class classification.
Note Modified Submodular is classified as an active search algorithms since we are using balanced set of training examples as the conditioning set. We are effectively searching for examples similar to the ones that are annotated in these classes.
As shown in Figures 3 and 6 regardless of the meta algorithm, the performance is better when using active learning algorithms as candidates only. Nonetheless, even with active search algorithms as candidates, TAILOR still outperforms other meta active learning algorithms.
1.00
0.98
Balanced Accuracy
0.96
0.94
Random Meta (AL, algs)
0.92
Meta, algs)
TAILOR Div lours, AL algs)
algs)
0.90
A1BI Mata, (all aigs)
10000
20000
30000 Number Labels
40000
S0000
Figure 5: SVHN, Balanced Accuracy
0.90
0.88
Moan Averoge Precsion
0.86
0.84
0.82
Random Meta [AL algs)
0.80
TAILOR Div tours, alas)
Random Meta fall algs)
ALBL Meta, algs)
TAILOR Div cours, algs)
20000
40000
60000 Number Labels
80000
100000
Figure 6: CelebA, mAP
18

---

D Full Results
All of the results below are averaged from four individual trials except for Imagenet, which the result of single trial.
D.1
Multi-label Classification
Random 11 sig)
0.90
3500
Uncertairty (40 algs)
GALAXY algs)
Aunrage Precsion
0.88
Number of Positael Labels
MLP (40 algs)
EMAL
0.86
2500
Weak Sup (1 alg)
Random 11 abg)
Random Mota (81 algs]
0.84
Uncertainty (40 algs)
2000
(81 algs)
GALAXY (40 algs)
TAILOR Div tours, algs)
0.82
MLP 140 algs)
1500
alg)
0.80
Weak (1 alg)
Random Meta
1000
0.78
Meta (81 aigs]
TAILOR Div (ours, 81 algs)
20000
40000
60000 Number Labels
80000
100000
20000
40000
60000
B0000
100000
Number of Labels
(a) Mean Average Precision
(b) Number of Labels in Rarest Class
0.065
Random
Uncertainty (40 algs)
0.060
GAI AXY (40 algs)
algs)
0.055
FMAI 11 aig)
Weak alg)
0.050
Random Meta (91 algs)
Imbalance
ALBL Meta (81 algs)
0.045
(ours, algs)
0.060
0.035
0.030
20000
40000
Number Labels
(c) Imbalance Ratio
Figure CelebA
19

---

100
Random 11 alg)
algs)
GALAXY 180 alos)
Number of Preitiva Labelt
80
180 algs)
EMAL aig)
Weak Sup 11 alg!
0.70
Random 11 alg)
Uncertainty algs)
60
ALBL Meta (161 algs)
algs)
GALAXY (80 algs)
LOR lours, 161 algs)
0.65
EMAL (1 alg)
40
Weak Sup alg]
0.60
algs)
ALBL Meta (161 algs)
20-
TAILOR 161
10000
20000
30000
40800
50000
20000
30000
40000
50000
(a) Mean Average Precision
(b) Number of Labels Rarest Class
8,0046
Random alg)
Uncertainty (60 aigs]
0.0064
GALAXY (80 algel
MLP (80 algs)
0.0042
EMAL algl
Weak (1 alg)
0.0040 Randam Meta (161 algst
Meta algs)
0.0038
Div 161 aigs)
0.0036
0.0034
0.0032
10000
20000
30000
40000
50000
Number of Labels
(c) Imbalance Ratio
Figure 8: COCO
20

---

1.00
Random 11 alg)
250
algs)
GALAXY 120 alos)
Average Predsion
0.95
Number of Preitive Labels
200
EMAL aig)
120 algs)
Weak Sup 11 algi
Random O alg)
algs)
Uncertainty algs)
ALBL Meta (41 algs)
0.85
GALAXY (20 algz)
LOL tours, algs)
0.80
EMAL 11 alg)
100
Weak Sup algl
algs)
ALBL Meta (41 algs)
TAILOR
6000
10000
6000
8o0n
10000
(a) Mean Average Precision
(b) Number of Labels Rarest Class
0.23
Random alg)
Uncertainty 120 algs)
0.32
GALAXY (20
MLP algs)
EMAL aig)
0.31
( alg!
Random Mata (41 algs)
Imbalance
0.10
Meta
TAILOR Dy (ears, algs)
0.09
0.08
2000
4000
6000
8000
10000
Number of Labels
(c) Imbalance Ratio
Figure 9: VOC
21

---

600
Random 11 alg)
algs)
GALAXY 120 algs)
Number of Preitive L.ablls
500
110 algs)
EMAL alg)
Weak Sup 11 algi
0.8-
Random ( alg)
elgs)
Uncertainty algs)
ALBL Meta (21 algs)
0.7
GALAXY (20 algz)
300
LNL tours. algs)
EMAL 11 alg)
0.6
Weak Sup algl
200
algs)
ALBL Meta (21 algs)
100
TAILOR
4000
6000
8000
10000
6000
800n
10000
(a) Mean Average Precision
(b) Number of Labels Rarest Class
0.28
Uncertainty 110 algs)
Random slg)
GALAXY (10
0.26
MLP 0.0 algs)
EMAL aig)
Sup ( alg!
0.24
Randim Mata (21 algs)
Mota (21
0.22
Dav (eurs, 21 algs)
0.20
0.18-
2000
4000
6000
8000
10000
Number of Labels
(c) Imbalance Ratio
Figure 10: Stanford Car
22

---

D.2
Multi-class Classification
1.00
0.95
Number of Pocitiun Labels
4000
Balanced Accumiy
0.90
Random (1 alg!
1000
Random (1 slg)
Confidence (1 alg)
GALAXY (2 algs)
GALAXY algs)
0.85
MLP (2 algs]
2000
MEP 12 aigs)
BADGE aig)
aig)
Modified Submodular (1 alg)
Modified Submodular (1 aig)
algs]
Random
algs)
ALEL Meta (? alga)
ALBL Meta alge)
TAILOR Div (ours,
TAILOR Div tours, aigs)
0.75
5000
10000
15000
20000 25000 30000 35000 40000 Number
5000 10000 15000 20000 25000 30000 35000 40000 Number Labels
(a) Balanced Accuracy
(b) Number of Labels Rarest Class
0.50
0.45
0.35
Random (1 alg!
Confidance (1 alg)
0.30-
GALAXY algs)
algs]
0.25
BADGE (1 alg)
0.20
Random Mata (7 algs)
alg)
0.25-
slas)
(ours. 7 algs)
5000 10000 15600 20000 25000 30000 35000 40000 Number of Labels
(c) Imbalance Ratio
Figure 11: CIFAR-IO, 2 classes
23

---

Random
Confidence (1 alg)
GALAXY 110 algs)
Actunry
0.8-
Number of Postive L.beli
BADGE O1 alg)
algs)
Modified Submodubr
0.7
Random (1 alg!
Random Meta (23 algs)
Confidence alg)
AL BL Mata (23 algs)
0.6-
GALAXY (10 algs]
alps)
200
0.5
BADGE (1 alg)
Modifled Submodular (3 aig)
algs]
100
ALBL Meta (23 algs)
TAILOR
5000
10000
15000
20000 25000 30000 35000 40000
5000
10000
15000 20000 25000
30000 35000
(a) Balanced Accuracy
(b) Number of Labels Rarest Class
0.024
Random
Confidence 11 alg)
0.022
GALAXY (10
MLP (10 algs)
0.020
BADGE aig)
alg)
Random Meta (23 algs)
Meta (23
Div (ours, algs)
0.014
0.012
0.010
5000 10000 15000 20000 25000 30000 35000 40000
Number of Labels
(c) Imbalance Ratio
Figure 12: 100, 10 classes
24

---

1:00
5000
Random 11 sig)
alg)
GALAXY (2 algs)
Number of Preitiva Labels
algs)
Accuncy
BADGE alg!
Modified Submoduler algi algs)
0.96
Random (1 alg!
Confidence alg)
2000
ALBI Meta (7 algs]
0.94
GALAXY (2 algs)
TAILOR lours, algs)
BADGE (1 alg)
2000
0.92
Modifled Submodularr (1 aig)
alas]
ALBL Meta (? algs)
0.90
TAILOR
10000
20000
40000
50000
60000
10000
20000
50000
60000
70000
(a) Balanced Accuracy
(b) Number of Labels Rarest Class
0.24
Random algl
0.22
Confidence (1 alg)
GALAXY
MLP wigs/
BADGE 11 aig)
0.28
Submodutar alg)
Random Mata (7 algs)
0.16
Meta algs)
TA OR Da (ours, aigst
0.24
0.32
0.20
10000
20000
30000
40000
50000
60000
70000
Number of Labels
(c) Imbalance Ratio
Figure 13: SVHN, 2 classes
25

---

1.0-
35
Random (1 alg)
alg?
GALAXY (49 algs)
Number of Prsitovn Labelc
30
MLP (49 algs)
Balancod Acruncy
BADGE slg)
Modifed Submodular alp)
0.8-
Random (1 alg!
algs)
Confidence alg)
ALBI Meta (101 algs)
GALAXY (49 algs]
TALOR tours, 201 algs)
0.7
BADGE (1 alg)
Modifled Submodularr (3 aig)
10
alos)
ALBL Meta (101 algsi
TAILOR 101
2000
4000
6000
10000
2000
6000
8000
10000
(a) Balanced Accuracy
(b) Number of Labels Rarest Class
Random
Confidence (1 alg)
0.275
GALAXY (49
MLP algs)
0.150
BADGE
Modified Submodular alg)
0.125
Random Meta (101 aigs)
Meta alos)
0.100
Div (ours, 101 algs)
0.075
0.050
0.025
2000
4000
6000
8000
10000
Number of Labels
(c) Imbalance Ratio
Figure 14: Kuzushiji-49
26

---

1.0
Random
Confidence (1 alg!
50
GALAXY (256 algs)
Number of Resativ Labelc
algs)
Balancod Mccurnyy
0.8-
BADGE Il aig)
Modified Submodular
Random
Random Meta alga)
Confidence alg)
30
ALBL Meta (515 algs)
GALAXY (256 algs)
algs)
0.6
algs)
RADGE (1 alg)
Modifled Submodular
(515 algs)
ALBL Meta (515 algs)
algs)
5000
10000
15000 17500
25000
20000
Labels
Labels
(a) Balanced Accuracy
(b) Number of Labels Rarest Class
Figure 15: Caltech256
Random
Confidence (1 alg)
0.150
GALAXY algs)
(256 alga)
0.125
BADGE algl
Modified Submodular
Random Meta (515 algs)
0.100
Meta algst
Div (ours, algs)
0.050
0.025
0.000
2500
5000
7500 10000 12500 15000 17500 20000 Number of Labels
(a) Imbalance Ratio
Figure 16: Caltech256
27

---

D.3 Multi-label Search
Random 11 alg)
800000
GALAXY (40 algs)
Number of Postive Labels
(40
EMAL (1 elg]
Weak
E00000
Random (122 alga)
ALBL Meta (122 algs)
500000
(ours, algs)
400000
300000
200000
100000
20000
40000
60000
80000
100000
Number Labels
Figure 17: CelebA, Total Number Positive Labels
Random alg!
Uncertainty (80 algs)
Number oositvve Labels
MLP (80 aigs)
alg]
Weak Sup alg)
100000
ALBL Meta (242 algs)
TAILOR Search (ours,
80000
60000
40000
20000
10000
20000
30000
40000
50000
Number of Labels
Figure 18: COCO, Total Number of Positive Labels
14000
alg]
Uncertainty 120 algs)
GALAXY (20
Number of Positive Labes
(20 algs)
10000
EMAL alg)
Weak alg)
Random Meta (62 alos)
8000
TAILOR S serch (ours, 62 algs)
6000
2000
6000 Labels
10000
Figure 19: VOC, Total Number of Positive Labels
D.4 Rarest Class Accuracy
We conduct an ablation study the accuracy on the rarest class (determined by the ground truth class distribution). TAILOR significantly outperform baselines.
28

---

elg1
12000
Uncertainty 11. alga)
GALAXY
Number of Positive Labels
MLP (10 algs)
10000
EMAL
Weak Sup alg!
Random Meta (32 algs)
TAILOR Search (ours, 32 algs)
2000
6000 Number of Labels
Figure 20: Stanford Car, Total Number of Positive Labels
0.975
Uncertainty (40 aige)
GALAXY (40
Average Precision Barest
0.950
MLP (40 algst
EMAL O alg)
0.925
Sup (1 alg)
Randam Meta (B1 algs)
algs)
LOR Div (ours, 81 elgs]
40000
80000
100000
Number Lebels
Figure 21: CelebA, Rarest Class Accuracy
29

---

E What Algorithms Does TAILOR Choose?
In the following two figures, we can see TAILOR chooses a non-uniform set of algorithms focus on for each dataset. On CelebA, TAILOR out out-perform the best baseline, EMAL sampling, by significant margin. As we can see, TAILOR rely on selecting combination of other candidate algorithms instead of only selecting EMAL.
On the other hand, for the Stanford car dataset, TAILOR "s selection mostly align with the baselines that perform well especially in the later phase.
Uncertainty,
Uncertainty, Class 429
Uncertainty, Closs 422
Uncertainty,
Algorthims
Uncertainty, Class 414
Uncertainty, Class #30
Uncertainty,
GALAXY. Cless +29
GALAXY, Class 44
GALAXY,
10000
15000
20000
Figure 22: TAILOR 10p-10 Most Selected Candidate Algorithms on CelebA Dataset
Uncertainty, Class #4
Uncertainty,
Uncertainty.
Uncertainty, Cless +8
Algorthins
Uncertainty,
EMAL
Uncertainty, Class #2
Uncertainty,
Uncartainty,
GALAXY. Cless #4
200
400
600
800
1000
1200
Number of Selections
Figure 23: TAILOR Top-10 10 Most Selected Candidate Algorithms on Stanford Car Dataset
In the following figures, plot the number of times the most frequent candidate algorithm is chosen. As can be shown, TAILOR chooses candidate algorithm much more aggressively than other meta algorithms in eight out of the ten settings.
30

---

20000
Random Meta (7 algs)
#Selection of Most Frequent Aiganthim
ALBL Meta (7 algs)
17500
TAILOR jours, algs)
15000
12500
10000
5000
2500
5000
10000 15600 20000 25000 30000 25000
Tatall Number Selection
Figure 24: CIFAR-10, Classes, Number of Pulls of The Most Frequent Selection
8000
algs)
#Selecton of Most Frequeett Algenthim
ALBL Mets 123 eigs)
7000
alga)
6000
4000
2000
35000
Total Number Selection
Figure 25: CIFAR-100, 100, 10 Classes, Number of Pulls of The Most Frequent Selection
35000
Random Meta (7 algs)
#Selection Most Frequert oresuuee Algorthm
algs) TMLOR Div (ours, algs)
30000
25000
15000
10000
5000
10000
20000
30000
40000
50000
60000
Figure 26: SVHN, 2 Classes, Number of Pulls of The Most Frequent Selection
31

---

700
Random Mata (2003 alge)
#Solection of Most Frequent Algarthi
ALBL Meta (2003 algs)
600
TALOR
2003
400
300
200
100
20000
40000 60000 80000 10 0000 4000000000000000000000mmmmm 80000
Total Number of Selection
Figure 27: ImageNet-Ik, Number of Pulls of The Most Frequent Selection
algs)
#Selection of Most Prequent Algenthi
ALBL Meta [101 elgs)
E00
101
400
300
200
100
Total Number Selection
Figure 28: Kuzushiji-49, Number of Pulls of The Most Frequent Selection
Random Meta (515 algs)
#5arection Most Frequert Alporthmm
140
(515 algs)
TALLOR Div (ours, $15 algs)
120
100
2500
5000
7500
10000
12500
15000
17500
Figure 29: Caltech256, Number of Pulls of The Most Frequent Selection
32

---

8000 Random Meta (83 algs)
#5election of Most Frequent Aigonthim
17500
ALBL Meta algs)
TAILOR (ours, algs)
15000
12500
10000
7500
2500
10000 20000 30000 40000 s0000 6000n 70600 s0000 900n0
Total Number of Selection
Figure 30: CelebA Number Pulls of The Most Frequent Selection
#Selection Most Frequrent Algenthim
3000
ALBL Meta 1163 algs)
2500
1000
500
30000
Total Number Selection
Figure 31: COCO, Number of Pulls of The Most Frequent Selection
700
Random Meta (43 algs)
#5olection Most Frequert Alporthi
800
TAILOR Div (ours, 43 algs)
500
400
200
100
2000
4000
6000 Selection
Figure 32: VOC, Number of Pulls of The Most Frequent Selection
33

---

algs)
#Selectio of Most Prequent Algonthim
ALBL Mets 123 eigs)
alga)
1000
800
600
400
200
0-
Total Number Selection
Figure 33: Stanford Car, Number of Pulls of The Most Frequent Selection
34


Reviews:
[{"review_id": "oZJ4QZwTaZ", "reviewer": "Reviewer_Ra5K", "summary": "This paper proposes an algorithm, TAILOR, that iteratively and adaptively selects candidate active learning algorithm to gather class-balanced examples. Experimental results demonstrate that TAILOR achieves comparable or better performance than the best of the candidate algorithms. ", "questions": "Please see the weaknesses above.", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper presents a new active learning algorithm and provides some theoretical analysis. Good empirical results are reported. ", "weaknesses": "The presentation of the paper leaves much to be desired, and its contribution appears to be quite limited. Additionally, the paper contains improper or insufficiently supported claims, such as “meta algorithm”, “focus on class imbalanced setting”, and “the first adaptive algorithm selection strategy”. \n\n\n1. The organization and content selection are unsatisfactory. \n\n(1) The introduction is not well motivated or presented. The framework illustrated in Figure 1 is an adaptive active learning procedure, and it is difficult to build connection with a multi-armed bandit problem from such a figure. It is not very proper to report a result figure in the introduction as well. \n\n(2) Algorithm 1 is not the contribution of this paper but was included on page 4 with a lot of space.  Since most contents of section 3.2 are from the literature, the presentation can be largely compressed. \n\n(3) Much space of the paper is not on the main contribution of the paper. The proposed algorithm TAILOR is only presented in 4.3.  \n\n(4) Throughout the overall paper (in particular section 4), method presentation, previous work review, and contribution claims are jumbled together without a clear and logical structure of presentation.\n\n\n\n2. The presentation of the paper lacks sufficient clarity.   \n\n(1) In 4.2, the notations and concepts are not well explained. For example, what is the 1-sub-Gaussian distribution?  What does it mean by stating “Nature reveals weighting vector v^t”?  \n\n(2) Section 4.2 also fails to present a clear and principled connection of the proposed active learning setting to the bandit problem. \n\n(3) The Equations are not well explained. For example, the “\\lor” operator in the class diversity reward is not described. \n\n\n\n3. Authors claim the algorithm as a meta algorithm. The TAILOR algorithm in Algorithm 2 didn’t show any meta-learning process. The meta concept needs to be clarified. \n\n\n\n4. The paper claims on focusing on class imbalanced setting,  but  fails to provide any substantial discussion or analysis on this aspect, except for conducting experiments on datasets with class-imbalance. \n\n\n\n5. The reward functions proposed in 4.1 are heuristic and lack principled connections to the model performance. There are no discussions on how to choose reward functions on different datasets.   \n\n\n\n6. The claim of “the first adaptive algorithm selection strategy for deep active learning” is not proper. Adaptive active learning has been studied in the active learning literature. Most active learning strategies developed in the literature are not dependent on the classifiers, and hence there is no need to distinguish linear models from deep models from the active learning perspective. In particular, the proposed active learning method has no special ties to deep models. \n\n\n\n7. Many related works on adaptive active learning or meta active learning are missing, e.g., [1,2,3]. \n[1] “Adaptive Active Learning for Image Classification”. 2013. \n[2] “Active Learning with Multi-label SVM Classification”. 2013. \n[3] “Meta-Learning for Batch Mode Active Learning”, 2018.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for writing a detailed review, but the reviewer appears to have some fundamental misunderstanding of what our paper is studying.\n### Research Problem and Related Work\nWe are not proposing another active learning algorithm. Our goal is to come up with an online and adaptive way to choose from hundreds of promising active learning algorithms during deployment.\n\nTo this end, we are indeed the first to study this problem for deep neural networks. Regarding related work,\n1. All active learning algorithms are by nature adaptive. We hope the reviewer can clarify what \"adaptive active learning\" means and how it differs from standard active learning papers.\n2. The two \"adaptive active learning\" papers suggested by the reviewer are individual AL algorithms that could serve as candidate algorithms in our framework. Our paper studies algorithm selection instead of introducing another AL algorithm. While there are thousands of AL algorithms proposed, we chose a set of popular candidate algorithms in the deep AL era. The algorithms are tested to be effective in practice and considered as \"standard\".\n3. We would also like to point the reviewer to our related work section where we discuss why meta algorithms proposed for algorithm selection in the past do not work in the era of deep learning. For our problem, there is a fundamental difference between linear models and deep neural nets. While many of the past work are not even computationally feasible for deep learning, we demonstrate in our experiments that \"Active Learning by Learning\" by Hsu et al. is no better than choosing candidate algorithms at random, and significantly underperforms TAILOR.\n4. While we use the term \"meta algorithm\", it bears minimal relevance to \"meta learning\", a term only popularized in the past few years. \"Meta algorithm\" simply refers to an algorithm that controls the procedure to run a pool of algorithms, by its literal meaning. The \"meta active learning\" paper suggested by the reviewer studies a very different problem from ours. The relatedness is not immediate to us other than common wording in the title. We hope the reviewer can elaborate on the relatedness and we would be more than happy to include the \"meta AL\" literature if they are indeed related to the problem we are studying.\n### Novelty and Contribution\n1. Figure 1 is not a figure on adaptive active learning, but instead adaptive algorithm selection for active learning.\n2. Algorithm 1 and section 3.2 is a novel summarization of the past literature of Baram et al, Hsu et al, and Pang et al. While the concepts introduced are not novel, the generality of the framework is. We also feel the importance to explain our setting of \"algorithm selection\" clear by presenting this section. Again, this is not the standard AL setting but rather a less studied yet very important problem. We would also like to note that many papers spend more than one or even two pages to describe the backgrounds and formulations of prior work, which we only took less than half a page in 3.2 (Assumption 3.1 is novel).\n3. The rewards, bandit reduction, TAILOR algorithm, analysis and empirical experiments are all novel contributions. Again, we are neither studying the standard AL problem nor proposing another AL algorithm.\n### Reward Design and Choices\nTo further elaborate on connections between our reward design and accuracy performance, the goal of our meta algorithm is to adaptively select the algorithm(s) that produce a class-balanced dataset. In general, labeling a more class-balanced dataset translates to better generalization performance in balanced accuracy, as observed in prior work such as SIMILAR (Kothawade et al.) and GALAXY (Zhang et al.), which are cited in the paper. The theoretical analysis also upper bounds the cumulative regret, which is the summation over rewards designed to promote class-diversity in the labeled set. We empirically demonstrate the importance of having a class-balanced labeled set and we are glad the reviewer thinks our experiments are convincing.\n\nRegarding the choice of reward function, we believe this largely depends on the goal of using AL in practice. The Class-diverse reward is the natural choice if the practitioner would like to maximize accuracy. If the practitioner would like to solve an active search problem for multi-label classification, then active search reward should be used. In addition, our framework and analysis allows the flexibility of choosing rewards beyond the two reward functions mentioned above. As an example, in certain medical applications, certain classes may be much more important. By designing the proper weighting vector, our algorithm can be adapted to such applications. We will add part of the above clarifications as part of section 4.1.\n\nLastly, as mentioned by Reviewer 4Aq9, inverse weighted sampling has been proven successful in many contexts before. We'd argue it is a pretty standard and justified technique due to its wide adoption.\n### Our Writing\n1. We believe there's not a single \"right way\" of communicating science. As an example, OpenAI's CLIP paper \"Learning Transferable Visual Models From Natural Language Supervision\" has result figures in introduction.\n2. We would also like to point the reviewer to the other reviewers' reviews, where they unanimously rated the paper with \"good\" or \"excellent\" presentations. Two of them explicitly says \"The work is well written with great graphics like Figure 1 to illustrate key ideas\" and \"The paper is well-written and easy to follow.\"\n3. $a \\lor b := max(a, b)$, we will add this in the final version, thanks!\n4. For the definition of 1-sub-Gaussian distribution, we point the reviewer to textbooks like \"High-Dimensional Probability: An Introduction with Applications in Data Science\" by Roman Vershynin. \"Nature reveals ...\" equivalently means \"The algorithm is given ...\". Both terms are common concepts and languages in the bandit community."}, {"review_id": "QBspMPqlAE", "reviewer": "Reviewer_4Aq9", "summary": "Selecting the most appropriate active learning algorithm for a given dataset poses a significant challenge when applying active learning in real-world scenarios. This challenge stems from the fact that the performance of different active learning strategies could vary significantly across various scenarios and datasets. The paper introduces an interactive and adaptive algorithm selection strategy inspired by the concept of multi-armed bandit. By employing carefully designed reward functions, the proposed strategy can identify a subset of acquisition functions that yield maximum rewards. The authors prove that their selection algorithm exhibits a tighter bound on the Bayesian regret. Experimental evaluations conducted on both multi-class and multi-label classification tasks illustrate the promising performance of the proposed approach in terms of accuracy. ", "questions": "* For each iteration of acquisition, B samples are selected from B acquisition strategies, it sounds like an ensemble approach, doesn’t it? Different acquisition functions might capture, for example, different types of uncertainties, some to do with the model parameters, some to do directly with the model performance. Will this contribute to the performance difference?\n* The reward function focuses on the class diversity in order to deal with the class imbalanced issue. It would be interesting to design some reward function that is closely related to the model performance.\n* It is good to show the higher bound. However, can the author prove the convergence of the classifier, as done in WMOCU (Guang Zhao, Edward Dougherty, Byung-Jun Yoon, Francis Alexander, and Xiaoning Qian. Uncertaintyaware active learning for optimal Bayesian classifier. In International Conference on Learning Representations, ICLR 2021, 2021)\n* In figure 3, there is no substantial difference between TAILOR and some other methods, including BADGE, can the author explain this? Meanwhile, BADGE is a diversity-based method using clustering, how this can be adopted in TAILOR with Assumption 3.1?", "limitations": "The author briefly touches on the limitations in section 6.3 and section 7. As mentioned above, it is also good to discuss more about the computational cost which could potential benefit the AL practitioners.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* Given the diverse nature of datasets, it is crucial to carefully consider and evaluate various active learning algorithms to achieve optimal performance and effectiveness. The concept of reducing the selection of acquisition functions to a multi-armed bandit problem is interesting as it allows the election process to incorporate accumulated rewards, providing a valuable approach for algorithm selection.\n* The proposed method demonstrates adaptability to both multi-class and multi-label classification tasks by utilizing well-designed reward functions that suitably capture the task-specific requirements.\n* Additionally, the authors present a proof establishing that the proposed selection algorithm outperforms an existing algorithm with a higher bound on Bayesian regret, although the reviewer did not thoroughly examine the soundness of the proof.", "weaknesses": "* The class imbalance issue is dealt with through a proper designed reward function, discussed in section 4.1. The idea of the inversely weighting each class based on its samples is not supervising, given that the weight scheme has been widely used in imbalanced semi supervised learning. The main concern is rather the empirical studies. Even though Figure 3(c) seems to show that the proposed method could deal with the imbalance problem, there is lack of studies about how tolerate the proposed method to different class imbalance ratios. Instead of showing the number of samples in the rarest class, it is better to plot the imbalance ratio. Furthermore, it is not clear how the imbalance issue is handled in the multi-label classification tasks.\n* With respect to Assumption 3.1, it basically assumes to choose the top B samples ranked based on, for example uncertainty/least confidence scores. However, there are other methods, in particularly, some diversity-based AL methods, that choose the samples using clustering, which cannot be directly converted into an iterative selection process.\n* The efficiency aspect of the proposed method is not adequately discussed in the paper. Consideration of efficiency factors, such as computational cost or time complexity, would provide a more holistic evaluation of the proposed method's practicality and real-world applicability.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed review and we would like to address the reviewer's concerns below.\n\n### Clarification on Diversity based algorithms\nAs we have noted in Appendix A.1, all of the popular diversity-based algorithms rely on iterative procedure in choosing examples one at a time. For BADGE, the K-Means++ algorithm is an iterative procedure that produces cluster centers one at a time. This is very different from the K-means algorithm where the centers are produced all at once and dependent on the total number of clusters. Similarly, the greedy K-center algorithm for CoreSet and greedy optimization of SIMILAR are all iterative procedures that will choose the examples sequentially independent of the budget. We also point the reviewer to the implementation of BADGE in our repo as well as the original BADGE repo, which share the same core pieces of code. In short, while all such diversity algorithms tells a story of clustering, they all use greedy algorithms that are sequential and iterative in their implementations.\n\n\n### Results on Imbalance Ratio\nWe would like to thank the reviewer for suggesting this metric. We think this is indeed a valuable metric. As shown in the PDF attached in our overall Rebuttal, the imbalanced ratios follows a similar trend as the size of the rarest class. We only include 6 datasets due to page limit and will include all datasets in the final version. We also see a clearer gap by this metric. We also would like to point the reviewer to Table 1 in our paper, which details different imbalance ratios ranging from .5 to .01 for all of the datasets we experiment on in this paper.\n\n\n### Clarification on Time Efficiency\nWe refer the reviewer to Appendix C for a detailed discussion of the time complexity of TAILOR. As a practical note in all of our experiments, TAILOR is more than 20% faster than the slowest candidate algorithm as it selects a diverse set of candidate algorithms instead of running a single algorithm the entire time. We would also like to note that the most significant time complexity often lies in neural network retraining. The retraining time dominates the running time of all algorithms including TAILOR.\n\n\n### Reward Design\nHaving a reward that directly measures performance improvement is likely impossible for the practical scenarios we are considering, where examples are annotated in large batches with very few batches in total. As mentioned in our paper, this is a scenario we as practitioners face every day due to high retraining cost and setups of annotation infrastructures. This is also a scenario studied in the seminal paper \"Batch Active Learning at Scale\". Performance signals are sparse -- they are measured once for each batch. On the other hand, class-balancedness signals are per-example. Due to the limited number of batches in total and large number of candidate algorithms, a reward signal that is measured per-batch is insufficient to distinguish which algorithm is better. As a result, the best proxy reward we could think of was class-balancedness. In our experiments and prior works such as SIMILAR and GALAXY, this seems to consistently and strongly correlate with better performance under imbalance settings. In general, we totally agree with the reviewer that having a reward that directly measures performance would be great, but due to the limitations discussed above, we were unable to come up with any meaningful/effective reward design. We'd be happy to hear any concrete reward designs the reviewer has in mind.\n\n### Proof of convergence\nThe paper suggested by the reviewer proposes a specific active learning algorithm that has convergence guarantees. However, we study the very different problem of algorithm selection where we adaptively choose from a set of candidate active learning algorithms. Since the set of candidate algorithms (uncertainty sampling, BADGE, GALAXY, etc) do not have such convergence guarantees, we doubt the same type of convergence can translate to our setting. Our upper bound is on the algorithm selection aspect of the problem. Moreover, due to the non-stationarity of what each candidate algorithm choose to label (an active learning algorithm may choose examples differently early on versus later, see Reviewer LjXi's review on their practical experience also), we doubt \"convergence\" is even the right goal to pursue.\n\nWe also want to note that the paper by Zhao et al. is largely a theoretical paper where they do not even experiment on deep neural networks. On the other hand, our paper has strong empirical experiments and the candidate algorithms we choose are deep active learning algorithms proven to be empirically effective."}, {"review_id": "swBKkI5WDx", "reviewer": "Reviewer_LjXi", "summary": "The paper proposed TAILOR, a Thompson Sampling framework for active learning algorithm selection for unlabeled, possibly imbalanced datasets by framing it as a multi-arm bandit problem. The authors compared with random Meta and another meta-framework ALBL, along with other AL methods on 10 multi-class multi-label vision datasets and concluded their framework new art.", "questions": "1. As an active learning practitioner, my experience with active learning strongly signifies a non-stationarity in the effectiveness of different AL methods at different label levels (they are also path dependent, not only the number of labels but which labels were annotated till this iteration matters for the next round reward). Therefore I would like to ask how the authors bake this non-stationarity into the current formation.\n\n2. What exactly are the 40 algs in the uncertainty (40 algs)? I didn't find it in Appendix F.\n\n\n", "limitations": "No potential negative social impact of this work is observed. The authors are encouraged to address their limitations more.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\n\nThe work is deemed original based on its discussion with related work.\n\nClarity & quality:\n\nThe work is well written with great graphics like Figure 1 to illustrate key ideas. The appendix is also very helpful information. \n\nSignificance:\n\nThe work is relevant to the broader community of active learning and computer vision. The technical contribution it makes is solid in terms that the TAILOR does show improved AL efficacy compared with individual AL methods.", "weaknesses": "I have a suggestion for clarity: Add / explain what is the pool of AL algorithms that TAILOR considers at the very beginning of the paper (perhaps the intro part) as the plot shows 81 algs are considered (which can raise confusion for readers)\n\nMy major concern about the paper lies in the necessity of the different pieces of the reward function. I think an ablation study on the three different types of rewards function would do great help towards readers' understanding of relative contributions of their modules.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed review and we would like to address the reviewer's concerns below.\n\n### Clarification on Reward Design and Choices:\n\nRegarding the choice of reward function, we believe this largely depends on the goal of using AL in practice. If the practitioner would like to maximize accuracy, using the class-diverse reward is the natural choice. If the practitioner would like to solve an active search problem for multi-label classification, then one would use the corresponding active search reward. Additionally, our framework and theoretical analysis allows the flexibility of choosing reward functions beyond the two reward functions mentioned above. As an example, in certain medical applications, certain classes may be much more important. By designing the proper weighting vector, our algorithm can be adapted to such applications. We will add part of the above clarifications as part of section 4.1.\n\nFor the ablation study, we have included a comparison between class diverse reward and active search reward. As shown in figures 1&2 in the PDF attached in our overall rebuttal, the class diverse reward generates better mAP whereas the active search reward promotes the algorithms to annotate as many labels as possible. This trend is consistent in all of the datasets we have tested on. Also, note that for the class diverse reward, since we are interested in improving accuracy, we do not include the active search algorithms as candidate algorithms. The active search is a fundamentally different problem than active learning, since one almost want to annotate examples that are most certain to be in rare classes.\n\n### Clarification on Candidate Algorithms:\n\nWe agree with the reviewer that we should include more discussion on how candidate algorithms are constructed in the main text. The current form was primarily due to the page limit, and we will certainly take advantage of the extra page for the final version. We will also include part of the below discussion in the main text as the reviewer points out.\n\nTo clarify on why the uncertainty algorithms have 40 individual algorithms, we construct $K$ uncertainty sampling algorithms for each dataset. Here, $K$ is the number of classes, and the $i$-th uncertainty sampling algorithm chooses the most uncertain examples for the $i$-th class. The reviewer can think of it as decomposition into $K$ individual binary classification problems. When running uncertainty sampling baseline, we run each algorithm approximately equal number of times. This design allows each class to be sample approximately equally. We would also like to note that the baseline EMAL computes the average of the uncertainty scores across all classes and samples the examples that are overall most uncertain across classes.\n\n\n### Discussion on non-stationarity:\n\nOur experience highly aligns with what the reviewer is describing. In our paper, the non-stationarity comes to play in two regards. First, the weighting vectors $v$ changes from batch to batch. Next, since some algorithms may collect rare examples early on while others start collect rare examples later in the process, we added the discount factor gamma as described in \"Implementation Details.\" of section 6.1. Since it is very hard to directly and effectively measure the generalization performance gain in the practical high batch size, low number of batch settings, we believe the class balancedness is a good proxy. Our above methods for handling non-stationarity seems sufficient according to our experiments."}, {"review_id": "SglBGFpXrH", "reviewer": "Reviewer_Fgsj", "summary": "This paper proposes a new method for algorithm selection in active learning. The problem is treated as a multi-armed bandit problem and the proposed method is based on Thompson sampling. Extensive experiments are conducted on several datasets, including both multi-class and multi-label classification setting.", "questions": "1. Are there any datasets where BADGE does not perform well?\n2. Can BADGE be adapted for multi-label setting?\n3. What's the time efficiency of TAILOR? Is TAILOR less efficient than the single algorithm?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow.\n2. The new reward functions designed for label balance are interesting. \n3. The authors provide regret analysis and the proposed method enjoys better regret bound than the standard linear contextual bandit algorithm.\n4. The experimental results are comprehensive, including several benchmarks and two settings. TAILOR is comparable to the best candidate algorithm and even performs better than the best candidate for multi-label setting.", "weaknesses": "1. My major concern is the motivation behind active learning algorithm selection. For all the multi-class datasets, BADGE is almost always the best algorithm. Are there any datasets where BADGE does not perform well?\n2. What's the time efficiency of TAILOR? Is TAILOR less efficient than the single algorithm?\n\nMinor:\nThe figure is somewhat difficult to read the specific numbers. It would be better to provide an additional table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed review and we would like to address the reviewer's concerns below.\n\n### Motivation Behind Algorithm Selection (Why not always BADGE?)\n\nThere are many cases BADGE is not the best. For example, under class imbalance, BADGE has been shown to underperform the best algorithms as shown in papers such as \"SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios\" by Kothawade et al. and \"GALAXY: Graph-based Active Learning at the Extreme\" by Zhang et al. on almost all datasets. The reasoning behind the success of such methods is primarily due to the importance of collecting a class-diverse set of labels. On the other hand, BADGE promotes diversity in the representation/gradient space, which does not guarantee a class-diverse labeled set.\n\nMoreover, in a recent paper that just came out less than two months ago, \"LabelBench: A Comprehensive Framework for Benchmarking Label-Efficient Learning\", the authors found that BADGE sometimes even underperform margin sampling in balanced settings when one fine-tunes from large pretrained models. In the imbalanced dataset iWildCam, BADGE is also shown to perform poorly in this paper.\n\nOverall, we believe the algorithm selection problem is a very important problem even beyond imbalance settings. This problem also arises from our experience deploying active learning on new applications, where it is very unpredictable which algorithm will even work better than random sampling.\n\n\n### Adapting BADGE to Multi-label\n\nWe think this is a very interesting problem, which deserves a paper on its own. However, as we have mentioned above, BADGE does not tend to work well in imbalanced settings, so we do not feel the necessity to adopt such an algorithm to multi-label classification in our setting.\n\n\n### Time Efficiency of TAILOR\n\nWe refer the reviewer to Appendix C for a detailed discussion of the time complexity of TAILOR. As a practical note in all of our experiments, TAILOR is more than 20% faster than the slowest candidate algorithm as it selects a diverse set of candidate algorithms instead of running a single algorithm the entire time. We would also like to note that the most significant time complexity often lies in neural network retraining. The retraining time dominates the running time of all algorithms including TAILOR."}, {"review_id": "klhJqzidKX", "reviewer": "Reviewer_NzMT", "summary": "This paper proposes a novel algorithm called TAILOR  that adaptively chooses the active learning algorithm from the candidate set of multiple algorithms.  Novel reward functions are proposed that encourage choosing the algorithm such that both class diversity, as well as informativeness, are maintained while selecting unlabeled samples for the annotation. A strong theoretical justification is provided to demonstrate the effectiveness of the proposed TAILOR algorithm using regret analysis. The extensive evaluation conducted on various multiclass (imbalanced) and multilabel datasets demonstrates the ability of the proposed technique to produce comparable/better accuracy compared to the data-specific best candidate active learning strategy.\n", "questions": "1. In the rebuttal, it would be interesting to see experimental results mentioned in the weakness. ", "limitations": "See Weaknesses.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. This paper has unified the strength of existing active learning algorithms into the single TAILOR framework. This avoids the burden of finding an effective active learning algorithm for a given specific problem.\n2. The authors have provided sufficient novelty in this paper. Specifically, considering the deep active learning setting, the reward function design along with the bandit setting seems novel and non-trivial to me.\n3. The extensive experimentation is conducted considering multiple datasets under  multiclass and multilabel settings. This enhances the credibility of the effectiveness of the proposed TAILOR framework.\n4. The theoretical analysis showing better regret bounds for the proposed TAILOR algorithm compared to linear contextual bandits seems to be a very important contribution.", "weaknesses": "1. The experimentation is conducted using a single ResNet-18 architecture. Having experimental results on multiple architectures, especially more powerful ones, such as ResNet101, ViT would be helpful to even strengthen the effectiveness of the proposed technique. \n2. The impact of \\gamma (line 281)  is missing. I would expect to see the performance variation with respect to different \\gamma values (some ablation study would be helpful).\n3. One of the crucial components is the reward that is designed to maximize the participation of the data samples from the minority (rarest) classes in an imbalanced data setting. It would be interesting to see how the involvement of those minority (rarest) class data samples affects minority class performance. An ablation study comparing the rarest class performance of the proposed TAILOR framework with regard to different baselines would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed review and we would like to address the reviewer's concerns below.\n\n### Ablation Study on Rarest Class Performance\n\nAs shown in the PDF attached to our overall rebuttal (Figure 3), TAILOR significantly outperforms all other methods in improving the rarest class average precision. We will include this ablation study in the final version of our paper.\n\n### Ablation Study on Discount Factor Gamma\n\nWe agree with the reviewer that this would be a valuable experiment to run and we will include an ablation study in the final version of the paper.\n\n### Additional Experiments on Larger Network Architectures\n\nDue to resource limitations, running active learning experiments that constantly retrain large neural network architectures can be prohibitive. We agree with the reviewer that these would add value to the paper, but cannot currently accommodate such experiments. As many existing papers in deep active learning use models only as large as ResNet18, we hope this meets the bar for acceptance. We will also add a note in future work and limitations section regarding model architectures."}]

Author rebuttal:
We would like to thank all of the reviewers for their insightful reviews. Attached PDF includes all of the figure plots mentioned in our rebuttals to each individual reviewer.

Meta-review: This paper was reviewed by 5 experts in the field and received one Reject, one Borderline Accept, two Weak Accept and one Accept as the ratings. The reviewers agreed that the paper addressed an important problem, and alleviates the burden of finding an effective active learning algorithm for a specific problem. Extensive experimental studies have been conducted on multiple datasets under the multiclass and multilabel settings. Theoretical analysis has also been conducted, showing better regret bounds for the proposed TAILOR algorithm compared to linear contextual bandits. 

The reviewers raised concerns about the time efficiency of the proposed algorithm, ablation studies on the different types of reward functions and on the rarest class performance, which were addressed by the authors in the rebuttal. Questions were also raised about the performance of the algorithm in the multi-label setup with class imbalance, adoption of diversity based algorithms like BADGE in the proposed framework, which were also convincingly addressed by the authors during the post-rebuttal discussion period. 

The reviewers, in general, have a positive opinion about the paper and its contributions. The AC appreciates the usefulness of the proposed method in appropriately identifying an effective active learning algorithm for a given problem, together with the theoretical analysis presented. Even though Reviewer Ra5K shares a negative opinion about the paper, the concerns raised were mostly about the organization and writing style of the paper. The AC believes that these issues can be addressed in the final version and should not be considered a reason for rejecting the paper. 

Based on the reviewers’ feedback, the decision is to recommend the paper for acceptance to NeurIPS 2023. The reviewers have expressed some valuable concerns, particularly about the choice of the candidate algorithms, ablation study on the discount factor \gamma, experiments on large model architectures and the organization and presentation of the paper. The authors are encouraged to address these in the final version of their paper. We congratulate the authors on the acceptance of their paper!
Decision: Accept (poster)