Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning

Thank you for your review of our work and the points you bring up. We answer your questions (weaknesses) below: **Weakness 1:** We clarify that while our results focus on the low data regime (<30% of the data each epoch) we do include results in the high data regime (>30%). In particular Figure 2a and Table 3 include results when training ResNet-18 on CIFAR10 for selection ratios up to 50%. Additionally, Table 5 contains results of training ResNet-18 on CIFAR100 and ImageNet 30 for selection ratios up to 90%. In this high data regime (>30%), our results support your intuition—that “harder” samples benefit model training. For example, in Table 3, for r=50%, SSP-Hard (self-supervised prototypes subset selection with hard examples; Sorscher et al., 2022) reaches 93.3% accuracy while SSP-Easy (self-supervised prototypes subset selection with easy examples) reaches 92.7%. **RS2 however, matches or outperforms all existing baseline methods—those which select “hard” or “easy” samples—in both the low and high data regimes.** For example, in the same setting as above, RS2 reaches 95.2% accuracy. We updated our manuscript to include a discussion of these results. **We also highlight that we conducted robustness experiments using noisy labels in our submission to investigate the behavior of RS2 and existing pruning methods on datasets with different properties** (e.g., noisy datasets; see Table 14 with selection ratios up to 50%). RS2 also outperforms baselines in this “noisier” setting. We agree that continued study of RS2 and data pruning methods over datasets with other properties is of interest for future work. **We plan to compare RS2 and baselines methods on two datasets with large intra-class variance and class-imbalance for our camera ready as suggested by Reviewer ph2c.** We provide initial results in that response under the section title Weakness 2/Question 4 (crossref. individual response to Reviewer ph2c). **Weakness 2:** We clarify that **the theoretical results on the generalization error of RS2 (Theorem 4.1) apply to both RS2 with replacement and RS2 without replacement**. The reason for this is that the proof depends only on the fact that the data is selected non-adaptively and in a data-independent fashion (true for both with and without replacement). We updated our manuscript to clarify this.

Thank you for your review. We appreciate your detailed questions and hope to address all concerns below: **Weakness 1:** **For the full dataset baseline, we use standard hyperparameters (learning rate schedules) for each dataset from prior works (Guo et al., 2022; He et al., 2016).** We do not think the hyperparameter settings affect the findings of our submission. The reason is that the primary goal of our experimental study is compare repeated random sampling (RS2) with existing SoTA data pruning methods. We ensure that the only difference between these methods in our experiments is which examples are used to generate mini batches (i.e., there are no learning rate schedule differences). **Weakness 2:** **We have added plots of the number of unique examples seen throughout training for RS2 and select baselines to our updated PDF.** RS2 without replacement is the fastest method to utilize all training examples. Baselines which reselect the subset each round (e.g., the -RS and -RC methods in Table 1) also explore most training examples in the full dataset (e.g., >99%). **Weakness 3:** Please see our response to Reviewer hzLv under Weakness 2. We clarified the setting for Table 1 in our submission and added specifics for each -RS and -RC baseline in the Appendix. **Weakness 4:** We believe that GraNd-RC performs worse than other methods because it is sensitive to the model weights used to rank example importance. To address this problem, prior works (Guo et al., 2022) report results after averaging scores from 10 different partially pretrained models. We follow this approach for GraNd and GraNd-RS. For GraNd-RC we use only the current model being trained. We hypothesize that the -RC methods perform worse than the -RS methods because the example importance distributions created after partially pretraining an auxiliary model on the full dataset (like those used for the -RS methods) are more accurate when compared to the distributions generated by the -RC methods (especially in the early rounds of training). **Weakness 5:** For Craig-RS, we performed sampling using the distribution output by the Craig implementation from the DeepCore framework (Guo et al., 2022) as example importance scores. We agree that this heuristic is not appropriate and we will remove it from Table 1 Left. For Table 1 Right, where we allow methods to directly re-select a new subset at every round, we use Craig (denoted Craig-RC) to select the subset at each epoch based on the current model weights. The results in Table 1 Right corroborate the results in Figure 5 (a) in Mirzasoleiman et al., which show that SGD + random can achieve higher accuracy than SGD + Craig. **Weakness 6:** **We compare active learning baselines to subset selection schemes as done in prior work (Park et al., 2022); In fact, active learning methods often outperform other approaches with respect to end-model accuracy (e.g., Table 3).** We acknowledge that active learning methods can be applied to other settings (beyond minimizing time-to-accuracy) (Section 6). **Weakness 7:** Existing works typically include comparisons to a random baseline that selects only a static subset once at the beginning of training. We also include this method in our submission (e.g., in Figure 2 and Tables 3-6; labeled as ‘Random’). Our work extends random sampling to include random exploration (something that is rarely considered in prior work) and shows that many methods that outperform ‘Random’ do not outperform repeated random sampling (RS2). **Weakness 8/9:** **We use the same hyperparameters etc. for prior methods as in the recent benchmarking papers (Guo et al., 2022; Park et al., 2022).** As stated in (Park et al., 2022), “The hyperparameters for all algorithms are favorably configured following the original papers.” **Question 1:** **We will include comparisons between RS2 and CREST for our camera ready.** **Initial experiments show that CREST matches or outperforms existing baselines that we compare against but that RS2 still reaches higher accuracy.** For example, on CIFAR10 with a selection ratio of 5% and 10% respectively, CREST achieves 86.07 and 90.42 percent accuracy, which outperforms our next-best static baseline (68.7 and 86.1; Table 3) and matches our next-best per-round baseline (86.2 and 90.4; Table 1). RS2, however, reaches an accuracy of 87.1 and 91.7 percent in these settings respectively. For these experiments, we use the publicly available CREST implementation and the learning rate schedule found to work best for CREST by the authors (all other hyperparameters are the same). We will include additional results as they become available, however, CREST currently takes 5+ hours per run on CIFAR10 with a selection ratio of five percent, compared to under 10 minutes for RS2.

Thank you for your review and feedback. We believe that some details of our work may have been misunderstood. We clarify those and respond to your concerns: **Weakness 1:** We clarify that **RS2 without replacement is equivalent to training on the full dataset for fewer epochs and with a compressed learning rate schedule** (as stated in “RS2 Without Replacement”, Section 3). We have improved our presentation for clarity (crossref. Reviewer ph2c Question 1). Thus, the simple baseline you suggest, “training on the full dataset with the compressed learning rate schedule” has already been included in our experimental results. We present this method as “RS2 without replacement” because the focus of our submission is on subset selection methods to minimize time-to-accuracy. Rather than sampling subsets based on importance scores as in existing SoTA data pruning methods, we show that time-to-accuracy can be improved by selecting subsets randomly, either with or without replacement, at each epoch. It is a consequence of the sampling procedure that “RS2 without replacement” is equivalent to full dataset training with adjusted hyperparameters. **Weakness 2:** We clarify 1) the experimental setting for Table 1 and 2) our experimental results using active learning based methods; these results corroborate those from Park et al., 2022 which show that active learning methods outperform other subset selection algorithms. We have updated the description of Table 1 in Section 5.2. 2 to reflect the clarifications below and added the implementation details for each method in the Appendix. **Experimental Setting and Table 1:** In our submission, we include comparisons to baseline methods that select a static subset once before training begins (Section 5.2 1) and to extensions of those baseline methods that dynamically re-select the subset before every round (Section 5.2 2). Comparisons to baselines which select static subsets are shown in Figure 2 and Tables 3-6. **Comparisons to baselines which re-select the subset before every round are shown in Table 1 (baselines in Table 1 Left and Right both reselect the subset at each round).** We use two different methods for re-selecting the subset at each round: 1. RS Methods (Table 1 Left): The -RS methods in Table 1 left start from an initial categorical distribution over all examples and then sample a subset for training from that static distribution each epoch. The initial categorical distribution is generated in the same manner as when generating the categorical distribution used to selecting static subsets in prior methods: an auxiliary ResNet-18 model is pretrained on the full dataset for 10 epochs and then used to quantify example importance based on the corresponding method for the baseline of interest (as in (Guo et al., 2022)). We do not present -RS results for baselines methods which do not generate an importance score for all examples. 2. RC Methods (Table 1 Right): In between each epoch, the -RC methods in Table 1 right use the weights of the current model being trained to either 1) re-quantify example importance—in this case the examples with the highest importance are then selected for the subset at the next round—or 2) directly re-select the subset for training (e.g., in the case of submodular-based methods). We do not use any pretraining or an auxiliary model for the -RC methods and do not present -RC results for baselines which generate subsets independently of model weights. **Active Learning Results:** Our **experimental results do not contradict those from Park et al., 2022**. We clarify that **the methods labeled Entropy and Margin in Table 1 are not active learning based methods**. Rather, these methods select subsets based on example uncertainty as described in (Guo et al., 2022). We label all active learning methods with an AL prefix (e.g., AL (Margin)) as described in Appendix B. In fact, our experimental findings corroborate those of Park et al., 2022—Table 3 shows that active learning based methods are the best performing baseline (yet still worse than RS2) for 20-40% selection ratios on CIFAR10. **Question 1:** Please see our response to Weakness 2. **Question 2:** The importance scores for training examples in the full dataset are recomputed for the -RC methods in Table 1 right after every epoch. We clarified this in Section 5.2 2. **Question 3:** **Our submission includes comparisons to selecting a fixed random subset.** Results are shown in Figure 2 and Tables 3-6 (labeled ‘Random’). This method achieves competitive performance, but does not outperform prior SoTA methods. Our work shows that extending random sampling to include random exploration (repeated sampling) improves time-to-accuracy. **Question 4:** Please see our response to Weakness 1. Training on the full dataset with the compressed learning rate schedule is equivalent to RS2 without replacement and is thus included in our experimental results.

Thank you for your detailed review and helpful suggestions. We go over your weaknesses and questions: **Weakness 1:** We edited the Repeated Sampling of Random Subsets (RS2) paragraph of Section 3 to highlight that the difference between RS2 and existing SoTA methods is twofold: 1) RS2 samples the subset for training randomly while existing methods use importance-based sampling and 2) RS2 resamples the subset for training before each round, while many prior methods opt to select only a static subset once at the beginning. **Weakness 2/Question 4:** We agree that studying RS2 and data pruning methods on datasets with large intra-class variance and class-imbalance is an interesting research question. **We will include comparisons between RS2 and baselines on the two datasets you suggested for our camera ready.** **Initial experiments show RS2 without replacement outperforms other baselines on DermaMNIST.** We train ResNet18 with a selection ratio of 10% using the same hyperparameters as for our experiments on CIFAR10. RS2 without replacement achieves 71.6% accuracy, while selected baselines achieve the following: 1) Random (static random subset): 68.5, 2) Margin: 65.5, 3) K-Center Greedy: 66.9. **Weakness 3:** We expanded the discussion of RS2’s theoretical properties to reference the experimental results. In particular, we highlight that the generalization error of standard gradient RS2 (Theorem 4.1) relies on the fact that RS2 selects data in a data-independent fashion. In contrast, all existing SoTA data pruning methods adopt data-dependent strategies, which prior work (Ayed & Hayou, 2023) has noted may worsen generalization. This theoretical insight (that data-independent sampling allows for improved generalization due to selecting diverse, unbiased samples), is the reason RS2 outperforms existing methods. Our conducted experiments support this hypothesis. **Question 1:** Thank you for your suggestion. **We merged Algorithm 2 into Algorithm 1 such that it describes both RS2 with and without replacement.** We changed the text describing RS2 without replacement to reference the new Algorithm 1 for clarity. **Question 2 and 3:** We updated the paper to use N when referring to the number of training examples and to use ‘selection ratio’ when referencing the fraction of data selected for training.

Thank you for your review. We are excited that you appreciate our experimental results. With respect to your concerns: **Weakness 1:** We present “training on the full dataset for a reduced number of epochs but with a compressed learning rate schedule” as “RS2 without replacement” because the focus of our submission is on subset selection methods to minimize time-to-accuracy. Rather than sampling subsets based on importance scores as in existing SoTA data pruning methods, we show that time-to-accuracy can be improved by selecting subsets randomly, either with or without replacement, at each epoch. It is a consequence of the sampling procedure that “RS2 without replacement” is equivalent to full dataset training with adjusted hyperparameters. **We have improved our presentation in Section 3 for clarity.** Random sampling allows for improved time-to-accuracy because of the theoretical insights presented in Section 4: We show that RS2 has desired convergence properties (in contrast to other data pruning methods) as a result of data-independent sampling, which prior work has shown may improve generalization (due to selecting diverse, unbiased samples) (Ayed & Hayou, 2023). Our conducted experiments support this hypothesis. **Weakness 2:** We compared RS2 directly to baselines which select a fixed subset because many static subset selection methods [e.g., Killamsetty et al., 2021; Paul et al., 2021; Sachdeva et al., 2021; Toneva et al., 54] were proposed with the goal to reduce total training cost (i.e., time-to-accuracy). These works opt to pay an initial subset selection cost such that training time is subsequently reduced. Our work shows that one does not need to pay this upfront cost—in many cases, RS2 completely trains a model to better accuracy within the time required to carefully select a data subset. Moreover, our results show that even though RS2 requires access to the full training set, this leads to minimal runtime overhead (Section 5.2 Training Time, ImageNet) compared to training on a static subset. The reason is that large datasets can be stored on cheap high capacity disks and paired with data loaders to prefetch samples, leaving model computation to dominate runtime. **When the goal is different from minimizing time-to-accuracy (e.g., active learning, data transfer, or to reduce dataset storage size as you mention) then RS2 may be a weaker baseline. We have expanded the limitations of RS2 discussion in Section 6.** **Weakness 3:** Thank you for the pointers to [Ref-1] and [Ref-2]. We acknowledge that instantiations of RS2 have been considered for a variety of contexts in recent works (Section 1), but to our knowledge, our work is the first to show that RS2 surpasses existing state-of-the-art data pruning and distillation methods in accuracy and end-to-end runtime. **We revised our paper to add missing citations to the above two references.**