Data Pruning via Moving-one-Sample-out

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.

Strengths

- The method is based on a simple yet effective idea. - The computational complexity problem of MoSo is effectively tackled with the proposed estimator. - In the experimental section a wide range of comparison methods are used as baselines. - An ablation study is performed to detail the necessity of sub-elements of the method. - The paper is fairly easy to follow. - 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: - The justification for the gradient based estimator of MoSo is solely based on intuition. A more rigorous justification would be desirable. - 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. - 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. - 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). Minor points: - 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. - 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. - 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. - Within the experimental section, it is unclear how the hyperparameters were chosen for the baseline methods. - Algorithm 1, line 1: $\phi$ is not defined/discussed. - 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). After the Rebuttal: I have read all other reviews and all rebuttals. Furthermore, I thank the authors for their answers. I keep my original score.

Questions

Questions: - Q1: In Algorithm 1, line 1: What is $\phi$? - Q2: How many runs were conducted? Are the aggregated statistics averages over multiple runs? What do the error bars represent? Can you clarify? - Q3: What is the implication of Proposition 1.2? How close is the gap of the estimator? - 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? - Q5: Does MoSo suggest an optimal pruning ratio, e.g., by a meaningful cut-off in the distribution of scores? - 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. - 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? - Q8: The exact scenario in which training ImageNet would take 45 years (line 152) in unclear. Can you clarify? Preferential comments: - 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]. - 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. - 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. - The statement "famous influence function" (line 188) may be inappropriate. Typos/grammar/other: - Potentially missing related work: - 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. - References [33] and [34] are the same paper. - Inconsistent spelling: "core set", "core-set", "coreset" - Why are there full stops after enumeration marks, i.e., (i). and (ii).? - 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). - 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. - line 123: we focus on **a** classification task? - line 124: i.i.d. (last dot is missing) - 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$. - line 126: Please introduce $\mathbf{w}$. - Equations (2) and (6): Is there an empty line in LaTeX before the equation? That would explain the spacing above the equation. - line 137: Please state once that by $z$ you mean a pair $(x,y)$. - line 157: Why "could" and not "can"? - 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 - line 187: Why are 1.1 and 1.2 not clickable references? - line 193: There is no Proposition 1. - line 203: Please name $I$ as the number of subsets. - line 252: additional blank space - line 256: remove 'when' - line 257: doesn't -> does not - 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. - It would have helped to start the counters (line numbers, equations, etc) in the supplementary material from the counters of the main paper. - 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are only mentioned in the supplementary material but could be more rigorously discussed in the main text.

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.

Strengths

- The motivating idea is intuitive. - Numerical results on CIFAR100 and TinyImagenet suggest the method is effective.

Weaknesses

- 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)$. 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. - The mathematical presentation is also generally unclear. - For example, in the Proof to Proposition 1.1., $L^t$ is used without definition. - 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. - Minor comment: there are also general presentation issues and errors in the main paper, although the authors have caught revisions in the Appendix.

Questions

Please see comments about Proposition 1.1

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

1 poor

Presentation

2 fair

Contribution

2 fair

Limitations

The paper includes a discussion on limitations in the Appendix.

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.

Strengths

* The proposed approximation of the MoSo score and the accompanying analysis are sound and novel to the best of my knowledge. * The authors present theoretical results establishing the accuracy of their approximation. * 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. * 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. * 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$. * 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. * The computational complexity of the method is quite high as it requires training the model on the entire dataset relative to the compared methods.

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? 2. 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$. 3. 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes, they are mentioned in the supplementary material.

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.

Strengths

- Good presentation: method is clear and contextualized properly through related work and comparison experiments - Good results: MoSo does better on all datasets evaluated than the comparison baselines - Method seems new and is differentiated from related work - 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.

Questions

See weaknesses Is there a reason why experiments aren't done on CIFAR-10? This seems to be a standard benchmark for this line of work. 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)

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Addressed in weaknesses - lack of analysis on computational cost.

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.

Strengths

[1] The proposed measure of sample importance is intuitive, and the approximation appears novel. [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.

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. [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?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors didn't discuss limitations in the paper.

Thanks for the response

Thanks for the response. My concern with the $1/N \approx 1/(N-1)$ approximation is that in the original influence functions paper [A], this is not used for a rigorous proof (c.f. Proposition 1.1). However in this draft, M(z) given in definition 1 is different from M(z) redefined in line 94-95 of the Supplement. I agree that this difference may be small in practice and I commend the authors for deriving a corrected version of the approximation and for running some experiments showing that the corrected version does not yield a major difference from the initial. I encourage the authors to revise the paper, for example by beginning with the rigorous version and then demonstrating approximations or by forgoing the theoretical statements and presenting the approximator via mathematical steps.

Rebuttal Response

Additional experiments and visualization provide further details to understand the proposed method. Thank the author's response, and I am happy to increase my score.

Sincerely thanks for the response!

We sincerely thank the reviewer for their generosity in time and feedback, and we are also incredibly grateful to the reviewer for their willingness to reconsider and increase their score after reviewing our detailed response! We are excited to continue refining the work guided by the reviewer's suggestions!