BWS: Best Window Selection Based on Sample Scores for Data Pruning across Broad Ranges

We sincerely thank the reviewer for the constructive feedback. Hope this response answers the reviewer’s questions.

1. For the experiments on CIFAR-10 with noise, the proposed method is outperformed by Moderate DS for 3 ratios. Could the authors illustrate the noisy rate of the selected subset to check whether the proposed method is prone to choose noisy data under this setting?

Below we compare the noisy rate of the selected subset (the fraction of label-noise data in the subset) between our method (BWS) and Moderate DS for the label-noise experiment reported in Fig. 4(c), considering 20% label-noise in CIFAR-10 dataset. We can see that the noise rate is comparable or relatively lower for Moderate DS across the subset ratios (10-40%), which could be a potential reason for Moderate DS’s outperformance for some cases.

To further compare these two methods, we additionally conducted a label-noise experiment by increasing the noise rate to 40%. We remind that Moderate-DS selects samples closest to the median of the features of each class, which can be interpreted as selecting moderate difficulty samples first. When the noise rate is as high as 40%, the top 40% difficult samples include many label-noise samples. Thus, Moderate-DS starts to include these noisy samples when the subset ratio becomes higher than a certain portion. On the other hand, since our method solves the proxy task to choose the best window subset of the highest accuracy while varying the starting point of the window, our method is still robust even for high noise ratio and relatively large subset portion. The table below compares the two methods in this scenario, and we can see that the performance of Moderate-DS degrades significantly at the subset ratio of 40%, while our method maintains its performance.

2. The experiments on CIFAR-10 fine-tuning on VIT shows that CCS is consistently better than the proposed method, could the author give concrete analysis of this phenomenon?

We apologize for the confusion originated from our previous report for CCS on VIT. There was some unintentional inconsistency in our experimental setup and we found that the pretrained ViT parameters were different (by using different versions of timm library) only for CCS in our previous experiment on VIT, which caused significantly better outcomes for CCS compared to other methodologies for some subset ratios. We have updated the paper with the revised results by matching the experimental conditions for CCS with other algorithms, and found that our method (BWS) outperforms CCS on the fine-tuning of VIT as summarized in the table below.

2. It would be intriguing to explore the broader scenario where a "window" comprises several smaller intervals and varying starting points.

We appreciate the reviewer for the interesting suggestion. We conducted an additional experiment on the CIFAR-10 dataset for finding the optimal two half-width windows while varying their starting points. In detail, for a subset of size $w$%, we searched over all combinations of two half-width windows, denoted by $[x_1, x_1+w/2] \cup [x_2, x_2+w/2]$ while varying their starting points $(x_1, x_2)$ in $x_1\in[0, 100-w]$ and $x_2\in [x_1+w/2, 100-w/2]$ with a step size of 5%. We trained ResNet18 on each subset and checked the corresponding test accuracies. Below we report the top five results (the compositions of half-width windows and their test accuracies) for subset ratios ranging from 10 to 40%. We highlight the cases where the two half-width windows are contiguous to each other with bold letters.

We can observe that for every considered subset ratio, the top-five best performing cases include contiguous windows (or windows near to each other with the gap of only 5%), even though we allowed flexibility in choosing the two half-width windows far away from each other. This result further supports our claim (in the response to the reviewer’s first question) that our window selection, which chooses a continuous interval of samples based on difficulty scores, successfully finds the near-optimal subset in an efficient manner across a broad range of selection ratios. The related results are added in Appendix G.3 of our revised paper.

3. Figure 3's readability could be enhanced by employing more distinguishable colors and markers for clarity.

We modified the figures (Figure 3, 4 and 6) by adding markers for better readability. Thank you for your feedback.

We sincerely appreciate the reviewer for the feedback. Hope this response answers the reviewer’s questions.

1. The notion of a "window" refers to a fixed-length interval within a sorted dataset. The "Best Window Selection (BWS)" algorithm operates under the assumption that the most optimal subset should be contiguous regarding the level of difficulty. However, the paper lacks an in-depth analysis of this particular aspect.

We’d like to highlight that the rationale behind the “window” selection from a sorted dataset mainly lies on two critical merits of this approach: 1) computational efficiency in searching for the optimal subset and 2) flexibility in choosing the data subset, enabling the selection of easy, moderate, or hard data subsets. In particular, this flexibility is pivotal in achieving competitive performances across a broad range of selection ratios.

As pointed out by the reviewer, the optimal subset might not be necessarily strictly contiguous in terms of the difficulty level of the samples. However, our theoretical analysis in Sec. 3.1 and the ablation study in Table 3 deliver some insights on the benefit of choosing samples from the continuous interval. First of all, in the simple toy example of binary classification problem introduced in Sec. 3.1, we show that the difficulty level of the optimal subset indeed changes depending on the subset size. In particular, for sample-deficient regimes, it is better to select easy samples (that are farther from the decision boundary), while selecting difficult samples (closer to the decision boundary) is more beneficial for sample-sufficient regimes. This theoretical analysis aligns well with the empirical findings (summarized in Table 1) that the previous score-based selection methods, which select rare or difficult-to-classify samples, achieve a better performance in high selection ratios, while the coreset selection methods, which select representative samples approximating the average behavior of the total dataset, achieves a stronger performance in low selection ratios. So, we can see that the optimal subset should be composed of relatively easy (hard) samples in low (high) selection ratios.

Then, the remaining question is whether there exists such a desirable difficulty level for the subset in the intermediate selection ratios. We do not provide theoretical analysis on this aspect, but present some empirical evidence in our ablation study. In particular, our ablation study in Table 3 compares different types of subsets (in addition to the hard-only or easy-only windows), such as “Hard-easy”, which combines the easy and hard samples with equal proportions or “25-75%”, which includes random samples from a moderate regime after pruning a fixed portion of too easy or hard samples. Compared to these non-contiguous subset selection methods, our window selection consistently achieves better performance over all the selection ratios (10 to 40%) by cleverly choosing the window starting point. This ablation study, combined with our pruning experiment results summarized in Figure 4, partly demonstrate that our window selection, which prunes top $s$% of the most difficult samples and top $(100-w-s)$% of the easiest samples with a properly chosen $s$ for a fixed width of $w$%, provides a good enough flexibility in choosing a subset of competitive performances across a broad range of selection ratios.

Lastly, we provide further evidence that even though our method selects samples from a contiguous range of difficulty level, our subset maintains diversity in sample selection (in the embedding space), which is often considered as a desirable criteria in subset selection. To show this, we compute the coverage (%) of the full dataset from the $k$-nearest neighbors of the selected samples from our method (BWS), and compare this coverage with that of random selection. For example, for the subset ratio of 10% and $k=3$, if the coverage is 30%, it means that all the selected samples do not share their neighborhoods within distance 3 in the embedding space. The tables below show that the coverage of our method is as high as that of the random selection, showing that selecting samples of similar difficulty does not reduce the sample diversity in the embedding space compared to the random selection.

The portion included in the 3-nearest neighborhood (k=3)

The portion included in the 5-nearest neighborhood (k=5)

3. The baseline evaluation results are inconsistent with data reported in the baseline method. For example, moderate are reported to have better performance than random on CIFAR10. CCS seems to have a better performance at 10% subset ratio than the numbers reported in the paper. It may be good to explain why the difference exists.

The differences between our CCS [f] numbers and those reported in the original paper stem from variations in the hyperparameter, $\beta$, employed within the algorithm. CCS prunes a $\beta$% of hard examples, with $\beta$ being a hyperparameter, and then selects samples with a uniform difficulty score distribution. Considering $\beta$ as a one-sided threshold for the window subset, tuning this parameter can be viewed as an oracle window search within our algorithm. Thus, for a fair comparison we set beta to 0 for all the pruning ratios, and this makes our evaluation of CCS the same as the 'stratified only' algorithm in Table 2 of the CCS paper. When we set beta to 0, it operates optimally when the subset ratio is high but sub-optimally when the ratio is low. This observation also aligns with the findings in the CCS paper Fig 6(b). Below are the comparisons between the reported numbers for CCS in CIFAR-10 dataset.

For the moderate coreset [g], the results for CIFAR10 were not provided in the original paper, so we could not directly compare the numbers. In the case of CIFAR100, we reported better results as summarized in the table below. This discrepancy arises from differences in experimental settings; we preserve the number of iterations per epoch regardless of the subset ratio, whereas the original paper varies the iterations according to the subset ratio.

[f] Coverage-centric Coreset Selection for High Pruning Rates. H Zheng et al.

[g] Moderate Coreset: A Universal Method of Data Selection for Real-world Data-efficient Deep Learning. X Xia et al.

2. I don’t fully understand why the performance of $w\_s$ can represent the performance of models trained on the same subset. Could the authors further explain the connection between kernel regression and deep learning model training? What I currently feel is that it is more like an empirical transferability stuff studied in [1]: it is possible to use a small model to select coresets that transfer well to larger models. [1] Coleman, C., et al. "Selection via Proxy: Efficient Data Selection for Deep Learning." International Conference on Learning Representations (ICLR). 2020.

As the reviewer suggested, we can also consider an alternative proxy from (SVP, Section via Proxy) by evaluating the performance of each subset using a smaller network. To evaluate the efficiency of this approach, we conducted an additional experiment of finding the best window subset using a small ConvNet model on the CIFAR-10 dataset. The selected subset is then evaluated on ResNet18. The table below summarizes this result (SVP) compared to our original proxy (KRR, Kernel Ridge Regression) and the oracle window using the target model. The table below summarizes the result.

We can observe that SVP tends to select easier samples (windows with larger index) compared to the oracle window over the selection ratios 10% to 90%, which results in performance loss especially in high selection ratio regimes. Our proxy, on the other hand, exactly matches the oracle window performance at selection ratios of 10% to 90%. We conjecture that the tendency that SVP selects an easier subset is attributed to the limited capability of the simple network used in the proxy task. Moreover, we’d like to highlight that solving our proxy task takes only about 1/15-1/250 (varying depending on the subset size) of the computational time compared to SVP, which requires training of the small network (ConvNet) for all considered subsets. We added this result in Appendix B of our revised paper.

We sincerely thank the reviewer for the feedback. Hope this response answers the reviewer’s questions.

1. Using kernel ridge regression to decide the best window is not quite intuitive. What is the motivation to use kernel ridge regression rather than training a small network to decide the best window?

We appreciate the reviewer for addressing this important question. Our use of the kernel ridge regression as a proxy for training neural networks can be partly explained by the recent progress in theoretical understanding of training neural networks using kernel methods. In particular, some recent works [a,b,c,d] have shown that training and generalization of neural networks can be approximated by two associated kernel matrices: the Conjugate Kernel (CK) and Neural Tangent Kernel (NTK). The Conjugate Kernel is defined by the gram matrix of the derived features produced by the final hidden layer of the network, while NTK is the gram matrix of the Jacobian of in-sample predictions with respect to the network weights. These two kernels also have fundamental relations in terms of their eigenvalue distributions as analyzed in [e]. Our proxy task is motivated by observation that the kernel regression with these model-related kernels can provide a good approximation to the original model (under some assumptions such as enough width, random initialization, and small enough learning rate, etc.).

In particular, we use the Conjugate Kernel (CK) in our kernel ridge regression (Equation (2)), by defining the kernel matrix as ${\mathbf{X}\_\mathbf{S}}^\top {\mathbf{X}\_\mathbf{S}}$ where $\mathbf{X}\_\mathbf{S}=[\mathbf{f}\_1,\dots,\mathbf{f}\_m]$ is composed of features produced by the exact target network of our consideration (ResNet18 for CIFAR-10 and ResNet50 for CIFAR-100/ImageNet). By considering the features from the target network, we can obtain the (approximate) network predictions that are linear in these derived features. Of course, this kernel approximation of the neural network models, which assumes a fixed feature extractor, does not exactly match our situation where the selected subset not only affects the linear classifier but also the feature extractor itself during the training. However, we’d like to emphasize that this is a proxy that can reflect the network architecture of our interest in a computationally-efficient manner. Also, our analysis in Table 2 shows that this proxy finds the best window subset that aligns well with the result from the actual training of the full model.

[a] Radford M Neal. Bayesian learning for neural networks, 1995.

[b] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes, ICLR 2018.

[c] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net, NeurIPS 2019.

[d] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks, NeurIPS 2018.

[e] Zhou Fan and Zhichao Wang. Spectra of the Conjugate Kernel and Neural Tangent Kernel for Linear-Width Neural Networks, NeruIPS 2020.

Thank the authors for the response, and I am sorry for my delayed response. The author’s response addresses some of my questions, but some of my concerns still remain:

Although the response explains that SVP always selects easier samples, which is different from BWS, I still feel that BWS shares the same insights as SVP: BWS uses light machine models as a proxy to select the best window for coreset selection. This is also based on the hypothesis that the coreset selected by the proxy models transfers well to the target model, which can impact the novelty of the work.

The additional evaluation provided by the authors shows that BWS actually underperforms SOTA methods (it seems that the number reported is based on a different setting from the original paper). My understanding is that CCS needs more time to choose the Oracle window, but BTW can choose the window in a more efficient way with a trade-off on the drop of accuracy? If this is true, it can hurt the contribution of the work, and the paper should have a more explicit discussion of this trade-off.

Thank the reviewer for the comments. First, we’d like to point out that the main contributions of our paper are in two parts: 1) reducing the search space of coresets from $n\choose k$ to a constant number by considering the window subsets of a fixed step size and 2) providing a proxy task that can reflect the network architecture of our interest in a computationally-efficient manner. Furthermore, our experimental results demonstrate the superior performance of our approach compared to other baselines across a broad range of selection ratios over datasets, including CIFAR-10/100 and ImageNet, and the scenarios involving training from random initialization or fine-tuning of pre-trained models.

We’d like to further emphasize two crucial differences between SVP and BWS. First, unlike SVP that uses a small network and therefore can not fully reflect the information of the target model, BWS incorporates this information by utilizing features from the model of interest. Second, while training an (even simple) neural network for every different subset is computationally costly, BWS offers a highly efficient way in choosing the best window as solving a regression problem requires only a few seconds. We’d like to point out that our research is the first work theoretically demonstrating that the difficulty level of the optimal subset needs to vary depending on the subset size, and providing the novel and efficient window selection strategy from samples ordered by the difficulty score.

Regarding the CCS, CCS not only takes more time to choose the window but also requires tuning of a hyperparamter, which determines the one-sided threshold of the window, for pruning $\beta$% hard samples. The grid search for $\beta$ not only introduces extra costs in selecting effective coresets but also requires validation or test dataset to evaluate each window subset. The authors in CCS left the efficient search of finetuning $\beta$ for future work. On the other hand, our work does not have any hyperparameter to tune for the window search, since we propose a proxy task to choose the window subset without any validation or test dataset. We think that this main difference makes our work effectively applicable in practical data subset selection scenarios.

Furthermore, we’d like to highlight that the performance of BWS is higher even compared to the numbers reported in the original CCS paper obtained after finetuning $\beta$ for each selection ratio. This may come from the fact that our method prunes both easy and hard samples in the process of choosing the window subset, but CCS only prunes the hard samples and selects among the remaining samples with a uniform difficulty score distribution.

We would like to thank the reviewers again for their constructive comments. We have uploaded the revised version and responded to all the reviewers in detail. We would greatly appreciate it if the reviewers could kindly advise if our responses solve their concerns. Thank you for your time.

Sincerely,

Authors.