Leveraging Importance Weights in Subset Selection
Authors: Gui Citovsky
Giulia DeSalvo
Sanjiv Kumar
Srikumar Ramalingam
Afshin Rostamizadeh
Yunjuan Wang
Venue: ICLR 2023 poster (2023)
Keywords: data subset selection
importance weighted sampling

Abstract: We present a subset selection algorithm designed to work with arbitrary model families in a practical batch setting. In such a setting, an algorithm can sample examples one at a time but, in order to limit overhead costs, is only able to update its state (i.e. further train model weights) once a large enough batch of examples is selected.  Our algorithm, IWeS, selects examples by importance sampling where the sampling probability assigned to each example is based on the entropy of models trained on previously selected batches. IWeS admits significant performance improvement compared to other subset selection algorithms for seven publicly available datasets. Additionally, it is competitive in an active learning setting, where the label information is not available at selection time. We also provide an initial theoretical analysis to support our importance weighting approach, proving generalization and sampling rate bounds.

Published as a conference paper at ICLR 2023
LEVERAGING IMPORTANCE WEIGHTS IN SUBSET SE- LECTION
Gui Citovsky', Giulia DeSalvo', Sanjiv Kumar', Srikumar Ramalingam', Afshin Rostamizadeh', Yunjuan Wang
GGoogle Research, New York, NY, 10011
Department of Computer Science, Johns Hopkins University, Baltimore, MD, 21218 (gcitovsky, giuliad, sanjivk, rostami, (erikumar)8@gooo com ywang5094 96 jhu. edu
ABSTRACT
We present a subset selection algorithm designed to work with arbitrary model families in practical batch setting. In such setting, an algorithm can sample examples one at a time but, in order to limit overhead costs, is only able to update its state (i.e. further train model weights) once a large enough batch of examples is selected, Our algorithm, IWeS, selects examples by importance sampling where the sampling probability assigned to each example is based on the entropy of mod- els trained on previously selected batches. IWeS admits significant performance improvement compared to other subset selection algorithms for seven publicly available datasets. Additionally, it is competitive in an active learning setting, where the label information is not available at selection time. We also provide an initial theoretical analysis to support importance weighting approach, proving generalization and sampling rate bounds.
INTRODUCTION
Deep neural networks have shown remarkable success in several domains such as computer vision and natural language processing. In many tasks, this is achieved by heavily relying on extremely large labeled datasets. In addition to the storage costs and potential security/privacy concerns that come along with large datasets, training modern deep neural networks such datasets also incur high computational costs. With the growing size of datasets in various domains, algorithm scalability real and imminent challenge that needs be addressed. One promising way solve this problem is with data subset selection, where the learner aims to find the most informative subset from large number of training samples to approximate (or even improve upon) training with the entire training set. Such ideas have been extensively studied in k-means and k-median clustering (Har-Peled & Mazumdar, 2004), subspace approximation (Feldman et al., 2010), computational geometry (Agarwal et al., 2005), density estimation (Turner et al., 3021). to name a few.
One particular approach for solving data subsampling involves the computation of coresets, which weighted subsets of dataset that can act the proxy for the whole dataset to solve some op- timization task. Coreset algorithms are primarily motivated with theoretical guarantees that bound the difference between the training loss (or other such objective) over the coreset and that over the full dataset under different assumptions on the losses and hypothesis classes (Mai et al., 2021; Munteanu et al., 2018; Curtin et al., 2019; Karnin & Liberty, 2019). However, in practice, most competitive subset selection algorithms, that are designed for general loss functions and arbitrary function classes, focus only on selecting informative subsets of the data and typically do not assign weights to the selected examples. These methods are, for example, based on some notion of model uncertainty (Scheffer al., 2001), information gain Erggamon-Engelsoon & Dagan, 1999), loss gra- dients (Paul et al., 2021; Ash et al., 2019), or diversity (Sener & Savarese, 2018). Counter to this trend, we show that weighting the selected samples can be very beneficial.
In this work, we present subset selection algorithm called IWeS that is designed for general loss functions and hypothesis classes and that selects examples by importance sampling, a theoretically
"This work done when the author was interning Google.

---

Published as a conference paper at ICLR 2023
motivated and unbiased sampling technique. Importance sampling is conducted according to spe- cially crafted probability distribution and, importantly, each sampled example is weighted inversely proportional to its sampling probability when computing the training loss. We develop two types of sampling probability for different practical requirements (e.g. computational constraints and label availability), but in both cases, the sampling probability is based on the example's entropy-basee score computed using a previously trained model. We note, the IWeS algorithm is similar to the IWAL active learning algorithm of Beygelzimer al. (2009) as both are based on importance sam- pling. However, in contrast to IWAL, IWeS uses different sampling probability definition with a focus on providing a practical method that amenable large deep networks and complex hypoth- esis classes
Through extensive experiments, we find that the IWeS algorithm competitive for deep neural networks over several datasets. We compare our algorithm against four types of baselines whose sampling strategies leverage: the model's uncertainty over examples, diversity of selected examples, gradient information, and random sampling. Finally, we analyze closely related albeit less practical algorithm that inspires the design of IWeS, called IWeS-V, proving admits generalization and sampling rate guarantees that hold for general loss functions and hypothesis classes.
The contributions of this work can be summarized as follows:
1. We present the Importance Weighted Subset Selection (TWeS) algorithm that selects examples by importance sampling with a sampling probability based on model's ' entropy, which is applicable to (and practical for) arbitrary model families including modern deep networks. In addition the subset selection framework, IWeS also works in the active learning setting where the examples are unlabeled at selection time.
2. We demonstrate that IWeS achieves significant improvement over several baselines (Ran- dom, Margin, Least-Confident, Entropy, Coreset, BADGE) using VGG16 model for six com- mon multi-class datasets (CIFARIO, CIFARIO-corrupte -0coorrpted. CIFAR 100, SVHN, Eurosat, Fashion MNIST), and using ResNet1 model for the large-scale multi-label OpenImages dataset.
We provide a theoretical analysis for closely related algorithm, IWeS-V, in Section 4. We prove ((/VT)) generalization bound, which depends on the full training dataset size T. We further give new definition of disagreement coefficient and prove sampling rate bound by leverag- ing label information, which is tighter compared with the label complexity bound provided by Beygelzimer et al. (2009) that does not use label information.
1.1 RELATED WORK
Uncertainty. Uncertainty sampling, which selects examples that the model is least confident on, is favored by practitioners (Mussmann & Liang, 2018) and rather competitive among many recent al- gorithms (Yang & Loog, 2018). Uncertainty can be measured through entropy (Argamon-Engelson & Dagan, 1999), least confidence (Culotta & McCallum, 2005), and most popular is the margin between the most likely and the second most likely labels (Scheffer et al., 2001). More recent works measure the model uncertainty indirectly, such as selecting examples based on an estimated loss (Yoo & Kweon, 2019) well leveraging variational autoencoders and adversarial networks to find points not well represented by the current labeled data (Sinha et al., 2019; Kim et al., 2021). Beygelzimer et al. (2009) makes use of disagreement-basse -basd notion of uncertainty and constructs an importance weighted predictor with theoretical guarantees called IWAL, which is further enhanced by Cortes al. (2019). However, IWAL is not directly suitable for use with complex hypothesis spaces, such as deep networks, since it requires solving non-trivial optimization over a subset of the hypothesis class, the so-called version space, in order to compute sampling probabilities. We further discuss these difficulties in Section 4.
Diversity. In another line of research, subsets are selected by enforeing diversity such as in the FASS (Wei et al., 2015) and Coreset (Sener & Savarese, 2018) algorithms. Wei et al. (2015) introduces a submodular sampling objective that trades off between uncertainty and diversity by finding a diverse set of samples from amongst those that the current trained model is most uncertain about. It was further explored by Kaushal et al. (2019) who designed a unified framework for data subset selection with facility location and dispersion- based diversity functions. Sener & Savarese (2018) show that the task of identifying a coreset in an active learning setting can be mapped to solving the k-center problem. Further recent works related to coreset idea Mirzasoleiman et al. (2020); Killamsetty
2

---

Published as a conference paper at ICLR 2023
et al. (2021), where the algorithms select representative subsets of the training data minimize the estimation error between the weighted gradient of selected subset and the full gradient.
Loss Gradient. Another class of algorithms selects subset by leveraging the loss gradients. For example, the GRAND score (Paul et al., 2021), or closely related EL2N score, leverages the aver- age gradient across several different independent models to measure the importance of each sample. However, as such, it requires training several neural networks, which is computationally expensive. BADGE (Ash al., 2019) is a sampling strategy for deep neural networks that uses k-MEANS++ on the gradient embedding of the networks to balance between uncertainty and diversity. ISAL (Liu al., 2021) measures the potential impact of each example by leveraging the loss gradient and Hes- sian. Finally, for the sake of completeness, we note that importance weighting type approaches have also been used for the selection of examples within an SGD minibatch (Katharopoulos & Fleuret, 2018; Johnson & Guestrin, 2018), which can be thought of change to the training procedure itself. In contrast, the problem setting we consider in this work requires explicitly producing a (weighted) subset of the training data and treats the training procedure itself black-box.
These are a sampling of data subset selection algorithms, and we refer the reader to (Guo et al., 2022) for a more detailed survey. In this work, we choose at least one algorithm from each of the categories mentioned above, in particular, Margin (Scheffer et al., 2001), BADGE (Ash et al., 2019), and Coreset (Sener & Savarese, 2018) to compare against empirically in Section 3. However, before that, we first formally define the IWeS algorithm in the following section.
THE IWES ALGORITHM
Algorithm Importance Weighted Subset Selection ([WeS)
Require: Labeled pool P, seed set size ko, subset batch size k number of iterations R, weight cap
parameter u.
1: Initialize the subset S = 0.
2: Su < Draw ky examples from P uniformly at random.
3: Set S [xx 1): (x, v) E So and So
4: for -1.2.... do
5: Set S, 0.
6: Train fr. on S using the weighted loss and independent random initializations.
7:
while [S,|
do
8:
Select (x, y) uniformly at random from P.
9:
Set (xx y) using entropy-baat based disagreement or entropy criteria shown in Eq (1) and (2).
10:
Q Bernoulli(p(x.)))
11:
if Q = then
Set S, = S, u {((xxx)) (x,,, min ( u4)) and p P)) ((x,))}.
12:
13:
end if
end while
15: S= U-SUS,
end for
17:
Train SRŞ1 on S using the weighted loss.
18: return S,
We consider practical batch streaming setting, where an algorithm processes one example time without updating its state until a batch of examples is selected. That is, like in standard streaming settings, the algorithm receives a labeled example, and decides whether to include it in the selected subset or not. Yet, the algorithm is only allowed to update its state after a fixed batch of examples have been selected order to limit the overhead costs (e.g. this typically can include retraining models and extracting gradients). Unlike the pool-based setting where the algorithm receives the entire labeled pool beforehand, a batch streaming setting can be more appropriate when facing a vast training data pool since the algorithm can only process subset of the pool without iterating over the whole pool. Note that any batch streaming algorithm can also be used in a pool-based setting, by simply streaming through the pool in uniformly random fashion. At high level, the IWeS algorithm selects examples by importance sampling where the sampling probability is based on the entropy of models trained on previously selected data. We define sampling probabilities
3

---

Published as a conference paper at ICLR 2023
that allow to trade-off between performance and the computational cost, as well as label-aware or an active learning setting leading to less label annotation costs. As we will subsequently see, these sampling definitions are both easy use and work well in practice.
To define the algorithm in more detail, we let X' E Rd and y = {l....,c) e} denote the input space and the multi-class label space, respectively. We assume the data (x, is drawn from an unknown joint distribution D on X' x Let H = {h: X' - 2) be the hypothesis class consisting of functions mapping from X' some prediction space Z IR and let e: Z x y + R denote the loss.
The pseudocode of IWeS is shown in Algorithm 1. Initially, a seed set So ([Sol = kn) is se- lected uniformly at random from the labeled pool P. Then the algorithm proceeds in rounds E [L...., ......,K R] and it consists of two main components: training and sampling. At the train- ing step at round r. the model(s) are trained using the importance-weighted loss, namely fr arg minkew n Lis.g.))sS w ((h(x),)) v) on the subset S, selected so far, in the previous r - rounds. Depending on the sampling strategy, we may need to randomly initialize two models fr, g. in which case they are trained independently on the same selected subset S, but with different random ini- tializations. At the sampling step at round r, the IWeS algorithm calculates sampling probably for example (x, y) E S based on one of the following definitions:
Entropy-based Disagreement. We define the sampling probability based on the disagreement on two functions with respect to entropy restricted to the labeled example (x. y). That is,
p(x. y) [Py, (v/x) log, P,, (v/x) Pg. (y) x) log2 pg. (v|x)]
(I)
where Py- is the probability of class y with model fr given example x. If the two functions, fr.gr. Ir. disagree on the labeled example (x, y). then p(x, y) will be small and the example will be less likely to be selected. This definition is the closest to the IWeS-V algorithm analyzed in
Section 4 and achieves the best performance when the computational cost of training two models is not an issue. In Appendix A, we show an efficient version of entropy- maasepy-based disagreement that utilizes only one model and achieves similar performance.
Entropy. We define the sampling probability by the normalized entropy of the model f, trained on past selected examples:
p(x,) = Σ ()(lx)))) Py (s/lx/ logz [
VEY
The sampling probability p(x.-) -) is high whenever the model class probability Py, (v'lx) is close to 1/13%, which is when the model is not confident about its prediction as it effectively randomly selects label from V. This definition does not use the label y and thus it can be used in active learning setting where the algorithm can only access the unlabeled examples. Another advantage is that it only requires training one model, thereby saving some computational cost.
We note that entropy- based sampling has been used in algorithms such uncertainty sampling as discussed in the related works section, but using entropy to define importance weights has not been done in past literature.
Based on one of these definitions, the IWeS algorithm then decides whether to include the example into the selected subset S by flipping a coin Q with chosen sampling probability p(x, y). If the ex- ample is selected, the example's corresponding weight w is set to p(x.zy and the example is removed from the labeled pool P = P\ {(x, y)}- This process is repeated until i examples have been lected. Below we use IWeS-dis as an abbreviation for IWeS algorithm with Entropy-based Disagree- ment sampling probability and IWeS-ent for IWeS algorithm with Entropy sampling probability.
Q: 2 (xx(x;); yi) and it is an The weighted loss used to train the model can be written as TP Eiep ((...)))
unbiased estimator of the population risk (xx,))D(((((() v)]. ). Yet such estimator can have a large variance when the model is highly confident its prediction, that whenever P,, (v/x) is large, then p(x. y) is small. This may lead to training instability and one pragmatic approach to addressing this issue is by "clipping" the importance sampling weights (Ionides, 2008; Swaminathan & Joachims, 2015). Thus in our algorithm, we let be the upper bound on the weight of the selected example. Although this clipping strategy introduces an additional parameter, we find it is not too sensitive and, as mentioned in the empirical section, set it fixed constant throughout our evaluation.
The primary computational cost of the algorithm, at each sampling round r, comes from (1) training the model and (2) the inference cost associated with computing the sampling probabilities on
4

---

Published as a conference paper at ICLR 2023
constant fraction of the unlabeled pool of examples. As described in the next section, besides for random sampling, all compared sampling algorithms incur similar re- re-training and model scoring costs at each sampling round.
3 EMPIRICAL EVALUATION
We compare IWeS with state-of-the-art baselines several image classification benchmarks. Specifically, we consider six multi-class datasets (CIFARIO, CIFAR100 (Krizhevsky & Hin- ton, 2009), SVHN (Netzer al., 2011), EUROSAT (Helber et al., 2019), CIFARIO Corrupted (Hendrycks & Dietterich, 2019), Fashion MNIST (Xiao et al., 2017) and one large-scale multi-label Openlmages dataset (Krasin et al., 2017). In the multi-class setting, each image associated with only one label. On the other hand, the multi-label OpenImages dataset consists of 19,957 classes over 9M images, where each image contains binary labels for small subset of the classes (on av- erage 6 labels per image). Further details of each dataset can be found in Table and Table 2 in the appendix.
For all experiments, we consider diverse set of standard baselines from both subset selection and active learning literature (discussed in Section 1.1).
Uncertainty Sampling selects top & examples on which the current model admits the high- uncertainty. There three popular ways of defining model uncertainty s(x) of ex- ample x, namely margin sampling, entropy sampling, and least confident sampling, and all are based on P Pylj|x], the probability of class ÿ given example x according to the model f. Margin sampling defines the model uncertainty of an example x as s(x) = 11 - (PyL0e (h [x] Pşlū2|x)) where ú = argmax, J Py[y/x], 02 argmax, ye>",, Príø[x] are the first and sec- ond most probable classes for model f. For entropy sampling, model uncertainty is defined as sxx = - Ewey P x) ( while for least confidence sampling, it is defined as (xx 1 - max (ūlx).
BADGE of Ash et al. (2019) selects h examples by using the k-MEANS++ seeding algorithm using the gradient vectors, computed with respect to the penultimate layer using the most likely labels given by the latest model checkpoint.
Coreset (e-Center) of Sener & Savarese (2018) selects subset of examples using their embed- dings derived from the penultimate layer using the latest model checkpoint. In particular, the examples are chosen using greedy 2-approximation algorithm for the k-center problem.
Random Sampling selects k examples uniformly at random.
3.1 MULTI-CLASS EXPERIMENTS
Here, we compare the IWeS algorithm against the baselines on the six multi-class image datasets. We use the VGG16 architecture with weights that were pre-trained using ImageNet as well as add two fully-comnected 4096 dimensional layers and final prediction layer. Xavier uniform initialization is used for the final layers. For each dataset, we tune the learning rate by choosing the rate from the set {0.001, 0.002, 0.005, 0.01, 0.1} that achieves best model performance on the seed set. We use batch SGD with the selected learning rate and fix SGD's batch size to 100. At each sampling round r, the model trained to convergence on all past selected examples for at least 20 epochs. For IWeS, we set the weight capping parameter to 2 for all datasets except for CIFAR10 which we decreased to 1.5 in order to reduce training instability.
The embedding layer for BADGE and Coreset is extracted from the penultimate layer having di- mension of 4096. The effective dimension of the gradient vector in BADGE grows with the number of labels, which is problematic for CIFAR 100 as it has 100 classes. More specifically, the runtime of BADGE is given by O (dkTT), which can be large for CIFAR 100 since the dimension of the gra- dient vector from the penultimate layer is d 4096 x 100. the size of the labeled pool is 7'50K, and the number of examples selected in each round is k=5K. In order to solve this inefficiency for CIFAR 100, we split the labeled pool randomly into 100 partitions and ran separate instances of the algorithm in each partition with batch size ke h/100.
Each algorithm is initialized with seed set that is sampled uniformly at random from the pool. Af- ter that, sampling then proceeds in a series of rounds r where the model is frozen until a batch & of examples is selected. The seed set size and sampling batch size k are set to 1K for CIFAR10 10, SVHN,
5

---

Published as a conference paper at ICLR 2023
Eurosst
Feshion
Syhn
6.04
0.25
3.00
Accuracy
Accuracy
3.00
Randam Margin
Handom
0.00
2.24
Hargin
0.00
Badgo
Entropy
dantConfieence
Entropy
Badge
Lozscooniienne
0375
0.69
Entrapy
LoadtCarfidence
0.0
Conseet
Mec5 ds
0:0
Conseet
1Wc5-dss
Coreset
Medi-ch
1000
1500
2000
1520
5000
3000
4000
2000
5003
4066
5000
2006
3003
4000
5000
Number Of Examples
Number Of Examples
Number Of Examples
Cifar10, corrupted
Cifar10
Clar100
3.57
0.550
0.70
0.723
0.535
Rccurecy
Accurecyy
6:42
Random
Random
3.500
Random
0.00
Hargin
Hargh
0.47%
Margin
6.0
LewoCConfidenee
Entroyy
0.53
Entrayy
LoastCorfidnne
Dedge
Badge
Bacge
000
(i65-ds
Cormett
0.22
Mes d5
Coreset
3.40
Corssct
mess-ci
1000
1160
2058
1333
3200
200
4000
2000
2000
siee
4300
5000
5000
1000c
15300
2000e
25000
Number Examples
Number Of Examples
Number Of Examples
Figure 1: Accuracy of VGGI6 when trained on examples selected by IWeS-dis and baseline algo- rithms.
Char100
Euroset
2335
0.302
2555
0.04
2.45
0.733
3.500
Accuracy
8:50
2.45
8:00
Random
Random
Rondom Margin
Margin
0:73
Martinn
0.53
IAv5-ent
0:00
5000
11:00
2000
22003
2000
2000
4300
5000
1190
2393
Examples
Number Examples
Examples
Figure 2: Accuracy of VGG16 when trained on examples selected by eeet-ent, IWeS-dis, margin sampling and random sampling.
EUROSAT, CIFARIO Corrupted, Fashion MNIST, and to 5K for CIFARIO0. The initial seed set size allows at least 50 initial examples per class on average. The experiment was repeated for 5 trials. Any trial that encountered divergent training, i.e. the resulting model accuracy is more than three times below the standard error of model's ' accuracy on seed set, was dropped. We note that this hap- pened infrequently (less than 3% of the time) and all reported averaged results have at least trials.
Figure shows the mean and standard error of VGG16 model's accuracy on held out test set com- paring IWeS-dis to the baseline methods. The IWeS-dis algorithm either outperforms matches the performance of the baseline algorithms for all datasets. We also find that margin sampling con- sistently performs well against the remaining baseline algorithms and that BADGE either matches the performance of margin sampling or slightly underperforms on some datasets (Eurosat, Fashion MNIST, CIFAR100). Coreset admits similar and times slightly poorer performance compared to random sampling.
Next, Figure compares the two variants of our algorithm: IWeS-dis and IWeS-ent. We find that the IWeS-dis performs slightly better than IWeS-ent on most of the datasets. This is not surprising since the IWeS-dis sampling probability leverages label information and more computational power, i.c. trains two models. As explained in Section 4, it also better fits our theoretical motivation. Nevertheless, it is important to note that IWeS-ent, without the label information, still consistently outperforms matches the performance of the baselines for all the datasets.
3.2 MULTI-LABEL OPENIMAGES EXPERIMENTS
Here, we evaluate the performance of the IWeS algorithm on OpenImages v6. We train ResNet101 model implemented using tf-slim on 64 Cloud two core TPU v4 acceleration. and apply batch SGD with batchsize of 6144 and an initial learning rate of 10-4 with decay logarithmically every 5 x 10
6

---

Published as a conference paper at ICLR 2023
examples. We add global pooling layer with fully connected layer of 128 dimensions as the final layers of the networks, which is needed by BADGE and Coreset. The model is initialized with weights that were pre-trained on the validation split using 150K SGD steps. and at each sampling round, the model is trained on all past selected examples with an additional 15K SGD steps.
Open Images
In the previous section, our results show that the IWeS- dis algorithm only slightly outperforms the eWtS-ent algorithm on a few datasets. Also, since the IWeS-dis requires training two neural networks, which is com- putationally expensive in this scenario, we only test the performance of IWeS-ent. Since IWeS-ent does not use the label information, we can also measure the perfor- mance of the algorithm in an active learning setting.
0.79
Pooled
Random
Hargin
0.76
Enbroyy
Bodge
Since OpenImages is a multi-label dataset, the sam- pling algorithms must not only select the image, but also the class. That is, each example selected by an algorithm consists of an image-class pair with cor- responding binary label indicating whether the corre- sponding class is present in the image not. In order to adapt WeS-entt to the multi-label setting, the entropy sampling probability for each image-class pair is defined as p(x, (y., (v/x) loga py, (vlx)
Conmett
0.75
0.4
0.6
0.8
3.0
1.4
Number Of Examples
306
Figure 3: Pooled Average Precision of ResNet101 trained on examples selected by IWeS-ent and the baseline algorithms.
(1 L-PP. yy. (v|x)) log2 (1 - p,, (y|x)). where Py. (v/xx is the model class probability of a positive label round A seed set of size 300K is sampled uniformly at random from the pool, and at each sampling round r, the algorithms select 100K examples. Similarly to the previous section, in order to run BADGE on Openlmages, we divide the pool into 100 partitions and run separate instances of the algorithm in each partition. For IWeS, the weight capping parameter is set to 10.
Figure shows the mean and standard error across 5 trials of the pooled average precision (Pooled AP) metric for each algorithm. As the number of selected examples increases, IWeS-ent outperforms all other baselines methods on the OpenImages dataset. We also find that BADGE performs similarly or even slightly worse than the uncertainty-basee sampling algorithms when the number of selected examples is smaller than 800K, and then outperforms all uncertainty-bast of selected examples increases. Coreset initially performs better than random sampling, but at later sampling rounds, it admits a similar performance to random sampling.
sampling as the number
4 THEORETICAL MOTIVATION
In order to theoretically motivate the IWeS algorithm, we analyze a closely related algorithm which we call IWeS-V, adapted from the IWAL algorithm of Beygelzimer et al. (2009). We prove that IWeS-V admits generalization bounds that scale with the dataset size T and sampling rate bounds that are in terms of new disagreement coefficient tailored to the subset selection framework.
Below, we let [hh = E(x.)) (((,))- (e(h(x).v) denote the expected loss of hypothesis h E H. and h² argmingeH L(h) be the best-in-class hypothesis. Without loss of generality, we consider a bounded loss é: Z x - [0, 1] mapping to the interval [o. 1]. Such a loss can be achieved by any bounded loss after normalization. For simplicity, we assume H. is finite set, but our results can be easily extended by standard covering arguments to more general hypothesis sets such as finite VC-classes.
The IWeS-V V algorithm operates on an i.i.d. example (x1,9)), (x2, v2)..... (XT, Dr) drawn from 'D sequentially. It maintains version space Hi at any time t, with Hi H. At time t, IWeS-V flips a coin Q, E (0, 1} with bias p, defined as
Pt max ((f(x)) v.) E(g(x)), vt)
S.9EH
where He- = {1c He-l: E. 1 PA (= v.) < minw + + p.
Ls ((h'(xx)) ya) + Ar-1)
with A,-1 = / 8 (ogg(22((++1)))) 11 The example is selected if Q = and otherwise it is dis- [-1
carded. The main idea behind this algorithm is thus to define a sampling probability that is in terms of the disagreement between two hypothesis f. g that are not too far from the best model trained on the past selected data, i.e mingen.-, E'= Qa ((h(x,)) ya). The formal IWeS-V V algorithm pseudo-code (Algorithm 2) and all the theorem proofs can be found in Appendix B.
p.
7

---

Published as a conference paper at ICLR 2023
For general, e.g. non-linear, hypothesis classes it is computationally infeasible to find two hypothe- ses f.g E H4 that maximize the expression in equation (3). This main impracticality of IWeS-V V is reason why we developed the IWeS algorithm of the previous section. This drawback is also shared by the IWAL algorithm of Beygelzimer et al. (2009), which computes a sampling probability very similar that of equation (3), but with an additional maximization over the choice of y E y in the definition of the sampling probability pt-
Before continuing we explain how our practical algorithm IWeS-dis, specifically using sampling probability in equation (1), is closely related to the IWeS-V algorithm. Recall that the IWeS al- gorithm trains two models f and g each minimizing the svportance-weighee loss using the data sampled so far. Therefore, each model exhibits reasonable training loss, i.e. they are expected to be included in the version space He of good hypothesis, while the different random initializations (in the case of non-convex neural network hypotheses) results in models that still differ in certain re- gions of the feature space. Thus, the difference equation (1) can be thought of as a less aggressive version of the difference found in the maximization of equation (3).
Another dissimilarity between the two is that the IWeS-dis algorithm is defined for the batch stream- ing setting while the IWeS-dis algorithm and its analysis is developed for the streaming setting. Said differently. the IWeS-V V algorithm can be seen as a special case of the IWeS-dit algorithm with target subset size of 1. To extend the theoretical guarantees of IWeS-V to the batch streaming setting, we can follow a similar analysis developed by Amin et al. (2020) to also find that the effects of delayed feedback in the batch streaming setting are in fact mild as compared to the streaming setting.
4.1 GENERALIZATION BOUND
Next, we turn to the topic of generalization guarantees and we review an existing bound for core- set based algorithms. The guarantees of coreset algorithms are generally focused on showing that a model's training loss on the selected subset is close to the same model's training loss on the whole dataset. That is, given dataset P {(x., yi)]²=
DV the learner seek select a sub- set m < T of examples S = {xx,, W/ along with corresponding set of weights wi...., Wmm such that for some small > 0 and for all h E H. the additive error coreset guarantee holds w,,((((( v/) - Ei= ((h(x.). M))
< eT. The following proposition, which is minor extension of Fact 8 of Karnin & Liberty (2019), allows us to convert a coreset guarantee into a generalization guarantee.
Proposition 4.1. Let h' = argminkeN Σn wxL(h(x(), vf), and let the additive error coreset guarantee hold for any e > O, then for any > O, with probability at least 1 - 8, it holds that L(h) < L(h")+ + 2e + 2/n(4/8)/2T.
As shown above, the generalization guarantee depends linearly on which in turn depends on the size of the subset m. To give few examples, Karmin & Liberty (2019) show that for hypotheses that are defined as analytic functions of dot products (c.g. generalized linear models) this dependence on m is < = O(1 (1/m), while for more complex Kernel Density Estimator type models the dependence e (1//mm). See Mai et al. (2021), Table 1, for examples on the dependency between c and m under different data distributions assumptions (e.g. uniform, deterministic, & Lewis) and for specific loss functions (e.g. log loss, hinge loss).
We now provide a generalization guarantee for the IWeS-V algorithm, which depends on the size of the labeled pool size T. The proof follows from that in Beygelzimer et al. (2009).
Theorem 4.2. Let h² E H be the minimizer of the expected loss function h- = argmin Lh)). For any 8 > O, with probability at least 1 - 5, for any t 2 1 with E {1, 21...... T), we have that h² E H, and that T((]- T(g)) S 2 1 for any S.g E He. In particular, if br the output of IWes-V, then L(hr) - L(h²) < 2 = O (
Unlike the distributionnspeecficc and loss-specific theoretical guarantees proposed in the coreset lit- erature, Theorem 4.2 holds for any bounded loss function and general hypothesis classes. If we ignore log terms and consider the more complex Kernel Density Estimator class of hypotheses, the coreset method of Karnin & Liberty (2019) requires = O(T) coreset samples in order to achieve an overall ((1/VT) generalization bound. As we will see in the next section, the required IWeS sampling rate can also be as high as OT'), but critically is scaled by the best-in-class loss, which in favorable cases is significantly smaller than one.
8

---

Published as a conference paper at ICLR 2023
4.2 SAMPLING RATE BOUNDS
Hanneke (2007) proves that the expected number of labeled examples needed to train model in an active learning setting can be characterized terms of the disagreement coefficient of the learning problem. Later, Beygelzimer et al. (2009) generalizes this notion to arbitrary loss functions, and in this work, we further generalize this for the subset selection setting.
Recall that the disagreement coefficient AAL in Beygelzimer al. (2009) for the active learning setting is defined as
Ex- [aakkeBaL(k x) maxgey [((h(z), v) ((h(((())))))))))))))))(())))( (2),
BAL sup r20
where (hr, - {h E H (h), S S with (At. = E (()()),)
((g(x).))l v)]l- Informally, this coefficient quantifies how much disagreement there is among a set of classifiers that is close to the best-in-class hypothesis. In the subset selection setting, labels available at sample time and, thus, we are able to define the following disagreement coefficient:
Definition 4.1. Let ps(f.g) Ex.,) (l(((xx), y) ((g(x), y)]l and Bs .)) {h : Ps(h, h²) $ r) for 2 The disagreement coefficient in the subset selection setting is defined as
0g sup (xx))~DD max [e(h(x), y) E(h" (xh"(x), v)l
r20
The main difference between the above coefficient and that of Beygelzimer al. (2009) that there is no supremum over all label E 3 both in the definition of the distance and the coefficient's numerator. Instead, the supremum replaced with an expectation over the label space.
The following theorem leverages Os to derive an upper bound on the expected number of selected examples for the IWeS-V algorithm. Below, let F, ((x,, Dis Q:) be the observations of the algorithm up to time t.
Theorem 4.3. For any > 0, with probability at least - 8, the expected sampling rate of the IWeS-V algorithm is: Σ B(,, [px Fi-1] 0 (I()))+++ (Tlgg(//))
Suppressing lower order terms, the above expected sampling rate bound is small whenever the prod- of the disagreement coefficient and the expected loss of the best-in-class is small. In such cases, by combining the above theorem with the generalization guarantee, it holds that IWeS-V returns hypothesis trained on a only fraction of the points that generalizes as well as a hypothesis trained on the full dataset of size T. Theorem 4.3 can be further improved by adapting the ideas found in Cortes et al. (2019) to the IWeS-V algorithm. See Appendix B.4 for this enhanced analysis.
The form of this sampling rate bound is similar to that of Beygelzimer et al. (2009). More con- cretely, under the assumption that a loss function has bounded slope asymmetry, that is K2 = maxyey [8(=.y))((s ((s'.g)) is bounded, with probability at least 8, the expected number suP,,''Z minyey ((=.,))((=='+)))
of examples selected by the IWAL algorithm is given by O (OAL (L(h))++ Tloog(T/5)
Thus, the main difference between the sampling rate bound of the IWAL algorithm and the IWeS- V algorithm are the factors that depends on the two disagreement coefficients: A Ke and Os. Since Os leverages the label information we may expect label-independent disagreement OAI. Theorem 4.4 shows that this is indeed the case.
provide a tighter bound, compared using the
Theorem 4.4. the loss function has a bounded slope asymmetry Ke, then 0g S OALKe.
The above theorem in conjunction with the sampling rate guarantees thus proves that the sampling rate bound of IWeS of Theorem 4.3 is tighter than the sampling rate bound of the IWAL algorithm.
5 CONCLUSION
In this paper we have introduced a subset selection algorithm, IWeS that is designed for arbitrary hypothesis classes including deep networks. We have shown that the IWeS algorithm outperforms several natural and important baselines across multiple datasets. In addition, we have developed an initial theoretical motivation for our approach based on the importance weighted sampling mecha- nism. A natural next step is enforcing notion of diversity it will likely provide improved perfor- mance in the largh-batch sampling setting and thus, we plan to adapt the diversity Citovsky et al. (2021) by replacing the uncertainty sampling component with the IWeS algorithm.
method in

---

Published as a conference paper at ICLR 2023
REFERENCES
Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 2005.
Kareem Amin, Corinna Cortes, Giulia DeSalvo, and Afshin Rostamizadeh. Understanding the ef- fects of batching online active learning. In International Conference on Artificial Intelligence and Statistics, 2020.
Shlomo Argamon-Engelson and Ido Dagan. Committee-based sample selection for probabilistic classifiers. Journal of Artificial Intelligence Research, 1999.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse. uncertain gradient lower bounds. In International Conference on Learning Representations, 2019.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In International conference on machine learning, 2009.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Ros- tamizadeh, and Sanjiv Kumar. Batch active learning at scale. In Advances in Neural Information Processing Systems, 2021.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Region- based active learning. In International Conference on Artificial Intelligence and Statistics, 2019.
Aron Culotta and Andrew McCallum. Reducing labeling effort for structured prediction tasks. In Association for the Advancement of Artificial Intelligence, 2005.
Ryan R Curtin, Sungjin Im, Ben Moseley, Kirk Pruhs, and Alireza Samadian. On coresets for regularized loss minimization. arXiv preprint arXiv: 10845, 2019.
Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P Woodruff. Coresets and sketches for high dimensional subspace approximation problems. Proceedings of the twenty- first anmual ACM-SIAM symposium Discrete Algorithms, 2010.
Chengcheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: comprehensive library for coreset
selection in deep learning. Database and Expert Systems Applications, 2022.
Steve Hanneke. bound on the label complexity of agnostic active learning. In International conference on machine learning, 2007.
Sariel Har-Peled and Soham Mazumdar. coresets for k-means and k-median clustering. In
Proceedings of the shirty-sixth annual ACM symposium on Theory of computing, 2004.
Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2019.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. In International Conference on Learning Representations, 2019.
Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statis- tics, 2008
Tyler B Johnson and Carlos Guestrin. Training deep models faster with robust, approximate impor- tance sampling. In Advances in Neural Information Processing Systems, 2018.
Zohar Karnin and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. In Confer- on Learning Theory, 2019.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference machine learning, 2018
10

---

Published as a conference paper at ICLR 2023
Vishal Kaushal, Rishabh Iyer, Suraj Kothawade, Rohan Mahadev, Khoshrav Doctor, and Ganesh Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference Applications of Computer Vision ( (WACV), 2019.
Krishnateja Killamsetty, S Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference Machine Learning, 2021.
Kwanyoung Kim, Dongwon Park, Kwang Kim, and Young Chun. Task-aware variational adversarial active learning. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021.
Ivan Krasin, Tom Duerig, Neil Alidrin, Vittorio Ferrari, Sami Abu-El-Haija, Alina Kuznetsova, Hassan Rom, Jasper Uijlings, Stefan Popov, Andreas Veit, et Openimages: public dataset for large-scale multi-label and multi-class image classification,, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, University of Toronto, Toronto, Ontario, 2009.
Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li. Jifeng Dai, and Conghui He. Influence selec- tion for active learning. In Proceedings of the IEEF/CVF International Conference on Computer Vision, 2021.
Tung Mai, Cameron Musco, and Anup Rao. Coresets for classification siniiiccation-siipliieeed and strengthened. In Advances in Neural Information Processing Systems, 2021.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning. 2020.
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Advances in Neural Information Processing Systems, 2018.
Stephen Mussmann and Percy S Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Advances in Neural Information Processing Systems, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Finding important examples early in training. In Advances in Neural Information Processing Systems, 2021.
Tobias Scheffer, Christian Decomain, and Stefan Wrobel. Active hidden markov models for infor- mation extraction. In International Symposium Intelligent Data Analysis, 2001.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the JEEE/CVF International Conference on Computer Vision, 2019.
Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, 2015.
Paxton Turner, Jingho Liu, and Philippe Rigollet. A statistical perspective on coreset density esti-
mation. In International Conference on Artificial Intelligence and Statisties, 2021.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint (rX8vv/708.07744 2017.

---

Published as a conference paper at ICLR 2023
Yazhou Yang and Marco Loog. A benchmark and comparison of active learning for logistic regres- sion. Pattern Recognition, 2018.
Donggeun Yoo and In So Kweon. Learning loss for active learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2019.
12

---

Published as a conference paper at ICLR 2023
Supplementary Material
A EXTENDED ALGORITHMIC AND EXPERIMENTAL DETAILS
A.1 DATASET DETAILS
Table I and Table provide further details of the six multi-class classification datasets and the multi- label Open Images dataset, respectively.
Train Test
# Classes
Image Size
Description
CIFARIO
10,000
10
32x32x3
classify the object in the image
SVHN
73,25726,032
10
32x32x3
classify street view house number
CIFAR Corrupted
7,614 2,386
10
32x32x3
classify the corrupted object in the image
Eurosat
8,000
5,000
10
64x64x3
classify land use and land cover satelite image
Fashion MNIST
10,000
10
32x32x3
classify the type of clothes classify the object in the image
CIFAR 100
50,000|10,000
100
32x32x3
Table 1: Multi-class Classification Datasets statistics
Images
Positives
Negatives
Train Validation
37 37,668 19,5669,,,,66
7,6682266
41,620
228,076 1,110,124
367,263
Test
125,436
689,759
Table 2: Open Images Dataset v6 statistics by data split
A.2 MORE EXPERIMENT DETAILS AND RESULTS
When running IWeS, at each iteration, we pass over the labeled pool sequentially in a uniform random order, removing each selected example from the pool. If we exhaust the entire pool before selecting A examples, we start again at the beginning of the sequence and iterate over the remaining examples. In order reduce the number of passes required for the smaller datasets, sampling probabilities of the remaining points uniformly by to where j is the number of passes so far.
scale the
Figure 4 compares IWeS-dis and IWeS-ent for additional three datasets that omit in Section 3.
Fashion moist
Cifar10 comrupted
Citar10
0.74
0.750
AccuroC)
3.80
Accuracy
6.700
0.675
3.02
Margin
Margin
Roncom
Mhi-da
0930
2293
2003
5662
Number Of Examples
Examples
Examples
Figure 4:
Accuracy of VGG16 trained on examples selected by IWeS-ent, IWeS-dis, margin sam-
pling and random sampling.
A.3 EFFICIENT VERSION OF ENTROPY-BASEE DISAGREEMENT
Here we develop an efficient version of entropy-based disagreement which we call IWeS-loss by defining the sampling probability to be proportional to the model's entropy restricted to the labeled examples (x, y) as follows:
p(x, (P)x log P,, (vlx).
13

---

Published as a conference paper at ICLR 2023
where py, (y/x) is the probability of class y with model f, given example As p.. (3/x) increase from to 1, this sampling probability first increase then decrease. Thus the sampling probability high whenever the model is not confident about the model prediction. Unlike IWeS-dis, this definition only requires training one model, thereby saving some computational cost.
Figure 5 compares the two variants IWeS-dis and IWeS-loss. We find that the performance similar across all datasets, with IWeS-loss behave slightly better than IWeS-dis at the first two sample iterations (i.e. Fashion MNIST, CIFARIO 10, Eurosat), and WWeS-dis slightly outperform IWeS-loss as the number of sample iteration increases (i.e. SVHN, Eurosat).
Cifar100
Eurozat
0.375
0.80
0.83
0.34
Accurcc
0.82
3.93
0375
0.8
IWS-dds
IWid-ds
IWs
IWib-los
0.88
loos
5000
10033
15000
20003
15000
1000
2006
3003
4000
5000
3977
2062
2000
2000
3393
Number Examples
Number Examples
Number Examples
Ofar10 corrupted
Oifar10
0,750
0.700
0.225
Accuracs
3.00
Accuracy
0.700
3.64
0.575
0.50
085
MiS--ds
0.00
Number Of Examples
Number Examples
Number Of Exarpples
Figure 5: Accuracy VGG16 trained on examples selected by IWeS-loss and IWeS-dis
B PROOFS OF THEORETICAL GUARANTEE
B.1 PROOF OF PROPOSITION 4.1
Proposition 4.1. Let N = argmin E w;:(h(((),,)) and let the additive error coreset guarantee hold for any O, then for any 0, with probability least 8, holds that L(V) < L(h*) + + 2 /In(4/6)/2T.
Proof of Proposition 4.1.
L(h') Exx,) (x)((x))v))
In(4/6)
en (x:),, vi) +
(Hoeffding inequality)
2T
In(4/8)
wel(h'(x()) v41 +
(0 S ((-) 1)
2T
- wrl(h (x)) + V
In(4/5)
(By the definition h')
2T
ト ((1*((x)) (x:), + v
(n(4/5)
21'
In(4/0)
((xs))>D((("(()))
2/
(Hoeffding inequality)
2T
14

---

Published as a conference paper at ICLR 2023
+ 2v lm(4/8)
B.2 PROOFS FOR STATEMENTS IN SECTION 4.1
Algorithm contains a detailed pseudocode of the IWeS-V V algorithm referred to the main body of the paper.
Algorithm IWeS-V
Require: Labeled Pool P. Initialize: So 0, Ho H.
2: for ( 1, 2,..., 7 do
3: Sample (x). uniformly random from P.
4: Update:
Qi ((h(x:).vi) S
1
Qi ((h(x:), Ac-1
Hi E thEt4-1
H4-1: t
min heHe-1
Ps
pi
1=1
(lon(27(T++))) 2/6)
where 1
t-1
5:
Set Pt f,9EH, ((f(x)) (g((x)))11))
6:
Q2 ~ Bernouli(pp))
7:
if Q. then
Set S. S U of Mx. }
8:
9:
else
10:
S. S1-1-
11:
end if
12: ht arg minNeN Σ (ss.nees, w ((h(x),9).
end for
14:
return ht
In order to prove Theorem 4.2, we first present the following Lemma.
Lemma B.1. Define the weighted empirical loss as L4-1ff) - (Ei=1 Q. [(f(xx). vi)) For all ô > 0 with probability least 6, for all t {I...., T)., and for all fig E He-1, we have ( - (,) - L(f) + L(g) < A.-
Proof of Lemma B.I. Fix any / (T....,T). For any S.g E He- 1. define
Qi (e(f(x:), w) ((g(x.) wi) (L(J) L(g))
2,
Pi
for E fl....,tt 1}. The sequence Z; a martingale difference since
Qi (e(S(x)) ((g(()((xxxx)))))))))) (L() L(g)) Z--1 Pi
E Z1 Z
Due to the fact that
1
12,1 < - ((f(xx), pi
(((xx)..v) v.) ((g(x)), v1) + (f() - L(g) 2
as p; 2 (x(((x)).v)) ((g(x;) y:)) for l,g E H.-1. Thus, we can apply Azuma's inequality,
Pr| L - L(f) L(g)) A.-1l
/8) < 2 2x (-(t 1)4, 1/8) = T(T + 2)
where we used the fact that (x.. 81) is i.i.d. Since H4-1 1 is random subset of H, we take the union bound over S.g H and /. 1. Then take another union bound over T finish the proof. n
15

---

Published as a conference paper at ICLR 2023
Next provide the proof of Theorem 4.2.
Theorem 4.2. Let h' H be the minimizer of the expected loss function h- arg L(h). For any 5 > O, with probability at least 1 - 6, for any 2 with E , T) we have that h" E H, and that [(ʃ) Mgg) 2 for any J,g H4. In particular, if hr the output of IWeS-V V, then L(hr) L(h") 2 ( (og((T6)/TT)
Proof of Theorem 4.2. We show that h E He by induction. Base case holds as h- E H1 = H. Now assuming that he E H4-1 holds, we show that h² H4. Let h' argmin 14-1(f). By Lemma B.I,
- (00)) L(N)) + A.-1 D
since L(h") - L(h)= I 0 by definition of h². Thus, L, I L,-1(h') + D.-1 which means that h² Hr by definition of H4.
Since H4 S Ht-1, Lemma B.1 implies that for any f.9 E He.
[( [(g) L- (S) 1- (g) Ac-1
- A LL-1 (h') A 2AL-1
Noting that h" hh, H4 completes the proof.
B.3 PROOFS FOR STATEMENTS IN SECTION 4.2
Theorem 4.3. For any 8 > O, with probability at least 1 - 6, the expected sampling rate of the IWeS-V V algorithm is: T E(x [pe Fi-1l = o 0s [L(h)TT+ + /Tlog(T/5)) )
Proof of Theorem 4.3. By Theorem 4.2, He C {h H: I(h) - I(hh") 24,-1). Using this fact and that h² is the best in class, holds that
ps (t, h²) = E ((k.))e(((((()))))
(x), < L(h) L(K") S 2L(h") 24.
Thus, letting r = 2h )= + 2 1. it holds that H4 C Bs r)) Then,
((s..)DD/pp 1 FF- = ((( sup
(x() v1) E((g(x)) v() Fi-1l figEHt
2E (s..)))
sup [e(h(x;), 91) - ex(h(xx,, (x)))))))]) F1-1
hERe
2E (s.v))D heBe(h".r) .))
sup
[e(h(xe), 36) - (xxh(xxx),))))))))))( (x)).
< 20sr = 40s 40s(L(h") + 11
By summing the above over E [T). the sample complexity bound of IWeS-V is then given by O (OL((H))+++ which completes the proof.
Theorem 4.4. If the loss function has a bounded slope asymmetry Kr, then S Ae
Proof of Theorem 4.4. We first prove
(h r)) S Bs(h",)) .r) S Bhw Ker).
(5)
The left hand side follows directly from the definition. For the right hand side, assume h Bs(h", ",r), then by the definition of K,, we have
r > (s( = ELDyED [l((A(x), 3) e(h0 (x),(x)) v)ll 2
ExEx sup [(h((), - E(h" = K, PIwa, It")
Kr
wey
16

---

Published as a conference paper at ICLR 2023
where the second inequality comes from
m [6(2,) v) ((2,,))
Ki sup 2, mingey [(2,)) y) ((2,
yyx [((h(x), .)) ((h (x)))x)
sup
x-x minyey [((h(x), v) <(hx(xx,
Ex max [e(h(xx) y) ((h"(x),))
minyey (((h(xx,.) - {(h*(x).
E E maxgey {e(h(x). ((h"(x).))
Exxxx min (((h(x),g) ((hr(x),
Exax max (é(h(x). ((hh(x),))))))
B(,,))= ((..))=((((((x:222 (ch()),,)) (xhx(x).
which follows by basic properties of expectations. As result, we have
E (x,))= (maxhe [((h(x), (x),
05 sup
(By definition of 0s)
r20
r
E (xy)>D [maNkeB (h- Kir) [0(h(x),)) (xh",,,,
< sup
(Use equation (5))
E (x.y)~ maxne (h [((h(z)). y) ((h'(z),)))
sup r20
sup
(Redefine Ker r)
r
EXEX maxpeBBuu.l yey (((((()))))))))))))))))))))))))) - (()"(()))))))))))))))))))))))) (x),
S susup r20
KK&0WAL-
which concludes the proof.
B.4 THE ENHANCED-IWES-Y ALGORITHM
Here we analyze a modified algorithm, which we called the Enhanced-IWeS. V, that uses new slack term defined as
2 Σ Pt + 6 6 log ((3 t)+2/))) IVog
A EIWes
to define the version space in the IWeS-V V algorithm. The theorem below proves that the Enhanced- IWeS-V admits improved sampling rate bound that smaller than the bound in Theorem 4.3 since the square root term also scales with [(h"). In particular, under realizable setting where L(h*) = 0, the sampling rate bound is O (log* (T)), which depends poly-logarithmic in T and smaller than the O log (T)) bound from Theorem 4.3.
Theorem B.2. For all 8 > 0, for all T 2 3, with probably at least 5, the expected sampling rate of the Enhanced-IWeS-V algorithm
T
E DB 0s (L(")I+
( +0 (VL(h>)Tog((T8)) (LINI00(/LI)T117777))) + (Tog)(T/)))
Proof of Theorem B.2. The proof follows from that of Lemma Cortes et (2019). From The- orem 4.3, for t. 2 3,
T
E (GGADDD [p([Fr2)] 40s (L(h") + At-1).
17

---

Published as a conference paper at ICLR 2023
Plugging in the expression of 4-1 Ei= P: to Ei=1 (n [pt Fi-1l, we end up with a recursion on (x.. )~D [pt [Fe-1]:
FIWeS into A and applying concentration inequality to relate
(ANDDDD [r-] S 40gI(h") 40sc1
log ((t - (1)-1//////1
Σ
BO [pa|Fs-1] 02
1
where 01 = =2/108 log
8T 92/2 (T
and C2 is a constant. Then we show for all f 2 3, for constant
c3 = 0 (Vlog (T (T]H//8) and e4 = O (log² (T]H1/6)), we have
B F.-1 I 4 c3
L(h*)
C1
1-1
The above can be proved by induction as in Cortes et al. (2019). By summing the above over / E [T] gives us the result. absorb the dependency on [H] inside the big-O notation.
18


Reviews:
[{"review_id": "l5nHyPLA2i", "reviewer": "Reviewer_q4Qj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper focuses on subset selection. Based on general loss functions and hypothesis classes, the author(s) proposed an importance-weighted subset selection algorithm called IWeS. Through Empirical experiments, the author(s) tried to show the advantage of the proposed algorithm.\n\n---\n", "summary_of_the_review": "The work in this paper is interesting and it considers weighting the selected samples; However, there are some unclear/inadequate aspects in the description (including experiments) of this paper. Maybe it needs the author(s) to clarify them. Thanks.\n\nIn addition, in this paper, the author(s) performed empirical experiments. I am not sure the description would be enough to reproduce since no code seems to be provided (other than some pseudo-code descriptions). \n\n---", "strength_and_weaknesses": "### Strength:\n\n1. Selecting an information subset from a large dataset can effectively reduce the computation time and storage costs. In this paper, the author(s) further considered the weights of selected samples.\n\n2. Empirical evaluations are performed for validating the proposed algorithm.\n\n---\n\n### Weaknesses:\n\nThe theoretical analysis of the proposed algorithm, such as the generalization bound and sampling rate bound, may require further empirical experiments.\n\nFor more details, please see the section of \"Clarity, Quality, Novelty And Reproducibility\".\n\n---\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "f28JIVReUQ", "reviewer": "Reviewer_7Jex", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper presents an approach for subset selection for training models in a batch setting.  The proposed approach, called IWeS, uses importance sampling to select examples for inclusion in the subset, where the sampling probability is based on the model’s entropy.  Experimental results show that IWeS provides moderate to substantial improvements in predictive performance compared to several competing baseline methods.  Furthermore, a theoretical analysis for a closely related approach, IWeS-V, including generalization and sampling rate bounds.  ", "summary_of_the_review": "This is a strong paper, with good empirical and theoretical results.  The experimental results are convincing, showing that the proposed method matches or outperforms a number of baselines.  While there are some issues, as mentioned in the list of weaknesses above, they do not significantly detract from the value of the contributions.  Overall, this is a good paper worthy of acceptance.  \n", "strength_and_weaknesses": "Strengths:\n* IWeS is applicable to arbitrary model families.  It can also be used in an active learning where only unlabeled examples are available.\n* IWeS matches or outperforms a number of competing baseline approaches for several datasets on multi-class and multi-label prediction tasks.\n* Useful theoretical guarantees, in terms of generalization and sampling rate bounds, are provided for a closely related algorithm, called IWeS-V.\n\nWeaknesses:\n* The entropy-disagreement-based variant of IWeS (IWeS-dis) requires training two models, which can be expensive in terms of computation and memory.\n* Theoretical guarantees are provided for the IWeS-V algorithm, which is closely related to the IWeS-dis algorithm.  However, theoretical guarantees are not provided for a variant of the IWeS-V algorithm that is closely related to the entropy-based IWeS algorithm (IWeS-ent), which is computationally less expensive since it requires training only one model.\n* No detailed analysis of the computational costs associated with the proposed methods is presented in the paper.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "U4kGPjCZg1r", "reviewer": "Reviewer_EWd7", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "In this paper, the authors proposed a method for subset selection, which is useful for applications such as active learning. Specifically, in the proposed method, when constructing the subset, data is selected by importance sampling, where the sampling probability relates to the model's entropy. In the subset, the selected data is weighted inversely proportional to its sampling probability for computing a weighted loss function. This method is empirically evaluated on six multi-class classification image datasets and a large-scale multi-label Open Images dataset, and shows good performance when compared with baselines. The theoretical motivation of the proposed method is also presented in the paper. \n\nThe paper's contributions include a theoretically motivated method for subset selection that is suitable for general losses and hypothesis classes and extensive experimental results for evaluating the proposed method and baselines. ", "summary_of_the_review": "The paper presents a subset selection method suitable for deep models with theoretical motivation and extensive experimental results. Although the paper's main idea is based on one prior work, this paper contributes to using model's entropy to define the sampling probability for the benefit of using deep models. This paper is also well-written and completed. ", "strength_and_weaknesses": "Strengths:\n1. In this paper, the considered subset selection problem is promising and useful in many cases, such as efficient deep neural network training, limited budget for data storage, and active learning. The proposed method is applicable for deep models, and for both labeled and unlabeled data during the subset selection.\n2. The proposed method is theoretically motivated and evaluated by extensive experiments on multi-class datasets and a large-scale multi-label dataset. \n3. The paper is well-written and presented. This paper's main messages are clear and easy to follow for readers.  \n \nWeaknesses:\n1. The core idea of the paper is largely based on prior work (i.e., Beygelzimer et al. (2009)), which may reduce the novelty of this paper. Compared with prior work, this paper contributes to using the model's entropy to define the sampling probability to make the method suitable for deep models.\n2. I am wondering if the seed set's size or the quality of pertained models affects the performance of the proposed method. If the seed set is very small, then the model may not be well pretrained (in Line 6, Algorithm 1). In this case, perhaps the data cannot be effectively weighted, especially during the beginning of the training.\n\nOther comments:\nIn the proposed method, it seems that once one data is selected, its weight would be fixed. However, as the model is trained to become better, the weight of one data may also change if recomputed. Then, for the proposed method, it may happen that the weights for one particular data may differ by the order of the data selection. Would it improves the proposed method if recomputing weights of all existing selected data at some specific training epoch?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LbIV9t13omb", "reviewer": "Reviewer_DSZY", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper proposes generic active learning methods for any learning method.  The main method is motivated by the other method with theoretical guarantees. More precisely, the main proposed method is a practical heuristic one. The proposed method is compared with other previous active learning methods and naive ones and shows better performances on the benchmark data sets. ", "summary_of_the_review": "The paper proposes a practical heuristic method for active learning by querying labels. The paper shows non-trivial practical improvements over previous work. ", "strength_and_weaknesses": "Strength:\nThe proposed method shows remarkable improvements over previous work in practice. Although the method does not have any theoretical guarantees, but it is motivated by the other theoretically guaranteed algorithm. \n\nWeaknesses:\nThe weakness of the paper is, as mentioned above, the lack of theoretical guarantees. However, other previous work does not have guarantees either. So, this is not a disadvantage over previous work. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4NdK8PeDrnC", "reviewer": "Reviewer_j2Bp", "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": "", "summary_of_the_paper": "The paper proposes an active learning method by utilizing importance reweighting technique. Authors derive two strategies, including entropy-based disagreement and entropy to sample examples. Then, authors reweight losses by the sampling probability of each example to achieve an unbiased estimator. Experiments are conducted on multiple benchmark datasets.", "summary_of_the_review": "The technical contribution is insufficient and the novelty is limited.\nAlthough the paper reports the extensive experimental results, it suffers from the lack of comparisons with some sota methods.\n", "strength_and_weaknesses": "Strength\n\nThe paper proposes the entropy-based disagreement sampling strategy, which is slightly different from the previous sampling strategies.\n\nThe paper conducts comparison experiments on a large-scale dataset OpenImage, which is relatively realistic.\n\nWeakness\n\nThe main idea of the proposed two strategies is similar to the previous strategies, such as uncertainty sampling and largest margin sampling [1]. It seems that the paper does not propose some new techniques. I think its technical contribution is limited.\n\n[1] Active learning literature survey\n\nThe theoretical analyses proposed in the paper are also trivial. The main results follow the previous works [1][2]. Furthermore, the main theoretical results are based on the unbiased estimator, which has been first proposed in [2].\n\n\n[1] Active Learning for Convolutional Neural Networks: A Core-Set Approach\n[2] Importance Weighted Active Learning \n\nThe experiments are weak in some extent due to the lack of comparison with sota methods. In fact, besides two baselines uncertainty sampling and random sampling, the proposed method is only compared with two methods, BADGE (2019) and Coreset (2017). These methods have been proposed three years ago. The paper is suggested to compare with more recent methods [1]\n\n[1] Influence selection for active learning, 2021\n[2] Task-aware variational adversarial active learning, 2021\n", "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": {}}]

Author rebuttal:

Decision: Accept: poster