Less data is more: Selecting informative and diverse subsets with balancing constraints
Authors: Srikumar Ramalingam
Daniel Glasner
Kaushal Patel
Raviteja Vemulapalli
Sadeep Jayasumana
Sanjiv Kumar
Venue: ICLR 2022 Submitted (2022)
Keywords: subset selection
approximation algorithm
active learning
efficient training

Abstract: Deep learning has yielded extraordinary results in vision and natural language processing, but this achievement comes at a cost. Most models require enormous resources during training, both in terms of computation and in human labeling effort. We show that we can identify informative and diverse subsets of data that lead to deep learning models with similar performance as the ones trained with the original dataset. Prior methods have exploited diversity and uncertainty in submodular objective functions for choosing subsets. In addition to these measures, we show that balancing constraints on predicted class labels and decision boundaries are beneficial. We propose a novel formulation of these constraints using matroids, an algebraic structure that generalizes linear independence in vector spaces, and present an efficient greedy algorithm with constant approximation guarantees. We outperform competing baselines on standard classification datasets such as CIFAR-10, CIFAR-100, ImageNet, as well as long-tailed datasets such as CIFAR-100-LT.

Under review as a conference paper at ICLR 2022
LESS IS MORE: SELECTING INFORMATIVE AND DI- VERSE SUBSETS WITH BALANCING CONSTRAINTS
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep learning has yielded extraordinary results in vision and natural language processing, but this achievement comes a cost. Most models require enormous resources during training. both in terms of computation and in human labeling effort. We show that we can identify informative and diverse subsets of data that lead deep learning models with similar performance the ones trained with the original dataset. Prior methods have exploited diversity and uncertainty in submodular objective functions for choosing subsets. In addition to these measures, show that balancing constraints on predicted class labels and decision boundaries are beneficial. We propose novel formulation of these constraints using matroids, an algebraic structure that generalizes linear independence in vector spaces, and present efficient greedy algorithm with constant approximation guarantees. We outperform competing baselines on standard classification datasets such as CIFAR- 10. CIFAR-I00, ImageNet, as well as long-tailed datasets such 100-R-
INTRODUCTION
Deep learning has shown unprecedented success in many domains, such speech (Hinton al., 2012), computer vision (Krizhevsky et al., 2012; Szegedy et al., 2015; He et al., 2016), and natural language processing (Sutskever et al., 2014; Devlin et al., 2018). This success generally relies on access to significant computational resources and large human annonattd datasets. For example, energy consumption and carbon footprint developing common NLP models are shown to be comparable to the lifetime emissions of a car (Strubell et al., 2019). Similarly, human annotation is also cons-connuming and expensive process; Badrinarayanan et al. (2010) reports that semantic labeling of single video frame takes around 45-60 minutes.
In this paper we ask the following question: Given large unlabeled dataset along with small labeled (seed) dataset and an annotation budget, how do select a subset of the labeled dataset, which, when annotated, will
100
GFAR-10
90
80
mageNet
Top-1 accuracy
70
achieve the best performance? While this is ad- dressed by many classical active learning meth-
60
CIFAR-100
50
ods (Settles, 2009), in this work we focus on the modern deep learning setting with CNNs and very deep networks such ResNets (He al.,
40
CIAR-110-41 100-LT
30
20
2016). Typical active learning methods employ an iterative process where a single image is la- beled and used to update the model at each step. The updated model is then used to pick the next image and
10
30
40
70
80
100
Subset size (%)
Such an approach is not fea- sible for deep networks. We therefore choose to study this problem in batch setting (Sener & Savarese, 2018: Zhdanov, 2019; Shui et al., 2020: Kim al., 2021; Ghorbani et al., 2021). In this setting, we first train an initial model using the labeled seed dataset. We typically use
show the accuracy of ResNer56 mod- els trained on subsets of different sizes, selected using our method on CIFAR-10, CIFAR-100, ImageNet, and CIFAR-100-L Models trained using subsets with 30- 40% less data, achieve similar accuracy to the trained using the full dataset.
Figure

---

Under review as a conference paper at ICLR 2022
randomly selected 10% subset of the full dataset as seed. After this, done in the standard batch-mode active learning setup, our algorithm uses this initial seed model to select a subset of the full dataset for which the labels will be revealed. We then train new model with the selected subset. As shown in Fig. 1, our subset selection methods can identify subsets with 30% to 40% less data, which achieve performance similar what could get training with the full annotated dataset.
Most existing methods for data subset selection use some notion of margin, representativeness, or diversity. For example, the classical margin-baset sampling selects images for which the prediction of the class labels are most uncertain. These could, for example, be the images having smallest difference between the highest and the second highest label probabilities (Lewis & Gale, 1994). Clustering- -ased objectives such as k-center (Sener & Savarese, 2018) or k-medoids (Kaufman & Roussceuw, 1987) select cluster centers with rich representativeness to model the entire dataset. Diverse subsets are identified by casting the problem as the maximization of submodular functions (Wei et al., 2015), which are discrete analogues of convex functions.
We see two main limitations with existing methods. First, there is no single subset selection criterion that achieves the best performance on different classification datasets. For example we observe in our experiments (Sec. 6) that in certain datasets, diversity works better than margin, and vice versa. The second limitation is particularly relevant to margin-based methods where the selection is driven by the closeness of an image to a decision boundary. In classification problem with L labels, we have (5) possible decision boundaries. Most margin- based methods greedily select images close to decision boundaries. This often results in a selection of too many images representing a small number of classes and boundaries, while ignoring many others.
To address the first limitation, we develop a unified algorithm based on maximization a submodular function, which can combine different selection objectives. Importantly, we do this without sacrificing constant approximation guarantees. To address the second limitation, we incorporate class-balancing and boundary-ballaa balancing constraints in our optimization using intersection of matroids. Typical diversity promoting objective functions use an underlying nearest neighbor graph that models the distances between the training samples. In this work, We present an improved diversity objective function that models the simultaneous interaction of three nearby samples, while the standard approach typically considers the interaction of two nearby samples.
To summarize, our contributions are: (1) We develop unified algorithm to combine different objective functions along with balancing and boundary-balanen
constraints using the intersection of matroids. (2) We propose improved diversity objective function based on 3-clique interactions in the nearest neighbor graph. (3) We outperform baseline methods on three standard classification datasets (CIFAR-IO, CIFAR--00, and ImageNet) and long-tailed classification dataset (CIFAR-100- LT).
2 RELATED WORK
Data summarization and submodularity: Submodularity (Nemhauser et al., 1978), often seen as the discrete analogue of convexity, can be used to model subset selection objectives associated with diversity and representativeness. While subset selection problems are mostly NP-hard, submodular optimization algorithms are efficient and come with constant approximation guarantees (Carbonell & Goldstein, 1998; Simon et al., 2007; Krause & Golovin; Golovin & Krause, 2010; Wei et al., 2015; Lin Bilmes, 2011; Kaushal et al., 2019; Kim et al., 2016; Prasad et al., 2014; Golovin Krause, 2010; 2011; Joseph et al., 2019; Zhou & Spanos, 2016; Qian et al., 2017: Das & Kempe, 2018; Elhamifar, 2019; Kothawade et al., 2021: Kaushal et al., 2021).
A submodular function that promotes representativennss and diversity was utilized in document summarization (Lin Bilmes, 2011). Discriminant point process (DPP) are probabilistic models capable of selecting diverse subsets. They were used for minibatch selection in Marict et al. (2020), and the maximum a posteriori (MAP) inference for DPP is submodular (Chen et al., 2018).
Uncertainty sampling and active learning: Active learning methods primarily focus reducing the label annotation costs by selecting images to label that are more likely to yield the best model (See Settles (2009) for detailed survey). Theoretical guarantees are usually about how quickly the version space, that maintains a set of good candidate classifiers, shrinks based on the availability of new data (Dasgupta et al., 2008). Uncertainty sampling selects the most challenging or uncertain
2

---

Under review as a conference paper at ICLR 2022
images first, in the hope that this will eliminate the need to label other, easier ones. In classification setting, predictions from the initial model can provide class probabilities that can help identify images with high uncertainty. Possibilities include simple uncertainty measures from the best and second best class probabilities (Lewis & Gale, 1994; Scheffer et al., 2001), ), entropy measure (Holub et al., 2008; Joshi et al., 2009), and geometric distance to the decision boundary (TTng & Koller, 2002; Brinker, 2003), selection via proxies (Coleman et al., 2020), and query by committee
et al., 2005; Seung et al., 1992), where committee of models are used to identify images where they most disagree.
Coresets: coreset a small set of points that approximates the shape of a larger point set. In an ML setting it is small subset of images from a larger dataset such that the model trained on the coreset is competitive with the one learned from the entire dataset. is shown in (Sener & Savarese, 2018; Wolf, 201 I) that the average loss over any given subset of the dataset and the remaining points can be bounded, and that the minimization of this bound can be mapped to the k-center problem.
Clustering: Other classical techniques for subset selection include clustering algorithms such as k-medoids (Kaufman& & Rousseeuw, 1987; Park & Jun, 2009), which minimizes the sum of dissimi- larities between images belonging to a cluster and point designated as its center. Agglomerative clustering was used to select subsets in Birodkar et al. (2019), where it was shown that at least 10% of images redundant in ImageNet and CIFAR- 10 training. In this work, we show that at least 30-40% of the images in CIFAR-10 10, CIFAR-100 and ImageNet are redundant. In Ash et al. (2020), k-MEANS++ algorithm is used to find set of diverse and uncertain samples using the gradients of the final layer of the network.
In the context of interpretability, prototypes are subsets that best represent the entire dataset where learned model performs the best, and criticisms are the images where a learned model does not do well. Both prototypes and criticisms can be modeled using maximum mean discrepancy (MMD), that measures the difference between two distributions. The resulting optimization to compute the subsets can be cast as submodular maximization (Kim et al., 2016). Minimization of the MMD between the entire dataset and the selected subset can be seen as empirical risk minimization, and such an approach was used for batch mode active learning (Wang& & Ye, 2015). Other classical techniques for prototype selection includes k-medoids (Bien & Tibshirani, 2011) clustering methods.
3 PROBLEM STATEMENT
We consider a classification setting with I. classes and n training images 21 = ..i,.......) Let G (I,...,,) n denote the indices in the dataset. Let 1/ X' + IR_ be a (trained) neural network that maps an input image to a probability distribution over the L classes. The model can be seen as the composition of embedding function o X + RR that maps an input to D-dimensional embedding, and a discriminator funiiiiciatoruuciiion h : I + R that maps the embedding to output probability predictions.
Subset selection and model evaluation. We assume that we are given a small, annotated subset of U, which refer to as the seed dataset (this is 10% of 2/ in our experiments). We use this seed dataset to train an initial model sjseed Our goal is to use this initial model to select a subset 5 of G. subject to a given annotation budget, such that when the images in S are annotated we can get the best classification performance training new model with them. To this end, using the seed model, we generate embeddings and predictions for all the input images in U. Next, we construct a neighborhood graph (G, E) where E denotes the weighted set of edges associated with nearby training images the embedding space R.,. Our subset selection algorithm only depends on these embeddings, predictions, and the nearest-neighhor graph (G, E). As in the standard active learning settings, we do not use the groundtruth labels in 1/ while selecting subsets.
For modeling subset selection, we employ submodular set function f 2G -> IR that provides a utility value for every subset of G using notions of uncertainty and diversity. We show that the class and boundary balancing constraints can be enforced using intersections of partition matroids. With this modeling, subset selection is essentially the task of finding the subset with maximum utility value while satisfying the matroid constraints. This inference problem is combinatorial in the number of training samples, and the brute-fore solution is infeasible. For efficient inference, we rely on the submodular property of the objective function and the use of matroids for modeling balancing
3

---

Under review as a conference paper at ICLR 2022
constraints. Such approach allows us efficient greedy algorithm to maximize the objective function while satisfying matroid constraints with constant approximation guarantees.
Once the subset S is computed, request the groundtruth labels for the images in S. We the annotated subset Us C u train a model v and evaluate its performance on a common held-out test set.
BACKGROUND
In Sec. we show that our subset selection objective is both submodular and monotonic. We formally define these properties of set function below.
Definition 1. Let Q be a finite set. set function F :2 + R is submodular for all A, B C with B C A and E Q \ A. we have F(AU {e}) [ F(A) & F(BU -F(B).
-
This property is also referred to as diminishing returns since the gain diminishes as we add ele- ments Nemhauser et al. (1978).
Definition 2. A set function F monotonically non-decreasing if F(B) S F(A) when B S A.
In Sec. 5.1 we show how to incorporate class balancing and boundary balancing priors in the subset selection algorithm. We use algebraic structures called matroids and their intersections. We formally define them below.
Definition 3. A matroid is an ordered pair M = (S2, I) consisting of a finite set Q and a collection of subsets ot satisfying three conditions. (1) The collection contains the empty set, i.e., E I. (2) I E I and I' Ç I, then I' E I. (3) If and Ia are in I and [1] < 12), then there is an element in 12 I1 such that I1 {e} E
The members of I are called the independent sets of M. See Oxley (1992) for other, equivalent definitions of matroids.
Definition 4. Let fi,...., Dn be a partition of the finite set Ω and let kı..... kn be positive integers.
The ordered pair M (I,, I) a partition matroid if = {T : Q [InΩ, S k2 S SiSh n)
Definition 5. Given two matroids Mi (S2, In) and M2 = (2,, over the ground set S the intersection of the matroids is given by M1 n M2 (Ω, Iı 0I2).
SUBSET SELECTION
We propose a unified formulation for uncertainty and diversity using set functions of the form f 2c - IR, where 2 is the power set of the vertex set G. We show that our unified objective function submodular and montonic, and that the balancing constraints could be incorporated as matroids (formally defined in Sec. 4). This implies that efficient greedy algorithm comes with constant approximation guarantees (Nemhauser et al., 1978).
We cast subset selection using criterion f, as maximizing corresponding set function under budget constraint:
S arg max f(S) s.t. | k. SCG
(1)
Here S* is the optimal subset based on the selection criterion, and is the budget. Our functions con- sist of sum of terms, and the individual terms are modeled using the distances between embeddings. These embeddings are produced by the initial model glsedd, which train using the annotated seed dataset.
Our unified objective function is written as the conic combination of several individual functions based on uncertainty (funcetaiint) diversity (fuversity).. ), and clique function (iptte)
f(S) > fu (S) + >2 faiversiyy (S) + (
(2)
where X; 2 0, (1....,3)
3}. Each of these constituent functions have simple geometric interpreta- tions (See Fig. 2), and we provide their analytical expressions below:
4

---

Under review as a conference paper at ICLR 2022
Uncertainty based sampling. We define the uncertainty- based utility function funcertainty as:
Decilion boundary (A,R)
Suncertainty (S)
En(1), SES
(3)
CLASS-C
where u(i) is a utility value for each example i G, based on its uncertainty. There are three popular choices for the utility functions using uncertainty: least confident, margin (Scheffer et al., 2001), and entropy. In this paper, we use margin, which is applicable in multi-class setting, and gives preference to "hard to classify" or "low margin" examples (see Scheffer et al. (2001) for more details). More specifically:
MARGIN
3
8
6
CLASS-B
Decision boundary (8,C)
A schematic with three classes (A,B,C), 8 training samples, and two decision boundaries for the label pairs (A,B) and (B,C). faierity promotes select- ing samples that are more spreadout and thereby gives higher utility for {1, 11.3,7 7} over {2,
Figure 2:
(1) 1 ) P(Y
bb]x,) -
sb (1))..))))
(4)
where bb and sb denote the best and the second best predicted class labels for x; according to our initial model ua P(Y -la;)) denotes the class probabilities predicted by the same model for dic.
Suncensiay prefers samples with high uncertainty or the ones closer the decision boundary, and thus gives higher utility for {2, 3, 4} over {1,3,7 7) firite avoids selecting triplets with negligible or small area, and thereby gives very low utility for subsets such as (5, 6, 7} where the samples all lie on a straight line. The class balancing constraint would prefer subset {1,3, 7). with samples from three classes, balancing constraint would prefer {4, 5), which spans
Diversity. Given budget on the size of the subset, the diversity criterion promotes selection of images that are diverse or spread apart in the embedding space. We define set function Jaiversty that evaluates diversity as follows:
single class {2, 3, 4). The boundary-
over two decision boundaries, to {3,4] lying near single decision boundary.
Jdiversity (S) = Σ unary( (1) -7
Σ (KJ)EE, KJES
sii.j).
iES
(5)
The unary terms unary(1) capture the utility of an individual image and the pairwise terms sii, are the similarity between a pair of images from the selected subset that have an edge (i,j) E E in the nearest neighbor graph (G, E). As discussed the Sec. 6, we use the cosine similarity in the embedding space as the similarity measure.
The hyperparameter 7 2 0 determines the relative importance of the unary and pairwise terms. The pairwise term limits redundancy. If two points and j with high similarity are both selected, we incur penalty based on the similarity between them.
To ensure monotonicity of fdiverityy we can use a constant unary term, unary(f) = maxieG ΣY..EE s).
Lemma 1. The function [diversity is monotonically non-decreasing and submodular.
The proof is available in the Appendix.
Clique function. Given a nearest neighbor graph, we identify cliques of size three by checking for edges among the k-nearest neighbors of every sample. Given set of cliques given by T, we define fuiple as follows:
Fuipte (S) = =aa(i) -7
Σ
j(1,j,
(6)
iES
S.j.:: (K.A)ET, JJ.KES
where ai)) denotes the number triple cliques involving the sample i, and t(i, j. k) is I when the volume consumed by the embeddings of the triplet {i,j, k) is less than threshold Tehresh- and 0 otherwise. The volume computation in higher dimensional space involves outer product (Lundholm & Svensson, 2009), similar to cross- prosuutr in 3-dimensional space. For computational efficiency, we approximate the volume using the area of triangle based on the three side lengths obtained from the nearest neighbor graph. We can extend the idea of triple cliques higher orders (Kolmogorov &
5

---

Under review as a conference paper at ICLR 2022
Zabin, 2004; Kohli al., 2007; Ramalingam al., 2017), but this can be computationally expensive when we consider millions of training samples.
We prove the following lemma in the Appendix.
Lemma 2. The function firipl is monotonically non-decreasing and submodular.
We note that there are other ways to maximize the diversity function. For example, by replacing the similarity term s(i,j) with a metric distance function, the diversity criteria can be seen as the max-sum k diversification problem, for which algorithms exist with constant approximation guarantees (Borodin et al., 2017).
Any conic combination of submodular functions is submodular (Nemhauser et al., 1978), and thus f(S) is submodular.
5.1 BALANCING CONSTRAINTS
In this section we show how we incorporate balancing constraints in our unified formulation.
Class balancing constraint. Subsets selected based diversity margin criteria can lead severe class imbalance. Consequently, models trained using these imbalanced subsets can show superior performance on common classes, and inferior performance on rare classes Cui et al. (2019). A reweighted loss function can partially address this problem but performance on classes with no, or very few representatives will still suffer.
To overcome this problem we incorporate explicit do this using a partition matroid constraint, choice that allows us maintain our approximation guarantees. Consider partition {G1, G2. .e....,Gr G.) of the full dataset G. Here L denotes the number of classes and G; consists of the images belonging to class where pseudo-labels are computed using the initial (seed) model. Let .,....,y be user-defined positive integers specifying the sizes of the desired subsets. We choose subsets that are independent sets the partition matroid (G,Ip);
constraints in our formulation. We
= -1:1GG [LnG]] 1s,
Boundary balancing constraint. The initial model sh that we trained using the seed dataset, defines set of decision boundaries for every pair of classes. Formally, the decision boundary for pair of classes {a, b} is given by:
D (a,b) A P()= alx)= P(Y = b|x)}
where P(ylar) are the posterior probabilities from the seed model. In other words, these are the set of points where the posterior class probabilities for two different classes agree. Decision boundaries can be defined in input space, output space, or in the space defined by the intermediate layers in the network Elsayed et al. (2018). Since we are only interested in associating image to its closest decision boundary, our formulation does not require computation of the exact distance to the boundary. Instead simply use predicted class probabilities.
rumber bounderies
L1AM-11
boundaries
CFAR-100
numb of boundarfes
ImageNot
Images
rumbe images
images
Images
Figure 3: Histogram of the number of images associated with the class boundaries in CIFAR-1O, CIFAR-100, ImageNet, and CIFAR-100-LT datasets.
We define the margin score of an image x; (given predictions from the initial model) as
m(xx)) = 1 - (P(Y- = bblo.)) - P(Y = =sbla:)).

---

Under review as a conference paper at ICLR 2022
where bb and sb correspond to best and the second best class labels, respectively. We associate x, with the boundary (bb, sb) if m(x) > т, for some threshold т.
We observe that the number of class boundaries grows quadratically with the number of classes and conjecture that many datasets with large number of classes do not contain any images close to many decision boundaries. Our goal is design subset selection algorithm that promotes selection of images near as many decision boundaries as possible.
To quantify this observation, we use predictions from our initial model for ImageNet associate any image in the dataset which has a margin score greater than T = 0.05 to the corresponding class boundary. Since ImageNet has 1000 classes, we have (1000) boundaries. We found that 15% of all possible boundaries were covered.
Let D = {b(=); z E u denote the set of all the decision boundaries associated with all the images in the training set L1 and b(z:) is function that associates given image certain decision boundary or to the empty set 0, based on the margin score. In Fig. 3, we show the histogram of the number of images associated with different decision boundaries. We note that it is possible associate an image to multiple decision boundaries, and defer exploring this option to future work.
Similar the class-balancing problem, we consider a partition {Go, Gbz...., Gosr] J of the full dataset G, where Gs, denotes the set of images belonging to the decision boundary b; E D.
Let dd be user-defined positive integers specifying the maximum number of images near different boundaries. Let us consider the following partition matroid M = (G,Ia):
Ia = (T ICC G, | I d,, 1 S M)
(10)
In order impose both should be the independent set of both the partition matroids given by (G, and (G,
and boundary-balancing constraints, our selected subset
Note that the intersection of two matroids is not a matroid in general. However, Fisher al. (1978) shows that applying the greedy algorithm to submodular monotonic objective with matroid intersection constraints maintains approximation guarantees.
5.2 GREEDY ALGORITIM
Subset selection using class- and boundary- constraints is given by:
S arg max (SS s.t. |S| k, Ic, E Las
(11)
SCG
where is our unified objective. The greedy algorithm for selecting subset of size k is given in Algorithm I.
Algorithm 1: Greedy algorithm
1. Initialize S 0:
2. Let = arg max f(SU f(S) such that SU E NI If & and |S| then S = SU (s). go 2.:
4. S is the required solution;
Given that is monotonic and submodular, theorem from Fisher et al. (1978) implies that we have a constant approximation guarantee for the greedy algorithm according to the bound [[Srreddy) Z #+I (Soor)) where f(0) = and p is the number of matroid constraints. Since we have two matroids, we have ((Sgreedy) 2 ((oPT)
5.3 COMPUTATIONAL COMPLEXITY
The greedy algorithm can efficiently implemented using priority queue. Given a k-nearest graph on the embeddings and the uncertainty estimates, the proposed algorithm has a complexity of O(V]+ + nok2 ((V])), where the set of all samples and n the size of the subset. Without the triple cliques its complexity is O(VV + (kl)) which is the same that of k-center. For implementation reference, we provide pseudo-code in Algorithm In experiments, we choose k = 10, and the additional overhead from triple-clique constraint is minimal.
7

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Pseudocode for Subset Selection.
Input: k-NN graph G (V, E).
2. Initialize empty priority queue pq.
For all v E V do pq t- ADD(U, u(u)), where the weight w(e) based on unary such as uncertainty.
4. Initialize S {c}, where (c, w) = POP(pg). While |S| and NOT-EMPTY(pg) do:
6. (c, w) + (OP(pT)
7. If S U satisfies balancing constraints, S U..
8. For all n1 E NEIGHBOR(C) and n1 & S, do pq UPDATE(21 w(n1) (s(11, c)).
9. For all n2 NEIGHBOR(C) and n2 S, do
pq + UP w((1) - 78(01, c) r)((e, n1 n2)).
Output S.
CIFAR1O
CIFAR100
Top-1 accuracy
Top-1 accuracy
70
68
80
88
submod-bal
submod-bal
randem
random
margin
80-
margin
submod
submod
k-center
k-center
30
40
50
60
70
50
40
50
60
70
Subset size (%)
Subset size (%)
(a)
(b)
ImageNet
CIFAR100-LT
76.
40
Top-1 accuracy
74-
Top-1 accuracy
72
35.
70
submod-bal
submod-bal
random
random
margin
margin
submod
submod
k-center
k-center
30
40
30
60
50
Subset size (%)
Subset size (%)
(c)
(d)
Figure 4: All the Top-I accuracy numbers are computed by averaging three trials. For the ImageNet, the error bars are only shown for our algoritiun SUBMOD-BAL with one standard deviation.
EXPERIMENTS
Datasets. We use four datasets: CIFARIO (Krizhevsky et al., 2009), CIFARI00 (Krizhevsky et al., 2009), ImageNet (Russakovsky et al., 2014), and CIFARI00-LE (Menon et al., 2020). The last one is long-tailed dataset where the head class is 100 times more frequent than the least-frequent class (Menon et al., 2020). We do not apply any long-tail techniques as we want to compare the performance of vanilla ERM across different methods.
Initial model. For each of the datasets we select a random seed subset of size 10% and use to train ResNet-56 (He et al., 2016) initial model. We use the initial model to generate predictions and
8

---

Under review as a conference paper at ICLR 2022
embeddings for all the images in the dataset. The embeddings are 64-dimensional for CIFAR and din--dimensional for Imagenet. We construct the neighborhood graph (G, E) by finding &o = 10 nearest neighbors of each image in embedding space, using the fast similarity search of Guo et al. (2020). We evaluated different similarity measures such as cosine similarity, L,, and Lg distances, and found no significant differences. All the reported experiments
cosine similarities.
Hyperparameters. For the CIFARIO, CIFARIOO, and CIFARI00-LT experiments we used 450 epochs and the learning rate is divided by 10 at the following epochs: 15, 200, 300, and 400. The base learning rate was set to 1.0. For ImageNet we used 90 epochs and the learning rate is divided by 10 the following epochs: 5, 30, 60, and 80. The base learning rate was set 0.1. In all the datasets, we used SGD with momentum 0.9 (with nestrov) for training. When trained with the full training set, the top-1 1 accuracies for CIFAR-10, CIFAR-100, ImageNet, and CIFAR- IOO-LT are 93.04%,,71.33 76.39%, and 39.01% % respectively.
Evaluation. We show four baselines: RANDOM, MARGIN, SUBMOD, and k- C-CENTER (Sener & Savarese, 2018). SUBMOD baseline is the function in Equation 2 without the triple clique term and the balancing constraints. The parameters (ki,..., kr.) in the class-balancing partition matroid are set based on the desired subset size. In other words, k; sets an upper limit on the number of images from a specific class. In our experiments. we set this value to be I: where n, 7). and L denote the number of images, fraction of the training set, and the number of labels, respectively. In the case of boundary balancing matroid, we set the parameters d: to be max(1, myn:), where n, denotes the number of images associated with the decision boundary b, D. For every subset, train three models and averaged performance is shown in Fig 4. For our algorithm SUBMOD-BAL we use A = 0.7, 22 0.30, and λa- in Equation 2. The baselines RANDOM and MARGIN do not have any hyperparameters, For k-CENTER and SUBMOD, we use the same nearest neighbor graph with the same number of neighbors.
mm
We outperform other methods marginally in standard datasets and significantly in the long-tailed dataset. The k-CENTER (Sener & Savarese. 2018) performs close to the proposed method and outperforms standard submdoular algorithm. Note that on all these datasets, accuracies with either 80% or 90% subsets, or both, exceed that with the full dataset. This is not surprising since completely eliminating some examples in the training set has shown to be beneficial in prior work (Kubat & Matwin, 1997; Wallace al., 2011).
Ablation study: The balancing constraints show an average improvement of 0.61% in CIFAR datasets, and 2.83% in CIFARIO0-LT. The clique function shows an improvement of 0.49% in CIFAR and 1.13% in CIFAR100-LT dataset. We evaluated the role of k. the number of nearest neighbors in k-nearest neighbor graph construction. While we used k: = 10 in all our experiments the marginal benefit in using h = 100 and k 1000 given by +0.15% and +0.25%, respectively.
7 DISCUSSION
We propose a triple-clique diversity objective and balancing constraints class labels and decision boundaries. We showed that the incorporation of balancing constraints usually leads to better subsets compared to standard baselines, and the impact is highly significant in training with long-tailed datasets such as CIFARION 100-LT. We also show that some popular image classification datasets have at least 30-40% redundant images.
On standard datasets, the difference between our method and k-center is marginal, and this can be due deeper connection. The k-center algorithm can be reduced to a series of dominating set problems ( (Vazirani, 2001). Dominating set can be reduced to set cover, which is also submodular problem. While k-center has connection to submodularity, our proposed framework does not generalize k-center. It will be beneficial to find principled way to combine these methods.
9

---

Under review as a conference paper at ICLR 2022
ETHICAL STATEMENT
Training large models are resource intensive and labeling data sets also extremely labor-intensive, requiring significant human effort. For example, detailed semantic segmentation for single image can take up to 60 minutes. In this work, we develop subset selection methods that can lead to accurate models with less computations and data. This will eventually lead reduced human labeling efforts, and less utilization of computational resources.
REPRODUCIBILITY STATEMENT
The basic algorithm to find the subset is a standard greedy algorithm and it is easy to implement. We also provided the pseudocode in Algorithm 2. This paper only about subset computation and the training code is not changed. All the hyperparameters are listed in experiment section. We will release the code, the seed model, and the nearest neighbor graph for other researchers to compare their models.
REFERENCES
J. T. Ash, C. Zhang, A. Krishnamurthy. J. Langford, and A. Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In ICLR, 2020. 3
V. Budrinarayanan, F. Galasso, and R. Cipolla. Label propagation in video sequences. CVPR, 2010. 1
Bien and R. Tibshirani. Prototype selection for interpretable classification. The Annals Applied Statistics, 2011. 3
V. Birodkar, H. Mobahi, and S. Bengio. Semantic redundancies in image-classification datasets: The 10% you don't 't need, 2019. 3
A. Borodin, A. Jain, H. C. Lee, and Ye. Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Trans. Algorithms, 2017. 6
K. Brinker. Incorporating diversity in active learning with support vector machines. In ICML, 2003.
J. Carbonell and J. Goldstein. The use of mmr, diversity-based reranking for reordering documents and producing summaries. SIGIR '98, 1998. 2
L. Chen, G. Zhang, and H.Zhou. Fast greedy map inference for determinantal point process to improve recommendation diversity. In NeurIPS, 2018. 2
C. Coleman, C. Yeh, S. Mussmann, B. Mirzasoleiman, Bailis, P. Liang, Leskovec, and M. Zaharia. Selection via proxy: Efficient data selection for deep learning, 2020.
Y. Cui, M. Jia, T. Y. Lin, Y. Song, and S. Belongie. Class-halanced loss based on effective number of samples. In CVPR, 2019.
Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal Machine Learning Research, 19(3): 1-34, 2018. URL http::/tp//.. / //jm r. org/ papers/v 9/16-533 html.
S. Dasgupta, D. J. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In NeurIPS, 2008. 2
J Devlin, M. W. Chang, K. Lee, and Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, 2018.
E. Elhamifar. Sequential facility location: Approximate submodularity and greedy algorithm. In ICML, 2019. 2
G. Elsayed, D. Krishnan, H. Mobahi, K. Regan, and S. Bengio. Large margin deep networks for classification. In NIPS, 2018.
10

---

Under review as a conference paper at ICLR 2022
M.L. Fisher, G.L. Nemhauser, and L.A. Wolsey. An analysis of approximations for maximizing submodular set functions-ii. In Polyhedral Combinatorics. Mathematical Programming Studies, 1978.
Amirata Ghorbani, James Zou, and Andre Esteva. Data shapley valuation for efficient batch active learning, 2021. 1
R. Gilad- filaa-Bachhrach, A. Navot, and N. Tishby. Query by committee made real. In NIPS, 2005.
D. Golovin and Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artif. Int. Res., 2011.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization, 2010. 2
R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simeha, F. Chern, and S. Kumar. Accelerating large-scale inference with anisotropic vector quantization. ICMI,, 2020. URL wwtpthsss//aaii...a/// abs/1908. 10396.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016. 1. 8
G. Hinton, L. Deng, G.E. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal Processing Magazine, 2012. 1
A. Holub, P. Perona, and M. Burl. Entropy-based active learning for object recognition. In CVPR Workshop, 2008. 3
K J Joseph, Vamshi Teja R, Krishnakant Singh, and Vineeth N Balasubramanian. Submodular batch selection for training deep neural networks, 2019.
A. J. Joshi, F. Porikli, and N. Papanikolopoulos. Multi-class active learning for image classification. In CVPR, 2009. 3
L. Kaufman and P. J. Rousseeuw. Clustering by means of medoids, 1987. 2,
V. Kaushal, R. Iyer, S. Kothawade, R. Mahadev, K. Doctor, and G Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision, 2019. 2
V. Kaushal, S. Kothawade, G. Ramakrishnan, J. A. Bilmes, and R. K. Iyer. PRISM: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization. CoRR, abs/2103.00128. 2021.
B. Kim, R. Khanna, and O. Koyejo. Examples are not enough, learn to criticize! criticism for interpretability. In NIPS, 2016. 2,3
K Kwan-Young Young Kim, Dongwon Park, Kwang In Kim, and Se Young Chun. Task-aware variational adversarial active learning. In CVPR, 2021.
Kohli, M. P. Kumar, and P. H. S. Torr. P3 beyond: Solving energies with higher order cliques, In 2007 IEEE Conference Computer Vision and Pattern Recognition, 2007. 6
V. Kolmogorov and R. Zabin. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):147-159, 2004. doi: 10. 109/ TPAMI.2004.120 1262177.
S. Kothawade, N. Beck, and K. Killamsetty R. K. Iyer. SIMILAR: submodular information measures based active learning in realistic scenarios. CoRR, abs/2107. .00717. 2021. 2
Andreas Krause and Daniel Golovin. Submodular function maximization.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In NeurIPS, 2012.
11

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Miroslav Kubat and Stan Matwin. Addressing the curse of imbalanced training sets: One-sided selection. In Proceedings of the International Conference on Machine Learning (ICML), 1997.
D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. In SIGIR, 1994. 2, 3
H. Lin and J. Bilmes. A class of submodular functions for document summarization. In ACL, 2011.
Douglas Lundholm and Lars Svensson. Clifford algebra, geometric algebra, and applications, 2009.
Z. Mariet, J. Robinson, J. Smith, S. Sra, and S. Jegelka. Optimal batch variance with second-order marginals. ICML Workshop, 2020. 2
Aditya Krishna Menon, Sadcep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment, 2020. 8
G. Nemhauser, L. Wolsey, and M. L. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 1978. 2, 4, 6
James Oxley, Matroid Theory. Oxford University Press, 1992. 4
H.S. Park and C.H. Jun. A simple and fast algorithm for k-medoids clustering. Expert Systems with Applications, 2009.
A. Prasad, S. Jegelka, and D. Batra. Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. NIPS, 2014.
Chao Qian, Jing-Cheng Shi, Yang Yu, Ke Tang, and Zui-Hua Zhou. Subset selection under noise. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, 2017.
S. Ramalingam, C. Russell, L. Ladicky, and P. H. S. Torr. Efficient minimization of higher order submodular functions using monotonic boolean functions. Discrete Applied Mathematics, 2017.
O. Russakovsky, J. Deng, H. Su, Krause J, S. Satheesh, S. Ma, Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. Imagenet large scale visual recognition challenge, 2014.
T. Scheffer, C. Decomain, and Wrobel. Active hidden markov models for information extraction.
In Advances in Intelligent Data Analysis, 2001. 3,
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. In ICML, 2018. 3,
B. Settles. Active learning literature survey. Technical report, University of Wisconsin-Madison 2009. 1,2
H. S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In COLT, 1992. 3
Changjian Shui, Fan Zhou, Christian Gagn's e, and Boyu Wang. Deep active learning: Unified and principled method for query and training. AISTATS, 2020.
Simon, N. Snavely, and M. Seitz. Scene summarization for online image collections. ICCV, 2007. 2
E. Strubell, A. Ganesh, and A. McCallum, Energy and policy considerations for deep learning in NLP. CoRR, 2019.
I. Sutskever, O. Vinyals, and Q.V. Le. Sequence to sequence learning with neural networks. In NeurIPS, 2014.
C. Szegedy, W. Liu, Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In CVPR, 2015. 1
12

---

Under review as a conference paper at ICLR 2022
S. Tong and D. Koller. Support vector machine active learning with applications to text classification. JMLR, 2002. 3
Vijay V. Vazirani. Approximation Algorithms. Springer- Verlag, 2001. 9
B.C. Wallace, K.Small, C.E. Brodley, and T.A. Trikalinos. Class imbalance, redux. In Proc. ICDM, 2011. 9
Z. Wang and J. Ye. Querying discriminative and representative samples for batch mode active learning. ACM Trans. Knowl. Discov. Data, 2015. 3
K. Wei, Iyer, and J. Bilmes. Submodularity in data subset selection and active learning. In ICML, 2015. 2
Gent W. Wolf. Facility location: Concepts, models, algorithms and case studies. series: Contributions to management science. 2011.
Fedor Zhdanov. Diverse mini-bate mini-batch active learning. CoRR, abs//190..09955 2019. 1
Yuxun Zhou and Costas J. Spanos. Causal meets submodular: Subset selection with directed information. In Proceedings of the 30th International Conference Neural Information Processing Systems, NIPS' 16, pp. 2657-2665, 2016.
A APPENDIX
Lemma 1. The function faiversity is monotonically non-decreasing and submodular.
Proof. The function fdivenity is given by
fdiversity (S)
Σ
max IEG
Σ s(l,j)
ies
;:(.))EE
Σ s(i.j).
(12)
1j (KJ)E,, IeES
We will show that the function monotonically non-decreasing and submodular when S 1.
We will first show that the function is monotonically non-decreasing. Consider an element e E G\SS:
Sdiversity (SUe) - Saiversity (S)
max LEG
Σ
8(l.))
j(UE))
Σ
s(e,j)
(13)
(e.)EF, jES
In the first term, j E G. whereas in the second E S. The first term a maximum over all samples in G. including e. Since and C G. we have fdiversity (S fdiversity (S) 2 0 and thus the function in Eq. 12 is monotonically non-decreasing.
Next, we will show that the function fdiversity (S) is submodular. In order to do this, we show the following when A, B C G, B C A, and G),A:
faieesitt (A faivenity (A) S faiverity (BUc) - faiversity (B)
(14)
We expand the left hand side of the above expression using the definition of fdiversity (S):
(diversin((AAee)) - fdiversity (A) max IEG
Σ s(l,j)-
HUBJEE
A
Σ
s(e,j)
(15)
ji (eJ)EE, JEA
13

---

Under review as a conference paper at ICLR 2022
We expand the right hand side follows:
Jdiversity (BUe) faiversity (B)
max
Σ
s(1,g)
IEG
jolljjER
? Σ
s(c,5)
(16)
je (eJ)ER, jeB
Subtracting Eq. 16 from Eq. 15 we have:
(Jdiversity (AUe) Jtiversiry (A))
(faiversity Ue) fdiversity (B))
E
s(c,5) -7 j: (OJ)EE, SEA
s(c,j)
(17)
8: (E,))E,, jEB Since 7 2 0, (-,))) 0, and B C A, we satisfy Eq.
Lemma 2. The function Stipte is monotonically non-decreasing and submodular.
Proof. The function fuiple is given by Suiple (5)
Σ
a(1)
E
(18)
iES
S.j.k: (I.AA)TT s...ES
We will show that the function monotonically non-decreasing and submodular when S S 1. We will first show that the function is monotonically dec-decra.,,ng. Consider an element G.
firpte Ue) fimpte a(e)-
Σ
t(c,j,k)
(19)
e.j.k: (e.j.)JT, e.j.kE
The first term (e) is the number of triple cliques associated with e, and the maximum value of the second term is (<)) since < 1 1. Thus we have firipee U e) SSr 2 0 and thus the function in Eq. 18 monotonically non-decreasing.
Next, we will show that the function Stript(()) submodular. In order to do this, we show the following when A, B C G, B C A, and E G::::
[uipte(AUe)
fuipte ()) s fuipte (BUe) - Siripee (B)
(20)
We expand the left hand side of the above expression using the definition of fmipte(S)
fippte (A Ue) fippee(A) = a(e)
Σ
((e,j,k)
(21)
e.j (e.jkJTT, ejjkEA
We expand the right hand side follows:
fuipte B Ue)
funpo = a(E)
n
Σ
k(e,j,k)
(22)
e.j: (e...)ET, e.jREB
Subtracting Eq. 22 from Eq. 21 we have:
fuiple(A)
(fupte (BU
(BUe)
Suipte
(htpte(B)) (B))
Σ
(e,,i,k)
(23)
k (.R),T e.J.KBB
"
Σ
t(e,j,k)
(24)
ejj.k: (e.j.))TT ej.kEA
Since r) 2 0, t(.....) >= 0, and B C A, we satisfy Eq. 20.
14


Reviews:
[{"review_id": "oMCnjYBEvwx", "reviewer": "Reviewer_4ATq", "summary": "", "questions": "", "limitations": "", "rating": 3, "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\nS1) This paper identifies and addresses a common issue in active learning, which is that selection criteria generally don't address class imbalance and decision boundary imbalance.\n\nS2) Experiments were performed on multiple datasets, including a highly class-imbalanced dataset (CIFAR-100LT) which may be more reflective of real-world settings.\n\n### Weaknesses and Issues\n\n**W1) Need to clarify misleading \"constant approximation guarantee\"**\n\nThe paper claims to have a \"constant approximation guarantee,\" which is misleading. This guarantee is only with respect to the proposed selection criteria $f(S)$, but there is no guarantee that a set $S$ which maximizes $f(S)$ is actually a good training set. To the best of my knowledge, the correlation between $f(S)$ and test accuracy is merely heuristic and empirical. This point needs to be made much clearer in the text to prevent readers from conflating a \"constant approximation guarantee\" for maximizing $f(S)$ and the (non-existent) guarantee for maximizing test accuracy.\n\nIn contrast, active learning methods based on influence functions (see W2 below), actually try to directly maximize test set accuracy.\n\n**W2) Missing discussions and comparisons against other related works**\n\nThe paper is missing discussions and comparisons against about other relevant active learning techniques such as [Deep Bayesian Active Learning (Gal et al., 2017)](https://proceedings.mlr.press/v70/gal17a) and [Active Learning via Influence Functions (Xu and Kazantsev, 2019)](http://arxiv.org/abs/1905.13183). Note that DBAL can be considered as another \"uncertainty\" metric. However, active learning via influence functions does not seem to fall within the uncertainty vs. diversity framework that this submission describes. Therefore, I would be particularly interested in seeing a discussion and comparison between the proposed framework and active learning via influence functions.\n\n**W3) How does the proposed framework address the limitation that \"no single subset selection criterion achieves the best performance\"?**\n\nThe authors write, \"To address the first limitation, we develop a unified algorithm based on maximization of a submodular function, which can combine different selection objectives.\" The limitation that they refer to is \"First, there is no single subset selection criterion that achieves the best performance on different classification datasets.\"\n\nIt is unclear to me how the proposed framework addresses this limitation. Putting the various selection objectives into a single selection criteria function $f$ does not magically mean that the combined criteria achieves the best performance on different classification datasets. The authors' claim seems very misleading.\n\n**W4) Need better justification and discussion about $f_{triple}$**\n\nIt is unclear to me how $f_{triple}$ is practically different from $f_{diversity}$. Are there situations where the two are very different? Is there a theoretical justification for why including both metrics is better than including just one of the two? Could you show a scatter plot of the two metrics (e.g., sample many different sets $S$, then plot $f_{diversity}(S)$ on the x-axis and $f_{triple}(S)$ on the y-axis)?\n\nAlso, I'm not sure I fully understand what the \"volume consumed by the embeddings of the triplet $\\{i,j,k\\}$\" means. A more thorough discussion of this is warranted. How is $\\mathcal{T}_{thresh}$ chosen? And why use a threshold on $t(i,j,k)$, instead of a proportional penalty on $t(i,j,k)$?\n\n**W5) How to select hyperparameters parameters like $\\lambda_i$, $\\gamma$, $\\mathcal{T}_{thresh}$, and $k$**\n\nI would appreciate a discussion on how to select the hyperparameters mentioned throughout the paper. The values chosen seem rather arbitrary.\n\n**W6) What about active learning for regression?**\n\nThe paper only describes active learning for classification problems. The authors should make this clearer from the start of the paper. Are any of the ideas proposed here generalizable to regression settings?\n\n**W7) Clarity Issues - please address each point individually in your response**\n\n- In the \"Subset selection and model evaluation\" paragraph under \"Section 3: Problem Statement\", it is unclear what edges are included in $E$. For example, is $E$ directed? Is $E$ fully-connected? Only after reading through the end of the paper did I understand $E$ to be the edge set of a $k$-degree nearest neighbor, where $k$ is a hyperparameter. This point should be made clearer.\n\n- Why define the margin score as $m(x) = 1 - \\left( P(Y=bb|x) - P(Y=sb|x) \\right)$? Why not define it more simply as $m(x) = P(Y=bb|x) - P(Y=sb|x)$?\n\n- What unary function did you use for $f_{diversity}$ in your experiments? Did you use the constant term?\n\n- Equation (7) says $M = (G, \\mathcal{I}_p)$, but then defines $\\mathcal{I}_c$. Looks like a typo.\n\n- The authors write that on ImageNet, \"we found that 15% of all possible boundaries were covered.\" Help me interpret this statement. Is 15% surprising? Is this more or less than the authors expected?\n\n- In equation (10), what is $M$? It seems like $M$ is used both as an integer (for the number of decision boundaries) and as a matroid. Please clarify.\n\n- In the \"Evaluation\" subsection under \"Section 6: Experiments,\" the authors write, \"Note that, on this dataset, accuracies with 80% and 90% subsets exceed that with the full dataset.\" Which dataset is this referring to?\n\n- In the Ablation study subsection, what are the standard deviations for the reported improvement percentages? Are these relative improvements, or absolute improvements? On which dataset(s) did the authors test the larger values of $k$?", "summary_of_the_paper": "The paper describes a new active learning algorithm for classification problems. The authors propose a selection criteria that trades off between uncertainty and diversity. The novelty lies in formulating a three-pronged approach to diversity that still manages to maintain submodularity of the selection criteria:\n1) a traditional diversity metric based on cosine similarity of embeddings\n2) a new triplet/clique \"loss\" that penalizes the selection of nearby points\n3) class-balancing and boundary-balancing constraints\n\nBy showing this three-pronged approach maintains submodularity, they are able to devise a greedy algorithm that still has a constant approximation guarantee to the optimal selection subset (as measured by the selection criteria). Experiments on CIFAR-10, CIFAR-100, ImageNet, and CIFAR-100LT (long-tailed) suggest that the new approach performs as well as or better than state-of-the-art methods.", "summary_of_the_review": "The active learning approach proposed by the paper builds incrementally on existing ideas of uncertainty and diversity sampling. They provide decent empirical evidence to suggest that their methods are at least as good as existing methods, and sometimes better. However, I hesitate to recommend this paper for acceptance as-is, due to misleading claims, incomplete discussions, and a number of clarity issues. Many of the design choices seemed arbitrary and require more thorough justification. I would be inclined to raise my score if the paper's current weaknesses and issues are properly addressed.", "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": "m4C2kxF3bpH", "reviewer": "Reviewer_oEcZ", "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:\n1.\tThe paper is easy to read and understand.\n2.\tThe proposed boundary balancing constraint is interesting.\n3.\tIt is good to do experiments on large datasets.\n\nWeaknesses:\n1.\tThe authors claimed that “we develop a unified algorithm based on maximization of a submodular function, which can combine different selection objectives” in Introduction. However, I can’t see the necessary or benefit of using “submodular function and matroid intersection” in this paper, except that some prior works about submodular show the guarantee of approximation to the original dataset in the some feature/output space. The question is that the subset with optimal approximation of a dataset in some feature space doesn’t guarantee that it is the optimal for training neural networks. It is known that random selection can also perfectly approximate the geometry of original dataset (Chen et al 2012) as long as the subset is large enough. In addition, it is also unknown that such approximation guarantee of using submodular function is better or faster to reach than other approximation methods like herding, k-center (Sener & Savarese, 2018), k-medoids etc. \n2.\tThe authors admitted that “the difference between our method and k-center is marginal” in Discussion. The performance comparison also verified it. The performance improvement of the proposed method is mainly due to balancing constraints. More detailed ablation study on each individual balancing constraint should be given. Otherwise, it is unclear which constraint works. \n3.\tThe experiments lack the comparison to state-of-the-art subset selection methods.\n4.\tIn the balancing constraints, the image number of each class is pre-defined and the underlying assumption is that the class number is known. Is this assumption realistic in the experimental setting (active learning)?\n\n(Chen et al 2012) Super-Samples from Kernel Herding\n", "summary_of_the_paper": "This paper proposed a new subset selection method with novel diversity objective and balancing constraints. The authors prove that the proposed sample selection criterion is a submodular function. Hence its greedy algorithm comes with approximation guarantees (Nemhauser et al., 1978). The experiments on popular image classification datasets show that the proposed method is slightly better than k-center (Sener & Savarese, 2018). ", "summary_of_the_review": "The proposed method achieves slight improvement over a classic method (k-center) by introducing new objective and constraints. The paper lacks deep analysis and solid experiments that explain why the new components are better. The contribution is somewhat incremental. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Z_z8U6en3DV", "reviewer": "Reviewer_yngU", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "## Pros\n- Formulation of the optimization problem is well motivated.\n- The proposed algorithm is clearly described using rigorous equations.\n- Proofs of important properties of the method (submodularity of objective functions) are provided in the appendix.\n\n## Cons\n- The motivation for the triplet clique objective (6) is unclear. The function appears to encourage diversity of subset $S$ as (5) has addressed, and no discussion (theoretical or empirical) is provided as to whether the advantage of including (6) can offset the additional computational complexity it introduces.\n- Balancing constraints seem to play the most important role from the empirical results. This puts into question the importance of the first claimed contribution of the paper, namely the unified objective function of (2), as `submod` without balancing does not significantly outperform other baselines. However, no ablation experiments are included to study the importance of boundary-level balancing constraints in addition to class-level balancing.\n- Theoretical analysis or ablation studies for important hyperparameters of the proposed method are also missing from the experiments. Some examples for these include the loss weights $\\lambda_1, \\lambda_2$ and $\\lambda_3$; the choice of balancing hyperparameters $k_{1:L}$, $d_{1:M}$; the margin score threshold $\\tau$.\n- Lack of comparison to state-of-the-art active learning methods. While the paper compared to core-set selection, stronger baselines (e.g. [A-C]) were not included. In addition, comparisons in the paper are limited to classification datasets, but not for more label-intensive tasks such as semantic segmentation, which [B, C] has studied.\n- Error bars for methods other than `submod-bal` were not reported. This makes it hard to determine the statistical significance of results when comparing two approaches.\n\n## Minor comments\n- Equation (9) seems redundant given the margin score has been defined in (4). I wonder if it makes more sense to instead define the boundary assignment function $b(x_i) = (bb(x_i), sb(x_i))$?\n\n[A] Yoo, Donggeun, and In So Kweon. \"Learning loss for active learning.\" *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*. 2019.\n\n[B] Sinha, Samarth, Sayna Ebrahimi, and Trevor Darrell. \"Variational adversarial active learning.\" *Proceedings of the IEEE/CVF International Conference on Computer Vision*. 2019.\n\n[C] Zhang, Beichen, et al. \"State-relabeling adversarial active learning.\" *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*. 2020.", "summary_of_the_paper": "This paper presents a new method for batch active learning in deep neural networks, which aims to progressively construct compact subsets from a training dataset that maximize accuracy of learned models. The authors propose to address this problem by optimizing a submodular set function, expressed as a weighted combination of uncertainty, diversity, and triplet objectives, under a set of balancing constraints on classes and decision boundaries. The resulting optimization problem is solved using a greedy algorithm. Experiments are conducted on CIFAR10, CIFAR100, ImageNet and CIFAR100-LT datasets, where the proposed approach outperforms all baselines, with larger improvements under a class-imbalanced setting (CIFAR100-LT).", "summary_of_the_review": "I appreciate the effort of authors towards a unified framework for sample selection in active learning. However, as detailed in the Cons section above, the importance of many elements of the proposed method are not adequately justified through theoretical or empirical results, and comparisons to prior work are lacking in number of baselines as well as range of tasks. I believe additional experiments/analysis addressing these concerns are needed to support the major claims of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PJ9BUWVuNOE", "reviewer": "Reviewer_Cp2k", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "AFTER REBUTTAL:\n\nI thank the authors for their detailed rebuttal and for testing out some of the suggested ablations. However, in light of the number of ablations and some of the confusion regarding the motivation behind class and boundary balancing, I feel this paper may not yet be ripe and could do with another round to review the explored experiments and revise the intuition and justification behind the setup. Therefore I leave my score as is.\n\n-------------------\n\n\nI like the review of how different strategies are biased to miss class and boundary diversity, as well as the matroid constraints for incorporating them. However, I feel that the paper can be improved with additional ablation and analysis. Below are some suggestions.\n\n\n- I found the histograms in Fig 3 and corresponding discussion confusing. It would be useful to revise the axis and give some more information as to how a reader can interpret the plot. I interpret the x-axis of the histogram as “boundaries covered by $n$ images”. So for example with CIFAR10, there are 12 decision boundaries that are covered by only 1 image, and 13 boundaries covered by 2 images. Is this correct?\n- It seems there is extensive parameter tuning involved, particularly in selecting how much to weigh the different terms in the objective function. Parameter tuning in active learning is a fundamental challenge since we typically don't have the validation data to tune parameters at onset. Can you provide details to how much parameter tuning was involved and how your custom objective would work in practice?\n- An alternative to the above point, in terms of delineating the value of parameter tuning would be to implement the class and decision boundary constraints with respect to existing active learning strategies. For example, $\\lambda_1 = 1, \\lambda_2 = \\lambda_3 = 0$ would give us a fair comparison on the value of class and boundary balance and how it improves a well-known existing method like margin. \n- The improvement of the proposed method over baselines is attributed to the balancing constraints (e.g., comparing submod-bal vs submod). How well does the proposed method work in covering class and decision boundaries? For example, it may be useful to have a histogram of labeled class frequencies after each round of active learning for each method. Ideally, we expect the proposed method to select more balanced sets to label than baselines. We can do a similar analysis replicating Fig. 3 evaluating selections in each round with the decision boundary of a final classifier trained with 100% of the data as ground truth. These analyses can answer: how much does the current method improve over baselines in selecting class and boundary-balanced data, whether there is room for more improvement, and what is more important (class or boundary balance?)\n- I am most interested to see what this looks like on CIFAR100-LT since this is where the proposed method shines the most and I expect class-balancing to be a key contributor. A good class balancing AL strategy can very much help imbalanced data collection practices and I encourage the authors to emphasize this value of their proposed method further. For example, another ablation could be to test on different imbalance factor for CIFAR100-LT and track the relative improvement of the proposed method over baselines as we vary the degree of imbalance.\n", "summary_of_the_paper": "Most batch-mode active learning strategies involve maximizing a sub-modular score function of the value of each image to be labeled. This paper demonstrates that current methods fail to sample diverse classes or images near decision boundaries, arguably one of the most important regions to obtain label information. The paper proposes a technique for incorporating class-balance and boundary-balance constraints to the sub-modular optimization problem and performs experiments over several image data sets to show the value of class and boundary balancing.\n", "summary_of_the_review": "Overall the approach and results look interesting, but the limited experiments make it difficult to fully capture the value of the methods proposed. I would be happy to increase my score if the authors can further expand numerically on where the improvements are coming from.\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": {}}]

Author rebuttal:

Meta-review: The paper studied an interesting yet challenging problem in active learning and provided an intuitive heuristic for selecting informative subset(s) of training examples. The reviewers generally find the paper well presented and highlight that the clarity of the exposition of the issues of existing query heuristics, especially for training deep models with class-imbalance data.

However, there are shared concerns among all reviewers in whether the existing experiments sufficiently justify the practical significance of the proposed heuristic (Reviewer 4ATq: Missing comparison against important baselines such as Gal et al 2017; Reviewer Cp2k: ablations of class and boundary balancing; Reviewer yngU: lack of comparison to SOTA and ablation for important hyperparameters; Reviewer oEcZ: lack comparison against SOTA). Reviewers also point out that the approximation guarantee is against an algorithm that is optimal wrt a somewhat ad-hoc objective, which makes the theoretical components of the paper not as significant. Given the above concerns, the paper does not appear to be ready for acceptance at the current stage.
Decision: Reject