SABAL: SPARSE APPROXIMATION-BASED BATCH ACTIVE LEARNING
Year: 2021

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.

heading: 1 INTRODUCTION
text: Over the last decade, deep neural networks have achieved promising results in various learning tasks. However, obtaining labels for a 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 et 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 a 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 as the query strategy, is the key problem in active learning.
A common strategy is to take the prediction uncertainty or data representation as the metric for data query. This uncertainty-based 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 to 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 a general method for both Bayesian and non-Bayesian models.
For deep models, it is reasonable to query a large batch of data simultaneously to reduce model update frequency. The batch selection approach is known as batch active learning. Taking an optimization perspective, finding the best batch is NP-hard in general. Two common approaches for such combinatorial problems are the greedy and clustering approaches. Greedy algorithms
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 as submodularity (Nemhauser et al., 1978) are required to guarantee a 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 et al. (2019) that focus on the Bayesian models, so far active learning has rarely been studied from a sparse approximation perspective. This is 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, i.e., 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 as an efficient finite-dimensional optimization problem: First, we derive an upper bound to balance the trade-off between uncertainty and representation in a principled way. Second, we approximate the loss functions using finite-dimensional approximation. This results in a sparsity-constrained discontinuous optimization problem, for which we propose several efficient optimization algorithms. We demonstrate the advantages of SABAL in experiments for both Bayesian and non-Bayesian batch active learning settings.
The structure of this manuscript is as follows. In Section 2, we formulate the general framework of SABAL, and in Section 3, we realize the framework into a 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 C.

heading: 2 BATCH ACTIVE LEARNING AS SPARSE APPROXIMATION
text: This section introduces the preliminaries and the general formulation of batch active learning as a sparse approximation problem.
Preliminaries Vectors are denoted as bold lower case letters, e.g., w ∈ Rn. The l0 pseudonorm of a vector w is denoted as ‖w‖0, i.e., the number of non-zero elements of w. We denote R+ := [0,+∞). Distributions are denoted in script, e.g., P , and a random variable is denoted by tilde, e.g., ỹ ∼P . We denote sets in calligraphy or in uppercase Greek alphabet (e.g., D,Θ), and additionally we denote [n] := {1, 2, . . . , n}. In supervised learning, given a labeled training dataset Dl := {(xi,yi)}nli=1, where we denote their domain to be x ∈ X and y ∈ Y , the empirical goal is to minimize a loss function Ll(θ) := ∑ (xi,yi)∈Dl `(xi,yi;θ) formed by the training dataset, where θ ∈ Θ ⊂ Rm is the parameter of the model and ` is a loss function evaluated on individual pairs of data. Without loss of generality, we assume Θ ⊂ Rm is compact and `(x,y; ·) : Θ→ R is in a normed space (L(Θ,R), ‖ · ‖†) for all x,y. We further assume the constant function f : Θ→ 1 is included in L(Θ,R). The “†” in the norm ‖ · ‖† : L(Θ,R) → R+, representing its definition is a placeholder that will be discussed later.
Batch Active Learning Besides the labeled dataset Dl, there is an unlabeled dataset Du := {xj}nuj=1 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. θ is∑
(xi,yi)∈Dl `(xi,yi;θ) + ∑ xj∈Du `(xj ,y ? j ;θ), (1)
where y?j is the unknown true label corresponding to the data xj . Since acquiring true labels could be costly, we have to impose a budget b (b < nu) on the number of label acquisitions. Therefore, the batch active learning problem is to find a subset S ⊂ Du such that we can obtain a good model by optimizing the following loss function w.r.t. θ,∑
(xi,yi)∈Dl `(xi,yi;θ) + ∑ xj∈S `(xj ,y ? j ;θ), where |S| = b. (2)
Generalized Batch Active Learning We start our method by generalizing the classical formulation (equation 2) by considering an importance weight for each unlabeled data. That is, we aim to find a sparse non-negative vector w ∈ Rnu+ such that we can obtain a good model by optimizing the following loss function w.r.t. θ:∑
(xi,yi)∈Dl `(xi,yi;θ) + ∑ xj∈Du wj`(xj ,y ? j ;θ), where ‖w‖0 = b. (3)
A key question now is—what is the criterion for a 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, a straight-forward informal criterion for a good importance weight w is that the two unlabeled data loss functions are close to each other, i.e.,
L?w(θ) := 1
b ∑ xj∈Du wj`(xj ,y ? j ;θ) ≈ L?(θ) := 1 nu ∑ xj∈Du `(xj ,y ? j ;θ).
However, as the true labels are unknown, we cannot compute L?w and L ?. Luckily, we can have an estimator for the true labels, i.e., estimation based on the labeled data p(ỹj | xj ,Dl) or an approximation of it. Denote P(xj) as an estimated distribution, so ỹj ∼P(xj), then the informal criterion for a good importance weight w then becomes
L̃w(θ) := 1
b ∑ xj∈Du wj`(xj , ỹj ;θ) ≈ L̃(θ) := 1 nu ∑ xj∈Du `(xj , ỹj ;θ). (4)
Thus, we are one step closer to evaluating the quality of a weighted selection. The next question is how to measure the difference between L̃ and L̃w.
Difference Between Two Loss Functions Given the two loss functions L̃, L̃w ∈ L(Θ,R), where L(Θ,R) is equipped with the norm ‖ · ‖†, a straight-forward measurement of the difference between them is ‖L̃− L̃w‖†. However, observing that the optimization of a loss function is shift-invariant, the difference between two loss functions should also be shift-invariant. For example, for ∀L ∈ L(Θ,R) we have arg minθ∈Θ(L(θ) + c) = arg minθ∈Θ L(θ) for ∀c ∈ R, implying that L + c should be treated the same as L. Therefore, to account for the shift-invariance, we define q : L(Θ,R)→ R+ as
q(L) := inf c∈R ‖L+ c‖†, ∀L ∈ L(Θ,R). (5)
Note that we abuse the notation a bit, i.e., the c in L+ c should be the constant function that maps every θ ∈ Θ to c. The above definition has some nice properties that make it a good difference measurement of two loss functions, as proved in proposition C.1 in the appendix. In particular, q(·) satisfies the triangle inequality, and q(L+ c) = q(L) for any constant c. Therefore, we can formulate the generalized batch active learning problem as the following sparse approximation problem.
Problem 1 (Sparse Approximation-based Batch Active Learning). Given the shift-invariant seminorm q induced by the norm ‖ · ‖† (equation 5), and a label estimation distribution P , the generalized batch active learning problem (equation 4) is formally defined as
arg min w∈Rnu+
EP [q(L̃− L̃w)] s.t. ‖w‖0 = b, (6)
where EP stands for the expectation over ỹj ∼P(xj) for ∀j ∈ [nu].
Problem 1 (SABAL) offers a 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-Bayesian active learning respectively.

heading: 3 SPARSE APPROXIMATION AS FINITE-DIMENSIONAL OPTIMIZATION
text: In this section, we transform the sparse approximation problem (equation 6) into a finite-dimensional sparse optimization problem. First, we address an issue regarding the sampling of EP . Then, we discuss some concrete choices of P and ‖ · ‖† that lead to a finite-dimensional sparse optimization.
Addressing the Sampling Issue In equation 6, the expectation EP is taken over the product space of (ỹ1, . . . , ỹnu) and each sample has to be remembered for future optimization, which can be intractable for large datasets. However, it has an upper bound where the complexity of the optimization is independent of the number of samples from P . First, by the triangle inequality EP [q(L̃− L̃w)] = EP [q(L̃− EP [L̃] + EP [L̃]− EP [L̃w] + EP [L̃w]− L̃w)]
≤ EP [q(L̃− EP [L̃])] + EP [q(L̃w − EP [L̃w])]︸ ︷︷ ︸ (i): variance + q(EP [L̃]− EP [L̃w])︸ ︷︷ ︸ (ii): approximation bias . (7)
We can see that it offers a trade-off between bias and variance, where the bias term is immediately tractable by expanding L̃, L̃w:
(ii) = q(EP [ 1nu ∑ xj∈Du `(xj , ỹj ; ·)]− EP [ 1 b ∑ xj∈Du wj`(xj , ỹj ; ·)])
= q(( 1nu ∑ xj∈Du EP(xj)[`(xj , ỹj ; ·)])− ( 1 b ∑ xj∈Du wjEP(xj)[`(xj , ỹj ; ·)])). (8)
It remains to address the variance term (i). Recall that the more accurate P is, the more accurate our approximation is. Given the decision wj > 0, if the label of xj is acquired, i.e., the oracle (human annotator) will offer us its true label y?j , and the labeling distribution would be improved. That being said, the distribution of ỹj given xj and wj > 0 will be concentrated on its true label y?j , i.e.,
ỹj ∼Pw(xj) := { P(xj) if wj = 0 δy?j if wj > 0 , where w ∈ Rnu+ (9)
where δy?j denotes the distribution that ỹj can only be y ? j . However, the improved distribution Pw is not known before the acquisition of the true labels y?j for wj > 0. Fortunately, although Pw(xj) is not known, it is known that the corresponding variance for ỹ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 ∈ Rnu+ and ‖w‖0 = b, by replacing the P by the improved estimation distribution Pw (equation 9) into (i) in equation 7, we have
EPw [q(L̃− EPw [L̃])] + EPw [q(L̃w − EPw [L̃w])] ≤ ∑ xj∈Du 1(wj = 0) · σj , (10)
where σj := 1nuEP(xj)[q(`(xj , ỹj ; ·)− EP(xj)[`(xj , ỹj ; ·)])] is the individual variance, and 1(·) is the indicator function.
Therefore, combining equation 8 and equation 10, we have a more tractable form of the sparse approximation, i.e.,
arg min w∈Rnu+ q(EP [L̃]− EP [L̃w]) + ∑ xj∈Du 1(wj = 0) · σj s.t. ‖w‖0 = b, (11)
Intuitively, such decomposition of bias and variance naturally provides metrics of uncertainty and representation for active learning, where the variance itself is a metric of uncertainty, meanwhile the bias term measures how well a subset of selected data can represent the whole unlabeled data. Now, it remains to specify the choice of ‖ · ‖†, i.e., the norm that induces q (equation 5).
Formulation of the Finite-Dimensional Optimization We consider two concrete choices of the ‖ · ‖† for Bayesian and non-Bayesian settings respectively.
1. In the Bayesian setting, we can easily sample θi ∼ π := p(θ | Dl) from the posterior. Utilizing the posterior, we make the norm ‖ · ‖† more concrete by considering the L2(π)-norm, i.e., ‖L‖2π = Eθ∼π[L(θ)2]. Accordingly,
q(L)2 = inf c∈R ‖L+ c‖2π = inf c∈R Eθ∼π[(L(θ) + c)2] = Eθ∼π[(L(θ)− Eθ∼π[L(θ)])2]. (12)
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 θi ∼ π to approximate it. Denote g := 1√
m [. . . , (L(θi)− L̄), . . . ]>i=1...m ∈ Rm where L̄ := 1m ∑m i=1 L(θi). equation 12 becomes
q(L)2 ≈ 1 m m∑ i=1 (L(θi)− L̄)2 = ‖g‖22, (13)
where ‖g‖2 is simply the Euclidean norm of the m-dimensional vector g.
2. In the non-Bayesian setting, we evaluate the loss function in a local “window” based on the current model. We consider the ‖ · ‖∞-norm over a Euclidean ball Br(θ0) of radius r centered at the current model parameter θ0, i.e., ‖L‖∞ = maxθ∈Br(θ0) |L(θ)|. Moreover, in the Euclidean ball we approximate L(θ) ≈ L(θ0) +∇L(θ0)>(θ − θ0). Therefore, we have
q(L) = inf c∈R ‖L+ c‖∞ = inf c∈R max θ∈Br(θ0) |L(θ) + c|
≈ inf c∈R max θ∈Br(θ0) |L(θ0) +∇L(θ0)>(θ − θ0) + c| = r‖∇L(θ0)‖2. (14)
Note that ‖∇L(θ0)‖2 is the Euclidean norm of the gradient vector∇L(θ0) ∈ Rm.
To estimate the label distribution, P(xj) = p(ỹj | xj ,Dl) can be directly applied on Bayesian models by estimating the predictive model posterior. For non-Bayesian models, one could utilize the calibrated model prediction (Guo et al., 2017) as the label distribution. Finally, plugging either of the two approximations of q(L) into equation 11, and squaring all of the terms for the ease of optimization, we can formulate the sparse approximation problem as the following finite-dimensional optimization problem, where α > 0 offers a trade-off between bias and variance.
arg min w∈Rnu+ ‖v − Φw‖22 + α ∑ xj∈Du 1(wj = 0) · σ2j s.t. ‖w‖0 = b, (15)
where we denote v ∈ Rm, Φ ∈ Rm×nu and σj as
v := 1
nu nu∑ j=1 EP(xj)[gj(ỹj)], Φ := 1 b (EP(x1)[g1(ỹ1)], . . . ,EP(xnu )[gnu(ỹnu)]),
σj = 1
nu EP(xj)[‖gj(ỹj)− EP(xj)[gj(ỹj)]‖2],
gj(ỹj) :=
{ [. . . , (`(xj , ỹj ;θi)− ¯̀), . . . ]>i=1...m, ¯̀ := 1m ∑m i=1 `(xj , ỹj ;θi) if use (13)
∇`(xj , ỹj ;θ0) if use (14). (16)
In practice, it is often the case that the number of parameters is less than the number of samples, i.e., m < nu, even for over-parameterized neural networks where the gradient of the last layer is commonly used to represent the full-model gradient (Katharopoulos & Fleuret, 2018; Ash et al., 2019). Therefore, if the batch size is big, i.e., b > m, the approximation bias ‖v − Φw‖22 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 `2 regularizer β‖w − 1‖22 with β > 0. Finally, since wj ≥ 0, minimizing α ∑ xj∈Du 1(wj = 0) · σ 2 j is equivalent to minimizing
−α ∑ xj∈Du 1(wj > 0) · σ 2 j . 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 w∈Rnu+ ‖v − Φw‖22 − α ∑ xj∈Du 1(wj > 0) · σ2j + β‖w − 1‖22 s.t. ‖w‖0 = b. (17)
While simplified, the result is a 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.

heading: 4 OPTIMIZATION ALGORITHMS
text: This section focuses on optimizing Problem 2. Rewrite equation 17 f(w) := f1(w) + f2(w), where f1(w) := ‖v − Φw‖22 + β‖w − 1‖22, f2(w) := −α ∑ xj∈Du 1(wj > 0) · σ 2 j .
The optimization has two major difficulties, i.e., the nonconvex sparsity constraint ‖w‖0 = b and the discontinuous objective function f2. When it comes to sparsity-constrained optimization, there are
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 0. For an index j, we denote gj or (g)j to be its jth element. For an index set S, we denote [g]S to be the vector where ([g]S)j = (g)j if j ∈ S and ([g]S)j = 0 if j /∈ S. Moreover, we denote ej to be the unit vector where (ej)j = 1 and (ej)i = 0 for ∀i 6= j. Although two algorithms use different schemes, they share the same two sub-procedures: a line search and de-bias step (Algorithm 4 and 5 in Appendix D), which significantly improve the optimization performance (Zhang et al., 2021). The line search sub-procedure optimally solves the problem arg minµ∈R f1(w − µu), i.e., given a direction u, what is the best step size µ to move the w along u. The de-bias sub-procedure adjusts a sparse w in its own sparse support for a better solution.
Algorithm 1: SABAL-Greedy Parameter: sparsity b; step size τ .
1 w ← 0; S ← ∅ 2 repeat 3 j ← arg min
j∈[nu]\S τ(∇f1(w))j − ασ2j
4 S ← S ∪ {j} (update selection) 5 µ← LineSearch(ej ,w) 6 w ← De-bias(w − µej) 7 wj ← 0 for ∀wj < 0 (w ∈ Rnu+ ) 8 until |S| = b;
Return: w
Algorithm 2: SABAL-IHT Parameter: sparsity b; number of iterations T .
1 w ← 0; z ← 0 2 repeat 3 w′ ← w (save previous w) 4 µ← LineSearch(∇f1(z), z) 5 s← z − µ∇f1(z) (gradient descent) 6 w ← arg min
w∈Rnu+ ,‖w‖0≤b
1 2‖w−s‖ 2 2 +f2(w)
7 w ← De-bias(w) 8 wj ← 0 for ∀wj < 0 (w ∈ Rnu+ ) 9 τ ← LineSearch(w −w′,w)
10 z ← w − τ(w −w′) (momentum) 11 until T iterations;
Return: w
Opt. Algorithm: Greedy The core idea of the greedy approach is noted in line 3 Algorithm 1, where it chooses an index j to move a step of size τ that minimizes the objective, i.e., j ← arg minj∈[nu]\S (f1(w + τe
j)− f1(w)) + (f2(w + τe
j) − f2(w)). By approximating f1(w+ τej)−f1(w) by its firstorder approximation 〈∇f1(w), τej〉, and noting that f2(w + τej)− f2(w) = −ασ2j , we have the greedy step (line 3) in Algorithm 1. After choosing the index j to include, line 5 chooses an optimal step to move, followed by a de-bias step that further improves the solution in the current sparse support supp(w).
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 discontinuous f2 in a 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 optimally by simply picking the top-b elements from nu elements. After this core step, a debias step improves the solution w within its sparse support, followed by a momentum step.
Complexity Analysis We analyze the time complexity of the proposed algorithms with respect to the number of data samples n, and the batch size b of batch active learning. Except for line 6 Algorithm 2, all steps are of time complexity O(n). The line 6 Algorithm 2 is finding the b smallest elements, which can be done in O(n log(b)). Therefore, the time complexity for SABAL-Greedy is O(nb), and the time complexity for SABAL-IHT is O(n log(b)). Comparing to the time complexity O(nb2) of the state-of-the-art method BADGE (Ash et al., 2019), the two proposed algorithms can be much faster, especially with a large batch size b used in practice.

heading: 5 RELATED WORK
text: 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-Bayesian settings. (3) it
formulates data acquisition as a sparse approximation problem. This section focuses on 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 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 a discriminator in an adversarial fashion. The discriminator predicts a 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 is 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 a feature space. It derives an upper bound for the coreset loss based on the Lipschitz continuity and transforms the original problem to a 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-posterior approximates the full-set logposterior, 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 is non-trivial for non-Bayesian models. In constrast, we propose SABAL, which characterizes the closeness in a more general sense, i.e., through a semi-norm function directly on the difference between the coreset loss function and the full-set loss function.

heading: 6 EXPERIMENT RESULTS
text: 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-art methods. We also conduct an ablation study to show how SABAL balances the trade-offs between uncertainty and representation in Appendix E.1.
We have a 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 as a 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 baselines in literature: (1) Random: A naive baseline that selects a batch of data uniformly at random. (2) BALD (Houlsby et al., 2011): An uncertaintybased Bayesian method that selects a batch of data with maximum mutual information between model parameters and predictions. (3) Entropy (Wang & Shang, 2014): An uncertainty-based non-Bayesian method that selects a batch of data with maximum entropy of the model predictions H (yi | xi;θ). (4) KCenter (Sener & Savarese, 2017): A representation-based non-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 a diverse batch of data using the k-MEANS++ seeding algorithm.
(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), CIFAR10 (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 a 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(ỹj | xj ,Dl) are estimated using 100 samples. Equation 13 is used to solve the finitedimensional 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-the-art 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-100, two more complicated datasets, we use 2000 samples for random projections, 3000 (10000 for CIFAR100) seed data, and query 5000 samples for 4 iterations. Because Bayesian Coreset usually finds a much smaller batch than requested, for a fair comparison, we let Bayesian Coreset acquire more data than the batch size, and stop the acquisition as long as it has selected a 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, we find SABAL-Greedy performs better than SABAL-IHT while outperforming other baselines, including the Bayesian Coreset, one of the current state-of-the-art 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-Greedy SABAL-IHT BALD Random
Fashion MNIST 89.53± 0.25 89.83± 0.26 89.97± 0.23 89.72± 0.23 88.39± 0.32 CIFAR10 77.73± 0.70 78.28± 0.53 77.55± 0.83 77.61± 0.59 76.36± 0.59 CIFAR100 42.40± 0.29 42.53± 0.34 42.30± 0.29 41.99± 0.60 42.10± 0.24
Figure 1: Active learning results on Bayesian models. Solid lines and shaded areas 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 convolutional neural networks, including LeNet-5 (LeCun et al., 2015) and VGG-16 (Simonyan & Zisserman, 2014) architectures without any Bayesian layers, using MNIST (LeCun et al., 1998), SVHN (Netzer et al., 2011), 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(ỹj | xj ,Dl). 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-Bayesian baselines: Random, Entropy, KCenter, and BADGE.
To evaluate the performance of SABAL, on MNIST dataset with LeNet-5 model, we use 40 seed 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,
and query 1000 (3000 for CIFAR-10) samples for 5 iterations. The results are shown in Table 2 and Figure 2. In general, SABAL-Greedy 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 on large models. In addition, most methods perform similarly on CIFAR-10, and we conjecture that for CIFAR-10 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.
Dataset BADGE SABAL-Greedy SABAL-IHT KCenter Entropy 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 SVHN 86.92± 0.71 87.23± 0.47 86.84± 0.57 87.04± 0.80 86.28± 1.05 85.52± 0.51 CIFAR10 68.20± 0.56 68.01± 0.66 67.80± 0.69 67.98± 0.63 67.94± 0.64 67.05± 0.59
Figure 2: Active learning results on general (non-Bayesian) 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 in non-Bayesian active learning experiment as an example. Here, we 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 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.

heading: 7 CONCLUSION
text: We introduce the SABAL as a novel framework that formulates batch active learning as a sparse approximation problem. It balances representation and uncertainty in a principled way, and has the flexibility to adapt to both Bayesian and non-Bayesian models. We realize the SABAL framework as a finite-dimensional optimization problem, efficiently solvable by the proposed greedy or proximal IHT algorithms. Numerical experiments demonstrate the strong performance of SABAL, comparable to the state-of-the-art with lower time complexity. For the future works, although the hyperparameter α 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, as well as other instantiations of our general framework, would also have the potential to inspire discoveries of even better batch active learning algorithms.

heading: 8 ETHICS STATEMENT
text: 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.

heading: 9 REPRODUCIBILITY STATEMENT
text: 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 in the Appendix.

heading: A THE OVERALL PROCEDURE
text: Algorithm 3: SABAL: Sparse Approximation-based Batch Active Learning Input: Intial parameters θ, initial unlabeled pool Du, initial labeled pool Dl = ∅, initial number
of samples b0, query batch size b, number of iterations T . 1 Query a random batch S0 of b0 data from Dl, update Du ← Du\S0 and Dl ← Dl ∪ S0. 2 Train the model using S0. 3 for t = 1, 2, . . . , T do 4 For each data xj ∈ Du, estimate its label distribution ỹj ∼P(xj). 5 Compute vector gj by sampling or gradient embedding using 16. 6 Compute v, Φ, and σj for each xj ∈ Du and form equation 17. 7 Find sparse weight w s.t. ‖w‖0 = b as specified in section 4. 8 Select a batch of data St = {xj ∈ Du | wj > 0} and query their labels. 9 Update Du ← Du\St and Dl ← Dl ∪ St.
10 Reinitialize and retrain the model using updated Dl, update model parameters θ 11 end
Return: Final model parameters θ.

heading: B MORE RELATED WORK
text: 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), we will briefly review some recent works in deep active learning.
Existing query strategies can mainly be categorized as uncertainty-based and representation-based. Uncertainty-based approaches look for data samples the model is 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) as an approximation of performing Bayesian inference, and enables efficient uncertainty estimations in neural networks. Gal et al. (2017) utilizes MC Dropout for approximating posterior distributions and adapts Houlsby et al. (2011) as their uncertainty based acquisition function, and similarly, Kirsch et al. (2019) proposes a batch-mode approach based on Gal et al. (2017) and shows some improvements through a more accurate measurement of mutual information between the data batch and model parameters. While MC Dropout becomes prevalent for uncertainty estimation, Beluch et al. (2018) shows ensemble-based methods lead to 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 metrics: 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 a cost-efficient strategy by pseudo labeling the confident samples.
Representation-based approaches attempt to query diverse data samples that could best represent the overall unlabeled dataset. A 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 a k-Center problem in the feature space. In Geifman & El-Yaniv (2017), the authors also explore the deep active learning with core-sets, but build the core-sets in the farthest-first compression scheme.

heading: C PROOFS
text: Proposition C.1. q : L(Θ,R) → R+ defined in (5) is a shift-invariant seminorm satisfying the following properties:
1. q(L1 + L2) ≤ q(L1) + q(L2) for ∀L1, L2 ∈ L(Θ,R); (triangle inequality)
2. q(cL) = |c|q(L) for ∀L ∈ L(Θ,R),∀c ∈ R; (absolute homogeneity)
3. q(L+ c) = q(L) for ∀L ∈ L(Θ,R),∀c ∈ R; (shift-invariance)
4. q(L) = 0 if and only if L maps every θ ∈ Θ to a constant.

heading: In other words, q defines a norm in the space of shift-equivalence classes of loss functions.
text: Proof. Recall that
q(L) := inf c∈R ‖L+ c‖†, ∀L ∈ L(Θ,R).
We prove the four properties respectively in the following.
1. The triangle inequality is inherited from the sub-additivity of the norm ‖ · ‖†. For ∀L ∈ L(Θ,R), we have
q(L1 + L2) = inf c∈R ‖L1 + L2 + c‖† = inf c1,c2∈R ‖L1 + L2 + c1 + c2‖†
≤ inf c1,c2∈R ‖L1 + c1‖† + ‖L2 + c2‖†
= (inf c∈R ‖L1 + c‖†) + (inf c∈R ‖L2 + c‖†)
= q(L1) + q(L2).
2. The absolute homogeneity is also inherited from the absolute homogeneity of the norm ‖ · ‖†. The case for c = 0 is obvious, and for c 6= 0 we have
q(cL) = |c|q(L) = inf c1∈R ‖cL+ c1‖† = inf c1∈R |c| · ‖L+ c1/c‖†
= inf c2∈R
|c| · ‖L+ c2‖† = |c|q(L).
3. By the definition of q(·), we have the shift-invariance of q(·).
4. The “if” part can be proved by definition, i.e., q(c) = infc1∈R ‖c1 + c‖† = ‖0‖† = 0. For the “only if” part, we need to be more rigorous by defining fc to be the function that maps Θ to c ∈ R. We further define F := {fc | c ∈ R} ⊂ L(Θ,R), and we can see (F , ‖ · ‖†) is a one-dimensional normed space. Letting L ∈ L(Θ,R) and q(L) = 0, we have
inf fc ∈F
‖L+ fc‖† = 0.
Therefore, for ∀ > 0, ∃c ∈ R such that
‖L+ fc ‖† ≤ =⇒ ‖fc ‖† = ‖L+ fc − L‖† ≤ + ‖L‖†.
That being said, for 0 < < 1, we have ‖fc ‖† ≤ 1 + ‖L‖†. Denote B = {fc ∈ F | ‖fc‖† ≤ 1 + ‖L‖†}, and we can see B is a closed ball in F . As F is one-dimensional, by Riesz’s lemma we have B compact. As lim →0 ‖L + fc ‖† = 0, i.e., fc → L, by the compactness of B we have L ∈ B. Therefore, L is also a constant function. Note that this conclusion does not require L(Θ,R) to be complete.
Proposition C.2 (Proposition 3.1 Restated). Asw ∈ Rnu+ and ‖w‖0 = b, by replacing the P by the improved estimation distribution Pw (equation 9) into (i) in equation 7, we have
EPw [q(L̃− EPw [L̃])] + EPw [q(L̃w − EPw [L̃w])] ≤ ∑ xj∈Du 1(wj = 0) · σj ,
where σj := 1nuEP(xj)[q(`(xj , ỹj ; ·)− EP(xj)[`(xj , ỹj ; ·)])] is the individual variance, and 1(·) is the indicator function.
Proof. Recall that
L̃w(θ) := 1
b ∑ xj∈Du wj`(xj , ỹj ;θ), L̃(θ) := 1 nu ∑ xj∈Du `(xj , ỹj ;θ),
ỹj ∼Pw(xj) := { P(xj) if wj = 0 δy?j if wj > 0 , w ∈ Rnu+ ,
where δy?j denotes the distribution that ỹj can only be y ? j . Therefore, by the definition of Pw, we have
EPw(xj) [ q ( `(xj , ỹj ; ·)− EPw(xj)[`(xj , ỹj ; ·)] )] = 0, if wj > 0.
Plugging the above definitions into EPw [q(L̃w − EPw [L̃w])] we have
EPw [q(L̃w − EPw [L̃w])] = EPw q  1 nu ∑ xj∈Du wj ( `(xj , ỹj ; ·)− EPw(xj)[`(xj , ỹj ; ·)] ) = EPw q  1 nu ∑ xj∈Du 1(wj > 0)wj ( `(xj , ỹj ; ·)− EPw(xj)[`(xj , ỹj ; ·)] ) = 0. (18)
Therefore, we only need to care about the EPw [q(L̃− EPw [L̃])].
EPw [q(L̃− EPw [L̃])] = EPw q  1 nu ∑ xj∈Du `(xj , ỹj ; ·)− EPw(xj)[`(xj , ỹj ; ·)]  ≤
∑ xj∈Du 1 nu EPw(xj) [ q ( `(xj , ỹj ; ·)− EPw(xj)[`(xj , ỹj ; ·)] )] =
∑ xj∈Du 1(wj = 0) 1 nu EP [ q ( `(xj , ỹj ; ·)− EP(xj)[`(xj , ỹj ; ·)] )] =
∑ xj∈Du 1(wj = 0) · σj , (19)
where the inequality is by the triangle inequality and the absolute homogeneity of q(·) (Proposition C.1). Combining equation 18 and equation 19, we have the proposition proved.

heading: D OMITTED ALGORITHMS
text: 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), as well as 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µ∈R f1(w−µu), 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 a sparse w in its own sparse support for a better solution.
Algorithm 4: LineSearch(u,w) Input: direction u; starting point w. Output: step size µ.
1 µ← 〈Φw−v,Φu〉+β〈w−1,u〉‖Φu‖22+β‖u‖22 (optimal µ) Return: µ
Algorithm 5: De-bias(w) Input: starting point w. Output: improved w.
1 u← [∇f1(w)]supp(w) (in-support grad.) 2 µ← LineSearch(u,w) 3 w ← w − µu (in-support adjustment)
Return: w
Recall the inner optimization (line 6) of Algorithm 2 is
w ← arg min w∈Rnu+ ,‖w‖0≤b 1 2‖w − s‖ 2 2 + f2(w).
Noting that 12‖w−s‖ 2 2 +f2(w) = ∑ j∈[nu]( 1 2 (wj−sj)
2−ασ2j ), this step can be done optimally by simply picking the top-b elements, as shown in the following. Given a b-sparse support set S ⊂ [nu], we can see that
min w∈Rnu+ ,supp(w)⊆S
∑ j∈[nu]( 1 2 (wj − sj) 2 − ασ2j ) = ∑ j∈S( 1 2 [−sj ] 2 + − ασ2j ).
Therefore, line 6 in Algorithm 2 can be done by: (1) find the b smallest ( 12 [−sj ] 2 + − ασ2j ), denoting the resulting b-sparse index set as S?; (2) let w ← [[s]S? ]+.

heading: E MORE EXPERIMENT RESULTS
text: 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 formulation 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 α = 0, under both IHT and Greedy optimizations respectively. We take two datasets MNIST and CIFAR-10 in the Bayesian experiment as examples. Results in Figure 3 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.
F IMPLEMENTATION DETAILS
All experiments are written in PyTorch 1.8.1. All hyper-parameters are chosen to ensure models achieve good and stable performance on each dataset, and they are kept identical for all active learning approaches.
F.1 BAYESIAN ACTIVE LEARNING EXPERIMENT
Model Architecture We use the exact same model as (Pinsler et al., 2019), it is a Bayesian neural network consisting of a ResNet-18 (He et al., 2016) feature extractor followed by a fully connected layer with a ReLU activation, and a final layer allows sampling by local reparametrization (Kingma et al., 2015) with a softmax activation.
Optimization and Hyperparameter Selection Due to larger models and more complicated classification tasks, e.g., CIFAR-100, data augmentation(including random cropping and random horizontal flipping) and learning rate scheduler are 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-parameters in experiment
on Bayesian batch active learning, where bs denotes the batch size in dataloader during the model training, lr denotes the learning rate, and wd denotes the weight decay. The hyper-parameters are chosen through grid search.
F.2 GENERAL ACTIVE LEARNING EXPERIMENT
Model Architecture On MNIST dataset, we use LeNet-5 model (LeCun et al., 2015). On SVHN and CIFAR10 datasets, we use VGG-16 model (Simonyan & Zisserman, 2014).
Optimization and Hyperparameter 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 batch active learning, where bs denotes the batch size in dataloader during the model training, lr denotes the learning rate, m denotes the momentum, and wd denotes the weight decay. The hyper-parameters are chosen through grid search.

Review summaries:
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.   Numerical experiments demonstrate the strong performance of SABAL, comparable to the state-of-the-art with lower time complexity.  Since 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. 

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.

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.