Data Pruning via Moving-one-Sample-out
Authors: Haoru Tan
Sitong Wu
Fei Du
Yukang Chen
Zhibin Wang
Fan Wang
XIAOJUAN QI
Venue: NeurIPS 2023 poster (2023)
Keywords: Data Valuation
Deep Learning
Data Pruning
Coreset Selection.

Abstract: In this paper, we propose a novel data-pruning approach called moving-one-sample-out (MoSo), which aims to identify and remove the least informative samples from the training set. The core insight behind MoSo is to determine the importance of each sample by assessing its impact on the optimal empirical risk. This is achieved by measuring the extent to which the empirical risk changes when a particular sample is excluded from the training set. Instead of using the computationally expensive leaving-one-out-retraining procedure, we propose an efficient first-order approximator that only requires gradient information from different training stages. The key idea behind our approximation is that samples with gradients that are consistently aligned with the average gradient of the training set are more informative and should receive higher scores, which could be intuitively understood as follows: if the gradient from a specific sample is consistent with the average gradient vector, it implies that optimizing the network using the sample will yield a similar effect on all remaining samples.  
Experimental results demonstrate that MoSo effectively mitigates severe performance degradation at high pruning ratios and achieves satisfactory performance across various settings. Experimental results demonstrate that MoSo effectively mitigates severe performance degradation at high pruning ratios and outperforms state-of-the-art methods by a large margin across various settings.

Data Pruning via Moving-one-Sample-our
Haoru 1.
Sitong 2
Fei Du
Yukang Chen
Zhibin Wang*.
Fan Wang
Xiaojuan Qi!
'HKU
2CUHK *DAMO Academy, Alibaba Group
"Hupan Lab, Zhejiang Province
MTXiv:2310.14664V [cs.LG] 23 Oct 2023
Official Implementation
Abstract
In this paper, we propose a novel data-pruning approach called moving-one-sample out (MoSo), which aims to identify and remove the least informative samples from the training set. The core insight behind MoSo is to determine the importance each sample by assessing its impact on the optimal empirical risk. This is achieved by measuring the extent to which the empirical risk changes when particular sample excluded from the training set. Instead of using the computationally expensive leaving- leaving-one-outt out-ouu--etraiiing procedure, we propose an efficient first-order approximator that only requires gradient information from different training stages. The key idea behind our approximation is that samples with gradients that are consistently aligned with the average gradient of the training set are more infor- mative and should receive higher scores, which could be intuitively understood as follows: if the gradient from a specific sample is consistent with the average gradient vector, it implies that optimizing the network using the sample will yield a similar effect on all remaining samples. Experimental results demonstrate that MoSo effectively mitigates severe performance degradation at high pruning ratios and achieves satisfactory performance across various settings.
Introduction
The recent advances in Al have been largely driven by the availability of large-scale datasets [31, 3, 6, 34, 41, 10, 37], which enable the training of powerful models [51, 45, 6, 1, 4, 36]. However, such datasets also pose significant challenges terms of computational and storage resources. is important to note that these datasets may contain redundant noisy samples that are either irrelevant or harmful to the model's performance. Data pruning techniques aim to address these issues by removing such samples and retaining smaller, more compact core set of training samples [11, 28, 42, 27, 48, 38, 15]. This can not only reduce the costs of model training and data storage but also maintain the performance of the model compared to the original dataset.
Existing approaches can be broadly categorized into three major groups: pruning by importance crite- ria [11, 42, 28, 27, 26, 46], coverage or diversity-driven methods [48, 29, 33, 15], and optimization- based methods [38, 8, 23, 24, 21, 44]. Among these, the first group of studies is the most effective and popular. These studies assume that hard samples are critical and informative core-set samples, and thus, they design difficulty-based metrics to assess sample importance. Such metries include prediction entropy [1]], forgetting [28] memorization [46] score, gradient norm [27], E2LN (variance of prediction) [27], self-supervised prototype distance [42], diverse ensembles [26], and others.
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Limitations and Motivations. The methods we discussed have some major drawbacks: (i). Hard samples are not necessarily important samples. For example, noisy samples [48] and outliers [39] often lead to high losses, which makes it difficult for importance criteria [11, 27] to distinguish
them from truly important samples. (ii). Training dynamies are rarely considered. The mainstream methods [27, 46, 26, 11, 42, 15, 48, 38] do not possess the awareness of training dynamics as they generally utilize a converged surrogate network for data selection. This may favor samples that are difficult or influential in the later stages of training, but not necessarily in the earlier stages or the whole training process [50, 12].
Our Method. In this paper, we propose a new data pruning algorithm, which involves the newly proposed Moving-one- on--Snmple-ouut (MoSo) score with an efficient and error- aror-guaranteed estimator. To address the first limitation, MoSo utilizes the change of the optimal empirical risk when removing specific sample from the training set to measure sample importance instead of only focusing on sample difficulty. By doing so, MoSo can better separate important samples from harmful noise samples, as the former tends to lower the empirical risk, while the latter may increase it. However, MoSo too Therefore, propose
costly to compute exactly as it needs brute force (eaving-one-oot-retaiine an efficient first-order approximator with linear complexity and guaranteed approximation error. The proposed approximation is simple: samples whose gradient agrees with gradient expectations at all training stages will get higher scores, which could be intuitively understood as follows: if the gradient from specific sample is consistent with the average gradient vector, it implies that optimizing the network using the sample will yield a similar effect on all remaining samples. The second limitation is addressed since MoSo comprchensively considers information from different training stages.
We evaluate our MoSo on CIFAR- 100 [5], Tiny-ImageNet [49], and ImageNer- 1K [31] under different pruning ratios. As shown in Figure| 1, our MoSo significantly surpasses the previous state-of-the-an methods, especially for high pruning ratios. Besides, experimental results demonstrate that the coreset selected by our MoSo under one network (such as ResNet) can generalize well to other unseen networks (such as SENet and EfficientNet) (refer to Figure 3(a) and Figure 3()). Additionally, we study the robustness of our MoSo on datasets with synthetic noisy labels (refer to Figure 3(c) and Figure 3()). It can be seen that our MoSo performs best on average, and surpasses the previous methods based on difficulty-baas -based importance criteria by large margin.
2 Related Work
Finding important samples is not only the purpose of data pruning, but also the core step in many machine learning tasks and problems, like active learning [7, 52, 32, 39, 19], noisy learning [9], and continuous learning [16]. In data-efficient deep learning, there are also some related topics like data distillation [13, 40, 53] and data condensation [17, 47, 20]. Unlike data pruning, they focus on synthesizing a small but informative dataset as an alternative to the original large-scale dataset. Existing data selection/ cattiion///iingggoe approaches could be broadly divided into several categories, pruning by importance criteria [11, 42, 28, 27, 26, 46], coverage or diversity driven methods [48, 29, 33, 15]. optimization-based methods [38, 8, 23-25, 21, 44, 43].
Pruning by importance criteria. This group of studies is the most popular. Generally, they assume that hard samples are critical and informative core-set samples and thus design difficulty-baa based metrics assess sample importance. The EL2N score [27] measures the data difficulty by computing the average of the f2-nrmm error vector from a set of networks. GraNd [27] measures the importance by calculating the expectation of the gradient norm. The Forgetting score [28] counts how many times a model changes its prediction from correct to incorrect for each example during the training process. Memorization [46] assigns a score to each example based on how much its presence or absence in the training set affects the model's 's ability to predict it correctly. Diverse ensembles [26] gave a score to each sample based on how many models in a group misclassified it. However, hard samples are not necessarily good for model training [42]. For example, noisy samples [48] and outliers [39] often lead to high losses, which makes it difficult for importance criteria [11, 27] to distinguish them from truly important samples. As comparison, our MoSo score measures sample importance instead of only focusing on sample difficulty by calculating the change of the optimal empirical risk when removing a specific sample from the training set. By doing so, it can better separate important samples from harmful noise samples, as the former tends to lower the empirical risk, while the latter may increase it.
2

---

Coverage or diversity driven methods. Sener et. al. [32] applied greedy k-center to choose the coreset with good data coverage. BADGE [19] is diversity-based basse selection method in active learning that clusters the gradient embeddings of the current model using k-means++ and selects subset from each cluster. CCS [15] balances the data distribution and the example importance in selecting data points. Moderate [48] chooses data points with scores near the median score. Note that some diversity-driven methods, such as CCS [15] and Moderate [48], can use any selection criterion, such as EL2N score [27], basis.
Optimization-based methods. In addition, a line of recent works proposed to select data by optimization, such as gradient matching [8, 23], bi-level optimization [24, 25], submodularity [21,44, 43]. One of the most advanced methods, the optimization- based dataset pruning [38], builds an algorithm over the sample-wise influence function [35] to remove samples with minimal impact and guarantees generalization, However, like mainstream methods [27, 46, 26, 11, 42, 15, 48, 38), does not account for the effect of samples on the training dynamics, it only uses the information from the final model. This may favor samples that are difficult or influential in the later stages of training, but not necessarily in the earlier stages the whole training process [50, 12]. In our work, the proposed method is fully soining-dynamie-ane comprehensively considers information from different training stages.
since the MoSo's s approximator
3 Method
In the following, we will first present the background knowledge in Section 3.1. Following that, we will elaborate on the proposed MoSo score for assessing sample importance in Section 3.2. Furthermore, we will introduce an efficient approximator of MoSo in Section 3.3. Section 3.4 shows the along with its complexity analysis and error guarantees.
3.1 Background
In this work, focus the classification task, where S {(x,, 3i)l denotes the training set, drawn i.i.d from underlying data distribution P. with input vectors Rd and one-hot label vectors E {0, 13KK Let ((.) denote the widely used cross-entropy loss function for classification tasks. Given pruning ratio 5 and a parameterized deep network fw. the data pruning task aims to find the most representative training subset $ S while pruning the remaining samples. This be formulated as:
$ = arg min Ex:(a.,)~ ((2, [(>,,,)]} w DES
(1)
where (|S) DD/[S| 8, |-1 represents the cardinality of a set, and w indicates the optimal network parameter trained on D with the stochastic gradient descent (SGD) optimizer. The SGD optimizer updates the parameters as follows:
w; = 1/. VL W:-1),
(2)
where {1...., T), Ne is the learning rate the t-th step, and B, represents the mini- bani-batch, the gradient operator with respect network parameters, L(-) is the average cross-entropy loss on the given set/batch of samples.
3.2 Definition for Moving-one-Sampll-ont
Here, we will describe the details Moving-one-Sample-ouu (MoSo) score.
Definition 1. The MoSo score for specific sample selected from the training set S is
M(z) ((/22 w - -C(S/2,w3)
where Siz indicates the dataset S excluding z, L(-) is the average cross-entropy loss the consid- ered set of samples, w is the optimal parameter trained on the full set S, and w i/= is the optimal parameter on S/z.
The MoSo score measures the importance of specific sample = by calculating how the empirical risk over S/2 changes when removing from the training set. Specifically, with representative

---

(important and with proper annotation) sample retaining it can promote training and result in lower empirical risk while removing could be harmful the training and result in higher empirical risk. Hence, M(z) > O. On the contrary, when is unrepresentative, .M()) O. Moreover, if the selected data point 2 harmful (e.g. noisy samples), the retention of z a hindrance to the learning process on S/2, so the risk would be high; removing the harmful 2 could result in a lower risk value. Hence, M(2) < 0.
3.3 Gradient-based approximator
The exact calculation of MoSo, as shown in (3.( has a quadratic time complexity of O considering dataset with n samples and total of T training iterations required obtain the surrogate network. However, this is practically infeasible; for instance. it may take more than 45 years to process the ImageNet-IK dataset using a Tesla-V100 GPU. To address this issue, we propose an efficient first-order approximator for calculating the MoSo score, which reduces the complexity to O(T)). This approximation not only significantly decreases the computational requirements but also maintains the effectiveness of the MoSo score in practical applications.
Proposition 1.1. The MoSo score could be efficiently approximated with linear complexity, that is,
T M(z) = Em-unttoon (1....TT) N VL(//2 VVl
where S/z indicates the dataset S excluding 2, I(.) is the cross-entropy loss function and L(-) means the average cross-entropy loss, V is the gradient operator with respect to the network parameters, and {(WE, 1]]) denotes a series of parameters and learning rate during training the surrogate network on S with the SGD optimizer. T is the maximum time-steps and N is the training set size.
The MoSo score approximator in (4. essentially represents the mathematical expectation of the inner product between the gradient with respect to network parameters considering only sample and the gradient using the training set excluding (denoted as 8/2) over T learning iterations. sample z will be assigned a higher MoSo score if the mathematical expectation of the inner product larger. This can be intuitively understood as follows: if the gradient V((2, w) from sample is consistent with the average gradient vector V LLS/2, w). it implies that optimizing the network using sample will yield similar effect on reducing the empirical risk as using all remaining samples. This indicates that sample 2 is an important and representative sample. Concurrently, according to (4), it is also assigned high MoSo score, which aligns with the intuition.
3.4 Theoretical analysis of tightness and complexity
First, we provide a rigorous mathematical justification to show that there is a theoretical guarantee for the error between the approximator we provide and the exact score by the brute-force leave-one-out retraining.
By supposing the loss function is L-Lipschitz continuous and the gradient norm of the network parameter is upper-bounded by g, and setting the learning rate as constant 11, the approximation error of Eq. (4) is bounded by:
Proposition 1.2.
[M(=) MM[= & (( (1)TT + nT?)),
(5)
where T is the maximum iterations.
The proposition shows that approximation eтror is positively correlated with many factors such as training duration T, gradient norm g, and learning rate n, In order to control the impact of approximate errors, in practice, we will not train the surrogate network to complete convergence, instead, we will only update small number of epochs.
Complexity analysis. We show that (q. efficiently approximates the MoSo score with linear complexity. Specifically, calculating the overall gradient information requires time complexity of O(n). Additionally, computing the expectation of the gradient over different training iterations in (4) takes 7 steps, resulting in a total complexity of O(Tn). In practice, we can randomly sample few time steps rather than considering all 7' steps to calculate the mathematical expectation, reducing the overall complexity to be less than O(Tn). Moreover, the optimized gradient calculation operator,

---

Algorithm 1: Data Pruning with MoSo.
Require: Dataset S = ((2,, W) pruning ratio d;
Require: Random initialized the parameter Wo of network;
Require: cross-entropy loss I(.), SCD optimizer;
Require: Learning-rate scheduler (m.....neh, maximum iteration T;
1: Initialize the sample-wise score set V= ø null set;
2: if multiple computing devices are available then
3: Partitioning S into S: (1).....1)::
//Wihh parallel acceleration.
4: else
5: $ = (S)
//Without acceleration.
6: end if
7: for S; E d
8:
SGD [(S;, wo); T, (m.....,rt);
//Train the surrogate network.
9: for 2 E S; do
10: M(2) - un-tt (I... 11 V/S/2 w.) (7((2,)))
I/MoSo scoring.
Merge into the score set V V (M(z))
12: end for
13: end for
return S- (
I/Data pruning.
implemented by advanced deep learning frameworks such as PyTorch [2]. further accelerates the computation, making more feasible for practical applications.
3.5 Data Pruning with MoSo
This section presents the pipeline for utilizing the approximated MoSo score in data pruning and coreset selection. The pseudocode is provided in Algorithm 1. In the MoSo scoring step (see line 10 of Algorithm 1), we employ (4. from Proposition to calculate the MoSo score. practice, there is need to sum all the time steps {1. when calculating the mathematical expectation. Instead, an efficient approach is randomly sampling several time steps for calculating the average or expectation, reducing the overall computational cost. In the data pruning step, samples with low scores are pruned, and the proportion pruned data corresponds to the predefined ratio 6.
Parallel acceleration by dataset partitioning. To enhance the practical applicability of MoSo on large-scale datasets, we propose a parallel acceleration scheme that can be employed when multiple GPU devices are available. Specifically, before training the surrogate network, we initially divide the original full dataset into series of non-overlapping subsets. This approach enables efficient processing by leveraging the parallel computing capabilities of multiple GPUs, where the number of subsets should be no more than the available computing devices. We select a subset from without replacement for each device and then perform training and scoring within the chosen subset, following Algorithm 1. Finally, MoSo scores from different devices are combined together. As long the number of samples in subset is large enough approximately represent the overall statistics of the dataset, this partitioning scheme will not compromise performance while significantly reducing computation time by factor of I. This approach particularly useful for large-scale datasets.
Experiments
Datasets and baselines. We evaluate our method on three well-known public benchmarks: the CIFAR-I00 100 [S], which contains 50,000 training examples of 100 categories; the Tiny-ImageNet [49], which has 100,000 images of 200 classes; and the ImageNet- [31], which covers 1000 classes with more than IM training images. We compare our method with a range of baselines. including: (I). Random selection; (2). Herding [29]; (3). Forgetting [28]; (4), GraNd [27]: (5). EL2N [27];
5

---

50
Top- Accuracy
60
Herting
Porgsting
GraNd
Top-1 Accuracy
30
40
Giokid
Herling
Pegesiig
Top-1 Accuracy
60
Randart
Deeiing
Pergeting
GraNd
ELEN
40
SSF
GPT
Modkotz
20
OPT
Madee
Mederiic
Meão
30
0.0
0.2
0.4
0.6
0.7 0.8
0.0
0.2
0.4
0.6 0.7
0.8
0.0
0.2
0.4
0.6 0.7 0.8
Pruning Rutio
Pruning Ratio
Pruning Ratio
CIFAR-100
(b) Tmny-ImageNee
(c) ImageNet-IK
Figure I: Performance comparison of our proposed MoSo and other baseline methods on three image classification datasets: CIFAR-I00 [5], Tiny-ImageNer [49], and ImageNet-IK IK [31]. The results show that our approach outperforms most of the baselines, especially for the high pruning rate (e.g.. 70%, 80%).
(6). Optimization-bannt -based Dataset Pruning (OPT) [38]; (7). Self-supervised pruning (SSP) [42]; (8). Moderate [48].
Implementation details. We implement our method Pytorch [2]. All the experiments are run on server with 8 Tesla-V 100 GPUs. Unless otherwise specified, we use the same network structure ResNet-50 [22] both the coreset and the surrogate network on the full data. keep all hyper- parameters and experimental settings of training before and after dataset pruning consistent. We train the surrogate network on all datasets for 50 epochs. To estimate the mathematical expectation in (4) from Proposition 1, randomly sample 10 time steps. Thus, MoSo compute gradients from multiple epochs without increasing the overall time cost significantly, compared to methods that need train network fully (e.g. 200 epochs for CIFAR- 100) before calculating the scores.
4.1 Main Results
In the following subsections, we present the detailed performance comparison our method and baselines on three experiments: data pruning, generalization to unseen structures, and robustness to label noise.
Data pruning. As Figure I(a) and 1(b) show, our method significantly surpasses the SOTA method [48] on CIFAR-100 and high pruning ratios. Note that some selected baselines perform worse than the random selection, especially when with high pruning ratios, e.g. the re- sults of the classic EL2N on CIFAR- 100, while our method doesn't suffer from this problem. Furthermore, in Figure (c), our method achieves sat- ImageNet- IK across different pruning rates, large-
1.0
Fuller
McS0
0.8
at
Accuracy
0.6
isfactory performances
Class index
showing its effecttiveness scale and complex datasets. These re- sults also indicate that our method can capture the sample importance more accurately and robustly than the exist- ing methods.
Figure We show the class-wise accuracy before (bars named Fullser) and after (bars named MoSo) applying our MoSo approach. The experiment is conducted on CIFAR- 100. We chose ResNet-18 the network architecture and set the pruning ratio be 0.8.
To study whether our algorithm improves/hurts certain classes, we visualize the class-wise accuracy before and after applying our MoSo data pruning approach Figure We observe a significant correlation between the two, with Spearman correlation coefficient of 0.913 and P value of

---

Apcuncy
Accuncy
Accumey
Accuncy
Herling
Perpetto
OPT
dtp
Maderns
Mall
Hestip
Farartin
OP7
Mederate
Moll
Hembay
Perpettog
OP
Medertte Mil
Heshing
Farartia
(a) ResNet SENet
(b) ResNet EfficientNet
(c) Truming-ratio 70%
(d) Pruning-ratio 80%
Figure 3: In (a) and (b), we study the generalization performance of MoSo and other baselines CIFAR-10 100 from ResNet-50 to SENet (R to S) and ResNet-50 to EfficientNet-Bi (R to E). In (c) and (d), show the robustness against label noise of MoSo and other baselines CIFAR-100, where the labels are randomly replaced with any possible label with a 20% probability.
0.0295. This indicates that the performance before and after pruning with MoSo is consistent across categories, and no significant improvement or harm to any particular category is observed.
Generalization test. To test whether the pruning results are overfitting to the specific network architecture, we evaluate MoSo's generalization ability to unseen architectures. Following the protocol in [48], we use ResNet-50 as the surrogate network for scoring, and training different network architectures, SENet [18] and EfficientNet-BO [30], on the selected data. Figure 3(a) and Figure 3(b) show the experimental results on different network architectures. MoSo exhibits a satisfying generalization ability to unseen models and consistently outperforms or matches the state-of-the-arg methods such as SSP [42], and OPT [38].
Robustness test. Label noise is common challenge in real-world applications. Therefore, how to improve the model robustness to label noise is an important and popular problem. this section, we study the robustness of MoSo to label noise by conducting comparative experiments on CIFAR-100 and -mageeet with synthetic label noise. Specifically, we inject label noise [14] into the two datasets by randomly replacing the labels for percentage of the training data with all possible labels. The noise rate is set to 20% for all the experiments. We use ResNet-50 as the network architecture and keep all experimental settings consistent with the previous data pruning experiments. The results are shown in Figure 3(c) and Figure 3(d). We observe that some difficulty-based importance criteria don't work very well, such Forgetting, GraNd on both settings, while Herding [29]. Moderate [48] and our MoSo, perform well and significantly outperform other baselines in all settings. Our MoSo achieves comparable performance with the best baseline, Herding [29], only lagging behind Herding by less than 1% Top-1 acc.
4.2 Computational Efficiency
Time (sumogate maining)
We evaluated MoSo and the other baseline methods on a server with
MoSo
Time-cnol (scoring)
8 Tesla V100 GPUs. We used the
Method
CIFAR-100 dataset and the ResNet50 backbone for experiments. It
I day
OPT
should be noted here that we also
take into account the training time of the surrogate network. This is because not all datasets will have community-provee provided network to cal- culate scores, and private datasets will require practitioners to train surro- gate network. MoSo achieves the best trade-off between computational re- quirements and performance, making it the best- west-performing model with rea-
GraNd
50
100
150
200
250
300
Time-cost (m)
Figure 4: Time-core comparison between our MoSo and other baselines. Please note that when implementing the GraNd method, we don't take the summation of the gradient norm from all epochs, instead, we use the same time-step sampling scheme as MoSo.
7

---

sonable computational demands. Notably, it outperforms the oate--o-the-aase art method, Moderate, while being more efficient. Because of the use of large-scale linear programming in the scoring phase, OPT is significantly more time-consuming than the other methods.
68
1op-1 Accuracy
Top-I Accuracy
67
60
66
50
Random
MoSo without TDA
65
0.0
0.2
0.4
0.6
0.8
0.1
0.15
0.2
0.4
Pruning Ratio
Sampling Rate (b)
(a)
Figure 5: Ablation study the effect of (a) incorporating the saannndddynmmii-aaa into the MoSo score, and (b) using different time step sampling rates on the accuracy of the selected coresct (with pruning ratio of 0.4). The experiments conducted on CIFAR- 100 with ResNet-50 as the network architecture.
(TDA)
4.3 Further Study
In this subsection, perform additional ablation experiments investigate the effect of the aware- ness of training dynamics, the effect of time step sampling, the effect of the parallel speed-up scheme (dataset partitioning), and the effect the number of epochs in the surrogate training stage.
Effect of the awareness of training dynamics. Here we investigate the effect of incorporating the awareness of training dynamics into our MoSo score. To do this, compare method with a variant that removes this awareness by only considering the gradient from the very last epoch of the surrogate network. This variant is equivalent to using the gradient importance. The results are shown Figure 5(a). We can clearly see that our method outperforms the variant both CIFAR-IOK 100 across different pruning rates. This indicates that the awareness of training dynamics is crucial for capturing the impact of sample on the model performance and that the gradient norm alone from a converged network
measure of sample
sufficient for measuring sample importance.
Effect of time step sampling. We then investigate the effect of time step sampling on the accuracy and efficiency of method. Time step sampling is technique that computational cost of calculating (4) by randomly selecting a subset of epochs to estimate the MoSo score. However, this technique also introduces variance into the estimation and may even affect the quality of the selected coreset with too-small sampling rate. To study this trade-off, we conduct experiments with different sampling rates and measure the performance of the final coreset on CIFAR-100 The results are shown in Figure 5(b). As expected, we observe that the mean performance decreases as the sampling rate decreases, and the variance also increases as the sampling rate decreases. This suggests that time-step sampling is useful technique for improving the efficiency of our method, but should be used with caution to avoid sacrificing too much accuracy.
to reduce the
Effeet of the parallel speed-up scheme. The time-consuming aspect of data pruning training the surrogate network. Our framework utilizes parallel speed-up scheme, explained in line 3 of Algorithm 1 in the main text. Es- sentially, we partition the original full set into several non-overlapping subsets with equivalent size {Si,... Sr), where represents the number of computing devices. On each device,
Table 1: The effect of dataset partitioning on final data pruning performance, where the pruning ratio 0.2. The bold one represents settings used in this work.
Subsets number 7
2
5
10
MoSo (ours)
74.35
75.11
75.76
75.81

---

we can train a surrogate network on S,. Then, for each sample E St, we perform MoSo scoring within the current set by using MMz to approximate MMz]S), Implementing this approach reduces the overall time overhead by fold. Table I demonstrates that partitioning S into more subsets can improve data pruning's s performance. This means that if the training set vast, a single sample's impact may be buried, making it challenging to measure. In relatively small training set, however, the effect of a single sample can be more sensitively reflected and easily captured.
Effeet of the number of epochs in the surrogate training stage. To investigate the impact of sur- rogate network training epochs on the ultimate data pruning performance, we augmented the number of training epochs and presented the experimen- tal outcomes CIFAR-100, as shown in Table 2. However, it is evident that augmenting the training duration does not lead uniform improvement in performance. For instance, lengthening the train-
The effect of surrogate network train- ing epochs the final data pruning perfor- mance, where the pruning ratio is 0.2.
Table 2:
Training epochs
50
100
150
200
MoSo
75.76
76.41
76.19
76.58
ing duration from 50 epochs to 200 epochs only resulted in meager 0.82 Top-1 accuracy gain, while the time consumed quadrupled. Note that this is consistent with our conclusion in Proposition 1.2 that the approximation error between the approximated MoSo and the exact MoSo value by seav--oeeouu-reteee out-retraining increases with time (T), leading to no improvement in DP performance with longer training time.
5 Conclusion
This paper introduces a novel metric for measuring sample importance, called the Moving-one Sample-out (MoSo) score. It quantifies sample importance by measuring the change of the optimal empirical risk when a specific sample is removed from the training set. By doing so, MoSo can better distinguish important samples that contribute to the model performance from harmful noise samples that degrade it, as the former tends to lower the empirical risk, while the latter may increase it. Moreover, we propose an efficient estimator for MoSo with linear complexity and approximation error guarantees. The estimator incorporates the awareness of training dynamics by considering the gradient difference across different epochs. We conduct extensive experiments on various data pruning tasks and demonstrate the effectiveness and generalization of our method.
Limitations and future work. First, the MoSo score is actually the agreement between the gradient of a single sample and the mathematical expectation of the gradient. The higher the agreement, the sample will be given higher score. In fact, this is based on the important assumption that the amount of information the data set is much greater than the amount of noise. However, the amount of noise is dominant, the usefulness of MoSo is not guaranteed. Therefore, is very necessary to propose a variant of MoSo to adapt to high noise conditions with theoretical guarantees. Secondly, in terms of application, this paper only evaluates the performance of MoSo on classification tasks. Many practical tasks, e.g. large-scale multimodal learning, are worth considering in future work.
believe that in the future,
Social Impact. MoSo has potential influences in important applications such as data collection and data-efficient AI. Moreover, it is beneficial for reducing the computational workload during training and the cost of storing datasets, which is of great significance for environmentally friendly and energy- meery--rriendly economies. But it may be deployed for inhumane web-data monitoring. The potential negative effects can be avoided by implementing strict and secure data privacy regulations.
Acknowledgment
This work has been supported by Hong Kong Research Grant Council Early Career Scheme (Grant No. 27209621), 1), General Research Fund Scheme (Grant No. 17202422). Theme-based Research (T45-702/22-R), and RGC Matching Fund Scheme (RMGS). Part of the described research work is conducted in the JC STEM Lab of Robotics for Soft Materials funded by The Hong Kong Jockey Club Charitics Trust.

---

References
[1] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, ct. al: Palm: Scaling language modeling with pathways. arXiv:2204.02311 (2022)
[2] Adam Paszke, Sam Gross, Soumith Chintala, G Chanan, Yang, Zachary Devito, Zeming Lin, Alban Desmaison, L Antiga, A Lerer, ct.al.: Automatic differentiation in pytorch. In: Advances neural information processing systems Workshop (2017)
[3] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, Ily Sutskever: Language models unsupervised multitask learners. OpenAl blog (2019)
[4] Alec Radford, Jong Wook Kim, Chris Hallacy, ditya Ramesh, Gabriel Goh, Sandhini Agarwa, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, Ilya Sutskever: Learning transferable visual models from natural language supervision. CoRR abs/2103.00020 (2021)
[5] Alex Krizhevsky: Learning multiple layers of features from tiny images. Technical report (2009)
[6] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander Berg, Wan-Yen Lo, Piotr Dollár, Ross Girshick: Segment anything. arXiv:2304.0264) (2023)
[7] Antoine Bordes, Seyda Ertekin, Jason Weston, Léon Bottou: Fast kernel classifiers with online and active learning. Journal of Machine Learning Research 6(54), 1579-1619 (2005)
[8] Baharan Mirzasoleiman, Jeff Bilmes, Jure Leskovec: Coresets for data-efficient training of machine learning models. In: International Conference on Machine Learning (2020)
[9] Baharan Mirzasoleiman, Kaidi Cao, Jure Leskovec: Coresets for robust training of deep neural networks against noisy labels. In: Advances in Neural Information Processing Systems (2020)
[10] Christoph Schuhmann, Romain Beaumont, Richard Vencu, et. al: LAION-5b: An open large- scale dataset for training next generation image-text models. In: Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track (2022)
[11] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, Matei Zaharia: Selection via proxy: Efficient data selection for deep learning. In: International Conference on Learning Representations (2019)
[12] Daphna Weinshall, Dan Amir: Theory of curriculum learning, with convex loss functions. Journal of Machine Learning Research 21(222), 1-19 (2020)
[13] George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei A Efros, Jun- Zhu: Dataset distillation by matching training trajectories. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition (2022)
[14] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, Lizhen Qu: Mak- ing deep neural networks robust to label noise: loss correction approach. In: IEEE/CVF Conference Computer Vision and Pattern Recognition (2017)
[15] Haizhong Zheng, Rui Liu, Fan Lai, Atul Prakash: Coverage-centric coreset selection for high pruning rates. In: International Conference on Learning Representations (2023)
[16] Jachong Yoon, Divyam Madaan, Eunho Yang, Sung Ju Hwang: Online coreset selection for rehearsal-based continual learning. In: International Conference on Learning Representations (2022)
[17] Jang-Hyun Kim, Jinuk Kim, Seong Joon Oh, Sangdoo Yun, Hwanjun Song, Joonhyun Jeong, Woo Ha, Hyun Oh Song: Dataset condensation via efficient synthetic-data parameteriza- tion. In: International Conference on Machine Learning (2022)
[18] Jie Hu, Li Shen, Gang Sun Squeeze-and-exciiatio networks, In: IEEE/CV Conference on Computer Vision and Pattern Recognition (2018)
10

---

[19] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, Alekh Agarwal: Deep batch active learning by diverse, uncertain gradient lower bounds. In: International Conference on Learning Representations (2019)
[20] Justin Cui, Ruochen Wang, Si Si, Cho-Jui Hsieh: De-bench: Dataset condensation benchmark. In: Advances in Neural Information Processing Systems (2022)
[21] Kai Wei, Rishabh Iyer, Jeff Bilmes: Submodularity in data subset selection and active learning. In: International Conference on Machine Learning (2015)
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun: Deep residual learning for image recognition. In: IEEE/ CVF Computer Vision and Pattern Recognition Conference (2016)
[23] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Abir De, Rishabh Iyer: Grad-match: Gradient matching based data subset selection for efficient deep model training. In: International Conference on Machine Learning (2021)
[24] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Rishabh Iyer: Gener- alization based data subset selection for efficient and robust learning. In: Proceedings of the AAAI Conference on Artificial Intelligence (2021)
[25] Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, Rishabh Iyer: Retrieve: Coreset selection for efficcinnt and robust semi-supervised learning, In: Advances in Neural Information Processing Systems (2021)
[26] Kristof Meding, Luca M. Schulze Buschoff, Robert Geirhos, Felix A. Wichmann: Trivial or impossible- dichotomous data difficulty masks model differences (on imagenet and beyond). In: International Conference Learning Representations (2022)
[27] Mansheej Paul, Surya Ganguli, Gintare Karolina Dziugaite: Deep learning on data diet: Finding important examples early in training. In: Advances in Neural Information Processing Systems (2018)
[28] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, Geoffrey J Gordon: An empirical study of example forgetting during deep neural network learning. In: International Conference on Learning Representations (2018)
[29] Max Welling: Herding dynamical weights to learn. In: International Conference Machine Learning (2009)
[30] Mingxing Tan, Quoe Le: Efficientnet: Rethinking model scaling for convolutional neural networks. In: International Conference on Machine Learning (2019)
[31] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, others: Imagenet large scale visual recognition challenge. International journal of computer vision 115(3), 211 (2015)
[32] Ozan Sener, Silvio Savarese: Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: .0489 (2017)
[33] Ozan Sener, Silvio Savarese: Active learning for convolutional neural networks: A coreset approach. In: International Conference on Learning Representations (2018)
[34] Pan Lu, Swaroop Mishra, Tony Xia, Liang Qiu, Kai-Wei Chang, Song-Chun Zhu, Oyvind Tafjord, Pete Clark, Ashwin Kalyan: Learn explain: Multimodal reasoning via thought chains for science question answering. In: Advances in Neural Information Processing Systems (2022)
[35] Pang Wei Koh, Percy Liang: Understanding black-box predictions via influence functions. In: International Conference on Machine Learning (2017)
[36] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, Björn Ommer: High- resolution image synthesis with latent diffusion models, arXiv preprint arXiv:2112.10752 (2021)
11

---

[37] Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang, Jonathan Hayase, et. al.: Datacomp: In search of the next generation of multimodal datasets, arXiv preprint arXiv:2304. 1411:2304..1108 (2023)
[38] Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, Ping Li: Dataset pruning: Reducing training data by examining generalization influence. In: International Conference on Learning Representations (2023)
[39] Siddharth Karamcheti, Ranjay Krishna, Li Fei-Fei, Christopher D Manning: Mind your outliers! investigating the negative impact of outliers on active learning for visual question answering. arXiv preprint arXiv:2107.000 022331 (2021)
[40] Songhua Liu, Kai Wang, Xingyi Yang, Jingwen Ye, Xinchao Wang: Dataset distillation via factorization. In: Advances in Neural Information Processing Systems (2022)
[41] Soravit Changpinyo, Piyush Sharma, Nan Ding, Radu Soricut: Conceptual 12M: Pushing web- scale image-text pre-training to recognize long-tail visual concepts. In: IEEE/ / CVF Computer Vision and Pattern Recognition Conference (2021)
[42] Sorscher, B., Geirhos, R., Shekhar, S., Ganguli, S., Morcos, A.: Beyond neural scaling laws: beating power law scaling via data pruning. In: Advances in Neural Information Processing Systems (2022)
[43] Suraj Kothawade, Nathan Alexander Beck, Krishnateja Killamsetty, Rishabh Iyer: Similar: Submodular information measures based active learning in realistic scenarios. In: Advances in Neural Information Processing Systems (2021)
[44] Suraj Kothawade, Vishal Kaushal, Ganesh Ramakrishnan, Jeff Bilmes, Rishabh Iyer: Prism: unified framework of parameterized submodular information measures for targeted data subset selection and summarizationg. In: Proceedings of the AAAI Conference on Artificial Intelligence (2022)
[45] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, et. al: Language models are few-shot learners. In: Advances in Neural Information Processing Systems (2020)
[46] Vitaly Feldman, Chiyuan Zhang: What neural networks memorize and why: Discovering the long tail via influence estimation. In: Advances in Neural Information Processing Systems (2020)
[47] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, Neil Shah: Graph conden- sation for graph neural networks. In: International Conference on Learning Representations (2022)
[48] Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, Tongliang Liu: Moderate coreset: A universal method of data selection for real-world data-efficient deep learning. In: International Conference on Learning Representations (2023)
[49] Ya Le, Xuan S. Yang: Tiny imagenet visual recognition challenge. CS 231N (2015)
[50] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, Jason Weston: Curriculum learning. Journal of the American Podiatry Association 60, 6 (2009)
[51] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Liu, Baining Guo: Swin transformer: Hierarchical vision transformer using shifted windows. arXiv preprint arXiv:2103.I 14030 (2021)
[52] Zeyad Ali Sami Emam, Hong-Min Chu, Ping- Yeh Chiang, Wojeiech Czaja, Richard Leap- man, Micah Goldblum, Tom Goldstein: Active learning at the imagenet scale. arXiv preprint arXiv:2111. 12880 (2021)
[53] Zhiwei Deng, Olga Russakovsky: Remember the past: Distilling datasets into addressable memories for neural networks. In: Advances in Neural Information Processing Systems (2022)
12


Reviews:
[{"review_id": "XysoIrxhhb", "reviewer": "Reviewer_xfpA", "summary": "This paper proposes a data-pruning method. The authors argue that sample importance should not be determined by sample difficulty. Alternatively, they present the MoSo score, which quantifies the changes in empirical risk upon excluding a single data point. An efficient approximation for MoSo is proposed to calculate the score with some theoretical guarantee. Experiments are conducted with common image classification benchmarks. ", "questions": "[1] I appreciate the set of experiments with label noise, as it could provide evidence for the authors' insight on difficult data. I would like to see the overlapping ratio between samples with injected noise and pruned data. This overlapping can be more informative than simple test accuracy in demonstrating whether the proposed method can exclude hard but noisy data.\n\n[2] The authors mainly report the trade-off of top-1 accuracy and data pruning ratio, which could demonstrate the effectiveness of a method. It would be interesting to see the data pruning ratio across classes to better understand the method. Does the pruning change the data sample distribution, and does the method improve/hurt certain classes?", "limitations": "The authors didn't discuss limitations in the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "[1] The proposed measure of sample importance is intuitive, and the approximation appears novel.\n\n[2] The paper is overall well-written, with a clear description of the insights and adequate related work.", "weaknesses": "[1] The authors propose an approximation for the MoSo score.  However, it is unclear from the experiment how expensive the proposed method is compared to the baselines. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer xfpA:\n\nThank you for your comments which help us improve our work! \n\n----\n\n**Q1: How expensive the proposed method is compared to the baselines?**\n\nA1: Thanks for your suggestion. We will incorporate the additional results into the paper. We evaluated MoSo and the other baseline methods on a server with 8 Tesla V100 GPUs. We used the CIFAR-100 dataset and the ResNet50 backbone for our experiments. \n\nMoSo achieves the best trade-off between computational requirements and performance, making it the best-performing model with reasonable computational demands. Notably, it outperforms the state-of-the-art method, Moderate, while being more efficient. Because of the use of large-scale linear programming in the scoring phase, OPT is significantly more time-consuming than the other methods. \n\n|  Method   | Time-cost (surrogate training)  | Time-cost (scoring)| Time-cost (total)| Accuracy (Pruning-ratio 60%)|\n|  ----  | ----  | ----  | ----  |  ----  |\n| Random  | 0 | 0 |0  | 64.32 | \n| GraNd  | 192.2 m | 683.8 m | 876.0 m  | 60.52 |\n| OPT  | 192.2 m | $\\geq 1$day | $\\geq 1$day | 58.93 |\n| Moderate  | 192.2 m | **6.63 m** | 198.8 m| 64.92 |\n| MoSo  | **46.5 m** | 56.2 m | 102.7 m | **68.97** |\n\n----\n\n**Q2: The overlapping ratio between samples with injected noise and pruned data.**\n\nA2:  Thanks! This is a good question! We present detailed statistics on TinyImageNet with 20% label noise, totaling 100,000 data samples. After pruning 80% of the data with either MoSo or random selection, we observe MoSo meaningfully reduces the noise ratio of the retained data (decreasing from 20% to 14%). \n\n|  MoSo | Noisy  data| Clean data | Noise Ratio|\n|  ----  | ----  | ----  |  ----  | \n| Retained subset  | 2795  |  17205   |  14% |\n| Discarded (Pruned)   | 17205   |  62795  | 22% |\n\n\n**Q3: Does the pruning change the data sample distribution, and does the method improve/hurt certain classes?**\n\nA3:  This is a very important question, and we have visualized and analyzed the relevant statistical results, which will be included in the revised paper in the future. See Q2 in Global-Rebuttal (https://openreview.net/forum?id=vO6ZdPWaHc&noteId=DsrmXiWeKr) for details.\n\n\n**Q4: The authors didn't discuss limitations in the paper.**\n\nA4: Please refer to Sec. 5. in the supplementary material, where we discussed the limitations and future works. \n\n"}, {"review_id": "X5YW6SiF80", "reviewer": "Reviewer_eYrR", "summary": "This paper presents moving-one-sample-out (MoSo) for the purpose of coreset selection. This algorithm measures how empirical loss changes when excluding individual points during training. The paper introduces an approximation and other tricks to make this method computationally feasible. Experimentally, MoSo outperforms other methods on standard datasets, and also has nice properties like generalization to other architectures and robustness to label noise.", "questions": "See weaknesses\n\nIs there a reason why experiments aren't done on CIFAR-10? This seems to be a standard benchmark for this line of work.\n\nWould also be interested in seeing this method evaluated on a larger dataset or other tasks (e.g. large-scale multi-modal learning mentioned in supplementary)", "limitations": "Addressed in weaknesses - lack of analysis on computational cost.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Good presentation: method is clear and contextualized properly through related work and comparison experiments\n- Good results: MoSo does better on all datasets evaluated than the comparison baselines\n- Method seems new and is differentiated from related work\n- Interesting ablations on architecture generalization and label noise", "weaknesses": "- Lack of analysis on the computational cost of this method. Comparisons use same amount of samples seen during training, but this does not take into account the extra cost of calculating the coreset for some of these methods. This can be addressed with end-to-end training time or a similar metric. Though the authors mention that this is substantially cheaper than methods that require training a full-network for scoring, this information is still important, especially when considering scaling up this method to larger datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer eYrR:\n\n\nThank you for appreciating our approach. We will address your comments below. \n\n----\n\n**Q1: Lack of analysis of the computational cost of this method.** \n\nA1: This is a good question!  We will incorporate this experiment into the paper. We evaluated MoSo and the other baseline methods on a server with 8 Tesla V100 GPUs. We used the CIFAR-100 dataset and the ResNet50 backbone for our experiments. \n\nMoSo achieves the best trade-off between computational requirements and performance, making it the best-performing model with reasonable computational demands. Notably, it outperforms the state-of-the-art method, Moderate, while being more efficient. Because of the use of large-scale linear programming in the scoring phase, OPT is significantly more time-consuming than the other methods. \n\n|  Method   | Time-cost (surrogate training)  | Time-cost (scoring)| Time-cost (total)| Accuracy (Pruning-ratio 60%)|\n|  ----  | ----  | ----  | ----  |  ----  |\n| Random  | 0 | 0 |0  | 64.32 | \n| GraNd  | 192.2 m | 683.8 m | 876.0 m  | 60.52 |\n| OPT  | 192.2 m | $\\geq 1$day | $\\geq 1$day | 58.93 |\n| Moderate  | 192.2 m | **6.63 m** | 198.8 m| 64.92 |\n| MoSo  | **46.5 m** | 56.2 m | 102.7 m | **68.97** |\n\n---\n\n**Questions.**\n\n**Q2: Is there a reason why experiments aren't done on CIFAR-10? This seems to be a standard benchmark for this line of work.**\n\nA2: We primarily followed the experimental setup in the recent method, Moderate [A]. Here, we have conducted experiments on CIFAR-10 and present the results in the Table below. Our method demonstrates comparable performance to existing methods at low pruning ratios and surpasses them at high pruning ratios. \n\nIt's worth noting that CIFAR-10 is a smaller dataset compared to CIFAR-100, Tiny-ImageNet, and ImageNet, which are evaluated in our paper. Our method exhibits superior performance on larger datasets, effectively showcasing the potency of our model. In the case of small-scale datasets like CIFAR-10, there isn't a compelling reason to employ pruning.\n\n\n|  Method   | 20%  | 40% |  60% | 80% |\n|  ----  | ----  | ----  | ----  |  ----  |\n| Random  | 93.05 | 92.19 | 89.77  | 85.20 | \n| Forgetting  | 94.52 | 93.33 | 91.41  | 86.12 |\n| EL2N  | **94.59** | 93.77 | 92.24 | 85.23 | \n| Moderate  | 94.05 | **93.81** | **93.10** | 86.05   |\n| MoSo  | 94.20 | 93.60 | 93.05 | **86.26** | \n\n\n**Q3: Would also be interested in seeing this method evaluated on a larger dataset or other tasks (e.g. large-scale multi-modal learning mentioned in supplementary).**\n\n\nA3: We have conducted experiments on the CC3M dataset, which contains 3 million image-text pairs, to train a CLIP [B] model using two backbone architectures: ResNet50 and ViT-B. \n\nFollowing CLIP [B], we evaluate the trained model in zero-shot image classification. The result shown in the Table below demonstrates notable improvements over the random selection baseline. Notably, after removing 80% of the data, we observe a 3.2% increase in performance. Furthermore, data selected using the ResNet50 backbone also enhances the performance of the transformer-based architecture, ViT-B, outperforming the random baseline by 2.6%. This showcases the generalization ability of the pruned data.\n\n\n|  Method   | Training Data | Zero-shot classification on ImageNet |\n|  ----  | ----  | ----  | \n| CLIP (R50) [B] | Full dataset | 16.7  | \n| CLIP (R50) | Random selection 20% subset  | 5.9 | \n| MoSo (R50) | MoSo (ours) Selection 20% subset using CLIP(R50) | 9.1(+3.2) | \n| CLIP (ViT-B) [B] | Full dataset | 16.1  | \n| CLIP (ViT-B) | Random selection 20% subset  | 5.5 | \n| CLIP (ViT-B) | MoSo (ours) Selection 20% subset using CLIP(R50)  | 8.1(+2.6) |  \n\n\n[A]. Xiaobao Xia, et.al.: Moderate Coreset: A Universal Method of Data Selection for Real-world Data-efficient Deep Learning. ICLR-2023\n[B]. Alec Radford, et.al.: Learning Transferable Visual Models From Natural Language Supervision. ICML-2021\n\n"}, {"review_id": "xFW7Ak9NTG", "reviewer": "Reviewer_QDiJ", "summary": "This paper presents MoSo, a method to identify and remove the least informative samples from a large dataset. The underlying idea is to consider the impact of each sample on the optimal empirical risk. Quantifying this exactly requires leave-one-out retraining for every point, which is intractable. So, the authors provide an approximation of this score that is more efficient in that it does not require leave-one-out retraining for every point. They provide bounds on the quality of this approximation and present empirical comparisons of the data pruning approach with contemporary baselines.", "questions": "1. It is not clear to me why the original MoSo score “takes $\\mathcal O(Tn^2)$ time.” More generally, the asymptotic complexities are confusing throughout because neither the batch size of SGD, nor the dimensionality of the data points $d$ are accounted for in the asymptotic analysis. Are we assuming that the batch size = $n$, i.e., regular GD and dimensionality = 1 for the samples?\n2. Related to the above, I don’t understand how the approximation in Eq. (4) is faster in an asymptotic sense than the original MoSo score in Eq. (3). Assuming that batch size = $n$ and ignoring the dimensionality of the points as the authors do, two full rounds of training to obtain $w_{\\mathcal S}^*$ and $w_{\\mathcal S \\setminus z}^*$ take $\\mathcal O(n T)$ time overall (based on the way the authors express training time). Once we have those two models, computing the difference of losses in Eq. (3) takes $\\mathcal O(n)$ time. Where is the quadratic in $n$ coming from? It would help to clarify that Eq. (4) requires only training the model once (as in Line 8 of Alg. 1), unlike Eq. (3) which requires computing $w_{\\mathcal S \\setminus z}^*$ for each $z$.\n3. What is the appeal of the data pruning method from a practical efficiency perspective, given that it requires training the surrogate network for $(T+1)/2$ iterations in expectation on the full dataset?\n", "limitations": "Yes, they are mentioned in the supplementary material.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proposed approximation of the MoSo score and the accompanying analysis are sound and novel to the best of my knowledge.\n* The authors present theoretical results establishing the accuracy of their approximation.\n* Empirical evaluations on benchmark vision tasks are provided that support the effectiveness of the method relative to state-of-the-art baselines.", "weaknesses": "* The authors state that data pruning can address the computational challenges in the introduction. However, it is not clear to me how the method can provide a computational speedup given that it needs to train a surrogate model on the entirety of the dataset (Line 8 of Algorithm 1) to compute the MoSo score approximation.\n* The claimed asymptotic computation times are difficult to understand. Upon looking at the algorithm, it seems that the power of the approximation in Eq. (4) comes from the fact that the surrogate network needs to only be trained once, rather than once per each point (as required by Eq. 3). This should be clarified. Please see the Questions section for more details.\n* The claim that randomly sampling a few time steps rather than considering all $T$ steps “reduces the overall complexity to be less than $\\mathcal O(Tn)$” does not seem sound since the expectation of a uniform sample from $\\\\{1, \\ldots, T\\\\}$ is $(T+1)/2$.\n* Only the ResNet50 architecture is used exclusively throughout the experiments to construct the pruned datasets. Diversity of architecture in the evaluations would have strengthened the method’s appeal.\n* The computational complexity of the method is quite high as it requires training the model on the entire dataset relative to the compared methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer QDiJ: \n\nThanks for your time and efforts in reviewing our paper. We will address your concerns below. \n\n---\n\n**Weaknesses**\n\n**Q1: It is not clear to me how the method can provide a computational speedup.**\n\nA1: Thanks for your suggestion. We evaluated MoSo and the other baseline methods on a server with 8 Tesla V100 GPUs. We used the CIFAR-100 dataset and the ResNet50 backbone for our experiments. \n\nMoSo achieves the best trade-off between computational requirements and performance, making it the best-performing model with reasonable computational demands. Notably, it outperforms the state-of-the-art method, Moderate, while being more efficient. \n\nThe overall time cost of MoSo (102.7 min) and re-training the network on the selected subset (61.7 min) is less than directly training a network on the full set (192.2 min). What's more, our method offers more possibilities for the efficient storage of data and the subsequent efficient training of more models. \n\n\n\n|  Method   | Time-cost (surrogate training)  | Time-cost (scoring)| Time-cost (total)| Accuracy (Pruning-ratio 60%)|\n|  ----  | ----  | ----  | ----  |  ----  |\n| Random  | 0 | 0 |0  | 64.32 | \n| GraNd  | 192.2 m | 683.8 m | 876.0 m  | 60.52 |\n| OPT  | 192.2 m | $\\geq 1$day | $\\geq 1$day | 58.93 |\n| Moderate  | 192.2 m | **6.63 m** | 198.8 m| 64.92 |\n| MoSo  | **46.5 m** | 56.2 m | 102.7 m | **68.97** (within 61.7 min) | \n\n\n\n**Q2: The claimed asymptotic computation times are difficult to understand. It is not clear why the original MoSo score “takes $O(Tn^2)$ time and how the approximation in Eq. (4) is faster.**\n\nA2: We will clarify this below. Hope it can address your concern. MoSo without approximation requires $n$ times full training of the network, with each training a network on $n-1$ data samples for $T$ epochs. Consequently, it has a theoretical complexity of $O(Tn(n-1)) \\approx O(Tn^2)$. Our MoSo estimator avoids this costly leave-one-out retraining. It only require training a network on the full dataset ($n$ data samples) for $T$ epochs. Thus, the time complexity is substantially reduced to $O(Tn)$, providing a notable gain in efficiency. \n\n\n**Q3: The claim that randomly sampling a few time steps rather than considering all T steps “reduces the overall complexity to be less than O(Tn)” does not seem sound since the expectation of a uniform sample from {1,...,T} is (1+T)/2.**\n\nA3: We would like to clarify that the time complexity primarily concerns the number of iterations needed to compute the required gradients in Equation 4, which is the most time-consuming process. Assuming the surrogate network is trained with T steps (T=50), our MoSo estimator requires estimating the gradients at each iteration, resulting in an O(Tn) time cost. In our implementation, we found that this process can be accelerated by randomly sampling t steps (t=10,t<T) from all the T steps (Line 231) to perform gradient estimation and take their average. So the actual complexity is O(tn) which is less than O(Tn) as t<T. Figure 2b in the paper shows the effect of the sampling ratio (t/T), demonstrating that such a sampling operation trades a slight drop in performance for a 5-fold increase in speed. \n\n\n**Q4: Only the ResNet50 architecture is used exclusively throughout the experiments to construct the pruned datasets. Diversity of architecture in the evaluations would have strengthened the method’s appeal.**\n\nA4: Thanks! According to your suggestion, we conduct experiments on various architectures and report the results in the following table. Notably, the generalization ability of MoSo is well since the data is scored by using ResNet-50 as the surrogate network. \n\n\n|  Network | Dataset  | Random (PR: 80%)| MoSo (PR: 80%) |\n|  ----  | ----  | ----  |  ----  | \n| GoogleNet  | C-100 | 59.2 |  62.37 |\n| MobileNetV2  | C-100 | 49.25 |  51.31 |\n| DenseNet121  | C-100 | 56.92 |  57.49 |\n| Swin-T  | IN-1K | 67.20 |  72.66 |\n\n\n\n**Q5: The computational complexity of the method is quite high as it requires training the model on the entire dataset relative to the compared methods.**\n\nA5: Pre-training a surrogate network before pruning is a commonly-used procedure. Almost all the compared methods except random selection require training a surrogate network on the full dataset before pruning. The previous pruning methods need to train the surrogate network until convergence, normally using the same number of epochs as training on the pruned dataset (e.g., 200 epochs on CIFAR-100). Notably, our MoSo does not require full convergence of the surrogate network, for example, we only use 50 epochs on CIFAR100 instead of the original 200 epochs. In summary, our MoSo achieves better performance with less computational cost. \n\n\n**[Questions]. Why the original MoSo score “takes $O(Tn^2)$ time and how the approximation in Eq. (4) is faster?**\n\nThank you for the feedback. Please refer to A2. \n\n\n**[Q6] What is the appeal of the data pruning method from a practical efficiency perspective**\n\nThanks for your comments! First, I think there must be some misunderstanding about “MoSo need (T+1)/2 training epochs”. Please refer to A3, which will address your question. \n\nWith the smaller but informative subset selected by MoSo (e.g. only 20% of the data), we can do many things, like reducing storage overhead, decreasing training cost for training subsequent models [A], and even enabling continual learning [B]. \n\n[A] Cody Coleman, et.al.: Selection via Proxy: Efficient Data Selection for Deep Learning. ICLR-2020.\n\n[B] Jachong Yoon, et.al.: Online Coreset Selection for Rehearsal-based Continual Learning. ICLR-2022.\n\n"}, {"review_id": "cq3gVRGo8E", "reviewer": "Reviewer_XiFz", "summary": "This paper proposes a framework for data pruning that retains important samples while considering the training dynamics. While the overall methodology relies on analyzing the change in empirical risk from removing individual points, the paper introduces a first-order approximation algorithm that can be efficiently computed. Numerical results demonstrate the effectiveness of the method.", "questions": "Please see comments about Proposition 1.1", "limitations": "The paper includes a discussion on limitations in the Appendix.", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "-\tThe motivating idea is intuitive.\n-\tNumerical results on CIFAR100 and TinyImagenet suggest the method is effective.\n", "weaknesses": "-\tThe proof for Proposition 1.1 seems to be incorrect. Specifically $L(S/z, w)$ is defined as $L(S,w) – l(z, w) / N$, however this ignores that the empirical risk when we remove a point also needs to be re-normalized to $1/(N-1)$. I believe this breaks the proof steps from page 4 onwards. I suspect that this mis-specification carries on to the remaining theoretical analysis as well.\n-\tThe mathematical presentation is also generally unclear. \n - For example, in the Proof to Proposition 1.1., $L^t$ is used without definition.\n - In Proposition 1.2, the loss function is assumed Lipschitz in parameters for fixed data, but what the loss function is Lipschitz in is not clear.\n-\tMinor comment: there are also general presentation issues and errors in the main paper, although the authors have caught revisions in the Appendix.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer XiFz: \n\nThank you also for your constructive suggestions. We will carefully address each of your concerns and revise the manuscript accordingly.  If you have any new feedback please do not hesitate to let us know! We will do our best to answer your feedback!  \n\n---\n\n**Q1: The proof for Proposition 1.1 seems to be incorrect. Specifically, $L(S/z, w)$ is defined as L(S, w) - l(z, w)/N, however, this ignores that the empirical risk when we remove a point also needs to be re-normalized to 1/(N-1).**\n\nA1: Thanks! Let me address your concern. In fact, the approximation of this coefficient is not wrong but is common and necessary. We can explain this in ways.\n\n\n1. Since N is very large in practice (e.g., 1M for ImageNet-1K), hence, the difference between $\\frac{1}{N}$ and $\\frac{1}{N-1}$ is negligible.\n\n2. Such an approximation is widely used by many previous works, most notably the ICML-2017 Best Paper [A] and its countless follow-ups. Please check Section 2.1 of the paper [A]. \n\n3. Following your suggestion, we also present an approximator based on the exact coefficient $\\frac{1}{N-1}$ according to your suggestion, that is, $$M(z) \\approx E_{t}\\Big( \\frac{\\eta_t (2N-3)}{(N-1)^2} ||G^t||^2 - \\frac{\\eta_t}{(N-1)^2} ||g^t||^2 + \\frac{\\eta_t(2N-4)}{(N-1)^2} (G^t)^\\mathrm{T}g^t\\Big),$$ where $G^t = \\nabla L(S, w^{t}_S)$, $g^t = \\nabla l(z, w^t_S)$, $\\eta_t$ is the learning rate, and N is the number of all training data. \n\nWe applied the new estimator to data pruning experiments on CIFAR-100, comparing it to the original MoSo estimator. The new estimator behaves similarly to the original one. \n\n|  Estimator   | Pruning-ratio 20%  | Pruning-ratio 40% | Pruning-ratio 60% | Pruning-ratio 80%|\n|  ----  | ----  | ----  | ----  |  ----  |\n| Original estimator in the paper | 75.76 | **74.29** | **68.97**  | 54.38 | \n| New estimator derived here | **75.81** | 73.95 | 68.48  | **54.45** |\n\n\n\n**Q2-1: The unclear mathematical presentation: in the Proof to Proposition 1.1., $L^t$ is used without definition.**\n\nA2-1: Thank you for the feedback. The loss functions $L(\\cdot)$ and $l(\\cdot)$are defined in Line 158 of the main paper. The superscript t refers to the t-th training epoch, as noted in Line 94 of the supplementary material. $L^t$ represents the loss value at epoch t. We will clarify these definitions in the revised paper.\n\n\n**Q2-2: The unclear mathematical presentation: In Proposition 1.2, the loss function is assumed Lipschitz in parameters for fixed data, but what the loss function is Lipschitz is not clear.**\n\nA2-2: Thank you for pointing this out. The proof relies only on the Lipschitz-continuity assumption for parameters, not the specific loss function. This suggests MoSo could apply more broadly, like data reduction for multimodal pretraining. In the paper, we state the loss function used is cross-entropy (Lines 125/133/138 in the main paper). The proof's generality indicates MoSo's potential beyond classification tasks. We will clarify that the proof holds for any continuously differentiable loss function satisfying Lipschitz continuity.\n\n**Q3: Minor comment: there are also general presentation issues and errors in the main paper, although the authors have caught revisions in the Appendix.**\n\nA3: Thanks. We will further check and polish the presentation in the revised paper.\n\n\n[A] Koh P W, Liang P. Understanding black-box predictions via influence functions. ICML-2017. \n\n\n"}, {"review_id": "Jp0DwaKcUn", "reviewer": "Reviewer_DWe5", "summary": "The paper proposes a new method called moving-on-sample-out (MoSo) to remove less informative samples from the training data. The criteria for removed samples is based on the change in the optimal empirical risk when the sample is removed. As exact calculation of the criterion is computationally challenging, the authors propose an estimator based on gradient information. MoSo shows empirical success compared to baseline methods in data pruning, generalization between networks, and robustness to label noise.", "questions": "Questions:\n- Q1: In Algorithm 1, line 1: What is $\\phi$?\n- Q2: How many runs were conducted? Are the aggregated statistics averages over multiple runs? What do the error bars represent? Can you clarify?\n- Q3: What is the implication of Proposition 1.2? How close is the gap of the estimator? \n- Q4: Regarding the paragraph about robustness to label noise. It is claimed that MoSo \"select informative and clean samples\" (line 288). However, it is unclear how MoSo is able to distinguish between informative and clean samples as only test accuracies are compared in Table 5. Is it possible to analyze which fraction of the pruned samples are clean and which are informative?\n- Q5: Does MoSo suggest an optimal pruning ratio, e.g., by a meaningful cut-off in the distribution of scores? \n- Q6: Is it possible to analyze whether MoSo actually selects \"representative\" samples? For example by comparing how a network trained on the pruned data performs on the full test set.\n- Q7: In Figure 2(a), there is a method called \"random\". It is unclear what this method does. I assume random data points get pruned, i.e., the score is uniform among all data points and so is the selection distribution. Can you clarify?\n- Q8: The exact scenario in which training ImageNet would take 45 years (line 152) in unclear. Can you clarify?\n\n\nPreferential comments:\n- When listing many references as in the introduction it is easier to read if they are sorted [1,2,3,4] instead of [4,1,3,2].\n- In the results tables bold the best numbers, as well as those with standard errors that overlap with the best method for fair highlighting of the best results.\n- Inconsistent presentation of tables. While in Tables 1-3 there are vertical lines between methods, results and avg rank, those lines are missing in Tables 4 and 5.\n- The statement \"famous influence function\" (line 188) may be inappropriate.\n\nTypos/grammar/other:\n- Potentially missing related work:\n\t- Mindermann, S., Brauner, J. M., Razzak, M. T., Sharma, M., Kirsch, A., Xu, W., ... & Gal, Y. (2022, June). Prioritized training on points that are learnable, worth learning, and not yet learnt. In International Conference on Machine Learning (pp. 15630-15649). PMLR.\n- References [33] and [34] are the same paper.\n- Inconsistent spelling: \"core set\", \"core-set\", \"coreset\"\n- Why are there full stops after enumeration marks, i.e., (i). and (ii).?\n- Whenever I read \"our MoSo\" I have the feeling a word is missing, like \"our MoSo score\" or \"our MoSo approach\" especially if I expand MoSo (what it stand for).\n- lines 117-121, 136, 187: I am not sure why *will* appears here. This is not the case later on, for example in lines 211-215.\n- line 123: we focus on **a** classification task?\n- line 124: i.i.d. (last dot is missing)\n- line 126: I would appreciate if you could specify the spaces of newly introduced variables, i.e., $\\delta \\in (0,1)$. Same holds for $\\eta$.\n- line 126: Please introduce $\\mathbf{w}$.\n- Equations (2) and (6): Is there an empty line in LaTeX before the equation? That would explain the spacing above the equation.\n- line 137: Please state once that by $z$ you mean a pair $(x,y)$.\n- line 157: Why \"could\" and not \"can\"?\n- Equation (4) and more: I think the transpose symbol and $T$ are too close. Especially in the supplement where $T$ also appears as an superscript. I would use another transpose symbol, i.e., `\\newcommand*{\\transpose}{{\\mkern-1.5mu\\mathsf{T}}}` (looks like $\\newcommand*{\\transpose}{{\\mkern-1.5mu\\mathsf{T}}}$) which follows the (DIN) EN ISO 80000-2:2013 standard\n- line 187: Why are 1.1 and 1.2 not clickable references?\n- line 193: There is no Proposition 1.\n- line 203: Please name $I$ as the number of subsets.\n- line 252: additional blank space\n- line 256: remove 'when'\n- line 257: doesn't -> does not\n- Sometimes I see $z:(x,y)$ or $\\epsilon:0$ in which I read and interpret the colon symbol as an equal sign and I think this notation is confusing for some people. \n- It would have helped to start the counters (line numbers, equations, etc) in the supplementary material from the counters of the main paper.\n- Appendix Equation (5): $\\mathcal{L}$ is a function, not a set (below the sum symbol). I guess $\\mathcal{S}$ is meant here. Also, consider putting brackets around the terms to clarify that both terms are within the sum! As mentioned earlier, I consider the notation $\\epsilon:0$ confusing.", "limitations": "Limitations are only mentioned in the supplementary material but could be more rigorously discussed in the main text.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The method is based on a simple yet effective idea.\n- The computational complexity problem of MoSo is effectively tackled with the proposed estimator.\n- In the experimental section a wide range of comparison methods are used as baselines.\n- An ablation study is performed to detail the necessity of sub-elements of the method.\n- The paper is fairly easy to follow.\n- MoSo is shown to outperform baseline methods in data pruning, generalization between networks, and robustness to label noise in terms of accuracy.", "weaknesses": "Main points:\n- The justification for the gradient based estimator of MoSo is solely based on intuition. A more rigorous justification would be desirable. \n- The initial motivation in the introduction (line 26) states that data pruning ideas can be used to reduce training time. However, within the experimental section, only the accuracy is compared to baseline methods. It would be interesting to see how MoSo compares to baseline methods in terms of training time. Especially because random seems to perform so good and takes essentially no time to score and sample.\n- It is mentioned that MoSo is aware of training dynamics (line 57). However, it is not entirely clear what is meant by *awareness* and what part of the method is responsible for this. Furthermore, it is not entirely clear how this is different from other methods that use gradients to prune data and why it should be utilized.\n- The conclusion of Proposition 1.2 is not discussed in the main text. It would be interesting to see how close the estimator is to the true criterion. This could even be done in an experimental setting comparable to the ablation in Figure 2(b).\n\nMinor points:\n- While Tables 1,2,3 are detailed, the same results are already summarized in Figure 1. Hence, those tables seem redundant if the error bars are included in Figure 1 and the tables could be moved to the supplementary material.\n- Initially, it is unclear that MoSo requires to train a surrogate model to estimate the criterion. This should be highlighted earlier and compared to baseline methods.\n- Within the experimental section, (all tables and Figure 2(b)) it is unclear how many runs the results are averaged over and if the errors are standard deviations or some other measure of uncertainty.\n- Within the experimental section, it is unclear how the hyperparameters were chosen for the baseline methods.\n- Algorithm 1, line 1: $\\phi$ is not defined/discussed.\n- The statement \"this suggests that time step sampling is a useful technique for improving the efficiency of our method\" in line 305 is not supported by the results in Figure 2(b).\n\nAfter the Rebuttal:\nI have read all other reviews and all rebuttals. Furthermore, I thank the authors for their answers. I keep my original score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Sincerely thanks for your appreciation of our work. Hoping our response will address your concerns.\n\n---\n\n**Q1: A rigorous justification of MoSo is desirable.**\n\nA1: Thanks! Proposition 1.2 gives rigorous proof of the approximation accuracy, and we have also updated it in the support material to give a tighter bound. Here, we restate a conclusion: \n$$|M(z) - \\hat{M}(z)| \\leq  O((\\ell \\eta + 1)gT + \\eta g^2T).$$ MoSo assigns high scores to samples that can reduce the empirical risk. Please refer to Line 112 in the supplementary material for details. \n\n**Q2: How data pruning ideas can be used to reduce training time.**\n\nA2: Thanks! We compare the training efficiency of our MoSo approach with baselines on CIFAR-100 using ResNet50, with 8 Tesla V100 GPUs. MoSo achieves the best trade-off between computational requirements and performance, making it the best-performing model with reasonable computational demands. The overall time cost of MoSo (102.7 min) and re-training the network on the selected subset (61.7 min) is less than directly training a network on the full set (192.2 min). What's more, our method offers more possibilities for the efficient storage of data and the subsequent efficient training of more models [A]. \n\n|  Method   | Time-cost (surrogate training)  | Time-cost (scoring)| Time-cost (total)| Accuracy (Pruning-ratio 60%)|\n|  ----  | ----  | ----  | ----  |  ----  |\n| Random  | 0 | 0 |0  | 64.32 | \n| GraNd  | 192.2 m | 683.8 m | 876.0 m  | 60.52 |\n| OPT  | 192.2 m | $\\geq 1$day | $\\geq 1$day | 58.93 |\n| Moderate  | 192.2 m | **6.63 m** | 198.8 m| 64.92 |\n| MoSo  | **46.5 m** | 56.2 m | 102.7 m | **68.97** (within 61.7 min) | \n\n\n**Q3: What is meant by awareness and what part is responsible for this?**\n\nA3: Thanks! The awareness of training dynamics is to consider the network information at different stages of the training process. The average across different epochs in Proposition 1.1 is responsible for this. Please refer to Figure 2(a) in the paper for the ablation of this part. \n\n**Q4: The difference from other gradient-based methods.**\n\nGraNd is the best-known scheme that also uses gradient information for data pruning. GraNd retains samples with large gradient norms, while our MoSo approach uses the gradient vector which retains more potentially useful information than the norm and approximates the empirical risk. \n\n\n**Q5-1: The conclusion of Proposition 1.2 is not discussed.**\n\nPlease refer to A1. And we will add further discussion about this. \n\n**Q5-2: How close the estimator is to the true criterion?**\n\nA5-2: Good question! Because of the word limit, please check Q1 in Global-Rebuttal (https://openreview.net/forum?id=vO6ZdPWaHc&noteId=DsrmXiWeKr) for details. \n\n\n**Q6&7: The same results in Tables 1/2/3 are already summarized in Figure 1. It should be highlighted that MoSo requires training a surrogate model to estimate the criterion.**\n\nA6&7: Thanks, we accept your suggestions and will make modifications accordingly!\n \n**Q8: About the number of runs and the kind of errors.**\n\nA8: The results are the average of 5 independent runs. The standard deviation is selected as the measure of uncertainty.   \n\n**Q9: How the hyperparameters were chosen for the baseline methods?**\n\nThanks! Regarding the experimental settings for the baselines and our MoSo approach, we largely followed the framework used in the Moderate paper for fairness of comparison. \n\n**Q10: That is the meaning of $\\phi$.**\n\nA10: $\\phi$ means the null set. \n\n**Q11: The statement in line 305 is not supported by Figure 2(b).**\n\nA11: Thanks for the careful review! We will add the computational cost comparison and delete this statement. \n\n**Q12: What is the implication of Proposition 1.2?**\n\nThanks! Please refer to A1.\n\n**Q13: Is it possible to analyze which fraction of the pruned samples are clean and which are informative?**\n\nA13:  Thanks! This is a good question! We present detailed statistics on TinyImageNet with 20% label noise, totaling 100,000 data samples. After pruning 80% of the data with either MoSo or random selection, we observe MoSo reduces the noise ratio of the retained data (from 20% to 14%). \n\n|  MoSo | Noisy  data| Clean data | Noise Ratio|\n|  ----  | ----  | ----  |  ----  | \n| Retained subset  | 2795  |  17205   |  14% |\n| Discarded (Pruned)   | 17205   |  62795  | 22% |\n\n**Q14: Does MoSo suggest an optimal pruning ratio?**\n\nAns: Good question! We think it should be artificially defined since it balances efficiency and performance. What MoSo now can do is provide a good pruning suggestion given the pre-defined pruning ratio. \n\n\n**Q15: Whether MoSo actually selects \"representative\" samples?**\n\nA15: Good question! Here, we compare networks trained on the subset with top-20% largest MoSo scores and the subset with 20% smallest MoSo scores. The former is significantly better than the latter, with a 7% higher top-1 accuracy. This confirms that MoSo-score can reflect the importance of samples to some extent. \n\n|  Subset   | top-1 acc on CIFAR-100|\n|  ----  | ----  | \n| largest 20%| 54.38 | \n| smallest 20%| 47.99|\n\n\n**Q16: In Figure 2(a), what is the method called \"random\"?**\n\nA16: Thanks! Random (selection) means a completely random selection from a data set. It is a strong baseline as many methods cannot beat it. \n\n**Q17: The exact scenario in which training ImageNet would take 45 years (line 152) is unclear.**\n\nA17: Thanks! Considering the fastest case, before scoring a sample, we choose a small surrogate network with unsupervised initialization and only finetune the last layer. Such a process needs  $>23$ mins. So, the overall time cost for scoring all (1 million) samples is at least about $45$ years.  \n\n[A] Cody Coleman, et.al.: Selection via Proxy: Efficient Data Selection for Deep Learning. ICLR-2020.\n"}]

Author rebuttal:
**Q1: How close the estimator is to the true criterion?**

A1: This is a good question! We will add this to the revised paper! 

We compare the approximation error comparison between ours and the well-known influence function, please refer to Figure 1 in the PDF attachment. Our method exhibits better approximation performance, with a Spearman correlation of 0.45041617686 to the real MoSo value, while the influence function is only with a Spearman correlation of 0.03515931916 to the real value. 

**Q2: Does the pruning change the data sample distribution, and does the method improve/hurt certain classes?**

A2: Thanks for the constructive question! We will add this to the revised paper! 

We visualize the class-wise accuracy before and after applying our MoSo data pruning approach, please refer to Figure 2 in the PDF attachment. We can observe that the correlation between the two is very significant, where the Spearman correlation coefficient is 0.9133613248, and the P value is 0.0295558770. This shows that the performances before and after being pruned with MoSo are quite consistent, and no significant improvement or harm to a particular category was observed.

We investigated whether the data in each category was balanced after applying our MoSo data pruning approach, please refer to Figure 2 in the PDF attachment. 
Ideally, in the most balanced case, the number of data in each category is 100. 
It is not difficult to find that the number of data categories is quite balanced for our approach, where the mean is 99.99, var is 9.006. 









Meta-review: Finding efficient ways to approximate the importance of individual data points is a critical problem. However, it is very expensive to perform methods like memorization score which require performing a variant of leave-one-out training. This paper proposes MoSo, which approximates the importance of individual data points by measuring the correlation between the gradient of each data point and the average gradient. Using this criterion, the authors demonstrated improved performance as data are removed, particularly for high pruning rates. 

Reviewers generally found the paper's topic important, experiments well done and results compelling. I recommend acceptance.
Decision: Accept (poster)