Coverage-centric Coreset Selection for High Pruning Rates
Authors: Haizhong Zheng
Rui Liu
Fan Lai
Atul Prakash
Venue: ICLR 2023 poster (2023)
Keywords: Coreset
Data coverage
Data pruning

Abstract: One-shot coreset selection aims to select a representative subset of the training data, given a pruning rate, that can later be used to train future models while retaining high accuracy. State-of-the-art coreset selection methods pick the highest importance examples based on an importance metric and are found to perform well at low pruning rates.  However, at high pruning rates, they suffer from a catastrophic accuracy drop, performing worse than even random sampling. This paper explores the reasons behind this accuracy drop both theoretically and empirically. We first propose a novel metric to measure the coverage of a dataset on a specific distribution by extending the classical geometric set cover problem to a distribution cover problem. This metric helps explain why coresets selected by SOTA methods at high pruning rates perform poorly compared to random sampling because of worse data coverage. We then propose a novel one-shot coreset selection method, Coverage-centric Coreset Selection (CCS), that jointly considers overall data coverage upon a distribution as well as the importance of each example. We evaluate CCS on five datasets and show that, at high pruning rates (e.g., 90%), it achieves significantly better accuracy than previous SOTA methods (e.g., at least 19.56% higher on CIFAR10) as well as random selection (e.g., 7.04% higher on CIFAR10) and comparable accuracy at low pruning rates.  We make our code publicly available at https://github.com/haizhongzheng/Coverage-centric-coreset-selection.

Published as a conference paper at ICLR 2023
COVERAGE-CENTRIC CORESET SELECTION FOR HIGH PRUNING RATES
Haizhong Zheng, Rui Liu, Fan Lai, Atul Prakash Computer Science and Engineering University of Michigan Ann Arbor, MI 48109, USA
{hzzheng, ruixliu, fanlai, aprakash) (areassh@@mmmccio edu
ABSTRACT
One-shot coreset selection aims to select a representative subset of the training data, given a pruning rate, that can later be used to train future models while re- taining high accuracy. State-of-the importance examples based on an importance metric and are found to perform well at low pruning rates. However, at high pruning rates, they suffer from a catastrophic accuracy drop, performing worse than even random sampling. This paper explores the reasons behind this accuracy drop both theoretically and em- pirically. We first propose novel metric to measure the coverage of dataset a specific distribution by extending the classical geometric set cover problem to distribution cover problem. This metric helps explain why coresets selected by SOTA methods at high pruning rates perform poorly compared to random sam- pling because of worse data coverage. We then propose a novel one-shot coreset selection method, Coverage- ers overall data coverage upon distribution example. We evaluate CCS on five datasets and show that, at high pruning rates (e.g., 90%), it achieves significantly better accuracy than previous SOTA meth- ods (e.g., at least 19.56% higher CIFAR 10) as well as random selection (e.g., 7.04% higher on CIFARIO) 10) and comparable accuracy at low pruning rates. We make our code publicly available GitHub'.
coreset selection methods pick the highest
Coreset Selection (CCS), that jointly consid-
well as the importance of each
INTRODUCTION
One-shot coreset selection aims to select small subset of the training data that can later be used to train future models while retaining high accuracy (Coleman al., 2019; Toneva et al., 2018). One-shot coreset selection is important because full datasets can be massive in many applications and training on them can be computationally expensive. A favored way to select coresets is to assign an importance score to each example and select more important examples to form the coreset (Paul et al., 2021; Sorscher al., 2022). Unfortunately, current SOTA methods for one-shot coreset selection suffer catastrophic accuracy drop under high pruning rates (Guo et al., 2022; Paul et al., 2021). For example, for the CIFAR-1O, SOTA method (forgetting score (Toneva al., 2018)) achieves 95.36% accuracy with 30% pruning rate, but that accuracy drops to only 34.03% at 90% pruning rate (which significantly worse than random coreset selection). This accuracy drop is currently unexplained and limits the extent to which coresets can be practically reduced in size.
In this paper, we provide both theoretical and empirical insights into reasons for the catastrophic accuracy drop and propose novel coreset selection algorithm that overcomes this issue. We first extend the classical geometrical set cover problem to a density- distribution cover problem and provide theoretical bounds on model loss as a function of properties of coreset providing specific coverage on a distribution. Furthermore, based on theoretical analysis, we propose novel metric AUCpr. which allows to quantify how dataset covers specific distribution (Section 3. With the proposed metric, we show that coresets selected by SOTA methods high pruning rates have much worse data coverage than random pruning, suggesting linkage between poor data coverage
httpp::///tt thub. com/ haa
http:////waaitigggggggg////o//// hhhngghhnng/Covereeeeeeeeeeeeeee centri coreset se ieeectioon

---

Published as a conference paper at ICLR 2023
of SOTA methods and poor accuracy at high pruning rates. We note that data coverage has also been studied in active learning setting (Ash et al., 2019; Citovsky et al., 2021), )) but techniques from active learning do not trivially extend to one-shot coresct selection. We discuss the similarity and differences in Section 5.
We then propose novel algorithm, Coverage-centric Coreset Selection (CCS), that addresses catas- trophic accuracy drop by improving data coverage. Different from SOTA methods that prune unim- portant (easy) examples first, CCS is inspired by stratified sampling and guarantees the sampling budget across importance scores to achieve better coverage at high pruning rates. (Section 3.3).
We find that CCS overcomes catastrophic accuracy drop at high pruning rates, outperforming SOTA methods by a significant margin, based on the evaluation on five datasets (CIFAR1O, CI- FARI0O (Krizhevsky et al., 2009), SVHN (Netzer et al., 2011), CINICIO (Darlow et al., 2018), and ImageNet (Deng et al., 2009)). For example, at 90% pruning rate, on the CIFARIO dataset, CCS achieves 85.7% accuracy versus 34.03% for SOTA coreset selection method based on forgetting scores (Toneva et al., 2018). Furthermore, CCS also outperforms random selection at high pruning rates. For example, at 90% pruning rate, CCS achieves 7.04% and 5.02% better accuracy than ran- dom sampling on CIFARIO and ImageNet, respectively (Section 4). Our method also outperforms concurrent work called Moderate (Xia et al., 2023) on CIFARIO 10 by 5.04% and ImageNet by 5.20% at 90% pruning rate. At low pruning rates, CCS still achieves comparable performance to baselines, outperforming random selection.
To summarize, contributions
follows:
1. We extend the geometric set cover problem density-based distribution cover problem and provide a theoretical bound on model loss as function of properties of a coreset (Section 3.1, Theorem 1).
2. We propose novel metric AUCpr to quantify data coverage for coreset (Section 3.1). As far as we know, AUCpr is firs metric to measure how dataset covers a distribution.
3. Based on this metric, we show that SOTA coreset selections tend to have poor data coverage at high pruning rates worse than random selection, thus suggesting linkage between coverage and observed catastrophic accuracy drop (Section 3.2).
4. To improve coverage in coresct selection, we propose a novel one-shot coreset selection method, CCS, that uses variation of stratified sampling across importance scores to im- prove coverage (Section 3.3).
5. We evaluate CCS on five different datasets and compare it with six baselines, and we find that CCS significantly outperforms baselines as well random coreset selection high pruning rates and has comparable performance at low pruning rates (Section 4).
Based on our results, we consider CCS to provide a new strong baseline for future one-shot coreset selection methods, even at higher pruning rates.
PRELIMINARIES
2.1 ONE- CORESET SELECTION
Consider classification task with training dataset containing N examples drawn i.idd. from an underlying distribution P. We denote the training dataset as = [xx,, y4) W)) where x; is the data, and y; is the ground-trutte truth label. The goal of one-shot coreset selection is to select training subset S' given a pruning rate a before training to maximize the accuracy of models trained on this subset, which can be formulated the following optimization problem (Sener & Savarese, 2017):
min
Bxy MM y5 hs:)),
S'CS::
$1-a
where is the loss function, and h& is the model trained with a labelled dataset S'.
SOTA methods typically assign importance score (also called difficulty score importance metric) to each example and preferably select more important (difficult) examples to form the core- set. One proposed importance score is the Forgetting score (Toneva al., 201 8)) which is defined as
2

---

Published as a conference paper at ICLR 2023
the number of times example is incorrectly classified after having been correctly classified earlier during model training. Another area under the margin (AUM) (Pleiss et al.. 2020), which is a data difficulty metric that identifies mislabeled data. Another importance metric, EL2N score (Paul et al, 2021) estimates data difficulty by the 1.2 norm of error vectors.
SOTA algorithms based these metrics all prune examples with low importance first (Sorscher et al., 2022). As discussed in Sorscher et al. (2022), harder examples usually contain more informa- tion and are treated more important data and thus more desirable for inclusion in a coreset.
2.2 CATASTROPHIC ACCURACY DROP WITH HIGH PRUNING RATES
Although SOTA coreset methods (Toneva et al., 2018; Coleman al., 2019; Paul et al., 2021) report encour- aging performance at low pruning rates, a catastrophic accuracy drop is observed as pruning rate increases (Guo et al., 2022; Paul et al., 2021). For instance, as shown in Figure I, SOTA methods based on forgetting number and AUM outperform random sampling when the pruning rate less than 70% but considerably underperform random sampling at 90% pruning rate, achieving only 34.03% and 28.06% accuracy, respectively, which are much worse than 79.04% for random sampling.
80
Accuracy
60
Rancom
40
Forgetting
Ertropy
20
20
60 Data Pruning Rate (%)
We hypothesize that this accuracy drop is a result of bad data coverage caused by the biased pruning of importance-based methods. In this paper, we conduct an in-depth study on this catastrophic accuracy drop and pro- pose a novel coreset selection method that overcomes the catastrophic accuracy drop at high pruning rates.
Figure 1: Existing coreset solutions have better accuracy than random sam- pling at low pruning rates, but perform worse at high pruning rates.
THE COVERAGE OF CORESETS
We start by studying data coverage provided by different coresets. We first extend the classical geo- metric set cover to a density-bant -based distribution cover problem and propose a novel metric to compare the data coverage of different coresets (Section 3.1). We then show that biased pruning on easy data leads to poor data coverage of coresets with high pruning rates (Section 3.2). In Section 3.3, inspired by stratified sampling, we propose novel coverage-cent centric coreset selection method which jointly consider both coverage and importance of each example based on given importance metrics.
3.1 DENSITY-BASED PARTIAL COVERAGE
To compare the data coverage of different coreset methods, we need to quantitatively measure how well dataset S covers a distribution P. In classical geometric set cover setting (Fowler et al., 1981; Sener & Savarese, 2017), we say set S' is r-cover of another set S, when set of r-radius balls centered at each element in S' covers the entire S. The radius r can be used as metric to measure coverage of S' on However, how to measure the coverage of a dataset on a distribution is not well-studied.
To measure how well a set covers a distribution, we extend the classical geometric set cover to the density-based distribution cover. Instead of covering set, study the covering a distribution Pa and consider probability density in different areas of the input space. Instead of taking a complete cover, we introduce the cover percentage p describe how set covers different percentages of distribution to better understand the trade-off between cover radius r and cover percentage p: Definition 1 (p-partial r-cover). Given metric space (X,d) d), set S X is p-partial r-cover for a distribution Pa on the space X if:
where Ba(x,r) r) = fx' E X d(x,x') S r) a r-radius ball whose center is ε. measures coverage (which will usually express a percentage and refer as percentage coverage), and
3

---

Published as a conference paper at ICLR 2023
is the probability measure" corresponding probability density function P.. The probability measure μ represents the density information in the input space.
For a model trained on a r-cover coreset, Sener & Savarese (2017) proved a bounded risk on the entire training dataset. In Theorem 1 below, extend their result to the distribution coverage scenario. The proof of Theorem relies on the same assumptions as in Sener & Savarese (2017), in particular Lipschitz-continuity loss function and zero training error the coreset. The zero training error assumption may not always be realistic, but Sener & Savarese (2017) found that the resulting bounds still hold and rely on the same assumption. The proof of theorem can be found in the Appendix C.
Theorem 1. Given n i..dd samples drawn from P.. as S = {æ;, Ye Vetre(m) where y: E [C] is the class label for example Tú, a coreset S' which is a p-partial r-cover for Pa on the imput space X, and an e > 1 1-p p, if the loss function 1(- y, w) is A >--Lipschitz continuous for all y, w and bounded by L. the class-specific regression function (x) = ply = dxa) is -xp-Lipshittz.on for all and (xx, y; hs)) ) = 0,
V(x y) E S', then with probability least E:
P log p+c-1
Σ SSSSS
1( yi hs)) + + X0 + 4
TI
2n
Theorem 1 shows that the model trained on a y-partial r-cover coreset S' has a bounded risk on the entire training dataset S. There several implications of Theorem 1: 1) A model trained on a p-partial r-cover coresct has a training risk bounded with the covering radius r and an additional term. This term goes to zero as n increases infinity. Also, we want a small e, a large p and a small radius r to get high probability small bound on the loss. 2) The probability that Equation 2 holds bounded by cover percentage p (since 1 c < p). This indicates that the bound in Theorem becomes meaningless (low probability) when the cover percentage is too small. 3) Theorem is more general form Theorem Sener & Savarese (2017); we set p = (i.e., complete cover), these two theorems are the same.
Definition shows that, for a given set S and distribu- tion Pa. the cover percentage p increases with the cover radius r. Conversely, given a cover percentage p and a set S, to achieve p percent coverage on distribution Pa. For a given set S and distribution PR., we can plot p-r curve to represent this relationship. In practice, the distribution P, is unknown. So, estimate the cover percentage for a given subset S' of the training dataset and ra- dius by measuring the fraction of the test dataset that is covered 3 To assess coverage for radius r, we use the L,2 distance between activations of the final convolutional layer of model trained with the entire dataset as the dis- tance metric d, as suggested Babenko & Lempitsky (2015); Sharif Razavian et al. (2014); Hsieh et al. (2018),
1.2
W/o Pruning
get a minimum cover radius for the S
1.0-
Prune 90% (Random)
0.8
Prune 90% (Forgetting)
Radlus
0.4
0.2
0.0
20
40 60
80
Cover percentage P (%)
The p-r curves of different subsets of CIFARIO training dataset. The dataset without any pruning has the lowest curve (blue). Forgetting curve (green) and random curve (orange) have a crossover around p = 80%.
Figure 2:
Figure shows the p-r curves for several subsets CI- FARI0 training dataset: (1) entire dataset (no pruning); (2) random coreset at 90% pruning rate (i.e., random 10% of the training data); and (3) coreset selected based forgetting score as the importance metric, as proposed by Toneva et al. (2018). As expected, the required radius increases to get the desired cover percentage p for all coresets. Also coreset with no pruning has the lowest curve, as expected. In general, lower curves are better and we expect models based on
By Ridon-Ni thcorem, there is a probability measure pc: Pa(x)do dp(x).
We noticed that some misclassified examples have much larger minimum cover radius than other data. To eliminate the influence of outliers, when we plot p-r curves, we ignore the data misclassified by the model trained with the entire CIFAR10 dataset (with a 95. 25% accuracy).
4

---

Published as a conference paper at ICLR 2023
the corresponding datasets have lower loss. However, find that there is crossover between forgetting curve and random curve around = 80%, making a comparison less obvious.
To make more obviously quantitative comparison, we propose use area under the p-r curve, AUCpr as proxy metric to assess the quality of a coreset selection strategy. Lower values of AUCpr suggest better coverage by the coreset. We note that AUCpr is the expected minimum distance between examples following the underlying distribution Pp. to those in the coreset, as stated in the following proposition (proved in Appendix C):
Proposition 1. Given a metric space (X, d), a distribution PRo. cover percentage p. a set S, and f-(p) [0,1] [0, +00 representing the mapping between and r, if fr Riemann- integrable, the AUC of the p-r curve AUCpr(S) = So (p(ddp = ExnP, [d(S, where d(S,x) esn d(x',m). m))
In practice, we can assess AUCpr with test set Drest : pr (r)) = Exe [ming's es d(æ', ..). We also note that this expected minimum distance (and thus AUC) is related in Theorem 1; lower values of AUCpr are preferred for lower loss and thus higher model accuracy.
3.2 COVERAGE ANALYSIS ON CORESETS
Table 1: AUCpr of different methods with different pruning rates, With low pruning rates (30%, 50%), forgetting and AUM have similar A to random. With high pruning rates (80%, 90%), forgetting and AUM have larger p than random, which means worse data coverage.
Pruning Rate
30%
50%
70%
80%
90%
Random
0.496
0.509
0.532
0.552
0.589
Forgetting
0.492
0.511
0.551
0.580
0.631
AUM
0.496
0.518
0.558
0.586
0.646
Table I shows the A for different CIFARIO coresets with different pruning rates. With 30% 50% prun- ing rate, forgetting and AUM have similar AUCpr to ran- dom sampling. However, with a pruning rate larger than 70%, forgetting and AUM have larger AUCpr than ran- dom pruning, suggesting that forgetting and AUM can expected to have
100
80
Accuracy
70
accuracy than random pruning.
60
50
Pruning Furgetting
The reason behind higher AUC - for forgetting and AUM is that they prune casy examples, which tend to be located in the high-density area of distribution since more com- mon examples often tend be well-separated easier ex- amples for classifiers. Low pruning rate coresets still con- tain plenty of easy examples for all methods; thus cover- age is not significant factor at low pruning rates. How- ever, with high pruning rates, coresets can completely exclude examples from the high-density areas, reducing coverage and raising AUCpr. and thus potentially raising loss and reducing accuracy.
30
20
0.50
0.55
0.60
0.65
AU
The relationship between AUCpr and accuracy. Different col- ors stands for different coreset selected methods. A larger circle size indicates a higher pruning ratio on the dataset. Smaller AUCpr often ends up with bet- ter accuracy. With high pruning rates (larger balls), forgetting and AUM have a higher AUCpr and worse accuracy.
Figure 3:
For the data points Table 1, Figure plots model ac- curacy and AUCpr. Size of the ball at point represents pruning rate for that point- larger ball size indicates a larger pruning rate. The plot generally confirms our intu- itions from Section 3.1 that higher AUC,r values tend to lead to lower model accuracy.
3.3 METHODOLOGY: COVERAGE-CENTES CORESET SELECTION
Based on our density- based distribution setting in Section 3.1, if the sampling budget is limited, easy examples in the high-density area provide more coverage than hard examples in the low-density area.
5

---

Published as a conference paper at ICLR 2023
Algorithm 1: Coverage-centric Coreset Selection (CCS)
Inputs:
$ -(1;; yi, si)) dataset with the importance score for each example;
0: dataset pruning rate; ,3: hard cutoff rate (3 I 1 - a); k: the number of strata.
2 3' / 8 n B] hardest examples }:
/+ Prune hard examples first +/
R1 R2.... Rg < Split scores in S' into i ranges with even range width;
13 + [ B; consists of examples whose scores are in RR =1.kk:
m
a)
/x m is total budget: across all strata */
6 Sc t Ø;
/N Initialize the coreset */
while B + do
Bmin <- arg min B
/+ Select the stratum with fewest examples +/
3EB
mB + min min
m B
/* Compute budget for selected stratum +/
10
Sg f randomly sample mg examples from Bmin
11
S. < S. USB:
/+ Update the coreset +/
12
+ B (Bmin))
/ Done with selected straum */ /* Update total budget for remaining strata */
13
m <- mB:
14
return S
/+ Return the final coreset */
SOTA methods prune low-importance (casy) data from the high-density area, which contributes to a larger AUCpr value and thus possibly lower model accuracy at high pruning rates.
Inspired by this insight, centric Coreset Selection (CCS), presented in Algorithm 1. CCS is still based on existing importance scores. However, unlike SOTA methods that simply select im- portant examples first, CCS aims to still guarantee the data coverage on high-density area at high pruning rates to improve coverage and lower the value of AUCpr. Compared to SOTA methods, CCS still assigns the sampling budget to the high-density area contain- ing easy examples at high- -ohnninuunngg rates, which pro- vides larger coverage to the underlying distribution. Compared to random sampling, CCS assigns larger sampling budget to the low-density area, where hard examples informative for training.
propose novel coreset selection method called Coverage-
15000
SOTA
12500
#Examples
10000
7500
2500
CCS first divides the dataset into different non- overlapping strata based on importance scores. Each stratum has a fixed-length score range, but may in- clude different numbers of examples. We fix an ini- tial budget on the number of examples to be chosen from each strata, based on the desired pruning rate, but, if stratum has fewer examples than the budget, remaining budget is evenly assigned to other strata.
50
125
200
Area under the margin (AUM)
Figure 4: CIFARIO data distribution with AUM as the importance metric (lower AUM values are more important). At 70% pruning rate, SOTA method selects data from the red region, since it prune tow-importance (easy) examples first. Our method, CCS, selects data from the green region using stratified sampling across the importance metric, along with pruning hardest examples on the left. The coreset selected by the SOTA method lacks "easy" examples on the right in the high-density region.
Thus, stratified sampling differs from random sam- pling in that examples from "dense" stratum are less likely to be sampled than examples in "sparse" stratum. Also, with a low pruning rate, strati- fied sampling tends to first discard data from low- importance strata, similar to SOTA methods. At high pruning rates, stratified sampling diverges from SOTA methods in that importance strata still get budget to guarantee data coverage. (In Appendix D.5, we discuss another coreset selection method based on importance sampling.)
Further evaluations confirm that coresets selected by CCS have lower AUCpr (i.e., hetter coverage) than the SOTA method, which prunes easy examples first. See Appendix D.2.

---

Published as a conference paper at ICLR 2023
Before CCS assigns budgets to strata, CCS prunes / percent "hard" examples based importance scores (Line 2 in Algorithm 1). This is based on two insights: (1) Mislabeled examples often also have higher importance scores (S (Swayamdipta et al., 2020) but do not benefit accuracy. As the pruning rate increases, the percentage of mislabeled data in the coreset also rises, which hurts model accuracy. (2) When data is really scarce, we need more data from higher-density areas to get better coverage. Pruning hard examples helps allocate more budget to high-density strata. In practice, we use grid search to find
hyperparameter. We discuss how /3 impacts training in Section 4.2 and further details on selecting 33 in Appendix B.
In Figure 4, we show an example on CIFARIO to compare the fraction of data selected between a SOTA method (AUM) and CCS (also based on AUM) for 70% pruning rate. The data selected by the SOTA method (Pleiss et al., 2020), shown with red shading, prunes all the easy examples (high AUM value). In contrast, CCS selects the data in the green region. Notice that CCS selects slightly fewer examples the curved area (around 140) because those stratum had insufficient examples for the budget; excess budget is evenly assigned to other strata.
EVALUATION
We evaluate CCS against six baselines (random, entropy, forgetting, EL2N, AUM, and Moderate) on five datasets (CIFAR10, CIFAR100, SVHN, CINIC10, and ImageNet). In total, trained over 800 models for performance comparison. We find that CCS outperforms other baselines at high pruning rates while achieving comparable accuracy at low pruning rates. We conduct an ablation study (Section 4.2) to better understand how hyperparameters and different components influence the accuracy. Due to space limits, we include experimental setting in Appendix B. All training is repeated 5 times with different random seeds to calculate mean accuracy with standard deviation.
Baselines. We compare CCS with six baselines, with the latter five being SOTA methods: 1) Ran- dom: Select examples with uniform random sampling to form coreset. 2) Entropy (Coleman al., 2019): Select highest entropy examples for coreset, since entropy reflects uncertainty of training ex- amples and thus more importance to training. 3) Forgetting score (Toneva et al., 2018): Select examples with highest Forgetting scores, which is the number of times an example is incorrectly classified after being correctly classified earlier during model training; 4) EL2N (Paul et al., 2021): Select examples with highest EL2N scores, which estimate data difficulty or importance by the L2 norm of error vectors. 5) Area under the margin (AUM) (Pleiss et al., 2020): Select examples with highest AUM scores, which measures the probability gap between the target class and the next largest class across all training epochs. A larger AUM suggests higher difficulty and importance. 6) Moderate (Xia et al., 2023) is a concurrent work that proposes distance-basse based score for one-shot coreset selection. Moderate treats examples close to the median value of feature space as more im- portant examples. For all baselines, we prune unimportant examples first when selecting coresets, based on a chosen importance metric. In Section 4.1, we combine CCS with AUM score, and we also discuss the performance of combining CCS with other importance metrics in Appendix D.
4.1 CORESET PERFORMANCE COMPARISON
As shown in Figure 5, our proposed method CCS significantly outperforms SOTA schemes as well as the random selection high pruning rates by comparing CSS with six other baselines on three datasets (CIFARIO, 10, CIFAR 100, and ImageNet). We observe that, besides Moderate, other four SOTA coreset methods tend to have similar or higher accuracy than random at 50% or lower pruning rates, but they have worse performance than random at high pruning rates (e.g., 80% and 90%). CCS achieves better accuracy than all other baseline selection methods at high pruning rates and achieves a comparable performance at low pruning rates. For example, at a 90% pruning rate of CI CCS achieves 7.04% better accuracy than random sampling. And CCS achieves 5.0 5.08% better accuracy than random sampling on ImageNet at 90% pruning rate. We have similar findings on SVHN and CINICIO (detailed results in the Appendix D). CCS outperforms all baselines at high pruning rates all these datasets.
4.2 ABLATION STUDY & ANALYSIS
We first observe that, when A = 1 and / = 0, CCS is equivalent to random sampling, i.c., random sampling is a special case of CCS. This guarantees that CCS, with appropriate choice of hyperpa-
7

---

Published as a conference paper at ICLR 2023
Test Accuracy (%)
Test Accurao 30 (%6
Test Accurac (%)
Random Fergetting
Random
80
Forgetting
Fargetting
AUN
Entryy
Entropy
Entropy
60
EL2N
EL2N
EL2N
Moderate
Moderate
Mod crate
(Ours)
20
16c
40
60
80
100
40
60
50
100
Data Pruning Rate (36)
Data Pruning Rate (%)
Data Pruning Rate (%)
Evaluation CIFARIO.
(b) Evaluation CIFARI00.
Evaluation ImageNet Ik.
Figure 5: Performance comparison between our proposed method (CCS) and other baselines CIFARIO, CIFARI00, and ImageNet- Ik. The pruning rate the fraction examples removed from the original datasets. The evaluation results show that our method achieves better performance than all other baselines at high pruning rates (e.g., 70%, 80%, 90%) and comparable performance at low pruning rates (e.g., 30%, 50%). We also present detailed numerical numbers in Appendix D.
100
100
Accuracy
Accuracy
80
85
90%
50%
90%
50%
75
80%
30%
60
80%
30%
70%
70%
50
75
100
150
10
30
40
50
60
Number strata
cutoff rate (%)
(a) Relationship between and accuracy.
(b) Relationship between & and accuracy.
Figure 6: Ablation study on the number of strata (k) and hard cutoff rate (3). We apply CCS with the forgetting score on CIFARIO. Each curve corresponding to a pruning rate. Different k leads similar accuracy. The optimal / goes up the pruning rate increases.
rameters, will not underperform random sampling. practice, larger values of & tend to be more useful to get the stratified sampling effect and to outperform random. Also, shown in Figure 6(a), for large k values, we found that the number of strata not a sensitive hyperparameter.
We then study the hard cutoff rate B. From Figure 6(b), observe that the optimal hard cutoff rate goes up as the pruning rate increases. This is expected since a larger hard cutoff rate helps shift more budget to high-density strata (see Section 3.3), When the total data budget is limited, better coverage on high-density strata helps improve model performance. We also observe that the optimal is 0 when the pruning rates is 30% and 50%. possible reason that the percentage mislabeled data is low in CIFARIO 10 (Pleiss et al., 2020), and deep neural network is robust to small portion of noisy data (Rolnick et al., 2017). Grid search for can introduce extra costs in selecting effective coresets. However, we note that our paper shows the possibility of achieving better accuracy than random sampling at high pruning rate. We leave how to efficiently finetune / for future work.
Table 2:
Ablation study on different components of coverage-centric coreset select method for importance metric of forgetting score. Best accuracy is in bold in each column.
Pruning Rate
30%
50%
70%
80%
90%
Random
94.33
93.4
90.94
87.98
79.04
Forgetting
95.36
95. 25.29
90.56
62.74
34.03
Stratified only
95.23
95.13
90.78
81.82
59.35
Prune hard only
91.50
88.46
85.62
80.98
80.62
CCS (Stratified Prune hard)
95.40
95.04
92.97
90.93
85.7
8

---

Published as a conference paper at ICLR 2023
Next, we study the impact of stratified sampling and pruning hard examples on model accuracy. We measure the forgetting score for CIFARIO and then apply only stratified sampling or only pruning hard examples to select the coreset, respectively, in Table 2. By comparing stratified sampling only with the vanilla forgetting method (pruning easy first), we observe that applying stratified sampling improves accuracy compared to the vanilla forgetting method, but it is still inferior to random sampling when we prune 80%, or 90% fraction of examples. Sorscher et al. (2022) discussed that pruning hard data is better strategy than pruning easy data when the original entire data is scarce. In our evaluation, we observe that pruning hard data outperforms pruning easy data at high pruning rates, but still has worse accuracy than CCS.
We also considered using proportional importance sampling strategy to improve coverage that samples examples proportional after mapping importance score to probability for one dataset. Unfortunately, the strategy underperformed random sampling at high pruning rates (results in Ap- pendix D.5). This evaluation suggested it non-trivial to beat random at high pruning rates, even for strategy that improves coverage.
5 RELATED WORK
Besides the coreset methods based on entropy (Coleman et al., 2019), forgetting score (Toneva et al., 2018), AUM (Pleiss et al., 2020), and EL2N scores (Paul et al., 2021) discussed in Section 2.1. Sorscher et al. (2022) use k-means to estimate importance scores, and Sener & Savarese (2017) apply greedy k-center to choose the coreset with good data coverage. However, k-means and k- center algorithms need to calculate the distance matrix between examples, which leads to an (n?)) time complexity and are expensive scale to large datasets.
Data selection also studied in active learning and some methods recognize importance of diversity or coverage in data selection (Ash et al., 2019; Citovsky et al., 2021; Beluch et al., 2018; Hsu & Lin, 2015; Chang et al., 2017). While our scheme shares the idea of improving coverage with these methods, one-shot coreset selection philosophically differs from dataset selection in active learning: one-shot coreset selection aims to select a model agnossic coreset for training new models from scratch, while active learning aims to select subset that, given the current state of the model, is to improve the model in the next training round. For example, BADGE (Ash et al., 2019), diversity- based selection method in active learning, selects a subset by performing k-means++ on the gradient embedding based on the latest model and then repeats that for subsequent rounds during training.
Another significant difference is that active learning, total number of examples queried across all rounds of training can be much larger than the size of a one-shot coreset. For instance, in experi- mental results of Ash et al. (2019), BADGE queried a different set of 10K (20%) examples on every round for the CIFAR- 10 dataset. The total number of different examples queried across all rounds is even larger. In contrast, CCS finds a fixed small subset (e.g. 10% data) that can be used to train new models from scratch while achieving high accuracy.
Another popular coreset selection area is the coreset selection for classical clustering problems such as k-means and k-median (Feldman et al., 2020; Feldman & Langberg, 2011; Cohen-Addad et al., 2021; Huang et al., 2019). However, these coreset methods are usually designed based on the good mathematical property of classical clustering. For example, importance sampling is a common practice for coreset for clustering (Huang & Vishnoi, 2020), but it does not generalize well in the deep learning classification scenario.
6 CONCLUSION
We conduct an in in-depth study to understand the catastrophic accuracy drop issue of one-shot coreset selection. By extending classical geometric set cover to density-based based partial cover, we propose a novel data coverage metric and show that existing importance-bases coreset selections lead poor data coverage, which in turn degrades model performance. Based on this observation, we design a novel Coverage-centric Coreset Selection (CCS) method to improve the data coverage, which empirically outperforms other baseline methods five datasets. Our paper shows that it is possible to achieve much better accuracy than random sampling, even in a high pruning rate setting, and provides a strong baseline for future research.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We also include detailed experimental setting in the appendix, and the code is available at GitHub.
ACKNOWLEDGEMENTS
We thank Yuwei Bao, Tony Zhang, and Yiwen Zhang for helpful discussions, We thank the anony- mous reviewers and area chairs for their time and efforts during the reviewing process. Their feed- back help us better improve our paper. This work is partially supported by DARPA under agreement number 885000. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of our research sponsors.
REFERENCES
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.
Artem Babenko and Victor Lempitsky. Aggregating deep convolutional features for image retrieval. arXiv preprint arXiv:
2015.
William H Beluch, Tim Genewein, Andreas Nümberger, and Jan M Köhler. The power of ensembles for active learning in image classification. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9368-9377 , 2018.
Christopher Berlind and Ruth Umner. Active nearest neighbors in changing environments. In Inter- national conference on machine learning, pp. 1879-1879. PMLR, 2015.
Haw-Shiuan Chang, Erik Learned-Miller, and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. Advances Neural Information Processing Systems, 30, 2017.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Ros- tamizadeh, and Sanjiv Kumar. Batch active learning at scale. Advances in Neural Information Processing Systems, 34:1 1933-11944, 2021.
Vincent Cohen-Addad, David Saulpie, and Chris Schwicgelshohn. A new coreset framework for clustering. In Proceedings of the 53rd Annual ACM SIGACT Symposiun on Theory Computing, pp. 182, 2021.
Cody Coleman, Christopher Ych, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference on Learning Representations, 2019.
Luke N Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey. Cinic-10 10 is not imagenet or c0f arXiv preprint arXiv: 1800.03555 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. leee, 2009.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 569-578, 2011.
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, pca, and projective clustering. SIAM Journal on Computing, 49(3): 601-657, 2020.
Robert Fowler, Michael S Paterson, and Steven L Tanimoto, Optimal packing and covering in the plane np-complete. Information processing letters, 12(3):133-137, 1981.
10

---

Published as a conference paper at ICLR 2023
Chengcheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. arXiv preprint arXiv:2204.08499 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffdding, pp. 409-4049440 Springer, 1994.
Kevin Hsieh, Ganesh Ananthanarayanan, Peter Bodik, Shivaram Venkataraman, Paramvir Bahl, Matthai Philipose, Phillip Gibbons, and Onur Mutlu. Focus: Querying large video datasets with low latency and low cost. In 13th USENIX Symposium Operating Systems Design and Implementation (OSDI 18), pp. 269-286, 2018.
Wei-Ning Hsu and Hsuan Tien Lin, Active learning by learning. In Twenty-Ninth AAAI conference on artificial intelligence, 2015.
Lingxiao Huang and Nisheeth K Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 4416-1429, 2020.
Lingxiao Huang, Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for clustering with faimesss con- straints. Advances in Neural Information Processing Systems, 32, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. In ICLR, 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URL http://ufidl. stanford. edu/ housenumbers https/nipsssoio1o/ housenumbers. pdf.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Find- ing important examples early in training. Advances in Neural Information Processing Systems, 34, 2021.
Geoff Pleiss, Tianyi Zhang, Ethan Elenberg, and Kilian Q Weinberger. Identifying mislabeled data using the area under the margin ranking. Advances in Neural Information Processing Systems, 33:17044-17056, 2020.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning robust to massive label noise. arXiv preprint arXiv: /0694, 2017.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set 2017.
approach. arXiv preprint
Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson. Can features off- the-shelf: an astounding baseline for recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 806-813, 2014.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. arXiv preprint
2022.
Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie. Yizhong Wang, Hannaneh Hajishirzi, Noah A Smith, and Yejin Choi. Dataset cartography: Mapping and diagnosing datasets with training dynamics. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9275-9293. 2020.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. In International Conference Learning Representations, 2018.
11

---

Published as a conference paper at ICLR 2023
Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, and Tongliang Liu. Moderate coreset: A universal method data selection for real-world data-efficient deep learning. In International Conference Learning Representations, 2023.
12

---

Published as a conference paper at ICLR 2023
A OVERVIEW
This appendix provides details on our experimental setting, theoretical analysis, and additional eval- uation results. In Section B, we introduce the detailed setup of our experiment to improve the reproducibility of our paper. In Section C, we provide proof for Theorem I and Proposition 1. At last, in Section D. we present evaluation results on SVHN and CINICIO. We also conduct a study on the transferability of the coreset selected by CCS.
B DETAILED EXPERIMENTAL SETTING
CIFARIO and CIFARI00 (Krizhevsky et al.. 2009). We use ResNet18 (He et al., 2016) as the network architecture for CIFARIO/CIFAR 100. For all coresets with different pruning rates, we train models for 40, 000 iterations with 256 batch size (about 200 epochs over the entire dataset). We use the SGD optimizer (0.9 momentum and 0.0002 weight decay) with a 0.1 initial learning rate. The learning rate scheduler is the cosine annealing learning rate scheduler (Loshchilov & Hutter, 2017) with a 0.0001 minimum learning rate, We use a 4-pixel padding crop and a randomly horizontal flip as data augmentation.
SVHN (Netzer et al., 2011). We use ResNet18 (He et al., 2016) as the network architecture. For all coresets with different pruning rates, train models for 30, 000 iterations with 256 batch size (about 100 epochs over the entire dataset). We use the SGD optimizer (0.9 momentum and 0.0002 weight decay) with 0.1 initial learning rate. The learning rate scheduler is the cosine annealing learning rate scheduler (Loshchilov & Hutter, 2017) with a 0.0001 minimum learning rate.
CINIC10 (Darlow al., 2018). The CINIC1O dataset contains 270, 000 images in total and is evenly split to three subsets: training, valid, and test. Guided by (Darlow et al., 2018), we combine the training and valid set to form large training dataset containing 180, 000 images and measure the test accuracy with the test set (containing 90, 000 examples). We use ResNet18 (He et al., 2016) as the network architecture. For all coresets with different pruning rates, we train models for 70, 000 iterations with a 256 batch size (about 100 epochs over the entire dataset). We use the SGD optimizer (0.9 momentum and 0.0002 weight decay) with a 0.1 initial learning rate. The learning rate scheduler is the cosine annealing learning rate scheduler (Loshchilov & Hutter, 2017) with a 0.0001 minimum learning rate. We use a 4-pixel padding crop and a randomly horizontal flip as data augmentation.
ImageNet (Deng et al., 2009). We use ResNet34 (He et al., 2016) as the network architecture. For all coresets with different pruning rates, train models for 300, 000 iterations with 256 batch size (about 60 epochs over the entire dataset). We use the SGD optimizer (0.9 momentum and 0.0001 weight decay) with 0.1 initial learning rate. The learning rate scheduler is the cosine annealing learning rate scheduler (Loshchilov & Hutter, 2017).
Difficulty score calculation. For CIFAR1O and CIFAR100, we train a model with the entire dataset for 200 epochs to calculate the forgetting score and AUM and use the last checkpoint to calculate entropy for each training example. We the first 10 epoch's 's training information to calculate the EL2N score. For SVHN and CINIC10, we train a model with the entire dataset for 100 epochs to calculate the forgetting score and AUM and use the last checkpoint to calculate entropy for each training example. For ImageNet, we train the entire dataset for 90 epochs to calculate the forgetting and AUM score. We use the first 10 epoch's 's training information to calculate the EL.2N score.
Coverage-centric methods setting. We set the number of strata k 50 for all datasets and prun- ing rates. We use the grid search with 0.1 step size to find an optimal hard cutoff rate 8 for dif- ferent datasets and pruning rates. For each dataset, we list the optimal B value for every as follows the format of tuple (a, (3). For CIFARIO, the optimal setting is (30%, 0), (50%, 0), (70%, 10%). (80%, 10%). (90%, 30%). For CIFAR 100, the optimal setting is (30%, 10%). (50%, 20%). (70%, 20%). (80%, 40%). (90%, 50%). For SVHN, the optimal setting is (30%, 0), (50%, 0), (70%, 10%), (90%, 10%), (95%, 20%). For CINIC10, the optimal setting is (30%, 0), (50%, 0). (70%, 10%). (80%, 10%). (90%, 20%). For ImageNet, the optimal setting is (30%, 0), (50%, 10%). (70%, 20%), (80%, 20%), (90%, 30%).
Each model is trained on a NVIDIA 2080TI GPU. We also include the implementation in the sup- plementary material.
13

---

Published as a conference paper at ICLR 2023
C THEORETICAL ANALYSIS
We include full proofs of Theorem and Proposition in this section.
C.I PROOF OF THEOREM
Our proof flow similar the proof of Theorem in Sener & Savarese (2017).
Lemma 1. Berlind & Urner (2015) Fix some p. p' E [0, and y' E 13. Then,
Py-ppy = 1/) S Pyrp' (y = =/ 1p-11 ppppp' p'l
Theorem 1. Given n i..d. samples drawn from Pa S = {a;, y1 heeln) where ys E [C] is the class label for example a coreset S' which is a p-partial r-cover for P.. on the input space X, and an e <> 1 1-p, p. the loss function 1(, y, w) is Xr-Lipschitz continuous for all y, w and bounded by L, the class-specific regression function Te ()x))) = ply = cla) is Xo -n-ssipcchis for all and (ax y; hs? = 0. ((r,)) v) E S', then with probability least E:
1 Σ KESES
log ptc-1
(x vi hs)) <r(Ar +,
2n
( (xx, Mii Ws where 17()) is the output of the model, and we represent {y: = k} ~ mh (2:) with Yi ~ mh (x;). We have a condition which states that there exists an Xj in ball around x; such that Xj has 0 loss. Since S' is p-partial r-cover for the distribution, for æ, ~ μr, with the probability p. there is n. E such that a vy S v and 2z has 0 loss.
Proof. We first bound E
The following inequality holds with the probability p:
E yn,, [xx, ye3 hs:)]
(x. k)),(x; hs))
kE(C
By applying Lemma and training loss condition on 2j, we have:
s Py: Py.-m(xx)(00 (ui Ix),(x,, k;; hs:) +
Σ
Im (x;) (x(x)))((x;,,))) hs!)
kE|C]
kE[C1
= =Σ Py: Py. (x,) (yr = (xx, (; hs-) 1(xj, k hs:)] +
Σ lxx)x,) The (xxx)) hsr)) kE[C]
kE[C]
By applying the Lipschitz property of regression function and loss function, have:
$ Σ (x;)) ke) [x; 221+
Σ
1(x, k; hi )aylax, xzy
kE[C]
RE(C
< A |x;
æı5 + Σ
1(x;, h;; his 1aylax æzyl
kE(C]
By applying the loss bound and the p-partial r-cover constraint, we have:
S Ayp æ, + I.A,, - æz1 (Ar + X, [.) - x.yl
rr(2r IC).
At last, we have the following inequality with probability p: E [[x,, Me hsr)] S r((, + LC)
(4)
Also, by the Hoeffding's 's Bound (Hoeffding, 1994), with probability at least - y, we have:
log(1/7))
Σ I( v: hss) F ye s I.
(5)
S.VSS
14

---

Published as a conference paper at ICLR 2023
By combining Equation 4 and Equation 5, we have that with probability at least
1 71 2,
Σ
(a.y:hh/
< XnLC)
V L
log p
2n
with > -
C.2 PROOF OF PROPOSITION
Proposition 1. Given metric space (X,d). distribution Pie. cover percentage P. set S, and fr(p) [o, 1] + [0, tool representing the mapping between and r, if fr Riemann- integrable, the AUC of the p-r curve AS) = =So fr(pddp = Ea ((), where d(S ess d(x',an x)).
Proof. Since fr is Riemamn-interrblle, can calculate So fp()dp, which is AUC pr. with Rie- mann sum. Specifically, by evenly dividing [0, to P0 < pt P2 ... Pr. 1, have:
L. (.(d)dp
lim Σ fplp)(p: - -P-1). n-00
Since P: = P)(((s,x)) S f+(i)),, we have
J fp(p)dp= lim Σ < d(5,)) f+(p))
We know f, is an increasing function and f,(0) Let A, = f.(e)) - Sr fr(pi-1). we have:
lim
(U < d(S,x) S (p(p-1) A.)
11+000
As n - oc, we have A, - 0, so we have:
lim
TPa(r S d(S,x) <r A)dr,
A-0
which is the expectation of the minimum distance data in S.
So we conclude that Arr is the expectation of the minimum distance to data in S.
D ADDITIONAL EVALUATION RESULTS
D.I EVALUATION RESULTS ON SVHN AND CINICIO
In this section, we present our comparison experiment on SVHN and CINICIO in Table and Table 6, respectively. Since SVHN classification is simpler than other classification tasks, we also study the performance of coreset with 95% pruning rate. We find similar comparison results that we discussed in Section 4. 1. For both datasets, we observe that CCS achieves comparable accuracy with low pruning rates, higher accuracy than random and other baseline coreset selection methods.
D.2 CORESET COVERAGE ANALYSIS
Figure and Table 7 compare AUCpr between CCS with forgetting score and the vanilla forgetting methods (pruning easy first) the CIFARI0 dataset. We observe that CCS has lower AUC and better accuracy with the same pruning rate, which suggests that the proposed coverage-centric method does improve the data coverage of the coresets.
15

---

Published as a conference paper at ICLR 2023
We compare the testing accuracy of CCS against baseline methods and Random CI- FARIO dataset at different pruning rates. When we prune out 30% or 50% fraction of data, CCS achieves comparable aceuracy. 70%. 80%, or 90% pruning rate, CCS outperforms baselines by a large margin. The model trained with the entire dataset has 95.23% accuracy.
Table 3:
Pruning Rate
30%
50%
70%
80%
90%
Random
94.33
93.440.17
90.9440.38
87.98
19.04
Entropy
94.4440.2
92.11
83.67
79.08.0.36
66.5211.08
Forgetting
95.36_0.13
95.29 10.18
90.56
62.74
34.03
EL.2N
95.44
94.61 10.20
87.48
70.32
22.33 1..54
AUM
95.07=0.21
95.26+0.15
91.36+114
57.84+4.1
28.06
Moderate
93.86=0.11
92.58+0.30
90.56+0.27
87.32+0.38
81.0441.66
Forgetting (CCS)
95.40=2.12
95.04
92.97
90.93
85.70
EL2N (CCS)
94.84
94.03+0.24
92.2540.24
89 89.8140.30
86.68 41.22
AUM (CCS)
95.27 20.06
94.93+0.1
93.00
90.91 90.91
86.08
Table 4: Accuracy results on CIFAR100 comparing CCS against other baselines. At low pruning rate, CCS achieves comparable accuracy to baselines. higher pruning rates, CCS outperforms baselines and random. The model trained with the entire dataset has 78.21% accuracy.
Pruning Rate
30%
50%
70%
80%
90%
Random
10.59
71.07
65.3
57.36
44.76
Entropy
72.26+0.08
03.2640.29
50.4940.8s
41.8340.33
28.9640075
Forgetting
76.91+0.32
68, 68.6+1.02
38.06+1.14 14
24.23+4..9
15.93++0.24
EL2N
76.25
65.90+1.06
34.4241.50
15.5141.20
8.36
AUM
76.93
67.42:0.49
30.6440.58
16.38=2.4
8.77 +0.35
Moderate
74.60
71.1040.24
65.3440.41
58.5140.84
45.51
Forgetting (CCS)
77.14
74.45
68.92
63.99
55.594007
EL2N (CCS)
75.02+0.12
72.09
67. 67.13+0.22
61.8340.93
52.55+1.68
AUM (CCS)
76.84
73.77 10.21
68.85 10.08
63.2
55.03
D.3
TRANSFERABILITY OF CORESETS
Similar Coleman (2019), we also conduct coreset transferability study. We train 8 model with the entire CIFAR10 dataset and use the forgetting score to select coresets with different pruning rates. Then we train the ResNet50 model with these coresets. The evalua- tion results are shown in Table 8. We find that coresets show good transferability across these two architectures.
100
90
Accuracy
70
60
40
W/o Pruning
Random
Forgetting (CCS)
Forgetting
20
0.50
0.55
0.60
0.65
AUC,r
Figure 7: The relationship between AUCpr and accuracy. A larger circle size indicates higher pruning ratio on the dataset. Compared to the vanilla forgetting method, CCS with the forgetting score achieves lower AUCpr and better accuracy.
16

---

Published as a conference paper at ICLR 2023
Table 5: Accuracy results on SVHN comparing CCS against other baseline methods. Pruning rate the fraction of examples that are removed from the original dataset. We report the testing accuracy of the model trained the pruned dataset. The model trained with the entire dataset has 96. 96.12% accuracy. When we prune out 30% or 50% fraction data, CCS achieves comparable accuracy. With 70%, 90%, 95% pruning rate, CCS outperforms baseline methods by large margin.
Pruning Rate
30%
50%
70%
90%
95%
Random
95.3840.4
94.24
93.39
89.5840.99
85.34
Entropy
95.47 10.45
94.95
93. 93.14
81.6
54.6
Forgetting
95.57 10.27
95.3710.29
94.761.009
66.57 12.83
27.95
E12NN
96.05 10.11
95.61 10.25
94.87
56.53
21.05 11.85
AUM
95.9 =0.38
95.76+0.10
94.93
52.5845.98
21.61+1.68
Moderate
93.91 93.91
93.0640.30
92.7440.88
89. 89.10+0.28
85.66400.40
Forgetting (CCS)
95.96+0.1
95.5+0.11
94.5640.24
91.49400.9
87.78
EL2N (CCS)
95.42=0.10
95.5940.17
95.05+0.14
92.0.60
88.55440.7
AUM (CCS)
96.02
95.69
94.88
92.27
88.8641.11
Table Accuracy results on CINICIO comparing CCS against other baseline methods. Pruning rate is the fraction of examples that removed from the original dataset. We report the testing accuracy of the model trained on the pruned dataset. The model trained with the entire dataset has 89.97% accuracy. When prune out 30% 50% fraction of data, CCS achieves comparable accuracy. With a 70%, 80%, or 90% pruning rate, CCS outperforms baseline methods by a large margin.
Pruning Rate
30%
50%
70%
80%
90%
Random
88.88
87.64
85.1340.17
82.63
77.31
Entropy
89.08
86.6940.21
82.140.15
77.37
67.21
Forgetting
90.07=0.11
89.68+0.18
81.9641.07
61.26+1185
45.0641.48
EL2N
89.93
87.65 87.6540.25
65. 65.10
36.09+1.37
18.50
AUM
90.11 10.14
89.5
66.2310.69
33.8910:2
18.61 10.15
Moderate
$7.25.0..1
86.04 10.08
84.15.0.10
82.09
78. 78.10
Forgetting (CCS)
90.03
89.47+0.08
88.0440.04
85.88+0.20
81.0440.91
EL2N (CCS)
80.52.o.11
88.41
87.7610.12
86. 86.2010.17
83. 83.18400 10.56
AUM (CCS)
90.04
89.24
87.99
85.82+0.27
81.92+1..4
Table AUCpr comparison between the vanilla forgetting method and CCS. Coresets obtained by CCS show lower AUCpr, which suggests better data coverage.
Pruning Rate
30%
50%
70%
80%
90%
Forgetting Forgetting (CCS)
0.492
0.511
0.551
0.580
0.631
0.491
0.504
0.529
0.547
0.592
Table 8: We train ResNet50 with coresets of CIFAR10 selected by the forgetting score calculated on training information with ResNet18. The evaluation results shows that the coresets selected by CCS have good transferability across models.
Pruning Rate
30%
50%
70%
80%
90%
Random
94.53
92.87
89.03
88.48
78.94
Forgetting
95.22
94.67
91.95
71.10
35.21
Forgetting (CCS)
95.08
94.99
92.84
89.59
85.65
17

---

Published as a conference paper at ICLR 2023
D.4 ADDITIONAL EVALUATION ON IMAGENET
In this part, we present our comparison experiment on ImageNet, a larger scale dataset compared to the other four datasets evaluated, in Table Due the large computational cost for the ImageNet training, we only apply CCS on the AUM importance score, and similar to the prior work Sorscher al. (2022), we train each model for one time.
From Table 9, we notice that CCS outperforms all baseline methods at high pruning rates and achieves comparable performance low pruning rates. We find that EL2N and AUM still ex- perience the catastrophic accuracy drop at high pruning rates. Specifically, compared to random sampling. CCS achieves a 5.02% improvements
90% pruning rate. The evaluation results on ImageNet indicate that CCS is also scaled to the large dataset.
Forgetting performs very similarly to random at high pruning rates. We think the reason behind this is that the training dynamics of ImageNet are only collected for 90 epochs, which causes an example to be forgotten at most 45 times. Considering the huge number of the ImageNet dataset, many example can share the same forgetting number. Since coreset selection will randomly sample examples when the scores of these examples are the same, forgetting method for ImageNet adds more randomness to the coreset selection.
Table 9: Accuracy results on ImageNet comparing CCS against other baseline methods. Pruning rate is the fraction of examples that are removed from the original dataset. We report the testing accuracy of the model trained on the pruned dataset. The model trained with the entire dataset has 73.54% Top-1 I accuracy. When we prune out 30% or 50% fraction of data, CCS achieves comparable accuracy. With a 70,, 80%, or 90% pruning rate, CCS outperforms baseline methods by large margin.
Pruning Rate
30%
50%
70%
80%
90%
Random
72.18
70.34
66.67
62.54
52.34
Entropy
72.34
70.76
64.04
55.8
39.04
Forgetting
72.6
70.89
66.51
62.92
52.28
EL2N
72.2
67.17
48.79
31.22
12.99
AUM
72.53
66.57
40.42
21.12
9.93
Moderate
72.06
70.32
65.86
61.3
52.16
AUM (CCS)
72.29
70.52
67.78
64.47
57.36
D.5 DISCUSSION ON IMPORTANCE SAMPLING BASED METHOD
Another potential way to resolve the coverage issue is the importance sampling based method: sam- ple each example in the data set with a probability based to its importance score. Examples with less importance assigned smaller sampling probability and examples with larger importance assigned larger sampling probability. We present preliminary experiments on CIFARIO, the AUM as the underlying importance metric, and using a softmax function to map importance scores to probabilities.
Unfortunately, experimental results in Table show that the above scheme failed beat random at high pruning rates. It did beat the SOTA method at high pruning rates. Not beating random is big deal, since random selection is the simplest possible strategy for constructing a coreset.
The above result also suggests that it is not easy to design a coreset selection scheme that beats random selection high pruning rates. Our proposed scheme, CCS does that on five the datasets that we evaluated it on, and it is the first coresct selection scheme achieve that, as far aware.
We note that the relationship between data importance score and good-property sampling probability not obvious. Unlike many statistical machine learning methods like KNN or k-means, which usually
usually have good math property, data importance scores in deep learning classification heuristically calculated (as we discussed at the beginning of Section 4), which makes it non-trivial to figure out effective way to calculate probabilities based on heuristic importance scores.
18

---

Published as a conference paper at ICLR 2023
Table 10: Accuracy results CIFARIO comparing importance sampling against other baseline methods. Pruning rate is the fraction of examples that are removed from the original dataset. We report the testing accuracy of the model trained on the pruned dataset. Importance sampling shows a better performance than AUM at high pruning rates, but it has worse performance than CCS and random sampling. We highlight the highest accuracy for each pruning rate in bold.
Pruning Rate
30%
50%
70%
80%
90%
Random
94.33
93.40
90.94
87.98
79.04
AUM
95.07
95.26
91.36
57.84
28.06
AUM (CCS)
95. 27
94.93
93.00
90.91
86.08
AUM (Importance sampling)
93.12
92.61
90.77
86.27
77.66
For the results in Table 10, used the popular softmax function. More specifically, since smaller AUM score indicates larger importance, we calculated the sampling probability Pt for the ith example follows:
Amce -A
En
N
where is the AUM score for each example, Smaz is the maximum possible AUM score, and N is the number of examples.
We do not rule out that a better-designed importance sampling technique exists, say, by rethinking the relationship between importance score and probability selection. CCS uses stratified sam- pling, which we found to work really well. CCS thus provides a good baseline for any further work in this area.
19


Reviews:
[{"review_id": "phM2B0BRxt", "reviewer": "Reviewer_f2Gh", "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": "", "summary_of_the_paper": "This paper addresses the following problem. Given a set of training examples, select a smaller subset of it which minimizes the expected model error. The goal is that the smaller subset can be used to train a different model with minimal drop in accuracy in comparison to training the model using the entire training dataset.\n\nThe SOTA approaches solve the problem in the following way: They compute an importance score for each of the training example for the given model. The examples with smaller importance score are pruned as they are not important enough for learning of the model. The importance score is computed in different ways. 1/ Forgetting score (Toneva et al., 2018) is defined as the number of times an example is incorrectly classified after having been correctly classified earlier during model training. 2/ Area under the margin (AUM) (Pleiss et al., 2020): AUM represents the probability gap between the target class and the largest other class across all training epochs. A larger AUM means higher difficulty and importance. 3/  EL2N (Paul et al., 2021): EL2N scores estimate data difficulty by the L2 norm of error vectors. Examples with large difficulty score are more important. 4/ Entropy (Coleman et al.,2019): The entropy of outputs reflects the uncertainty of training examples, and a high entropy indicates an example containing more information and is more important.\n\nThe above described methods beats the baseline random selection method in moderate pruning regime but performs poorer than random method in high pruning regime, say 90% pruning.\n\nThe paper identifies that poor performance of the SOTA methods in comparison to random selection is because SOTA methods prune all the easy examples which correspond to the high density region of training examples. Hence the paper proposes stratified sampling instead of pruning all the low-score examples. It implemented stratified sampling on top of each of the SOTA methods described above and shows that it significantly improves performance in high pruning regime in comparison to the low-score pruning of the SOTA method.\n\nThe paper also extends the Lipschitz constant based bounds on pruning based loss function when pruning is done using core-set radius r, to the p-partial r-cover based bounds, where radius r covers only p fraction of the probability density space.\n", "summary_of_the_review": "The paper provides a simple approach for a well defined problem in high pruning regime. However, the approach lacks novelty and the provided theory is very tangential to the proposed approach.", "strength_and_weaknesses": "Strength: A well defined practical problem is solved using a simple method. An investigation of the SOTA methods revealed the problem with the existing approaches in high pruning regime, and a simple stratified sampling based fix solves the problem. Though the theory is not directly relevant to the proposed approach and is not innovative, but the extension of r-cover core-set bounds to the p-partial r-cover bounds does show the tradeoff between p-partial cover and r-radius cover. The numerical experiments show a significant improvement over the baseline methods in the high pruning regime.\n\nWeakness: The paper lacks novelty, and the given theory is very tangential to the proposed solution. A theoretical bound on loss function for stratified sampling in combination with any of the SOTA importance score estimation method would be more useful.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "TaHNmGFHzk", "reviewer": "Reviewer_6QHN", "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": "This paper gives an improved one-shot coreset selection method for classification problems. A one-shot coreset is a subset of the training set, and the goal is to find a coreset/subset of a given size such that the training error on the coreset is minimized.\n\nThe paper first studies the ability of the coreset to “cover” the data distribution, and justifies why this is important. To this end, the notion of partial cover was proposed. Roughly, a subset S is a p-partial r-cover for some distribution, if the total probability measure of the union of all radius-r neighborhoods around each point in S is p. This generalizes a previous notion which is essentially p = 1. In Theorem 1, this paper proves that if a coreset is a p-partial r-cover, then it has a bounded error w.h.p. on the training set (where the randomness comes from the training set). Hence, this is a valid error measure. To further stabilize the measure, the AUC (area under curve) measure is considered, which may be viewed as an average/overall measure of the radius r, over all cover percentage.\n\nThe paper observes that the AUC of several existing coreset algorithms is worse than a naive uniform sampling, when the pruning rate is high (i.e., 90%). The focus is thus to propose a new algorithm that improves the performance when the pruning rate is high. The key observation is that the previous results drop points too aggressively under high pruning rate. Hence, given a set of importance score of data points, the new algorithm, called CCS, first excludes a \\beta fraction (which is smaller than the total pruning rate) of the hardest examples (according to the score), and then picks the data points to be kept in a somewhat uniform way.\n\nExperiment results show that the proposed method has a significant improvement over previous coreset methods when the pruning rate is high, regardless how the importance score is defined (tested on at least 4 different scoring schemes), while still matches, or slightly outperforms, the existing methods when the pruning rate is low.", "summary_of_the_review": "This is a nice paper. However, I would suggest a weak reject for now, due to the concerns that I raised in the \"Weakness\" part. They can significantly affect the justification of novelty of the paper.", "strength_and_weaknesses": "# Strength:\n\nThe technical idea and the reasoning is well grounded by theoretical and empirical analysis, and the comparison with previous methods seem to be comprehensive, which is convincing. The new algorithm makes sense, and the empirical result shows a significant improvement over previous results.\n\n# Weakness:\n\nThe reasoning generally makes sense, but I do find a few important aspects not discussed (I might be wrong since I mostly work on coresets for clustering instead of classification). In particular:\n\n1. From the literature of coresets for clustering, once importance score is given, the next step is usually importance sampling: sample each point x in the data set with probability *proportional to its importance score*. Note that this distribution can sample both easiest and hardest points, and more importantly, if the easy points are a lot, each of them is sampled with small probability but the combined probability of sampling an easy point can be very significant. Hence, this seems to resolve the issue that you mention, where easy points tend to be very “dense”, and simply focusing on hard points may miss them. Unfortunately, I don't see this very natural approach discussed/reflected in the paper.\n\n2. Actually, I don’t find any reference about coresets for clustering (and related problems), especially those using importance sampling. Consider to cite and discuss the typical ones, such as\n\n* Turning Big Data Into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering, Feldman et al, SICOMP 20.\n\n* A unified framework for approximating and clustering data, Feldman and Langberg, STOC 11.\n\n3. The entire paper seems to assume the importance score is given which can be arbitrary. However, the quality of the importance score can also greatly affect the performance, but this does not seem to be modeled/considered in the algorithm? Moreover, I find it unclear whether improving the sampling algorithm or improving the importance score is the most significant issue of the existing algorithms. For instance, it is a fact that the previous works perform worse than random sampling at 90% pruning rate, but why this has to be caused by a bad sampling algorithm? What about using an improved importance score? ", "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": "6M9VU77_G_", "reviewer": "Reviewer_17rD", "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": "The authors study a known shortcoming of the SoTA coreset selection methods, which they call \"catastrophic accuracy drop\". The SoTA methods usually perform well under low-pruning regimes, but at high pruning rates they work even worse than random sampling.\n\nThe authors hypothesize that this is due to reduction in \"data coverage\" at high pruning rates. As such, they define \"p-partial r-cover\" for a selected subset and based on it propose the AUC_pr metric to quantify coverage. Then using this new metric they show that the SoTA methods indeed suffer from low data coverage at high pruning rates and AUC_pr of a selected subset correlates well with the performance of the models trained on it.\n\nFinally, they propose a method, called Coverage-centric Coreset Selection (CCS), which uses stratified sampling over a given scoring mechanism. This method can complement the existing score-based pruning methods. They then experimentally show that their method can highly improve the existing SoTA methods at high pruning rates, both based on their proposed AUC_pr metric and the actual final model performance.", "summary_of_the_review": "The authors' argument and observation seems quite valid and well-supported, but I'm confused by their method. I believe the AUC_pr metric could be quite valuable to the community, either in its current form, or an improved version of it. It will allow further research to take into account an important aspect that has not been easily addressable before.\nAs for the method, the improvements are quite large, but I have a hard time figuring out how the stratified sampling part is different from normal random sampling. I would've also like to see some evaluation of the method on a dataset such as ImageNet.\n\nThe main concerns that I have are that: 1) the proposed method seems a bit complicated/hacky and doesn't directly address the issues that are raised; and 2) I see some conflicts between Figure 4 and Alg 1.\n3) I believe the metric might also need some adjusting in the future, but currently it should be adequate.\n\nWhatever my reservations about the CCS method itself, the results are better than I expected.", "strength_and_weaknesses": "Strengths:\n- The argument is well-grounded: it starts with an observation, then a hypothesis is presented, a metric is proposed to validate the hypothesis, and finally a method is proposed that empirically fixes the issue\n- The improvements are quite large: the proposed method not only improves the SoTA at high-pruning rates, it beats the random baseline, which has been very strong at high-pruning rates until now, by a large margin\n\nWeaknesses:\n- The final method seems hacky and looking more closely, I'm not convinced that it does address the \"coverage\" issue directly. I can see how this method is way better at getting a distribution with higher coverage than the existing \"hard cut-off\" method. Anyway, maybe I'm expecting too much from the paper\n- Relatedly, the method requires some hyper-parameter tuning, but the authors show that it's mostly invariant to one parameter and provide some intuition as to how to tune the other\n- The method is only tested on datasets that are both small and fairly similar. Having results on ImageNet would make the results way more convincing.\n\nQuestions:\n- The way I see it and by looking at Figure 2, AUC_pr metric might be dominated by the \"r\" values of the high coverage (high \"p\") regions. Do you think some normalization could be applied here to remove this bias or is that not necessary?\n- I'm totally confused about the way CCS is represented in Figure 2. Looking at Algorithm 1, I'd expect CCS to have some a peak on the right side (i.e. hard cases that are removed on line 2 of Alg. 1) and then I'd expect CCS to have a more-or-less uniform distribution for the rest of the data (i.e. to be a scaled version of \"all data\") as you claim to take samples from all strata, not just a few. I'm not sure what I'm missing here.\n- You show that the value of k is not important, but only show it for k>25. If you set k=1 and beta=0, do you recover random sampling? Because if you claim that k is not important, the only difference with random sampling would be just that you prune the hard samples. Is that correct?", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-H5rGRV0U8W", "reviewer": "Reviewer_Vae7", "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": "", "summary_of_the_paper": "This paper tries to ameliorate the serious performance degradation when a substantial portion of data is pruned. It is argued that the problem is caused by poor coverage of the selected subset. Then a new data selection strategy CCS is then proposed. CCS jointly considers sample coverage and the informativeness of each example. The effectiveness of CCS is validated on Cifar-10 and Cifar-100.\n", "summary_of_the_review": "The paper is overall well written, however, the problems mentioned in the weakness part undermine its significance. ", "strength_and_weaknesses": "Strength:\n\n1. Selecting subsets to retain the full training performance is important for efficient training, hyperparameter tuning as well as. The problem this paper trying to address is important.\n\n2. The authors do a good job presenting their intuitions developing CCS.\n\n3. The proposed method seems to be technically sound. Theoretical analysis on the risk of training only on subset is provided.\n\n4. The paper is clearly written. Experiments and ablation studies are well performed.  Many details, including the implementation are provided for reproducing. \n\nWeakness:\n\n1. Coverage, or “data representativeness” is widely discussed in the very related active learning literature [1][2]. Active learning shares a lot in common with data selection considering scoring examples and maintaining representative samples. In this field, informativeness (data importance) and representativeness (coverage) are explicitly formulated as two main considerations. This undermines the novelty of this work. \n\n2. There lacks experiments on large scale dataset like ImageNet. The selection strategy behaves pretty inconsistent on ImageNet and Cifar-10, results on small data may not be reliable enough. Besides, ImageNet experiments are commonly conducted in recent data selection methods [3,4,5], so I recommend experiments on ImageNet to further strengthen the paper. \n\nReferences:\n\n[1] J T. Ash et.al. Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds. ICLR ‘20 \n\n[2] G.Citovsky et.al. Batch Active Learning at Scale. NeurIPS ‘21 \n\n[3] K. Killamsetty et.al. GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training. ICML’21\n\n[4] Ben Sorscher et.al. Beyond neural scaling laws: beating power law scaling via data pruning. arXiv: 2206.14486\n\n[5] Cody Coleman et.al. Selection via Proxy: Efficient Data Selection for Deep Learning. ICLR’19\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": {}}]

Author rebuttal:

Decision: Accept: poster