Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Authors: Shyam Nuggehalli
Jifan Zhang
Lalit K Jain
Robert D Nowak
Venue: ICML 2025 poster (2025)
Keywords: Deep Learning
Active Labeling
Class Imbalance
Primary area: deep_learning->algorithms

Abstract: Class imbalance severely impacts machine learning performance on minority classes in real-world applications. While various solutions exist, active learning offers a fundamental fix by strategically collecting balanced, informative labeled examples from abundant unlabeled data. We introduce DIRECT, an algorithm that identifies class separation boundaries and selects the most uncertain nearby examples for annotation. By reducing the problem to one-dimensional active learning, DIRECT leverages established theory to handle batch labeling and label noise -- another common challenge in data annotation that particularly affects active learning methods.
Our work presents the first comprehensive study of active learning under both class imbalance and label noise. Extensive experiments on imbalanced datasets show DIRECT reduces annotation costs by over 60\% compared to state-of-the-art active learning methods and over 80\% versus random sampling, while maintaining robustness to label noise.

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Shyam Nuggehalli"
Jifan Zhang"
Lalit Jain
Robert Nowak
Abstract
To mitigate this issue, many recent active learning algo- rithms have focused on labeling more class-balanced and informative examples (Aggarwal et al., 2020; Kothawade et al., 2021; Zhang et al., 2022; 2024b; Soltani et al., 2024). For many large-scale annotation jobs, this challenge of data imbalance is further compounded by label noise a critical and common issue that results from annotator decision fa- tigue and perception differences. A rich body of literature agnostic active learning (Balcan et al., 2006; Dasgupta et al., 2021)
Class imbalance severely impacts machine learn- ing performance on minority classes real-world applications. While various solutions exist, ac- tive learning offers a fundamental fix by strate- gically collecting balanced, informative labeled examples from abundant unlabeled data. We intro- duce DIRECT, algorithm that identifies class separation boundaries and selects the most uncer- tain nearby examples for annotation. By reducing the problem to one-dimensional active learning, DIRECT leverages established theory to handle batch labeling and label noise- another common challenge in data annotation that particularly af- fects active learning methods. Our work presents the first comprehensive study of active learning under both class imbalance and label noise. Ex- tensive experiments on imbalanced datasets show DIRECT reduces annotation costs by over 60% compared state-of-the-ar active learning meth- ods and over 80% versus random sampling, while maintaining robustness to label noise.
et al., 2007; Hanneke et al., 2014: addresses this challenge on low-complexity model classes (e.g. linear models). However, for deep learning models, these algorithms often becomes ineffective due to the large model class complexity. In this paper, we propose novel active learning strategy for both class imbalance and label noise. Our algorithm DIRECT sequentially and adaptively chooses informative and more class baass-balaneed examples for annotation while being robust to noisy annotations. To the best of our knowledge, this is the first deep active learn- ing study to address the challenging yet prevalent scenario where both imbalance and label noise coexist.
To bridge the gap between the imbalanced deep active learn ing and the agnostic active learning literature, we propose a novel reduction of the imbalanced classification problem into a set of one-dimensional agnostic active learning prob- lems. For each class, our reduction sorts unlabeled examples into an list ordered by one- ve-rest margin scores. The objec- tive of DIRECT which best separates the examples in the given class from the rest. By relating problem to that of finding the best threshold classifier, we are able to employ ideas from the ag- nostic active learning literature to learn the separation thresh- old robustly under label noise. By annotating around the threshold, the annotated examples are more class-balas balancb and informative.
1. Introduction
Large-scale deep learning models are playing increasingly important roles across many industries. Human feedback and annotations have played significant role in develop- ing such systems. Progressively over time, we believe the role of humans in a machine learning pipeline will shift to annotating rare yet important cases. However, under data imbalance, the typical strategy randomly choosing exam- ples for annotation becomes especially inefficient. This is because the majority of the labeling budget would be spent on common and well-learned classes, resulting in insuffi- cient rare class examples for training an effective model.
find the optimal separation threshold
Comparing existing active learning algorithms such as BADGE (Ash et al., 2019), Cluster-Margin (Citovsky et al., 2021), SIMILAR (Kothawade et al.. 2021). GALAXY (Zhang et al., 2022) and many others, DIRECT improves significantly label efficiencies less annotations needed to reach the same accuracy. Notably, most existing methods mentioned above are proposed handle batch la-
Equal contribution University of Muacconsin-Madisoon UUniversity Washington, Seattle. Correspondence to: Jifan Zhang <jifan@es. wisc.edu>>
less
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

3223 Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
0.82
Random
LIM IPLOMO
0.68
Rantiom
3/M LSLONO
Random
0.34
B6
BA3G:
0.56
BADGE
Cont dence Sampling
Bolanced Tee Accursee
0-05225
Margis Sumpling
RADGE
0.82
0.92
Nest Jiely Fostive
RASE
Ouzzr Vargin
0.64
GALARY (Bquine 23
DREET Chacstr
GALAXYLPP
CORESET
Corfience Sampling
DIRFCT( Baonai
29
0.75
0.72
Linecl 15 1)
DIRECT 8p 50
0.00
0,
0.24
0.38
0.72
0.72
1000
2020
Numberot Lubel
4205
5000
1000
2200
Number Laids
3000
4000
5000
5000
15000
Number Label
15200
20030
25000
30000
(a) Imbalanced CIFAR-10, 10, two classes, no (b) Imbalanced CIFAR-100, two classes, (c) LabelBench FMoW (62 classes with im- balance). no label noise
label noise.
20% label noise.
Figure 1: Performance of DIRECT over existing baselines for both noiseless and noisy settings. The x-axis represents the total number of labeled examples so far and the y-axis shows the neural network's ' balanced accuracy. Both (a) and (b) are using supervised training of ResNet-18. In (c), we finetune CLIP ViT-B32 model in combination of semi-supervised training under the LabelBench framework (Zhang et al., 2024a). Bpanallll is the batch size indicating the number of parallel annotators. Bparallal = 1 indicates the synchronous annotation requirement by GALAXY. Our algorithm DIRECT takes pre-specified parallle as input, which determined by real world scenarios.
beling, while previous work by Zhang et al. (2022) proposes superior performance algorithm at the cost of only allow- ing one annotation at time. Our algorithm DIRECT is able to obtain the best of both worlds practical scalability to large annotation jobs by batch labeling while also getting su- perior performance than all algorithms including GALAXY. On imbalanced datasets, DIRECT achieves state-of-art label efficiency on both supervised fine- tne-tuning of ResNet-18 and semi-supervised fine-tuning of large pretrained model under the LabelBench (Zhang et al., 2024a) framework.
annotation. Many uncertainty- based deep active learning methods extend the traditional active learning literature such as margin, least confidence and entropy sampling (Tong & Koller, 2001; Settles, 2009; Balcan et al., 2006; Kremer et al., 2014). These methods have been shown to perform among the top when fine-tuning large pretrained models and combined with semi-supervised learning algorithms (Zhang et al., 2024a). More sophisticated methods have been proposed optimize chosen examples' uncertainty (Gal et al., 2017; Ducoffe & Precioso, 2018; Beluch et al., 201 8), diversity (Sener & Savarese, 2017; Geifman & El- Yaniv, 2017; Citovsky et al., 2021). or mix of both (Ash et al., 2019; 2021; Wang et al., 2021; Elenter et al., 2022; Mohamadi et al., 2022). However, these methods often perform poorly under prevalent and realistic scenarios such as label noises (Khosla et al., 2022) or class imbalance (Kothawade al., 2021; Zhang al., 2022; 2024a).
To summarize our main contributions:
We propose a novel reduction that bridges the advance- ment in the theoretical agnostic active learning literature to imbalanced active classification for deep neural net- works.
Our algorithm DIRECT addresses the prevalent imbal- ance and label noise issues and annotates a more class- balanced and informative set of examples. Compared to state-of-art algorithm GALAXY (Zhang et al., 2022), DIRECT allows parallel annotation by mul- tiple annotators while still maintaining significant label- efficiency improvement.
Deep Active Learning under Imbalance Data imbalance and rare instances are prevalent in almost all modern ma- chine learning applications. Active learning techniques are effective in addressing the problem in its root by col- lecting a more class-balanced dataset (Aggarwal et al., 2020; Kothawade et al., 2021; Emam al., 2021; Zhang et al., 2022; Coleman et al., 2022: Jin et al., 2022; Cai, 2022; Zhang et al., 2024b; Xie et al., 2024). To this end, Kothawade et al. (2021) propose a submodular-base method that actively annotates examples similar to known examples of rare instances. GALAXY et al., 2022) constructs one-dimensional linear graphs and applies graph- based active learning techniques annotating a set of ex- amples that are both Mlas-bblaacee and uncertain. While GALAXY outperforms existing algorithms, due to bisec- tion procedure involved, it does not allow parallel annotation. In addition, bisection procedures are generally not robust
We conduct experiments across 12 dataset settings, four levels of label noise and for both ResNet-18 and large pretrained model (CLIP ViT-B32). DIRECT consistently outperforms existing baseline algorithms by saving more than 60% annotation cost compared to the best existing algorithm, and more than 80% annotation cost compared to random sampling.
2. Related Work
Class-Balanced Deep Active Learning Active learning strategies sequentially and adaptively choose examples for
2

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
against label noises, a prevalent challenge in real world an- notation tasks. Our algorithm DIRECT mitigates all of the
our work is agnostic to the noise distributions and conduct experiments on uniformly random corrupted labels. To knowledge, no deep active learning literature has studied the scenario where both imbalance and label noise present. Yet, this setting is the most prevalent in real-world annotation applications.
above shortcomings of GALAXY while outperforming it even with synchronous labeling and no label noise, beating GALAXY in its own game. Lastly, we distinguish our work from Zhang et al. (2024b), where the paper studies the al- gorithm selection problem. Unlike our goal of proposing a new deep active learning algorithm, the paper proposes meta algorithms to choose the right active learning algo- rithm among large number of candidate algorithms.
3. Preliminary
3.1. Notations
Agnostic Active Learning for Label Noise Label noise for active learning has been primarily studied under the exten- sive literature on agnostic learning. We refer the interested reader to the survey (Hanneke et al., 2014) for a thorough discussion. All of these works, beginning with the semi- nal works by Balcan et al. (2006); Dasgupta et al. (2007), follow a familiar paradigm of disagreement based learn- ing. This involves maintaining version space of promising hypotheses at each time and constructing a disagreement region of unlabeled examples. For any unlabeled example in the disagreement region, there exists two hypotheses in the version disagreeing on their predictions. An example then chosen for annotation by sampling from a informative sampling distribution computed over the disagreement re- gion. Several approaches have been proposed for computing such sampling distributions, e.g. Jain & Jamieson (2019); et al. (2020; 2021); Huang et al. (2015). As described in Section 4.3, our main subroutine VReduce is equivalent to Exee-bbugeet one dimensional threshold dis- agreement learning based on the ACED algorithm of Katz- Samuels et al. (2021). We remark that these algorithms tend to be overly pessimistic in training deep neural nets, and this paper hopes to close this gap.
We study the pool-based active learning problem, where an initial unlabeled set of N examples X == {xI,...,'' NN> are available for annotation. Their corresponding labels Y = (11, --.. UN } are initially unknown. Furthermore, we study the multi-class classification problem, where the space of labels y == [K] is consisted of K classes. Moreover, let Ni...., .Nx denote the number of examples in X of each minke[K] Na. class. We define the imbalance ratio as 7 [ Nur
A deep active learning algorithm iteratively chooses batches of examples for annotation. During the t-th iteration, the algorithm is given labeled and unlabeled sets of examples, L, and U2 respectively, where LUUU, = X and LU = 0. The algorithm then chooses B examples from the unlabeled set (() S Ut and then obtains their corresponding labels y The labeled and unlabeled sets are then updated, i.e., L+ < L, U ( and U4+1 + U,) Based on new labeled set L and its corresponding labels, neural net- work ft X - [K] is trained to inform the choice for the next iteration. The ultimate goal of deep active learning is to obtain high predictive accuracy for the trained neural network while annotating as few examples as possible.
3.2. Limitations of Existing Imbalanced Active Learning Algorithms
Deep Active Learning under Label Noise Label noisy settings has rarely been studied in the deep active learning literature. Related but tangential to our work, several papers have studied to use active learning for cleaning existing noisy labels (Lin et al., 2016; Younesian et al., 2021). In this line of work, they assume access to an oracle annotator that will provide clean labels when queried upon. This is funda- mentally different from our work, where our annotator may provide noisy labels. Another line of more theoretical active learning research studies active learning with multiple anno- tators with different qualities (Zhang & Chaudhuri, 2015; Chen et al., 2022). The primary goal in these work is to identify examples a weak annotator and strong annotator may disagree, in order to only use the strong annotator on such instances. In our work, we assume access to a single source of annotator that is noisy, which is prevalent in anno- tation jobs today. Recently, Khosla al. (2022) proposed novel deep active learning algorithm specialized for Het- eroskedastic noise, where different "regions" of examples are subject to different levels of noise. Unlike their work,
Below we document the several active learning algorithms and how their progressive improvement. At the end, we highlight the shortcomings of the state-of-art algorithm GALAXY (Zhang et al., 2022) and motivate DIRECT's objective of adaptively finding the optimal separation thresh- old. We first consider an imbalanced binary classification case, where N1 < N2 without loss of generality.
Random Sampling. After annotating a significant number of examples, random sampling would annotate subset of X Ni. with an imbalance ratio close Na This approach suffers from annotating examples that are neither dass-balanced nor informative.
Uncertainty Sampling. In the binary classification case, uncertainty sampling methods, such as confidence (Settles, 2009), margin (Tong & Koller, 2001; Balcan et al., 2006) and entropy (Kremer et al., 2014) sampling, simply sort examples based on their predictive sigmoid scores ğ and
3

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Optimal Separation
the right (see Figure 2b). The algorithm aims find all cuts in the sorted graph as shown in Figure 2b. However, GALAXY suffers from three weaknesses:
Threshold j*
π = 0.3
0 = 0.5
O ... +000::00 ?
00000
1. During active learning, the neural network is still under training and cannot perfectly separate the two classes of examples yet. Therefore, the sorted graph could have a significant number of cuts. As an example in Figure 2b, when annotating around all of such cuts, the algorithm could waste significant portion of the annotation budget around misclassified outliers, leading to a large number of majority class annotations.
Low, Class
High, Class 2
Sigmoid Score P
(a) Uncertainty based methods that query around p = .5 could annotate examples only in the majority class. Cut
Cut
O OO 000-
...
2. Under label noise, the incorrect annotation could lead to more cuts in the sorted graph, further exacerbating the above issue.
Low, Class 1
High, Class 2
Sigmoid Score p
(b) GALAXY spends approximately equal annotation budget around both cuts, while the cut on the right would yield examples mostly in the majority class.
GALAXY finds all cuts through a modified bisection procedure, which only allows for sequential labeling and prevents multiple annotators labeling in parallel.
Figure 2: Demonstration of existing imbalance active learn- ing algorithms. Ordered lists of examples are ranked by the predictive sigmoid score p. The ground truth label of each example is represented by its border- solid blue for class and dotted red for class 2. Annotated examples are shaded.
In this paper, we take a DIRECT approach by identifying only the optimal separation threshold and address all of the shortcomings above.
4. A Robust Algorithm for Active Learning under Imbalance and Label Noise
annotate examples closest to .5 as demonstrated in Fig- ure 2a. As shown in our results in Figure 1 and Section 5, uncertainty sampling, despite improving over random sam- pling, significantly underperforms DIRECT and GALAXY and consistently collects less balanced annotations. This shortcoming suggests there are significantly more majority examples than minorities around the decision boundary of .5.
In this section, we formally define the optimal separation threshold and pose the problem of identifying it as an 1- dimensional reduction to the agnostic active learning prob- lem. We then propose an algorithm inspired by the agnostic active learning literature (Balcan et al., 2006; Dasgupta et al., 2007; Hanneke et al., 2014; Katz-Samuels et al., 2021).
Objective of DIRECT. To mitigate the above issue with the decision boundary, we propose to identify the optimal separation threshold. The threshold best separates the mi- nority and majority classes and approximately equalizes the number of examples from both classes around its vicinity (see Section 4. for formal definition). We note the optimal separation threshold could be relatively distant from p = .5. as shown in Figure 2a. Our overall objective is to label ex- amples that are both uncertain and Mlass-balanced and can be decomposed into the following two-phased procedure:
4.1. An 1-D Reduction to Agnostic Active Learning
We start by considering the imbalanced binary classifica- tion setting mentioned in Section 3.2. When given a neural network model, we let P: X - [0, 1] be the predictive func- tion mapping examples to sigmoid scores. Here, a higher sigmoid score represents a higher confidence of the example being in class 2. We sort examples by their sigmoid predic- tive score similar to Section 3.2. Formally, now define the optimal separation threshold as described in Section 3.2.
1. Identify the optimal separation threshold jL that best separates the minority class from the majority class, as shown in Figure 2a.
Definition 4.1. Let 0 = ((0) S 9() < ... < 9(N). where {1() E R is a sorted permutation of (f(c,)) Fur- ther we let (z() IN and (M N denote the sorted list's corresponding examples and labels. We define the optimal separation threshold as j E {0, 1, .... N) such that
2. Annotate equal number of examples next to j* from both sides.
Limitation of G'GAAXY(Zhangg et al., 2022). As discussed above, the neural network decision boundary P .5 does not necessarily best separate minority and majority class examples. GALAXY draws inspiration from graph-based active learning. It relies on the fact that the best separation threshold must be a cut, namely thresholds with a minority class example to the left and a majority class example to
j = arg max (H()) = 1: : 51 H76) = =2: =2:1
= arg max (Hz() 2: :::::::: >>>>>>>> ا} KM60 = =1:1> j}i)
In other words, on either side of j", it has the largest discrep-
4

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Class 1:
by sigmoid scores for binary classification.
4.2. One-Dimensional Agnostic Active Learning
Class 2:
The key insight of our approach is to leverage the well- established theory of agnostic active learning for threshold classifiers, which provides robust guarantees even under label noise. This allows us to robustly identify the optimal separation threshold j* from the 1-D reduction above.
Class
Low margin score
High margin score
p 4(0)
p ((N)
Problem Formulation and Noise Handling. In the ag- nostic setting, we have a sorted sequence 4(1) S 9(2) S S ((N) with corresponding (possibly noisy) binary la- bels y(1), 9(2). W(N) The fundamental challenge is that hypothesis hj H may achieve zero empirical loss [(h;) due to label noise model misspecification.
Figure 3: Visualization of multi-class classification. For each class, we formulate the problem as a one-vs-rest binary classification problem by sorting examples based on margin scores. The black arrows indicates the optimal separation thresholds for each class.
To formalize how our algorithm handles label noise, we consider the underlying conditional probability function ((vi(a)) for each data example x;. Through the dimen- sionality reduction 2; - qi (where q the real-valued sigmoid/margin score), we obtain ordered set of 1- dimensional features {4, ) This mapping induces dis- tribution P(vilg) over the reduced space, which naturally encodes any label noise present in the annotations.
ancy in the number of examples between the two classes. This captures the intuition of Figure 2a - our goal is to find a threshold that best separates one class from the other. We quickly remark that ties are broken by choosing the largest j* that attains the argmax if class 1 is the minority class and the lowest j otherwise.
ID Reduction. We now provide a reduction of finding j* to an I-dimensional agnostic active learning problem. We
Our objective is to find the threshold classifier hy- from the set of 1-dimensional threshold classifiers (h₂) that mini- mizes the probability of error with respect to P Cru- cially, our agnostic approach makes no assumptions about the form of P(y (z,)) or the induced (()llg), allowing the algorithm to handle arbitrary noise models without requiring prior knowledge of the noise distribution.
define the hypothesis class H = (ho, .i.... hy) where
1 if S 96)
each hypothesis hy is defined as hy(9)= 2 qf > q
Here, 9(0)- = 0 defines the hypothesis ho that predicts class 2 at all times. The empirical zero-one loss for each hy- pothesis then defined as C(hy)) Σ. ((()) * ga.. In Appendix A, we show that optimizing for the zero-one loss arg mingsjjN C(hy) is equivalent to equa- tion 1. Namely, with ties broken similar to above, j* arg minosieN ((hg).
Version Space Reduction. The VReduce algorithm (Algo- rithm 1) implements a version space approach that maintains an interval [7, JJ representing plausible optimal thresholds. The key principle is that if we observe labeled examples 20() with i / mostly belong to class 1, and examples ziz) with 2 J mostly belong to class 2, then the optimal threshold j with high likelihood will lie within [].
Multi-Class Classification. To generalize the above prob- lem formulation to multi-class classification, we follow a similar strategy to Zhang al. (2022). As shown in Figure 3, for each class k. we can view the problem of class-k v.s. oth- ers binary classification problem. The goal therefore becomes finding all K optimal separation thresholds, which is equivalent with solving K 1-D agnostic active learning problems. Moreover, let 5= : X + (K- denote the neural network prediction function, mapping examples to softmax scores. For each class k. we use the margin scores p. := ((xx))k max;. [p(x:)] to sort the examples and break ties by their corresponding confidence scores [px;;]].- Formally.
The algorithm proceeds iteratively by: (1) maintaining and updating the version space interval [I, based on observed labels, (2) sampling unlabeled examples uniformly within this interval to maximize information gain, (3) shrinking the version space based on empirical loss estimates that account for the noisy observations, and (4) repeating until the labeling budget is exhausted.
Theoretical Guarantees. The VReduce algorithm inherits robust theoretical properties from the agnostic active leamn ing literature, achieving near-minimax and instance-optimal sample complexity bounds (Dasgupta et al., 2007; Hanneke et al., 2014). Unlike bisection-based methods that fail un- der label corruption, the disagreement- based framework (Balcan et al., 2006) provides natural robustness with high
(o)) 5.... :NNy; sorted permutation of (D)))=)> (ci = p(ax))+ 2 (((++1)))).
Note that sorting by margin scores equivalent to sorting
5

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Algorithm VReduce: Version Space Reduction for Threshold Learning
DImension REduction for aCTivve Learning under Imbalance and Label Noise
Algorithm 2 DIRECT:
Input: Labeled set L, budget b, class of inter- est h, parallel batch size Bparalel- sorted examples (algn Miay ( (note Vig of unlabeled examples are hidden to the learner).
Input: Pool X, #Rounds T, retraining batch size Buain-
number of parallel annotations Bparalle.
Initialize: Uniformly sample B elements from X to form Lo. Let Uo + X Lo
Initialize: Version space [] as the shortest interval such that: Vi < 1 with zi(() E L: y(a) = k, and Vj 2 J with (()) E L: M63 + k.
for t = L.... - do
Train neural network on 1₃-1 and obtain ft-1- Find optimal separation thresholds
Number of iterations m 4 b/ Bpurallet Shrinking factor C c+ (J-m) for t. 1,..., do
Initialize labeled set L3 t L1-1 and budget per class 6- b-Busann20
for l in RandPerml ((1, [1....,K] do
Sample Bparatlel unlabeled examples uniformly from {x (.())....., (ز) and add to L.
Sort margin scores 0- = Gfo S oii S .... S L(N)
based on equation 2.
Compute empirical loss: (s)
Let (e)) V() denote the example and label corre-
Ersomcnee 186r)
k}
+
sponding di.
En
EL 1 1B(r)) = k].
Identify threshold for class k: Le VReduce(L, b, k. Bparattel (zfs) Miyy Kis J. Ji=1).
Update version space:
[] + arg (. D)/e max m (1),
end for
end for
Annotate examples around the identified threshold
Return: Updated labeled set L.
Compute budget per class b t- (Bunin - [L,])/K K.
for & in RandPerm( ((1, [l.... K}) do
Estimate separation threshold (break ties by choos- ing the index closest to ))
probability guarantees regardless of the underlying data dis- tribution or noise model. Building on the ACED framework (Katz-Samuels et al., 2021), our algorithm extends these classical guarantees to practical batch settings through the Bparaliel parameter while preserving all theoretical proper- ties, making it suitable for real-world annotation scenarios with multiple parallel annotators.
3 + arg max; (HHb)) = k I(t) E Le and <
iil - ((y # k: T(t) E L, and S j)))
Annotate i unlabeled examples with sorted indices
closest to 3 and insert to Lt. end for
end for
Return: Train final classifier fr based on Lr.
4.3. Algorithm
annotated in parallel. We note that, in practice, the num- ber of examples collected before retraining is usually far greater than the number of annotators annotating in parallel, i.e., Bparatlel < Buain- Lastly, as will be discussed in Sec- tion 6, our algorithm can also be modified for asynchronous labeling.
We are now ready to state our algorithm DIRECT as shown in Algorithm 2. Each round of DIRECT follows two- phased procedure, where the first phase aims to identify the optimal separation threshold for each class using the agnostic active learning approach described above. The sec- ond phase then annotates examples closest to the estimated optimal separation thresholds for each class. We spend half each round's budget for both phases.
Theoretical Comparison with GALAXY. As mentioned in Section 3.2, GALAXY's graph-based approach aims to identify all cuts and sample examples around all of them equally. On the other hand, DIRECT aims to identify only the separation threshold and sample around it, which is su- perior as we have argued before and shown in our results. We now present a more theoretical comparison. As we show in Appendix A, the graph-based approach in GALAXY will identify and annotate around at least one more cut in addi- tion to the optimal separation threshold, with probability at least 1 exp(-bbloge (/)) 1/2). Here, b is the budget of single round of annotation and is the label noise ratio (see Appendix A for more details). This implies, when the budget is large, GALAXY will likely annotate around unnecessary cuts. This is in contrast with the agnostic active
During the first phase, to identify the optimal separation threshold for all classes, we loop over each class & and run the agnostic active learning procedure VReduce for the corresponding 1-D class-k v.s. rest reduction. The second phase of DIRECT simply annotates examples closest to each optimal separation threshold, aiming to annotate class-balanced and uncertain examples.
To address batch labeling, we let Bizain denote the number of examples the algorithm collects before the neural network is retrained. In practice, this number is usually determined by the constraints of computational training cost. On the other hand, we let Bparatle denote the number of examples
6

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Bansiom
Bardem
SP9LAR (PLOP))
LA (PLOM)
0.95
BAII
BADGE
BADGE
Nost Liceyy Frellive
Nout Lidy Tox the
Cueter Nargh
0.75
Ouster Margi
Carfilena Sampling
Bansom
BASE
GALAXY Paoas
SAMI AR (FL0M))
dentidence Samptng
DIRECT (8uone 5
0.03
RAIT
GALAXY (Saans
BADDe
DIsECT Hyuens 1)
DI (yoai +3)
0.25
0.80
Most Likyy hoithe
Margin
0.45
GALAXY
1003
2002
3000 Labes
4200
5000
0:35
3000
7,000
3200
4000
5003
0.70
3000
2:00
2000
4003
5005
Numbar Labes
Number Lobos
(a) Imbalanced CIFAR-IO, three classes
(h) Imbalanced CIFAR-100, ten classes
(c) Imbalanced SVHN, two classes
0.70
Randam
SHBLAR (FL0M)
Mac Aeciin Marye
0.65
BADGE
Margin Sampling
1400
BAT
BADGB
CORESET
Mus: Uisy "eciGre
Eurce sardding
Taitiing
0.60
GAL AXY
1000
BASI
Custer Nargin
676
0.55
DIRECT(BB
201
Homber Labbiied
GA AXY Panmer
Cardttece Sampirg
6.00
DIECT (Rpase 50
0.50
672
0.45
2000
01400
3300
Sumber Laneb
3.90
2003
5000
1000/0
Number abbels
150000
200000
25000
302000
1000
2200
Number Labex
2020
4000
5000
(d) PathMNIST, two classes
FMoW, Balanced Pool Accuracy
(1) Imbalanced SVHIN two classes, # of mi- nority labeled examples
Figure 4: Performance comparison of DIRECT against other baselines algorithms in the noiseless but imbalanced setting. (a)-(d) are balanced accuracy ResNet-18 experiments while (c) shows experiment under the LabelBench framework. Bparattel indicates the number of parallel annotations as mentioned in Section 4.3. B Pparallet = 1 is equivalent with sychornous labeling. Results are averaged over four trials and the shaded areas represent standard errors around the mean.
learning approach we take in DIRECT, where as shown by Katz-Samuels et al. (2021), the probability of misidentify- ing the optimal separation threshold decays exponentially w.r.t. budget In other words, with large budget b, with high likelihood, DIRECT will focus its annotation around the optimal separation threshold. Lastly, time complexity analysis in Appendix C shows DIRECT's superior speed compared to BADGE and GALAXY.
DIRECT on various levels of label noises. While we highlight many results in this section, see Appendix E for complete results. Our implementation is publicly available at: https://github. http:///gg..uuub.coo//eeiiiiccca wttp://ccc//cicceae///t//eooooce Labe habb.l//Baccchh/b.ooo///aaaaalaa Tranenttrinnnnnn st strategy/strateey_iing
py
Experiment Setups. Our experiments utilize 14 imbalanced datasets derived from popular computer vision datasets. For the ResNet experiments, we utilize imbalanced and/or long-tail versions of CIFAR-10, CIFAR- 100 (Krizhevsky et al., 2009), SVHN (Netzer al., 2011) and PathM- NIST (Yang et al., 2021) datasets. For the LabelBench experiments, we utilize the FMoW (Christie et al., 2018), iWildcam (Beery et al., 2021), iNaturalist ( (Van Horn et al., 2018) and ImageNet-LT (Deng et al., 2009) datasets. We refer the readers to Appendix D for more details on our experiment setups.
5. Experiments
We conduct experiments under two primary setups:
1. Supervised fine-tuning of ResNet-18 18 on imbalanced datasets similar to Zhang et al. (2022).
2. Fine-tuning large pretrained model (CLIP ViT-B32) with semi-supervised training strategies under the LabelBench framework (Zhang et al., 2024a).
For both evaluation setups, we first evaluate the per- formance of DIRECT under the noiseless setting in Section 5. showing its superior label-efficiency and ability to accommodate batch labeling. In Section 5.2, we evaluate deep active learning algorithms under a novel setting with both class imbalance and noisy labels. Under this setting, we also include an ablation study of the performance of
5.1. Experiments under Imbalance, without Label Noise
For the noiseless experiment on ResNet-18, 18, we compare against nine baselines: GALAXY (Zhang et al., 2022), SIM- ILAR (Kothawade al., 2021), BADGE (Ash et al., 2019). BASE (Emam et al., 2021), BAIT (Ash et al., 2021), Cluster Margin (Citovsky et al., 2021), Confidence Sampling (Set-
7

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Random RADGE
DSenced Accuracy
0.75
0.80
0.5
Mangin
GALAXY(B
0.70
DIRECT(P 1503
Random
0.4
0.60
ARMILAR (FLOMI)
BADGE
Sandam
9-000
Balunal
Confidence Sampling
GALAXY
GMAAYY kng
0.50
DIRECT
0.72
0.2
2000
4000
Number of Labels
6000
8000
20000
0.700
1300
2020
Mumber
3003
4000
5000
50.00
10300
Number of Label
10000
20000
25000
5000
(a) CIFAR-1011 claasses 15% label noise (h) Imbalanced SVHN, two classes, 10% (c) iWildeam Balanced Pool Accuracy, 10% label noise
label noise
Figure 5: Performance of DIRECT against baseline algorithms under label noise. (a)-(b) are balanced accuracy ResNet- 18 experiments while (c) shows results under the LabelBench framework. Results are averaged over four trials and the shaded areas represent standard errors around the mean.
2.25
Bardom
SMLAR (TLOM)
Carfilena Sampting
BADGE
0.61
GAJAXY Marmao
11
2.85
Random
DIRECT (Rpaaee 53
0.05
SMLAR ITLOND
2.50
SAIT
BADGE
Seterce
0.65
2.35
0.62
BAGE
MADGE
Cont Contidence Samplng
denfidence Samplro
GALARY (8pr
GALAXY 11
D-RECT
1002
2006
3000
4200
$000
1000
2000
3300
4000
5003
3000
2:00
3000
4003
5000
(a) Imbalanced CIFAR- 100, two classes, no (b) Imbalanced CIFAR-100, two classes, Imbalanced CIFAR- 100, two classes, label noise
10% label noise
15% label noise
Figure 6: Performance of DIRECT against baseline algorithms under different levels of label noise. Results are averaged over four trials and the shaded areas represent standard errors around the mean.
tles, 2009), Most Likely Positive (Jiang et al., 2018; War- muth et al., 2001; 2003) and Random Sampling. We briefly distinguish the algorithms into two categories. particular, both SIMILAR and Most Likely Positive annotate examples that are similar to existing labeled minority examples, thus can significantly annotate a large quantity of minority ex- amples. The rest of the algorithms primarily optimizes for different notions of informativeness such as diversity and uncertainty.
blass-balancedness, we consistently observe that both Most Likely Positive and SIMILAR annotating greater number of minority class examples, but significantly underperforms in terms of balanced accuracy (an example showin in Fig- ure 4())) While Zhang et al. (2022) has already observed this phenomenon, we can further see that DIRECT collects slightly less minority class examples than GALAXY, but out- performs in terms of balanced accuracy. While it is crucial to optimize mass-balancedness for better model performance, we see that both extremes of annotating too few and too many minority examples could lead to worse generalization performances. When too few examples are from minority class, the performance of the minority classes could be sig- nificantly hindered. When optimized to annotate as many examples from minority class as possible, the algorithm has to tradeoff annotating informative examples to examples is more certain to be in the minority class. Together, this suggests intricate balance between the objectives, generalization performance and muns-balaaceddess.
For the LabelBench experiments, due the large dataset and model embedding sizes, we choose subset of the algo- rithms that are computationally efficient and among top per- formers in the ResNet-18 18 results, including BADGE, Mar- gin Sampling, CORESET and GALAXY. As highlighted in Figures ((a) and (d). DIRECT consistently and signif- icantly outperforms existing algorithms on the ResNet- 18 experiments. In Figures I(c) and 4(e), we demonstrate the increased label-efficiency is also consistently shown in the LabelBench experiments. Compared to random sampling, DIRECT can save more than 80% of the annotation cost on imbalanced SVHN experiment of Figure 4(c). In terms of
We would also like to highlight the ability to handle batch labeling. Across our experiments, we see DIRECT out-
8

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
0.85
DIRECT (Gur Algorithm)
Margin Sampling
0.770.780.75
Random Sampling
0.75
9.75
0.75
0.73
0.73
0.74
0.70
0.70
0.09
Accuracy
0.65
0.62
0.60
0.57
0.55
0.1
0.460.48
2.45
0.45
0.40
1100
101-200
201-300
301-400
401-500
501-600
601 701
701-800
801 900
901 -1001000
Class Range (Most to Least Frequent)
Figure 7: Performance of different active learning algorithm across different classes for the ImageNet-LT dataset.
performs with different amounts of parallel annotation (Bpanalel 1, 5 and 20), indicating its general effective- ness. This is in comparison to the synchoronous nature of GALAXY, where is always using Bparallel = 1. On Figures I(a) and 5(a), we see that DIRECT outperforms GALAXY with synchronous labeling. Furthermore, these experiments we also see using Bparallel only affects al- gorithm performances minimally for DIRECT.
with high label noise of 20%, observe in Figure 1(b) that existing algorithms underperform random sampling. In con- trast, DIRECT significantly outperforms random sampling, saving more than 60% of the annotation cost.
5.3. Qualitative Analysis
The ImageNet-LT dataset is constructed with class frequen- cies that gradually decrease according to class index. In Fig- ure 7, we organize classes into bins ordered from most fre- quent to least frequent. The results show that DIRECT sig- nificantly outperforms baseline algorithms on less frequent classes (indices 301-1000), which accounts for DIRECT's superior overall performance despite modest accuracy re- ductions on more frequent classes. This finding aligns with our balancedness analysis, where DIRECT demonstrates improved labeling samples from rare classes.
5.2. Experiments under Imbalance and Label Noise
We conduct novel sets of experiments under both class im- balance and label noise. Here, for both ResNet-18 and LabelBench experiments, we evaluate against all of the algorithms that performed well under the imbalance but noiseless setting above. For all of our experiments, we in- troduce a fixed percentage of label noise, where the given fraction of the examples' labels are corrupted to different class uniformly random. For most of our experiments observe again that DIRECT consistently improves over all baselines in- cluding GALAXY. The results are consistent on 18 and Labh setups, and with different Bpuraltel values, showing DIRECT's robustness under label noise.
6. Conclusion and Future Work
with 10% label noise shown in Figure
In this paper, we conducted the first study of deep active learning under both class imbalance and label noise. We proposed an algorithm DIRECT that significantly and con- sistently outperforms existing literature. In this work, we also addressed the batch sampling problem of Zhang et al. (2022), by annotating multiple examples in parallel. Study- ing asynchronous labeling could be natural extension of our work. A potential solution is to utilize asynchronous variant of one-dimensional active learning algorithm. In addition, one can further batch the labeling process across different classes to further accommodate an even larger number of parallel annotators.
Different Levels Label Noise As shown in Figures 6(a)- (c) and (bb), we observe the results on imbalanced CIFAR- 100 with two classes across numerous levels of label noise, with 0%, 10%, 15% and 20% respectively. In fact, the noise- less experiment in Figure 6(a) is the only setting DIRECT slightly underperforms GALAXY in terms of generaliza- tion accuracy. However, we see DIRECT becomes more label-efficient under label noise. also worth noting that

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Impact Statement
Beery, S., Agarwal, A., Cole, E., and Birodkar, V. The iwildcam 2021 competition dataset. arXiv preprint arXiv:2105.03494, 2021.
In the rapidly evolving landscape of machine learning, the efficacy of active learning in addressing data imbalance and label noise significant stride towards more robust and equitable AI systems. This research explores how active learning can effectively mitigate the challenges posed by imbalanced datasets and erroncous labels, prevalent in real- world scenarios.
Beluch, W. H., Genewein, T., Nürnberger, A., and Köhler, J. The power of ensembles for active learning in image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9368-9377, 2018.
The positive impacts of this research are multifaceted. It enhances the accessibility and utility of machine learning in domains where data imbalance is common challenge, such as healthcare, finance, and social media analytics. By im- proving fass-balancednes,, in annotated sets, models trained on these datasets are less biased and more representative of real-world distributions, leading to fairer and more accurate outcomes. Additionally, this research contributes to reduc- ing the time and cost associated with data annotation, which particularly beneficial in fields where expert annotation is expensive scarce.
Cai, Active learning for imbalanced data: The difficulty and proportions of class matter. Wireless Communications and Mobile Computing, 2022, 2022.
Chen, Y., Sankararaman, K., Lazaric, A., Pirotta, M., Karamshuk, D., Wang, Q., Mandyam, K., Wang, S., and Fang, H. Improved adaptive algorithm for scal- able active learning with weak labeler. arXiv preprint arXiv:2211.00 1.02233, 2022.
Christie, G., Fendley, N., Wilson, J., and Mukherjee, Functional map of the world. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6172-6180, 2018.
However, if not carefully implemented, active learning strategies could inadvertently introduce new biases or am- plify existing ones, particularly in scenarios where the initial data severely imbalanced or contains deeply ingrained bi- ases. Furthermore, the advanced nature of these techniques may widen the gap between organizations with access to state-of-the-ard technology and those without, potentially ex- acerbating existing inequalities in technology deployment.
Citovsky, G., DeSalvo, G., Gentile, C., Karydas, L., Ra- jagopalan, A., Rostamizadeh, A., and Kumar, S. Batch active learning at scale. Advances in Neural Information Processing Systems, 14:11933--1944 2021.
Coleman, C., Chou, E., Katz-Samuels, J., Culatana, S., Bailis, P., Berg, A. C., Nowak, R., Sumbaly, R., Zaharia, M., and Yalniz, I. Z. Similarity search for efficient ac- tive learning and search of rare concepts. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 36, pp. 6402-6410, 2022.
Acknowledgements
This work has been supported part by NSF Award 2112471.
References
Dasgupta, S., Hsu, D. J., and Monteleoni, C. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
Aggarwal, U.. Popescu, A., and Hudelot, C. Active learning for imbalanced datasets. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision, pp. 2020.
Deng, J., Dong, W., Socher, R., Li, L.-J,, Li, K., and Fei-Fei, Imagenet: A large-scale hierarchical image database. In 2009 IEFE conference on computer vision and pattern recognition, pp. 248-252 Icee, 2009.
Ash, J., Goel, S., Krishnamurthy, A., and Kakade, S. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34: 8927-8939, 2021.
Ducoffe, M. and Precioso, F. Adversarial active learning for deep networks: a margin based approach. arXiv preprint /AXiv:800.00984. 2018
Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. Deep batch active learning by di- verse, uncertain gradient lower bounds. arXiv preprint (906:00900.3777 2019.
Elenter, J., NaderiAlizadeh, N., and Ribeiro, A. A la- grangian duality approach to active learning. arXiv preprint arXiv:2202.041088 2022.
Emam, Z. A. S., Chu, H.-M., Chiang, P.-Y,, Czaja, W., Leap- man, R., Goldblum, M., and Goldstein, T. Active learning at the imagenet scale. arXiv preprint 2rXiv22111.12880. 2021.
Balcan, M.-F., Beygelzime,, A., and Langford, J. Agnostic active learning. In Proceedings of the 23rd international conference on Machine learning, pp. 65-72, 2006.
10

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Gal, Y., Islam, R., and Ghahramani, Z. Deep bayesian active learning with image data. In International Conference on Machine Learning, pp. 1183-1192. PMLR, 2017.
Kremer, J., Steenstrup Pedersen, K., and Igel, C. Active learning with support vector machines. Wiley Interdisci- plinary Reviews: Data Mining and Knowledge Discovery, 4(4):313-33) 326, 2014.
Geifman, Y. and EI- Yaniv, R. Deep active learning over the long tail. arXiv preprint arXiv: 1et::111100000 1,00941, 2017.
Krizhevsky, A., Hinton, G., al. Learning multiple layers of features from tiny images. 2009.
Hanneke, S. et al. Theory of disagreement- based active learning. Foundations and Trends& Machine Learning, 7(2-3):131-309 2014.
Lin, C., Mausam, M., and Weld, D. Re-active learning: Active learning with relabeling. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Mohamadi, M. A., Bae, W., and Sutherland, D. J. Making look-ahead active learning strategies feasible with neural tangent kernels. arXiv preprint arXiv:2206.1235:
2022.
Huang. T.-K., Agarwal, A., Hsu, D. J., Langford, J., and Schapire, R. E. Efficient and parsimonious agnostic active learning. Advances Neural Information Processing Systems, 28, 2015.
Müller, R., Kornblith, S., and Hinton, G. E. When does label smoothing help? Advances in neural information processing systems, 32, 2019.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y. Reading digits in natural images with unsupervised feature learning. 2011.
Jain, L. and Jamieson, K. G. A new perspective on pool- based active classification and false-discovery control. Advances in Neural Information Processing Systems, 32, 2019.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., al. Learning transferable visual models from natural language supervision. In International conference machine learning, pp. 8748-888 8763. PMLR, 2021.
Jiang, S.. Malkomes, G., Abbott, M., Moseley. B., and Garnett, R. Efficient nonmyopic batch active search. In 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), 2018
Sener, O. and Savarese, Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 1708.0089, 2017.
Jin, Q. Yuan, M., Wang, H., Wang, M., and Song, Z. Deep active learning models for imbalanced image classifica- tion. Knowledge-Baud Baaeed Systems, 257: 257:109811 109817, 2022.
Settles, Active learning literature survey. 2009.
Katz-Samuels, J., Jain, L., Jamieson, K. G., et al. An em- pirical process approach to the union bound: Practical al- gorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33:10371- 10382, 2020.
Soltani, N., Zhang, J., Salehi, B., Roy, D., Nowak, R., and Chowdhury, K. Learning from the best: Active learning for wireless communications. arXiv preprint w0X.:2240..04866, 2024.
Tong, S. and Koller, D. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45-66 2001.
Katz-Samuels, J., Zhang, J., Jain, I.., and Jamieson, K. Im- proved algorithms for agnostic pool-based active classifi- cation. In International Conference on Machine Learning, pp. 3334-5344. PMLR, 2021.
Van Horn, G., Mac Aodha, O., Song, Y., Cui, Y.. Sun, C., Shepard, A., Adam, H., Perona, P., and Belongie, S. The inaturalist species classification and detection dataset. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 8769-8778. 2018
Khosla, S., Whye, C. K., Ash, T., Zhang, C., Kawaguchi, K., and Lamb, A. Neural active learning on heteroskedas- tic distributions. arXiv preprini urXiv:2211.00922 2022.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Wang. H., Huang, W., Margenot, A., Tong, H., and He. J.
Deep active learning by leveraging training dynamics. arXiv preprint arXiv:2110.08611 2021.
Kothawade, S. Beck, N., Killamsetty, K., and Iyer, R. Simi- lar: Submodular information measures based active leamn ing in realistic scenarios. Advances in Neural Information Processing Systems, 34:1 18885-18697, 2021.
Warmuth, M. K., Rätsch, G., Mathieson, M., Liao, J., and Lemmen, C. Active learning in the drug discovery pro- cess. In NIPS, pp. 1456, 2001.

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Warmuth, M. K., Liao, J., Rätsch, G., Mathieson, M., Putta, S., and Lemmen, C. Active learning with support vector machines in the drug discovery process. Journal of chem- ical information and computer sciences, 43(2):667-673, 2003.
Xie, T., Zhang. J., Bai, H., and Nowak, R. Deep active learn- ing in the open world. arXiv preprint arXiv:2411.0633 2024.
Yang, J., Shi, R., Wei, D., Liu, Z., Zhao, L., Ke, B., Plister, H., and Ni, B. Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification. arXiv preprint arXiv: / 10. /4795, 2021.
Younesian, T., Zhao, Z., Ghiassi, A., Birke, R., and Chen, L. Y. Qactor: Active learning on noisy labels. In Asian Conference Machine Learning, pp. 548-548833 PMLR, 2021.
Zhang, B.. Wang, Hou, W. Wu, H., Wang, J., Oku- mura, M., and Shinozaki, T. Flexmatch: Boosting semi- supervised learning with eurriculum pseudo labeling. Ad- vances in Neural Information Processing Systems, 34: 18408-18419, 2021.
Zhang, C. and Chaudhuri, Active learning from weak and strong labelers. Advances in Neural Information Processing Systems, 28, 2015.
Zhang. J., Ratz-Samuels, J., and Nowak, R. Galaxy: Graph- based active learning at the extreme. arXiv preprint mrxiv:2202.01400) 2022.
Zhang J., Chen, Y., Canal, G., Das, A. M., Bhatt, G., Mussmann, S., Zhu, Y., Bilmes, J., Du, S. S., Jamieson, K., al. Labelbench: comprehensive framework for benchmarking adaptive label-efficient learning. Journal of Data-centric Machine Learning Research, 2024a.
Zhang, J., Shao, S., Verma, S., and Nowak, Algorithm se- lection for deep active learning with imbalanced datasets. Advances in Neural Information Processing Systems, 36, 2024b.
12

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
A. Equivalent Objective
Lemma A.1. The agnostic active learning reduction is equivalentty the optimal separation threshold. Namely, arg min C(hy) = arg max (HUC)) = =1: -K = 2: ::::::==::1::::: ii:iss5))
N ((1)(1()) + v(0) ) we can expand the loss as 1 ifq S (6)) and [(h,) =
Proof. Recall the definitions: h1(9))
2 i 9())
follows
arg min C(hz) arg min
[by (q61) + v()
N
= arg min N
(h)(( = yO)
arg max
1 (hy(((0) = )O)
N
= arg max j
Σ 1 (v()) = =1)) +
Σ
(u(o) 23
i=j+1
N
N
= arg max
1 18(00 = =13) +
Σ
11m00 = 23
- Σ
Hu(c = 2}
j
1=1+1
arg max
(1(2)) 1} - 1(1 21)
B. Theoretical Analysis
In this section, we analyze the performance of GALAXY under random label noise and show the probability of identifying and sampling around additional cuts increases as more examples are labeled. This is in contrast to the DIRECT's agnostic active learning approach, where the probability of identifying and sampling around only the optimal separation threshold decays exponentially in the number of labeling budget.
Specifically, under the binary classification scenario, one is given a sorted list of N examples {ar()) | with ground truth labels v(1) = M(2)
V(N., and ((N++1) = = ((N)+Na) = 2, where N1 + N2 = N. Under uniform i.i.d. label N. where P(y() + v(n) = 17. In other words, the noise with noise ratio 77 > the observed labels are denoted as { observed label is flipped with probability 1).
Theorem B.I. Given budget of > 2 log N, let M, be the random variable denoting number of identified cuts in addition to the optimal separation threshold by one round of GALAXY. We must have P(M, 2 1) 2 1 exp(-bb bogg /22). implying GALAXY samples around at least one more cut in addition to the optimal separation threshold with high probability.
Proof. In the perfect scenario where GALAXY does not receive any corrupted labels, it would use log N budget with bisection to find the optimal separation threshold and annotate around it. However, within the first & annotations, whenever GALAXY receives corrupted label, it will identify a cut in addition to the optimal separation threshold, i.e., M, 2 1. Therefore, the probability of M, is greater than the probability of receiving at least one corrupted labels in the first annotations. With simple probability bound, we can show that
1 1- ( 122).
P(M, 2 1)> 1 1- (1 - 6/2 = 1 exp(blog(1 - m)) = 1 - exp( hop(-bley bogg(
13

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Imb Ratio min, Ny
Name
K
N
maxg N
Imb CIFAR-10
50000
.1111
Imb CIFAR-10
3
50000
.150
Imb CIFAR-I0K 100
2
50000
.0101
Imb CIFAR-
50000
.0102
Imb CIFAR-I0
50000
.0110
Imb SVHN
73257
.0724
Imb SVHN
3
54448
.2466
PathMNIST
2
89996
.1166
FMoW
62
76863
.0049
iWildCam
14
129809
4.57 4.57-10-
Table 1: Dataset settings for our experiments. N denotes the total number of examples in our dataset. is the class imbalance ratio defined in Section 3.1.
As the theorem suggests, when is large, GALAXY will identify and annotate around at least one additional cut with high probability.
C. Time Complexity
The computation complexity for each batch of DIRECT is O(KN log(N) + N) for data selection plus the training and inference costs of the neural network. O(KN OogNlog(NN) comes from sorting examples by their margin scores for each class and O N) the cost for running Algorithm 2 for O( iterations. Each iteration of Algorithm only costs ((N) time we can efficiently solve the objective by cumulative sums. We note that the cost associated with neural network training and inference always the dominating factor.
For comparisons, BADGE has time complexity O(Buain + D)), significantly more expensive than DIRECT, with D denotes the dimensionality of the penultimate layer features. In addition, GALAXY has computational complexity of O(KN log(N)) + Biaain K N, also more expensive than DIRECT. In all of our experiments, both BADGE and GALAXY indeed is slower than DIRECT. We further note that the time complexity factor of K in DIRECT can be easily parallelized by conducting the K sorting procedures on different CPU cores.
Below, we also provide a comprehensive list of computational complexity of different algorithms we consider in our implementation: As for data selection algorithms, let K be the number of classes, N be the pool size and Buain be the batch size, D be the penultimate layer embedding dimension and T be the number of batches. Below, we detail the computation cost of data selection of each algorithm we consider.
DIRECT: O(T(KN N log N + Birain N)).
GALAXY: ((T(KN N log N + Btrain KN)
BADGE: OT N (K + D))
Margin sampling/most likely positive/confiddnce sampling: O(TKN)
Coreset: O(T Btrain N D)
SIMILAR: O(TBrrain N D)
Cluster margin: O log N + TTNN(KKK + Nog
BASE: (T + Birain))
Overall, our experiments are conducted on NVIDIA 3090 GPUs. Each trial of the ResNet-18 experiment takes less than two hours while each trial of the LabelBench experiments takes roughly 12 hours.
D. Experiment Setup
ResNet-18 Experiments. ResNet-18 with passive training has been the standard evaluation in existing deep active literature (Ash et al., 2019; Zhang et al., 2022). Our experiment setup utilizes the CIFAR-10, CIFAR-100 (Krizhevsky et al., 2009), SVHN (Netzer et al., 2011) and PathMNIST (Yang et al., 2021) image classification datasets. The original forms of these datasets are roughly balanced across 10 or 100 classes. We construct an extremely imbalanced dataset by grouping a
14

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
large number of classes into majority class. For example, given balanced dataset above with M classes. We generate imbalanced dataset with K classes (K .) by the first K classes from the original dataset and combining the rest of the classes K, .... M into single majority class K. Imbalance ratios are shown in Table 1. In addition, also utilize the standard 1OLT and CIFAR- 100LT variants in our experiments for noisy label setting.
For neural network training, we utilize the standard passive training on labeled examples with cross entropy loss and Adam optimizer (Kingma Ba, 2014). The ResNet-18 model (He et al., 2016) is pretrained on ImageNet (Deng al., 2009) from the PyTorch library. To address data imbalance, for all algorithms, frequency of the number of labeled examples in each class. For experiments with label noise, we further add 10% label smoothing during training (Müller et al., 2019) for all algorithms.
utilize a reweighted cross entropy loss by the inverse
LabelBench Experiments. Proposed by Zhang et al. (2024a), LabelBench evaluates active learning performance in more comprehensive framework. Here, we fine-tune the large pretrained model from CLIP's ViT-B32 model (Radford et al., 2021). The framework also utilizes semi supervipe learning method FlexMatch (Zhang et al., 2021) to further leverage the unlabeled examples in pool for training. We conduct experiments on the two imbalanced datasets in LabelBench, with FMoW (Christic al., 2018) and iWildcam (Beery al., 2021). Similar to the ResNet-18 experiments, for all algorithms, we use 10% label smoothing in the loss function to improve training under label noise. We did find FlexMatch perform poorly under the combination of imbalance and label noise, used the passive training method for label noise experiments.
E. All Results
E.1. Noiseless Results under Imbalance
Random
2000
Random
0.86
SIMILAR (FLOMI)
Number of Labeled Rare: Class Examples
SIMILAR (FLOMI)
BAIT
1750
BAIT
0.84
BADGE
BADGE
Balanced Accuracy
0.82
Most Likely Positive
1500
Most Likely Positive
Cluster Margin
Cluster Margin
0.80
BASE
BASE
Confidence Sampling
1000
Confidence Sampling
0.78
GALAXY (6 paraali 1)
GALAXY (Byunate 1)
DIRECT porata
750
DIRECT (Bpvave
DIRECT (a 5)
DIRECT (Bumaate'
500
0.74
250
0.72
1000
2000
3000
4000
1000
2000
3000
4000
5000
Number of Labels
Number of Labels
Figure 8: Imbalanced CIFAR-10, classes
15

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
2500
Random
Random
SIMILAR (FLOMI)
Number Labeled Ranc Class Examples
SIMILAR (FLOMI)
0.80
BAIT
BAIT
2000
BADGE
BADGE
Accuracy
Most Likely Positive
Most Likely Positive
0.75
Cluster Margin
Cluster Margin
1500
BASE
Confidence Sampling
Confidence Sampling
GALAXY perakee
GALAXY ppunt
0.70
1000
DIRECT parate 1)
DIRECT (Bporate 1)
DIRECT parat
DIRECT (8puratel 5)
0.65
500
0.60
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Labels
Figure 9: Imbalanced CIFAR-10, three classes
0.95
Random
Number Labeled Rare Class Examples
(FLOMI)
400
0.90
BADGE
Accuracy
Likely Positive
Random
300
Cluster Margin
SIMILAR (FLOMI)
BASE
BAIT
Confidence Sampling
0.80
BADGE
200
GALAXY (8panate 11
Most Likely Positive
(Bavate
Cluster Margin
BASE
100
Confidence Sampling
0.70
GALAXY (8 parraal 1)
DIRECT (8poravo
1000
3000 Number of Labels
1000
2000
3000
4000
5000
Number Labels
Figure 10: Imbalanced CIFAR-100 100, two classes
Random
Random
SIMILAR (FLQMI)
Number of Labeled Rare Class Exampies
700
SIMILAR (FLOMI)
0.80
BAIT
BAIT
600
BADGE
BADGE
Accuracy
0.75
Most Likely Positive
Most Likely Positive
500
Cluster Margin
Cluster Margin
0.70
BASE
BASE
Confidence Sampling
Confidence Sampling
GALAXY (8 (Bparake 1)
GALAXY (B 1)
0.60
DIRECT (Baara
DIRECT (Bparate
0.55
100
0.50
1000
2000
4000
5000
1000
2000
3000
4000
5000
Number of Labels
Number of Labels
Figure 11: Imbalanced CIFAR-100, three classes.
16

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Random
Random
SIMILAR (FLOMI)
Number Labeled Rare Clacs Examples
700
SIMILAR (FLOMI)
0.35
BADGE
BADGE
Most Likely Positive
600
Most Likely Positive
Accuracy
Cluster Margin
Cluster Margin
Confidence Sampling
500
Confidence Sampling
0.30
(8parave 1)
GALAXY (aparatu 1)
DIRECT (8paaata 5)
400-
DIRECT (8paave 5]
0.25
300
200
100
0.15
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Figure 12: Imbalanced CIFAR-100, 10 classes
1600
Random
Number Labcled Rare Class Examples
0.95
(FLOMI)
1400
BADGE
Balanced Accuracy
0.90
Most Likely Positive
Random
Cluster Margin
1000
SIMILAR (FLOMI)
BASE
BAIT
800
Confidence Sampling
BADGE
GALAXY (8 1
Most Likely Positive
=8pxare=
0.80
Cluster Margin
BASE
400
Confidence Sampling
0.75
GALAXY (8 parraa 1)
200
DIRECT (0parate)
0.70
1000
1000
2000
3000
4000
5000
Number of Labels
Number of Labels
Figure 13: Imbalanced SVHN, two classes.
0.95
Random
Number of Labeled Rare Class Examples
SIMILAR (FLOMI)
BAIT
BADGE
Accuracy
0.85
Most Likely Positive
Random
Cluster Margin
0.80
SIMILAR (FLOMI))
BASE
BAIT
Confidence Sampling
BADGE
GALAXY (B 1)
Most Likely Positive
DIRECT (Bamave
Cluster Margin
0.70
BASE
500
Confidence Sampling
0.65
GALAXY (8penane 1)
DIRECT (6 (0 5)
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of Labels
Number of Labels
Figure 14: Imbalanced SVHN, three classes.
17

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Random
SIKILAR (FLQM))
Number of Labeled Rare. Class. Exemples
2000
BADGE
Most. Ukely Positive
Likely
Margin
Clustor Margin
Delenced Acarrocy
BASE
1500
BASE
Confidence Sampling
GALAXY (Bearks 1]
GALAXY
DIRECT perrrata"
0.76
0.74
0.72
500
2000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of Labels
Number Labels
Figure 15: PathMNIST, two classes.
0.60
0.70
Random
Random
Balanced Training Accuracy
BADGE
Balanced Training Accuracy
0.55
BADGE
0.65
Margin Sampling
Margin Sampling
CORESET
CORESET
0.60
GALAXY( Bparaliel
GALAXY( (Pprratle
1)
0.55
DIRECT (B paocalle
20)
DIRECT (aarraaie
20)
0.45
0.50
0.40
0.45
0.40
5000
10000
13000
20000
25000
30000
5000
10000
15000
20000
Number Labels
Number Labels
(a) FMoW Balanced Pool Accuracy
(b) iWildeam Balanced Pool Accuracy
0.95
0.225
0.200
0.90
Balanced Accuracy
Balanced Accuracy
0.175
0.85
0.150
0.80
0.125
Random
Random
0.75
BADGE
0.100
BADGE
0.70
Margin
0.075
Margin
GALAXY
GALAXY
0.65
DIRECT
0.050
DIRECT
20000
40000
60000
80000
100000
10000
20000
30000 40000 Number of Labels
50000 60000
Number Labels
(c) ImageNet-LT Balanced Pool Accuracy
(d) iNaturalist Balanced Pool Accuracy
Figure 16: LabelBench results in the noiseless setting.
18

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
E.2. Label Noise Results under Imbalance
Random
Random
SIMILAR (FLQMI)
Number of Labeled Rare Clase Exampies
SIMILAR (FLQMI)
BADGE
1500
BADGE
0.76
Confidence Sampling
Confidence Sampling
Accuracy
GALAXY (8parater 1)
GALAXY (8perate 1)
DIRECT parata
DIRECT (8paate
1000
0.72
750
0.70
250
0.66
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Number of Labels
Number of Labels
Figure 17: Imbalanced CIFAR-10, two classes, 10% label noise.
Random
Number of Labeled Rare Class Examples
2000
SIMILAR (FLOMI)
BADGE
Confidence Sampling (8
Accuracy
0.65
DIRECT (Bpwaate 5)
0.60
SIMILAR (FLOMI)
BADGE
500
0.55
Confidence Sampling
GALAXY (8
1)
DIRECT paraaa 5)
0.50
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Figure 18: Imbalanced CIFAR-10, three classes, 10% label noise.
19

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
Random
140
Random
0.74
SIMILAR (FLOMI)
Number: Labeled Rare Class Examples
SIMILAR (FLOMI)
BADGE
120
BADGE
0.72
Confidence Sampling
Confidence Sampling
Accuracy
GALAXY (8 (errall 1)
100
GALAXY (8perate 1)
DIRECT paratt 5)
DIRECT (Bpaovo 5]
60
0.66
40
0.64
20
0.62
0.60
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
Figure 19: Imbalanced CIFAR-100, two classes, 10% label noise.
0.70
Random
Number Labeled Rare Class Examples
(FLOMI)
100
BADGE
0.68
Confidence Sampling
Accuracy
GALAXY (8 ppperatel 1)
0.66
DIRECT (@panatie =
Random
SIMILAR (FLQMI)
BADGE
0.60
Confidence Sampling
20
GALAXY (Bpraa 1)
DIRECT (8porate
0.58
1000
5000
1000
2000
3000
4000
5000
Number of Labels
Number Labels
Figure 20: Imbalanced CIFAR-100, two classes, 15% label noise.
Random
Random
0.68
SIMILAR (FLQMI)
SIMILAR (FLOMI)
80
BADGE
BADGE
Confidence Samoling
Confidence Sampling
Accuracy
GALAXY (8 (8parate 1)
Number of Labeled Rare Class
GALAXY (8parate 1)
DIRECT manatt
DIRECT (8pmnatw
0.62
40
0.60
20
0.56
0
1000
2000
1000
2000
4000
5000
Number of Labels
Number of Labels
Figure 21: Imbalanced CIFAR-100, two classes, 20% label noise.
20

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
0.60
SIMILAR (FLOMI)
Random
Number Labeled Rare Class Examples
250
SIMILAR (FLOMI)
Random
BADGE
BADGE
0.58
Confidence Sampling
200
Confidence Sampling
Balanced Accuracy
0.56
GALAXY (8 perrali 1)
GALAXY (8peraee 1)
DIRECT paratt 5)
DIRECT (B = 5]
150
0.54
0.52
100
0.48
0.46
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Figure 22: Imbalanced CIFAR-100, three classes, 10% label noise.
Random
0.875
Number Labcled Rare Class Examples
800
(FLOMI)
BADGE
Confidence Sampling
Accuracy
GALAXY peperatel 1)
0.825
600
DIRECT (8punatie' =
0.800
400
0.775
Random
SIMILAR (FLQMI)
0.750
BADGE
200
Confidence Sampling
GALAXY (8 paraae 1)
DIRECT (8porato)
0.700
1000
3000
4000
1000
2000
3000
4000
5000
Number Labels
Number Labels
Figure 23: Imbalanced SVHN, two classes, 10% label noise.
Random
Number Labeled Rare: Class Examples
SIMILAR (FLQMI)
0.85
BADGE
Confidence Sampling
GALAXY paraaa 1)
0.80
DIRECT (Baxate =
0.75
1000
Random
SIMILAR (FLQMI)
BADGE
Confidence Sampling
500
GALAXY (8penetll 1)
DIRECT (0 5)
1000
4000
5000
1000
2000
3000
4000
5000
Number of Labels
Number of Labels
Figure 24: Imbalanced SVHN, three classes, 10% label noise.
21

---

Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation
0.85
Random
0.7
SIMILAR (FLQMI)
BADGE
Balanced Accuracy
Balanced Accuracy
0.75
0.6
Confidence Sampling
GALAXY
0.70
DIRECT
Random
0.65
0.5
SAMILAR (FLQMI)
0.60
BADGE
Confidence Sampling
0.4
0.55
GALAXY
0.50
DIRECT
0.3
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Number of Labels
Number of Labels
(a) CIFAR-1OLT, 10 classes, 15% label noise.
(h) CIFAR- 100LT, classes, label noise.
Random
Random
0.60
0.6
Balanced Training Accuracy
BADGE
Balanced Training Accuracy
BADGE
Margin
Margin
0.55
GALAXY (I Bjurraticc = 1)
0.5
GALAXY (Baonil 1)
DIRECT (Bpacelle
20)
DIRECT( (Bporaltes 20)
0.50
0.4
0.45
0.40
0.3
0.35
0.2
5000
10000
15000
20000
25000
30000
5000
10000
15000
20000
25000
30000
Number Labels
Number Labels
(a) FMoW Balanced Pool Accuracy
(b) iWildcam Balanced Pool Accuracy
Figure 26: LabelBench results in the 10% label noise setting.
22


Reviews:
[{"review_id": "kMWV3Lrwgt", "reviewer": "Reviewer_ZLPU", "summary": "This paper studies active learning under both class imbalance and label noise. An improved algorithm for agnostic active learning is proposed, referred to as DIRECT, which is considered an advanced version of GALAXY. Various experiments are done to validate the property of DIRECT, showing its superiority in the case of imbalance and label noise. The results are promising.\n\n## update after rebuttal", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for providing the insightful review. We address your concerns below.\n\n**Using a different scoring in Eqn. 2**\nAs you suggested, we could indeed subtract the mean instead of the max of the per-class softmax scores. The mean will simply be a constant for all examples, which makes the scoring equivalent to the confidence score. We totally agree that different scores can be used to rank the examples. For confidence scores, however, some of our initial experiments found it to be less effective than margin sampling. Notably, margin sampling has been shown to be a superior scoring function over confidence and entropy in several previous large scale benchmarking papers (e.g. [1] and [2]). We will nevertheless add a future work direction to test out different scoring methods beyond these scores.\n\n\n**Computation cost of all algorithms**\nFirst, as a reminder in our paper in Appendix C, the dominating computational cost has always been the neural network training and inference cost, which takes more than 90% of the total computational cost.\n\nAs for data selection algorithms, let $K$ be the number of classes, $N$ be the pool size and $B_{\\text{train}}$ be the batch size, $D$ be the penultimate layer embedding dimension and $T$ be the number of batches. Below, we detail the computation cost of data selection of each algorithm we consider.\n* DIRECT: $O(T(KN\\log N + B_{train}N))$.\n* GALAXY: $O(T(KN\\log N + B_{train}KN))$\n* BADGE: $O(TB_{train}N(K + D))$\n* Margin sampling/most likely positive/confidence sampling: $O(TKN)$\n* Coreset: $O(T^2B_{train}ND)$\n* SIMILAR: $O(TB_{train}ND)$\n* Cluster margin: $O(N^2\\log N + TN(K + \\log N))$\n* BASE: $O(TN(D+B_{train}))$\n\n[1] Zhang, J., Chen, Y., Canal, G., Mussmann, S., Das, A. M., Bhatt, G., ... & Nowak, R. D. (2023). Labelbench: A comprehensive framework for benchmarking adaptive label-efficient learning. arXiv preprint arXiv:2306.09910.\n\n[2] Bahri, D., Jiang, H., Schuster, T., & Rostamizadeh, A. (2022). Is margin all you need? An extensive empirical study of active learning on tabular data. arXiv preprint arXiv:2210.03822.\n\n**Sensitivity Analysis**\nThank you for the suggestion. We think our experiments already cover a wide range of imbalance ratios as shown in Table 1, even when fixing model training to be ResNet-18. As we have shown that our algorithm is superior across all of these ratios. Interestingly, when comparing the performance of random sampling, we see DIRECT saves an increasing amount of annotation costs as the dataset is more and more imbalanced. We will definitely add this observation to our paper.\n\n**More Detailed Analysis**\nThank you for the suggestion! We think this is indeed beneficial. We have to rerun some of the experiments for this. We will send over the analysis during the discussion period as soon as possible, once we get these numbers.", "claims_and_evidence": "Using object function for agnostic active learning in finding optimal separation points and annotating the unlabeled data points near these optimal separation points can improve active learning for imbalanced datasets on the tasks of agnostic active learning. The experiment results show this claim can be achieved.", "methods_and_evaluation_criteria": "The proposed algorithm is conventional and sound in active learning for assessing uncertainty. Performance is usually measured by prediction accuracies, which are well presented in the paper.", "theoretical_claims": "None", "experimental_designs_or_analyses": "The experimental design and analysis are logical and acceptable in studying active learning. I have two points, if possible, that should be supplemented. \n1) The effect of several classes and the more detailed analyses, such as the confusion matrix, showing the prediction accuracy per (major/minor) class. \n2) Sensitivity analysis from the balance to a severe imbalance in the Toy dataset. \nThese experiments can provide more insight into the proposed algorithm.", "relation_to_broader_scientific_literature": "The study is closely related to efficient learning and obtaining more representative data points, which is essential in the development of AI.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "DIRECT can be applied to the problem of agnostic active learning. When label noise exists, the advantages of DRECT can be dominant.\n The proposed algorithm's merits are small for balance with small noise. However, more robustness to the imbalance ratio can be required in some cases due to limited prior knowledge.", "other_comments_or_suggestions": "Please see the comments on Experimental Designs Or Analyses", "questions_for_authors": "Q1: Can you consider any other metrics (Eqn. 2) in the multi-class problem, such as the use of mean instead of maximum probabilities of remaining classes?  \n\nQ2: Can you provide the computational costs for all algorithms considered in the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IYV4YqXqaE", "reviewer": "Reviewer_7FVV", "summary": "## update after rebuttal\nAfter read the rebuttal and other reviews, the reviewer maintains the initial recommendation.\n\nThe paper introduces DIRECT, a new algorithm for deep active learning under class imbalance and label noise. The main contribution is a reduction of the imbalanced classification problem into a set of one-dimensional agnostic active learning problems, allowing the algorithm to identify optimal separation thresholds for each class. DIRECT selects the most uncertain examples near these thresholds for annotation, ensuring a more class-balanced and informative labeled set. The authors claim that DIRECT significantly reduces annotation costs by over 60% compared to state-of-the-art active learning methods and over 80% compared to random sampling, while maintaining robustness to label noise.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful and detailed review. We make the following clarifications to address your concerns.\n\n**Handling Label Noise by Agnostic Active Learning Algorithm**\nThe large body of classic literature of agnostic active learning studies exactly the active learning under label noise scenarios (please see [1-3] as examples). These papers study sample complexities in identifying the optimal hypothesis when annotations are noisy. DIRECT applies an instance of the agnostic active learning algorithm in finding the optimal separation threshold, which inherits the noise robustness with theoretical guarantees to be minimax and instance optimal (shown in [1] and [3]). We will include some of these discussions in our paper.\n\n[1] Balcan, M. F., ... & Langford, J. (2006, June). Agnostic active learning. ICML.\n\n[2] Dasgupta, S., ... & Monteleoni, C. (2007). A general agnostic active learning algorithm. NeurIPS.\n\n[3] Katz-Samuels, ... & Jamieson, K. (2021). Improved algorithms for agnostic pool-based active classification. ICML.\n\n**Motivation and Justification behind DIRECT**\nIn active learning, almost all algorithms are trying to balance between querying uncertain examples and diverse examples. Uncertainty can come in many forms, such as entropy score, margin score, epistemic uncertainty, or even more recent methods such as local model smoothness and influence functions. In our paper, we choose to use margin sampling as it is computationally efficient, and has been shown to perform no worse than other more advanced methods in various benchmarking efforts [4-5]. We would also note that our method can use any of the scoring methods above in place of margin score.\n\nThe other beneficial philosophy is diversity in sampling. In other words, we want to provide better data coverage in our annotation. This has been traditionally done in the representation space using penultimate layer embeddings or gradient embeddings. However, as we show in our paper, these methods (such as BADGE and Coreset) underperform DIRECT in imbalance scenarios. DIRECT focuses on class diversity, combined with uncertainty sampling, labeling a more balanced dataset of uncertain examples (i.e. ones around the optimal separation threshold).\n\nAs we demonstrated in our experiments, we include plots for both accuracy and number of minority class labels, where the latter clearly shows DIRECT labels more class-diverse sets of examples.\n\nFurthermore, to address your concerns, the optimal separation threshold is a novel proposal in our paper in the context of active learning.\n\n[4] Zhang, J., Chen, Y., ... & Nowak, R. D. (2023). Labelbench: A comprehensive framework for benchmarking adaptive label-efficient learning. DMLR Journal.\n\n[5] Bahri, D., ... & Rostamizadeh, A. (2022). Is margin all you need? An extensive empirical study of active learning on tabular data.\n\n\n**Different Learning Speed of Minority Class**\nWe think the different learning speed argument of minority class examples contributes to the motivation of DIRECT. Firstly, as DIRECT labels a more class-balanced set of examples, the learning speed of minority classes will be much faster when compared to other active learning algorithms. Furthermore, as we are adaptively labeling more examples when identifying the optimal separation threshold (Algorithm 2), we think these additional labels can significantly help in estimating the threshold. Without these additional labels, as you suggested, the decision boundary will be very inaccurate, which is exactly what the other active algorithms are experiencing. In other words, the slow learning speed of minority class results in bad estimation in uncertainty threshold (Figure 2a), and DIRECT mitigates this issue by adaptively labeling to find the optimal separation threshold, instead of relying only on the current decision boundary. \n\n\n**Additional Experiments Suggested by The Reviewer**\nWe actually do have the standard long-tail experiments in our paper, for CIFAR-10LT and CIFAR-100LT. In addition, we have conducted extra experiments under the LabelBench benchmark for ImageNet-LT (https://ibb.co/fVq3wsYJ) and iNaturalist datasets (https://ibb.co/F4fqyfdQ). In both cases, we are clearly seeding DIRECT dominating the other active learning algorithms.\n\n\n**Training Details**\nOur pretrained ResNet-18 is the standard checkpoint in the PyTorch library. As pretrained models are much more widely available, we believe finetuning of neural networks can provide us better signal for practice.\n\n\n**Notation Issues**\nIn our paper the label space is defined as $[K] = 1, 2, …, K$. In the binary case, the label space is therefore {1, 2}. In section 4.1, as we mentioned right after the [0, 1], $\\widehat{p}$ is mapping to sigmoid scores, which is different from the label space.\n\nWe just like the name DIRECT for our algorithm.\n\nThe margin score $\\widehat{p}_i^k$ is indeed confusing as it is not a probability. We will change the notation to $\\widehat{s}_i^k$ instead.", "claims_and_evidence": "Refer to other part.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand, but there are some limitations:\n1. The authors use fine-tuning of ResNet-18 on imbalanced datasets but do not explain why fine-tuning is preferred over training from scratch. Additionally, the pre-training details of the model are not provided, which could be important for reproducibility.\n2. The experiments do not include commonly used imbalanced datasets like ImageNet-LT and iNaturalist, which could provide additional validation of the algorithm's effectiveness.\n3. The paper does not use the more common method of constructing imbalanced datasets by creating a long-tailed distribution[1]. Furthermore, it is unclear whether the test datasets are imbalanced or uniformly distributed, which could affect the evaluation of the algorithm's performance.\n[1] Long-tail learning via logit adjustment", "theoretical_claims": "The theoretical claims in the paper are partially supported. The proofs in the appendix establish the equivalence between the ERM solution based on the learner's output and the \"best threshold\" on the same training set. However, this does not directly address the key claim that this solution serves as the optimal threshold for active learning on unlabeled data. The theoretical justification for the algorithm's robustness to label noise is also lacking.", "experimental_designs_or_analyses": "Yes. Refer to other part.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-situated within the broader literature on active learning and class imbalance.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The approach of combining class separation thresholds with one-dimensional active learning is innovative and provides a fresh perspective on tackling these issues.\n2. The experimental results are comprehensive and demonstrate significant improvements over existing methods.\n3. The paper is well-organized.\n\nWeaknesses\n1. The authors claim that DIRECT addresses both class imbalance and label noise issues, and the experiments include extensive evaluations under noisy settings. However, the algorithm itself does not appear to include any explicit mechanism designed to handle label noise. This is, in my opinion, the most significant weakness of the paper.\n2. Recent research has shown that majority and minority classes often have different learning speeds during training. The proposed method does not seem to account for this, which makes the estimation of thresholds for minority classes particularly challenging.\n3. There is some confusion in the notation used in the paper. In Section 4.1, the label space is described as [0,1], while in Equation 1, the labels y take values of 1 and 2. This inconsistency is puzzling and could lead to misunderstandings.\n4. The authors do not clearly explain the difference between active learning for imbalanced datasets and general active learning. Intuitively, for an imbalanced problem, labeling samples from the minority class should yield higher benefits than labeling samples from the majority class. While Definition 4.1 seems intuitively effective, the authors do not provide a detailed explanation or experimental results to demonstrate the characteristics of the samples selected by active learning.", "other_comments_or_suggestions": "Refer to weakness and questions.", "questions_for_authors": "1. Why is the method called DIRECT? Is it an abbreviation? The paper does not seem to provide an explanation for the name.\n2. ​Is the optimal separation threshold proposed in Definition 4.1 a novel contribution, or is it based on prior work?\n3. Intuitively, in multi-class classification, $\\hat{p}_i^k$ can take negative values, which seems unreasonable for probabilities.\n4. Could the authors explain the motivation behind this paper? Specifically, in active learning, what makes certain unlabeled samples more beneficial to label, and how does this principle change when the training data is imbalanced?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lPC7DJsT61", "reviewer": "Reviewer_VqkV", "summary": "The paper proposes DIRECT, an algorithm for deep active learning under the dual challenges of class imbalance and label noise. DIRECT reduces the multi-class problem to a set of one-dimensional agnostic active learning subproblems by identifying an “optimal separation threshold” for each class. Annotating examples close to these thresholds is intended to yield a more balanced and informative labeled set. DIRECT is designed to support parallel annotation while still benefiting from guarantees drawn from classic active learning results. Experiments on several imbalanced datasets (with and without label noise) claim that DIRECT saves over 60% of the annotation budget compared to state-of-the-art methods and over 80% compared to random sampling.\n\n## update after rebuttal\n\nThank you for your response. I appreciate that most of my concerns have been addressed. In light of these improvements, I will raise my rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Experimental Settings Compared to SIMILAR**\n\nOur settings actually closely mirror the settings in SIMILAR. In SIMILAR, the rare class setup is very close to the long tail distribution setups in our paper. SIMILAR’s setting reduces the number of examples in some of the classes to form rare classes. Our long tailed setup also reduces the number of examples in different classes, but following a long tail distribution. In fact, the later half of the classes receive way less examples than the largest class, effectively making them the rare classes. We chose the long tail version for experiments since this setting has been much more widely adopted in deep learning literature than the construction in SIMILAR. Also, real world data often follow long-tailed distribution in practice. In our experiments, we included CIFAR-10LT and CIFAR-100LT in the original draft. Also, as suggested by Reviewer 7FVV, we also conducted extra experiment for ImageNet-LT (https://ibb.co/fVq3wsYJ) and iNaturalist datasets (https://ibb.co/F4fqyfdQ).\n\nOur setup adopted from GALAXY, where we combined multiple classes into a single “other” or “out-of-distribution” class, which directly mirrors the out-of-distribution setting in SIMILAR. This is also known as the Open-Set classification setting, which is widely studied in deep learning literature.\n\n\n**Model Retraining Strategy**\n\nAs mentioned in our paper, we use a reweighting strategy by weighting the loss of each example by the inverse class frequencies. Reweighting is usually preferred over resampling strategies (balanced dataloader suggested by the reviewer) for deep learning as we want to reduce the repetition of examples during neural network training to avoid overfitting.\n\n**Complete Time Complexity Analysis**\n\nFirst, as a reminder in our paper in Appendix C, the dominating computational cost has always been the neural network training and inference cost, which takes more than 90% of the total computational cost.\n\nAs for data selection algorithms, let $K$ be the number of classes, $N$ be the pool size and $B_{\\text{train}}$ be the batch size, $D$ be the penultimate layer embedding dimension and $T$ be the number of batches. Below, we detail the computation cost of data selection of each algorithm we consider.\n* DIRECT: $O(T(KN\\log N + B_{train}N))$.\n* GALAXY: $O(T(KN\\log N + B_{train}KN))$\n* BADGE: $O(TB_{train}N(K + D))$\n* Margin sampling/most likely positive/confidence sampling: $O(TKN)$\n* Coreset: $O(T^2B_{train}ND)$\n* SIMILAR: $O(TB_{train}ND)$\n* Cluster margin: $O(N^2\\log N + TN(K + \\log N))$\n* BASE: $O(TN(D+B_{train}))$\n\n\n**Theoretical Guarantee**\n\nWe are not sure about what you mean by “In practice, the effect of label noise and imbalance on such outputs might be more complex.” As the agnostic active learning algorithm specifically targets the label noise scenario and the optimal 1D threshold classifier is defined to address the imbalance issue, we think our theoretical argument can exactly be applied to this 1-D reduction setting. Concretely, the agnostic active learning procedure in Algorithm 2 is exactly trying to recover the empirical risk minimizer (ERM) when freezing all of the neural network weights and only looking at the sigmoid/softmax score space. The agnostic active learning algorithm has been proven to be noise robust and can identify the ERM efficiently.\n\nTo bridge the theoretical guarantee and the effect for deep learning, in deep active learning, almost all algorithms are trying to balance between querying uncertain examples and diverse examples. In our case, we utilize the margin scores as an uncertainty measure. For diversity, we want to provide better data coverage in our annotation. This has been traditionally done in the representation space using penultimate layer embeddings or gradient embeddings. However, as we show in our paper, these methods (such as BADGE and Coreset) underperform DIRECT in imbalance scenarios. DIRECT focuses on class diversity, combined with uncertainty sampling, labeling a more balanced dataset of uncertain examples (i.e. ones around the optimal separation threshold). Our theoretical guarantee directly translates into how well we are ensuring class-balancedness of the annotated examples. With an accurate threshold, our annotation around the threshold would result in higher class-diversity in annotated examples.", "claims_and_evidence": "The paper makes strong claims regarding label efficiency improvements, robustness to label noise, and scalability via parallel annotation. Experimental results on multiple datasets generally support these claims. However, some aspects remain less clearly supported:\n\nThe absence of a direct comparison with SIMILAR—even though SIMILAR also addresses imbalanced data—is a gap that makes it difficult to assess the relative benefits of DIRECT in similar settings.", "methods_and_evaluation_criteria": "The methodological approach is innovative, particularly the reduction of the active learning problem to a one-dimensional thresholding task. The evaluation criteria—balanced accuracy and annotation cost—are appropriate for imbalanced learning scenarios. Nevertheless, The paper does not clearly explain the training procedure in each active learning iteration. For example, it is ambiguous whether a balanced data loader is used during retraining, which is crucial for mitigating imbalance during model updates.", "theoretical_claims": "The theoretical contribution builds on existing agnostic active learning results (e.g., from ACED) to justify that the probability of misidentifying the optimal threshold decays exponentially with the annotation budget. While the reduction to a one-dimensional problem is elegant, some concerns persist:\n\n(1) The proofs (provided in the appendix) assume that the behavior of deep neural network outputs is amenable to a threshold classifier analysis. In practice, the effect of label noise and imbalance on such outputs might be more complex.\n\n(2) A more detailed discussion on how the theoretical guarantees translate into deep learning contexts would strengthen the paper’s claims.", "experimental_designs_or_analyses": "The experimental section is extensive and evaluates DIRECT under various noise levels and across different architectures (ResNet-18 and CLIP ViT-B32). The experiments support the claim of improved label efficiency. However:\n\n(1) The starting point for active learning (e.g., the initialization strategy and subsequent retraining details) is not thoroughly clarified, raising questions about reproducibility.\n\n(2) As mentioned, the experiments lack a direct comparison with SIMILAR which handles imbalanced datasets effectively.", "relation_to_broader_scientific_literature": "The paper builds on and extends several strands of active learning research:\n\n(1) It leverages classic agnostic active learning theory to tackle deep learning challenges under imbalance and noise.\n(2) It directly builds on prior work such as GALAXY.\n(3) The reduction to one-dimensional threshold learning represents a creative attempt to bridge theory and practice in active learning for deep neural networks.", "essential_references_not_discussed": "The paper has cited relevant works.", "other_strengths_and_weaknesses": "Strengths:\n\n(1) aim to address a very practical and challenging scenario in real-world applications.\n\n(2) The reduction to a one-dimensional active learning problem is novel and well-motivated.\n\n(3) The ability to support parallel annotation is a significant practical advantage.\n\nWeaknesses:\n\n(1) Experiments results that connected empirical observations with theoretical understanding could help.", "other_comments_or_suggestions": "Expanding on the computational cost analysis and other limitation discussion in the main text (or summarizing key points from Appendix C) would strengthen the practical implications of the work.", "questions_for_authors": "(1) Training Strategy: How is the model retrained at each active learning iteration? Specifically, is a balanced data loader used during retraining to mitigate class imbalance, and how does this affect performance?\n\n(2) Comparison with SIMILAR: Given that SIMILER also targets imbalanced datasets, can you provide a direct experimental comparison in SIMILAR paper’s figures. or detailed discussion on how DIRECT’s performance differs in similar settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The manuscript makes a significant contribution, but it would increase the paper’s accessibility and impact, if the authors could address a few points to clarify the benefits methodology.

First, in the context of imbalanced classes, although balanced accuracy implicitly includes worst-group accuracy, it would be nice to report it explicitly in some plots as well and perhaps show ablations as a function of $\gamma$. Further, the authors should compare / use accuracy compared to simple reweighting methods or JustTrainTwice. 

Second, the reduction to agnostic active learning draws heavily on theoretical results from the ACED literature. However, readers unfamiliar with those works may not find it clear how ACED / VReduce mitigates noisy annotations (see reviewers comments). Describing it in words or even a 
self‑contained summary of ACED’s key sample‑complexity guarantees under label noise - perhaps in the preliminaries - would help to understand how DIRECT inherits and adapts these guarantees. 

Further, while the theoretical comparison shows GALAXY is likely to sample around extra cuts under noise (M_b ≥ 1), the lower bound remains somewhat loose. To bolster the theoretical claims, the authors could either tighten the bound (e.g. show M_b > 1) or present empirical evidence explicitly demonstrating how the probability of misidentifying the optimal threshold decays with the query budget b and noise rate η.
Also, this parallelization with B-parallel=5 (in experiments) really does not feel to me like a major point that should be considered the main contribution in an elevator pitch. It is a constant factor gain and it’s nice nonetheless but doesn’t change the inherently sequential nature  (the m iterations in vreduce need to be done sequentially like in GALAXY). 

Finally, Appendix E currently holds a wealth of results that could be better integrated into the main text. The authors should summarize the most important ablations—across datasets, noise levels, and model sizes—in a concise table or paragraph, highlighting where DIRECT’s advantages emerge. In particular, exploring B_parallel values beyond 1 and 5 (for example 10 or 20) in the same plot would illustrate the trade‑off between parallel annotation and sample‐complexity shrinkage factor c. 

With these revisions, I believe this work will offer both strong practical results and a clear path for readers to understand and build upon the algorithmic and theoretical innovations.

(minor point: the current way it's written, it's not clear what is actually inputted to the Vreduce algorithm:
line 279 says “unlabeled y-i hidden to learner” whereas line 236 implies y are the label corresponding to q(i) … ? - x-i is unlabeled and y-i is hidden to the learner - it doesn’t quite matter since y-i with not in L are not used, but the imprecision is a bit confusing and can mislead people who do not read carefully.)
Decision: Accept (poster)