Dataset Pruning: Reducing Training Data by Examining Generalization Influence
Authors: Shuo Yang
Zeke Xie
Hanyu Peng
Min Xu
Mingming Sun
Ping Li
Venue: ICLR 2023 poster (2023)

Abstract: The great success of deep learning heavily relies on increasingly larger training data, which comes at a price of huge computational and infrastructural costs. This poses crucial questions that, do all training data contribute to model's performance? How much does each individual training sample or a sub-training-set affect the model's generalization, and how to construct the smallest subset from the entire training data as a proxy training set without significantly sacrificing the model's performance? To answer these, we propose dataset pruning, an optimization-based sample selection method that can (1) examine the influence of removing a particular set of training samples on model's generalization ability with theoretical guarantee, and (2) construct the smallest subset of training data that yields strictly constrained generalization gap. The empirically observed generalization gap of dataset pruning is substantially consistent with our theoretical expectations. Furthermore, the proposed method prunes 40% training examples on the CIFAR-10 dataset, halves the convergence time with only 1.3% test accuracy decrease, which is superior to previous score-based sample selection methods.

Published as a conference paper at ICLR 2023
DATASET PRUNING: REDUCING TRAINING DATA BY EXAMINING GENERALIZATION INFLUENCE
Shuo Yang' Zeke Xie?
Hanyu Peng²
Min Xu'
Mingming Sun? Ping Li
1 Schooo of Electrical and Data Engineering, University of Technology Sydney
2 Cognitive Computing Lab, Baidu Research
ABSTRACT
The great success of deep learning heavily relies on increasingly larger training data, which comes at price of huge computational and infrastructural costs. This poses crucial questions that, do all training data contribute to model's performance? How much does each individual training sample or a sub-training-set affect the model's generalization, and how to construct the smallest subset from the entire training data as a proxy training set without significantly sacrificing the model's s performance? To answer these, we propose dataset pruming, optimization- based sample selection method that can (1) examine the influence of removing particular set of training samples on model's generalization ability with theoretical guarantee, and (2) construct the smallest subset of training data that yields strictly constrained generalization gap. The empirically observed generalization gap of dataset pruning is substantially consistent with our theoretical expectations. Furthermore, the proposed method prunes 40% training examples on the CIFAR-10 10 dataset, halves the convergence time with only 1.3% test accuracy decrease, which is superior to previous score-based sample selection methods.
INTRODUCTION
The great advances in deep learning over the past decades have been powered by ever-bigger models crunching ever-bigger amounts of data. However, this success comes at a price of huge computational and infrastructural costs for network training, network inference, hyper-parameter tuning, and model architecture search. While lots of research efforts seek reduce the network inference cost by pruning redundant parameters Blalock et al. (2020); Liu et al. (2018) 20:18); Molchanov et al. (2019), scant attention has been paid to the data redundant problem, which is crucial for network training and parameter tuning efficiency.
Investigating the data redundant problem not only helps to improve the training efficiency, but also helps understand the representation ability of small data and how many training samples is required and sufficient for a learning system. Previous literatures on subset selection try to sort and select fraction of training data according scalar score computed based some criterions, such as the distance to class center Welling (2009); Rebuffi et al. (2017); Castro et al. (2018): Belouadah & Popescu (2020). the distance other selected examples Wolf 2201);; Sencr & Savarese (2018b). the forgetting score Toneva et al. (2019)), and the gradient norm Paul et al. (202I). However, these methods are (a) heuristic and lack of theoretically guaranteed generalization for the selected data, also (b) discard the joint effect, i.e. the norm of averaged gradient vector of two high-gradient-noon samples could be zero if the direction of these two samples' gradient is opposite.
To go beyond these limitations, natural ask is, how much does a combination of particular training examples contribute to the model's generalization ability? However, simply evaluating the test performance drop caused by removing each possible subset is not acceptable. Because it requires to re-train the model for 2n times given a dataset with size n. Therefore, the key challenges of dataset pruning (1) how efficiently estimate the generalization influence of all possible subsets without iteratively re- re-training the model, and (2) how to identify the smallest subset of the original training data with strictly constrained generalization gap.
In this work, we present an optimization based dataset pruning method that can identify the largest redundant subset from the entire training dataset with (a) theoretically guaranteed generalization gap

---

Published as a conference paper at ICLR 2023
and (b) consideration of the joint influence of all collected data. Specifically, define the parameter influence of a training example as the model's parameter change caused by omitting the example from training. The parameter influence can be linearly approximated without traininng the model by Influence Function Koh & Liang] 2017a). Then, we formulate the subset selection as a constrained discrete optimization problem with an objective of maximizing the number of collected samples, and a constraint of penalizing the network parameter change caused by removing the collected subset within given threshold e. We then conduct extensive theoretical and empirical analysis show that the generalization gap of the proposed dataset pruning can be upper bounded by the pre-defined threshold c. Superior to previous score-based sample selection methods, our proposed method prunes 40% training examples in CIFAR-10 10 Krizhevsky (2009), halves the convergence time, and achieves only 1.3% test accuracy drop. Before delving into details, we summarize our contributions as below:
This paper proposes a dataset pruning problem, which extends the sample selection problem from cardinality constraint to generalization constraint. Specifically, previous sample selection methods find a data subset with fixed size budget and try to improve their performance, while dataset pruning tries to identify the smallest subset that satisfies the expected generalization ability.
This paper proposes to leverage the influence function to approximate the network parameter change caused by omitting each individual training example. Then an optimization- barrrattoo--addddddd method is proposed to identify the largest subset that satisfies the expected parameter change.
We prove that the generalization gap caused by removing the identified subset can be up- up-bounded by the network parameter change that was strictly constrained during the dataset pruning proce- dure. The observed empirical result is substantially consistent with our theoretical expectation.
The experimental results on dataset pruning and neural architecture search (NAS) demonstrate that the proposed dataset pruning method is extremely effective on improving the network training and architecture search efficiency.
The rest of this paper is organized as follows. In Section. 2 we briefly review existing sample selection and dataset condensation research, where we will discuss the major differences between our proposed dataset pruning and previous methods. In Section. 3 we present the formal definition of the dataset pruning problem. In Section. and Section. [5 our optimization-base
dataset pruning we conduct extensive experiments
method and its generalization bound are introduced. In Section. 6 to verify the validity of the theoretical result and the effectiveness of dataset pruning. Finally, in we conclude our paper.
Section. 7
2 RELATED WORKS
Dataset pruning is orthogonal to few-shot learning Finn et al. (2017): Chen et al. (2019); Zhang al.] (2020); Yang et al. a222aab Few-shot learning aims at improving the performance given limited training data, while dataset pruning aims at reducing the training data without hurting the performance much.
(2017); p Vinyals et al. : Snell et al.
Dataset pruning is closely related to the data selection methods, which try to identify the most representative training samples. Classical data selection methods Aggawal et al. (2004); Har-Peeedd & Mazumdar (2004): Feldman et al. (2013) focus on clustering problems. Recently, more and more data selection methods have been proposed in continual learning Rebuttii et al. (017); Toneva et al. (2019b): Castro et al. (2018); Aljundi et al. (2119) and active learning Sener & Savarese (2018a) to identify which example needs be stored or labeled. The data selection methods typically rely on pre-defined criterion to compute a scalur score for each training example, e.g. the RRebfffi compactness|Ree RRebutt et al.) (2017): Castro al. (2018), diversity (Sener & Savarese (20T8b): (Aljundi] et al. (2019), forgetfulness Toneva et al. (2019b), the gradient norm Paul et al. (2221). then rank and select the training data according to the computed score. However, these methods are heuristic and lack of generalization guarantee, they also discard the influence interaction between the collected samples. Our proposed dataset pruning method overcomes these shortcomings.
Another line of works on reducing the training data is dataset distillation Wang al. (2018): 8) Such et al. (2020); Sucholutsky & Schonlau (2019); [Bohdal et al. (2020); Nguyen et al. (202 a b): Cazenavette al. 2022) or dataset condensation Zhao et al. 2021 Zhhao & Bilen (2021a b): Wang al. (2022):
2

---

Published as a conference paper at ICLR 2023
Jin et al. (2021 2022). This series of works focus synthesizing small but informative dataset as an alternative to the original large dataset. For example, Dataset Distillation Wang et al. (2018) try to learn the synthetic dataset by directly minimizing the classification loss on the real training data of the neural networks trained on the synthetic data. Cazenavette et al. (2022) proposed to learn the synthetie images by matching the training trajectories. /Zhao et al. al.] ( Zhao & Bilen (2021 b) proposed to learn the synthetic images by matching the gradients and features, However, due to the computational power limitation, these methods usually only synthesize an extremely small number of examples (e.g. 50 images per class) and the performance is far from satisfactory. Therefore, the performances of dataset distillation and dataset pruning are not directly comparable.
Our method is inspired by Influence Function Koh & Liang (017a)) in statistical machine learning. Removing training example from the training dataset and not damage the generalization indicates that the example has small influence on the expected test loss. Earlier works focused on studying the influence of removing training points from linear models, and later works extended this to more general models Hampel et al. (2011;; Cook (1986); Thomas & Cook (1990;; Chatterjee & Hadi (1986); Wei et al. (1998). Liu et al. (2014) used influence functions to study model robustness and to to fast cross- validation in kernel methods. Kabra et al. (2015) defined a different notion of influence that is specialized to finite hypothesis classes. Koh & Liang (2017a) studied the influence of weighting an example model's parameters. [Borsos et al. (2020) proposes to construct coreset by learning a per-sample weight score, the proposed selection rule eventually converge to the formulation of influence function Koh Liang (2017b). But different with our work, Borsos et al. (2020) did not directly leverage the influence function to select examples and cannot guarantee the generalization of the selected examples.
3 PROBLEM DEFINITION
Given a large-scale dataset D = { [1. .......2. 2n containing n training points where 2; = (z,, Ve) E X' x Vi, X' is the input space and }/ is the label space. The goal of dataset pruning is to identify set of redundant training samples from as many as possible and remove them to reduce the training cost. The identified redundant subset, ò = , {m} and c D, should have a minimal impact on the learned model, i.e. the test performances of the models learned the training sets before and after pruning should be very close, as described below:
E2,,())L(2,0) ~ ( ((3
where P(D) is the data distribution, L. is the loss function, and and 0 O_p are the empiri- cal risk minimizers on the training set D before and after pruning D. respectively, i.e., θ = Σ E L(z,, 0). Considering the neural network is locally smooth function Rifai et al. 2012) Goodfellow et al. (2014); Zhao et al. (2021), similar weights (0 = 0) imply similar mappings in local neighborhood and thus generalization performance. Therefore, we can achieve Eq. by obtaining 0_6 that is very close
arg mingge 1 Ex,eD L(z,,)) 0) and 0_p = arg mingge
to Ô (the distance between 0_ D and 0 is smaller than given very small value e). To this end, we first define the dataset pruning problem on the perspective of model parameter change, we will later provide the theoretical evidence that the generalization gap in Eq. [ can be upper bounded by the parameter change in Section.
Definition (c-redundant subset.). Given a dataset D = {zi...., 2n} containing n. training points where = (I B1) E X x V, considering D is a subset of D where D = {ā....., ......,,m 2mh
D C D. We say D is an e-redundant subset of DD is 0 - S where 0_ = arg minego n-m EXEDYD Liz, 0) and θ arg minage 1 EnED L(z,, 0), then write D as D...
Dataset Pruning: Given dataset D, dataset pruning aims at finding its largest e-redundant subset Dmmor ie.,, VD. C DD (Dmar] 2 [Dz], so that the pruned dataset can be constructed as D D D.Daaaz
3

---

Published as a conference paper at ICLR 2023
4 METHOD
||0 |
To achieve the goal of dataset pruning, we need to evaluate the model's parameter change caused by removing each possible subset of D. However, it is impossible to re-train the model for 2n times obtain Dieer for given dataset ID with size In this section, propose efficiently approximate the Dmaz without the need re-train the model.
4.1 PARAMETER INFLUENCE ESTIMATION
We start from studying the model parameter change of removing each single training sample = from the training set D. The change can be formally written as Ô_ 0, where 0_2 = arg mingge - L L.,., T. 0). Estimating the parameter change for each training exam- ple by re-training the model for n times is also unacceptable time-consuming, because is usually
on the order of tens or even hundreds of thousands.
Alternatively, the researches of Influence Function Cook 1977); Cook & Weisberg 1980); Cook (1986); Cook & Weisberg (1982); Koh Liang (20 provide us an accurate and fast estimation of the parameter change caused by weighting example Z was weighted by small during training. the empirical risk minimizer can be written as 0;.- arg mingee 1 -..ep L (2;, + 5L (z, 0). Assigning a
example for training. Considering training
to 6 is equivalent to removing the training example z. Then, the influence of weighting 2 on the parameters is given by
dd
I Iaraam (2) =
V
- VoL(2,0)
(2)
d6
6=0
where - VOL(Z, 0) is the Hessian and positive definite by assumption, Iparam (2) R.N N is the number of network parameters. The proof of Eq.equation can be found in Koh &
Liang (017a). Then, we can linearly approximate the parameter change due to removing & without
retraining the model by computing p_ 0 ~ - Iprramm (z) = =.. H VoL 0). Similarly, we can
approximate the parameter change caused by removing a subset D by accumulating the parameter change of removing each example, 0_ 0 ~ Σn,e - Iparam (z+) Σn,e o VoL 0). The accumulated individual influence can accurately reflect the influence of removing group of data, as proved in Koh et al. (2019).
4.2 DATASET PRUNING AS DISCRETE OPTIMIZATION
Combining definition I and the parameter influence function (Eq. equation 2 it is easy to derive
that if the parameter influence of subset D satisfies Σn
2 n Iaraam (z:) c, then it is
e-redundant subset of D. Denote = I (21). ... n I (zn)) }. to find the largest Σ CDmes , I(x) and (2)
c-redundant subset Dinaz that satisfies the conditions of (1)
[D.| simultaneously, we formulate the generalization-guaaane dataset pruning discrete optimization problem as below (a):
VD. C D, Dimaa
(a) generalization-eee -uaraittedd pruning:
(b) cardinality-guaranii pruning:
minimize
maximize
W
(3)
subject to
Σ 1=1
W
(4)
subject
SWTs|| Sc W (0, 1]"
W E 1)
where W is a discrete variable that is needed to be optimized. For each dimension i, W; = 1 indicates the training sample z; is selected into Dmaar, while W; = 0 indicates the training sample is not pruned. After solving W in Eq 3 the largest e-redundant subset can be constructed as Dmmo (2//22, E D. W. 1). For some scenarios when need to specify the removed subset
4

---

Published as a conference paper at ICLR 2023
Algorithm I Generalization guaranteed dataset pruning.
Require: Dataset D
{21,.... 2
Require: Random initialized network 0;
Require: Expected generalization drop e;
1: 0 arg mingge 1 π D..ED (zz, 0);
//compute ERM D
2: Initialize S = Ø;
3: for 1, ..... do
4: 8; = n I (2i) n 7 Vol.,,,,
//store the parameter influence of each example
5: end for
6: Initialize W 1)";
7: Solve the following problem to get W:
maximize
Σ W
//maximize the subset size
subject
| Se
/guarantee the generalization drop
W WE& 10,1]"
8: Construct the largest c-redundant subset D.ne= = 22/V2 E D, W;
9: return Pruned dataset: D = D Dimas
size and want to minimize their influence parameter change, we provide gardinalit-guuaranter dataset pruning in Eq.
5 GENERALIZATION ANALYSIS
In this section, we theoretically formulate the generalization guarantee of the minimizer given by the pruned dataset. Our theoretical analysis suggests that the proposed dataset pruming method have relatively tight upper bound on the expected test loss, given small enough c.
For simplicity, we first assume that we prune only one training sample (namely, 5 one- dimensional). Following the classical results, we may write the influence function of the test loss
dL. Etestt, 0s.5)
dds.=
Tooss (asas(tee (Eeest, 2)
VeLeeetest 8)
VoL T Iparam (2)
d8
dō
8=0
1=
(5)
which indicates the first-order derivative of the test loss (2ess 02.6) with respect to d.
We may easily generalize the theoretical analysis the case that prunes m training samples, if let 8 be m-dimennsinnl vector (-1... .... }) and é D. Then we may write the multi milti-dimensional form of the influence function of the test loss
ddg.e
Tooss (Ztost, D) V
(Z (Ztest, 0)
(Iooss (Iross(2test; 21), ... Iiose (Zrest Em)),
(6)
dō
6=(00....0)
which is an N x m matrix and N indicates the number of parameters.
We define the expected test loss the data distribution P(D) L(() E ( L (#test, 0)
and define the generalization gap due to dataset pruning L(θ b) L(+)). By using the influence function of the test loss (Singh al. (202I), we obtain Theorem which formulates the upper bound of the generalization gap.
Theorem (Generalization Gap of Dataset Pruning). Suppose that the original dataset is D and
the pruned dataset is D mm If Σt. Iparam (24) S 6, we have the upper bound of the

---

Published as a conference paper at ICLR 2023
generalization gap
sup - = 0 0
m n2
Proof. We express the test loss 0 0_D using the first-order Taylor approximation as
( Ztsst s(0_)))
(restt S(0)) + (Ztest D (111))),
(8)
where the last term ( is usually ignorable in practice, because ||ō|| m is very small for popular benchmark datasets. The same approximation is also used in related papers which used influence function for generalization analysis Singh et al.) (202T). According to Equation equation g have
n
C(0 [(0_b) L(0) =E Bust P(D) [Tose (Zeest D)jō
(9)
E Exsa P(D) [Tnnss Zzeest 2:)
(10)
n
9,ED
E
B
V VoL(2eest T
Σ
H VoL
(11)
2ED
< |Voc(0) 12
Σ
Iparam (2i)
(12)
MED
<
(13)
where the first inequality is the Cauchy-Schward inequality, the second inequality is based on the algorithmic guarantee that Σ EeED Iparam (a)) (anrmam@)// S in Eq. equation 3. and is hyperparameter. Given the second-order Taylor term, finally, obtain the upper bound of the expected loss as
- = O + m. supic(0_s) [(0)
(14)
n?
The proof is complete.
Theorem I demonstrates that, if we hope to effectively decrease the upper bound of the generalization gap due dataset pruning, should focus on constraining even directly minimizing e. The basic idea of the proposed ceiiiization-based dataset pruning method exactly aims at penalizing e via discrete optimization, shown Eq. and Eq.
Moreover, our empirical results in the following section successfully verify the estimated general- ization gap. The estimated generalization gap the proposed optimization- approximately has the order of magnitude as (110-3) on CIFAR- 10 and CIFAR- 100, which is significantly smaller the estimated generalization gap of random dataset pruning by more than one order of magnitude.
dataset pruning
6 EXPERIMENT
In the following paragraph, we conduct experiments to verify the validity of the theoretical results and the effectiveness of the proposed dataset pruning method. In Section. 6.1] we introduce all experimental details. Section. 6.2 we empirically verify the validity of the Theorem. T In Section. 6.3 and Section. 6.4. compare method with several baseline methods dataset pruning performance and cross-architecture generalization. Finally, in Section. 6.3 we show the proposed dataset pruning method is extremely effective improving the training efficiency.

---

Published as a conference paper at ICLR 2023
CIFAR1O
CIFARD00
iny-ImageNet
30
6C
Optimization
Optivization
40
Optim bazed
vlJerce scre
ieluence sore
Hiuunn scare
Torgetting score
Fargeting score
Forgezing score
112hoarem
67
Grahd score
Grahd score
Cruht soon
2/
Pruning ratio
Pruning ratio
Pruning ratio
Figure I: We compare our proposed optimization- dataset pruning method with several sample- selection baselines. Our optimization- based pruning method considers the 'group effect' of pruned examples and exhibits superior performance, especially when the pruning ratio is high.
6.1 EXPERIMENT SETUP AND IMPLEMENTATION DETAILS
We evaluate dataset pruning methods on CIFAR1O. CIFAR 100 Krizhevsky (2099), and TinyIma- geNet [e & Yang (015) datasets. CIFARIO and CIFAR 100 contains 50,000 training examples from 10 and T00 categories, respectively. TinylmageNet is a larger dataset contains 100,000 training examples from 200 categories. We verify the cross-architecture generalization of the pruned dataset on three popular deep neural networks with different complexity, e.g., SqueezeNett Hu et al. (2018) (1.25M parameters), ResNet18 He et al. (2016) (11.69M parameters), and ResNet50 He al. (2016) (25.56M parameters). All apper-parameters and experimental settings of training before and after dataset pruning were controlled to the same. Specifically, in experiments, we train the model for 200 epochs with a batch size of 128, a learning rate of 0.01 with cosine annealing learning rate decay strategy, SGD optimizer with the momentum of 0.9 and weight decay of Se-4, data augmentation of random crop and random horizontal flip. In Eq. 2 calculate the Hessian matrix inverse by using seconder-order optimization trick Agarwal et al. (2016) which can significantly boost the Hessian matrix inverse estimation time. To further improve the estimation efficiency, we only calculate parameter influence in Eq. 2 for the last linear layer. In Eq. [3] and Eq. 4 we solve the discrete optimization problem using simulated annealing Van Laarhoven & Aarts 1987), which a popular heuristic algorithm for solving complex discrete optimization problem in a given time budget.
6.2 THEORETICAL ANALYSIS VERIFICATION
Our proposed optimization-basee dataset pruning method tries to collect the smallest subset by straining the parameter influence c. In Theorem. [ demonstrate that the generalization gap of dataset
0.5
random, e/n
random, c(ô z()) ours, e/n
0.4
ours, c( c(0)
pruning can be upper-bounded by O + n² The term of m can be simply ignored since usually has a much smaller magnitude than f. To verify the valid- ity of the generalization guarantee of dataset pruning,
0.1
we compare the empirically observed test loss gap be-
fore and after dataset pruning L(O () L()) and our theoretical expectation f. in Fig.
2 can be clearly observed that the actual generalization gap is highly consistent with our theoretical prediction. We can also observe that there is a strong correlation between the pruned dataset generalization and c, therefore Eq, ef- fectively guarantees the generalization of dataset prun- ing by constraining e. Compared with random pruning, our proposed optimization-basee dataset pruning ex- hibits much smaller and better generalization.
Pruning size m
Figure 2: The comparison of empirically ob- served generalization gap and our theoretical expectation in Theorem. I We ignore the term of m m/n? since it has much smaller mag- nitude with c/n.
6.3 DATASET PRUNING
In the previous section, we motivated the optimization-bused dataset pruning method by constraining directly minimizing the network parameter influence of selected data subset. The theoretical
7

---

Published as a conference paper at ICLR 2023
SENet - ResNet18
SENet - ResNet50
ResNet18 ResNet50
30
Opinsxtlanbaad
90
Opinzatlonbuud
50
Optimiasiin- bases
Inflance score
Infunnee-scor
idluene-ssoee
Porgellinssore
Pergelingsoree
Fergeting score
66
E12h-acom
lindrr
Hlerzing
11
10%
Pruning ratio
Pruning ratio
Pruning ratio
Figure 3: To evaluate the auseen-architectume generalization of the pruned dataset, we prune the CIFARIO dataset using a relatively small network and then train a larger network on the pruned dataset. We consider three networks from two families with different parameter complexity, SENet (1.25M parameters), ResNet18 (11.69M parameters), and ResNet50 (25.56M parameters). The results indicate that the dataset pruned by small networks can generalize well to large networks.
result and the empirical evidence show that constraining parameter influence can effectively bound the generalization gap of the pruned dataset. In this section, we evaluate the proposed optimization- based dataset pruning method empirically. We show that the test accuracy of network trained on the pruned dataset is comparable to the test accuracy of the network trained on the whole dataset, and is competitive with other baseline methods.
We prune CIFARIO, 10, CIFAR 10 Krizhevsky (2099) and TinyImageNer & Yang 2015) using a random initialized ResNet50 network He et al. (2016). We compare our proposed method with the following baselines, (a) Random pruning. which selects an expected number of training examples randomly. (b) Herding Welling 2009), which selects expected number of training examples that are closest to the cluster center of each class. (c) Forgetting Toneva et al. (2019b). which selects training examples that are easy to be forgotten. (d) GraNd Paul et al. (2021), which selects training examples with larger loss gradient norms. (e) EL2N Paul et al. (2021) which selects training examples with larger norms of the error vector that is the predicted class probabilities minus one-hot label encoding. (f) Influence- sccren Koh& & Liang (2017a), which selects training examples with high norms of the influence function in Eq. 2 without considering the "group effect'. To make our method comparable to dataset
those cardinality-based pruning baselines, we pruned datasets using the cardinality-guaran pruning as in Eq. After dataset pruming and selecting a training subset, we obtain the test accuracy by retraining
random initialized ResNet50 network only the pruned dataset. The retraining settings of all methods are controlled to be the same. The experimental results are shown in Fig. In Fig. [ our method consistently surpasses all baseline methods. Among all baseline methods, the forgetting and EL2N methods achieve very close performance to ours when the pruning ratio is small, while the performance gap increases along with the increase of the pruning ratio. The influence-score. as direct baseline of our method, also performs poorly compared to our optimization-banl based method. This is because all these baseline methods are cassed they prune training examples by removing the lowest-score examples without considering the influence iteractions between high-score examples and low-score examples. The influence of combination of high-score examples may be minor, and vice versa. Our method overcomes this issue by considering the influence of a subset rather than each individual example, by a designed optimization process. The consideration of the group effect make method outperforms baselines methods, especially when the pruning ratio is high.
6.4 UNSEEN ARCHITECTURE GENERALIZATION
We conduct experiments to verify the pruned dataset can generalize well to those unknown or larger network architectures that are inaccessible during dataset pruning. To this end, we use a smaller network to prune the dataset and further use the pruned dataset to train larger network architectures. As shown in Fig. 3 we evaluate the CIFAR 10 pruned by SENet Hu et al. (2018) on two unknown and larger architectures, i.e., ResNet18 He et al. (016)) and ResNet50 He et al. (2016). SENet contains 1.25 million parameters, ResNet18 contains 11.69 parameters, and ResNet50 contains 25.56 parameters. The experimental results show that the pruned dataset has a good generalization on network architectures that are unknown during dataset pruning. This indicates that the pruned dataset can be used in a wide range of applications regardless of specific network architecture. In addition, the results also indicate that we can prune the dataset using small network and the pruned dataset
8

---

Published as a conference paper at ICLR 2023
generalize to larger network architectures well. These two conclusions make dataset pruning proper technique to reduce the time consumption of neural architecture search (NAS).
6.5 DATASET PRUNING IMPROVES THE TRAINING EFFICIENCY.
The pruned dataset significantly improve the training efficiency while maintaining the perfor- mance, as shown in Fig. Therefore, the proposed dataset pruning benefits when one needs to train many trails the same dataset. One such application is neural network search (NAS) Zoph al. (2018) which aims at searching a network architecture that can achieve the best performance for a specific dataset. A potential powerful tool to accelerate the NAS by searching architectures on the smaller pruned dataset, if the pruned dataset has the same ability of identifying the best network to the original dataset.
We construct 720 ConvNets searching space with dif- ferent depth, width, pooling, activation and normalization layers. We train all these 720 models on the whole CI- FARIO training set and four smaller proxy datasets that are constructed by random, herding Welling (2009), for-
1800, 98.8)
15.0.95.11
Test acc. (%)
getting Toneva et al. (2019b), and our proposed dataset pruning method. All the four proxy datasets contain only 100 images per class. We train all models with 100 epochs. The proxy dataset contains 1000 images in total, which cupies 2% storage cost than training on the whole dataset.
5
X0.39
X0.56
500
1005
1500
2000
2500
3000
3500
Time (s)
Table I reports (a) the average test performance of the best selected architectures trained on the whole dataset, (b) the Spearmen's 's rank correlation coefficient between the validation accuracies obtained by training the selected top 10 models on the proxy dataset and the whole dataset, (c) time of training 720 architectures on a Tesla V100 GPU, and (d) the memory cost. Table. [ shows that searching 720 architectures on the whole dataset raises huge timing cost. Randomly selecting 2% dataset to perform the archi- tecture search can decrease the searching time from 3029 minutes to 113 minutes, but the searched architecture achieves much lower performance when trained on the whole dataset, making it far from the best architecture. Compared with baselines, our proposed dataset pruning method achieves the best performance (the closest one to that of the whole dataset) and significantly reduces the searching time (3% of the whole dataset).
Figure 4: Dataset pruning significantly improves the training efficiency with mi- nor performance scarification. When pruning 40% training examples, the con- vergence time is nearly halved with only 1.3% test accuracy drop. The pruned dataset can be used to tune hyper- parameters and network architectures to reduce the searching time.
Random
Herding
Forgetting
Ours
Whole Datasct
Performance (%)
79.4
80.1
82.5
85.7
85.9
Correlation
0.21
0.23
0.79
0.94
1.00
Time cost (min)
113
113
113
113
3029
Storage (imgs)
103
103
103
103
x 10
Table 1: Neural architecture search on proxy-sets and whole dataset. The search space is 720 ConvNets. We do experiments on CIFAR10 10 with 100 images/class proxy dataset selected by random, herding, forgetting, and our proposed optimization-base dataset pruning. The network architecture selected by our pruned dataset achieves very close performance to the upper-bound.
7 CONCLUSION
This paper proposes a problem of dataset prunning, which aims at removing redundant training examples with minor impact on model's performance. By theoretically examining the influence of removing particular subset of training examples on network's 's parameter, this paper proposes to model the sample selection procedure as a constrained discrete optimization problem. During the sample selection, we constrain the network parameter change while maximize the number of collected samples. The collected training examples can then be removed from the training set. The extensive theoretical and empirical studies demonstrate that the proposed optimization- baaedd dataset pruning method is extremely effective on improving the training efficiency while maintaining the model's generalization ability.

---

Published as a conference paper at ICLR 2023
REFERENCES
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization in linear time. stat, 1050:15, 2016.
Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Approximating extent measures of points. Journal of the ACM (JACM), 51(4):606-635 2004.
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. Advances in Neural Information Processing Systems, pp. 11816- 11825, 2019.
Eden Belouadah and Adrian Popescu. Scail: Classifier weights scaling for class incremental learning. In The IEEE Winter Conference on Applications of Computer Vision, 2020.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2: 129-1146, 2020.
Ondrej Bohdal, Yongxin Yang, and Timothy Hospedales. Flexible dataset distillation: Learn labels instead of images. Neural Information Processing Systems Workshop, 2020.
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in Neural Information Processing Systems, 93:14879-1489) 2020.
Francisco M Castro, Manuel Marín-Jiméne Nicolás Guil, Cordelia Schmid, and Karteek Alahari. End-to-end incremental learning. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 233-248, 2018.
George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei Efros, and Jun-Yan Zhu. Dataset distillation by matching training trajectories. arXiv preprint arXiv:2203. /9322, 2022.
Samprit Chatterjee and Ali S Hadi. Influential observations, high leverage points, and outliers in linear regression. Statistical science, 1986.
Wei- Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. closer look at few-shot classification. In ICLR, 2019.
R Dennis Cook. Detection of influential observation in linear regression. Technometrics, 19(1):15-18. 1977.
R Dennis Cook. Assessment of local influence. Journal of the Royal Statistical Society: Series B (Methodological), 48(2):133-153: 1986.
Dennis Cook and Sanford Weisberg. Characterizations of empirical influence function for detecting influential cases in regression. Technometrics, 22(4):495-55) 4088 1980.
R Dennis Cook and Sanford Weisberg. Residuals and influence in regression. New York: Chapman and Hall, 1982.
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea and projective clustering. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithmss, pp. 1434-1453. SIAM, 2013.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. ICML, 2017.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 4rXiv: 2014.
Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel. Robust statistics: the approach based on influence functions. John Wiley Sons, 2011.
Sariel Har-Peled and Soham Mazumdar, On coresets for k-means and k-median clustering. In Proceedings of the thitty-sixth annual ACM symposium Theory of computing, 2004.
10

---

Published as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excitation networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. ICLR, 2021.
Wei Jin, Xianfeng Tang. Haoming Jiang, Zheng Li, Danqing Zhang. Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 720-730, 2022.
Mayank Kabra, Alice Robic, and Kristin Branson. Understanding classifier errors by examining influential neighbors. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2015.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894. PMLR, 2017a
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning-Volume Volume 70, pp. 1885-1894. JMLR. org, 2017b.
Pang Wei W Koh, Kai-Siang Ang, Hubert Teo, and Percy S Liang. On the accuracy of influence functions for measuring group effects. Advances in neural information processing systems, 32, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 23/N, 7(7):3, 2015.
Yong Liu, Shali Jiang, and Shizhong Liao. Efficient approximation cross-validation for kernel methods using bouligand influence function. In International Conference Machine Learning. PMLR, 2014.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint 1rXiv:1810.0553 2018.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, Iuri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 11264-11233 11222, 2019.
Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. Dataset meta-learning from kernel-ridge regression. In International Conference Learning Representations, 2021a. URL htttps //openreview. net wtwt:/oorrrmmdde-rrrrrrr
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. arXiv preprint arXiv:2107.13334 2021b.
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, 2021.
Sylvestre-AINe Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.
Salah Rifai, Yoshua Bengio, Yann Dauphin, and Pascal Vincent. A generative process for sampling contractive auto-encoders. arXiv preprint 1206.62006.444. 2012.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. ICLR, 2018a.
11

---

Published as a conference paper at ICLR 2023
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018b.
Sidak Pal Singh, Aurelien Lucchi, Thomas Hofmann, and Bernhard Schölkopf. Phenomenology of double descent in finite-width neural networks. In International Conference on Learning Representations, 2021.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in neural information processing systems, pp. 4077-4087, 2017.
Felipe Petroski Such, Aditya Rawal, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Generative teaching networks: Accelerating neural architecture search by learning to generate synthetic training data. International Conference on Machine Learning (ICML), 2020.
Ilia Sucholutsky and Matthias Schonlau. Soft-label dataset distillation and text dataset distillation. arXiv preprint arviv: (rXxv:991000255/// 2019.
William Thomas and R Dennis Cook. Assessing influence on predictions from generalized linear models. Technometrics, 1990.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning. ICLR, 2019a.
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. ICLR, 2019b.
Peter JM Van Laarhoven and Emile HL Aarts. Simulated annealing. In Simulated annealing: Theory and applications. pp- 7-15. Springer, 1987.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In NeurlPS, 2016.
Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang. Shuo Wang. Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. arXiv preprint arXiv:2203.0153/ 2022.
Tongzhou Wang, Jun- Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint arXiv:1811.109932 2018
Bo-Cheng Wei, Yue-Qing Hu, and Wing-Kam faa Fung. Generalized leverage and its applications. Scandinavian Journal of statistics, 1998.
Max Welling. Herding dynamical weights leam. In Proceedings of the 26th Annual International Conference on Machine Learning, 1121-1128. ACM, 2009.
G W Wolf. Facility location: concepts, models, algorithms and case studies. 2011.
Shuo Yang, Lu Liu, and Min Xu. Free lunch for few-shot learning: Distribution calibration. In ICLR, 2021a.
Shuo Yang, Songhua Wu, Tongliang Liu, and Min Xu. Bridging the gap between few-shot and many- shot learning via distribution calibration. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021b.
Chi Zhang, Yujun Cai, Guosheng Lin, and Chunhua Shen. Deepemd: Few-shot image classification with differentiable earth mover's distance and structured classifiers. In CVPR, 2020.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In International Conference on Machine Learning, 2021a.
Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. arXiv preprint arXiv:21 1 10.04181. 2021b.
12

---

Published as a conference paper at ICLR 2023
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2021. URL URLpatpp:://ppereeviee
net /utt/Eon
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018.
13


Reviews:
[{"review_id": "si-U7Tt7lLq", "reviewer": "Reviewer_F3Cs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "**Overall Summary** This paper presents an approach aims to selecting a subset of training data that (1) makes training more computationally efficient while (2) incurring little-to-no loss in accuracy. The proposed approach is analyzed in terms of its generalization performance in addition to computational requirements.\n\n**Methodological Summary** The proposed method uses influence functions to select which datapoints to keep and which to prune in the given training dataset.\n\n**Empirical Summary** The authors perform extensive empirical analysis that compares to baseline methods (herding, forgetting, random), across architectures, and across training settings (standard training, architecture search).", "summary_of_the_review": "This paper presents a simple and effective method for dataset pruning using influence functions. There are effective empirical results, but questions about depth of methodological contribution and clarity around some technical details of the approach.", "strength_and_weaknesses": "This paper presents an interesting, clear, and effectively simple (in a good way) idea for dataset pruning. Here are a summary of strengths and weaknesses\n\n**Strengths**\n1. **Effective empirical results** - The authors demonstrate on CIFAR10 & CIFAR100 the effectiveness of their approach. It would appear to have clear improvements over baseline methods, particularly in ~60% pruning.\n2. **Simple and well motivated idea** - The proposed idea of using influence functions to select which training points to use is clear and understandable and well suited for the task of reducing training complexity\n\n**Weaknesses and clarifications**\n\n3. **Motivation for Optimization** - I think it would be helpful to justify the need for the constrained optimization problem, compared to say a greedy approximation -- which would select top $m$ examples by $||\\mathbb{S}_i||_2$. This is said in \"high-gradient-norm samples could be zero if the direction of these two samples’ gradient is opposite\", but how does this compare theoretically? empirically? \n\n4. **Computing Influence Functions (efficiency)** - It would be helpful to clarify the computational cost of computing influence functions in the empirical analysis. \n\n5. **Computing Influence Functions (during training)** - Is there no benefit to incrementally pruning while training?\n\n6. **Methodological Depth** - I support the simplicity of the approach, however, it is not entirely clear to me whether it would meet the expectations of an ICLR conference paper in terms of the depth to which the authors explore the problem at hand. It seems there are many open questions about (1) class imbalance pruning (2) which parameters are used for influence function computation (3) approximations / exact / efficiency/ tradeoffs  of solution of constrained optimization problem?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dejXJWtSiHx", "reviewer": "Reviewer_gH14", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes dataset pruning, a method to remove/reduce training data that has low overall contribution towards model accuracy. The paper uses the concept of influence functions and uses an optimization function to find subsets of data that do not contribute to changes over model parameters. The paper includes theoretical proofs and experiments to validate the claims.\n\n\n", "summary_of_the_review": "I recommend accepting this paper because it addresses an important problem, has a clear and practical solution and has been empirically validated.", "strength_and_weaknesses": "Strengths:\n\n+ The paper addresses an important problem given the large datasets in real world, that are often redundant.\n+ The validation of the central claim is exhaustive and the paper also evaluates on different architectures.\n\n\nWeakness\n\n- What is the overall time required for dataset pruning? Do you need to review each data point more than once?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "L0m0aRhmvuz", "reviewer": "Reviewer_W84Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an optimization-based framework with influence functions for subset selection (or dataset pruning). The authors show in certain cases that the influence based method can be used to prune large datasets with only a small increase in the generalization error. From a practical point of view, this framework can be useful in situations when there is a repeated need for re-training models. ", "summary_of_the_review": "Although the components of the framework is not novel, their combination leads to a generalizable framework (with theoretical guarantees) for dataset pruning.  I will be leaning towards a weak-accept, as I feel that the framework can potentially be used to alleviate the cost of re-training. ", "strength_and_weaknesses": "First, I want to highlight that dataset pruning is an important problem and having a robust framework can help in mitigating multiple re-training routines, which can be expensive.  The framework proposed in the paper is new and shows good improvements over other baselines, though the coverage of experiments is slightly limited, which is my main concern. \n\nStrengths:\n\n\t- While both influence function and the optimization algorithm is not new, their combination is relatively new. \n\n\t- The paper is very well written and is coherent.\n\n\t- The method has good improvements over the baselines (forgetting and herding), though would like to see some more baselines such as [1] in the main paper. Moreover, showing the generalizability of the framework to other architectures is critical which the authors have shown positive results on. \n\nWeaknesses:\n\n\t- While the paper shows improvements on CIFAR derivatives, it lacks analysis or results on other datasets (e.g., ImageNet derivatives). Verifying the effectiveness of the framework on ImageNet-1k or even ImageNet-100 is important. These results ideally can be presented in the main paper. \n\n\t- The authors should add some details on how to solve the optimization in the main paper.  It's an important piece of information currently lacking in the paper.\n\n\t- Some baselines such as [1] are not considered and should be added.\n\n\nI feel that influence function can be replaced by other influence estimation methods such as datamodels[2] or tracin[3]. It will be beneficial to understand if the updated framework results in better pruning than the baselines. I am assuming it would result in better pruning results, however it would be beneficial to understand which influence based methods are particularly suitable for pruning. \n\n\n[1]. https://arxiv.org/pdf/2107.07075\n\n[2]. https://arxiv.org/abs/2202.00622\n\n[3]. https://arxiv.org/abs/2002.08484\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4IzZcO3EiUO", "reviewer": "Reviewer_HgbD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers a problem of selecting a largest redundant subset in training examples, without which the model parameter changes within $\\epsilon$ bound compared to the case of training with the full dataset. The applications of such data selection include the data pruning, where the goal is to identify a set of redundant training samples as many as possible and remove them to reduce the training cost, and neural network search, which aims at searching a network architecture that can achieve the best performance for a specific dataset, with a few training samples as possible. The main idea is to use influence function Koh & Liang (2017a) and formulate the discrete optimization problem to find the largest redundant subset of data with the constraint on the change of the model parameters. By empirical results, the authors show that the proposed optimization can find a subset of training samples effective in data pruning and neural network search. \n", "summary_of_the_review": "The paper is clearly written and the idea is well addressed with empirical support. The novelty is slightly limited since the influence function has been widely considered in dataset selection. The main idea is on formulating the discrete optimization problem based on the influence function, but the computational cost of this optimization could be the main bottleneck in using this method in practice.", "strength_and_weaknesses": "Strength\n\n- The authors propose a new discrete optimization problem to find a smallest subset of data samples with which a model can be trained with a slight parameter change compared to the model trained with the full dataset. The solution of the proposed optimization can guarantee a small generalization gap. \n\n- The authors provide simulation results demonstrating that the solution of their optimization (subsets of data samples selected for CIFAR-10 and CIFAR-100, resp.) are indeed effective in applications of data pruning and neural network search. Moreover, the theoretical analysis on generalization gap with respect to the pruning size is shown to be quite close to the empirical generalization gap in Figure 2. \n\nWeakness\n\n- Computational complexity of the proposed optimization: Even though the proposed discrete optimization does not require re-training of a model, still the optimization itself may require high computational complexity, increasing exponentially in the number of data samples, since the optimization space for (3) or (4) increases exponentially in $n$, e.g. if m=0.5n in (4) (finding 50\\% most informative samples) it require ${n\\choose n/2}=\\Theta(2^n)$ complexity. Can the authors explain the issue with computational complexity?\n\n- Empirical results: In data pruning experiment shown in Fig.1, the authors did not include the most recent SOTA baselines e.g., the Gradient Normed (GraNd) and the Error L2-Norm (EL2N) scores from Paul et al (2021), where the empirical result shows that for CIFAR-10 dataset 50\\% training examples can be removed without affecting the test accuracy. The performance of these baselines might be superior than the authors’ method since the authors claim that their method can prune 40\\% of examples with 1.3\\% test accuracy drop. Can the authors add this comparison as well?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3OMkiZCjqm", "reviewer": "Reviewer_63py", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the problem of dataset pruning, which seeks to remove redundant data points from the training set while minimizing model change as much as possible. The method consists of using influence functions to identify the influence of each datapoint, and use a discrete solver to identify which data subset has the least overall influence. The authors derive a rough upper bound for the generalization gap of this method, which are validated experimentally. Empirical results show that the proposed method outperforms competing dataset selection methods such as herding and data forgetting, also show generalization to unseen architectures and improvement in training efficiency.", "summary_of_the_review": "Accept. I make this recommendation because, overall, the paper addresses a key problem that has both practical and conceptual implications (i.e. how to prune a dataset, which can reduce the computational intensity of model training in practice and help us better understand how models learn from a dataset) in a compelling manner (i.e. proposing a data pruning method that leverages influence functions and discrete optimization). ", "strength_and_weaknesses": "**Strengths**:\n- The paper proposes a simple, yet elegant method to perform dataset pruning which is not only a key practical challenge, but can also contribute to a conceptual understanding of the role of particular data points on weights learned by the model. The proposed method seems sound and overcomes limitations of prior methods.\n\n- The broad structure of the paper’s argument is clear and logical. The authors provide an informative presentation of related works and how their work differs from related works, define the problem formulation, present their solution to the problem, and validate their solution empirically, showing that their method outperforms previous methods. The application of this approach to NAS is also very intruiging and presents a strong contribution.\n\n**Weaknesses**: The paper contains typos, awkward sentence structures, and grammatical errors that could benefit from proofreading. Also, the paper does not provide any discussion of the limitations of the method or its assumptions. In addition, there are some questions about the method itself and the interpretation of experimental results (see below). However, these are areas of improvement for the paper, rather than major weaknesses that warrant rejection.\n\nQuestions / Suggestions:\n\n- The paper does not provide an understanding of how far off the proposed algorithm is from an oracle algorithm that yields the best data subsets. To this end, it can be helpful to evaluate this approach for small datasets and models, and compare performance against a brute-force oracle which performs an exhaustive search over all data subsets. \n\n- Is there some analysis on the generalization of the proposed approach from a smaller architecture to a larger one in practice? This might make the proposed approach even more practically relevant at least for the case of NAS.\n\n- Section 6.2, Figure 2\n    - The experiment is meant to demonstrate that the generalization gap can be bounded by O(e/n + m/(n^2)) (which is approximately O(e/n)). If this is the case, then the dotted lines should be lower than their corresponding solid lines. However, they both seem to match pointwise, despite the rough nature of the upper bound. Is there a re-scaling of the theoretical results in the graph?\n\n    - What dataset and model are used here? Is it CIFAR10 and ResNet50? It could be helpful to test model architectures of varying orders of complexity to see if empirical results consistently match theoretical results across model architectures or if they deviate more from theoretical results as model complexity increases, as presumably the loss surface becomes less non-linear.\n\n- Section 6.5: Data pruning reduces convergence time, but how much time did it take to perform dataset pruning? It seems that to see the true time savings obtained by the method, the comparison should be [dataset pruning time + NAS training times] vs. [NAS on full training set] (rather than [NAS training time on pruned dataset] vs. [NAS training time on full training set]).\n\n- Regarding this statement in the paper \"We compare our method with forgetting Toneva et al. (2019b) because it has the strongest empirical performance compared with Borsos et al. (2020); Paul et al. (2021).\", it is still relevant to compare against gradient-norm or loss ranking methods, and as such I would strongly encourage the authors to directly compare against such methods instead of relying on such proxy comparison.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster