SABAL: Sparse Approximation-based Batch Active Learning
Authors: Maohao Shen
Bowen Jiang
Jacky Y. Zhang
Oluwasanmi O Koyejo
Venue: ICLR 2022 Submitted (2022)
Keywords: active learning
Bayesian active learning
batch active learning

Abstract: We propose a novel and general framework (i.e., SABAL) that formulates batch active learning as a sparse approximation problem. SABAL aims to find a weighted subset from the unlabeled data pool such that the corresponding training loss function approximates its full data pool counterpart. We realize the general framework as a sparsity-constrained discontinuous optimization problem that explicitly balances uncertainty and representation for large-scale applications, for which we propose both greedy and iterative hard thresholding schemes. The proposed method can adapt to various settings, including both Bayesian and non-Bayesian neural networks. Numerical experiments show that that SABAL achieves state-of-the-art performance across different settings with lower computational complexity.

Under review as a conference paper at ICLR 2022
SABAL: SPARSE APPROXIMATION-BASEI BATCH ACTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We propose novel and general framework (i.e., SABAL) that formulates batch active learning as a sparse approximation problem. SABAL aims to find a weighted subset from the unlabeled data pool such that the corresponding training loss func- tion approximates its full data pool counterpart. We realize the general framework as sparsity-constringg
discontinuous optimization problem that explicitly bal- ances uncertainty and representation for large-scale applications, for which we propose both greedy and iterative hard thresholding schemes. The proposed method can adapt to various settings, including both Bayesian and non- non-Bayesi Bayesian neural networks. Numerical experiments show that that SABAL achieves state-of-the-art performance across different settings with lower computational complexity.
INTRODUCTION
Over the last decade, deep neural networks have achieved promising results in various learning tasks. However, obtaining labels for complex training dataset can be challenging in practice, as the data annotation is usually a time-consuming process that may require professional knowledge in certain applications such as in medicine (Hoi al., 2006; Shen et al., 2021). Active Learning (AL) (Settles, 2009) is commonly employed to mitigate the problem of scarce labeled data enabling efficient model training with limited annotation costs. Given partially labeled dataset, active learning ideally selects data samples that are the best for learning. Specifically, it aims to iteratively query the most helpful data to ask an oracle (human annotator) to annotate. The queried data samples can be added back to the labeled data pool, and the model is updated. This process is repeated until the model has achieved the desired performance. Intelligently identifying the most valuable data for annotation, also known the query strategy, is the key problem in active learning.
common strategy is to take the prediction uncertainty or data representation as the metric for data query. This snterraiintybbseee approach (Settles, 2009; Tong & Koller, 2001; Gal et al., 2017; Beluch et al., 2018) works by querying samples with high uncertainty, but often results in selecting correlated and redundant data samples in each batch (Kirsch et al., 2019; Ducoffe & Precioso, 2018). Representation- based approaches (Sener & Savarese, 2017; Yang & Loog, 2019) aim to select a subset of data that represents the whole unlabeled dataset, but tend be computationally expensive and sensitive to batch sizes (Ash et al., 2019; Shui et al., 2020). More recently, several hybrid approaches that try to take both uncertainty and representation into consideration have shown advantages (Ash et al., 2019; Shui et al., 2020; Sinha et al., 2019). This paper takes this hybrid view towards an active learning framework that balances the trade-off between uncertainty and representation.
Besides hybrid approaches, deep Bayesian active learning has also gained attention due to recent advances in Bayesian deep learning. Several Bayesian approaches (Gal et al., 2017; Kirsch et al., 2019) leverage model uncertainty measurements (Gal & Ghahramani, 2015; 2016) determined by Bayesian neural networks, while other works (Pinsler et al., 2019) leverage progress in Bayesian Coreset problems (Zhang et al., 2021; Huggins et al., 2016; Campbell & Broderick, 2019). However, as most existing Bayesian approaches are explicitly designed for Bayesian neural networks, another goal of this paper is to propose general method for both Bayesian and non- Ba--Bayeian models.
For deep models, is reasonable to query a large batch of data simultaneously to reduce model update frequency. The batch selection approach is known batch active learning. Taking an optimization perspective, finding the best batch is NP-hard in general. Two common approaches for such combinatorial problems the greedy and clustering approaches. Greedy algorithms

---

Under review as a conference paper at ICLR 2022
select one data sample in sequence until the batch budget is exhausted (Kirsch et al., 2019; Bıyık et al., 2019; Chen & Krause, 2013). Here, specific conditions of the acquisition function such submodularity (Nemhauser et al., 1978) required to guarantee good optimization result. Clustering algorithms regard cluster centers as their queried batch (Sener & Savarese, 2017; Ash et al., 2019), but can be computationally expensive. 'To our knowledge, except for Pinsler al. (2019) that focus on the Bayesian models, so far active learning has rarely been studied from sparse approximation perspective. This despite the ubiquity of sparse approximation in signal processing for tasks such as dictionary learning (Aharon et al., 2006) and compressed sensing (Donoho, 2006) due to its performance for discovering a sparse representation while avoiding redundant information. Here we employ sparse approximation methods for batch active learning tasks.
Our main contributions are summarized in the following. We propose a novel and flexible Sparse Approximation- based Batch Active Learning framework, ie., SABAL. We show how SABAL generalizes batch active learning as a sparse approximation problem and can adapt to different settings and models. The central intuition of SABAL is finding a weighted subset from the unlabeled data pool so that its corresponding training loss approximates the full-set loss function in a function space. We realize the SABAL framework an efficient siiteedimensional optimization problem: First, we derive an upper bound to balance the trade-off between uncertainty and representation in a principled way. Second, approximate the loss functions using finite-dimensiona approximation. This results in a sparsity-constrall several efficient optimization algorithms. We demonstrate the advantages of SABAL in experiments for both Bayesian and non- Bayesian batch active learning settings.
discontinuous optimization problem, for which we propose
The structure of this manuscript as follows. In Section we formulate the general framework of SABAL, and in Section 3, we realize the framework into finite-dimensional discontinuous sparse optimization problem. To solve the resulting optimization problem, we propose two optimization algorithms in Section 4. Related work are discussed in Section 5 and Appendix Section B. Results of our experiments are presented in section 6, and all proofs are provided in Appendix Section
2 BATCH ACTIVE LEARNING AS SPARSE APPROXIMATION
This section introduces the preliminaries and the general formulation of batch active learning sparse approximation problem.
Preliminaries Vectors are denoted as bold lower case letters, e.g., w E R"_ The lo pseudo- norm of vector w is denoted as ||l]|,, i.e., the number of non-zero elements of w. We denote R. := =00, +oo). Distributions are denoted in script, e.g., P, and a random variable is denoted by tilde, e.g., y S. We denote sets in calligraphy in uppercase Greek alphabet (e.g. D, θ), and In supervised learning, given a labeled training dataset Dj := [(2;; {(),,,)))" } where we denote their domain be X' and y Y, the empirical goal is to minimize loss function (0) := (.).))) ((x,, y:; 0) formed by the training dataset, where 0 E e C Ih" is the parameter of the model and E is a loss function evaluated on individual pairs of data. Without loss of generality, we assume C IRm is compact and f(x;, y; θ + : normed space (C(O, RR, || ||+)) for all æ, y. We further assume the constant function f O 1 is included in L(O, ()). The "t" in the norm || || R) + R,, representing its definition is a placeholder that will be discussed later.
additionally we denote [n] == {1, 112,....,1) n2).
in
Batch Active Learning Besides the labeled dataset Dr, there is an unlabeled dataset D. (m,
The )= where the labels are unknown but could be acquired at a high cost through human labeling. Combining two datasets, the ideal loss function to minimize w.r.t. 0 is
ElEYDeED, ((,; yı 0) + EnjED. U;;
(1)
where y the unknown true label corresponding to the data my- Since acquiring true labels could be costly, we have to impose budget b (b < n.,) on the number of label acquisitions. Therefore, the batch active learning problem is to find subset S C Dr, such that we can obtain a good model by optimizing the following loss function w.r.t. O,
ElE.Yee,, ((:; yes 0) + Emyes l (( where |S| b.
2

---

Under review as a conference paper at ICLR 2022
Generalized Batch Active Learning We start method by generalizing the classical formulation (equation 2) by considering an importance weight for each unlabeled data. That is, we aim to find sparse non-negative vector T such that we obtain good model by optimizing the following loss function w.r.t. A:
E(a.y)ED (x,, y:: 0) + Ea,ED, wy((Z,, yJ: 0), where ||w/|o = b.
(3)
A key question now what is the criterion for good w? Comparing the ideal loss function (equation 1) and the sparse importance weighted loss (equation 3), the only difference is their unlabeled data loss functions. Therefore, straight-forward informal criterion for good importance weight wo is that the two unlabeled data loss functions are close to each other, i.e.
L (0)
Σ 32 2D
wyllaz. U3:
L'
Σ v) Th DDED,
1
However, the true labels unknown, cannot compute L and L* Luckily, we can have an estimator for the true labels, i.e., estimation based on the labeled data p(ūj æy. Dr) or an approximation of it. Denote (xy estimated distribution, DJ 30 (xz)) then the informal criterion for good importance weight w then becomes
L (0) = Σ wfl(æ,, Ú5:0)
((
Σ (xx, Øy:
The æYED.
B,ED.
Thus, step closer evaluating the quality of weighted selection. The next question is how to measure the difference between L and Law-
Difference Between Two Loss Functions Given the two loss functions L, L. E L(O, R), where C(O, R) is equipped with the norm || |||, straight-forward measurement the difference between them is I Lwlll 1l However, observing that the optimization of a loss function shift-invariant, the difference between two loss functions should also be shift-invan haftt-nvvariant. For example, for VL E L(O, R) we have arg min + c) = arg mingee I(O)) for Ve & IR, implying that L + e should be treated the same as I.. Therefore, account for the shift-invariance, we define q L(O, R) R4 as
q (L) inf || + cll DER
VL E ((),R)
Note that we abuse the notation a bit, i.e. the in + c should the constant function that maps nice properties that make it good difference
every 0 E O to The above definition has measurement of two loss functions, as proved proposition C. in the appendix. In particular, q(-) satisfies the triangle inequality, and g(L+c) c) (()) for any constant Therefore, the generalized batch active learning problem as the following sparse approximation problem.
can formulate
Problem (Sparse Approximation based Batch Active Learning.. Given the hiift-invariat seminorm q induced by the norm I| ||+ (equation 5), and label estimation distribution P, the generalized batch active learning problem (equation 4) is formally defined as
arg min
BolggL-- Lww]]
S.t.
| b,
(6)
wER""
where Eg stands for the expectation over ÿ (1x)) for E [nw].
Problem (SABAL) offers general framework for batch active learning and can be applied with various settings, i.e., both the norm || ||= and the individual loss function & can be chosen based on
specific problems and applications. In the next section, we introduce two practical realizations of equation 6 for Bayesian and non- oon-Bayesian active learning respectively.
SPARSE APPROXIMATION AS FINITE-DIMENSIONALL OPTIMIZATION
In this section, transform the sparse approximation problem (equation 6) into sparse optimization problem. First, we address an issue regarding the sampling of Egg. Then, we discuss some concrete choices of @ and || that lead finite-dimensional sparse optimization.
3

---

Under review as a conference paper at ICLR 2022
Addressing the Sampling Issue In equation 6, the expectation Eg is taken over the product space of (f1...... yn.) and each sample has to be remembered for future optimization, which can be intractable for large datasets. However, it has upper bound where the complexity of the optimization is independent of the number of samples from P. First, by the triangle inequality
E [g [.m)
E ( g [L] + B E [L + Eg [[ L..)
S EE (a( se [T]]] + E Easaa(LTn (a( g [mm))]] + (B)) ( (7)
(s):
variance
appoxxiatin bias
We can see that it offers a tra between bias and variance, where the bias term is immediately tractable by expanding i., T.w: (tt) q (+t Tu EayeD. l( 0,: Egll EayeD. ",l(0, 01;
(8) It remains to address the variance term (i). Recall that the more accurate S is, the more accurate our approximation is. Given the decision wy 0, if the label of æ; is acquired, i.e. the oracle (human annotator) will offer us its true label yz. and the labeling distribution would be improved. That being said, the distribution of y given 24 and wy will be concentrated on its true label yz. i.e.
= = +t, Ex,ED. (((E, my: - EE (m,))(, (l)-
9 (xy) 6gy
if w 0 if wy
y (2,)
where w R
where byj denotes the distribution that fy can only be yz- However, the improved distribution Pw is not known before the acquisition of the true labels y for w, > 0. Fortunately, although P (x,) not known, it is known that the corresponding variance for ÿj would be zero no matter what its label is. Applying this trick, we show in the following proposition that the term (i) with the improved label distribution Pw has an upper bound that does not require to know the true labels.
Proposition 3.1. Let w E RT and ||oloo = b. by replacing the P by the improved estimation distribution Pw (equation 9) into (i) in equation we have
E Eg -Eg [[]]] + Es (9( Eg [LoD)s
11,,==))o
(10)
where a=:- == Th (a, Na(((m, )) E ( (1; -); is the individual variance, and 1()
is the indicator function.
Therefore, combining equation 8 and equation 10, we have more tractable form of the sparse approximation, i.e.,
arg min wERS"
(Lwl) + Σ 1) ayEDD
s.t. | = b, (1I)
Intuitively, such decomposition of bias and variance naturally provides metrics of uncertainty and representation for active learning, where the variance itself a metric of uncertainty, meanwhile the bias term measures how well a subset of selected data can represent the whole unlabeled data. Now, ||+, i.e., the norm that induces q (equation 5).
it remains to specify the choice of)
Formulation of the Finite-Dimensions Optimization We consider two concrete choices of the ||- II+ for Bayesian and non-Ban -ayessia settings respectively.
1. In the Bayesian setting, we can easily sample 0, ~ ग == p(0 D:) from the posterior. Utilizing the posterior, make the norm || |lt more concrete by considering the L²( i.e., ||T. = E [T))) Accordingly.
(L)) 2 inf L + c|I = inf Ee~xI(L(O) + c) = Eg (L(()) - E (L())))
(12)
<ER
<ER
The posterior π tells us where and how to evaluate the "magnitude" of L. Noting that equation 12 is in the form of an expectation, we can draw m samples 0, ~ to approximate it. Denote
g = -n (L(O.) L), .I E RRm where L == 1 m L(O.). equation 12 becomes
q(L)2 ~ 1 m
Σ (L(0.) - L 11
(13)
where ||g||2 is simply the Fuclidean norm of the m-dimensional vector g-
4

---

Under review as a conference paper at ICLR 2022
2. In the non-Bayesian setting, evaluate the loss function in local "window" based the current model. We consider the l -lle--norm over a Euclidean ball B, (0,) of radius r centered at the current model parameter pp. L.e., || m, |L()) Moreover, in the Euclidean ball 0o). Therefore, we have
we approximate L(0)= [(0)) [+ VL(O0)
q( inf L cl
inf max cER (B.)
[L(0) c
cER
inf max [[(O.) + VL( T 0o) + rl)V1(00)ll2 cEE 0E
(14)
Note that |[T]()))] 2 the Euclidean norm of the gradient vector VI((0) E R
To estimate the label distribution, (mx,) p(ū; T;; D:) can be directly applied Bayesian models by estimating the predictive model posterior. For non-Bayesian models, one could utilize the calibrated model prediction (Guo al., 2017) as the label distribution. Finally, plugging either of the two approximations of (L) into equation 11, and squaring all of the terms for the ease of optimization, we can formulate the sparse approximation problem the following finite-dimensional optimization problem, where >
0 offers trade-off between bias and variance.
arg min WER
|| tw + t
Σ EEE
1(w, = 0) oz s.t. ||w||o b,
(15)
where we denote v E R + mmxnn and of as
o (m,)) 9 (3,)
+
(B 19 (31)). ... . ( Ign (fn... II)
na
1
Jj Tu
( |1g) (ū,) (x وy 112]
[..., (f(ar)) J5: 0.) .) I 8:= 8:=1 m Σn (f:
if use (13)
9, (,)ū Vi(a,, 00)
if use (14).
(16)
In practice, it is often the case that the number of parameters is less than the number of samples, ie., m < Yuu, even for aver-parameterized neural networks where the gradient of the last layer is commonly used represent the full-mn full-model gradient (Katharopoulos Fleuret, 2018; Ash al., 2019). Therefore, if the batch size is big, i.e., b > the approximation bias |/v T 1 may be under-determined with infinitely many w to make v &w, and the optimization (equation 15) may be "overfitted". To make our method more stable, we include a &g regularizer /l| - 1 with 0. Finally, since w/ 2 0, minimizing En, 1(w, 0) og equivalent to minimizing
-a -a E2, 1(w, 0) oj. Consequently, we have the following optimization problem.
Problem 2 (Sparse Approximation as Finite-dimensional Optimization). The finite-dimensional
optimization for generalized batch active learning is
arg min wER"
||0- fv-ww/i
Σ m
1( > 0) o7 +
+
1 s.t. ||w||o =
(17)
While simplified, the result is sparse discontinuous optimization problem generally difficult to solve. In the next section, we propose two optimization algorithms for equation 17 by exploiting its unique properties. The overall procedure of SABAL in practice is presented in Algorithm 3 Appendix A.
4 OPTIMIZATION ALGORITHMS
This section focuses optimizing Problem 2. Rewrite equation 17 f(w) := fi (w) + fa(w), where
fi (w) = a| &w + Bl| 111.
fe(w) a En, ED. 1( 0) o7.
The optimization has two major difficulties, i.e., the nonconvex sparsity constraint ||w||o = and the discontinuous objective function, f2. When it comes to ppansity-oonstrainedd optimization, there
5

---

Under review as a conference paper at ICLR 2022
two schemes that are widely considered - greedy (Nemhauser et al., 1978; Campbell & Broderick, 2019) and iterative hard thresholding (IHT) (Zhang et al., 2021; Khanna & Kyrillidis, 2018). However, Problem 2 introduces the new difficulty other than the sparsity constraint, i.e., the discontinuous component f2, which violate the assumptions of many of these methods which require the use of gradient. Instead, we propose two algorithms (Algorithm 1&2) specifically for Problem 2 under the two schemes respectively, while incorporating the discontinuity.
We introduce some notations used in this section. Given a vector g. we denote [g]+ as g with its negative elements set to O. For an index j. we denote or (g); to be its jth element. For an index set S, we denote [g]s be the vector where ([g]s) (g); if j E S and ([gls), = 0 if $ S. Moreover, denote e to be the unit vector where (e)) and (e² )2
for vi +
Although two algorithms use different schemes, they share the same two aub--poccedues: line search and de-bias step (Algorithm and in Appendix D), which significantly improve the optimization performance (Zhang et al., 2021). The line search sub-procedure optimally solves the problem arg min fi( yu)), i.e., given a direction u, what is the best step size p to move the w along u. The de-bias sub-procedure adjusts a sparse uo in its own sparse support for a better solution.
Greedy The core idea of the greedy approach is noted in line 3 Algo- rithm 1, where it chooses an index to move a step of size t that minimizes the objective, i... + arg Jemnlis (fiww + Te') fi(w) (f2(w + re)) - f2(w)). By ap- proximating fi (w -
Opt. Algorithm:
Algorithm 1: SABAL-Greedy
Parameter: sparsity b, step size T. w +- 0; S <
repeat
j + arg min (()f(())) - ooo
JEin.Jis
by its first- order approximation (V (Vfi(w), Te"), and not- ing that f2(w + re)) -2 = -ao we have the greedy step (line 3) in Algorithm 1. After choosing the index to include, line 5 chooses an optimal step to move, followed by de-bias step that further improves the solu- tion in the current sparse support supp(w))
S + S si
(update selection)
and
f- LineSearch(e', w)
w De-bias(w ue²)
Wy <- 0 for Vut < 0
(w E R
until [S] = by
Return: w
Algorithm 2: SABAL-IHT
Opt. Algorithm: Proximal iterative hard thresholding The core idea of the proximal IHT (Algorithm 2) is noted in line 6, where it combines both the hard thresholding and the proximal operator. It minimizes the discontin- uous f2 in neighbourhood of the solution s obtained by minimizing f1, while satisfying the constraints. As discussed in the section D, the inner optimization (line 6) can be done op- timally by simply picking the top-b elements from n, elements. After this core step, de- bias step improves the solution w within its sparse support, followed by momentum step.
Parameter: sparsity b; number of iterations T.
w t 0; z 0
repeat
w² < w
(save previous w)
μ f- LineSearch (z),
4-++ ())(
(gnadient descent)
w f- arg min
1
11 w
s f2
wER"" .ll w/ lo
w + De-bias(ww) (D)
Wj f 0 for Vw, <
(w RT (momentum)
f- LineSearch( (w w', w)
x- w w- 7(w w')
until T iterations;
Return: w
Complexity Analysis We analyze the time complexity of the proposed algorithms with respect the number of data samples and the batch size b of batch active learning. Except for line 6 Algorithm 2, all steps are of time complexity On)). The line 6 Algorithm is finding the smallest elements, which can be done in O(n log( Therefore, the time complexity for SABAL-Greedy is (mb)), and the time complexity for SABAL-IHT is (n log(b)). Comparing to the time complexity O(bb²) of the state-of-the- the--rr method BADGE (Ash et al., 2019), the two proposed algorithms can be much faster, especially with a large batch size b used in practice.
5 RELATED WORK
Our method has several characteristics: (1) it's a hybrid active learning approach. (2) it's a general framework with building blocks easily adapted to both Bayesian and non- -a--aaysian settings. (3) it.

---

Under review as a conference paper at ICLR 2022
formulates data acquisition as sparse approximation problem. This section focuses discussing some most relevant works, and explain how they motivate and compare to our work. Other related works are discussed in Appendix B.
As data acquisitions with the trade-off between uncertainty and representation have attracted attention, several recent works have proposed hybrid active learning methods. One of the state-of-art art methods, BADGE (Ash et al., 2019), captures uncertainty through the lens of gradients, and samples diverse batches on the gradient embedding by the k-MEANS+ seeding algorithm. However, one of the downsides of BADGE is the high run-time complexity, as data acquisition speed is crucial in practice. Sinha et al. (2019) train a Variational Autoencoder and discriminator in an adversarial fashion. The discriminator predicts sample as unlabeled based on its likelihood of representativeness. and a batch of samples with the lowest confidence will be queried, but their adversarial method difficult to apply to general and Bayesian neural networks. Our proposed method explicitly balances the trade-offs between uncertainty and representation by bias and variance decomposition.
Coreset selection is a common high-level idea used in active learning, and methods vary in how one characterizes the closeness of a chosen coreset to the full-set. Sener & Savarese (2017) characterizes the closeness as how much a coreset covers the full-set in the Euclidean distance in feature space. derives an upper bound for the coreset loss based on the Lipschitz continuity and transforms the original problem to KCenter problem. However, their method relies on good feature representation. which is not always guaranteed in practice. Pinsler et al. (2019) is mainly based on existing Bayesian inference literature, especially the Bayesian Coreset problem (Campbell & Broderick, 2019). They characterizes the closeness as how much the core-set log-posterio approximates the full-set log- posterior, with the log-posterior directly derived from the Bayes' rule. However, their problem formulation relies on the Bayesian setting and Bayesian models, and conducting posterior inference non- coivaaivial for non- -on-Biani models. In constrast, we propose SABAL, which characterizes the closeness in a more general sense, i.e., through semi-norn function directly on the difference between the coreset loss function and the full-set loss function.
EXPERIMENT RESULTS
We demonstrate that SABAL is a flexible batch active learning framework with relatively small time complexity by evaluating its performance on image classification tasks with various models under different settings. First, using Bayesian neural networks, we show the effectiveness of SABAL on Bayesian batch active learning. Next, we demonstrate that SABAL can also adapt well to general batch active learning with general neural networks. Finally, we show that SABAL also has runtime advantages compared to other state-of-ar art methods. We also conduct an ablation study to show how SABAL balances the trade-offs between uncertainty and representation in Appendix E.
We have fixed training, validation, and testing set in each experiment. The model is initially trained on small amounts of labeled data randomly selected from the training set and then iteratively performs the data acquisition and annotation. The model is reinitialized and retrained at the beginning of each active learning iteration. After the model is well trained, its testing accuracy is evaluated on the testing set measure of the performance. All experiments are repeated multiple times using 5 random seeds (3 for the small model LeNet-5 (LeCun et al., 2015)), and the results are reported as mean and standard deviations. The performance of each iteration are shown in learning curve plots. To better visualize the overall performance of AL methods, We also measure the area under curve (AUC) scores of the learning curve of different AL methods across different datasets. The top two AUC scores are highlighted in bald. We implement SABAL using both proximal IHT and greedy as two different optimization methods for the sparse approximation, denoted as SABAL-IHT and SABAL-Greedy, compared with following basclines in literature: (1) Random: A naive bascline that selects batch of data uniformly at random.
(2) BALD (Houlsby et al., 2011): An uncertainty- based Bayesian method that selects batch of data with maximum mutual information between model parameters and predictions.
(3) Entropy (Wang & Shang, 2014): An uncertainty-base non-Bayesian method that selects a batch of data with maximum entropy of the model predictions H (y: x;; 0). (4) KCenter (Sener& & Savarese, 2017): A representation- based non-Bayen Bayesian method that reformulates the coreset selection as a KCenter problem in the feature embedding space. (5) BADGE (Batch Active Learning by Diverse Gradient Embeddings) (Ash et al., 2019): A hybrid non-Bayesian method that samples diverse batch of data using the k-MEANS++ seeding algorithm.
7

---

Under review as a conference paper at ICLR 2022
(6) Bayesian Coreset (Pinsler et al., 2019): A Bayesian batch active learning approach based on the Bayesian Coreset problem (Huggins et al., 2016; Campbell & Broderick, 2019).
SABAL for Bayesian Active Learning We first implement our experiments on Bayesian neural networks and perform Bayesian active learning on Fashion MNIST (LeCun et al., 1998), CIFAR- 10 (Krizhevsky et al., 2009), and CIFAR-100 (Krizhevsky et al., 2009). For fair comparison, we keep the same experiment settings of Pinsler et al. (2019), using Bayesian neural network consisting of a ResNet-18 (He et al., 2016) feature extractor. The posterior inference is obtained by variational inference (Wainwright& & Jordan, 2008; Blundell et al., 2015) at the last layer, and model predictive posteriors p p J Di) are estimated using 100 samples. Equation 13 is used to solve the finite- dimensional optimization problem, because sampling from the posterior distribution in a Bayesian neural network will be efficient by leveraging the local reparameterization trick (Kingma et al., 2015). Besides Random, we mainly focus on comparing with state-of oftee-------tttttt approaches specifically designed for Bayesian active learning: BALD and Bayesian Coreset.
We then evaluate SABAL's performace. On Fashion MNIST dataset, we use 100 samples for random projections, 1000 seed data, and query 1000 samples for 9 iterations. On CIFAR- 10 and CIFAR- two more complicated datasets, we use 2000 samples for random projections, 3000 (10000 for CIFAR- 100) seed data, and query 5000 samples for 4 iterations. Because Bayesian Coreset usually finds much smaller batch than requested, for a fair comparison, we let Bayesian Coreset acquire more data than the batch size, and stop the acquisition long it has selected full batch of data. It can be seen in Table 1 and Figure 1 that both SABAL-IHT and SABAL-Greedy show some advantages on Fashion MNIST dataset. On CIFAR-10 and CIFAR- 100, find SABAL-Greedy performs better than SABAL-IHT while outperforming other baselines, including the Bayesian Coreset, one of the current state-of-the-ae approach in the literature under Bayesian settings.
Table 1: AUC Score (+ std.) for different AL methods on Bayesian active learning. AUC measures the overall performance improvement across number of queries. Results show the proposed SABAL- matches or outperforms all baselines.
Dataset
Bayesian Coreset
SABAL-Gredd
SABAL-IHT
BALD
Random
Fashion MNIST
89.53 + 0.25
89.83 + 0.26
89.97 97 + 0 23 77.55
89.72 + 0.23
88.39 39 + 0.32 76.36
CIFARIO
77.73 0.70
0.53
0.83
77.61
0.59
0.59
CIFAR
42.40 1 0.29
42.53 4 0.34
42.30 + 0.29
41.99 4 0.60
42.10 + 0.24
Fashion MNIST
CIFAR1O
CIFAR100
Aardwy Dovmlin
Fasker Davel Connet
Excesler Cormat
SASALHIT (40)
SADNL (oam))
SABAL-IIT loung
300
300
800
1000
200
data queriod
2000
num of da13 quoried
1220
2008 numm of queried
Figure I: Active learning results on Bayesian models. Solid lines and shaded arcas represent means and standard deviations of test accuracy over different seeds. Our method especially SABAL-Greedy outperforms most baselines and the SOTA method Bayesian Coreset.
SABAL for General Active Learning We then implement our experiments on general convolu- tional neural networks, including LeNet-5 (LeCun al., 2015) and VGG-16 (Simonyan & Zisserman, 2014) architectures without any Bayesian layers, using MNIST (LeCun et al., 1998). SVHN (Netzer et al., 201 I), and CIFAR-10 (Krizhevsky et al., 2009) datasets. We utilize calibrated prediction of current model with temperature scaling (Guo et al., 2017) to approximate the label distribution p(ū; x,, D:). Because the gradient of the last layer represents the full-model gradient (Ash et al., 2019), we can easily solve the optimization problem with gradient embedding as equation 14. We compare with popular non- -on-Bayesian baselines: Random, Entropy, KCenter, and BADGE
To evaluate the performance of SABAL, MNIST dataset with LeNet-5 model, data, and query 40 samples for 15 iterations. On SVHN and CIFAR- 10 with VGG-16 model, which contains more complicated real-world color images, we use 1000 (3000 for CIFAR-10) seed data,
40 seed
8

---

Under review as a conference paper at ICLR 2022
and query 1000 (3000 for CIFAR-10) samples for 5 iterations. The results shown in Table 2 and Figure 2. In general, SABAL-Greehe also performs better than SABAL-IHT and outperform most baselines, while achieving comparable performance to the strong baseline BADGE, the current SOTA non-Bayesian method in literature, but SABAL requires much less acquisition time than BADGE especially large models. In addition, most methods perform similarly CIFAR-10, and conjecture that for CIFAR-I0 each sample is informative enough and thus random selection can achieve good enough performance.
Table 2: AUC Score (+ std.) for different AL methods on general active learning. AUC measures the overall performance improvement across number of queries. Results show the proposed SABAL. matches or outperforms all baselines.
Dutasel
BADGE
SABAL-Gredy
SABAL-IHT
KCenter
Entrupy
Random
MNIST
91.24 + 0.48
90.89 + 0.38
91.07 + 0.45
89.57
1,02
90.68 + 0.81
86,48 + 1.11
SVIN
86.92 0.71
87.23 1 0.47
86.84 0.57
87.04 1 0.80
86.28 1 1.05
85.52 1 0.51
CIFARIO
68.20 0.56
68.01
0.66
67.80 0.69
67.98 0.63
67.94 + 0.64
67.05
0.59
MISST
SVINN
QIARIO
Drincs
SAMILOO (oun))
SASAL-01 bannd
Fum/ Of 8ata QU00100
PUn of cora Qutriol
numm of dato queried
Figure 2: Active learning results on general (non- Bae-esayei models. Solid lines and shaded areas represent means and standard deviations of test accuracy over different seeds. Our method performs comparable or better than baselines and the SOTA method BADGE.
Run Time Comparison Our experiments show that SABAL can achieve comparable performance of SOTA methods while requiring much less acquisition time. We compare the empirical results of runtime complexity of SABAL with other baselines example. Here, consider the acquisition time of the first query, where the unlabeled data pool has the largest size compared with later queries. Large models and datasets (SVHN and CIFAR-10 10 on VGG-16) are used to better illustrate the runtime complexity. Results are shown in Table 3. It can be seen that SABAL requires much less runtime than BADGE especially when queried batch is large, and even less than KCenter in most cases.
non-Bayesian active learning experiment as an
Table 3: first query's acquisition time (# std.) of different AL methods on two large datasets. SABAL_ shows big runtime advantage.
Dataset
Method
Time (unit:s)
Dataset
Method
Time (unit:s)
SVHN
BADGE
732. 18 + 26. 29
CIFARI0
BADGE
1207 19 + 121.09
SABAL-Grood -roddy
201.65 3.54
SABAL-Gredd
333.67 3.53
SABAL-IHT
211.04 + 10.65
SABAL-IHT
174.28 3.27
KCenter
309. 0.81
KCenter
258.29 2 1.75
Entropy
16.46 0.29
Entropy
11.76 0.03
Random
0.81 1 0.02
Random
1.42 1 0.02
7 CONCLUSION
We introduce the SABAL as a novel framework that formulates batch active learning as sparse approximation problem. It balances representation and uncertainty in principled way, and has the flexibility to adapt to both Bayesian and non-Bayese Bayesian models. We realize the SABAL framework as fiite--imennional optimization problem, efficiently solvable by the proposed greedy proximal IHT algorithms. Numerical experiments demonstrate the strong performance of SABAL, comparable to the state-of-the-arr with lower time complexity. For the future works, although the hyperparameter a offers a controllable trade-off between the variance and bias, it is still not well-understood how to strike the best balance. An in-depth theoretical analysis of the SABAL optimizations, well as other instantiations of our general framework, would also have the potential to inspire discoveries of even better batch active learning algorithms.

---

Under review as a conference paper at ICLR 2022
8 ETHICS STATEMENT
This work is proposing an active learning approach for more efficient data acquisition and model training, we do not expect any obvious ethical issue from this work.
REPRODUCIBILITY STATEMENT
We have included the code and instructions to reproduce our work in the supplementary material. We also provide the experiment settings, training details and hyperparameters the Appendix.
REFERENCES
Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing over- complete dictionaries for sparse representation. IEEE Transactions on signal processing, 54(11): 4311-4322, 2006.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint 2019.
William Beluch, Tim Genewein, Andreas Nürnberger, and Jan Köhler. 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.
Erdem Bıyik, Kenneth Wang, Nima Anari, and Dorsa Sadigh. Batch active learning using determi- 2019.
nantal point processes. arXiv preprint
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning, pp. 1613-1622. PMLR, 2015.
Trevor Camphell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. The Journal of Machine Learning Research, 20(1):551-588, 2019.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In International Conference on Machine Learning, pp. 160-168. PMLR, 2013.
Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 412(11):1777-1781. 2011.
David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289-1306 2006.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint arXiv:/802.09844] 2018.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Insights and applications. In Deep Learning Workshop. ICML, volume pp. 2015.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, PMLR, 2016.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. arXiv preprint we..iv1703.0022 02910, 2017.
Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprint arXiv:1711.00941. 2017.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pp. 1321-1330. PMLR, 2017.
Steve Hanneke et al. Theory of disagreement-bused active learning. Foundations and Trends@ in Machine Learning, 132-3):131-300 2014.
10

---

Under review as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Patrick Hemmer, Niklas Kühl, and Jakob Schöffer. Deal: Deep evidential active learning for image classification. arXiv preprint arXiv:2007. 1144, 2020.
Steven CH Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu. Batch mode active learning and its application medical image classification. In Proceedings of the 23rd international conference on Machine learning, pp. 417-424, 2006.
Neil Houlsby, Ferene Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv:1112.5745, 2011.
Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. arXiv preprint 1.Kiv:6605.064255 2016.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525 2534. PMLR, 2018. 8.
Rajiv Khanna and Anastasios Kyrillidis. Iht dies hard: Provable accelerated iterative hard thresholding. In International Conference on Artificial Intelligence and Statistics, pp. 188-198. PMLR, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1412::1412.6680, 2014.
Diederik P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteri- zation trick. arXiv preprint arXiv: 2015.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Advances in Neural Information Processing Systems, pp. 7026-7037, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11)6 (6611))2278-253 1998.
Yann LeCun al. Lenet-5, convolutional neural networks. URL: http://yann. lecun. com/exdb/lenet, 20( 2015.
Xin Li and Yuhong Guo. Adaptive active learning for image classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 859-866, 2013.
George Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i, Mathematical programming, 14(1):265 2944, 1978.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Lobate Bayesian batch active learning as sparse subset approximation. In Advances in Neural Information Processing Systems, pp. 6359-6370, 2019.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. arXiv preprint 1uXiv:1708.0048) 2017.
Burr Settles. Active learning literature survey. Technical report, University of Mesconsin-Madisee Department of Computer Sciences, 2009.
Maohao Shen, Jacky Y. Zhang. Leihao Chen, Weiman Yan, Neel Jani, Brad Sutton, and Oluwasammi Koyejo. Labeling cost sensitive batch active learning for brain tumor segmentation. In 2021 IEÉE 18th International Symposium on Biomedical Imaging (ISBI), pp. 1269-1273, 2021. doi: 10.1 109/181142211 2.2021 191.9994498.
11

---

Under review as a conference paper at ICLR 2022
Changjian Shui, Fan Zhou, Christian Gagné, and Boyu Wang. Deep active learning: Unified and principled method for query and training. In International Conference on Artificial Intelligence and Statistics, pp. 1308 1318. PMLR. 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1ecki::440..110 1556, 2014.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp- 5972-5981, 2019.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45 66, 2001.
Martin J Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and variational inference. Now Publishers Inc, 2008.
Dan Wang and Yi Shang. A new active labeling method for deep learning. In 2014 International joint conference on neural networks (IJCNN). pp. 112-119. IEEE, 2014.
Keze Wang, Dongyu Zhang, Ya Li, Ruimao Zhang, and Liang Lin. Cost-effective active learning for deep image classification. IEEE Transactions Circuits and Systems for Video Technology, 27 (12):2591-2600, 2016.
Yazhou Yang and Marco Loog. Single shot active learning using pseudo annotators. Recognition, 89:22-31, 2019.
Pattern
Jacky Y. Zhang, Rajiv Khanna, Anastasios Kyrillidis, and Oluwasanmi Koyejo. Bayesian coresets: Revisiting the nonconvex optimization perspective. In International Conference on Artificial Intelligence and Statistics, pp. 2782-2790. PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2022
SABAL: Sparse Approximation-based Batch Active Learning Appendix
A THE OVERALL PROCEDURE
Algorithm 3: SABAL: Sparse Approximation-based Batch Active Learning
Input: Intial parameters 0, initial unlaheled pool D,, initial labeled pool Di Ø, initial number
samples bo. query batch size 6, number of iterations T.
Query random batch So of bo data from Dr, update D., + Du and Dr Dr U So.
2 Train the model using So.
for f = 1, 1,2, ... T do
For each data æ;j E "D., estimate its label distribution ÿü (xz)). Compute vector 9j by sampling gradient embedding using 16. Compute v, 4 and 0j for each 2; E 'D, and form equation 17. Find sparse weight w s.t. || lo 6 as specified section 4. Select batch of data S, = {az E Du wy > 0} and query their labels.
Update D., < Du SS, and D: < Di U.S.
Reinitialize and retrain the model using updated Di, update model parameters O
11 end
Return: Final model parameters
B MORE RELATED WORK
Active learning has been widely studied by the machine learning community. As most classic approaches have already been discussed in a detail in Settles (2009); Dasgupta (2011); Hanneke et al. (2014), will briefly review some recent works in deep active learning.
Existing query strategies can mainly be categorized as mncertainty-basee and representation-buds based. Uncertainty- -base approaches look for data samples the model mostly uncertain about. Meanwhile, under the Bayesian setting, several recent works leverage the Bayesian neural network to well measure the model uncertainty. Gal Ghahramani (2015; 2016) proves the Monte-Carlo dropout (MC Dropout) approximation of performing Bayesian inference, and enables efficient uncertainty estimations neural networks. Gal et al. (2017) utilizes MC Dropout for approximating posterior distributions and adapts Houlsby et al. (2011) their uncertainty based acquisition function, and similarly, Kirsch et al. (2019) proposes batch-mode approach based on Gal et al. (2017) and shows some improvements through batch and model parameters. While MC Dropout becomes prevalent for uncertainty estimation, Beluch et (2018) shows ensemble-based methods lead better performance because of more calibrated uncertainty estimation, and another recent work Hemmer et al. (2020) also proposes a new uncertainty estimation method by replacing the softmax output of a neural network with the parameter of Dirichlet density. Other non- Bayesian approaches sometimes combine uncertainty estimation with other metries: Li & Guo (2013) combines an information density measure to maximize the mutual information between selected samples and remaining unlabeled samples under the Gaussian Process setting. Wang et al. (2016) selects data based on several classic uncertainty metrics and incorporate cost-efficient strategy by pseudo labeling the confident samples.
accurate measurement of mutual information between the data
Representation-base approaches attempt to query diverse data samples that could best represent the overall unlabeled dataset. recent work proposed by Sener & Savarese (2017) defines the active learning as a core-set selection problem. They derive an upper bound for the core-set loss and construct representative batches by solving k- Cennter problem in the feature space. In Geifman EI- Yaniv (2017), the authors also explore the deep active learning with core-sets, but build the core-sets in the farthest- ftrstttttttttttteete compression scheme.
13

---

Under review as a conference paper at ICLR 2022
C PROOFS
Proposition C.1. q ((), + R2 defined in (5) is a shift-invariant seminorm satisfying the following properties:
1. (L1 L2) I (Ln) (L2) 114 (()
(triangle inequality)
2. ((T)) = Icla( C VC
(absolute homogeneity)
3. (LL + c) q()) for VL ((O, R)
(shiffiinvariance)
4. (()) if and only if L maps every θ constant.
In other words. defines nomm in the space of shift-equivalence classes of loss functions. Proof. Recall that
(L) = inf I| + cllt,
VL ()),
We prove the four properties respectively in the following.
1. The triangle inequality is inherited from the sub-additivity the norm || ||+. For VL e C(O, R), we have
aLLn + I2) = inf .E3
[| + L2 + clli = inf
[[ + L2 + a + calli
inf ||4 + cillt || + 02llt
q.ogER
-inf [[ + +lll))
(inf L2 + clli) CER
cER
(Ta (
2. The absolute homogeneity is also inherited from the absolute homogeneity of the norm || Ilt The case for 0 obvious, and for c + 0 have
q(cL) [cll(L) = inf ||cL + +ill+
inf Ce
|d| dll- + c1/ellt
ER
inf |d| [|-||L++op Lc)g(L).
czER
3. By the definition of 4(-), we have the shift-invariance of g(-).
4. The "if" part can be proved by definition, i.e., q(c) = infe,ER ||c| + cll+ |[0]| = 0.
For the "only if" part, we need be more rigorous by defining fo to be the function that maps @ to e E R. We further define F := {ffe E RJ C L(e, R). and we can see (F, (1+)) a one-dimensional normed space. Letting
L(O, IR) and (() O, we have
inf |T. + fall: = 0. fe.E
Therefore, for Ve > 0, 3c, E R such that
|L + fc. 11ll Sc
|l = IL fe, - L S c ||
That being said, for 0 < 1, have ||f < + ||]| Denote B = (fa F [[allt S + [ and we can see B is a closed ball in F. As F is one-dimensional, by Riesz's lemma have B compact.
As lim | + fo.ll = 0, ie., Sc. + L, by the compactness of B we have L E B. Therefore, L is also constant function. Note that this conclusion does not require K() to be complete.
14

---

Under review as a conference paper at ICLR 2022
Proposition C.2 (Proposition 3.1 Restated), As B+ and ||o||o b, by replacing the P by the
improved estimation distribution P (equation 9) into (i) in equation 7, we have
B Lall Ege. [L]]] Ese (a( Ege [bm)))]] S
Σ 2y E..
1
where o. := 1 E, (0, M): E E -y: the individual variance, and 1())
The the indicator function.
Proof. Recall that
(0) = Σ
(( = 1
Σ
Thu w,EDx
ByeD,
(x,)
if w =
D P w (xz)
RT
if wi
where by; denotes the distribution that ú, can only be yz. Therefore, by the definition of Pw. have
Eg (s)(s)) [a (E(æ), (5; ww (( 9y; 0,
if if > 0.
Plugging the above definitions into E (Lw E [iw])] we have
Eg, (Lw - E. [(wl))] = Es
q
Σ
wy ([(z).0g:-) Ege (m, 05و
The
Esw
Σ
1(w, > 0)w, (4(x,, - E Ee (( Uys = 0.
The ayED.
(18)
Therefore, we only need to care about the E Be -Ese [7.)]]
1 Σ
E Ese.. lg(L - Es [b])] = E E
(,; E ( [,:
Tu
a;ED,
1
nu (x
(x2) [g (l(z,,, .): E (0, (e(,,,
2; ED
1 Egr (E( 0yi - E (0 0): Iwwj- = 0)
Σ EDED,
Tbu
Imm .).
(19)
2, E,ED
where the inequality is by the triangle inequality and the absolute homogeneity of q(-) (Proposi- tion C.I). Combining equation 18 and equation 19, we have the proposition proved.
D OMITTED ALGORITHMS
In this section we present the two sub-procedures, i.e., line search and de-bias, shared by two main optimization algorithms (Algorithm 1&2), well how the optimization (line 6) in Algorithm 2 is solved optimally.
The line search sub- procedure (Algorithm 4) optimally solve the problem of arg min fi (w wu). i.e., given a direction u what is the best step size to move the w along u. The de-bias sub- procedure (Algorithm 5) adjusts sparse in its sparse support for better solution.
15

---

Under review as a conference paper at ICLR 2022
Algorithm 5: De-bias(ws)
Algorithm 4: LineSearch(u, w)
Input: starting point w.
Input: direction u, starting point w. Output: step size μ.
Output: improved w.
u (ur( (in-support grad.)
(4:0 n. +. | B+
1
(optimal p))
μ LineSearch(u, w)
Return: 14
w <- w pm
(in-support adjustment)
Return: w
Recall the inner optimization (line 6) of Algorithm 2 is
W f-
arg min
1100 - 8 f2(w))
Noting that - simply picking the top-b elements, as shown in the following. Given a b-sparse support set [nu]. that
aoo)). this step can be done optimally by $2 EJem ( -
min WERT supp( w [jemm.1(2(u)) =5)² 1 aao) = Ejes( - arr)).
Therefore, line 6 in Algorithm 2 can be done by: (1) find the smallest (g|-s;} - coof), denoting the resulting b-sparse index set as S* (2) let w [[s]s-]+.
E MORE EXPERIMENT RESULTS
E.1 ABLATION STUDY: TRADE-OFF OF UNCERTAINTY AND REPRESENTATION
We perform an ablation study to understand better the trade-off between the variance and the bias terms in our final formula- tion equation 15. To remove the bias term, we query the data with top variances. To remove the variance term, we query the data by only minimizing the approximation bias, i.e., setting a 0, under both IHT and Greedy optimizations respectively. We take two datasets MNIST and CIFAR-10 ( in the Bayesian experiment as examples. Results Figure demonstrate the necessity of taking both uncertainty and representation into consideration during the data acquisitions for ideal performance, while for some datasets like CIFAR-10, the variance contributes much more significantly.
Sua Gela (011)
num cata queried
800
CIFAR10
F IMPLEMENTATION DETAILS
lasing
Sum Only
All experiments are written in PyTorch 1.8.1. All hyper-parametert are chosen to ensure models achieve good and stable performance on each dataset, and they are kept identical for all active learning approaches.
cirncyy
1990
2900
Figure 3: Ablation Study Re- sults on Bayesian models.
F.1 BAYESIAN ACTIVE LEARNING EXPERIMENT
Model Architecture We use the exact same model as (Pinsler al., 2019), it is a Bayesian neural network consisting of ResNet-18 18 (He al., 2016) feature extractor followed by fully connected layer with a ReLU activation, and final layer allows sampling by local reparametrization (Kingma al., 2015) with a softmax activation.
Optimization and Hyperparameter Selection Due to larger models and more complicated classi- fication tasks, e.g., CIFAR-100, 100, data augmennation(includngg random cropping and random horizontal flipping) and learning rate scheduler used in this experiment to achieve good model performance. The model is optimized with the Adam (Kingma & Ba, 2014) optimizer using default exponential decay rates (0.9, 0.999) for the moment estimates. Table 4 shows the hyper-parameten in experiment
16

---

Under review as a conference paper at ICLR 2022
Bayesian batch active learning, where bs denotes the batch size in dataloader during the model training, denotes the learning rate, and wd denotes the weight decay. The parrr-easaeeerss are chosen through grid search.
Table 4: Hyperparameters used in Bayesian active learning experiment
Dataset
Method
Epoch
bs
G
Ir
wd
Fashion MNIST
SABAL-IHT
200
256
1
10-3
0.001
5 x 10
Fashion MNIST
SABAL-Greed
200
256
2
0.5
0.001
5 x 10
CIFAR-10
SABAL-IHT
200
256
10-6
0.001
10
CIFAR-10
SABAL-Greedy
200
256
2
0,001
5 5 10
CIFAR-100
SABAL-IHT
200
256
1
10-6
0.001
5 10-4
CIFAR-100
SABAI-Greedy
200
256
0.5
0.001
x 10
F.2 GENERAL ACTIVE LEARNING EXPERIMENT
Model Architecture MNIST dataset, we use LeNet-5 model (LeCun et al., 2015). On SVHN and CIFARIO datasets, we use VGG-16 model (Simonyan & Zisserman, 2014).
Optimization and Hyperaarameter Selection All models are trained using the cross entropy loss with SGD optimizer, and no data augmentation or learning rate scheduler is used. Tabel 5 shows the hyper-parameters in experiment on general hatch active learning, where bs denotes the batch size in dataloader during the model training, Ir denotes the learning rate, denotes the momentum, and wd denotes the weight decay. The hyper-parameters are chosen through grid search.
Table 5: Hyperparameters used in general active learning experiment
Dataset
Method
Epoch
bs
8
1r
wd
MNIST
SABAL-IHT
150
32
10
10
0.01
0.9
5 x 10 10-4
MNIST
SABAL-Greedy
150
32
10-8
10-1
0.01
0.9
5 10
SVHN
SABAL-IHT
150
128
10-8
10-1
0.01
0.9
5 10
SVHN
SABAL-Greedy
150
128
10-1
10-1
0.01
0.9
5 10
CIFAR-10
SABAL-IHT
100
128
10-8
10-6
0.001
0.9
5 10
CIFAR-10
SABAL-Greedy
100
128
10
10-1
0.001
0.9
5 10
17


Reviews:
[{"review_id": "tyqGw-1VjtA", "reviewer": "Reviewer_dVWY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The re-formulation of the active learning problem into a sparse approximation problem is interesting (which I haven't seen elsewhere before). The empirical results also show advantages of the proposed method (under certain approximations) over existing ones. The paper is generally well-written. I summarize my concerns as follows.\n\n1. Is it true that the authors implicitly assume that they are studying the problem in a realizable case where there is no labeling noise in the Y domain?\n2. The sparse approximation problem aims to optimize over $w \\in {\\mathbb R}^{n_u}_{+}$. However, it seems to me that it's more like optimizing over $w \\in \\{0, 1\\}^{n_u}$? Otherwise, Eq (9) doesn't really make sense to me, e.g., what does it really mean to have $w_j = 0.01$?\n3. The proposed method focuses on the batched active learning setting, what would happen in the case of sequential labeling?", "summary_of_the_paper": "This paper formulate the batched active learning problem as a sparse approximation problem. The authors also provide algorithms to solve the sparse approximation problem. Empirical evaluations show the advantages of the proposed methods.", "summary_of_the_review": "Based on the main review above, I vote for a weak rejection of the current version.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "auks8l8N9R-", "reviewer": "Reviewer_ECiF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The formulation of batch active learning as sparse approximation is interesting and seems novel.\n* The paper considers two choices for the norm for Bayesian and non-Bayesian settings.\n\n\nWeaknesses:\n* The formulation between batch active learning and sparse approximation requires a series of approximations. \n* In short, there are multiple approximation techniques used in this paper while the empirical gain is minimal. Random approach performs extremely well for batch active learning task without relying on complex computation.\n* Missing a key comparison with Batch BALD. Note that the performance of BALD with $b>1$ is different from BatchBALD with $b>1$ as showed in [1].\n\nComments/Questions:\n* Since the original objective function is intractable. The paper proposes to minimize the upper bound. However, the approximation relies on the tightness of the upper bound. It is questionable about the gap in Eq. (7).\n\n* Then the final approximation form is nonconvex sparsity constraint and discontinuous objective function. To solve this approximation, the paper utilizes two approximation algorithms including the greedy and the iterative hard thresholding to optimize the objective function.\n\n* In Eq (11), the variance term (right handside) will tend to enforce $w_j=0$ as much as possible. The effect is similar in using L0 regularisation.\n* where $\\alpha$ in Eq. (15) comes from?\n\n\nSuggestions:\n* Ablation study with respect to the batch size b\n* while the reviewer has seen the ablation study of trading-off uncertainty and representation (E.1), the reviewer thinks it may be useful to empirically study the performance w.r.t. different choice of $\\alpha$.\n\nPresentation:\n* The paper is in general well written and easy to follow.\n\nReproducibility:\n* The results appear to be reproducible. The code is included in the appendix.\n\n[1] Kirsch, A., Van Amersfoort, J. and Gal, Y., 2019. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in neural information processing systems, 32, pp.7026-7037.\n\n", "summary_of_the_paper": "The paper proposes SABAL as a framework to formulate batch active learning as a sparse approximation problem. The paper considers the SABAL framework as a finite-dimensional optimization problem, efficiently solvable by the proposed greedy or proximal IHT algorithms. \n\nNumerical experiments demonstrate the strong performance of SABAL, comparable to the state-of-the-art with lower time complexity.\n\nSince directly optimising the original objective function is intractable, SABAL proposes to optimise (minimise) the upper bound which is obtained by the triangle inequality including the (i) variance and (ii) approximation bias.\n", "summary_of_the_review": "Active learning is helpful to acquire labelled data for supervised learning. Formulating the batch active learning as sparse approximation problem is interesting.\n\nHowever, the reviewer has three main concerns: (i) while the maths looks correct, there are a lot of approximations used in finding the solution. These approximations may affect the overall performance and hinder the applicability of the paper. (ii) the empirical performance is minimal comparing to the random baseline. (iii) missing the key comparison to Batch BALD [1].\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MEVYUs0pXuX", "reviewer": "Reviewer_3Nq2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: This work decompose the upper bound of the sparse approximation problem as bias and variance terms, which naturally provides the uncertainty and representativeness during AL processes. By transforming the sparse approximation problem to finite-dim optimization problem, and solve w to implement subset selection of AL. The idea is interesting and novel.\n\nWeaknesses: my questions focused on the experimental part.\n\n1) The quota of different experiments are inconsistent, i.e., in Figure 1, the quota on CIFAR10 dataset is 18000, while in Figure 2, the quota of CIFAR10 is 23000. The change of quota would influence the value of AUC score.\n2) For the chosen of baseline, why not employ BatchBALD[1] instead of BALD? SABAL should compare with hybrid AL sampling strategies, BatchBALD would be more suitable for comparison.\n3) From the experimental results, although SABAL reduce the acquisition time, the improvement of performance is marginal. However, there is no shortage of AL algorithms that perform better and run faster, e.g., WAAL [2]. WAAL achieved significant performance improvement, while the acquisition time cost is low (see Table 1 in [2]).\n\nReferences:\n\n[1] Kirsch A, Van Amersfoort J, Gal Y. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning[J]. Advances in neural information processing systems, 2019, 32: 7026-7037.\n\n[2] Shui C, Zhou F, Gagné C, et al. Deep active learning: Unified and principled method for query and training[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2020: 1308-1318.", "summary_of_the_paper": "This work formulated batch active learning as sparse approximation problem and provided bayesian & non-bayesian versions of their framework. Experimental results shows their effectiveness of reducing the acquisition time, especially when compare with other hybrid AL sampling strategies, such as BADGE.", "summary_of_the_review": "This paper provides a novel perspective of combining uncertainty and representativeness criteria together in deep active learning. However, the performance gain compared with baseline models is marginal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8I_KImWAaUG", "reviewer": "Reviewer_DQaH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the algorithm features favorable empirical results and a nice conceptual framework, I have some concerns about the details of the algorithm algorithm and evaluation.\n\nHow are \\alpha, \\beta, and \\tau chosen? Are they optimized for each dataset? If so, this may be a major drawback of the proposed method.\n\nThis optimization seems to have many heuristics and approximations: the choice of norm for the Bayesian and non-Bayesian settings, the L2 regularization, \"squaring all of the terms for the ease of optimization\", the \"de-biasing\" step, and using only the neural network's last layer. It would be very helpful if the effect of these approximations could be bounded or quantified. I'm concerned about the scenario that heuristics were added to the algorithm until the algorithm worked well, rather than being theoretically motivated.\n\nIf only using the neural network's last layer, isn't the loss convex, and it'd be better to match the loss optimizer rather than the loss (which is indirect), at least in the non-Bayesian setting?\n\nWhy are the dataset for the Bayesian setting (Fashion MNIST, CIFAR 10, CIFAR 100) different from the non-Bayesian setting (MNIST, SVHN, CIFAR 10)? Is it possible that all methods could be run on the 5 datasets presented?", "summary_of_the_paper": "This paper provides a framework which attempts to find a weighted subset of the unlabeled pool that matches the loss on all the points. This paper introduces a seminorm on the loss functions and proposes an optimization method to minimize this. Somewhat favorable results are shown for vision datasets.", "summary_of_the_review": "Without the above concerns addressed, this paper could have major drawbacks. Thus, for the time being, I'm recommending rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a batch active learning approach (where in each active learning round, instead of a single input, we wish to select several inputs to be labeled). The paper attempts to solve this problem by posing it as a sparse approximation problem and shows that their approach performs favorably as compared to some of the existing methods such as BALD and Bayesian Coresets for batch active learning.

While the reviewers appreciated the basic idea and the general framework, there were several concerns from the reviewers (as well as myself upon reading the manuscript). Firstly, the idea of batch active learning as a sparse subset selection problem is not new (Pinsler et al, 2019). While previous methods such as (Pinsler et al, 2019) have used ideas such as Coresets, this paper uses sparse optimization techniques such as Greedy and IHT. Moreover, there were concerns about experimental settings relying on various heuristics, and lack of a more extensive and thorough comparison with important baselines, such as BatchBALD and others, which the authors acknowledged.

The reviewers have read the authors' response and engaged in discussion but their assessment remained unchanged. Based on their assessment and my own reading of the manuscript, the paper does not seem to be ready for publication. The authors are advised to consider the points raised in the reviews which I hope will help strengthen the paper for a future submission.
Decision: Reject