Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning
Authors: Patrik Okanovic
Roger Waleffe
Vasilis Mageirakos
Konstantinos Nikolakakis
Amin Karbasi
Dionysios Kalogerias
Nezihe Merve Gürel
Theodoros Rekatsinas
Venue: ICLR 2024 poster (2024)
Keywords: data pruning
dataset distillation
random sampling
corset selection
data-efficient learning
Primary area: datasets and benchmarks

Abstract: Methods for carefully selecting or generating a small set of training data to learn from, i.e., data pruning, coreset selection, and dataset distillation, have been shown to be effective in reducing the ever-increasing cost of training neural networks. Behind this success are rigorously designed, yet expensive, strategies for identifying the most informative training examples out of large datasets. In this work, we revisit these methods to understand if the additional computational costs associated with such strategies are justified from the perspective of time-to-accuracy, which has become a critical efficiency measure of deep neural network training over large datasets. Surprisingly, we find that many of the recently proposed methods underperform what we call Repeated Sampling of Random Subsets (RSRS or RS2), a powerful yet overlooked extension of the standard random baseline that learns from repeatedly sampled data throughout training instead of a fixed random subset. We test RS2 against thirty-two state-of-the-art data pruning and distillation methods across four datasets including ImageNet. Our results demonstrate that RS2 significantly reduces time-to-accuracy, particularly in practical regimes where accuracy, but not runtime, is similar to that of training on full dataset. For example, when training ResNet-18 on ImageNet, with 10\% of the dataset each epoch RS2 reaches an accuracy of 66\% versus 69\% when training with the full dataset. The best competing method achieves only 55\% while training 1.6$\times$ slower than RS2. Beyond the above meta-study, we discuss the theoretical properties of RS2 such as its convergence rate and generalization error. Our primary goal is to highlight that future works that aim to minimize total training cost by using subset selection, need to consider 1) the total computation cost (including preparing the subset) and 2) should aim to outperform a simple extension of random sampling (i.e., RS2).

Published as a conference paper at ICLR 2024
REPEATED RANDOM SAMPLING FOR MINIMIZING THE TIME-TO- TC-AURRACY OF LEARNING
Patrik Okanovic Roger Waleffe Vasilis Mageirakos' Konstantinos E. Nikolakakis
Amin Karbasi Dionysis Kalogerias Nezihe Merve Gürel Theodoros Rekatsinas*)
'ETH Zürich PUniversity of Wisconsin-Madison
Yale 'Google Research STU Delft
ABSTRACT
Methods for carefully selecting or generating a small set of training data to learn from, i.c., data pruning, coreset selection, and dataset distillation, have been shown to be effective in reducing the ever-increasing cost of training neural networks. Behind this success are rigorously designed, yet expensive, strategies for identifying the most informative training examples out of large datasets. In this work, we revisit these methods understand if the additional computational costs associated with such strategies are justified from the perspective of time-to-accuracy, which has become critical efficiency measure of deep neural network training over large datasets. Surprisingly. we find that many of the recently proposed methods underperform what we call Repeated Sampling of Random Subsets (RSRS or RS2), a powerful yet overlooked extension of the standard random baseline that learns from repeatedly sampled data throughout training instead of fixed random subset. We test RS2 against thirty-two state-of-the- thee--art data pruning and distillation methods across four datasets including ImageNet. Our results demonstrate that RS2 significantly reduces time-to-act -o-ccurcc,,,,, particularly in practical regimes where accuracy, but not runtime, is similar to that of training on full dataset. For example, when training Re on ImageNet, with 10% of the dataset each epoch RS2 reaches an accuracy of 66% versus 69% when training with the full dataset. The best competing method achieves only 55% while training 1.6x slower than RS2. Beyond the above meta-study, we discuss the theoretical properties of RS2 such as its convergence rate and generalization error. Our primary goal is to highlight that future works that aim to minimize total training cost by using subset selection, need to consider 1) the total computation cost (including preparing the subset) and 2) should aim to outperform simple extension of random sampling (i.e., RS2).
INTRODUCTION
Deep learning is continually achieving impressive results, from image classification (He et al., 2016
Dosovitskiy et al. 2020) speech recognition (Chiu et al. 2018) and natural language process- ing (Brown al. 2020 Radford et al. 2019 OpenAl 2023). Much of this success can be attributed to training large neural networks over datasets with millions or billions of examples (Russakovsky et al. 2015 Gokaslan & Cohen 2019 Brown et al. 2020 Radford et al. 202I). However, these network and dataset sizes lead to model training that requires weeks or months and yields significant monetary and computational costs (Mindermann et al. 2022 Brown et al. 2020). Such costs nearly prohibit model refinement through hyperparameter neural architecture search. As result, there has been an arms race to minimize the required training time to reach a given accuracy, i.e., time-to-ast -o-acuraccc..cc...
To reduce to-acurccc recent works focus decreasing the amount of training data used for model learning during each epoch. More specifically, given a large, labeled dataset, these works aim to maximize end-model accuracy and minimize runtime when training for multiple rounds, where training within each round is performed only on small set of examples equal in size to fraction of the full dataset. The of examples used for training at each round can be either chosen once before learning begins or periodically recomputed between rounds based on model updates (e.g., as
'Equal contribution. 'Currently Apple. Correspondence o.kanvvviiiiiiiooooo cê inf www.f.tt......m............ ch and wal ff sc.edu.

---

Published as a conference paper at ICLR 2024
in Mirzasoleiman et al. p020); Killamsetty et al. (2021b)) Existing methods in this framework span
two main categories: 1) data pruming methods which aim to reduce time-to- -cccuurry by selecting a
subset of the most informative examples for training (Welling 2009 Bachem et al. 2015 Bateni
(et al. 2014 Chen et al. 2010 Paul et al. 2021 |Sorccher et al. 2022); 2) dataset distillation methods
which generate small sets of synthetie examples summarize the full dataset (Wang et al. 2018 Yu
ct al. 2023). We review these methods in Section Briefly, these methods have demonstrated strong competitiveness in minimizing the time-to-accuracy of learning and influenced a large number of subsequent works, including ours, However, several challenges persist in the pursuit of minimizing time-to-aceunl -accuu-a using these methods. One major challenge lies in the time efficiency aspect, as there is a notable overhead associated with subset selection. For example, many methods require pretraining an auxiliary model on the full dataset for few epochs in order to select the subset, a task which we find can take roughly 250 minutes on ImageNet (Figure 3bb) while training itself with r = 10 and 30% takes only 400 and 1200 minutes respectively. Even when efforts are made to address this issue, score-based data pruning has fallen short in achieving high accuracy compared to a simple baseline- of training particularly in practical regimes (e.g., [10, 30 %) that enable ML practitioners to efficiently perform tasks such as hyperparameter search (Ayed & Hayou 2023 Sorscher et al.) 2022).
randomly samples a static subset of the full dataset once at the beginning
With these challenges in mind, in this work, revisit the random sampling baseline for subset selection and study an intuitive and powerful extension of this method for optimizing the time-to- accuracy of learning. Random sampling is already a competitive baseline due to its ability to select representative data examples for training, thus preventing overfitting. Typically, a static subset of
the complete dataset sampled once before the learning begins (Guo al. 2022 Park et al. 2022). However, we believe that a stronger instance of this baseline would repeatedly sample data instances at each epoch, as this allows the learner to explore more previously unseen examples throughout training. Random exploration has already proven advantageous for data pruning methods (Ayed & Hayou 2023). allowing them to calibrate for distribution shift (caused by discarded examples). Moreover, adversarial training has also experienced time-to-accurcc) reduction with random explo- ration (Kaufmann et al., (2022. Surprisingly, however, this method has yet to be established as a data pruning baseline for standard training of deep neural networks. Motivated by this gap, in this work study Repeated Sampling of Random Subsets (RSRS = RS2), a data pruning baseline which samples subset of data uniformly random for each training epoch. The main contribution of this paper is in-depth study of RS2 and a comprehensive evaluation of to what extent it is competitive, and can even outperform, expensive and complex data selection algorithms introduced in the recent literature; when the goal is to minimize total training time including subset selection, i.e., time-to-accurace While instantiations of RS2 have been considered for variety of contexts in recent works (Bartoldson et al. 2023) [Safran& & Shamir 2020, Wang et al. 2019 Wu et al.] [0200), to our knowledge, this work the first to show that RS2 surpasses all state-of-the art data pruning and distillation methods in accuracy and end-to-end runtime across wide range of subset sizes. This finding makes RS2 strong baseline to beat for minimizing monccurycccrrac....... In Section 3 we provide a detailed explanation of RS2, and in Section 4 we discuss its theoretical properties.
We extensively evaluate the time-to-accuracy of RS2 and compare it against 24 proposed data pruning and eight dataset distillation methods from the literature (Section 5p. We find that RS2 outperforms existing methods with respect to runtime and accuracy across varying subset selection sizes and datasets, including CIFAR1O 10, CIFAR 100, ImageNet30, and ImageNet. For example, when training R8 with r = 10% on ImageNet, RS2 yields a model with 66% accuracy, 11 points higher than the next-best method and only 3.5 points less than training with the entire dataset every round. Yet, RS2 reaches this accuracy 9x faster than standard full-dataset training and 1.6x faster than the next- best method. Finally, we present an extension of RS2 beyond supervised learning by benchmarking its performance on self-supervise that RS2 can potentially be a competitive baseline in this setting. Overall, our findings highlight that future works that aim to minimize neural network training cost need to consider both the end-model accuracy and runtime, including subset selection, and should aim to outperform RS2.
pretraining of GPT2 (Radford et al., (219)). Our evaluation shows
PRELIMINARIES
We first present a unified framework for the problem of reducing aine-to-accurall by training on less data each epoch and then review existing data pruning and distillation methods.
2

---

Published as a conference paper at ICLR 2024
Problem Statement Given a large, labeled dataset S V consists of an imput feature vector x; and a given ground truth label ys, our goal is to minimize rumtime and maximize accuracy when training for X rounds, with the training of each round performed set of examples S' with size |S"| r- |S| for E (0, 1).
Yo 1
where each training example
We highlight two points: First, it is assumed that X is chosen such that training proceeds for the same number of rounds as when training on the full dataset, otherwise the computational benefits are reduced (e.g., r = 50% with X 200 is the same amount of computation as r 100% with X == 100). Second, note that the subset S' may be static (e.g., as in [Sorscher et al. (2022) ) or vary across rounds (e.g., as in Mirzasoleiman et al. (2020); Killamsetty al. (202Ib)). Given the primary goal of minimizing time-to-acuuray. either choice is valid so long as the time to generate the subset S' at each round included the overall runtime.
Related Work To minimize tume-to-accuraee data pruming methods attempt to find a subset (also called a coreset) of informative examples S' C S (Guo et al. 2022 Park et al. (022). Numerous metrics have been proposed to quantify importance: Uncertainty based methods such as Least Confidence, Entropy, and Margin (Sachdeva et al.) (02T) assume examples with lower confidence will have higher impact on training. Loss and error based methods operate on a similar principle
(e.g., Forgetting Events (Toneva et al. 2018). GraNd, EL2N (Paul et al. 2021), and others (Bachem
ct al. for subset selection, such as CRAIG (Mirzasoleiman et al. 2020) and GradMatch (Killamsetty
2015 Munteanu et al.) 2018 Dasgupta et al.) 2019 Liu ct al. 202I)). Other techniques
et al. 2021a), focus on gradient matching, where the goal is construct a subset of examples such that a weighted sum of the model gradients on the subset matches the overall gradient on the full dataset. A different class of methods focuses on feature geometry for data subset selection (e.g., Herding (Welling) 2009 Chen et al.] (2010), K-Center Greedy (Sener & Savarese 2018). and prototypes (Sorscher al. 2022)). Additional data pruning algorithms attempt find the training examples closest to the decision boundary (e.g., Adversarial Deepfool (Ducoffe & Precioso (018))
and Contrastive Active Learning (Liu et al. (02T)), pose subset selection as a bilevel optimization problem (e.g., Retrieve (Killamsetty et al., (021c) and Glister (Killamsetty et al. (b21b)), or connect subset selection to maximization of a submodular function (c.g.. GraphCut, Facility Location, and Log Determinant (Iyer et al.) (021 )) Active learning methods (which aim to minimize labeling cost by selecting a subset given a large unlabeled dataset), can also be used in the presence of labeled dataset when the goal is to reduce time-to-accuranl (Park et al. 2022). We refer the reader recent surveys (Guo et al. 2022) for more details on the above methods and for comparisons between them.
In contrast data pruning which assumes S' to be subset of S, dataset distillation methods use S to generate a small set of synthetic examples 5' that aims to summarize S. Dataset distillation methods be split into three groups: 1) Performance matching methods (Wang al. [018]] Deng & Russakovsky. 2022) aim to optimize the synthetic examples in S' such that models trained on S achieve the lowest loss on the original data S. 2) Parameter matching techniques (Zhao al. 202
Lee et al. 2022, Kim et al. 2022 Cazenavette et al. 2022) focus instead on matching the parameters of network trained on S' with those of network trained on by training both models for number of steps. 3) Finally, the distribution matching approach (Zhao & Bilen 2023) to dataset distillation attempts to obtain synthetic examples in S' such that the distribution of S matches the distribution of S. We refer the reader to Yu et al. 2023) for detailed survey on dataset distillation.
RS2: REPEATED RANDOM SAMPLING TO REDUCE TOME-TO-ACCUREE
We describe the RS2 framework in the context of data pruning and discuss how it yields efficient training by reducing the amount of training data used at each round of model learning.
Repeated Sampling of Random Subsets (RS2) As discussed in Section 2 we assume access to large, labeled dataset S and aim reduce time-to-accuracy by training for X rounds, with the training of each round performed on subset S' c S (of size | = r -SS). We define RS2 as follows: at each round, sample S' randomly from S (Algorithmm]) [ Thus, the only differences between RS2 and existing SOTA data pruning methods (Section 2 are: 1) the subset is sampled randomly rather than based on example importance and 2) the subset is resampled before each round, compared to many prior methods which opt to select only a static subset once at the beginning. We next discuss two variants of the sampling strategy and the importance of appropriate learning rate scheduling.
3

---

Published as a conference paper at ICLR 2024
RS2 With Replacement The simplest version of RS2 samples S' with replacement across rounds- sampling can be stratified. This means that examples included in the subset of previous rounds are replaced in S and eligible to be resampled when constructing S' for the current round, i..,, S" is always constructed by sampling uniformly from all examples in (Algorithm Lines 7-8).
RS2 Without Replacement A second variant of RS2 samples S' without replacement across rounds. That is, examples in S that have been included in the subset during previous rounds are not considered when sampling S' for the current round. This continues until all examples from have been included in S' at some round, at which point the process repeats. RS2 with- out replacement can implemented as follows (Algorithm I Lines 3-6): Given a random per- mutation of the full dataset S = {x,, 3e: y: we select the first r.N examples the subset for the first round, then the next rN examples as the subset for the second round, and so on. After
Algorithm 1 RS2 General Algorithm
Require: Dataset S (x., yr Ji selection ratio r (0, 1J. batch size b, initial model w X rounds, sampling mode mode = "with repl.' or "w/o repl.'
1: T 4- [N/6]; t <<
2:
for round j 1 X do
3:
if mode = 'w/o repl.' then
4:
if t% = 0 then
5:
sluffle(S)
> Shuffle full dataset
6:
S' + S[( -N jjN:jjrM jjrr if mode == "with repl.' then
7:
8:
S' + randomly_ssame wrandomll_sampplesaueeetttt
r)
9:
for k = 1 to
do
10:
batch m S*[(k 1) 1):b:::0.0 k. w² < ttrainn
iterating over the full dataset, we generate a new permutation and repeat. Observe that as a con- sequence of sampling S' without replacement. this version of RS2 across X rounds is equivalent to training on the full dataset S for X rounds. Thus, RS2 without replacement can also be viewed as training on the full dataset for fewer epochs (with an adjusted learning rate as described next).
m): 1+
return w²
RS2 Hyperparameters For both RS2 variants, we as- sume that training proceeds using the same hyperparam- eters (e.g., batch size, etc.) as those used when training the full dataset with one exception: the learning rate sched- ule. The reason for this is that state-of-the-ar training procedures often slowly decay the learning rate after each SGD step, shown in Figure We include vertical line showing the number of SGD iterations when running RS2 for r 10%-data pruning with RS2 (or any method) leads to fewer SGD iterations (we train for the same X rounds, but on fewer examples per round). Thus, if the pruming method retains the same learning rate schedule, the learning rate will not decay enough to achieve high end-model accuracy. For example, on CIFARIO with r = 10%. RS2 with the full dataset schedule reaches just 83.9% accuracy compared to 95.5% when training without pruning. As such, we train both RS2 variants with the full dataset learning rate schedule adapted to decay faster, inversely proportional to the subset size r (e.g., green line in Figure [.. This is standard across existing data pruning methods (Guo al. 2022, [Smth & Topin| 2019). In this case, on CIFARI 10 respectively. While RS2 without replacement generally reaches the highest accuracy of the two variants, we do not claim that one is strictly better. We refer the reader to existing works regarding this question (Haochen &
Learning Rate
0.10
Full Dataset Schedule
RS2 Schedule (r- (0-)
0.05
Stopping Point (r=10%)
0.00
20000
40000
60000
BO0GO
SGD Iteration
Figure 1: Learning rate schedules on CI- FARIO with and without data pruning.
with r = 10%, RS2 reaches 89.7% and 91. with and without replacemee
Sra 2019
Lu et al. 2022
De Sa 2020
4 THEORETICAL PROPERTIES OF RS2
With time-to-accuracy in mind, we now study the relevant theoretical properties of RS2. We first comment on its convergence rate and then provide its generalization error.
RS2 Convergence Rate As familiar readers may identify, RS2 without replacement, under the assumption of nonconvex loss with bounded, 3-Lipschitz gradients, converges to an approximate critical point of the expected loss (Wang& & Srebrol 2019). Following the convergence result for mini batch SGD with Nesterov's 's accelerated gradient update (Ghadimi & Lan 2016). the convergence rate of RS2 without replacement can be shown to have scaling factor in front of the total number of iterates compared to the full dataset SGD convergence rate (Ghadimi & Lan 2016), while the bound remains consistent with respect to all the other parameters (we defer to Appendix H for details).
4

---

Published as a conference paper at ICLR 2024
RS2 Generalization Error We now provide upper bound the generalization error of RS2. For this analysis, we relax the update rule from Algorithm to a standard gradient update without momentum. Recall that as decreases, RS2 results in smaller total number of gradient steps after X rounds compared to r 1. While this may lead to an increase in optimization error, the generalization error is expected be smaller than that of the full dataset schedule (shorter training time gives smaller generalization error). This phenomenon has been characterized rigorously in prior works (Hardt et al., 2016) for vanilla SGD with batch size = however it does not directly apply to larger mini batch sizes and general selection rules. As such, we show an extension of known generalization error bounds that also holds for RS2 with mini batch size b. Before we proceed, we first introduce some notation for brevity. We define the training dataset S - (21, (2,.22.... , ,.,..., ,NN, for which 2; - (x,, Us) for E (1,.... N and the (empirical) loss ((w) & E f(w, 2;), where : Rd x Z + Rt. Let 22,............................. 2N, be i.i.d random variables with respect to an unknown distribution D. Then for any stochastic algorithm A with input S, and output A(5), the generalization error 'gen is defined as the difference between the empirical and population loss (Hardt et al. 2016
N
Egen (f, AA) A Es.A.s [f(A(S) 2)] ES,
E ((A(S)
(1)
N
We now proceed with upper bound on the generalization error of RS2. The next result follows from recent work (Nikolakakis et al. 2023). and applies to RS2 without momentum and batch size b.
u
Theorem 4.1 (Generalization error of standard gradient RS2). Let the function f be nonconvex, Ly-Lisschitz and B B-smoohhh Then the generalization error of the standard gradient RS2 algorithm with a decreasing step-size 1/t S C/Il (for C < 1/Br), is bounded as:
Egen (f.D, RS2)
cBe 13 . - C) min {1+
1 CB, logle r- T TXX). (2)
The proof of Theorem 4.1 is deferred to Appendix F Observe that, for the convergence rate, the generalization error of RS2 remains the same as for that of the full dataset (Nikolakakis et al. 2023), except that the number of iterates for RS2 is scaled by We note that Theorem 4.1 applies to both RS2 with and without replacement-11a it relies on the fact that the batch at each itcration is selected non-adaptively and in data-inde iata-inndepndeent fashion. However, most exisiting data pruning methods adopt dependent strategies, which recent work (Ayed & Hayou 2023) has shown may worsen generalization due to discarding many training examples, resulting in inferior performance compared to random sampling. This theoretical insight (that data-independent sampling allows for improved generalization due selecting diverse, unbiased samples), is the reason RS2 outperforms existing methods. Our conducted experiments in Section 5 support this hypothesis.
5 EVALUATION
We evaluate RS2 on four common benchmarks for supervised learning and compare against data pruning and distillation methods. We show that:
1. Across a wide range of selection ratios, RS2 reaches higher accuracy than all existing methods.
2. For a given selection ratio, RS2 also trains the fastest, and thus has the fastest time-to-accuracy.
3. In the presence noisy labels, RS2 is the most robust data pruning method; achieves the highest end-model accuracy and lowest relative drop in performance vs. training the clean dataset.
We also end this section by discussing an initial extension of RS2 beyond conventional supervised learning to self-supervised training settings for text.
5.1 EXPERIMENTAL SETUP
We summarize the setup used in the experiments. More details can be found in Appendix B
Datasets, Models, and Metrics FARIO (Krizhevsky et al. 2009). CIFARI00 (Krizhevsky et al. 2009), ImageNet30 (a subset
We benchmark RS2 against baseline methods using CI-
Source code: http:://gg http:/ittu..ccoottttotttt wwtteatttoooooooo.a.ooooooooetat www.aaiii/kkkaaaa///////////
5

---

Published as a conference paper at ICLR 2024
of ImageNet) (Hendrycks al.
2019), and ImageNet (Russakovsky et al. 2015) itself. We train
ResNet models (He et a (016) representative of modern state-of-the- convolutional neural net- works. We use the same moodels/daaasee as those used in the recent published works on SOTA data pruning methods (Guo et al.
2022 Killamsetty et al. 2021a] Mirzasoleiman et al., 2020; Paul et al. 202T (Schhdeva et al. 2021 Sorscher et al., 2022 Toneva 20188); this choice enables direct comparison with prior work. For all experiments we measure subset selection overhead, overall training time (including the total time for subset selection across all rounds and the total training time on selected subsets), and end-model accuracy. We believe that the consistency of our findings across all models/datasets provides sufficient experimental evidence that RS2 is strong baseline that has been overlooked in literature.
Baselines We compare RS2 against 24 data pruning methods and eight dataset distillation methods from the literature. A full list and their abbreviations can be found in Appendix B All baselines are used for the smallest dataset (i.e., CIFARIO), but some methods do not scale to larger datasets (e.g.. ImageNet). We utilize existing open-source implementations and results where applicable (Park et al. Guo et al. 2022) and implement RS2 within the same code for equal comparison.
2022
We use standard hyperparameters for each dataset from prior works known to achieve high accuracy. We use the same hyperparameters for all methods where applicable (e.g.. batch size, initial learning rate, number of training rounds, etc.). This means that, for the same subset selection size r, RS2 and all baseline methods train for the same number of SGD iterations using the same learning rate schedule; the only difference is how the examples in each mini batch are generated. More details are provided in Appendix B.3
Training Details
5.2 END-TO-END DATA PRUNING EXPERIMENTS
We discuss end-to-end comparisons of RS2 with data pruning baselines on supervised learning
benchmarks. Results are shown in Figures 3 and Table I
Accuracy We first focus on end-model accuracy of RS2 compared to existing methods. We include comparisons both to baselines which we modify re-select the subset each round and to the original methods which select fixed subset-this enables us to compare directly to many recent works that aim reduce total training cost (i.e., fime-to-accuracy through data pruning and propose to select static subsets (e.g., Killamsetty et al.] (202 Paul et al. (2021); Sachdeva et al. (202]): Toneva et al. (2018). Evaluating the performance of data pruning baselines in both static and repeated sampling modes allows us to highlight the importance of 1. selecting subsets randomly (RS2 vs. baselines in
per-round sampling mode) and 2. selecting subsets repeatedly (RS2 vs. baselines in static mode).
1. Accuracy Vs Baselines with Static Subset Selection In Figure 2 we show the end-model accuracy of RS2 compared to existing methods on CIFARIO and ImageNet for varying selection ratios. We use the combined baseline methods and setting from recent studies (Guo et al. 2022
Park
et al. 2022) together with newer prototype-based data pruning methods (Sorscher et al. 2022 We include further discussion of results and the exact accuracies for these Figures in Tables and in Appendix C.T The repeated sampling of RS2 leads to accuracy improvements over existing methods: For example, CIFARIO 10 with 10% of the data each epoch, RS2 without replacement achieves 91.7% accuracy while the next closest baseline reaches just 86.1 %. Similar results hold on CIFAR 100 and ImageNet30 (Appendix C.2 as well as on CIFARIO 10 with VIT architectures rather than ResNets (Appendix C.4). Figure shows that RS2 also outperforms existing methods on the much larger ImageNet dataset: RS2 end-model accuracy with 10% is 66% while the next closest baseline trains to only 55%. Moreover, the end-model accuracy of RS2 is actually on par with training on the full dataset for non-trive non-trivial selection ratios (e.g.. r [10, 30)% offering a potential practical solution to reduce the cost of training in some applications (see also runtime reductions below).
Accuracy Vs Baselines with Repeated Subset Selection Next, we extend baselines to also perform repeated sampling. Our goal is to examine if the prior observations are attributed only to the fact that RS2 performs repeated sampling while the above baselines do not. We implement repeated sampling for baselines in two different ways. For given baseline M 1) if M computes numerical importance score for all training examples to select a subset, we compute those scores once at the beginning of training and view them categorical distribution over the dataset. We then define M-RS follows: at each round, we resample the subset according to the categorical distribution. 2) We define M MRRC as follows: In between every round, use the weights of the current model being trained to either

---

Published as a conference paper at ICLR 2024
Accuracy (%)
90
Accuracy (%)
60
18%
Existing Methods
Existing Methods
60
Random
40
.29%
Random
RS2 w/o
20
RS2 w/o repl
30
Full Dataset
Full Dataset
0
1
5
10
20
30
40
50
1
10
30
Selection Ratio r (%)
Selection Ratio (%)
(a) CIFAR10 10 accuracy
(b) ImageNet accuracy
Figure 2: Accuracy achieved by data pruning methods (baselines select static subsets) when training
ResNet-16 18 on CIFARIO and ImageNet. RS2 outperforms existing methods.
Table Accuracy achieved by data pruning methods with per-round sampling when training ResNet- 18 on CIFARIO. The training subset is update for all methods after each round, either by resampling from a static example importance distribution (RS, left) or by recomputing subsets based on the model weights after each epoch (RC, right). Repeated Sampling of Random Subsets (RS2) outperforms repeated sampling based on example importance. Best method bolded; Next best underlined.
Selection Ratio
5%
10%
30%
Selection Ratio
5%
10%
30%
CD-RS
CD-RC
75.24:2.2
83.1200.7
87.520..2
Herding-RS
Herding- RC
30.11:2.6
80.61:.4
81,0:10.9
K-Center Greedy-RS
K-Censer Greedy-RC
78.1
82.3+-0.5
86.3-20.4
Least Confidence RS
67.6:1:.11
83.414999
93.7.10.44
Least Confidence- RC
44.81:12
36.72:3.9
08.3-10.3
Entropy-RS RS
85.24:099
89.8:04
94.4+-0.3
Entropy-RC RC
41.4-:699
78.4+:29
86.9:10.1
Margin-RS
84.3:22.
90.41:0
94.40022
Mangin- RC
79.71:144
12.8
86.8-0022
Forgetting RS
81.9:1311
88.3:124
91.01:0.1
Forgetting RC
28.71:0.8
60.72:6.5
78.8:2-1.3
GraNd-RS
86.2422.1
90.11:09
94.5:10.11
GraNd RC
18.
24.12:6.0
75.2-1..00
CAL-RS
81.1230
866617
93.34:0.1
66.71:177
74.52-0.8
84.8:00.4
Crag-RS RS
Craig: RC
70.3:113
80.3:20.8
0..5220.3
Glister RS
Glisser RC
72.54:066
81,42:0.7
86.6:10.55
SP-Easy -RS
84.0:14.3
88.410.1
93.610.3
SP-Easy RC
RS2 repl (stratified) R52 wio rept
86.6::0.5
89.8::0.4
94.5+0.11
RS2 repl (stratified) RS2 w/o repl
$6.61::055
89.8::0:4
94,5=10.1
87.1:10.8
91.7:1055
94.320022
87.1:10.8
91.7:1005
94.3200.
recompute example importance scores- the examples with the highest scores are then selected for the subset the next round-ov or directly re-select the subset for training. We do not present -RC results for baselines which generate subsets independently of the model weights (as the subset would remain static). Full implementation details for our repeated sampling baselines are included Appendix [B.4] Note that the latter set of methods (RC) are unlikely to be able to improve the efficiency of training as they generally require computing the model forward pass for every example between each round (to compute importance scores). Results CIFARIO (for computational considerations
do not these methods on ImageNet) are shown in Table I While updating the subset for existing methods each round improves their accuracy, RS2 still reaches the highest end-model accuracy.
Training Time
We now study the training time (time-to-an -o-cuurccc)))a of RS2 compared to existing methods on CIFAR1O and ImageNet. We train all methods from scratch on NVIDIA 3090 GPUs and use all baselines which do not give GPU out-of-memory. For the experiments reported here, run baseline as they were originally proposed (i.e., with static subset selection). This allows us to quantify the overhead of selecting single subset with existing methods compared to repeatedly selecting many random subsets with RS2. We show the -oacurrcyy on CIFARIO in Figure 3a and on ImageNet in Figure 3b using = 10% for both datasets.
More time-to-accuracy results are included in Appendix C.6 and and subset selection on CIFARIO for baselines with static subset selection in Appendix Table g and for baselines which utilize per-round sampling in Appendix Table We also include the time-to to-cuuaay measurements on CIFAR10 and ImageNet for different selection ratios in Appendix Tables 10 14
We report the total time for
Figures 3a and 3b show that RS2 provides the fastest acce-to-accuracy when compared to previous data pruning methods. Note that the repeated subset selection in RS2 leads to negligible overhead compared to training on a static random subset (Figure 3 and to the total training time: For example, the total subset selection time for RS2 on CIFARIO with r 10% is less than one second, yet the total runtime is 750 seconds. Existing methods, however, are primarily limited by the fact that they require pretraining importance: On ImageNet the fastest baseline begins training after 250 minutes, yet training itself only requires 400 minutes. Even if the pretraining overhead is amortized by fixing the subset for the
auxiliary model the full dataset for few epochs in order to rank example
7

---

Published as a conference paper at ICLR 2024
Accuracy (%)
90-
4.3x
Accuracy (%)
60
9x
Existing Methods
Existing Methods
60-
Random
Random
30-
RS2 w/o
20
RS2 w/o repl
Dataset
Full Dataset
0
1000
2000
3000
4000
0
1000
2000
3000
4000
5000
Time (s)
Time (min)
(a) CIFARIO time-to-accuracy
(b) ImageNet time-to-accuracy
Figure 3: Time-to-aceuracy for RS2 vs. existing data pruning methods (with static subset selection), static random subset, and standard training on the full dataset. We use selection ratio of r 10%. RS2 is both the fastest and highest accuracy data pruning method.
Table 2: Accuracy achieved by dataset distillation methods, RS2, and Random data pruning when training ConvNet model. We select the specified number of images per class (Img/Cls) correspond- ing to the given selection ratio on the full dataset. Best method bolded. Next best underlined.
Ing[Ch
Ratio
Ruslion
DD
LD
DC
Danout Diaillaiion Methods
DSA
DM
CAFE
CAFENDSA
TM
RS2 rxp
Fall Durnctt
0.02
144220
25.720.7
28.340.5
28.85077
26.000.8
30.32111
31,610.5
46-3-0.8
54778855
CIFARI
M.kell
Waeld
36.4004
41910.
521160
48910.
71:718.1
81-01
30
43.410
42550.
53.900
606605
63.020.4
55.5::0
62.340.4
76.518.3
422003
11.5.04
12.6003
139500
11,410.3
129:03
14000.3
24.3:0.3
37,4184
CHAARIOO
10
146440
25,240.1
32,340.3
197360.3
278603
$1.540.
40.1404
43919.4
262503
50
10
30.0004
428804
43.62004
37.920.3
42.9.0.2
44.620.3
1440011
39:002
5.840.3
23,518.2
Thy Imageher
10
1291-04
25:24112
27,418.1
40
10
15,00044
26.160.3
28.610.4
remaining rounds, or by resampling from the importance distribution after each round (-RS baselines in Table Ip. the initial overhead of these methods is still orders of magnitude higher than the total overhead of RS2 across all rounds (e.g., Table 9 Moreover, Figures 3a and 3b highlight the practical potential of RS2 to reduce the computational cost of training high-
nigh-accuracy models: For CIFAR1O, RS2 reaches 91.7% accuracy 4.3 x faster than standard training on the full dataset, while for ImageNet, RS2 reaches 66% accuracy 9x faster than standard training.
Takeaway
The above results show that RS2 outperforms existing data pruning methods with respect to end-model accuracy. RS2 also has the lowest subset selection overhead resulting in the best time-to-accuracy across small (CIFAR10) and large (ImageNet) datasets.
5.3 COMPARISON TO DATASET DISTILLATION
We compare RS2 to dataset distillation methods which generate small sets of synthetic examples. Our experiments on CIFAR10 10, CIFAR100, and Tiny ImageNet (for computational reasons) are shown in T We use no data augmentation for these experiments due to small selection ratios. We train ConvNet models for consistency with existing dataset distillation evaluations. While dataset distillation methods generally outperform data pruning methods (e.g., in Table 2 a static random subset on CIFARIO with 1% reaches 43.4% accuracy while dataset distillation methods reach up to 71.6%), they have drawbacks. The synthetic sets are model- speciffc and computationally expensive generate. For instance, the best performing method, Trajectory Matching (TM), requires 133, 317, and 433 minutes to generate 50 images per class on CIFAR 10, CIFARIO) 100, and Tiny ImageNet, respectively. In comparison, RS2 requires just seven, 33, and 187 minutes for end-to-end training in these settings. Yet RS2 outperforms Trajectory Matching with respect to end-mode accuracy for eight of the nine selection ratio/dataset combinations Table 2
5.4 EXPERIMENTAL EXTENSIONS
We consider two practical extensions beyond the supervised benchmarks considered in the data pruning literature: We aim to 1) provide evidence RS2's robustness against noisy labels compared to other data pruning methods and 2) explore its possible application to unsupervised learning settings.
Robustness of RS2 to Noisy Labels One aspect that is usually underexplored in literature the robustness of standard data pruning baselines, which assume clean, moise-free labels. Here, aim to challenge this assumption and compare standard pruning methods against RS2 in practical scenario where this assumption fails. We present a detailed discussion of our experiments in Appendix C.8
8

---

Published as a conference paper at ICLR 2024
but summarize our main findings here: For this experiment, we use CIFARIO and randomly flip p percentage of the labels in the dataset- we vary p in (10%, 30%, 50%}. Different data pruning methods are used over this noisy dataset and measure end-mode accuracy and raw accuracy drop compared to no noise (p- = 0). In summary, we find that RS2 achieves higher end-model accuracy in the presence of noisy labels compared to existing data pruning methods. For example, with 30% of the training examples mislabeled, RS2 without replacement achieves 74.4% accuracy while the next closest baseline our modified per-round subset selection version of supervised prototypes with easy examples (SP- Pe--Eayy-R) -cchievess just 63.4%. Moreover, RS2 is generally the most robust method in that it suffers the lowest relative drop in performance when presented with noisy labels. All results are reported in Appendix Table 15
RS2-based Pretraining of Language Models the supervised training setting we find that RS2 can lead to measurable end-to-end cost reductions without significant drop in accuracy. We now extend our evaluation to unsupervised training aiming to understand if similar finding holds. To this end, we focus pretraining of large language models (LLMs), cost intensive procedure. We focus on the popular GPT architecture and specifically, explore if repeated random sampling (i.c., RS2) can help reduce the cost of training GPT2 (Radford et al. 2019) OpenWeb (Gokaslan & Cohen 2019) from scratch, without significant loss in mndel quality. A detailed discussion can be found Appendix C.9 Here, we present a summary of our findings.
We consider the standard metrics of accuracy and perplexity over the LAMBADA (Paperno et al. 2016) and WikiText103 (Merity et al., 2016) benchmarks. In addition, cost required to train GPT2-we we choose to train GPT2 due to monetary restrictions. We compare RS2-based training of GPT2 against 1) training over the full dataset, and 2) training over a random sample of the dataset (a basic baseline considered as a lower bound). We find that for LAMBADA, using a selection ratio of r = 30%, RS2-basee training of GPT2 yields relative accuracy drop of only 2.8% and a perplexity increase of only 0.5%, while offering a 3x cost reduction from $5,200, when the full dataset is used for training, to $1,560. For comparison, static random sample, yields an accuracy drop of 4. 4.2% and perplexity increase of 3.3%. Details are reported in Appendix Table T6
measure the monetary
We believe that this extension highlights a promising direction for reducting the cost of LLM training. and that RS2 offers competitive baseline for future unsupervised data pruning. Moreover, our findings seem to corroborate the very recent findings of Marion et al. (202)), which identify that static random sampling is a competitive data pruning baseline for LLM pretraining, while also offering a stronger baseline. Finally, we believe that repeated random sampling is complementary to methods that aim to reduce L.M training costs by focusing on high-quality data points (Zhou et al. 2023) Gunasekar et al., 2023). A more extensive study of data pruning for L.M training that will combine the aforementioned ideas between selecting high-quality examples in randomized manner (to promote diversity) is definitely an exciting future direction.
CONCLUSION
We showed that training on random subsets repeatedly sampled (RS2) from a large dataset results in reduced runtime and higher end-model accuracy when compared existing data pruning and distillation methods. While RS2 may provide a practical solution for reducing time-to-accuracy. e.g., for hyperparameter or neural architecture search, we also hope that our findings serve as a baseline for future research to minimize time-to-accuracy through data subset selection. RS2 is likely to be a weaker baseline when the goal is different from minimizing time-to-accuracy, e.g., if the goal is to reduce dataset storage overhead or to minimize the cost of labeling examples for training by selecting a subset from a large, unlabeled dataset. We believe that other methods we consider (e.g., active learning methods (Park et al.) 2022
Ren et al. 202T)) are more practical for these settings.
Finally, we are excited for future work to address the next questions: How can we further close the gap between RS2 and training on the full dataset? Interesting sub directions to answering this question include: 1) further study of importance sampling-base based methods for reducing time-to-accuracy and 2) improving the subset training procedure (independent of the method) to benefit the end-model accuracy. The key issue with the latter is that training on a subset results in fewer total SGD iterations when compared to training on the full dataset for the same number of rounds. Can we overcome this limitation of data pruning without eliminating the runtime benefits? We believe that new research into these questions can enable further reductions in time-to-accuracy.

---

Published as a conference paper at ICLR 2024
Ethics statement. We do not potential ethical issues with the contributions of the paper. In contrast, we evaluate a performant extension random sampling for environmentally ffiinddlyy training and offer extensive comparison of it to the existing data pruning methods.
Reproducibility statement. The reproducibility of RS2 spans theoretical and experimental per- spectives. We provide complete proofs of all the theoretical results appendices. We upload the source codes for implementing RS2 and reproducing experiment results supplementary materials.
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers for their constructive comments paper. This work was supported by DARPA under grant ASKEM HR001 122S0005, The U.S. Government is authorized reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or recommendations expressed in this material those of the authors and do not necessarily reflect the views, policies, endorsements, either expressed or implied, of DARPA or the U.S. Government. This work is also supported with funding from the Wisconsin Alumni Research Foundation. Amin Karbasi acknowledges funding in direct support of this work from NSF (IS-11855032) ONR (N00014- 19-1-2406), and the Al Institute for Learning- Enabled Optimization at Scale (TILOS).
REFERENCES
Sharat Agarwal, Himanshu Arora, Saket Anand, and Chetan Arora. Contextual diversity for active learning. In ECCV, pp. 137-153. Springer, 2020.
Fadhel Ayed and Soufiane Hayou. Data pruning and neural scaling laws: fundamental limitations of score-based algorithms. arXiv preprint (:XXi::2302.6666 2023.
Olivier Bachem, Mario Lucic, and Andreas Krause. Coresets for nonparametric estimation-the case of dp-means. In ICML., pp. 209-217. PMLR, 2015.
Brian Bartoldson. Bhavya Kailkhura, and Davis Blalock. Compute-efficient deep learning: Algo- rithmic trends and opportunities. Journal of Machine Learning Research, 24:1-77, 2023.
MossmmadHoossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab S Mirrokni. Distributed balanced clustering via mapping coresets. In NIPS, pp. 2591-2599, 2014.
Ondrej Bohdal, Yongxin Yang, and Timothy Hospedales. Flexible dataset distillation: Learn labels instead of images. arXiv preprint arXiv:2006.08572, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 202., 2020.
George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei Efros, and Jun-Yan Zhu. Dataset distillation by matching training trajectories. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4750-4759, 2022.
Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding. The Twenty-Sixie Conference Annual Conference on Uncertainty in Artificial Intelligence, 2010.
Chung-Cheng Chiu, Tara N Sainath, Yonghui Wu, Rohit Prabhavalkar, Patrick Nguyen, Zhifeng Chen, Anjuli Kannan, Ron Weiss, Kanishka Rao, Ekaterina Gonina, al. State-of-the-an speech recogmition with sequence-to-sequeee models. In 2018 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp. 4778-4778. 4778. IEEE, 2018.
Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances neural information processing systems, 24, 2011.
Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu. Teaching black-box learner, In ICML.. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2024
Christopher M De Sa. Random reshuffling is not always better. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5957-5967. Curran Associates, Inc., 2020.
Ofer Dekel, Ran Balad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Zhiwei Deng and Olga Russakovsky. Remember the past: Distilling datasets into addressable memories for neural networks. arXiv preprint arXiv:2206.02916 2022.
Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 19929, 1929, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition scale, 2021.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach. arXiv preprint arXiv:1802.0999 098800 2018.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99,22) 2016.
Aaron Gokaslan and Vanya Cohen. Openwebtext corpus. httt:://kky1cnn07..ggg
ío/
OpenWebbeext 2019.
Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, et al. Textbooks are all you need. arXiv preprint arXiv:2306. 1644, 2023.
Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In Database and Expert Systems Applications: 33rd International Conference, DEXA 2022, Vienna, Austria, August 22-24, 2022, Proceedings, Part I, pp. 181-195. Springer, 2022.
Jeff Haochen and Suvrit Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pp. 2624-2633. PMLR, 2019.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1225-1234, New York, New York, USA, 20-22 Jun 2016. PMLR.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016.
Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self-supervised learning can improve model robustness and uncertainty. Advances in neural information processing systems, 32, 2019.
Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combinatorial information measures with applications in machine learning. In Algorithmic Learning Theory, pp. 722-754. PMLR, 2021.
Maximilian Kaufmann, Yiren Zhao, Ilia Shumailov, Robert Mullins, and Nicolas Papernot. Efficient adversarial training with data pruning. arXiv preprint 2XXi:2207.0069. 2022.
Krishnateja Killamsetty, S Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-matee Gradient matching based data subset selection for efficient deep model training. In ICML, pp. 2021a.
11

---

Published as a conference paper at ICLR 2024
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning. In Proceedings of the AAAI Conference Artificial Intelligence, 2021b.
Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, and Rishabh Iyer. Retrieve: Coreset selection for efficient and robust semi-super learning. arXiv preprint 11X.::200..77700,, 2021c
Hhyn Kim, Jinuk Kim, Seong Joon Oh, Sangdoo Yun, Hwanjun Song, Joonhyun Jeong, Jung- Woo Ha, and Hyun Oh Song. Dataset condensation via efficient synthetic-data parameterization. In International Conference on Machine Learning, pp. 11 11102-11118 PMLR, 2022.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(112):365-339) 2012
Saehyung Lee, Sanghyuk Chun, Sangwon Jung. Sangdoo Yun, and Sungroh Yoon. Dataset condensa- tion with contrastive signals. In International Conference on Machine Learning, pp. 12362-12364.
PMLR, 2022.
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. ICML, pp. 6781-6792, 2021.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:/608.000 03983, 2016.
Yucheng Lu, Wentao Guo, and Christopher M De Sa. Grab: Finding provably better data permutations than random reshuffling. Advances in Neural Information Processing Systems, 35:8969-899 1981, 2022.
Max Marion, Ahmet Üstün, Luiza Pozzobon, Alex Wang, Marzieh Fadaee, and Sara Hooker. When less is more: Investigating data pruning for pretraining Ilms at scale. arXiv preprint arXiv:2309.0455 04564,, 2023.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture 2016.
models. arXiv preprint
Sören Mindermann, Jan M Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. Prioritized training on points that are learnable, worth learning, and not yet learnt. International Conference on Machine Learning, pp. 15630-15649, PMLR, 2022.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-cfficient training of machine learning models. In ICML. PMLR, 2020.
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P Woodruff. On coresets for logistic regression. In NeurlPS, 2018.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Yurii Evgen' evich Nesterov. A method of solving convex programming problem with convergence rate O(1/kP). In Doklady Akademii Nauk, volume 269, pp. 543-547. Russian Academy of Sciences, 1983.
Konstantinos E Nikolakakis, Amin Karbasi, and Dionysis Kalogerias. Select without fear: Almost all mini-batch schedules generalize optimally. arXiv preprint (i..ii::335.0224440 2023.
OpenAl. Gpt-4 technical report. arXiv preprint w...vv:3003.087777 2023.
Denis Papern, Germán Kruszewski, Angeliki Lazaridou, Quan Ngoc Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The lambada dataset: Word prediction requiring broad discourse context. arXiv preprint arXiv: 1606.06031, 2016.
12

---

Published as a conference paper at ICLR 2024
Dongmin Park, Dimitris Papailiopoulos, and Kangwook Lee. Active learning is strong baseline for data subset selection. In Has it Trained Yet? NeurlPS 2022 Workshop, 2022.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Finding important examples early in training. arXiv preprint arXiv:2107.07075. 2021.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and 1ly Sutskever. Language models are unsupervised multitask learners. 2019.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et Learning transferable visual models from natural language supervision. In International conference on machine learning, pp. 8748-8763. PMLR, 2021.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM computing surveys (CSUR), 54(9):1-40, 2021.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. ICV, 2015.
Noveen Sachdeva, Carole-Jean Wu, and Julian McAuley. Svp-cf: Selection via proxy for collaborative filtering data, arXiv preprint (0..iv:2107.049965 2021.
Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pp. 3250-3284, PMLR, 2020.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In ICLR, 2018.
Leslie N Smith and Nicholay Topin. Super-convergence Very fast training of neural networks using large learning rates. In Artificial intelligence and machine learning for multi-domain operations applications, volume 1006, pp. 369-386. SPIE, 2019.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35:19523-19536 2022.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. In ICLR, 2018
Kai Wang, Bo Zhao, Xiangyu Peng, Zheng Zhu, Shuo Yang, Shuo Wang. Guan Huang, Hakan Bilen, Xinchao Wang, and Yang You. Cafe: Learning to condense dataset by aligning features. In Proceedings of the IEEE/CVE Conference on Computer Vision and Puttern Recognition, pp. 12196-12205. 2022.
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint arXiv: 1811:1111..1999 2018
Weiran Wang and Nathan Srebro. Stochastic nonconvex optimization with large minibatches. arXiv preprint arxiv: XXXXv:1709.080 787208878, 2019.
Yue Wang, Ziyu Jiang, Xiaohan Chen, Pengfei Xu, Yang Zhao, Yingyan Lin, and Zhangyang Wang. E2-train: Training hate-of-thhearn cnns with over 80% energy savings. Advances in Neural Information Processing Systems, 32, 2019.
Max Welling. Herding dynamical weights to learn. In Proceedings of the 26th Annual International Conference Machine Learning, pp. 1121-128, 2009.
Yawen Wu, Zhepeng Wang, Yiyu Shi, and Jingtong Hu. Enabling on-device training by self- supervised instance filtering and error map pruning. JEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 39(1 1):3445-3455 2020.
13

---

Published as a conference paper at ICLR 2024
Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, and Tongliang Liu. Moderate coreset: A universal method data selection for real-world data-efficient deep learning. In The Eleventh International Conference Learning Representations, 2023. htttps:://penreveew..rtt
id=7D5EFCbOaff
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Data, 10(1):41, 2023a.
Yu Yang, Hao Kang, and Baharan Mirzasoleiman. Towards sustainable learning: Coresets for data-efficient deep learning, 2023b.
Ruonan Yu, Songhua Liu, and Xinchao Wang. Dataset distillation: comprehensive review. arXiv preprint ar XXix:2301.070111 2023.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In International Conference on Machine Learning, 2021.
Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. In Proceedings of the IEEF/CVE Winter Conference on Applications of Computer Vision, pp. 6514-6523, 2023.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference Learning Representations, 2021.
Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage-centric coreset selection for high pruning rates. In The Eleventh International Conference on Learning Representations, 2023, URL https:
https::/epenrevil ppw.revievveveeeeeoo
net wwt.:neetooooiieeeeeee
Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, et al. Lima: Less is more for alignment. arXiv preprint arXiv:2305. 2023.
14

---

Published as a conference paper at ICLR 2024
APPENDIX
A A MOTIVATING EXPERIMENT FOR REPEATEDLY SAMPLING RANDOM SUBSETS
We have shown in the main body of the paper that Repeated Sampling of Random Subsets (RS2) allows for faster training and more accurate models when compared existing data pruning and dataset distillation techniques. In this section, we discuss a simple experiment that helped motivate our work.
Existing data pruning methods are primarily based on the intuition that small subset S" of "diffi- cult' (Toneva al. 2018 Paul et al. 2021) (or sometimes "easy' (Sorscher et al. 2022) examples contained in the full dataset S are close to (far from) the decision boundary and thus likely to be the most informative for lcarning. During our initial investigation into data pruning methods, we empirically studied this intuition. Calculating the distance between training example and the decision boundary, however, can be challenging because the decision boundary is not known until training completes, and because the location of the decision boundary in high dimensional space can be computationally intensive to compute. Thus, we consider the following proxy measurement: To decide whether training example is close to the decision boundary, we find the nearest neighbor (e.g., Le distance) from the full dataset and check whether it has the same label as æ. If not, then the decision boundary in the input feature space must be between the two points (i.e., they are 'close' to the boundary).
We evaluated the above proxy measurement for all examples in the CIFARIO dataset decide whether each one was close to the decision boundary. Surprisingly, we found that the nearest neighbor for 65% of the training examples had different label than the example itself. In other words, in the raw feature space, this experiment provides some evidence that a majority of examples may be needed for learning the final decision boundary. This observation motivates RS2 as a strong data pruning baseline because it satisfies two desired properties: 1) it maximizes overall data coverage by periodically resampling the subset and 2) it provides representative examples from the dataset without overfitting. We remark that majority of points are unlikely to be the decision boundary if we first encode the input examples x into a more semantically meaningful feature space. Learning such an encoding. however, requires first learning a decision boundary over the raw features and must be done during the model training itself. We leave detailed study of this experiment, and the implications of this observation on selecting hard/easy examples for importance-samplinn based data pruning to future work.
B ADDITIONAL DETAILS ON EXPERIMENTAL SETUP
We expand on the experimental setup described in Section 5.1 of the main body of the paper.
B. DATA PRUNING BASELINES
We consider the following 24 data pruning baselines. We refer the reader to existing studies for more detailed deseriptions of these methods (Guo et al., 2022).
1. Random: standard baseline; sample static random subset of the dataset once before training
2. Contextual Diversity (CD) Agaawal et al. 2020
3. Herding (Welling 2009 Chen et al.
2010
4. K-Center Greedy (Sener & Savarese
2018
5. Least Confidence (Sachdeva al.
202
6. Entropy (Sachdeva et al.
2021)
7. Margin (Sachdeva al.
202
8. Forgetting (Toneva al.
2018)
9. GraNd (Paul et al. 2021
10. Contrastive Active Learning (CAL) (Liu et al.
2021
11. Craig MMizzasoleiman et al.
2020
15

---

Published as a conference paper at ICLR 2024
12. GradMatch (Killamsetty al. aa)
13. Glister (Killamsetty al. 202 lb)
14. Facility Location (FL) (lyer et al. 2021
15. GraphCut (Iyer et al. 2
16. Active Learning with confidence-based example informativeness (AL (Conf)) PPrk et al.
2022)
17. Active Learning with loss-based example informativeness (AL (LL)) PPark et al.
2022)
18. Active Learning with margin-based example informativeness (AL (Margin)) Park et al.
2022)
Self-supervised prototypes with easy examples (SSP-Easy) (Sorscher et al.
2022)
20. Self-supervised prototypes with hard examples (SSP-Hard) (Sorccher et al.
2022
21. Supervised prototypes with easy examples (SP-Easy) (Sorscher et al.
2022)
22. Supervised prototypes with hard examples (SP-Hard) (Sorscher et al.
2022
23. Moderate-DS (Xia et al., 2023)
24. Area under the margin (Coverage-centric Coreset Selection) (AUM (CCS)
(Zheng et al.
2023)
25. Coresets for Data-efficient Deep Learning (CREST) YYang al.
2023b
B.2 DATASET DISTILLATION BASELINES
We compare against the following eight dataset distillation methods.
1. Dataset Distillation (DD) (Wang et al.
2018
2. Flexible Dataset Distillation (L.) (Bohdal et al.
2020
3. Dataset Condensation (DC) (Zhao et al. 2021)
4. Differentiable Siamese Augmentation (DSA) Zhao & Bilen 2021
5. Distribution Matching (DM) (Zhao & Bilen 2023)
6. Aligning Features (CAFE) (Wang al. 2022
7. Aligning Features Differentiable Siamese Augmentation (CAFE+DSA) (002))
(Wang al.
8. Trajectory Matching (TM) Cazenavette et al. 2022)
B.3 ADDITIONAL TRAINING DETAILS
For all experiments (except GPT2 due to cost considerations) we conduct three runs using different random seeds and report the average accuracy and runtime. We include additional details on the hyperparameters and hardware used below.
Hyperparameters We use the following hyperparameters for experiments: For CIFAR10 and CIFAR100 experiments, we use SGD as the optimizer with batch size 128, initial learning rate 0.1, cosine decay learning schedule (Loshchilov & Hutter 2016), momentum 0.9, weight decay 0.0005, and 200 training epochs. For data augmentation, we apply random cropping and horizontal flipping with four-pixel padding on the 32x32 training images. For ImageNet30 and ImageNet, we use the same hyerparameters as above except for a larger batch size on ImageNet (256). We also use different data augmentation: training images are randomly resized and cropped to 224 x24 with random horizontal flipping. Further details can be found in the source code.
Hardware Setup We run image classification experiments on university cluster with job isolation and NVIDIA RTX 3090 GPUs. We run GPT2 experiments using AWS P3 GPU instances with eight NVIDIA V100 GPUs (as GPT2 experiments require more compute power). Utilizing the former allows us to reduce the cost of our experiments (e.g., compared to training entirely using AWS), but introduces the potential for increased variance compared to training with completely dedicated hardware- though all experiments run with exclusive access one GPU and set of CPU cores, cluster load can influence runtime measurements. We observe small variance across multiple runs of the same experiment small datasets (e.g., CIFAR10 the three standard deviation is generally less than one percent of the total runtime), but larger variance on ImageNet, likely do to an increased load the shared file system and longer experiment runtimes. As such, calculate the runtime of
16

---

Published as a conference paper at ICLR 2024
each method on ImageNet follows: We calculate the minimum time per mini-batch using all runs across all methods, and then use this value to compute individual method runtimes by multiplying by the total number of batches during training and adding any necessary overheads for subset selection. More specifically, we have: the total runtime of any method Twaal = T Tunal, subset_ selection Tioal trainttrininggin time with Tioal training time glabal minimum, batch_ runtime X total Lotal_number.cmm __eorr_______eeeee batches. Note that this means runtimes differ only due to subset selection overhead as expected (once a subset has been selected, all methods train on the same number of examples per round using the same hardware, and thus should have the same per round training time). Furthermore, we calculate Twoal subset selection as the minimum subset selection time observed across three runs of each method. The above runtime calculation allows us to minimize the affect of cluster noise on our experiments and ensure fair comparison for the ImageNet -imeto-aceuracy reported the paper.
B.4 BASELINES WITH REPEATED SUBSET SELECTION
We expand on Section 5.2 and provide additional details for our implementations of baseline data pruning methods with repeated (per-round) subset selection. Accuracy results on CIFARIO when training with these methods are shown in Table I
B.4.1 DESCRIPTIONS OF -RS BASELINES
The -RS methods in Table I (left) start from an initial importance distribution over all training examples and then sample subset for learning from that static distribution each epoch. The initial distribution is generated by pretraining an auxiliary model(s) on the full dataset for 10 epochs and then using this model quantify example importance according the corresponding baseline method of interest (in the same manner as the baseline would quantify example importance using a partially pretrained auxiliary model when generating a static subset at the beginning of training Guo al.) (2022)). We do not present -RS results for baselines methods which do not generate importance scores for all examples.
For each baseline, to create a categorical distribution over the dataset we apply the fomorrr function to the baseline-specific example scores that are normally used for subset selection. Specifically, given dataset S (x1, 1/ -
Least Confidence-RS We calculate 8teast confedence (x;s) = 1 - maxj-11....f P(ù: = j|x for each data point using the partially pretrained auxiliary model. The example importance scores for each instance are taken to be-
Steast confudence (x)).
Entropy-RS -RS
We calculate the example importance scores as in Least Confidence-RS, but replace C
Sleast confidence Xx) with Seuropy (xi) Σラ= P(u = j 11x; P(ù: = =]|x)).
Margin-RS
of.. (P x1) (()](x)) for each data point using the partially pretrained auxiliary model. The example importance scores are taken to be
We calculate Smarginn (x1)
-Sarrii (x:).
Forgetting-RS We create the categorical distribution such that the probability of sampling data point x; is proportional the number of times x; is missclassified while partially pretraining the auxiliary model. A missclassification is defined as follows: is classified incorrectly in the current epoch after having been correctly classified in the previous epoch.
GraNd-RS
We calculate the categorical distribution such that the probability of sampling data point x; is proportional to the average contribution from x; to the decline the training loss while pretraining the auxiliary model.
CAL-RS We calculate the categorical distribution based on a heuristic for how far each data point is from the decision boundary. Examples that have predictive likelihood that diverges most from their neighbors in the embedding space have a higher probability of being sampled (they are assumed to be closer the decision boundary and thus more important) (see Liu al. ()
We create the distribution based on the distance between each data point x; and its corresponding class mean in the embedding space (see Sorscher et al. (2022)). That is the probability of sampling a data point z; is higher if, in the embedding space, 2; is closer to the mean of all embeddings with the same class label.
SP-Easy-RS
17

---

Published as a conference paper at ICLR 2024
B.4.2 DESCRIPTIONS OF RCC BASELINES
In between each round, the -RC methods in Table (right) use the current weights of the model being trained to reselect the subset according to the baseline of interest's standard subset selection algorithm. That is, each epoch the current model weights are used to either recompute example importance-in in this case the examples with the highest importance scores are then selected for the subset at the next round or 2) directly re-select the subset for training (e.g., the case of submodular methods). We do not use any pretraining present -RC results for baselines which generate subsets independently of model weights. We show the pseudocode for -RC methods in Algorithm 2 Sampling in Line 4 of Algorithm is specific for each baseline and depends on the current state of the model.
auxiliary model for the -RC methods and do not
Algorithm 2 -RC Baselines
Require: Dataset S = {æ,, Ui ) selection ratio E (0, 1}, batch size b, initial model wo, X rounds, baseline method M
1: T - [N/6]
2: t
3: for round j == X do
4: S' + M.sample [.lsaapllesuuss(((... r; w') for k = to batch m + [ - 1) .). b. bb w² + trainnw' m)
5:
do
6:
7:
8:
return w
B.4.3 COMPARISON TO CREST
In addition to our -SS and -RC baselines above, we evaluated the repeated subset selection method CREST under the same conditions presented in Table CREST achieves accuracy rates of 87.1%, 90.4%, and 92.4% for selection ratios r of 5%, 10%, and 30% respectively. noteworthy that CREST distinguishes itself from -RC methods by undergoing multiple rounds of training on the same subset before resampling.
B.4.4 TOTAL UNIQUE EXAMPLES SEEN BY REPEATED SUBSET SELECTION
We compare the total number of unique examples from the full dataset selected throughout training (as part of some subset) when using RS2 and select per-round baselines described above. Result on CIFAR10 with selection ratio of 10% are shown in Figure 4 By definition, RS2 without replacement the fastest method to utilize all training examples, however other baselines which reselect the subset each round (e.g., Margin-RS, Margin-RC, and Craig-RC) also explore nearly all training examples in the full dataset (e.g., >99%). Modifying baseline methods which select static subsets to re-select the subset each round leads more of exploration of full dataset and contributes to the improved accuracy of these baselines compared to their static counterparts (e.g., Table vs. Table 3)
C ADDITIONAL EXPERIMENTAL RESULTS
Here we include additional evaluation result comparing Repeated Sampling of Random Subsets (RS2) to existing data pruning and dataset distillation methods. These results extend those presented in Section the main paper. We briefly discuss each result (table) in turn and how connects to the arguments made in Section 5
C.1 END-TO-END DATA PRUNING ACCURACY ON CIFARIO AND IMAGENET
In Tables 4 show the end model accuracy of RS2 and existing data pruming methods for varying selection ratios on CIFARIO and ImageNet respectively. The numbers in these tables were used to create Figure 2 in the main body of the paper. Recall from the discussion of Figure 2 in Section 5.2
18

---

Published as a conference paper at ICLR 2024
50000
40000
Examples
20000
RS2 w/o repl Margin-RS
10000
Margin-RC
Craig
50
100
150
200
Epochs
Figure 4: The total number of unique examples from the full dataset selected for training (as part of some subset) when using RS2 and select baseline methods with repeated subset selection. Dashed lines indicate the epoch which each method saw 99% of the full dataset. RS2 without replacement is the fastes method to explore the full dataset, but baseline methods with repeated subset selection also explore >99% of the examples in the full dataset over the course of training.
that we use the combined baseline methods from recent studies (Park et al. 2022 Guo al. 2022)
together with newer prototype-bare based data pruning methods (Sorscher et al. 2022 Recall also that for these tables, subset once before training starts. We use all baseline methods for CIFAR 10, but some methods do scale to the larger ImageNet dataset. We show Table 8 that active learning already takes more than eight hours for subset selection in some settings on CIFARI0 and we are not aware of a scalable implementation of prototype-based methods that would allow for training on ImageNet.
sample static the setting proposed by these works: for all baselines,
As in Figure 2 Tables 3 show that the repeated sampling of RS2 leads to accuracy improvements compared to existing data pruning methods which sample static subset (see discussion in Section(5.2). RS2 outperforms existing method across selection ratios. Interestingly. in the low compression regime (r > 30%) our results support the intuition of many data pruning methods- 'harder' samples benefit model training. For example, in Table 3 for 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 For example, in the same setting above, RS2 reaches 95.2% accuracy. While RS2 also generally outperforms existing methods in the high compression regime (r S 10%), for extreme compression find RS2 be inferior existing methods. We hypothesize
50%, SSP-Hard (self-supervised prototypes
existing baseline methods- those which select 'hard' or 'easy' samples.
ratios, like 0.1% % on ImageNet, that this occurs because in these extreme regimes, only few examples are shown to the model for each class and these examples likely have large variance when using repeated random sampling coupled with data augmentation. In this setting, it may be best to select a static subset of only the easiest examples as highlighted in recent work (Sorscher al. 2022). however the significance of this regime is debatable given the low end-model accuracy of all methods. Improving the performance in these regimes is of interest for future work.
19

---

Published as a conference paper at ICLR 2024
Table 3: Accuracy achieved by different data pruning methods when training ResNet-18 on CIFARIO for different subset selection sizes. Best method bolded; Next best underlined.
Selection Ratio (r)
1%
5%
10%
20%
30%
40%
50%
100%
Random
3..7:11.7
6..5
7.
88.1 0.5
91.0:10.3
91.9:00.2
93.2= 0.3
95.5 0..2
23.6=1.9
38.1+222
58.8+20
81.3=2.5
90.8--0.5
93.3=0.44
94.3=0.2
95.5+0.2
Herding
3..8
51.0#:31
63.54:3.4
7..1=2.5
80.1-222
85.2+0.9
88.0=11 1.1
95.5
K- X-Center Greedy
31.1::1.2
21.422.1
75.2.
87.3=1.0
91.2.10.66
92.2:1..5
0.5
95.5.00.2
Confidence
3.221199
57.613.1
90.31:0.4
93.120.5
Entropy
2..1::133
35.31.3.0
57.6.12.88
8..9-0.4
8..8.:1.6
93.2:10.2
94.4
95.5
Margin
2..2:1..0
43.423.3
85.5=099
91.3--0.5
93.6-20.3
94.5=0.2
95.540.2
Forgetting
35.2::1.6
52.11:2.2
1.00
0.9
92.31.0.4
93.6110.4
93.8-0.3
95.51..2
GraNd
1.3
3..842..
75.44 1.2
0.66
92.4110.4
93.3-10.5
9422-044
95.540.22
CAL
37.8=2.0
60.0=144
1..8=10
80.=1.1
1.
87.5=0.8
89
95,5+0,2
Craig
11.7
45.2442.9
60.2:14.4
79.6 3.1
8.
90.8 1.4
93.3 0.6
95.5
GradMatch
3..8-1.0
47.2-0.7
61.5424
799922
874-20
9.
92.9-066
95,540.2
Glister
32.9=2.4
50.7=
1.07=
06
90.1=00.7
91.5=0.5
93.3-0.6
95.5=002
FL
1..9
60842.5
1.
85.6199
41
93.240.3
0.2
95.5
GraphCCt
1.3
65.7=122
1..0=
863=0.9
90.2=0055
91.5=0.4
93.8-0.5
95,5+0.2
(Conf)
1..2221.5
60643.11
83.620..7
9.55-0.4
93.4-0.44
94.8-0.3
9..1
95.5
AL (LL)
37.5-4.3
63.1-200
85.0=0.9
9122-0.7
93.8-0.66
94,4=0.5
95.0=0.4
95.5+0.2
AT. (Margin)
36.7-0.8
62.21111
84.51107
0.5
93.9-0.4
94.5
95.3-022
95.5
SSP-Easy
1..6=21.7
62.1
72.0=0.8
85.9004
90.0=0022
91,320.4
92.7-000
95.5
-SP-Hard
90.31.0.4
91.910.3
SP-Easy
17.1=1.4
59.8=0.5
72.3+29
85.1=10
89.6=0.2
91.6=002
92.7=0.2
95.5
SP Hard
35.0:10.7
60.91.88
7..111.1
0.3
89.6
91.5
93.0
95.5
Moderate-DS
36.2330
64.913.2
79.0=208
87.0=0.3
90.0=:0.0
91.620.0
92.6-0.1
95.5
AUM (CCS)
39.6=3.2
68.7-4.1
86.1
90.9-033
93.0=20.2
89.7
94.9=0.2
95,5+0.2
RS2 w/ repl
51.123.5
86.710.8
89.711.2
93.5-0.3
94.210.11
94.6.0.2
95.1=022
95.510.2
RS2 w/ repl (stratified)
51.1=2.55
86.620.5
89 99.840.4
934-0.1
94.5
94.820.1
95.1-033
95,5+0.2
RS2 repl
51.8=22.0
8..1=008
9..7=1055
94.0=0.5
94.3#0.2
94.720.1
95.2-0.1
95.520.2
Table 4: Accuracy achieved by different data pruning methods when training ResNet-18 ImageNet for different subset selection sizes. Repeatedly Sampling Random Subsets (RS2) considerably outperforms existing methods for realistic selection ratios. Best method bolded; Next best underlined.
Select Ratio (r))
0.1%
0.5%
1%
5%
10%
30%
100%
Random
0.76=0.01
3.78=0.144
8.85=0.46
40.09:t0.21
12.02:0222
14.11:00.05
69.52=0.45
CD
0.76=0001
1.1810.06
2.16.10.18
25.82.1.2.2
43.84-10.12
62.13:10.45
69.52-10.45
Herding
0.34-0.01
1.740.13
4.17-0.26
17.1110.34
28.06:00008
48.58-10.4
09.52-00.55
K-Conter Groedy
0.76=0.01
1.57=0.09
2.96=0.24
27.36+20.08
44.84=11008
62:1::00:46
69.52=0.45
Least Conlidence
0.29=0.04
1.03:10.25
2.03
27.05:1:..25
44.47:1:.42
61.8:110.33
69.52-0.45
Entropy
0.31.10.2
10117
2.26.10.3
28.2112.83
1..68
61.82.1.311
0.45
Margin
0.47-0.02
1.99-00229
4.73-0.64
15.99.11.67
50.29:10.92
63.62:0.115
69.52 02.5
Forgetting
0.76=0.01
4.69=0.17
14.02+0.11
47.64+10.03
55.12-+0.13
62.49:00111
59.52
GraNd
1.040.04
7.02-10.05
18.120.22
43.53:1-0119
49.92-10.21
57.98
69.52=0.45
Craig
L.3=0008
5.4420052
9.4
32.3-11.24
38.77-20.56
44.89-13.72
69.52-0045
GradMatch
0.93-0.04
5.240.22
12.28+00.49
40.16:22.28
15.91
52.69-2.116
00.52-0045
Glister
0.98=0.06
5.9120042
14.87=0.14
44.95-00.28
12.044+:1118
60.26:10.28
69,52=0.45
FL
1.23.0.03
5.78
12.72.10.21
1..85.1..25
$1.05
0..04
69.52.10.45
GraphCut
1.11=0.09
7.66:20.3
16.43:0.53
42.23::0.6
40.53+20.42
63.22::0.66
69.52=0.45
RS2 repl
0.17-0.03
16.35-0.56
44.45-0.07
45.417.18
64.87
68.23-10.07
50-5224455
RS2 repl (stratified)
0.18=0002
33.66:0.113
46.96120.13
62.32++0.08
64.92-0.10
68.24:10.08
69.52=0445
RS2 wio rep!
0.19:00.22
18.2:10.55
44.42-10.04
63.2-1.007
66.0:10.18
68.19:10.06
69.52-00.45
20

---

Published as a conference paper at ICLR 2024
C.2 END-TO-ENT TO-ENN DATA PRUNING ACCURACY ON CIFARIOO AND IMAGENET30
In Table 5 we include additional end-model accuracy results for RS2 and existing data pruning methods two datasets, CIFAR 100 and ImageNer30, included in the main paper due to space considerations. For these experiments, we include representative set of baseline methods which sample static subsets, together with our modified version of the recent prototype-basee data pruning method which utilizes repeated subset selection between each round (SP-Easy-RS) (see Section 5.2). Thus, eextenss the end-model accuracy results presented previously for CIFARIO and Observe that RS2 also outperforms existing methods on these datasets. For example, in the high compression regime (r = 10%), RS2 without replacement reaches 73% accuracy on CIFARION 100, while the best baseline method, our per-round prototype-based data pruning method reaches only 66%. Existing methods which sample static subsets only once before training begins reach just 36% in this setting.
and ImageNet in Figure Tables [ [
C.3 END-TO-ENT DATA PRUNING ACCURACY ON MEDMNIST
To demonstrate the application of RS2 in real-world, class-imbalanced settings, we present end-model accuracy results for RS2 alongside selected baselines on four datasets from MedMNIST YYngg et al.) 2023a in Table 6 RS2 achieves the highest end-model accuracy on each dataset. Moreover, for selection ratio r 10%, RS2 achieves comparable accuracy to training on the entire dataset every round. Specifically, it achieves 90. 7% compared to 92.2% on PathMNIST, 72. 72. compared to 75.5% on DermaMNIST, 95.3% compared to 96.3% on BloodMNIST, and 90.2% compared to 92.0% on OrganCMNIST.
C.4 END-TO-END DATA PRUNING ACCURACY FOR VISUAL TRANSFORMERS (VIT)
In Table we show end-model accuracy results for RS2 and selected baselines for a different neural network architecture, i.e. ViT Dosovvisskiy al. 2021). Specifically, train ViT with patch size four on CIFARIO. RS2 achieves higher end-model accuracy than selected baselines across varying selection ratios. For example, RS2 achieves 67% accuracy with r 10% while the next closest baseline (GraphCut) achieves 59.6%. These results show that our initial findings extend to ViT models as well, i.e., RS2 is a strong baseline which outperforms existing data pruning methods.
21

---

Published as a conference paper at ICLR 2024
Table 5: Accuracy achieved by select data pruning methods when training ResNet- 18 on CIFAR100 and ImageNet30. Best method bolded; Next best underlined.
Dataser
Ratiotr)
1OS5
70%
1006
Randor
32.0:0055
536::06
63.6:10.5
67.22005
73.1
75.2=0.2
70.12:03
77.51022
7KT.20.
Center Greedy
339111
56.21:1
64.5100
695294
72..205
74.313
75.8-0.3
77.2.:0.
728182
7K.49..
Margin
1872:211
882118
58. 1110
65.1296
70128.5
733399
25.420.3
7K749.
Poegriting
M44210 10
96.7499
64.:10..7
MA529
25 73995
25.5220.
267491
Gn/N
4942110
628:10.
7053203
24.5
228200
Glieer
16.4:10 0
$5.52100
71
73.5204
25.0-633
760102
22
2672203
30.1111
160108
0551100
095204
71.11
25.4.92
2K7492
(Couf)
16.15:16
55.74:10
6588
7.6--0.5
73.7404
76.
77.1-63
787
CIFAR
(11.3
31:218
3
649:18
71128
38320
267102
(Margis)
6
660:26
704295
21.22b1
26
SSPxFacy
500E13
035215
620292
70:2:00
250
267202
SSP.Red
29.7
5333
6322005
07 22:202
71:2502
7299022
248:201
730100
22
2KTH02
334409
53.04200
6300100
70:3:03
733302
74.--02
7623:06
769203
7KTH02
312827
$3.6204
6300:06
63::00
E0::11
730000
746-008
738209
7742044
7K7402
SP-EaryBe RS
66111
72.75:06
746:205
75.5=02
76.3-0.3
769204
77.6=6.1
78.000.11
78.3003
787.02
RS2 wt rept
08215
16 1641111
761:19.
75
777730
763-203
784102
787181
7KT
R82 wi upt (smmited)
08422
75 91003
775201
71
78122011
7672002
7K7492
RS1 weo mpl
7M
749207
77.120.1
77. 775204
7K02811
76.3-0.2
78.220
18420
7K7207
Rondom
1200
63 537399
86 91004
931203
90.25.33
940222
94.620011
95 2500
454202
96 12.1
K-Ganter Groaly
08.2009
64 1::5
88 9:2.4
01A203
914202
94 4442
95. 1-:
0531202
656202
96 120
Margin
$6.91111
77 77
8377205
905204
02.92:02
94 444303
05.1-02
958
96 961
Fregsting
64.12009
65.4
87.3+0055
900+0.
036400
9482
949-002
05.1+02
901
Gnadd
00.3:009
65.7+:0.5
00.000.5
924200
93.640.3
94.7
0511002
95.5002
957
901
Gliser
72
$2.9::055
87.0:0.44
012:003
92.75-03
93.3+-333
9422-02
950002
9582002
901
7..9:066
$3.01:033
885500.3
01.2-0.3
92.91.22
93.7
014
95.3101
956:002
901
AL (Conf)
7.
57 $7.09:055
90.3:05
01.1204
9..300333
95.1
05.5-04
95.7001
96118.11
961
ImageNer30
AL (LL)
53 7
8931100
05.1205
9472022
95.3100
05
95X103
961101
Al (Margin)
71.9:009
$6.7+:0.5
00.1
01.3004
9452003
911002
036-011
958:001
961
SSP-
71.3:0.5
$1.5+2000
87.4:0.7
001:003
92.6:-055
93.1224
9122-02
94910.11
953:202
#01
SSP Hard
1.4
$3.0::0.7
87.4:0.3
01.1:02
9251022
912200
94.-002
949104
9522102
961
SP Easy
10
$2.40:33
87.1:2133
899205
926114
93.4202
94.3-03
966102
95.2000
961
SP Hard
08:112
$166::3
87.6:20.7
90520
927210
93.71933
9433022
94.104
953102
9K1
SP-Eac-RS
80.120
92.35:
03.2:00.
91.5204
945500
950033
949-=02
954203
957202
961
BS2
91.72066
9:73::
94,9:0.2
95.4004
056200
059+01
961
(eraiifal)
91.7:06
948:244
94,9:03
05.5=000
0564003
961
920::04
94.620.
94.500.
03.22033
95.7=4.1
05.3:003
96.1001
Table 6: Accuracy achieved by different data pruning methods when training ResNet-18 with 10% on MedMNIST datasets. Best method bolded; Next best underlined.
PathMNIST
DermaMNIST
BloodMNIST
OrganCMNIST
Random
85.8:1-0.8
68.5=0.6
86.3+ 1.6
84.910.77
77.9144
68.0:10.5
6..816..5
71.31.3.2
Herding
55.2
18
69.5 1.4
37.6--3.33
K-Center Gready
84.4:-0.9
66.9=0.1
25.4+2.5
85.8+00.6
Least Condidence
67.71:4.4
19.6::
16
57.241:3
Entropy
62,3::3.11
59.8:12
55,3=133
56.3+t9.5
Margin
71.2:16.0
6.55=115
66.3
61.9--2.88
GralNd
72.5.16.2
66.9.10.1
49.611.0
$2.2.14.6
79.6:16.9
62.9.7.1
81.9
14.04
Craig
84.6:20.66
68.8=0.2
84,8+1.11
1..12
Glister
85.8:10.88
69.5=0.1
87.0+ 1.3
84.7+00.1
FL
84,7+00.5
69.3-0.6
86.8 14
84.7-00.5
GraphCCut
84.9::0.2
68.9=1.0
07.1+0077
84.9-0022
RS2 repl
87.9-22.55
70,5=222
89.91:.11
87.5+3300
RS2 w/ repl (stratified)
89.7.1.0.8
72.7.0.4
95.2.00.5
90.0.10.3
RS2 repl
90.7:10.6
1..62
95.310.11
90.2-1.0.2
22

---

Published as a conference paper at ICLR 2024
Table 7: Accuracy achieved by different data pruning methods when training ViT with patch size four on CIFARIO for varying subset selection sizes. Best method bolded; Next best underlined.
Selection (r)
5%
10%
30%
50%
100%
Random
37.1
50.6.10.5
59.2.10.9
66.1
70.6.10.6
72.5
74.4:11.1
78.0
CD
1..2
1.2
44.6422
32.94377
61.21
63.6=0.7
67.342.00
78.0=0.9
Herding
25.7.1...5
40.7..3.5
47.514.11
57.61288
66.8.13..
6..61.244
72.9.13.0
78.010.9
K-Center Greedy
35.5.40.8
1.50
57.6+00.4
64.64:1.2
68.9-10.3
72.1-0066
74.54-0.3
78.0=00.9
Least Confidence
21.3+11.6
34.2+33.6
39.7+332
4..6+4.3
17.2+177
61.7=110
66.1
78.0=0.9
Entropy
23.7:44.2
36.94:2.7
44.3#2299
54.3+114
61.4113
66.2=0.11
69.2-1:0.4
78.0=0.9
Margin
27.7:12.3
31.71.14
45.0:10.4
50.71:3.3
58.613300
62.61344
67.4:12.22
78.010.9
GrNNd
27.5:40.9
3.4
1.3
13.1
61.6110.7
65.0-0.3
68.4:104
78.0
CAL
35.4=22.1
48.74:3.1
55.5445
62.7+:.0
66.74:400
69.6-3.7
72.0+22.8
78.0=0.9
Craig
34.3:20.6
46.72:0.3
16.9+110
63.8+:10
68.1::0.5
70.0=118
7144:0.1
78.0=0.9
Glister
1..8+1.11
48.54-0.3
58.940.11
66240022
09.8:-0.7
72.6=0.3
74.0+112
78.0=0.9
FL GraphCCt
37.5+112
49.7+0077
59.6+00.6
65.7=0.9
69.9+-0.6
72.8=0.7
74.0=t0.6
78.0=0.9
40.2:4:1.6
53.0:1.3
59.6:10.3
65.910.88
70.9:10.5
0..7=:0.6
73.6::0.6
78.0
RS2 w/ repl
51.6.10.1
62.7.10.9
64.911.0
713110.2
73.5.10.9
75.3
75.5.10.4
78.010.9
w/ repl (stratified)
52.5:10.6
6.
65.6
70.5.088
72.71:0.6
75.1
77.3+:10
78.0=0.9
RS2 w/ repl
50.0.10.6
63.40..7
67.0.1022
72.1.0.3
742211
7.48
74.8113
78.010.9
C.5 END-TO-END DATA PRUNING TRAINING TIME
We now focus on additional results to accompany the runtime and tine-rr-accuraey results presented in the main body of the paper. Specifically, in Table g we show the total time needed for subset selection on CIFARIN 10 across all rounds for RS2 and compare to the total time needed for subset selection for existing data pruning methods which sample a static subset once before learning begins. In Table we show the same measurement for our baseline methods which utilize repeated sampling between each round. Note that the differences presented these tables are the dominant factor leading differences in end-to-end runtime between methods: Once subset has been selected for training at each round, all methods train on the same number of examples, and thus have the same per-round training time (assuming there no noise). Thus the method with the lowest subset selection overhead will also be the fastest method for end-to-end training.
9
C.6 TOTAL TIME FOR SUBSET SELECTION ON CIFAR10
& that sampling static random subset once before training leads to the lowest total subset selection time, but that repeated random sampling (RS2) also has low subset selection overhead, i.c., generally less than second CIFAR10. The subset selection overhead of RS2 is orders-of- magnitude less than existing methods, even though they sample the subset only once at the beginning of training. For example, most existing methods require over 200 seconds for subset selection because they require pretraining an auxiliary model on the full dataset for a few epochs in order to rank example importance. Some methods, however, require even more time for subset selection; Active Learning based methods can require more than 32,000 seconds to select a subset with = 50%. Once example importance has been calculated, Table D shows that this information can be used to resample the subset for training between each round (our -RS baseline methods, see Section 5.2) with little additional overhead. All such methods, however, still require orders of magnitude more time for subset selection compared to RS2 due to the initial pretraining ! On the other hand, recomputing the most important examples between each round (our -RC methods), leads to increased subset selection overhead. The reason for this is that reranking example importance requires computing the model forward pass for all training examples between each round. Thus, such methods generally are unable to significantly reduce the end-to-end runtime compared to simply training on the full dataset each round; Even with a selection ratio of 5%, the fastest -RC method requires more than 3500 seconds for subset selection, yet end-to-end training, each round on the full dataset, requires only 4500 seconds.
We note that the pretraining overhead of GraNd in Table uses the default hyperparameters from Guo al. 2022) in which the results from 10 pretrained auxiliary models are averaged, but for GraNd-RS in Table only one model for consistency across all -RS methods.
23

---

Published as a conference paper at ICLR 2024
Table 8: Comparison of the total time needed for subset selection for different data pruning methods when training on CIFARIO. Time reported seconds. The overhead of repeated random sampling is considerably less than existing data pruning methods. For reference, training on the full dataset for 200 epochs takes roughly 4500 seconds. Best method bolded; Next best underlined.
Select Ratio
118
315
1015
2018
3016
4016
2015
Xandom
0.61::0.0
0.00
00001::000
1.001=000
0.001::000
0.901::000
CD
257.78:8:100
243-75:50.06
247.01 13.73
244.29 15
263-42662118
254.46:99.55
254 254.7:::2.28
Herding
235 134
241 2:3.37
1500525
25% 09 12.35
256 11
768 91 25813
263 16:22116
K-Crner Groady
238.428:2.75
243.16:00. 10.16
243.12:5.1
266.71 1:5.54
250.00 2.2.1
260.44
259 37-.34.511
Lest Cosfidines
238.61::66
238,08:22 2.55
241 56.-96-5..30
239792-33.72
257.07
229 229.47
240.01-::500
Enncpp
239.4420091
242
239.5 5.57
242 7.49
235
240.77 1.19
239 2.:
Margi
241.71
245
240
240
243 233.12251
241484400
243 45-35--113
Forplling
234 78-2
GraNa
2406
2375.
559.37-5000
13
Crig
280
790.0:1130:94
2723
GrapliCu
325.6620.37
(Coaf)
00% 3:3544
1XK1199
13598 1845
32M4 11-177
AL..U.
396-52.1.44
10
5349
13200 821729
21913 WNISSETOON
32R63 1:
Al. (MMMinn
396 19.19
87% 92.
2107 71776
1881
1328 5:241
92871 6:2-28
SSP Easy
263.678:5.87
269 3.948
268 263.4
261.8426.49
264.5525.58
268.21
209, 29-5
SSP Hard
285.9113::25
29033:2645
244.22422.16
20341+2102
247 211.262:200
271 271,5944 29..00
SP Eay
229:06::2246
231 3394
231.47
23161
231.6623:66
231,5825500 5.05
233 4336224322
SP-Hard
227 07778881600 16
254 12
29085
2276743225
251 06:104
230
231 12 90
Mokrrie-DS
(529.128:75.71
$528.39 1528.39-75..0
5529 74.778
$528.18:75.00
757785
$528. 1528.10:77..07
5525, 20:75
ALM (CCS)
10105.011 8: 36.97
10106.00
13697
10106.01:156.77
10105:01 13369
10105.01 136697
10006.01 136997
10105.01 #1
RS2 wiespt
0.16::0011
0.16::001
0.16::001
0.16:001
0.15::0::
0.16::001
0.16::001
R52 ispl (uutifle))
0.6:2:002
0.22:003
0.7500011
0542003
0.33:0055
1.0
10P2-003
R52 wio regl
0009::001
0.1:0.01
0.11::011
0.12:001
0.142:001
0.15:001
0.19:001
Table 9: Comparison of the total time (in seconds) needed for subset selection for our dynamic data pruning methods when training on CIFARIO. The training subset is update for all methods after each round, either by resampling from a static example importance distribution (RS, left) or by recomputing example importance based model updates (RC, right). For reference, training the full dataset for 200 epochs takes roughly 4500 seconds. Best method bolded; Next best underlined.
Ratio
(r)
CD-RS
CT-BC
3800 41:71 16.16 K23
18
Hontny-BS
Hending-RC
17:1/-45
K-Czeter
79:3-5.000
344.12::5
36305199.
241
240.1=:133
247.27::3311
IIC
Margin RS
243 46:11.29
239.55
259 000.11::333
Marge
3715.31 7115.11:75.0
5066
5760
Fongating-
236 32.61
239.8:2334
236 236.24254.34
Beaalling-le &C
5758. 12622.55
9732.819:33.
3725 22:3-10.55
GriNE-R5
397.02:6.55
409.33-9.32 9.32
405.89:44744
GuaNd RC
939
29 334344- 163
CAI
45% 75.270877
540/012: 10
5:7 37.3
CAT JIC
NM09 11 10.
64647 1o.
67766 71 1715
Crais R5
1025 144 70.
161.0611611
102),92:11377
Chüs RC
20337.31
27407.62::55 2591
63 088--009.66
Clarrss
Giste:
4558.00-556655
4966.5742 57:457144444
6395 33-33.50
SR-Baag-RS
326.26 63.72
371.25 63.71
497.39
SP-Easy-Kee
R52 or repl (snutiiie)) wos
0.22 4: 0.03
0.25 = 0.01
0L9 0.05
RS1 repi (stutifeed) whrnel
0.2 0.08
0.75 0.01
(L03 IUIS
0.1::8.1
0.11:9.11
8.14:0011
6.1::001
0.11::0011
0.141001
24

---

Published as a conference paper at ICLR 2024
Table 10: The total time required for RS2 and baseline data pruning methods to reach a target accuracy cime-to-accuracy when training with varying selection ratios on CIFAR1O. Time is reported in seconds. Part 1/3. The best method(s) is bolded.
Target
Select Ratio (r)
1%
5%6
10%
20%
30%%
-00%
500
60%%
70%
80%
9096
Random
73
16
28
23
15
20
13
14
16
18
20
CD
352
289
297
284
290
286
Hending
295
296
275
283
279
273
278
281
28-5
291
Center Greedy
353
284
304
273
267
280
283
281
283
290
296
Least Coafidence
393
330
299
278
275
265
259
262
264
Eutropy
484
398
346
289
270
274
267
256
259
262
Margin
38.1
297
297
279
264
Forgetting
302
263
299
264
2.58
264
258
249
257
252
253
GraNd
2461
CAL
596
597
574
385
579
565
605
605
591
595
Craig
365
342
395
461
583
668
7740
Glister
280
274
264
270
278
283
278
280
291
293
30%
FL
377
605
H03
1279
1878
2179
2734
3239
3671
4696
4513
GraphCut
371
.57
771
1268
1617
2355
2684
3462
3771
4427
4455
AL (Conl)
395
395
395
395
395
395
395
395
395
395
395
(1..)
386
386
386
386
AL (Margin)
383
383
38.3
38.3
383
383
383
38.3
383
383
383
SSP-Easy
SSP Har-Hard
403
325
330
307
309
308
283
283
2.86
293
289
SP-Easy
295
246
258
2249
246
254
240
243
SP-Hard
315
260
262
250
247
250
257
250
2.51
248
252
SP AP-Easy-RS RS
284
249
256
262
249
250
257
249
2.50
249
252
RS2 w/ repl RS2 w/ repl (stratified)
67
36
21
15
19
12
14
16
59
20
43
27
15
19
12
14
1.5
18
20
RS2 wio repl
Random Cl)
78
109
65
55
69
49
56
48
617
354
3666
3884
3611
325
3118
349
304
Herding
345
K- Center Greedy
390
397
322
314
309
318
323
331
327
317
Confidence
383
Entropy
513
412
339
345
324
321
314
303
Margin
755
439
4017
359
351
305
308
314
304
Forgetting
455
386
350
333
306
305
306
306
295
GraNd
2811
2550
2531
2454
2498
2453
2408
2509
2428
CAL
881
764
652
633
630
612
648
638
628
635
Craig
458
$23
S37
568
633
704
782
885
946
993
Glister
50% acc
FL
695
909
1341
1917
2219
2771
3267
3704
4733
4535
GraphCut
1664
2305
3506
AL. (Conf)
895
89.5
895
895
895
89.5
895
895
895
895
(L.L)
867
867
867
867
867
867
867
867
867
867
AL (Margin)
862
862
862
862
862
B62
862
862
862
B62
SSP-Easy
375
394
336
333
336
316
323
314
324
329
SSP-Hard
432
433
365
357
358
332
326
3.5
330
329
SP-Easy
340
362
306
301
284
287
271
282
261
293
SP-Hard
301
290
SP-EasyRR
355
335
289
298
304
290
w/ repl
279
66
61
48
47
56
RS2 w/ repl (stratified)
250
87
123
83
69
(0)
72
57
64
54
RS2 wlo repl
64
46
46
58
38
41
32
C.7 TIME-TO-ACCURACY ON CIFARIO AND IMAGENET
Finally, as our primary focus is on reducing time-to-accuracy, we include in Tables 10 14 the time for select baseline methods and RS2 reach a set of accuracy targets when training with varying selection ratios on CIFAR1O 10 and ImageNet. For the active learning time-to-accures
results in these tables, we report the runtime of the smallest selection ratio that reached the given accuracy. This prevents active learning to-curr-ccc from being dominated by large subset selection overheads as the selection ratio increases (e.g., Table 8), when these selection ratios are not strictly needed to reach the desired accuracy. As shown in the main body of the paper, RS2 provides the fastest time-to-ace moa-tro-cc compared to existing methods. Dashes indicate that the given method and selection ratio failed to reach the target accuracy. We leave detailed study of these results for future work. In particular, an interesting question how to decide what selection ratio r one should use in order to minimize runtime reach desired accuracy.
25

---

Published as a conference paper at ICLR 2024
Table 11: The total time required for RS2 and baseline data pruning methods to reach a target accuracy (ime-to-accuracy) when training with varying selection ratios on CIFARIO. Time is reported in seconds. Part 2/3. The best method(s) is bolded.
Target
Select Ratio (r)
15
5%
10%
20%
30%
40%
50%
60%
70%-
80%
90%
Random
364
216
184
139
136
139
130
126
143
Herding
926
760
456
406
418
395
415
393
Greedy
Least Confidence
911
514
455
453
420
374
372
369
Entropy
Margin
705
564
479
473
387
402
387
366
Forgetting
374
356
GraNd
2727
2689
2573
2583
2523
2489
2584
2489
CAL.
1025
Craig
775
664
693
724
803
854
966
1020
1075
Glisser
601
429
409
383
396
70% acc
Fl.
1144
1467
2009
2299
2855
3326
3785
4807
4597
GraphCut
1136
1465
1734
2484
2804
3578
38899
4536
4538
AL (Conf)
2884
2884
2884
2884
2584
2884
2884
(LL))
2804
2804
2804
2804
2804
2804
2804
2804
2804
AL (Margin)
2833
2833
2833
2833
2833
2833
SSP-Easy
716
445
440
404
412
407
410
399
390
SSP-Hard
SP SP-Easy
705
431
409
403
370
355
363
332
373
SP-Hard
SP-Easy-RS
RS2 w/ repl (stratified) repl
213
260
179
155
151
144
126
145
126
121
Random
CD
917
713
654
601
494
495
567
508
Hending
K-Center Greedy
692
695
635
606
535
557
511
563
Confidence
Entropy
912
675
584
521
516
498
529
Margin
Forgetting
719
641
616
511
518
541
451
$38
GraNd
2984
2831
2671
2681
2636
2585
2716
2650
CAL
1378
1132
995
978
968
921
816
Craig
1057
1063
1075
1116
1242
1218
Glister
788
650
614
604
S86
494
559
80% sce
FL
1765
2331
2525
3122
3528
3997
4936
4742
GraphiCut
1779
2681
3782
4106
4697
AL (Conf)
2884
2884
2884
2884
2884
2884
2584
2884
2884
AL (LL)
2804
2804
2504
2804
2804
Al. (Margin)
2833
2833
2833
2833
2833
2833
2833
2833
2833
SSP.Casy Tasy
8SP-Hard
840
786
739
$84
625
626
570
573
SP-Easy
SP-Hard
766
673
605
558
578
496
503
514
SP- SP-Easy-RS
564
634
637
585
501
590
567
490
538
516
RS2 w/ r/repl
331
383
334
308
343
274
293
337
312
324
RS2 repl (stratified)
R52 w/o repl.
333
278
257
278
264
212
264
241
270
264
26

---

Published as a conference paper at ICLR 2024
Table 12: The total time required for RS2 and baseline data pruning methods to reach target accuracy cane-to-accuragee when training with varying selection ratios on CIFARIO. Time is reported in seconds. Part 3/3. The best method(s) is bolded.
Target
Select Ratio (r)
5%
Random
1732
1906
2037
2149
2403
CD
1327
1615
1806
1917
2002
2181
2461
Herding
K-Conter Greedy
1412
1662
1915
2193
2310
24.33
2455
Least Confudence
1446
1546
1746
2268
2423
Entropy
1788
2024
2255
2468
Margin
1554
1749
1877
2020
2151
2498
Forgetting
GraNd
3580
3645
3944
3889
4042
4465
4531
CAL
2201
2292
2459
2658
2692
3042
Craig
1798
2024
2381
2613
2982
3134
3030
Glister
1718
1734
1885
2222
2368
2485
2639
GraphCut
28446
3782
4428
5387
5860
6159
6782
(Conf)
(I.LLL))
7740
7740
7740
7740
7740
7740
7740
7740
AL (Margin)
7787
7787
7787
7787
7787
7787
7787
7787
SSP-Easy
SSP-Hard
1740
1760
1961
21555
2273
2452
2449
SP-Easy
SP-Hard
1712
1906
2157
2206
2407
2650
SP PP-Eayy-R
1080
1284
1505
1721
1962
2173
2365
2619
R52 repl.
777
1028
1220
1435
1645
1893
1979
2378
RS2 witepl (stratified)
785
995
1267
1483
1577
1786
2099
2127
repl
Random CD
3124
3416
3784
Herding
3815
K-Cooter Greedy
3952
Least Confidence
3084
3432
3838
Entropy
Margin
3057
3522
3797
Forgeting
3835
GraNd
5133
5721
5936
CAL
4153
Craig
Glister
4012
GraphCut
8028
AL (Coof)
48708
48708
48708
48708
(1.1)
48549
AL. (Margin)
48326
48.22
48326
48326
SSP-Easy
SSP-Hard
3908
Easy
4214
SP-Hard
3922
SP-Cary-RS
R52 repl.
3696
RS2 wircpl (stratffie))
2585
3003
3500
3501
repl
2153
27

---

Published as a conference paper at ICLR 2024
The total time required for RS2 and select baseline data pruning methods to reach target accuracy (time-to-ace accuracy) when training with varying selection ratios on ImageNet. Time is reported in seconds. Part 1/2. The best method(s) is bolded.
Table 13:
Targel
Select Ratio (r)
Random
919
289
231
Herding
22222
27794
24243
Least Confidence
15292
19362
Entropy
19535
19285
Margin
19494
14121
15785
Forgetting
19081
18394
15978
5% ace
GraNd
146059
143640
147931
FL GraphCut
67907
67789
220647
66336
224755
303318
RS2 w/ repl
542
347
231
RS2 w/ repl (stratified)
403
350
RS2 repl
530
347
Random
2003
462
579
Herding
29468
24822
Least Confidence
16043
20056
Entropy
20517
19864
Margin
14698
Forgetting
10% ace
GraNd
14743
143755
148047
Fl.
69144
220878
308052
GraphCut
66831
224928
303434
RS2 w/ repl RS2 w/ repl (stratified)
931
635
463
581
RS2 repl
463
Random
1906
1157
Herding
36974
Least Confidence
22684
23065
Entropy
27158
22757
Margin
19029
17984
Forgetting
20% ace
GraNd
146123
148741
Fl. GruphCut
221802
308630
225794
304012
RS2 w/ repll
1355
1502
1273
RS2 w/ repl (stratified)
1145
1160
repl
Random
7219
4282
Herding
Least Confidence
32555
Entrupy
32131
Margin
43750
25159
Forgetting
25959
18293
30% acc
GraNd
151840
158347
FL. GraphCut
227519
313954
307600
307600
RS2 w/ repl
1626
3927
4514
RS2 w/ repl (stratified)
1546
3583
3937
RS2 w/o repl.
1673
3166
28

---

Published as a conference paper at ICLR 2024
Table 14:
The total time required for RS2 and select baseline data pruning methods to reach target accuracy (ame-to-accuracy) when training with varying selection ratios on ImageNet. Time is reported in seconds. Part 2/2. The best method(s) is bolded.
Target
Select Ratio (r)
1%
5%
10%
Random
14814
Herding
Least Confidence
Entropy
Margin
32682
Forgetting
28824
40% acc
GraNd
166680
FL GraphCutt
322518
234399
317553
RS2 repl
2015
6815
11689
RS2 w/ repl (stratified)
1864
6586
11923
RS2 w/o repl
2015
6699
12152
Random
Herding
Least Confidence
Entrupy
Margin
Forgetting
35305
50% acc
GraNd
FL GraphCut
RS2 repl
8605
16550
RS2 repl (stratified) RS2 w/o repl
16552
8605
16434
Random
Herding
Least Contidence
Entropy
Margin
Forgetting
60% acc
GraNd
FL GraphCut
RS2 w/ repl
10337
20021
RS2 w/ repl (stratified)
10282
20024
RS2 w/o repl
10280
19790
Random
Herding
Least Confidence
Entropy
Margin
Forgetting
65% ace
GraNd
FL
GraphCut
RS2 w/ repl
22105
RS2 w/ repl (stratified)
22107
RS2 w/o repl
21873
29

---

Published as a conference paper at ICLR 2024
Table 15: Accuracy achieved by different data pruning methods when training ResNet-18 on the CIFARIO dataset with p percent of the train set labels randomly flipped (noise ratio). Data pruning methods use a selection ratio of 10%. We test on the normal test set. We report raw end-model accuracy/accuracy drop compared to p Ofrelative accuracy drop compared to p- 0 (as percentage of the p = accuracy). Best method (highest accuracy) bolded; Next best underlined. Most robust method (lowest relative accuracy drop) starred.
Noise Ratio
10%
30%
50%
Random
50.7:1
(0.9::2.33775447.
37.2:11.1/41 2/52.6
CD
31.2.11.997,,67..
30.3.10.6288500 5/48
29.7.12.9/29.1888
Herding
15.9-42..447.6/774
1..1
I
1 4/74.7
K-Conter Groody
41.6:t1../333.//44
33.1=0.7/42. 1/56.0
31.1=0../44.1/88.
Least Coulidence
27.444-.77/3.2/52.4
25.2+2..13324155.
63.331572663331/55.5
Entropy
26.9114.2330.7/55.
24991..7733.7/56.
23.3
Margin
29.2:1 012-22.2/44.000
27.412.244..8666
28.5433.344..7661
Forgetting
17.5.111.//1155999
19.0:11.6/30000
GraNd
49.4 5/14.5
CAL
45.4+-22./26.44136
1. 1,944,
35.5==0.4/360 4/36,/////////.33
Craig
50.3::0.799.9116.5
0..5000.000.7/444
37.3++1 5/22.9///8.0
Glister
49.8:22.5/25.90 9/22
40 1.5355 6/47.
37.9 5/57 8/50.0
GraphCut
42.0=0.7/32.04443.
37.7 1/36,3/49.
50.4:1
41.::0833.11 1/443
36.8-10.71377
AL (Conf)
$3.5.13. 1/30.1///////
37.2.1 4/55,5
(LL.)
57.1+004/27.9/222
45 8/39 9
38.2 60..66//6688555 8/55,1
AL (Margin)
57.6++0.5/26.995 1.8
1.238.//8.4441
36,9 16.9=10/477 11..000466550 6/56,3
SSP-Fasy
51.1 1/20099999//
40.7 3/4444
36.7 1.035 3/49.
SSP-Hard
50.4-t00./22399/22.
10.9+1.5/3344444
36.3 99/3 088051551 .22
SP-Eas
33.4:::2.4/23.//33
40.0=:0.4/32.3/44.6
37.7= 1./33.1.///44/47..
SP.lard
47.5:12.4726.6/33.9
1.344..3344444..
34.3:122.0/39 8/53.7
SP RP-Eary-RS
74.2:10..114.2/1666
6344 1//25.0/28..
57.8:10.7/30.6/44
RS2 w/ repl
77.5+:1.0/1..2/1...6
69 01-9--0///99.//2
64.6 5/2555512222 1/28.0
RS2 w/ repl (stratified)
76.1400./113.7/15.33
68. 68.7-0.6211/22
65.0+11440 14/4414//////77.
RS2 w/o repl
787::10.//13:W1..1
69/0::9.9/22.724.88
C.8 ROBUSTNESS OF RS2 TO NOISY LABELS
In Table 13 we show the robustness of RS2 and existing data pruning methods against noisy labels. We include existing methods which sample static subsets, well our modified version of the recent prototype-based data pruning method which utilizes repeated subset selection between each round (SP-Easy-RS) (see Section 5.2 As discussed in Section 5.4 in the main paper, we evaluate the robustness of data pruning methods as follows: We randomly flip some percentage of the labels in CIFAR10 and then run data pruning methods with these labels. We use a subset selection ratio r = 10% for all methods and evaluate on the regular test set. For each method we report end- accuracy/raw accuracy drop compared to p = Ofrelative accuracy drop compared to p = (as a percentage of the p = O accuracy). Table 15 shows that RS2 achieves higher end-model accuracy than existing data pruning methods in the presence of noisy labels. RS2 also the most robust method (lowest relative accuracy drop) when the noise ratio is 10% and 30%. Interestingly, the GraNd baseline actually gets better as the noise ratio increases. While surprising. the overall end-model quality of GraNd is still limited, however, as the GraNd accuracy begins decrease again as the noise increases beyond 50% and all noise ratios result in lower accuracy than training on clean data. We leave detailed study of these observations and robust data pruning methods for future work.
C.9 RS2-BASED PRETRAINING OF LANGUAGE MODELS
Next, in Table T6 we use RS2 to reduce the cost of pretraining large GPT2 language model. We extend RS2 to this setting as follows: we repeatedly sample random subsets of text from the OpenWebTexx (Gokaslan & Cohen 2019) dataset and use this data for next token prediction (the standard GPT2 pretraining task). We train RS2 for r 600k iterations for r = [0.1, 0.3] and compare to training with the full dataset for 600k iterations (recall the connection between RS2 and the number of SGD iterations). We also compare RS2 to random data pruning. i.e., training for r 600k iterations on static fraction of the full dataset selected once before learning begins. We are not aware of existing data pruning methods being evaluated in this setting and present these results as an initial baseline. We report accuracy (higher is better) and perplexity (lower is better) on the
30

---

Published as a conference paper at ICLR 2024
Table 16: Zero-shot results of GPT2 pretrained using RS2, static random subset, and the full dataset. We report accuracy (ACC; higher is better) and perplexity (PPL; lower is better).
Method
Selection Ratio (r)
Training Cost
LAMBADA (ACC T)
LAMBADA (PPL.
WikiText103 (PPI. ()
Random
10%
$520
43.37
45.02
53.36
Random
30%
$1,560
44.63
41.99
46.44
repl
RS2 w/ repl
30%
$1,560
45.29
40.51
42.58
Full Daraset
$5,200
46.61
40.30
40.55
LAMBADA (Paperno al. 2016) benchmark as well as perplexity WikiText103 (Merity et al. 2016). RS2 leads to better model quality but not cost compared to static random sample. Moreover, we see that RS2 leads near matching accuracy and perplexity compared training using the full dataset for r = 30%. This result highlights the practical potential of RS2 to enable faster and cheaper training, hyperparameter tuning, or neural architecture search for large language model pretraining, currently one of the most expensive and time consuming training paradigms in machine learning.
31

---

Published as a conference paper at ICLR 2024
D ADDITIONAL RS2 PSEUDOCODE
In this section, we include additional RS2 pseudocode algorithms to accompany Algorithm|] presented in the main body of the paper and to present additional details useful for the RS2 theoretical analysis.
In Algorithm we describe RS2 without replacement when training with accelerated mini batch SGD (Ghadimi & Lan 2016 Nesterov 1983). Nesterov's 's accelerated gradient introduces three different sets of parameters that are updated at each iteration t. We denote them as w', w and wna Furthermore, the algorithm introduces learning rate parameters ot St, and λς- In later sections, specialize the learning rate parameters for obtaining a convergence rate bound. Finally, g( & m) step i. represents the gradient estimate batch of data that is used for updating the model. & are random vectors whose distributions are supported on E, E R²
Algorithm 3 RS2 w/o Replacement With Accelerated Mini batch SGD
Require: Dataset S {*r,, 1/ ) selection ratio E (0, 1), batch size initial model wo, X
rounds, learning rate parameters {ar} s.t. di 1, az (0, 1), Vt > 2, {3s 0}, {he > 0}. gradient estimate function for batch m and parameters w with noise &: g(w,E:m.
1: T
[NN/6]]
2: t+1
3: whg w
4: for round j = to X do
5: if t%T == then
Shuffle after full dataset has been seen
6:
fleffle(S)
7: S' S[] rN. : rN]
Select the subset across rounds without replacement
8:
for k= r do
9:
batch S'[(k: 1) b: k-
10:
md t (1 a1)way 1- + arw-
} train on batch for Nesterov mini batch SGD
11:
w w Arg(ut md Eri m)
12:
Wa + whd Beg mas Eci t tt ++111
13:
return w md
In Algorithm we also show RS2 without replacement, but using standard mini batch SGD, We also write this algorithm using a different perspective: instead of iterating over rounds, selecting the training subset for each round, and then iterating over batches in the selected subset, RS2 without replacement can be equivalently implemented by iterating directly over batches from the full dataset, as long as these batches are correctly selected and the full dataset is shuffled as necessary. This perspective be more useful for understanding the generalization error of RS2 without replacement as it more closely matches the common algorithms in related works analyzing SGD (Ghadimi & Lan 2016 Nikolakakis et al. 2023).
Algorithm 4 RS2 w/o Replacement With Mini batch SGD; Single For Loop Perspective
Require: Dataset S {x1, J. selection ratio E (0, 1]. batch size b, initial model w X
rounds, learning rate 7/t
1: T < [N/6]]
2: for iterate = 1 to r T X do
3: if t%1 = 0 then
Shuffle after full dataset has been seen
4:
shuffle(S,
5: batch m 3 S([ 11(--))97 b 1%T .
6: W f- w²-1 lt Σ E( =f(w=>;aa
b train on batch for mini batch SGD
return =²
E RS2 CONVERGENCE RATE
Performance of accelerated mini batch SGD has been well studied for convex functions (Lan 2012
Dekel et al., 2012 Cotter et al. 2011). It has been shown that mini batch SGD using batch of size b.
32

---

Published as a conference paper at ICLR 2024
after X rounds with T batches per round returns solution satisfying o
L [
w011 T2X2
allw" - w=1l
Bl((w) - [(ww(ww)) S O
vbTX
Furthermore, Ghadimi & Lan (016) have analyzed the convergence rate of mini batch SGD for nonconvex 8-smooth functions. After TX mini batch steps of size the algorithm guarantees solution w such that
? SO (((w")-((")) o V ((((())) - [ww))) TX
(4)
VITX
We provide convergence analysis for accelerated mini batch SGD using RS2 without replacement as shown in Algorithm following the analysis of Ghadimi & Lan (2016).
Corollary E.1. Suppose the loss I(w) is nonconvex, has B-Lipschitz continuous gradients, and is bounded below. Let g (w. E,) at step represent the gradient estimate used when updating the model as in Algorithm 3 in the Appendix. Assume the gradient estimate satisfies E [[g[(w, Et) VI(w)]? S a², and gig W, {t] Vl(w), where & are random vectors whose distributions are supported on E, E Rdd With the previous assumptions, using selection ratio r E (0, 1] and mini batch of size b,
RS2 produces an iterate w after rounds, with rT batches per round, such that:
E [IV]((W) so ((((u²) )( -((())))))))))))) σ - [(ww))
(
(5)
T
Vb..T..X
Furthermore, assuming that l(w) is convex it holds that
( 22. X2
(8l
w=1 112
a allw0 - w01l
Bl((w) - [(ww)) =0
(6)
We find that the convergence rate of RS2 compared to the full dataset convergence rate GGhadimi & Lan 2016) has a scaling factor in front of the total number of iterates, while the bound remains consistent with respect to all the other parameters; With r= 1 we recover the results from previous the gradient bound after X rounds increases compared to training with the full dataset for X rounds, but this is intuitive each round contains fewer mini batches (rT with r < instead of T). If RS2 with r < is instead allowed to train for more rounds, specifically X
work (Ghadimi & Lan 2016). When
X, then both training RS2 for Xnew rounds and training on the full dataset for rounds result in the same number of mini-batch iterations (TX). In this case, the gradient is bounded by the same value, implying that RS2 and training the full dataset converge with respect to mini-batch iterations at the same rate.
While the above analysis is straightforward extension of the convergence result for mini batch SGD with Nesterov's 's accelerated gradient update, it highlights the stability and guaranteed convergence properties of RS2, property that does not necessarily hold for other data pruning methods.
Proof. Each round we use Nesterov's accelerated method to update the gradient:
wind - (1 - ar ar) + +aw
(7)
w² f- =--1 Aeg(windr m))
(8)
wag + w Sig(winds m);
(9)
where g(w {t) represents the gradient batch of data We assume that the following holds:
Eg(w, {,) ) V((w)
(10)
Ellg(w, { [ = o²,
(11)
where & are random vectors whose distributions are supported on E, E IR:; These are the source of randomness when estimating the full data gradient.
We repeat the procedure for X rounds. When using full data each round we have T batches, resulting in total TX gradient updates. If we perform RS2 w/o replacement. each round will contain r7
33

---

Published as a conference paper at ICLR 2024
updates per round, resulting in total of rTX iterations. Assume relaxation for the learning rate parameters. For this part of the proof assume they are chosen {at} s.t. 01 = 1, E (0, v 2 2. {3, > 0}, {h, > 0}, such that the following holds:
t= 1
F
(12)
(1 aa)
t2 2
B(). - B1)²
/r2'x
C² == 1- - 81
Σ r >0
(13)
A₂C
Pt Σ AcO t= IT....,TX.
(14)
Furthermore, let R represent an index chosen randomly in all the iterate updates from I to rTX, chosen such that Prob(R R = t] Pt.
First we want to show the following holds:
E| (
1
((w9) (1((-) + _0
rTX
X²
1+ (de B.)
TxX
Σ 17
TXX 2t=1 A,
2
(15)
Let define, for ease of writing, the following: 5, = g( - Vl(w(na) Since l(w) is bounded from below and differentiable nonconvex B-smooth function it holds that (see (Nesterov 2003)):
[el)-Vl((mmm and A == Vi(w--1)-
(vv) I(x) (Vi(x),y =>1 8
=0|2 -
Va, ER"
(16)
We start from the assumption that the loss function / 3-smooth:
I(w") S [(w0=l) (VI(w" w - - + 2
1w0 w''
(17)
Then, using the update step eq.
(8) and the definitions of oz, A::
3X?
I(w²)= S ((ww--)) + (A + Vi(w - Ae (V((m)ma)) + + + ||VI((na) + +011
2
333
=1(w²~)) + AA + vi(wind) - d (((((()))) - do (. )) +
[il + 5'1..
2
(18)
Now using the inequality eq. (6) get:
Iww') S
1(w²=1) - da 35c
Vll + >||A""|||V[[[""ma]
-
BX2
1100112
2
2
>e >v((Vl(w' - BAr Vi( (Wnm), 8²).
(19)
Since / is 3-smooth and by the update rule eq. 7 we have:
|| = [|V](==11)- Vllwhaall < B BB whalll = ((1 ax)llwag - w w²1
(20)
Continuing from eq. 18 and inserting eq. (0):
l(w') 1(w0 dx (1 (1-
_6,
|Vl(w + X, - -ac)llugg w²- -w''
2
BX? + 2
118"112-
>e >e(Vi((w'1)) - BA, Vi(w 8*)
(21)
Using the general fact that xy < (y²+ holds, bound the previous inequality:
+ 3(1 - 321=
82?
I(w')= < 1(w de (1 3x) [I(
2 || 1-
w²=1112
118"112
- -\i(V((u'-1 Bbx, (ilaaa))
(22)
34

---

Published as a conference paper at ICLR 2024
Now we take small digression from the main flow of the proof. We want show that the following inequality holds:
(A+ 3r)²
f---l =
-
[VV(()ma) + 1011
aa
(A, - 3,)² + 2(V(((u [|
+ +107713].
(23)
aa
We show that the following way. First, let us combine the update steps eqs. change of variable we have:
to
Performing
Way w' = (4) 0r) + a,w' 1-1 3, (lw [wo- de (((mmaal
= =(1 (1)(1ag - ) (Ae B,) Vl)
(24)
Following from eq. (24 and using Lemma I stated in Ghadimi & Lan (2016) it is implied that:
A Br Vl(w)d)
ogg w² = pr
(25)
Furthermore, we have:
B (Wind)
I og
w²1 =
1r
(26)
rr
From the definition in eq.
11) we have:
Pr
1
(27)
|--
F
Inserting that into eq. (6) we get:
| ag
w01l== 12t
ar
d, Br
Vi(w mnd)
(28)
a
Applying Jensen's 's inequality to eq.
28 have:
A Br (((m))))
(Ar - -Br)2
|| w 11'1 < l
1d
||
(29)
a'
Hence, eq. 23 holds.
Coming back to the main flow of the proof. We combine the previous two inequalities eq. 22 and
eq. 23 Also, we use the fact that 1 (1 a²)²
< I
.x?
I(w') <l(w" 1)- de BXx) Vi(
11
2 - - Bbe (l(win)) 8²)
3 (A+ A 8,)²
(laall + +((Vl( 87) + [|6T119]
(30)
l'aar
Summing up the above inequalities (eq. (30) up to the rTX iterate, we get:
rTX
TT
Tx) < 1(w0)
Σ
(1-
(ww
\v(V(((=-1) - BA, V((w 8*)
1=1
TX
3X?
8 TTX
(Ar - B2
1180112
V((w 11 ++V((( 87) + 118
l'arr
1=1
T=1
xTX
3 rTX
1+ (Ne B2) rTX
TT
= =((w²)
Σ
( 11
Σ X
Σ r"
110$112
Σ b
t=1
(31)
35

---

Published as a conference paper at ICLR 2024
where b, = (A, (
Vi(uma), Due to the fact that under assumptions eqs. (10) and [1] B118"11 S ² and {br} J is martingale difference, when taking expectation on both sides we obtain:
322 +
A(A, 0.)²
EEr=t rr)
a
rxx
300 rxx
rxx 1+ (4-
1 ((w0) V((
+
Σr Td
(32)
2
a
1=1
Using the fact that I(w")= 2 I(w"), RE] (((w)))
2
X, 6 Vi(w and by dividing both ΣiE
A.C
sides by ΣØ AO we obtain:
_002 T
(A,
3,)²
TTX
)
B| V 11
1(w") - ((w") +
12
1+
Σ m
ErTX ACC
2
T
1=1
T=t
(33)
Hence, we have proven the wanted eq. 15 holds.
For the remainder of the proof for the nonconvex case we specialize the previously obtained result. Let us assume the following:
2
at [+1
(34)
A E
Be, 11
at 4
3.
(35)
2
(36)
t(t + 1)
8
D
B. = min
for some D > 0.
(37)
213'
oVrTX
Now, we want to prove:
E Vi( it 12
< 213(((w8) ((w)))
2a
((w0) - [(ww)
+ {D)
(38)
4rTX
VrTX
D
From definition of eq. (34g
eq. 35
let us make claim about C². For that, from eq.
35) we observe
0 < A
.e S ar,0
4. Now we have:
B1)2
rTX Σ r
C² -1=1-1
A₂
(39)
Ta Ae
(1+
ar
a7
2 1 3
3 +
(40)
4
16
1
3,3(1 +
Q1
1
(41)
4
16'
21
2 1 3.B
(42)
16"
Multiplied by d we have X,C*, > 116. 32
Now we make the following claim about 1 From eq. 36
Txx
Σ
TTX
rXX
1
s
2
2
(43)
T(T 1)
1
From the eq.
33 eq.
37
eq.
(2
we have:
21
B.
C*
2
B3,
2
>
0
and
x
(44)
16
2
2
36

---

Published as a conference paper at ICLR 2024
Furthermore, from eq. eq.
(35
B6 eq. (37 and eq. (43) we obtain:
(Ne
B,)²
rxx
Σ mr) ]
a+
2
2
x +
S x
1+
+
a
4
8
8
S (1
at 2
1
8 S
2B3.
(45)
Together with eq. 33 holds that:
rX
Vl ma)l x
1(10") - 1(w0)) + 1300²
Σ
19
Et=1 Br
2(1(w") -1(10)))
+ 2
rTX311
2(1(w0)) - -1(w"))
213
ovrTX
23Do
(46)
rT'
8
VrTX
which implies:
21,3((w0)) - I(w=))
2a
(w00) - -l(1w))
E
(W <
+ BBD
(47)
4r
VrTX
D
Hence, we have shown that eq.
47 holds. Continuing from that, minimizing
(47 with respect to
D, the optimal choice is D (( t(w=)) Inserting that value for D, eq. 447) becomes:
V Vw (1 21,(1(w0)) I(w")) 40 / /B(llw0) - [(w))))
(48)
4rTX
VrTX
Until now we have assumed that IE| g( , Et) v((w)||3= we assume that the gradient is calculated on a batch of size b, the variance of the stochastic gradient reduces to o² /b (see (Wang & Srebro 2 The entire previous results follow with that assumption without loss of generality. Therefore we conclude it holds that:
0² for the ease of the proof. However,
((((ww)- ((w"))
BB((W()) - ((w)))
E [((w)]? So
(49)
rTX
VbrTX
Convex case Now, let us consider the case for convex functions. First, in order to prove eq. want to show that, assuming:
44 we
1
B. < 3' acde S 388,
(50)
14 (1 - (3²)
Pt
(51)
Σ1TX pr Bc - 3Bc)
and
Agl 2
(52)
X1
the following holds:
TT 3,(1 33:)
(2x1)~ 0- w0122
2 + 30 j==1 1
[ - I(w)))
(53)
E F (3,)
Starting from the update rule eq. 7 and using the convexity of I(-) we have:
1(wind) - [[1 (ar)))llwug) adl(w)) at [(w'na) [[w)] (1 av)) -
- ((wky!1) b)]
v a (VI(w wind - w) + (1 - ae)(Vi(w wind - wa
(Vllwind) ar (w w) + (1 az) w(-1))
an (VI(w e0111 w))
(54)
37

---

Published as a conference paper at ICLR 2024
Similar to before, start with the smoothness eq. (16) and use the update step eq. (
to obtain:
B
((wag) ((wmm)) + (Vl(wnm)) w/g wmd)
|lwaag wmdll"
2
3/3
= =((wmd) Bel VI(u || 3r (Vi(w 88) [i([uma)
811..
(55)
Inserting eq. (54) into the previous inequality, we have:
(w N (1 (n))(w())))) + arl(w) + or ()((((((nd))
w w)
[.llV[( B Vl(w 33g
VV(( md) + 1.11
(56)
From eq. (9) we have:
| 1 w/ 24, (V( 6", w0, 1 w)
((l - 80112 = =1lw0 de (V((wnn) + +60) - w0l? = 1/w - w|l?
(57)
From the previous equation, have:
[||ur=1 w|12 - 1| w| w|]²] az + (58)
an Vl( (m) +
w +8
w)
2d,
Combining eqs. 56 and 58 and the fact that [[Vl(u + +81112 VI(w 111 118:112
2(VI(uemd) 5²), we get:
ae (wag)) S (1 ac) (e))((()))) arl(w)
w|1 -wwl
I|we - ww]l]]
2x
3r (1- 33g
aide
[333 + tade
|18$11
2 23,
2
(5 (Be + 333 aςdx)
Vi(w + aa(w-w'1J)
(59)
Due to the fact that 01 = r = and by eq.
52 it holds that:
TX
[ w||
w
a1
1/00
w/l
||10
w|l
(60)
A
A
Using Lemma I from Ghadimi & Lan
2016),
eq.
(60) and subtracting ((w) from eq.
59
we obtain:
(wrTxx
((w)
w|l2
rTX
3.
arde
2
-33,
IvXX
2
21
B,
1=1
rx
333 + arde
TT
110¹112 +
Σ
b/
(61)
21
where U1 = (8', (Be + 33t + ar ax Vi(w ( + +v,(w w w Together with eq. inequality gives:
50 the above
(( (wrTx) - ((w)
1|00
w|1
rTX
3 T (1 Vl()
T+XX
2X1
t=1
TTX
33
XTX
T 118
+
(62)
Since {b}} is martingale difference, we have:
|| 0² and by taking expectation with respect {irTx]-
w
TX
3
TTX Σ
B33
FrTx [[wxi]x] - [(w)] <
r (1 -
33,
E
(63)
2X1
r
t=1
t=1
38

---

Published as a conference paper at ICLR 2024
Now, assume w² and since by definition ((waxx) 2 I(ww), obtain:
TX -
| - 222111 11
rTX
3
(64)
-=1
2
from which, using the definition of w it follows that
(2X1)
w0 1 + _0
E Vi
R 2
21=1
(65)
EE
B P (1 BB:)
Also, using eq.
50 and eq.
in eq.
for rTX 2 we have:
(1w0--wl²
w|12
3
E [w [[w)))] S P
2
which implies that eq.
(53) holds:
f (1 33,)
Ell(wag ((
EEl([wgg (((www))
TX ftr (38a)
1=1
DE Be(1 - 33:)
TX
(211)- "11 - w/1 + 3o 2
Σ
(66)
Σ [1 - 33,)
Now, assuming ar is set as in eq. 34 Pe is set as in eq.
51).
1/4
1
D
Be min
(67)
2
(
and
t3
A = 2
(68)
we want to show that the following incquality holds:
Blllw l(wwww)) ]
48,3
w0
12c
|w00
w0
+D).
+
(69)
x2
VrT'X
D
for some D 0. Note, that eq.
67 and eq.
68
imply eq.
52
and eq. 550
Since, 1
2 π(++ī and by eq.
667 we obtain:
TX
TT
TX
(1
33,)
(70)
2 t=1
2
TX
TX
2
1
1T
2
(71)
2
12
6
(=1
1=1
By I
2(++1) eqs.
65
and 688, we obtain:
2
||w0
112
rTX
E ( 1|
1-30 8
B1 > >
1
3,39
Tr
Fr
t=1 31333
2| w0
w0 1|2
12|| w"1 1
+ 2,30
B1 S
+ 2802 31
3 X
1
96.321 - ==112
B1/202/2
12 w w0112
+ 2D112)
(72)
X3
(TTx)33/4
D3/2
39

---

Published as a conference paper at ICLR 2024
Moreover, by eq. 667 it holds that:
1 - 33, <
and
Σ
2
-
Σラ イ
st.
r
j=1
j=1
It is implied by eqs. 666.
67
70
and
71
that:
TTX Σ t
E Bll(wag) R - [(ww)] ) -
rTX((A)) -11000 =111 + 30
12 12 - w011
1280 FXX
33 Σ
+
r2T2X² 3/3
1=1
12 12 - ==11
+ 1280 89rTX
22T2X2B3
48 = w01
12x
||10 w011
D + =))
(73)
x2
VrTX
This shows that eq.
699 holds.
Minimizing the previous inequality with respect to Đ, the optimal
choice δ 1 ||. Hence, becomes:
E (l( l(w"))))))))))))))))) S 48/1|100 10112
24 24|lw0
+
(74)
22
VrTX
As in Wang & Srebro (2019). the variance of the stochastic gradient reduces o² //6 when estimating with 6 samples. Theretore we conclude it holds that:
( 22
[illuo
w011
allwo w=1l
E(((w) I(w")) =o
(75)
vbrTX
F RS2 GENERALIZATION ERROR
We proceed with the generalization error bound of RS2 for nonconvex Lipschitz and smooth losses. start by introducing the assumptions on the function f : Rdd x Z R+ (see Section 4 for
completeness, and then we proceed with the proof of Theorem 4.1
Assumption. (Smooth and Lipschitz Loss) There exist constants By 2 and Ly 2 0, such
that for all w, u E Id and x E X, is true that | (w, Vuf(u, 2)122 I By|| - u|] and (wf 2) fu, 2)ll2 Lyllw u/l2.
The next result follows form prior work (Nikolakakis et al., 2023) and it suffices to show that RS2 sampling is data independent and belongs the set of general mini batch schedules that appear in (Nikolakakis et al. 2023] Definition 1).
2023) Theorem 8). Let the function if be nonconvex, L-gLipschitz and By-smooth. Then the generalization error of the standard gradient RS2 algorithm with a decreasing step-size T)t S C/t (for < 1/8,), ). is bounded
Theorem F.1 (Generalization error of standard gradient RS2, (Nikolakakis et
IEgen (F,D,RS2) < N
0B 12 -- XXx) min {1+ C3, ro.geerr-T.. x.)x.. (76)
Proof. Let (No ki/) (1,2...., NY be the set of indices for mini batch selection at each gradient step (1,.... (1....,rT)) We select the mini batch through the choice of indices [K],...,kj k/) as follows. For sampling with replacement in line 4 of Algorithm a round j selects subset of indices "di...,Kyy,, These indices are sampled independently from any other round i
40

---

Published as a conference paper at ICLR 2024
XI,...,X), i.e., the same indices can be sampled in consecutive rounds, hence with replacement. Note, that at round j sampled indices in the set are unique. The parameters are then updated using a deterministic batch schedule iterating through the sampled subset of indices resulting in rT' gradient updates. On the contrary, RS2 without replacement can be seen as traversing the full dataset in deterministic round-Robin fashion. That is, the model parameters
updated by sequentially
selecting indices :.. K. After iterating over the full dataset, i.e., after T N/b gradient updates we shuffle the full dataset array and repeat the procedure (e.g.. Algorithm 4p. The algorithm early stops after rT'X gradient updates. Thus the selection rule is non non- adaptive and data independent and it belongs to the set of the general batch schedules (Nikolakakis et al. 2023 Definition 1). As consequence, (Nikolakakis et al. 2023 Lemma and the growth recursion (Nikolakakis et al.) 2023 Lemma 3 (Growth Recursion)) holds verbatim for RS2 with standard gradient training with batch size b. Then, we solve the recursion identically to (Nikolakakis et al. 2023 Proof of Theorem 8)) for rT'X total number of gradient steps. The solution of the recursion gives (the on-average stability and thus) the generalization error bound of RS2, as appears the theorem, and completes the proof. D
41


Reviews:
[{"review_id": "vQ7r3u19xv", "reviewer": "Reviewer_9ict", "summary": "This work empirically investigated a strong baseline called Repeated Sampling of Random Subsets (RSRS, or RS2), in the context of dataset pruning/distillation. The authors found that this sampling scheme, which has been overlooked by the literature, served as a very strong baseline in terms of many metrics, such as end model accuracy and *time-to-accuracy*.\n\nThe authors did intensive experiments that compare RS2 with up to 24 existing dataset pruning/distillation methods and observed the superiority of RS2 under all of the above metrics. The authors called for attention from the community on this strong but overlooked baseline.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The highlight of an overlooked baseline in the context of dataset pruning/distillation.\n+ Intensive experiments over so many baselines. This provides a very good benchmark and starting point for the following works, which I find really appreciable.", "weaknesses": "- The RS2 without replacement is exactly the same as reducing the number of training epochs but with tuned learning rate scheduling. The new term is not helping to make the concept clear but more confusing. This also means that the theoretical analysis in Section 4 did not make actual contributions over previous work.\n\n- In my opinion, a type of dataset pruning methods, which generate static subsets before real training starts, are up to a slightly different point from RS2. While we all know that the more data used for training the better, these methods try to find a coreset that is essential for good generalization. Therefore, it is important that the pruned data are not seen during the training process later (thus static subset). This reduces the storage cost which is not possible with RS2 because RS2 still requires access to the full training set.\n\n- RS2 with replacement has been adopted in a few more works in the context of efficient training like [Ref-1, Ref-2].\n\n------------------\n\nRefs:\n\n[Ref-1] Wang, Yue, et al. \"E2-train: Training state-of-the-art cnns with over 80% energy savings.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[Ref-2] Wu, Yawen, et al. \"Enabling on-device cnn training by self-supervised instance filtering and error map pruning.\" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39.11 (2020): 3445-3457.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T970a3ftGD", "reviewer": "Reviewer_ph2C", "summary": "The paper introduces a novel approach to improve time-to-accuracy of deep learning model training by using a fraction of the full dataset in each training epoch. \n\nThe paper discussed the limitations of two commonly used methods in this domain, (1) Data Pruning: Selecting the most informative examples to train more efficiently. (2) Dataset Distillation: Creating synthetic examples that represent the larger dataset to train quickly.\n\nThe paper proposes Repeated Sampling of Random Subsets (RS2), which simplifies the process by randomly selecting different data subsets for each training epoch, promoting broader learning and efficiency. RS2 has been shown to outperform State-of-the-Art methods, achieving near-full dataset accuracy with significantly reduced training time on various datasets, including large scale image benchmarks like ImageNet. \n\nIt is interesting to note that the paper achieves very close performance to models trained on complete datasets with just 10\\% of the datapoints for large scale benchmarks like ImageNet.", "questions": "1. The subset selection strategy of RS2 without replacement is unclear in section 3. A suggestion would be to replace the textual description in this section with Algorithm 2 in section D of the appendix.\n2. The variables $n$ and $N$ are used interchangeably in section 4.\n3. The term ‘selection ratio’ and ‘pruning ratio’ has been used interchangeably and should be fixed in the paper.\n4. As mentioned in the ‘weaknesses’ of the paper, experiments on real-world class-imbalanced settings ((eg: MedMNIST (Yang et al., 2021), CUBS-2011 (Wah et al., 2011))) would be an effective demonstration of the application of RS2.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a simple but novel approach to achieve significant reductions in time-to-accuracy while training on a fraction of the full dataset per epoch of model training.\n2. The paper also presents detailed theoretical properties that support the faster convergence of the model as compared to existing approaches in the domain.\n3. The paper demonstrates results on four image datasets including large scale image benchmarks like ImageNet wherein it achieves State-of-the-Art (SoTA) performance (accuracy) with just 10 \\% of the data samples in the complete dataset.\n4. The paper also demonstrates SoTA performance on auxiliary tasks like data distillation, noisy label classification and pretraining of large language models.", "weaknesses": "1. Although the experimental results are exemplary (primary contributor to my decision), the method RS2 itself is an incremental update over random sampling. The paper must call out the clear difference with SoTA methods (please refer to questions for more details).\n2. All experiments demonstrated in the paper adopt canonical benchmarks which are well curated, while lacking experiments on datasets (eg: MedMNIST (Yang et al., 2021), CUBS-2011 (Wah et al., 2011)) with large intra-class variance and class-imbalance wherein data pruning might underperform. \n3. The paper does not show any relation between the theoretical properties of RS2 (convergence rate and bounds on generalization error) and the conducted experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "akwbZ5JRYJ", "reviewer": "Reviewer_hzLv", "summary": "This paper compares approaches to reducing the training time by curating a smaller representative dataset like data pruning, coreset selection, and dataset distillation to a simple random sampling-based approach termed Repeated Sampling of Random Subsets (RS2).  Results show that prior adaptive approaches fail to beat RS2 on four image datasets in both final accuracy and time-to-accuracy when accounting for overhead associated with active selection.  Owing to the properties of random\nsampling, RS2 comes with convergence and generalization guarantees.  The authors highlight the importance of evaluating approaches based on time-to-accuracy and the need for more complex approaches to beat a simple baseline like RS2.", "questions": "- What model weights are used for computing the static subsets of approaches like Entropy, Margin, Least Confidence, etc in Table 1 left?\n- How often are importance scores recomputed for adaptive methods in Table 1 right?\n- How does random with fixed subset perform on the tasks studied?\n- How does training on full dataset with the same LR schedule and training window as that used for RS2 perform?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "- The authors point out important considerations missing in prior work on speeding up training with adaptive dataset subset selection.  First, whether there is a need to restrict data to a fixed subset in the first place if similar accuracy can be achieved by training with a compressed learning rate schedule on fewer epochs.  Second, the importance of including overhead associated with data selection when evaluating training compute efficiency of an approach.", "weaknesses": "- As I understand, RS2 without replacement is effectively the same as training on the full dataset with the learning rate schedule compressed into fewer epochs.  RS2 with replacement is a slight variant to that but still highly resembles standard training with shuffling between epochs just with a condensed training window. This is not discussed anywhere but brings into question the whole exposition of proposing RS2 as a sampling method.  An even simpler baseline is training as usual on the full dataset with the condensed schedule.  I would wager such a baseline would yield similar performance as RS2.\n- The paper is light on experimental details for how prior methods are evaluated in particular for case where samples are reselected based on latest model weights.  I am surprised the results in Table 1 right are worse than that for Table 1 left when selecting a new subset with updated model weights can expand the number of samples seen during training.  The poor performance of AL approaches like Entropy and Margin also contradicts the experimental results from Park et al., 2022 where AL outperformance other subset selection methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LJavXQd587", "reviewer": "Reviewer_ns5a", "summary": "This paper revisits the utility of random selection when it comes to speeding up the training. The paper considers two types of random sampling, random sampling with and without replacement. The paper surprisingly shows that these two samplings can easily outperform the popular data subset selection baselines (adaptively or static) when it comes to comparing the time to achieve the same accuracy. Moreover, the authors show that for many training budgets, it outperforms famous baselines, demonstrating the efficacy of uniform random  selection.", "questions": "Can authors also add a comparison to more recent versions of CRAIG such as CREST [1]? \n\n[1] Towards Sustainable Learning: Coresets for Data-efficient Deep Learning (ICML'23)", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper conducts experiments across several baselines, including active learning and dataset distillation. In addition, the paper provides an analysis of the convergence of the RS2 algorithm, which I am not sure is how novel is it, in terms of proof technique, but it's a good contribution to have in any data subset selection paper. Lastly, I think robustness and LLM pretraining results are also interesting making the overall comparisons spanning different modalities and scales.", "weaknesses": "- RS2 w/o replacement is the same as training on a reduced number of epochs. For the cases where RS2 achieves the same accuracy in significantly less amount of time, I think the main issue was not tuning the epoch/learning rate hyperparameter of the full dataset baseline. Therefore making the RS2 w/o replacement results less exciting. \n\n- Can authors provide a plot #unique examples seen throughout training? It could be the case that certain baselines are not exploring the full dataset, due to possibly inadequate hyperparameter search on them. \n\n- I am very confused about Table 1, where we allow the model to update the subset after every round. I request authors provide a clear description for every baseline for both cases, where the distribution is allowed to change over time. The notion of RC and RS has to be made clear for each of the baselines. \n\n- Why is RC's performance extremely worse in certain baselines such as GraNd? In general, why is there a strong dip in the performance of all the baselines, when switched to RC? \n\n- For the baselines that sample set based on submodular function, what does it mean to have a distribution? How are authors defining the distribution over each set of size \"k\"? If that is the case, how are they sampling? If not, what is the heuristic?\n\n- I think it is not correct to compare active learning baselines to subset selection schemes that look at  - (1) all the dataset, but the reduced number of iterations, and (2) assume labels for all the data points, since AL does not assume labels. \n\n- Each of these baseline papers has comparisons against random, on the other hand here the authors break the baselines by mere random selection. What is the reason for this discrepancy?  \n\n- Can authors please point to the hyperparameter tuning for each of the baselines? Submodular functions often work well if tuned properly, therefore it is important to see if enough hyperparameter tuning was done to make sure the function is good. \n\n- For the submodular methods if the corresponding greedy gain was used to sample sets (distribution defined using gains), it should be noted that if the function saturates, then greedy gains do not provide any useful information (yet another reason to provide hyperparameter search grids). \n\n\nI am willing to raise scores upon satisfactory responses to my questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LbMrPdkRmq", "reviewer": "Reviewer_MpXN", "summary": "This paper revisits a rather simple subset selection strategy for efficient deep learning. The authors claim that repeated sampling of random subsets (RS2), that is, only randomly sample subsets at each round, can be a powerful baseline strategy. RS2 is competitive against most of the sampling strategies as well as dataset distillation methods developed previously. Besides, there is no additional computation cost extracting the coreset using RS2, so RS2 reaches the best acceleration under the same sample budget.", "questions": "Please see the weakness part above", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tSelecting the coreset for efficient deep learning is important for machine learning practices. The paper may be valuable to the community trying to address this problem. To the best of my knowledge, this is the first paper to formally discuss the repeated random sampling strategy.\n\n2.\tThe paper is clearly written, the authors do a good job in presenting their intuitions, and the analysis is convincing. \n\n3.\tExtensive experiments are conducted to show the effectiveness of RS2.", "weaknesses": "1.\tThe paper considers only the low data regime (<30% data). RS2 performs well in this regime as it will not reshape the underlying data distribution. Actually, I think whether RS2 can outperform other strategies depends on the subset size and the property of the original dataset itself. In the data-abundance regime,  I believe selecting \"harder\" samples benefits model training. More discussion on this will greatly strengthen the paper. \n\n2.\tIn the theoretical analysis, only RS2 without replacement is considered. I wonder if the result changes for RS2 with replacement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)