$\mathbb{D}^2$ Pruning: Message Passing for Balancing Diversity & Difficulty in Data Pruning
Authors: Adyasha Maharana
Prateek Yadav
Mohit Bansal
Venue: ICLR 2024 poster (2024)
Keywords: coreset selection
data pruning
data
graph
message passing
data distillation
Primary area: general machine learning (i.e., none of the above)

Abstract: In recent years, data quality has emerged as an important factor for training massive models. Analytical theories suggest that higher-quality data can lead to lower test errors in models trained on a fixed data budget. Moreover, a model can be trained on a lower compute budget without compromising performance if a dataset can be stripped of its redundancies. Coreset selection (or data pruning) seeks to select a subset of the training data so as to maximize the performance of models trained on this subset, also referred to as coreset. There are two dominant approaches: (1) geometry-based data selection for maximizing *data diversity* in the coreset, and (2) functions that assign *difficulty scores* to samples based on training dynamics. Optimizing for data diversity leads to a coreset that is biased towards easier samples, whereas, selection by difficulty ranking omits easy samples that are necessary for the training of deep learning models. This demonstrates that data diversity and importance scores are two complementary factors that need to be jointly considered during coreset selection. In this work, we represent a dataset as an undirected graph and propose a novel pruning algorithm, $\mathbb{D}^2$ Pruning, that uses message passing over this dataset graph for coreset selection. $\mathbb{D}^2$ Pruning updates the difficulty scores of each example by incorporating the difficulty of its neighboring examples in the dataset graph. Then, these updated difficulty scores direct a graph-based sampling method to select a coreset that encapsulates both diverse and difficult regions of the dataset space. We evaluate supervised and self-supervised versions of our method on various vision and NLP datasets. Results show that $\mathbb{D}^2$ Pruning improves coreset selection over previous state-of-the-art methods at low-to-medium pruning rates. Additionally, we find that using $\mathbb{D}^2$ Pruning for filtering large multimodal datasets leads to increased diversity in the dataset and improved generalization of pretrained models. Our work shows that $\mathbb{D}^2$ Pruning is a versatile framework for understanding and processing datasets.

Published as a conference paper at ICLR 2024
D2 PRUNING: MESSAGE PASSING FOR BALANCING DIVERSITY & DIFFICULTY IN DATA PRUNING
Adyasha Maharana, Prateek Yadav & Mohit Bansal Department of Computer Science University of North Carolina at Chapel Hill
(adyasha, praty, mbansal ) @cs. unc. edu
ABSTRACT
In recent years, data quality has emerged as an important factor for training massive models. Analytical theories suggest that higher-quality data can lead to lower test errors in models trained on a fixed data budget. Moreover, a model can be trained on lower compute budget without compromising performance if dataset can be stripped of its redundancies. Coreset selection (or data pruning) seeks to select a subset the training data so as to maximize the performance of models trained on this subset, also referred to coreset. There are two dominant approaches: (1) geometry-base -aased data selection for maximizing data diversity in the coreset, and (2) functions that assign difficulty scores to samples based training dynamies. Optimizing for data diversity leads to a coreset that is biased towards easier samples, whereas, selection by difficulty ranking omits easy samples that are necessary for the training of deep learning models. This demonstrates that data diversity and importance scores two complementary factors that need be jointly considered during coreset selection. In this work, we represent a dataset as an undirected graph and propose a novel pruning algorithm, D22 PRUNING, that uses message passing over this dataset graph for coreset selection. D PRUNING updates the difficulty scores of each example by incorporating the difficulty of its neighboring examples in the dataset graph. Then, these updated difficulty scores direct a graph-based sampling method to select a coreset that encapsulates both diverse and difficult regions of the dataset space. We evaluate supervised and self-supervised versions of our method on various vision and NLP datasets. Results show that ID3 PRUNING improves coreset selection over previous state-of-the-art methods at now-to-medium pruning rates. Additionally, we find that using ID2 PRUNING for filtering large multimodal datasets leads increased diversity in the dataset and improved generalization of pretrained models. Our work shows that ID2 PRUNING is versatile framework for understanding and processing datasets.'
INTRODUCTION
Deep learning models are evolving into massive architectures with trillions of learnable parameters requiring enormous training datasets for optimal performance. Empirical experiments demonstrate that the test error in such models falls off as power law with model size well as training dataset size (Kaplan et al., 2020). Recently, Sorscher et al. (2022) developed an analytical theory that shows that the power law association of test error with data size can be demoted to exponential scaling if one has access to high-quality data pruming metric for careful data selection. This has the implication that for a fixed data budget, high-quality training data can yield lower test loss in deep learning models. Coreset selection (Mirzasoleiman et al., 2020; Guo et al., 2022) is similar line of work that aims to select a subset (coreset) of the most informative samples S from large training dataset T without significantly compromising the performance of the model. Existing coreset selection methods (Toneva et al., 2018; Killamsetty et al., 2021 1;;; Yang et al., 2022; Sorscher et al., 2022) demonstrate promising performance on many vision datasets for one-shot coreset selection. However, significant
'Our code is available at ht httpp:://// //g/ tht.....b.....gg com/ adymaharana /atiaaharaaa//220 /dtp///ppnnnnnnm ingu We use the terms coreset selection and data pruning interchangeably throughout the paper.

---

Published as a conference paper at ICLR 2024
progress remains to be made the selection of better coresets, especially using self- self-suue approaches. Moreover, there is a lack of systematic evaluation of these methods on NLP datasets.
Real-world data distributions comprise high-density as well as low-density regions. Yu et al. (2020); Chan et al. (2022) claim that maximizing the variance of intra-class features results in robust representations. To this end, geometry- -based coreset selection methods (Sener & Savarese, 2018; Chen et al., 2010) operate under the assumption that samples located close to each other provide redundant information, and try to remove those data points by selecting the samples most distant from k-means cluster centers (Sorscher et al., 2022) or at a median distance from the class center (Xia et al., 2023), in order to maximize diversity in the coreset. On the other hand, uncertainty-bat based methods (Coleman et al., 2019) and eттоr or loss-based methods (Toneva et al., 2018; Paul et al., 2021) propose a score-based function to estimate the difficulty of each sample in the training dataset from the model's 's training dynamics and retain the most difficult samples. However, the distribution of difficulty scores for the original data is highly skewed and contain way more low-difficllyy (or easy) samples (S (Swayamdipta et al., 2020), as we show in Figure 2(a). As low-difficulty samples predominantly arise in densely populated regions (Sorscher et al., 2022), incorporating some of these well-connected, low-difiielly samples into the coreset guarantees adequate representation of these dense areas within the coreset (Zheng et al., 2022). At the same time, selecting high- high-difficulty samples with higher connectivity increases the information content of the (Kim & Shin, 2022). Evidently, example difficulty and data diversity are two crucial factors for selecting effective coresets, yet, there has been little work towards combining them into a unifying framework for coreset selection.
To unity these two factors, we propose the 2 PRUNING method, where we represent the dataset S as an undirected graph G and design message-passingg algorithm that unifies the difficulty scores and the underlying spatial distribution of the dataset to select a coreset with balanced difficulty and diversity. D2 PRUNING consists of three simple steps: (1) Graph Initialization: First, we create a graph, G. where each node is an example from the dataset S and is connected to its k-closest neighbors based on notion of distance in the embedding space (see Fig. ((A)). Each node has a feature value that represents the difficulty score of the example. This graph can be used to understand the connectivity of each sample with respect to the rest of the dataset (Ebert ct al., 2012). (2) Forward Message Passing: Next, we perform message passing (Gasteiger al., 2020; Yadav et al., 2019) over the dataset graph to update the difficulty scores of all examples by taking into account the distance and difficulty of its neighboring examples in the graph (see Fig. 1(B).. Specifically, each node collects a message from all of its neighbors (where the message is their difficulty scores scaled by their distance) and uses these messages to update its own difficulty score. (3) Coreset Selection & Reverse Message Passing: Finally, we use these updated scores to iteratively select a balanced subset of samples from high-density low-difficulty regions and low-density high-difficulty regions. At each step of selection, the neighbors of the selected sample are down- weighttdd via reverse message-passingg to promote diversity in the coreset (see Fig. (CC). Our design ensures that highly connected nodes of low difficulty are on equal footing with sparsely connected nodes of high difficulty during selection.
We refer this diversity- -ifrfitttyi (D²) approach of coreset selection using pesssage-pasinggg as D2 PRUNING and evaluate this pruning method on multiple image classification and natural language processing (NLP) datasets. We find that ID2 PRUNING outperforms state-of-art methods for coreset selection at low-to-medium pruning rates. Our analysis shows that D2 PRUNING selects a coreset with a higher distribution of difficult samples for low pruning rates and with equitable distribution over easy and difficult samples for medium-to to-humm-tt-hhhhh pruning rates. Further, we adapt D PRUNING for self- supervised and unsupervised data selection approaches and show improvements over existing methods for self supervieddd coreset selection and data filtering respectively. Importantly, the message-passing framework for coreset selection opens up possibilities for exploring different message schemes, possibly incorporating factors other than data diversity and difficulty, in an easy plug-and-play framework. In summary, our contributions are:
We propose D2 PRUNING, a one-shot coreset selection algorithm that represents datasets as undirected graphs and uses message-passing to combine the influence of two important factors, example difficulty and data diversity, for data selection.
We evaluate our method on several image classification, NLP benchmarks and show state-of- the-art results for low-to-medium pruning rates for supervised & self-supervised approaches.
We show that D2 PRUNING selects diverse data pools when filtering massive multimodal datasets, which improves the generalization of pretrained multimodal models.
2

---

Published as a conference paper at ICLR 2024
A. Graph Initialization
B. Forward Message Passing
Higher Sample Importance
Each mode reedives mueeauge from neighbors
E-nrourett
Nodey
Nodey
neighlorr
aclectidd
upweightinn
Noday
daz
Σng Edgey Noday
dai
C. Reverse Message Passing
are initialiedd with difficulty scures
dus
Selented mode sends
Dóge weights are inversely poopettional distlncce
Df PRUSING selects few represeutative camples from dener regions
DP PInLNING selects many important samples Erom sparse regions
neighbors
dowgweighsing
Nodey
Nodey Node,
Edga,, x Noda
Figure 1: Overview of ID2 PRUNING. (left) Our proposed algorithm contains three steps: (a) Initialization of graph G using difficulty scores and edge weights based on feature distance, (b) message passing between connected nodes to propagate difficulty scores of neighboring samples, and (c) data selection and reverse message passing avoid sampling from the same neighborhood. (right)
D2 PRUNING selects a balanced subset of samples (red) from sparse and dense regions.
PRELIMINARIES
In this section, we describe one-shot coreset selection and discuss the motivation behind our work.
2.1 ONE-SHOT CORESET SELECTION
Consider training dataset S containing N examples {(r;. {:) drawn i.i.d. from an underlying distribution P. One-shot coreset selection refers the selection of subset S' of the data at a given pruning rate a such that the loss of the model 0 trained on S' using loss function L is minimized on an evaluation set drawn from P. This results in the optimization problem as follows:
min S'c:: (8) 5(1-a)
E [L(, yi 0; (S'))
2.2 DESIDERATA CORESET
Coresets are representative subsets of larger datasets and aim to preserve the performance achieved by training on the full dataset. Prior works on understanding training dynamics point towards two important factors for ensuring the same i.e. example difficulty and data diversity.
Example difficulty. Multiple works have sought to define example difficulty in order to understand how deep neural networks process data. Statistical metrics like consistency score (Jiang al., 2021) measure the probability predicting the correct label of an instance when it is left out of the training dataset. Sorscher al. (2022) provide theoretical justification for retaining the hardest examples when pruning large datasets for a perceptron learning setting. Swayamdipta et al. (2020) show that examples that have high degree of variance the model's predictions during training have the largest impact on the model's 's overall performance. Accordingly, coreset selection methods based on difficulty score functions prioritize the selection of difficult examples for coresets (Guo et al., 2022). However, it has been shown that deep learning models learn easy data and simple functions earlier in training (Jiang al., 2021: Toneva al., 2018; Baldock et al., 2021) and easy examples ease the optimization of deep learning networks in the high-dimensional data manifold. Moreover, Zheng et al. (2022) demonstrate that it necessary to include easy examples to ensure coverage in high-density areas of the data distribution, which leads to the next factor of consideration i.c. data diversity.
Data diversity. Representation structure has been explored several works as the key to the generalization of deep learning models; variance in representations for each class should be as large as possible while also being uncorrelated from other classes (Xia et al., 2023). The diversity of a dataset can be captured in many ways such coding rate (Yu et al., 2020; Chan et al., 2022), max dispersion or convex hull volume (Yu et al., 2022) and coverage (Sener & Savarese, 2018; Zheng et al., 2022). A set S' is r-cover of another set S, when set of r-radius balls centered each element in

---

Published as a conference paper at ICLR 2024
Dataset
(B) Random
(C) Facility Location
Graph Cut
Moderate
D
PCA (dim-
Density
Importance score distribution selected coreset
Figure 2: Sampling Methods. Density heat map of data distribution (left) and histogram of importance scores (right) in (A) single class in the CIFAR 10 dataset, and coresets selected under 90% pruning rate via (B) random sampling, diversity-only submodular approaches (C) facility location, (D) graph- cut (Iyer et al., 2021). (E) Moderate selection (Xia et al., 2023) and (F) our method, D PRUNING, designed to balance data diversity (pretrained ResNet18 features) and difficulty (Toneva et al., 2018).
S' covers the entire S. The radius 7 can be used as a metric to measure coverage of S' on S (Sener & Savarese, 2018). Zheng al. (2022) introduce the metric AUCpr (Area under coverage), which is computed against test set Dtest i.e. AUC (S) = Ere (min.'edd(1t x2] and theoretically show that it is important to minimize the AUCpr for better generalization. Difficult samples tend to be rarer samples found in the low-density areas of the data distribution whereas easy samples tend to lie in high-density areas. An effective coreset should contain sufficient samples from both areas to ensure maximum coverage. However, optimizing for diversity only leads to coresets with a skewed distribution over example difficulty. As we show in Fig. 2(c), k-center selection minimizes the distance of samples in S from S' and has high coverage of the underlying data distribution. But, the selected coreset contains disproportionate number of easy samples, rendering ineffective.
Example difficulty and diversity are two complementary factors that make an effective coreset. Hence, coreset selection methods need unify the influence of these factors constructive manner. this end, we represent the dataset S as graph and introduce novel message-pan paaaanggepaiigggggee algorithm (Vashishth al., 2019a;b), ID2 PRUNING, that accounts for both factors when selecting samples for coreset.
ID2 PRUNING: MESSAGE PASSING FOR CORESET SELECTION
Consider a dataset S, where each sample represented in an embedding space, i.e., s Rd We seek to select a coreset S" consisting of subset of the samples in S as outlined in Sec. 2.1. Moreover, our goal is to combine the influence of embedding distance and difficulty scores when selecting samples for coreset (see Sec. 2.2). This setting naturally lends itself to a representation using undirected graph G, where each sample represented as a node with node-feature æ;, and edge weights 6ú to indicate its connectivity with other samples in the embedding space (see Fig. 1(a)). We use message-passing to 'inform' sample about (a) its proximity to adjacent samples in an embedding space, and (b) the difficulty scores of its neighbors. First, we briefly discuss message passing for graphs, and then we discuss our proposed algorithm, 2 PRUNING.
3.1 MESSAGE PASSING
Message passing (Hamilton al., 2017) is widely-used operation performed graphs to propagate information from a node's neighbors to itself and update the state of the node based on the newly acquired information. For instance, Gilmer et al. (2017); Gasteiger et al. (2020) use pessage-passing to encode molecular structures for chemical prediction. The paessag--passing phase is defined in terms of message function M and node update function U. In the message passing phase, a given node i receives messages from each of its neighbors and aggregates them to update its feature value:
m; Σ maj: where mij M M(j, Eis) JEN())
(2)
3; = U m))
where (i) denotes the neighbors of node in graph G. is an aggregation function that accounts for the messages received from all neighbors, as well the node's own feature.
4

---

Published as a conference paper at ICLR 2024
3.2 D2 PRUNING
D2 PRUNING consists of 3 stages i.e., (a) Graph initialization, (b) forward message passing, and (c) data selection via reverse message passing.
Graph initialization. We create a single, sparse graph for the dataset 5 where each sample in S represented by a node in the graph. In order account for example difficulty during coreset selection, we initialize the node feature as the difficulty score of the sample based on training dynamics of the model 0 trained on S, i.e., I; = fo(),), where f(.) is the scoring function. In practice, the scoring function can be one of the many metrics used to measure difficulty such as forgetting (Toneva al., 2018), consistency score (Jiang al., 2021), and self seff-supervieed metrics like prototypicality (Sorscher et al., 2022) etc. Next, we collect the k nearest neighboring samples for every sample in the dataset. Within the graph, the connecting edges between each node and its k nearest neighbors are initialized with non-zero edge weight ei,j, where node j is one of the k nearest neighbors (see Fig. (aa)). All other edge weights are set to zero, leading to a sparse graphical representation of the entire dataset S. The edge weight ei, represents the proximity of the two nodes i, j using the RBF kernel of the distance j(i.j). We use the Euclidean distance as the distance function i.e., d( = ||u, will where v; is the embedding vector for sample i.
Forward message passing. In this step, each node in the graph receives information about its neighborhood via single step of message propagation. Every connected node j sends a message M to node about its importance score which is scaled by the edge weight as,
May, esy) = Ca, * Øz where Ci = c-p(-1y d(i,))²)
The intuition behind this definition is that samples that are farther away from the node but are of higher difficulty should be weighted similarly to samples that are closer to the node and have lower difficulty. This promotes diversity in the coreset by ensuring representation from all regions of the data distribution. Finally, the receiving node aggregates all of the messages received from its neighboring nodes and updates its own feature value as,
Uf(2,, I4 + Σ ((z,
(5)
JEN(()
This reinforces the importance of dense regions comprising easy samples or sparse regions comprising difficult samples. Existing methods (Ash et al., 2019; Das et al., 2023) do not make a distinction between casy-to-learn and hard-to-learn areas in the data representation space whereas, this step in D PRUNING increases the importance of a sample by an amount that is proportional to the importance scores of the samples surrounding it, thus ranking an easy sample in a hard-to-learn area higher than that in an easy-to-learn area. Therefore, in this way, we start with graph G where connectivity is based on the distance between two samples in the feature space and convert it into graph based on distance as well as difficulty scores via message passing.
Data selection via reverse message passing, the final step, samples in S are ranked according to their corresponding updated node feature values in G. Iteratively, the highest ranking sample Igk = arg m 2; is selected (Ebert et al., 2012), and its neighboring nodes are down-weighted to maximize the diversity of the coreset. However, since the distance between two nodes is representation of their semantic similarity, neighboring nodes that are farther away from the selected node must be down-weighted relatively less than those that are closer. We implement this via reverse message passing, where the neighboring nodes receive a weighted message from the selected node and use it to update their feature value as,
Tj xjj Ck.j TK, Vj (A)): where ex.j = exp (- * d(k,
where a lower value of 7, causes larger updates in connected nodes and vice-versa. With these steps, D2 PRUNING selects coreset that contains samples from all regions of the data distribution and are more uniformly distributed over the range of difficulty scores (see Fig. 2(f)).
4 EXPERIMENTAL SETUP
Tasks, Models & Datasets. We evaluate ID2 PRUNING on three vision datasets i.c., CIFAR1O. CIFAR100 (Krizhevsky et al., 2009) and Imagenet-1K (Deng et al., 2009), and two NLP datasets
5

---

Published as a conference paper at ICLR 2024
ie., subset (2k train examples) of ImDB reviews for sentiment analysis, and the Adversarial NLI (ANLI) dataset (Nie et al., 2020) for natural language inference. To the best of our knowledge, we are the first to perform systematic evaluation of coreset selection methods NLP datasets. We evaluate unsupervsied 23 PRUNING on the DataComp (small) dataset (Gadre et al., 2023). We use ResNet-18 for CIFARIO and CIFAR 100, ResNet-34 for ImageNet-1K K and RoBERTa for NLP datasets.
Baselines. (Supervised) We compare 22 PRUNING with several score-based and geometry-based coreset selection methods derived from the training dynamics of model trained on the full dataset: A) Random selection. B) Entropy (Coleman et al., 2019) of prediction vector. C) Forgetting (Toneva et al., 2018) score. D) EL2N (Paul et al., 2021) i.c. L2 norm of error vectors. E) Area under the margin (Pleiss et al., 2020) score. E) Moderate (Xia et al., 2023) coreset consisting of samples median distance from class center, F) CCS (Zheng et al., 2022) divides range of difficulty scores into equal-sized bins and randomly samples from each bin, G) CCS + k-Center, where k-center samples are selected within each CCS bin, H) BADGE (Ash et al., 2019) that selects samples using k-means++ in the gradient vector space, I) GLISTER (Killamsetty et al., 2021b) uses bi-level optimization to select robust coresets, J) CAL-SDS2 (Das et al., 2023) combines a facility location submodular function (Iyer et al., 2021) with forgetting scores, and J) INGENIOUS (Renduchintala et al., 2023), a diversity-only approach using facility location function for NLP tasks. (Unsupervised) We use self-supervised embeddings to compare D32 PRUNING with A) Prototypicality (Sorscher et al., 2022) computes k-means clusters using embeddings and selects samples farthest from cluster center, B) CCS over prototypicalit scores, and C) Moderate selection (Xia al., 2023).
Implementation. In the supervised approach of DD PRUNING, graph nodes are initialized with supervised difficulty score values and feature embeddings extracted from the model trained on the entire dataset. We use the forgetting score for CIFARIO 10, CIFAR 100 and AUM score for ImageNet- K (Zheng et al., 2022). We substitute the forgetting score with variance (Swayamdipta et al., 2020) for NLP datasets since they are trained for fewer epochs and the [CLS] token representation in RoBERTa models for feature embeddings. Self-supervised DD2 PRUNING initialized with feature embeddings from SWAV (Caron et al., 2020) for ImageNet- KK and uniform difficulty scores over the dataset.
Computational Complexity of m PRUNING. Graph initialization involves getting the k-nearest neighbors which are computed on a A100 GPU using PyTorch, taking <2 minutes for CIFAR 10, CIFARIOO, Adversarial NLI and ImDB datasets, and approx. 12 minutes for ImageNet- at quadratic time complexity O(un?), ), where is the vector dimension. We use faiss indexing (CPU) to get the approximate nearest neighbors for the 12.8 M samples in the Datacomp dataset taking nearly 55 minutes (8 workers) at (( log (d)) time complexity, where d=256K is the number of documents in the fa i as index (Johnson et al., 2019). Forward message passing is parallelizable step of linear time complexity that scales with & as ((nk). The iterative selection step in ID2 PRUNING takes (()) time in our optimized implementation, completing in <5 minutes for DataComp (Sec. B, Appendix).
Algorithm Hyperparameters. We use the best reported hyperparameters for baseline methods. For 2 PRUNING, we set the forward message passing weight y to 1.0 and perform a sweep over k {1.5, 5, 10, 15) and 7, = {0000.1, 0.1, 0.2...100) for CIFAR10, CIFAR 100 datasets. Insights from these runs are used to select three configurations for each run on ImageNet- IK (see Sec. 5.2).
5 RESULTS& & DISCUSSION
5.1 COMPARISON TO SUPERVISED CORESET SELECTION METHIOSS
We evaluate 2D PRUNING and other coreset selection methods outlined in Sec. 4 on three vision datasets and present results in Tab. 1. 2D2 PRUNING demonstrates consistent gains over the previous state-of-art for all datasets at low and medium pruning rates. TD² PRUNING yields significant gains (p < 0.05) i.c., 1.0% and 1.4%, over the previous best for 50% and 80% pruning rates on ImageNet- IK. showing the efficacy of graphs and message passing for coreset selection." Notably, random pruning works surprisingly well for ImageNet- K, especially for low pruning rates, and is hard to beat. CCS (Zheng et al., 2022) remains strong baseline for 90% pruning rate and only benefits a little from additional diversity-based selection within the CCS bins (see CCS + k-Center in Tab. 1). CCS enforces uniform distribution of sample difficulty scores in the coreset, which is beneficial at
Statistical significance computed by bootstrapping 100K samples (Noreen, 1989; Tihshirani & Efron, 1993)
6

---

Published as a conference paper at ICLR 2024
Table 1: Results on Vision Datasets. Performance (acc.) of ID2 PRUNING and baselines on CIFARIO I0, CIFARI 100 using ResNet18, and ImageNet-IK using ResNet34 models. Higher is better.
Datasst (-1)
CIFARIO
CIPARI00
ImageNett-IK
Prusing Rate (-+)
0%
30%
50%
70%
90%
90%
0%
30%
50%
70%
50%
90%
0%
30%
50%
70%
50%
90%
Random
95.5
94.3
93.4
90.9
58.0
79.0
78.7
74.6
71.1
65.3
57.4
44.8
73.1
72.2
70.3
66.7
62.5
52.3
Entropy (Coleman al. 2019)
94.8
92,9
84.1
72.1
14.7
68.9
60.3
49.6
35.0
70.8
64,0
55.8
39.0
Forgetting
al,, 2018)
20.6
$2.3
EL.2 (Panl et al...022)
78.6
30.3
47.2
24.8
11.8
48.8
11.2
12.9
AUM (Pleiss et 2020)
95.6
95.1
87.9
68.0
40.0
73.0
67.
40.1
26.4
13.1
72.5
66.
404
21.1
9.9
GLISTER (Killamsetty et
2021b)
95.1
94.5
90.9
85.3
69.3
78.1
74.1
68.2
58.1
52.4
68.7
65.6
61.4
08.3
52.0
CAL-SDS2 (Das et al. 2023)
95.7
94.4
92.1
88.9
R1.5
77.6
74.5
69.1
6:11
56.2
718
70.5
68.0
61.2
56.1
Moderate (Xin ot.,, 2023)
93.9
92.6
90.6
57.3
81.0
74.6
71.1
65.3
58.5
45.5
72.0
703
65.9
61.3
52.1
OCS (Zheng ai.,, 2022)
954
95.0
93.0
91.
86.9
744
68.9
64.0
57.3
72.3
705
67.8
64.5
57.3
K-Conter
57.2
BADGE al,, 2019)
82.5
58.9
47.8
53.4
PRUNING
95.7
91,9
93.3
91.4
87.1
78.2
75.9
70.5
63.2
56.9
72.9
71.8
68.1
65.9 55.6
Table 2: Results on NLP Datasets. Comparison of performance (acc.) of DD2 PRUNING with existing coreset selection methods on ANLI, ImDB reviews using pretrained RoBERTaL Higher is better.
Datuoet (-)
Adversarial (ANLT)
ImDB Ruviews (2k)
Pruning (-+)
30%
70%
Random
85.6
81.3
Entropy (Cxleman et al., 2010)
45.
90.6
$1.3
Variance (Susyandipto 20200)
48.3
45.4
41.7
91.4
90.2
$1.5
50.7
EL2N (Pual et al., 2021)
47.7
46.3
43.9
41.1
40.3
91.6
91.4
51.0
50.5
50.3
AUM (Plcss al., 2020)
47.9
36.2
42.7
41.0
39.5
91.6
91.6
53.4
50.3
50.3
GLISTER (Killammetty et al. 2021b)
48.6
46.2
43.8
45.1
79.9
90.9
91.2
90.1
89.1
87.4
CAL-SDS2 (Dus el al., 2023)
45.2
46.8
44.1
43.1
10.2
90.7
90.5
85.4
86.2
88.3
Moderate (Xia ct 2023)
46.1
44.5
43.2
42.5
40.3
91.4
91.2
3819
89.8
85.4
(Zhmg 3022)
48.5
46.2
44.5
43.2
40.4
91.6
90.8
90.2
89.6
87.5
CCS + k-Center
48.4
46.3
44.1
45.
40.2
91.4
91.0
90.6
90.2
88.3
BADGE (Ash 2019)
39.5
91.3
90.0
89.5
INGENIOUS (Kenduchintala
82.4
PRUNING
91.3
90.9
90.3
high pruning rates for providing even coverage over easy and difficult samples. However, at lower pruning rates (or with increasing data budget), difficult training samples yield lower test loss from deep learning models (Sorscher et al., 2022). The hyperparameters i and yr in ID² PRUNING (see Sec. 3) allow flexibility in the distribution of easy/difficult samples in coresets. We find that higher values of ",, and lower value of DD2 PRUNING leads to a coreset that is skewed towards more difficult samples and benefits performance at lower pruning rates. Conversely, low 7 and high & lead to an equitable distribution over casy/difficult samples and are more useful for higher pruning rates. CAL-SDS2 (Das al., 2023) also introduces tunable hyperparameter for balancing difficulty and diversity, however, its use of facility location (Iyer et al., 2021) for measuring diversity yields lower gains than the graph-based local neighborhoods in 2 PRUNING. See discussion on hyperparameters in Sec.5.2 and qualitative analysis of coresets in Sec. D, Appendix.
Results from the evaluation of various coreset selection methods, including ID2 PRUNING, on NLP datasets are presented in Tab. 2. First, we find that when pretrained language models (PLMs) are finetuned on task-specific datasets, the models do not suffer from a catastrophic decline in performance at high pruning rates, in contrast to models trained from scratch on vision datasets. For IMDB reviews, the performance of finetuned RoBERTa goes from 91.8% at 0% pruning to 81.3% at 90% pruning using random sampling. The performance improves to 87.5% 755% using CCS coreset selection and further improves to 90.3% (p < 0.05) using ID² PRUNING. The ANLI dataset has been carefully crafted with an iterative, adversarial suman--nd--modl-inn-tee significantly less redundant than conventional NLP datasets. The performance for ANLI falls from 48.8% to 42.8% at 80% pruning using random sampling. In this case, CCS coreset selection does not lead to a significant improvement in performance (43.2%) whereas D2 PRUNING improves the performance by 1.7% to obtain 44.5% (p < 0.05). Score-based selection methods largely fail to yield results better than random pruning at high pruning rates. Additionally, the use of facility location function for representing diversity CAL-SDS2 (Das et al., 2023) and INGENIOUS (Renduchintala et al., 2023) yield less gains than our graph-based approach in D PRUNING.
process, and hence, is
5.2 ANALYSIS OF D PRUNING
D2 PRUNING contains two hyperparameters, nearest neighbors and reverse message passing weight Yr (see Sec. 3) that allow various distributions of importance scores in the selected coreset. At low
7

---

Published as a conference paper at ICLR 2024
A.
daboret datribution
A-10 y. Ermoay---45
1-10, y-m01, Ertrsgy-100:
30% Fruning CIAAR100
0.
Fecureyy
01
20
40
20
40
90% Fruning of CIRAR100
C.
Full sataget dictttution
Dificult Soore
1-1 y LB. 2ntrapy-2./85
Difficllty Score
600100 y..... Cotmoyy-1.0
Difficulty Score
Froeton of Datsott
K-0.0
4=1.0
0.20
8.05
Neighoorrs
20
Dimiiity Stree
50
120
Dificcllt Score
50
100
Difficuly Score
120
Figure 3: Effect of ki Tr- (A) Accuracy at 30%, 90% pruning of CIFAR100 for nearest neighbors (k) and message passing weight "y values; Distribution of difficulty scores in the best coresets selected via 2 PRUNING for 30% (center) and 70% (right) pruning of (B) CIFARI00, (C) ImageNet- IK.
pruning rates (see top, Fig. 3())), higher k has small effect on performance when the updates during reverse message passing are weak (7,=1.0). However, the coresets selected at high k and low "r include majority of the difficult samples from the full dataset, which works best for low pruning rates on CIFARI00, as demonstrated by the distribution of importance scores in best- west-performing coreset at 30% pruning rate (see Fig. 3B). center). We use this insight pick similar configuration of D&² PRUNING for ImageNet- IK and find that it transfers well. The distribution of difficulty scores in the rest-performing coreset of ImageNet- 1K at 30% pruning rate is presented in Fig. 3(C).
Higher k improves performance when large updates (%,=0.)) are being made to the nodes connected to the selected node at high pruning rates (see bottom, Fig. 3()). This is because low 7 value leads to aggressive downweighting of semantically similar samples when sample is selected and promotes diversity under a fixed data budget. The selected samples also form an equitable distribution over a small range of difficulty scores. Consequently, such coresets work best for medium-to-hin pruning rates, as evidenced by the distribution of difficulty scores in the best performing coresets at 70% pruning rate for CIFAR 100 and ImageNet-I K (see Fig. 3(B.)), right).
5.3 SELF-SUPERVISED AND UNSUPERVISED APPROACHES USING D2 PRUNING
Existing methods for obtaining sample difficulty scores generally rely on a model trained on the full dataset, which undermines their utility for scalably curating new datasets. Hence, we adopt 2 PRUNING for self-supervised and unsupervised data selection approaches.
Self-supervised coreset selection. Sorscher et al. (2022) use embeddings from SWAV, model trained on ImageNet- Ik in a self-supervised manner, and use the spatial distribution of the samples in the embed- ding space to assign difficulty scores (prototypicality). ) This menthod suffers drastically at over 30% prun- ing rates (see Fig. 4.). When combined with CCS, it yields 10% gain for 90% pruning rate and lesser gains for 70%, 80% pruning rates. We adopt 2D2 PRUNING for similar supervueee approach by using SWAV embeddings to compute sample distances and initial- ize node features with unit value. In the absence of difficulty scores, 2 PRUNING ranks the samples solely by the density of their neighborhood the em- bedding space. ID2 PRUNING improves performance by 3% at 80% pruning rate and provides similar gains over prototypicality for lower pruning rates.
Performance of Seliispeeriised Pruning Methods
75
Superssed Prurtig (Bec)
Randan
Polssppoulty
Protebpice
20
04
Figure 4: Self-supervised pruning of
ImageNet- IK. D2 PRUNING performs as well supervised pruning at 30% and signifi- cantly improves over existing methods.
Unsupervised data filtering, Gadre et al. (2023) show that a simple strategy of retaining the samples with high CLIP score is strong baseline filtering method (see Tab. 3) on DataComp, massive unfiltered corpus of images and texts to train CLIP-style models (Radford et al., 2021).* However, a
'Our reproduced numbers are lower than Gadre et al. (2023) because some images in the original corpus fail download. We report improvements using TD² PRUNING this subset of images for fair comparison.
8

---

Published as a conference paper at ICLR 2024
Table 3: Results on DataComp. Comparison of performance (acc.) of TD2 PRUNING with CCS
(Zheng al., 2022) and data filtering methods presented in Gadre et al. (2023). Higher is better. Fillering Stralegy
Dalase Size
ImaggeNet
ImageNet Dist. Shin
VTAB
Retrieval
Average
fitering (Giddia al., 2003)
128M
2.5
13.2
lext-based fittning (Cadre 2023)
Imuge-lused fitteing (Gadre
2023)
17.8
12.1
CLIP score (1/14 30%) (Gadre et al,, 2025)
3.8
5.1
5.5
19.0
11.7
17.3
CLIP score (L/14 30% ceproduced)
3.8
5.1
56
17.0
11.9
16.0
al., 2022)
PRUNING (image text)
388
5.1
566
18.2
11.7
17.0
12 PRUNING (image only)
3.5
4.4
511
16.9
12.1
15.9
only)
T.MARS (Maini et al., 20233
2.5M
6.3
6.6
17.9
12.8
17.7
T-MARS D PRUNING (Image +
2.5M
655
6.7
19.1
12.8
18.8
strategy based on individual sample scores only ignores potential redundancies in the dataset and may allot unnecessary data budget to an easy but dense region of the sample space. Hence, we adapt DD PRUNING for filtering DataComp by treating the CLIP score as the difficulty score and using CLIP embeddings for computing sample distances. The data selected by ID2 PRUNING using both, CLIP text and image embeddings, for computing sample distances improves average zero-shot performance on 38 image classification, multimodal datasets by 1% at same data budget (see Tab. 3.). When combined with filtering method T-MARS (Maini et al., 2023) that removes images containing overlapping textual content (with caption), ID? PRUNING achieves cumulative improvements.
RELATED WORK
Coreset Selection. Coreset selection has been widely studied in machine learning (Welling, 2009; Chen et al., 2010; Feldman et al., 201 for supervised learning. Recent works have focused on large datasets and deep networks. Geometry-based methods remove redundant information (Welling, 2009; Sener & Savarese, 2018). Uncertainty//los/errooo based methods estimate the difficulty of sample from model confidence (Swayamdipta et al., 2020) or its training dynamics (Toneva et al., 2018; Paul et al., 2021; Bachem et al., 2015). Submodular functions (Wei et al., 2015; Killamsetty et al., 2023), gradient-matching (Mirzasoleiman et al., 2020), and optimization (Yang et al., 2022; 2023; Park et al., 2022) have been explored for coreset selection. Zhou & Bilmes (2018); Zhou et al. (2020); Das et al. (2023) combine submodular functions with difficulty scores for selecting data. Joshi & Mirzasoleiman (2023) study the importance of data samples for self-supervised learning via submodular optimization. We combine data diversity and sample difficulty via graphs for selection.
Data Pruning in NLP. Works exploring coreset selection methods for NLP datasets have been far and few (Fayyaz et al., 2022). Abbas et al. (2023) removes semantic duplicates from C4 dataset (Raffel et al., 2020) to reduce data size and improve performance. Kaddour (2023) introduce a small version of the Pile dataset (Gao et al., 2020) for pretraining BERT (Devlin et al., 2018; Liu et al., 2019). We evaluate coreset selection methods on sentiment analysis, natural language inference tasks.
Graphs & Message Passing for Data Selection. Neural message passing (Yadav et al., 2019; Yadati et al., 2019) is well-explored graph neural networks for chemical structures (Gilmer et al., 2017), however, has seen less exploration in the representation of datasets. Kim et al. (2021) use message-passingg passiggggaaiigggggg to learn the topology of data in online learning. Ebert et al. (2012) use message- passing based on feature distance only for performing graph-based density sampling during active learning. Hongjin et al. (2022) construct a sparse graph from the k-nearest neighbors of in-context examples and nown-weiight the selected example's ' connected nodes, which is similar to the reverse sassage-passing step in D PRUNING. In contrast, we initialize the nodes with sample importance scores and first use forward pressage-passing to merge the influence of importance score and density of local neighborhood to rank samples in D PRUNING.
7 CONCLUSION
We introduce a novel coreset selection algorithm, Dd2 PRUNING, based on message- message-passing within a graph representing the dataset. Our algorithm combines data diversity and difficulty select a coreset that outperforms existing coreset selection methods at now-to-meding pruning rates on multiple vision and NL.P benchmarks, and can be adapted into self-supervised, unsupervised data selection.

---

Published as a conference paper at ICLR 2024
Reproducibility. We report the training hyperparameters used for our best models, well the best hyperparameters for 2 PRUNING (see Sec. 3 and a discussion Sec. 5.2) in the Appendix. The code for rumning the experiments in paper is available part of the supplementary submission. All datasets used in our experiments are openly available.
REFERENCES
Amro Abbas, Kushal Tirumala, Dániel Simig, Surya Ganguli, and Ari S Morcos. Semdedup: Data- efficient learning at web-scale through semantic deduplication. arXiv preprint arXiv:2303.09544 2023.
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.
Olivier Bachem, Mario Lucic, and Andreas Krause. Coresets for nonparametric estimation case of de-means. In International Conference on Machine Learning, pp. 209-217. PMLR, 2015.
Robert Baldock, Hartmut Maennel, and Behnam Neyshabur. Deep learning through the lens of example difficulty. Advances in Neural Information Processing Systems, 34:10876-10889, 2021.
Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. In Proceedings of the 2015 Conference Empirical Methods in Natural Language Processing, pp. 632-642, 2015.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in neural information processing systems, 33:9912-9922 2020.
Kwan Ho Ryan Chan, Yaodong Yu, Chong You, Haozhi Qi, John Wright, and Yi Ma. Redunet: A white-box deep network from the principle of maximizing rate reduction. The Journal of Machine Learning Research, 23(1):4907-5009, 2022.
Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pp. 109-116, 2010.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. International Conference on Learning Representations, 2019.
Arnav Mohanty Das, Gantavya Bhatt, Megh Manoj Bhalerao, Vianne R Gao, Rui Yang, and Jeff Bilmes. Accelerating batch active learning using continual learning techniques. Transactions on Machine Learning Research, 2023.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Ieee, 2009.
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1rXiv:1810.04805. 2018.
Sandra Ebert, Mario Fritz, and Bernt Schiele. Ralf: A reinforced active learning formulation for object class recognition. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3626-3633. IEBE, 2012.
Mohsen Fayyaz, Ehsan Aghazadeh, Ali Modarressi, Mohammad Taher Pilehvar, Yadollah Yaghoobzadeh, and Samira Ebrahimi Kahou. Bert on a data diet: Finding important examples by gradient-based pruming. arXiv preprint 1tXi::2211.05100 2022.
Dan Feldman, Matthew Faulkner, and Andreas Krause. Scalable training of mixture models via coresets. Advances in neural information processing systems, 24, 2011.
10

---

Published as a conference paper at ICLR 2024
Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang. Jonathan Hayase, Georgios Smymis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets. arXiv preprint axXiv:230..4100. 2023.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint 1xXi::20110002: 2020.
Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. In International Conference Learning Representations, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In Dutabase and Expert Systems Applications: 33rd International Conference, DEXA 2022, Vienna, Austria, August 22-24 2022, Proceedings, Part I, pp. 181-195. Springer, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Xiaochuang Han and Yulia Tsvetkov. Influence tuning: Demoting spurious correlations via in- stance attribution and instance-driven updates. In Findings of the Association for Computational
Linguistics: EMNLP 2021, pp. 4398-4409 2021.
SU Hongjin, Jungo Kasai, Chen Henry Wu, Weijia Shi, Tianlu Wang, Jiayi Xin, Rui Zhang, Mari Ostendorf, Luke Zettlemoyer, Noah A Smith, al. Selective annotation makes language models better few-shot learners. In The Eleventh International Conference on Learning Representations, 2022.
Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combinatorial information measures with applications in machine learning. Algorithmic Learning Theory, pp. 722-754. PMLR, 2021.
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, and Michael C Mozer. Characterizing structural regularities of labeled data overparameterized models. In International Conference on Machine Learning, pp. 5034-5044. PMLR, 2021.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions Big Data, 7(3):335 547, 2019.
Siddharth Joshi and Baharan Mirzasoleiman. Data-efficient contrastive self-supervised learning: Most beneficial examples for supervised learning contribute the least. In International conference on machine learning, pp. 15356-15370. PMLR, 2023.
Jean Kaddour. The minipile challenge for data-efficient language models. arXiv preprint arXiv:2304.08442. 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0883 2020.
Kirshnateja Killamsetty, Alexandre V Evfimievski. Tejaswini Pedapati, Kiran Kate, Lucian Popa, and Rishabh Iyer. Milo: agdestag subset selection framework for efficient model training and tuning. arXiv preprint wrXiv:2301.13287 2023.
Krishnateja Killamsetty, Sivasubramanian 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, pp. 5464-5474, PMLR, 2021a.

---

Published as a conference paper at ICLR 2024
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8110-810111111 8118, 2021b.
Tachyeong Kim, Injune Hwang, Hyundo Lee, Hyunseo Kim, Won-Seok Choi, Joseph J Lim, and Byoung- Tak Zhang. Message passing adaptive resonance theory for online active semi-supervised learning. International Conference on Machine Learning, pp. 5519-5529. PMLR, 2021.
Yeachan Kim and Bonggun Shin. In defense of core-set: A dens core-set selection for active learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 804-3 812, 2022.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pp. 142-150, 2011.
Pratyush Maini, Sachin Goyal, Zachary C Lipton, Zico Kolter, and Aditi Raghunathan. T- mars: Improving visual representations by circumventing text feature learning. arXiv preprint arXiv:2307.03132. 2023.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950-6960.
PMLR, 2020.
Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. Adversarial nli: A new benchmark for natural language understanding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4885 4901, 2020.
Eric W Noreen. Computer-intensive methods for testing hypotheses. Wiley New York, 1989.
Dongmin Park, Dimitris Papailiopoulos, and Kangwook Lee. Active learning strong baseline for data subset selection. In Has it Trained Yet? NeurlPS 2022 Workshop, 2022.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34: 20596-20607, 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.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. International conference on machine learning, pp. PMLR, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-555 -5551, 2020.
HSVNS Kowndinya Renduchintala, Krishnateja Killamsetty, Sumit Bhatia, Milan Aggarwal, Ganesh Ramakrishnan, Rishabh Iyer, and Balaji Krishnamurthy. Ingenious: Using informative data subsets for efficient pre-training of large language models. arXiv preprint arXiv:2305.0661 2023.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set
approach. In International Conference Learning Representations, 2018.
12

---

Published as a conference paper at ICLR 2024
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang. Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing, pp. 1631-1642, 2013.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35:19523-19536, 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.
Robert Tibshirani and Bradley Efron. An introduction to the bootstrap. Monographs on statistics and applied probability. 57:1-436, 436, 1993.
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 on Learning Representations, 2018.
Peter Turney. Thumbs up or thumbs down? semantic orientation applied to unsupervised classification of reviews. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 417-424, 2002.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1)), 2008.
Shikhar Vashishth, Prateek* Yadav, Manik Bhandari, Piyush Rai, Chiranjib Bhattacharyya, and Partha Talukdar. Incorporating syntactic and semantic information in word embeddings using graph convolutional networks. In Proceedings of the 57th Annual Meeting of the Association for Compu- tational Linguistics. pp. 3308-33 -311, Florence, Italy, July 2019a. Association for Computational Linguistics. doi: 18.18653/v 1/t1/ 1320. https : / a /a//cccannttt aclanthology, wrtp:/r-gg1/11/
Shikhar Vashishth, Prateek* Yadav, Manik Bhandari, and Partha Talukdar. Confidence-basee graph convolutional networks for semi-supervised learning. In Kamalika Chaudhuri and Masashi Sugiyama (eds.). Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 1792-1801. PMLR, 16-18 Apr 2019b. URL https: http:::://ppcceednngs.... Pashishth. 9a html.
war.ggssml...................mme mlr prw.spppes///ee... v
Kai Wei, Rishabh lyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pp. 1954-1963. PMLR, 2015.
Max Welling. Herding dynamical weights to learn. In Proceedings of the 26th Annual International Conference Machine Learning, pp. 1121-1128, 2009.
Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, and Tongliang Liu. Moderate coreset: A universal method of data selection for real-world data-efficient deep learning. In The Eleventh International Conference on Learning Representations, 2023.
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hyper- graphs. In H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché-Bun -uc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019, URL https: http:s/:///ccceeeiegeee www.riiiinnnnnnnnnnnoeeeeee neurips wecpiis..ccpppppee wttpc/pppp/e/////e/eee/ /2tp///119/////////////
Prateek Yadav, Madhav Nimishakavi, Naganand Yadati, Shikhar Vashishth, Arun Rajkumar, and Partha Talukdar. Lovasz convolutional networks. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty-Secone International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 1978-1987. PMLR, 16-18 Apr 2019. URL https: httpess///prooeeeo ptop/eooceeeiie ngs ml press / v ///9////9////////// yadvvi 9a html.
13

---

Published as a conference paper at ICLR 2024
Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, and Ping Li. Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint arXiv:2205.09339, 2022.
Yu Yang, Hao Kang, and Baharan Mirzasoleiman. Towards sustainable learning: Coresets for data-efficient deep learning. In International Conference on Machine Learning, pp. 39314-39330. PMLR, 2023.
Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, and Yi Ma. Learning diverse and discriminative representations via the principle of maximal coding rate reduction. Advances in Neural Information Processing Systems, 33:9422-9434, 2020.
Yu Yu, Shahram Khadivi, and Jia Xu. Can data diversity enhance learning generalization? In Proceedings of the 29th international conference on computational linguistics, pp. 4933 4945, 2022.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage-centric coreset selection for high pruning rates. arXiv preprint MxXiv:2210115801 2022.
Tianyi Zhou and Jeff Bilmes. Minimax curriculum learning: Machine teaching with desirable difficulties and scheduled diversity. In International conference on learning representations, 2018.
Tianyi Zhou, Shengjie Wang, and Jeffrey Bilmes. Curriculum learning by dynamic instance hardness. Advances in Neural Information Processing Systems, 33:8602-8613. 2020.
OVERVIEW
The appendix is organized as follows:
Section A: Details of the datasets, baselines and the best hyperparameters for our models.
Section B: Computational complexity of ID2 PRUNING for all datasets.
Section C: Additional results for high pruning rates and ablation experiments.
Section D: Qualitative analysis of coresets selected via 2 PRUNING.
Section E: Limitations and license.
A DATASETS & HYPERPARAMETERS
A. DATASETS
Vision Benchmarks. We use the CIFARIO, CIFAR100 (Krizhevsky et al., 2009) and ImageNet-I1 (Deng et al., 2009) image classification datasets for our experiments on vision benchmarks. The (IFAR10 dataset consists of 60000 32x32 color images for 10 classes, with 6000 images per class. The training and test splits contain 50000 and 10000 images respectively. The CIFAR 100 dataset has 100 classes containing 500 and 100 images per class in the training and test splits respectively. Details about the class labels in CIFAR 10, CIFAR 100 datasets can found here. The ImageNet- IK dataset comprises approximately 1.2 million real-world images distributed over 1000 object classes. contains 167 and 50,000 images in training and validation splits respectively.
NLP Benchmarks. We select two popularly used NLP tasks i.c. natural language inference (NLI) (Bowman et al., 2015) and sentiment analysis (Tumney 2002). For natural language inference, we use the Adversarial NLI dataset (Nie et al., 2020) that has been created an iterative human-and- model-in-the-logg adversarial procedure. During each iteration, human annotators are instructed to devise examples that the current best models are unable to answer correctly. The models are trained on these challenging annotations for stronger performance. Multiple rounds of such iterations result in a challenging NLI benchmark. We use the data created in the third (and final) round of this process which contains 100459, 1200. and 1200 examples in the training, development, and test splits respectively. We use the ImDB reviews dataset (Maas et al., 2011) for the sentiment analysis task. The original dataset contains 25000 examples each in the training and test splits and is binary
14

---

Published as a conference paper at ICLR 2024
Table 4:
Best values of nearest-neighhors (k) and reverse message passing weight (%) for vision datasets. See discussion on these hyperparameters in Sec. 5.2.
Dataset (-)
CIFAR10
CIFAR100
ImageeNet-1K IK
Pruning Rate (-)
0%
30%
50%
70%
80%
90%
0%
30%
50%
70% 80%
90%
0%
30%
50%
70%
80%
90%
Nearest Neighbors (k)
10
10
10
10
15
50
100
10
Reverse Message Passing (nv)
0.9 1.0 0.1 0.0 0.0
0.9
0.8 0.3
033 0.0 1.0 1,0 0.3 0.1 0.0
Table 5:
Best values of nearest-neighbors (k) and reverse message passing weight (7r) for NLP datasets and self-supervised D2 PRUNING of ImageNet-1K K. See details in Sec. 5.2.
Dataset (-)
Advercarial NI.I
ImDB(2K)
ImageNet- IK (sellsunerviseed)
Pruning Rate
0%
30%
50%
70%
80%
90%
0%
30%
50%
70%
80%
90%
0%
30%
50%
70%
80%
90%
Neurest Neighbors (l)
15
10
5
5
10
10
10
2
100
25
10
25
Reverse Message Passing (%)
1.0
0.1
0.1
0.0
1.0
0.8
0.3
0.0
1.0
0.5
0.5
0.0
classification dataset. Our experiments showed that models trained on 10% of this dataset achieved nearly the same performance as 100% of the dataset. We observed similar trends for other popular sentiment analysis benchmarks well such Yclp Reviews (Zhang et al., 2015), SST2 (Socher et al., 2013) etc. Hence, we created an in-house version of the ImDB Reviews dataset that contains 2000, and 1000 samples in the training and development splits respectively, that are randomly selected from the original training set. We retain the original test split containing 25000 samples for evaluation in our experiments.
A.2 BASELINES
(Supervised) We compare D PRUNING with several score-based and geometry- -based coreset selec- tion methods derived from the training dynamics of a model trained on the full dataset as discussed in Zheng et al. (2022): A) Random selection of examples. B) Entropy (Coleman et al., 2019) of model's prediction vector. C) Forgetting (Toneva et al., 2018) score for each example i.e., the number of times model predicts the example incorrectly after having predicted correctly in the previous epoch. D) EL2N (Paul et al., 2021) i.c. L2 norm of eгror vectors. E) Area under the margin (Pleiss al., 2020) score that measures the gap between the prediction probability of the correct target and the next highest probability target. E) Moderate coresets (Xia et al., 2023) that selects samples at median distance from class center, F) Coverage- based Coreset Selection (CCS) (Zheng et al., 2022) that divides a range of difficulty scores into cqual-sized bins and randomly samples from each bin, and is sfate-of-art for high pruning rates, G) CCS + k-Center, where k-center samples are selected within each CCS bin, H) BADGE that selects diverse samples using k-means++ in the gradient vector space. D) GLISTER (Killamsetty et al., 2021b) uses bi-level optimization to select robust coresets, J) CAL-SDS2 (Das et al., 2023) combines a facilty location submodular function (lyer et al., 2021) with entropy scores to unify the effects of difficulty score and diversity, and J) INGENIOUS (Renduchintala et al., 2023), diversity-only approach that uses facility location as the information gain function for NLP tasks. (Unsupervised) We compare DD2 PRUNING with A) Prototy Prototypicality (Sorscher et al., 2022) that uses self-supervised embeddings compute k-means clusters and treats samples at a farther distance from the cluster center as more important, B) CCS over prototypicality scores, and C) Moderate coreset selection (Xia et al., 2023) over the self superviedd embeddings.
A.3 TRAINING HYPERPARAMETERS
Coreset Selection. We use the recommended hyperparameters in Zheng et al. (2022) for exper- iments using Coverage-based coreset selection (CCS) i.e. 50 bins (or strata) for all pruning rates. Models trained on vision datasets are also subjected to hard cutoff rate 3 on the difficulty score for climinating outliers or erroneous samples (see Zheng et al. (2022) for the values). We report the best hyperparameters for 2D2 PRUNING in Tabs. 4& 5.
We follow the best training hyperparameters for ResNet18 model and ResNet34 models as suggested in Zheng et al. (2022) to remain emoparable to the numbers reported in their work. For fine-tuning of pretrained RoBERTa on NLP datasets, we perform grid search over learning
Models.
15

---

end for Published as a conference paper at ICLR 2024
rates (1c"6,ee" 2e 55-5. 1 and batch sizes {8, 16, 32) using 100% of the data, which results in learning rate le 44 and batch size of 32 for Adversarial NLI, ImDB (2k) datasets. Models are trained on pruned datasets using the same hyperparameters that used for training 100% of the data. The maximum number training steps is kept constant across all pruning rates. RoBERTa models trained for 10000 and 1500 training steps for Adversarial NLI and ImDB (2k) datasets respectively, with early stopping.
Algorithm 1 DD2 PRUNING for Data Selection
I: selectioo = supervised then
2: Input Data: D æ,
else
4: Input Data: D ク=<オ>
5: end if
6: Validation Data: D æ,
7: Input Data: Drest < 2.
9: Train:
10: 0. initialize trainable parameters
11: for epoch ..2.....VV .V do
Train O,
13: end for
14:
15: Optimize Data Selection using 2 PRUNING:
16: (k) grid search values for nearest-neighbor hyperparameter in ID2 PRUNING
(イ-} < grid search values reverse message passing hyperparameter ID' PRUNING
18: D. < number of samples to be selected
19: for lc in {k) do
20:
for 7, in (7.) do
21:
22:
Select D2 C using 2 PRUNING: G + -niitiallize graph in D PRUNING using k Tr. Og
23:
24:
for d 1,2 ......... ..... do
25:
Perform forward message passing for for i 11 D. do
26:
27:
28:
Select sample with highest node feature and add to D, Downweight neighbors of selected sample
29:
30:
31:
Obtain labels for D.
32:
33:
Train D.:
34:
0, initialize trainable parameters
35:
for epoch = I, .,,.....N N do
36:
Train 0, on D. end for
37:
38:
Evaluate 02 on Deaf
39:
40:
end for
41:
end for
42:
43: Evaluate best O.. Drest
B COMPUTATIONAL COMPLEXITY OF 2 PRUNING
We divide the runtime of 2 PRUNING into: (1) Graph creation which includes graph initialization and forward message passing, (2) Iterative selection (see Sec. 3) and present results Tab. 6 for 100% data selection of the various datasets used in our experiments. Numbers are rounded to the nearest minute. Runtime for iterative selection is proportional to the size of the coreset being selected. Hence, in practice, the runtime for iterative selection is lower since we only select subset of the data in our experiments. Time estimates of graph creation for different datasets are not strictly comparable because jobs of different batch sizes according to the size of the dataset to prevent
16

---

Published as a conference paper at ICLR 2024
Table 6: Computational Overhead for ID² PRUNING. Comparison of runtime of TD² PRUNING for 100% selection of the various datasets in our experiments. D2 PRUNING can be divided into the "Graph creation' and 'Iterative selection' steps (see General Response). Larger datasets like DataComp have a 'faiss indexing' step to enable fast nearest-neighhor lookup. Results are computed using multi-thread implementation of D2 PRUNING using 8 workers on a CPU with 32 cores.
Dataset (+)
CIFARIO CIEARI00 Adv. NLI ImDB DataComp ImageNet-IK
faiss indexing
25m
Graph creation
2m
Im
4m
1m
30m
15m
Iterative selection
1m
1m
2m
1m
7m
8m
Total selection time
3m
6m
2m
1h 2m
23m
Training time
4h 30m
4h 45m
2h
15m
4h 15m
125h
Table 7: Results on Vision Datasets. Comparison of performance (acc.) of ID² PRUNING with existing coreset selection methods for very high pruning rates on CIFAR1O, CIFAR 100 using ResNet18, and ImageNet- Ik using ResNet34 models. Higher is better.
Dataset .)
CIFAR10
CIFAR100
ImageNet-1K
Prusing Rate (-))
0%
90%
95%
99%
99.5%
99.9%
0%
90%
95% 99%
99.5%
99.9%
0%
90%
95%
99%
99.5%
99.95
Random
79.0
28.7
11.1
CCS (Zheng al., 2022)
86.9
77,2
41.8
33.0
25.7
57.3
36.9
13.5
57.3
45.9
10.1
6.2
D' PRUNING
87.1
74,5
44.4
33,8
24.6
56.9
35.8
14.2
59
24
55.6
418
7.6
7.2
1,9
OOM issues when computing similarity matrix. Additionally, we provide the approximate training times for each dataset computed on single A 100 GPU.
C ADDITIONAL RESULTS
C.I RESULTS ON HIGH PRUNING RATES
We perform coreset selection at very high pruning rates (Guo et al., 2022) for CIFARIO, CIFAR100 and ImageNet-IK using D PRUNING and select few baselines, and present results in Tab. 7. D PRUNING outperforms random selection as well as CCS (Zheng et al., 2022) in some scenarios, such as by 3% and 0.5% at 99% and 99.5% pruning of CIFARIO respectively. However, we do not see any consistent trends in improvement using D PRUNING at very high pruning rates, especially for ImageNet-1 K. Improvement margins using CCS also go down at high pruning rates, suggesting that diversity is not as important as difficulty when the data budget is extremely low (Sorscher et al., 2022).
C.2 ABLATION EXPERIMENTS
Multiple message passing iterations. To better understand the effect of the forward message passing procedure in 2 PRUNING, visualize a random subset of CIFAR10 samples in 2- dimensional (-SNE (Van der Maaten & Hinton, 2008) embedding space in Fig. 5 before and after forward message passing under various scenarios. When the graph first initialized in IB2 PRUNING, the node feature is initialized with the sample's 's importance score (see Fig. 5A). A single iteration of a forward message passing over the local neighborhood of sample consisting of nearest neighbors leads to the significant up-weighting of neighbors of a very important node. Thus, higher & leads up- weightiigtng of larger neighborhood of samples in the spatial dimension (see Fig. 5B vs. Fig. 5C). Consequently, the distribution of normalized node feature values has heavier tail with increasing k, as compared to the distribution of original importance scores. In contrast, multiple iterations of message passing at the same & have an effect similar to that of Gaussian smoothing in the embedding space (see Fig. 5D). With increasing iterations, the local neighborhood of a node becomes increasingly similar to that of other nodes in the graph, and hence, all nodes receive similar updates (see Fig. 5D vs. Fig. SE). As a result, the distribution of node features is biased towards a narrow spectrum of values that longer benefits the data selection task (see results in Tab. in Appendix).
17

---

Published as a conference paper at ICLR 2024
(A) Initialization
iterm1l Km5
(C) Iterm1. km10
iteem Km10
(E) iterm3, km10
t:SNE
02
0.0
Density
10
0.00
0.50
5.75
1.00
0.50 0.75
100 0.23
0.50
0.75
1.00 0.00 0.25
1.00 0.00 0.25
1.00
Normalized node feature value
Figure 5: Effect of forward message passing iterations. (top) Scatter plots of CIFARIO samples' normalized node feature values in a t-SNE embedding space (dim=2) and (bottom) corresponding histograms for the following scenarios: (A) Initialization of graph in D2 PRUNING, one-shot forward message passing with k=5 (B) and k=10 (C) nearest neighbors, and two-shot (D), three-shot (E)
forward message passing k=10.
Table 8: Ablation Analysis. Results from ablations of ID² PRUNING by varying the embedding representation (rows A-B), difficulty score (rows C-F), and multiple iterations message passing (rows H-J) CIFARIO and Adversarial NLI datasets. Higher is better.
Datasel (-)
CIEAR10
Adversurial NLI
Pruning Rate (-))
70%
Last Layer/ [CTS]
95.5
95.7
94.9
93.3
91.4
87.1
48.8
48.9
46.7
45.3
44.5
40.3
B.
Pre-final convolutional/ pon-[CLS) (CLS)
95.1
94.9
92.7
90.5
85.4
45.3
45.3
42.7
42.8
39.1
Forgetting/ Variance
45.3
44.5
D.
Entropy
95.6
94.6
93.8
91.9
87.3
48.5
46.1
45.4
44.2
40.1
E.
EL2N
94.9
94.2
93.1
91.1
86.0
49.3
47.9
45.2
44.3
40.3
F I-shot
95.5
95.7
94,9
93.3
91.4
87.1
48.8
48.9
46.7
45.3
44.5
40.3
94.1
Effect of importance scores. We experiment with different importance scores 1 PRUNING and present results in Tab. 8 in Appendix. We find that the entropy score (Coleman et al., 2019) benefits performance on CIFAR10 at higher pruning rates, whereas EL2N (Paul et al., 2021) benefits performance Adversarial NLI for low pruning rates. Importantly, we do not large drops in performance with any of these score functions, suggesting that the idea of combining diversity and difficulty in ID PRUNING is universally beneficial. Further, improved difficulty metrics be paired with 2 PRUNING for larger improvements in data selection.
Effect of embedding sources. Next, we experiment with alternative sources of feature embeddings for measuring the distance between two samples. Since final layers in a task-specific model are known to be attuned to the task (Han & Tsvetkov, 2021). instead, we extract features from the last convolutional layer in ResNet18 for CIFARIO and use the average of non-[CLS] tokens RoBERTa for ImDB dataset (row B). We find that neither source effective as the features extracted from the last layer of the model trained on the full dataset. Especially, we see large drops in performance on the use of non- [CL[] token features for representing diversity. We leave the study of the utility of different embedding spaces for measuring diversity to future work.
D ANALYSIS & DISCUSSION
Qualitative analysis of coresets selected by TD2 PRUNING In order to perform a qualitative analysis of the merits of 2 PRUNING, we first use the connectivity graph G to extract meaningful sub-populations from the entire ImageNet-1K dataset. For each sample, we recursively seek nearest neighbors that are situated at distance in the embedding space that is less than a predefined threshold. Next, for each of these sub- aub-oopllations we differentiate the samples that appear in the coreset selected by 2 PRUNING at 30% pruning of ImageNet- IK. We present and analyze few representative sub-populations Fig. 6. First, we observe several cases where 2 PRUNING successfully avoids selecting perceptual duplicates (Abbas al., 2023) in the coreset (see top left and middle left in
18

---

Published as a conference paper at ICLR 2024
X
Figure 6: Example of coresets selected by D PRUNING from ImageNet-IK K at 30% pruning rate. Image sub-populations are extracted from ImageNet- IK by recursive traversal of the connectivity graph G initialized for IBa PRUNING. For each sub-population show the images retained in the coreset with v and the images left out of the coreset with
Fig. 6). Next, see multiple cases where a composite image is selected for the coreset, and images that contain one or more of the subjects/objects in the selected image are left out (see middle right in Fig. 6). Finally, we find that relying on the semantic similarity of pretrained embeddings can lead to the propagation of errors, seen in the sub-population on the bottom right in Fig. 6. The images that contain dolphins are left out of the coreset because of their similarity an image depicting a water landscape.
Visualization of data distribution in coresets. We showcase the results of various sampling methods for single class in the CIFAR10 dataset in Fig. 2. The features are obtained from ResNet18 network trained on the full training dataset and compressed to two dimensions using PCA ( 90% explained variance) for simpler visualization. As seen in Fig. 2(b), random sampling leads to relatively larger samples from the denser region of the distribution and consequently, higher percentage of easy samples feature in the coreset after 90% pruming. By optimizing for diversity only via facility location (Iyer et al., 2021) submodular optimization (Fig. 2(c)), the diversity of the coreset remains high but it is plagued with the samples are preferred. Alternatively, the use of graph-cut function with cosine similarity distance (Iyer et al., 2021) the information gain function results the slection of narrow sliver of data from the 2-D space (Fig. 2(d)). Moderate coresets (Xia et al., 2023) also sample from narrow area in the distribution, resulting in poor diversity, but slightly better balance between easy and difficult samples (Fig. 2(c)). Finally, with our proposed method, the diversity remains high and the distribution of difficulty scores the coreset is also balanced (Fig. 2(f)).
problem random sampling i.e. easier
E LIMITATIONS & LICENSE
E LIMITATIONS
Access to Full Dataset Pretrained Model. Similar to the many previous coreset selection methods, our method relies on model that has been pretrained or finetuned on the full dataset. We leverage the pretrained embeddings as well as the difficulty scores from this model. In doing so, we risk capturing the biases of the model. Further, one cannot use D PRUNING to create datasets from scratch and reduce annotation costs by avoiding redundant samples in the dataset. We note that an ideal data pruning method would not rely access the full dataset that it can be used for creating challenging and effective datasets in a cost-effectivv manner. Our experiments in self-supervised and unsupervised data selection show promising results in this direction.
19

---

Published as a conference paper at ICLR 2024
E.2 LICENSE
We will publicly release our code and models. We use standard licenses from the community and provide the following links the licenses for the datasets that we used in the project.
CIFARIO, CIFAR100: Other
Adversarial NLI:
Creative Commons
ImDB Reviews: Other
Counterfactual ImDB, NLI: Apache
DataComp: MIT
20


Reviews:
[{"review_id": "2P1l83oTdv", "reviewer": "Reviewer_DbMJ", "summary": "The $\\mathbb{D}^2$ PRUNING method presented in this paper demonstrates a novel approach for selecting the most useful data from large training sets (coresets) for deep learning model training. \n\nIt combines two key factors: data diversity and sample difficulty. The method represents the training dataset as a graph and uses a message-passing algorithm to update each data point's difficulty score by considering its neighbors. This process ensures a balance of diverse and challenging data in the selected coreset. \n\n$\\mathbb{D}^2$ PRUNING has shown to be effective in improving model performance, particularly for image classification and natural language processing tasks, and is especially useful at low-to-medium data pruning rates.", "questions": "1. The paper uses inconsistent numberings (A and then 2, 3) in section 1 which should be rectified.\n2. An important investigation aspect for this paper would be to demonstrate performance on very small values of selection ratios $k$ as discussed in (Guo et al, 2021) and perform more than 1 message passing (K-shot setting).\n3. The paper refers to additional information in the appendix section. It would greatly improve the readability of the paper if the authors point to exact section numbers in the appendix.\n4. It is unclear if the parameter $\\gamma$ mentioned in section 5.1 refers to $\\gamma_f$ or $\\gamma_r$. \n5. Although optional, including an algorithmic view of the proposed approach would be interesting to clarify how $\\mathbb{D}^2$-PRUNING fits into the training and evaluation process of deep-learning models.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper presents a novel approach - $\\mathbb{D}^2$-PRUNING, which balances both data diversity and difficulty, along with its applicability to both supervised and self-supervised learning contexts. This positions it as a valuable tool in the ongoing evolution of corset selection techniques for data efficient learning.\n2. The experiments are clear and the authors provide ablation experiments to support the theory and newly introduced hyper-parameters in the paper.\n3. It is commendable that the paper divulges into the NLP domain and demonstrates improved performance over existing methods in coreset selection.", "weaknesses": "1. The paper demonstrates very incremental gains in performance over State-of-the-Art method (like Ash et al., 2019).\n2. The experiments in section 5.1 do not compare $\\mathbb{D}^2$-PRUNING State-of-the-Art methods discussed in (Guo et al., 2021) such as GLISTER (Killamsetty et al., 2021), CRAIG (Mirzasoleiman et al., 2020), GRAD-MATCH (Killamsetty et al., 2021) etc.", "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": "", "extra_scores": {}}, {"review_id": "P813VS8hhv", "reviewer": "Reviewer_4iU9", "summary": "This paper starts by emphasizing the significance of maintaining a balance between the diversity and difficulty of samples used in data subset selection, for speeding up the training process. To this end, the authors initially illustrate instances in which diversity sampling can result in an excessive over-sampling (attributable to over-representation) from regions characterized by relatively low complexity. Following this, as shown in Figure~2, the authors introduce a graph-based algorithm designed to select training examples that maintain a balance between diversity and difficulty. The algorithm is based on message parsing on the constructed graph where each datapoint is a node. Subsequently, the paper provides experimental evidence in support of their proposed method, conducted across a range of datasets encompassing both vision and language domains, as well as their joint modality. The experimentation includes scenarios involving both supervised and self-supervised learning. The paper also addresses the interesting datacomp setting and evaluates its performance against the corresponding benchmarks, including VTAB and retrieval.", "questions": "- For the difficulty-based methods, in supervised settings, methods such as forgetting-event are clear that they use the learning dynamics. However, methods such as -- entropy, EL2N (which is similar to the norm of the gradient concerning bias term), and area under margin score, can be computed during any step of training. Therefore, does the paper consider the moving average of the dynamics (of some pre-trained models, for which they've assumed the access), or is it taken at the end of the training? In case it is moving average, I am okay with it, but if it is taken at the end of the training, then the training set methods like entropy/margin/EL2N can be very wrong in judging the hardness. \n\n\n- Can authors provide standard deviation or statistical analysis in cases where the second-best technique is very close? \n- For BADGE does the author use true labels instead of pseudo labels? BADGE was proposed in Active learning and hence it is important to make sure it doesn't have a disadvantage in supervised setting comparisons. \n- k and s_k are overloaded as expressions in the paragraph above equation 6. \n- What happens when one runs message parsing for more than one round? Can authors provide an experiment on that or justification? \n- Eq. 1 theta should rather me $\\theta^*(S')$ to show that it is a solution to the optimization.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A wide range of data modalities is considered which I particularly appreciate, unlike other papers in the community. Ablation is also done on the hyperparameters mentioned in the proposed algorithm, which include $\\gamma_r$, $\\gamma_f$ (kernel width), and the sparsity of the graph. The paper was pretty much straightforward and they mentioned that $D^2$ provides boosts under a low to medium \"pruning\" regime. Overall, I like the simplicity of writing.", "weaknesses": "I feel that the prime weakness of this work is from the angle of related works, and baselines. Highlighting the importance of balancing diversity and difficulty is not new, and indeed if one is using not well-tuned diversity selection methods, then they won't be able to give a full representation of the dataset (minor modes which are not outliers but are difficult). That being said, I need an explanation, and if possible, results on the following baselines --\n\nFor general supervised cases \n\n- CRAIG [1]\n- GLISTER (this paper has the same motivation as mentioned in Eq1) [2]\n- GradMatch [3]\n- Top-k method [4]: Another graph-based sampling that downweighs the contribution based on neighbors.\n- CREST (an extension of CRAIG) [5]\n\nA combination of submodularity with difficulty has been explored in the following -- \n\n- FASS (two-stage procedure for active learning, but a similar two-stage procedure can be considered here) [6]\n- A combination of submodularity and difficulty has been considered in CAL-SDS2 [7]\n- MCL (Combination of hardness and diversity for curriculum learning) [8]\n- DIHCL (another combination of hardness and diversity for curriculum learning) [9]\n\nMore recent works on diversity-based selection (for NLP) --\n- MILO [10]\n- INGENIOUS [11]  \n\nOn SSL: \n- See SAS [12] \n\nOn multimodality see T-MARS [13]\n\nConcluding thoughts: \nI believe the paper should discuss these works and should include some of them as baseline.  \n\nReferences\n- [1] Data-efficient Training of Machine Learning Models (ICML'20) \n- [2] GLISTER: Generalization-based Data Subset Selection for Efficient and Robust Learning (AAAI'21) \n- [3] GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training (ICML'21)\n- [4] SELECTIVE ANNOTATION MAKES LANGUAGE MODELS BETTER FEW-SHOT LEARNERS (ICLR'23)\n- [5] Towards Sustainable Learning: Coresets for Data-efficient Deep Learning (ICML'23)\n- [6] Submodularity in Data Subset Selection and Active Learning (ICML'15)\n- [7] Accelerating Batch Active Learning Using Continual Learning Techniques (TMLR/DMLR@ICML'23)\n- [8] Minimax Curriculum Learning: Machine Teaching with Desirable Difficulties and Scheduled Diversity (ICLR'18)\n- [9] Curriculum Learning by Dynamic Instance Hardness (NeurIPS'19) \n- [10] MILO: Model-Agnostic Subset Selection Framework for Efficient Model Training and Tuning \n- [11] INGENIOUS: Using Informative Data Subsets for Efficient Pre-Training of Language Models\n- [12] Data-Efficient Contrastive Self-supervised Learning: Most Beneficial Examples for Supervised Learning Contribute the Least (ICML'23)\n-  [13] T-MARS: Improving Visual Representations by Circumventing Text Feature Learning", "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": "", "extra_scores": {}}, {"review_id": "9ZGMHT5Gn8", "reviewer": "Reviewer_2S5F", "summary": "This work proposes a new data pruning model called D^2 pruning that balances diversity and difficulty via a message-passing algorithm.\nThey show the performance superiority of the proposed method on vision and NLP datasets with supervised and self-supervised variants.", "questions": "I think this work is also related but missed in discussion/comparison.\n\n[a] Active learning is a strong baseline for data subset selection. NeurIPS workshop, 2022", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- Clear presentation and easy-to-follow writing.\n- The algorithm is straightforward and easy-to-implement.\n- The evaluation is extensive, with many datasets in multiple tasks, and solid.", "weaknesses": "- No time complexity analysis. The proposed algorithm based on message-passing seems to take quite a lot of time. The author should provide the time-complexity analysis with the exact GPU time taken because a data pruning method that takes too long time is less practical.\n- No theoretical analysis. How this message-passing algorithm can guarantee better generalization than other baselines? Although the author provides some intuition (data pruning should consider both diversity and difficulty), why it should be achieved by the message-passing and how it can reduce the generalization error in Eq.(1) is missing.", "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": "", "extra_scores": {}}, {"review_id": "i1nhXrPT4p", "reviewer": "Reviewer_niHR", "summary": "This paper proposes to balance both difficulty and diversity in the data sampling process. The authors argue that difficulty and diversity have been independently optimized but should be optimized together. To this end, this work proposes a graph-based method, D^2 pruning, which builds the graph based on data diversity and uses message passing to get information difficulty.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors perform extensive experiments, on both vision and NLP datasets, and compare to a well-covered set of baseline. Empirical results appear to be promising.  The methodology itself also appears to be interesting and novel, to the best of my knowledge.", "weaknesses": "The authors use distance in embedding space to construct the near-neighbor graph. However, there is a lack of support for why distance in embedding space is a good indicator of diversity. For example, what if we use another model to generate the embedding? What’s the influence between feature level embedding versus final layer embedding? Similarly, the authors use the forgetting score as the difficulty indicator. There is no discussion on why the author choose forgetting score? What would be the influence of choosing another score, such as a consistency score or loss of an approximate model?", "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": "", "extra_scores": {}}, {"review_id": "6cFWqIygqX", "reviewer": "Reviewer_3E93", "summary": "This paper introduces a novel coreset selection algorithm called D2 pruning (Diversity-Difficulty pruning), which leverages undirected graphs and message passing to calculate difficulty score. The algorithm's primary goal is to tackle two important aspects: example difficulty and diversity within the selected subset of data points. D2 pruning works in the following way: 1. Graph Initialization: Nodes in graph G represent dataset examples and are connected to their k-closest neighbors in the embedding space. 2. Update difficulty score: Use message passing on the graph to update difficulty scores based on neighbor distance and difficulty.  3. Coreset Selection: Iteratively select balanced samples from high-density low-difficulty and low-density high-difficulty regions. Down-weight neighbors of selected samples to promote coreset diversity.", "questions": "1. How many iterations will the forward message passing phase have?\n\n2. What is the importance score in fig 2 (what metrics used)? \n\n3. It seems that $D^2$ can be combined with other metrics. Do you run an ablation study to see how $D^2$ performs with other importance scores?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors proposed a novel coreset selection algorithm that aims to unify the benefits of data diversity and data difficulty. The proposed method is intuitive.\n\n2. The proposed method is also evaluated on NLP datasets - lacked in prior work. \n\n3. The evaluation compares $D^2$ with various baselines and shows that $D^2$ achieves better or comparable performance than SOTA methods.\n\n4. The writing is good and easy to follow.", "weaknesses": "1. The performance improvement seems marginal. In most cases, the improvement is less than $1\\%$. \n\n2. With such performance differences, repeated evaluation can be suggested to mitigate the variance in the model training.\n\n3. $D^2$ introduces some additional hyper-parameter, which may increase the coreset selection cost.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)