REDUCR: Robust Data Downsampling using Class Priority Reweighting
Authors: William Bankes
George Hughes
Ilija Bogunovic
Zi Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Class Robustness
Online Batch Selection
Robust Machine Learning
Training Efficiency
Data Downsampling
Class Imbalance
Primary area: active_learning

Abstract: Modern machine learning models are becoming increasingly expensive to train for real-world image and text classification tasks, where massive web-scale data is collected in a streaming fashion. To reduce the training cost, online batch selection techniques have been developed to choose the most informative datapoints. However, many existing techniques are not robust to class imbalance and distributional shifts, and can suffer from poor worst-class generalization performance. This work introduces REDUCR, a robust and efficient data downsampling method that uses class priority reweighting. REDUCR reduces the training data while preserving worst-class generalization performance. REDUCR assigns priority weights to datapoints in a class-aware manner using an online learning algorithm. We demonstrate the data efficiency and robust performance of REDUCR on vision and text classification tasks. On web-scraped datasets with imbalanced class distributions, REDUCR significantly improves worst-class test accuracy (and average accuracy), surpassing state-of-the-art methods by around 15\%.

REDUCR: Robust Data Downsampling using Class Priority Reweighting
William Bankes
George Hughes
Department of Computer Science University College London wi william. bankes. 21 @lcucl..o. ac. uk
Department of Computer Science University College London
Ilija Begunovic*
Zi Wang" Google DeepMind wangzi@google com
Department of Electrical Engineering University College London i. bogunovicuucl........ooo.o...... ac.uk
Abstract
Modern machine learning models are becoming increasingly expensive to train for real-world image and text classification tasks, where massive web-scale data is collected a streaming fashion. To reduce the training cost, online batch selection techniques have been developed choose the most informative datapoints. How- ever, many existing techniques are not robust to class imbalance and distributional shifts, and can suffer from poor worst-class generalization performance. This work introduces REDUCR, robust and efficient data downsampling method that uses class priority reweighting. REDUCR reduces the training data while preserving worst-class generalization performance. REDUCR assigns priority weights to datapoints in a class-awa aware manner using an online learning algorithm. We demon- strate the data efficiency and robust performance of REDUCR on vision and text classification tasks. On web-scraped datasets with imbalanced class distributions, REDUCR significantly improves worst-class test accuracy (and average accuracy), surpassing state-of-the-ae methods by around 15%.
Introduction
The abundance of data has had profound impact on machine learning (ML), both positive and negative. On the one hand, it has enabled ML models achieve unprecedented performance
wide range of tasks, such as image and text classification [Kuznetsova et al.) [2020] He et al. 2015 Brown et al.) 2020 Tran et al. 2022, Anil al. 2023 On the other hand, training models on such large datasets can demand significant computational resources [Kaddour et al., 2023). making unsustainable in some situations [Bender al. 2021 Patterson et al. 2021]. Additionally, the high speed at which streaming data is collected can make it infcasible to train on all of the data before deployment. To tackle these issues, various methods have emerged selectively choose training data, either through pre-training data pruning [Sorscher et al. [2022] Bachem et al.) 2017 or online batch se- lection techniques [Loshchilov and Hutter] [006]] Mindermann et al., 2022], ultimately reducing data requirements and enabling ML models to handle otherwise unmanageable large and complex datasets.
In real-world settings, variety of factors can affect the selection of datapoints, such noise [Xiao et al. 2015 Cao et al., 2021 Wei et al., 2021 and class-imbalance in the data [Van Horn et al.
2018
Philip and Chan 1998 Radivojac al. 2004 Online selection methods can exacerbate
Co-senior authors. Code available https//ggthlccoomlllllaaaaleelet
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Update model parameters
Initialise weights
Receive batch B,
Selection scores
Select points by
s-brcck
cat
5, yay
cog
truck
yooat X juct!
S ymttg
yrlisc
cat
rrinukk
Sy j-buck
dog
truck
Update model parameters 0t+1
Select points be+1
Receive batch Be+1
Adjust weights
Selection soores
Figure I: REDUCR starts by initializing weights of classes. At each timestep the model receives batch datapoints B.. REDUCR computes the selection scores for each datapoint based on usefulness to the model and the class weights, and selects new datapoints b, C B, that achieve the highest selection scores. After the model takes gradient steps the selected datapoints, REDUCR adjusts the weights to reflect increased priorities underperforming classes.
these problems by further reducing the number datapoints from underrepresented classes, which degrade the performance of the model those classes [Buda al. 2018 Cui al.) 2019). Moreover, distributional shift [Koh et al., 2021] between training and test time can lead to increased generalization error if classes with poor generalization error overrepresented test time.
In this work, we introduce REDUCR, which a new online batch selection method that is robust to noise, imbalance, and distributional shifts. REDUCR employs multiplicative weights update to reweight and prioritize classes that are performing poorly during online batch selection. Figure iillutraats the
Worst Class Test Ace (9))
intuition behind how the method works. REDUCR effectively reduce the training data while pre- serving the worst-class generalization performance of the model. For example, the ClothingIM dataset [Xiao et al.) 2015), Figure[]shove that, com- pared to the best performing online batch selection methods, REDUCR achieves around a 15% boost performance for the worst-class test accuracy.
20 Mindem Uniform al.(222))
Loshchllov al.1215))
REDUCR
Figure 2: REDUCR significantly improves worst- class test accuracy on Clothing outperforming Uniform and other recent works.
Main contributions. (1) We formalise the maximin problem of robust data downsampling ($3) (2) We propose the REDUCR algorithm, which is equipped with a new robust selection rule that evaluates how much datapoints will affect the generalization evaluate our algorithm on a series of text and image classification tasks and show that achieves strong worst-class test accuracy while frequently surpassing state-of-the-as methods in terms of average test (ccuracy($5).
of specific class ($4.2). (3) We
Related work. Mindermann et al. 2022 have developed an online batch selection method called RHO-LOss, which uses reference model trained holdout dataset guide the selection of points during training. Certain extensions of this work have focused on using reference model different settings such as reinforcement learning (Sujit al. 2022]. However, to our knowledge, none have focused on improving the worst-class generalisation performance. Other batch selection methods Loshchilov and Hutter 2016 Jiang al. 2019 Kawaguchi and Lu [2020] use the training loss of points under the model or approximate gradient norm |Katharopoulos and Fleuret 2017 to select challenging points. We observe that these methods (e.g., see Loshchilo and Hutter [2066] in Figure exhibit greater consistency in terms of worst-class generalization error in imbalanced datasets. Nev- ertheless, Loshchilov and Hutter (2016) do not surpass the average generalization error achieved by point selection with a reference model, namely, RHO-LosS. Recently, several works have also used reference models or holdout dataset to train robust models. Oren al. (2099 Liu et [2021] Clark
al. 2019 use reference model identify lifficult-to-lcanl groups (or points, or biases) during

---

training, Hann et al. [0118] use two models which act as reference model for the other to remove noisy points from the training data. Cao al.) [02T]. Renn et al. [2018] use holdout dataset to reweight points or their regularization during training to achieve the best loss on the validation holdout dataset.
Sagawa et al. [2020) reweight groups known at training time and focus fighting spurious correlations and improving worst-group generalisation error. In contrast, in our setting, class labels are available and we measure the performance in terms of worst-class generalisation error. Moreover, whilst these works aim to train robust models they do not consider efficient data downsampling strategies. The approach of Sagawa et al. [2020) to group robustness considers small number of groups (up to 4 in their empirical study). Similarly. in our work, we consider classification settings with a controlled number of classes (< 1000) as the problem of robustness becomes less applicable in settings where the number of classes are high.
Xie et al. 2023) use both weights update rules and reference model find mixtures of corpora in LLM pretraining resulting in improved performance and training speed. Besides the problem setup, our method differs in three ways: we focus upon online batch selection; ii) we use multiple reference models; iii) and we use class-holdout loss term (see Equation (8) to reweight batches. well-explored problem with various approaches, including active
Efficient data downsampling learning methods when label information is unknown (MacKay 1992 Houlsby et al. 2011 Kirsch
al. 2019 2023 Ash et al. 2020]; data pruning and coreset techniques for pre- pre-training data downsampling [Sorscher et al. 2022 Bachem et al. 2017 Borsos et al.
2020 Coleman et al. 2020); data distillation approaches Cazenavette et al.] [022] guyen al.
2021 and non-parametric
inducing point methods (aaly-Fajou and Opper 2021
2 Background
We consider C-way classification task and denote model as p(y xz f), where x denotes an input and y [C] the corresponding class label; the model is parameterized by 9. For any training dataset D = {2 y:) } fi=1 with N datapoints, we use a point estimate of 0 to approximate the posterior model as p(y x, D) p(y z, 0). This estimate i can be obtained by running stochastic gradient descent (SGD) to optimize the cross-entropy loss over a training dataset D.
The goal of data downsampling is to select a dataset Dr D of size T (< N) for training such that the generalisation error of the resulting model is minimised. We write this objective in terms of separate holdout dataset Dro = (KTho, (ho.:)
Now Nar as follows:
Dr = argmax log Pgyphool D), DCD,ID|-T
where the inputs and their labels are Xιa = [zn,holirr the likelihood of the holdout dataset is used as proxy for the generalisation error. The problem computationally prohibitive due to its combinatorial nature. Moreover, for massive (or streaming) training dataset DD it is not computationally possible to load 'D all at once and it is common to loop through the data by iteratively loading subsets.
Noo and yho bel. Noo. respectively. Here,
Online batch selection is practical streaming setup to approximate the data downsampling problem, where each timestep f, the model observes a training data subset B, C D. and the goal is to iteratively select a small batch b, C B₁ for the model to take gradient steps. A standard solution to this problem to design selection score function that take into account the labels of the data. The selection score function can then be used to score the utility of the small batch b, See Algorithm in Appendix A for an example method.
Reducible Holdout Loss (RHO-Loss) [Mindermann et al. 2022 is an online batch selection method that uses the performance on a holdout dataset as the selection scores for small batches. More precisely, for each timestep f, RHO-Loss selects
by argmaxx logo(yno Xho, D, b)),
bC B,
where D. = U by is the cumulative training data the model has encountered until iteration L.
3

---

3 Problem Formulation
In this work, we introduce the robust data downsampling problem, where the goal is to select a training dataset Dr of size T such that worst-class performance is optimized. Let the holdout dataset with class c E [C] be D = {( y) E Dro = c} = { ho Who,))
(e) No We can write the
objective of robust data downsampling as
DT
argmax min logp(ying (e) (.I.T
ho Xho D),
where x (c) = [arhho No and yho - W hi correspond the collections inputs and labels in ho,
No
the class-specific holdout dataset D
Compared to Equation I the objective in Equation (3) is even more challenging because of the maximin optimisation that involves discrete classes. fact, solving Equation (3) is known to
be NP-hard, even when the objectives (each p ho ho -), E [C]) are submodular set functions. Chen et al. [017) demonstrate the application of zero-sum game no-regret dynamics, where learner employs a (1 I/e) (reee)-neergge near-optimal greedy strategy and an adversary seeks to find a distribution over loss functions that maximizes the learner's loss. In this scenario, single set is identified, which, although larger than size 7, achieves constant-factor approximation.
(e) [xc)
Robust online batch selection approximates the robust data downsampling problem by taking into account the practical limitations of data operation. Namely, we assume a streaming setting where the model observes training data subset B, D each timestep t. The goal is select small batch by C B, to compute gradients for model training with SGD, such that the model obtains top performance for the worst-class (Equation (3) The robust setting motivates the development of novel batch selection methods that consider how each datapoint affects the generalization error on the worst-case class of inputs, rather than just the overall generalization error. Next, we introduce a new selection rule that achieves this and propose practical algorithm for its implementation.
4 REDUCR for Robust Online Batch Selection
We propose REDUCR, a robust and efficient data downsampling method using class priority reweighting to solve the robust online batch selection problem in Section 3 The batch selec- tion strategy of REDUCR relates the effect of training on batch of candidate points b, to the generalization error of a specific class in the holdout dataset.
4.1 Online Learning
To solve Equation 3 in an online manner, we propose to use class priority reweighting, a variant of the multiplicative weights update method [Freund and Schapire 1997 Gesa-Bianchi and Lugosi 2006, [Sessa et al., 2019]. At the beginning of training we initialise weight vector Wo over a C' dimensional simplex. A {w [we][] E RCIE We 1}. Each element of wo is initialised to be W = 1/C. For each iteration t, small batch 6 c B, is chosen by maximising the weighted sum of the C different class class-specific scoring functions (i.e., by best-responding the current weeihhs wt).
be = argmax
Σ
Wi.e (logp(y (c) 1x De D.Ub)
(4)
B,
c=1
where D. = - by. W. [ A. and
exp exp(-nlog ply D2)
Wr.c = Wt-1 2g 1, exp log p (2) 1x D.))
(5)
In the previous alternating procedure, class-weights are updated multiplicatively according to how well they perform given the selected batch, they increase for poorly performing classes and decrease otherwise. In Equation (5). 1) is a learning rate that adjusts how concentrated the probability mass in the resulting distribution. Figure shows an intuitive illustration of how reweighting works in practice where classes that perform badly have low data likelihoods and are thus upweighted by

---

Equation (5) In Appendix A.7.3 we explore an alternative solution to solve Equation (3; we solve an approximate robust optimisation problem directly at every timestep f and empirically demonstrate the multiplicative weights method outperforms it. We next introduce how to compute the likelihoods (e) (e) for class-specific holdout sets, i.e., p(y ho hoo Dj U b) in Equation (4
4.2 Computing selection scores
Given the current dataset D; at timestep t and additional datapoints b C BN, we would like compute the likelihood of the holdout dataset that belongs to class c. For simplicity, we consider the case where the small batch be selected only includes single datapoint, i..,, b = {(z, y)}. We express the objective using a Bayesian perspective.
x De U (1x, v)}) = log piula,Do De Inly Ix .n.D.)
logp(y p(y ho
ply P.)
p(y|,, 11 D. Poly 1o lx ..) D.)
log
(7)
pla D2)
- lologgl log x., D.) + logp(v x Dr, Dio) log ho Xho D.).
(c)
(c)
Equation (6) follows from the application of the Bayes rule and the conditional independence of
and xhe with yio and y, respectively. The posterior terms in Equation (6) can be approximated with
point estimates of model parameters (see $ Computing Equation (6) involves two models: (1) the
target model with parameters O,, which is trained on the cumulative training dataset D,
bri
(2) a class- irreuiireeeeeble loss model (following the terminology from Mindermann et al. [2022] with
parameters 8(0), which is trained on D, and class-specific holdout data D(C)_ The target model is what we are interested in for the classification task. We use [2 0J - log p(y x 0) to denote
the cross-entropy loss for any model parameters 0, and we re-write Equation (6) follows,
log ply ho xho D. U ((,,)()))))))) = Ciul2.
(e) (e)
Ciyl (001 Cly No x ho 0r].
(8)
model loss cluss: irreduciblee loss
class-holdour loss
We name the three terms in Equation 88 the model loss, class-irreducible losy and class-holdou loss, respectively. We define the term excexs loss as the difference of the model loss and class-irreducible loss. The excess loss is the improvement in loss for point (ar, y) by observing more data from class c (i.e., D(.)) Intuitively, if two data points are from different classes, REDUCR will take into account the weight of the porst-performing class, which reflected by the class-holdout loss. This ensures that REDUCR is focusing on improving the performance of the model on the classes that are most difficult learn. In different scenario, if two datapoints are from the same class, their class-holdout losses will be the same, and the point with a larger excess loss will be preferred. This means that REDUCR prefers datapoints whose losses have more potential to be improved.
Computing the approximate in Equation 8 is far more tractable than naively re-training a new model (i.e., p(y x ( D; U ((x, )) for each possible candidate point (Ir, y). The model loss and the class-holdout loss only require evaluating the cross-entropy losses some datapoints on the
target model. More generaly, if batch 6 can include more than one point, we simply change the and y to list of inputs and labels instead. Next, we further improve the efficiency of REDUCR by approximating the class caassiirreuuebbee loss model.
4.3 Class-Irreducible Loss Models
For each selected batch be under the current selection rule in Equation (8). need to update C class-irreducible loss models to compute the daass-rreducible losses. We propose to approximate these models using amortised class-irreduible loss models, which are trained for each class the beginning of REDUCR and do not need to be updated during online batch selection.
We interpret the class irreducible loss term an expert model at predicting the label of points from specific class c due to the extra data from the holdout dataset this term has available. To create an approximation of this expert model, train the amortised dass--rreduuibll loss models using an adjusted loss function in which points with a label from the class c are up- sp-weighted by a parameter y (0, +o0) (set in Section 5
de = arg min
Σ (x.0)ED;
(1+7T(e= v)) Clylxx, ().
5

---

Algorithm 1 REDUCR for robust online batch selection
1: Input: data pool D, holdout data Dro = Ucec Dko learning rate 1j (0, oo), small batch size
k, total timesteps T/k:
2: Initialize class weights WT = =
3: Use Dro to train C' amortised class irreducible loss models as per Equation 9 to obtain &e
4: for E [T/k] do
5: Receive batch B, C
6: be argmax E(a.wjeb EeEc Wre max(00 0I] - Clyla, Qcl) bc
Select points with
top k selection scores
7:
Compute the objective value for every class E C::
(c) (c) Or = (a.a)e,,, max(0, Clylar, 0.] Llylæ, @el) - fly ho x 0c]
8:
Update class weights for every class e E C:: W1+1. = Wh,e Ejec Wi, na5)
exp(-noe)
9: 0c+11 + SGD(O,,, bt)
10: end for
Here we define Il[:] as the indicator function. Equation optimizes over the parameters of the amortised class-irreuucible loss model for class c, and obtain &e to approximate 0.00 in Equation (8)
i.e., Lly )( ~ Clyl Φc)- The up-weighting of points can be considered form of importance weighting (Siioodiraa [000]. where by up-weighting points with labels in a specific class we calculate a Monte Carlo approximation of the loss under a distribution in which points from class e are more prevalent. Algorithm details the full amortised
loss model training We provide further motivation of our approximation Appendix A.3
procedure in Appendix A.2
4.4 REDUCR practical algorithm
We use the selection objective in Equation (8) along with the amortised class-irreducbbl loss model approximation (Section 4.3) and the online algorithm (Section 4.1) to reweight the worst performing class during training and select points that improve its performance. See Algorithm for a full description of the REDUCR method.
At each iteration, the top i points are selected (Line 6) according to the weighted sum of Equation (8) for each class E C, thus efficiently approximating the combinatorial problem from Equation 4 As the class-holdout loss does not depend on the selected points b, and we sum over the classes, we can
remove this term from the weighted sum of the selection scores and only apply it when updating the weights w, (in Line and 8). We calculate the average class-holdout loss to remove any dependence of the term upon the size of the classes in the holdout dataset. We find that clipping the excess loss improves the stability of the algorithm in practice. We test this heuristic empirically in Section 5.2 and provide an intuitive explanation for why this is the case in Appendix A.7.2 When comparing REDUCR to other online batch selection methods, we observe distinct batch selection patterns. When the dataset is class-imbalanced the underrepresented classes tend to perform worse because of the lack of training data from those classes. RHO-LOSS may struggle to select points from the underrepresented classes as they have less effect on the loss of the holdout dataset. Selection rules that select points with high training loss [Loshchilov and Hutter, 2016 Kawaguchi and Lu 2020 Jiang et al.) 2019] might select points from the underrepresented classes but have no reference model to determine which of these points are learnable given more data and thus noisy or task-irrelevan points may be selected. In contrast, REDUCR addresses both of these issues by identifying underrepresented classes and using the dass-irreduuible loss model to help to determine which points from these classes should be selected.
Even when the dataset is not imbalanced, certain classes might be difficult to learn; for example, due to noise sources in the data collection processes. Via Equation (5), REDUCR is able to re-weight the selection scores such that points that are harder to learn from worse-performing classes are selected over points that are easier to learn from classes that are already performing well. This is in contrast to RHO-LoSS which will always select points that are easier to learn. We empirically demonstrate this on class balanced datasets in Section

---

Word Cluss Text Accuracy (%
Wore:-can Clac-ccss Text ACC (%1
50
62-
15-
20
Unatum
REDUCH
RHO Loss Unifrm
23-
440 LaSS
REDUCR
RHO Loss
Train Loss
Unitorm
10000
15000
Training
Training
Training Steps
ClothingIM
(b) CINICIO
(c) CIFAR100
Figure 3: REDUCR improves the worst-class test accuracy and data efficiency when compared with the RHO-Loss, TRAIN Loss and UNIFORM baselines on the lap Clothing dataset, b the CINIC10 dataset, a the CIFAR100 dataset.
5
Experiments
In this section, present empirical results to showcase the performance of REDUCR on large-scale vision and text classification tasks.
Datasets, We train and test REDUCR on image and text datasets. We use CIFAR1O Krizhevsky al. 2012], CINICIO (Darlow al. 2018), Clothing IM [Xiao al., 2015), the Multi-Genre Natural Language Interface (MNLI), and the Quora Question Pairs (QQP) datasets from the GLUE NLP benchmark [Wang et 2019 Each dataset is split into labelled training, validation and test dataset (for details see Appendix A.5). the validation dataset is used to train the class- irredcbleee loss models and evaluate the additional points from the training dataset along with the validation dataset to train the irreducible loss model(s) (as per [Mindermann et al. 2022 ). We simulate the streaming setting by randomly sampling batch B, from dataset D at each timestep.
loss during training. The Clothing dataset uses 100k
Models. For the experiments image datasets (CIFARIO. CINIC10 and Clothing 1M) all models use a ResNet-18 model architecture [He et al. 2016). For the Clothing M dataset we use ResNet- 18 model pretrained the imagenet dataset [Deng et al. 2009]. The networks are optimised with AdamW W [Loshchilov and Hutter 2019] and the default Pytorch hyperparameters are used for all methods except CINICIO for which the weight decay is set a value of 0.1. For the NLP dataset we use the bert-base-ue basseed [Devlin et al. 2019] model from HuggingFace [Wolf et al. 2020 and set the optimizer learning rate le
Baselines. We benchmark our method against the state-of-the-arr RHO-LOss Mindermann et al. 2022) Loshchhlv and Hutter (2016), an online batch selection method that the training loss to select points. We refer to the latter baseline as TRAIN Loss. We also compare against UNIFORM where points chosen at random from the large batch each training step All experiments are run multiple times and the mean and standard deviation across runs calculated. Unless stated otherwise 10% of batch B, is selected the small batch b, and we set 7/ = le 4. 7 is used when training each of the amortised class-irreducible loss models on the vision datasets and > = 4 for the NLP datasets. We study the impact ? and on REDUCR further in Appendix A. For full details of the experimental setup see Appendix A.5
Metrics. Finally, it is important to note that analyse the worst-class test accuracy metric which can be interpreted as a lower bound on a model's performance under all class distribution shifts. This is because the worst possible distribution shift between the training and test set is one where the entire test set consists of only points from the worst performing class.
5.1 Key results
The worst-class and average test accuracy for the datasets and model are shown in Table and Table 2 respectively. Across all datasets, REDUCR outperforms the baselines in terms of the worst-class accuracy and matches or even outperforms the average test accuracy of RHO-Loss within one standard deviation. This is surprising because the primary goal of REDUCR is not to optimize the overall average (over classes) performance. REDUCR performs particularly strongly
We use training step and timestep intrccangecallyyyy......
Code available https//gghhbbboooowwwwlllabbblet
7

---

Table 1: REDUCR outperforms RHO-LOSS (the hest overall baseline) in terms of the worst-class test accuracy on Clothing IM, CINIC10 and CTFAR by at least 5-26%. Across all basclines, REDUCR gains about 15% more accuracy on the noisy imbalanced Clothing dataset shown Figure 2 "CIFARI00 results from training step 10k where REDUCR converges, after 10k further training steps TRAIN LOss achieves a similar performance.
Worst-Class Test Accuracy (%) =1 std
Dataset
UNIFORM
TRAIN LOss
RHO-LOSS
REDUCR
CIFARIO (10 runs)
75.01 + 1.37
76.1 2.31
78.80 2.09
83.29 + 0.84
CINICIO (10 runs)
64.70 + 2.45
64.83 +: 4.75
69.39 3.56
75.30 1 0.85
CIFARI00" (5 runs)
3.66
17.59 5.17
16.0
26.00 + 2.65
Clothing IM (5 runs)
39.23
40.37 3.58
53,91 = 2.42
MNLI (5 runs)
74.70 + 1.26
74.56 + 1.44
76.74
79.45 = 0.39
QQP (5 runs)
73.21 + 2.04
79.96 = 2.34
78.21 = 1.95
86.61 = 0.49
Table 2: Together with Table these results demonstrate that REDUCR improves the worst-class test accuracy while maintaining strong average test accuracy despite REDUCR not explicitly optimizing the average test accuracy. REDUCR outperforms the baseline methods on the CIFAR100 and Clothing IM datasets.
Average Test Accuracy (%) +1 std
Dataset
UNIFORM
TRAIN LOSS
RHO-LOSS
REDUCR
CIFARIO (10 runs)
85.09 + 0.52
88.86 + 0.22
90.00 + 0.33
90.02 + 0.44
CINIC1O (10 runs)
79.51 + 0.30
79.25 0.33
82.09 0.30
81.68 + 0.47
CIFARI00 (5 runs)
57.94 0.69
59.77 + 0.71
60.95 + 0.64
62.21 + 0.62
Clothing (5 runs)
0.85
69.63 0.30
71.07 0.46
72.69 = 0.42
MNLI (5 runs)
79.19 + 0.53
76.85 - 0.14
80.89 + 0.31
80.28 = 0.33
QQP runs)
85.05 0.43
86.30 0.41
86.88 0.31
86.99 0.49
on the Clothing dataset, Table 1 shows REDUCR improves the worst-class test accuracy by around 15% when compared to TRAIN LOss, the next gest-performing baseline, and by around 26% when compared to RHO-LOss, the overall best-performing baseline across datasets. Figurel 3aoshows shows that REDUCR also achieves this performance a more data efficient manner than the comparable baselines, achieving a mean worst-class test accuracy of 40% within the first 10k training steps. We also observe improved efficiency on the CINICIO dataset, as shown in Figure 3b and the MNLI and QQP datasets detailed in Figure 7
The Clothing IM dataset also sees distribution shift between the training and test dataset. In the test dataset, the worst performing class is much more prevalent than in the training dataset and as such improvements to performance impact the average test accuracy significantly. Figure impact of this distribution shift as the improved performance of the model on the worst-class results an improved average test accuracy to the state-of-the-art RHO-LOSS baseline.
the
5.2 Ablation Studies
To further motivate the selection rule in Equation ( we conduct a series of ablation studies to show that all the terms are necessary for robust online batch selection. Figure 4a shows the performance of REDUCR on the CINICIO dataset when the model loss, amortised class-irreducible loss and class-holdout loss terms of the algorithm were individually excluded from the selection rule. All three terms in Equation
4a
g are required to achieve a strong worst-class test accuracy.
Removing the Model Loss results in the worst performance in the set of ablation studies. This is because the Model Loss provides REDUCR with information about which points are currently not classified correctly by the model. By removing this term REDUCR only selects points which do well under the Class Irreducible Loss model and does not prioritise points the model has not yet learnt. Selecting points not yet learnt by the model is important quality in online batch selection approaches and the main premise of the Train Loss baseline algorithm. Likewise by removing the Class Irreducible Loss Model term we remove the ability of the model to infer if point can be learnt or not. In Mindermann et al. 2022), the authors note that these pretrained models enable the algorithm to pick points that are learnable and do not have label noise.
8

---

80
0.7
0.6
Woret Class test Acc)%)
70
0.6
class
class
class 4
cluss 5
60
Cless Weights
0.5
Class Weights
Term Removed
Model Loss
0.3
Class Iired Loss
0.2
20
Class Holdout
0.2
10
REDUCR
0.1
REQUCR clip!
0.0
0.0
20000 Training Steps
40000
0
20000
40000
20000
40000
Training Steps
Training Steps
(a)
(b)
(c)
The worst-class test accuracy decreases when the model loss, class irreducible loss, and class-holdout loss terms removed from REDUCR CINICIO. Comparing REDUCR with clipping for excess losses (Algorithm [ and REDUCR (no clip) which removes elipping. we observe REDUCR achieves more stable performance. We show the class weights w at each training step for REDUCR and C REDDUC with the class-holdon loss term ablated. The ablation model fäils to consistently prioritise the underperforming classes across multiple runs.
Figure 4:
The removal of the class-holdout loss term affects the ability of REDUCR to prioritise the weights the model correctly. In Figure we compare the class weights of REDUCR and an ablation model with- out the class-holdout loss term. The standard model clearly prioritises classes 3, and during training across all 5 runs, whilst the ablation model does not consistently weight the same classes across multiple ablation study on the
74
Average Accuracy
70
68
REDUCR RHO-Loss
Train Loss
64
Uniform
runs. We also conducted clipping the excess loss to motivate its inclusion in the algorithm, this is also shown in Figure 4a note that this stabilises the model performance to- wards the end of training and investigate further in Appendix A.7.2
50000
100000
150000
Training Steps
Figure 5: REDUCR improves the average test ac- curacy the Clothing M dataset.
5.3 Scaling up the number of classes
REDUCR can handle problems involving large number of classes without needing train separate class- iass-irrrduuible loss model for each class. One idea to group the classes into superclasses, where Gi G. E {Ge) Gi n 9j 0 for + j and GG < |C], and solve the robust data downsampling problem over these superclasses. We test proposed variant of REDUCR on CIFAR 100 dataset using the provided groupings with 20 superclasses in total (Krizhessky et al.) 2012]. fig. 3c shows that REDUCR outperforms the baselines in terms of the worst-class test accuracy, even though the robust objectives in half' the number of training steps as shown Table
the superclasses. It achieves this performance
5.4 Imbalanced Datasets
We investigate the performance of models trained using REDUCR imbalanced datasets. We artificially imbalance the CIFAR10 training and validation datasets such that a datapoint of the imbalanced class is sampled with probability p (0, L/C" (referred to as the percent imbalance) and datapoints from the remaining classes are sampled with probability (1 Pp)((CCCC 1) during model training. We conduct experiments with 0.01, 0,025 and 0.1 (which is equivalent to the balanced dataset) percent imbalance on classes 3 and 5. The results are shown in Figure
We find the performance of models trained using REDUCR deteriorates less than those trained with RHO-LOSS or UNIFORM baselines as the percent imbalance of particular class decreases (see Figure 6). For example, when class 3 is imbalanced, in the most imbalanced case (1.0%) the median performance REDUCR outperforms that of RHO-LoSS run by 14%. This demonstrates the effectiveness of REDUCR in prioritising the selection of data points from underrepresented classes.

---

Worst-class Thit: Accurary (S)
100
100
10.0%
2.5%
1.0%
10.0%
2.5% 1.0%
Worst-class Test.
60-
40
40-
20
(a) Under-sampling on class 3
(b) Under-sampling on class
Figure 6: REDUCR significantly reduces the deterioration the worst-class accuracy CTFAR1O for class and [b) class when compared the UNIFORM RHO-Loss baselines as the percent imhalance is decreased from 10.0% (balanced) to 1.0%. Each experiment was repeated 10 times, the median value was plotted and the error bars denote the best and worst run across 10 runs.
Conclusions, Broader Impact and Limitations
In summary, identified the problem of class-robust data downsampling and proposed new method, REDUCR, to solve this problem using class priority reweighting. Our experimental results indicate that REDUCR significantly enhances data efficiency during training, achieving superior test accuracy for the porst-performing class and frequently surpassing state-of-ther methods in terms of average test accuracy. REDUCR excels in settings where the available data are class-imbalane by prioritising the selection of points from underrepresented classes.
Limitations. The computational efficiency of REDUCR scales linearly with the number of classes. We propose one solution to this in Section 5.3 where we show that using groups of classes can still result in improved worst-class performance. Another solution is
smaller model architectures for the class-irreducible loss model. [Mindermann et al.) [0022] provide extensive evidence that small reference models can improve computational efficiency whilst still providing a useful signal for data selection, we leave investigation of these methods as future research direction.
Broader Impact. Improving data efficiency is important and practical problem as machine learning models are being trained and deployed for real-world applications. Moreover critical ensure the robustness of models for reliable and trustworthy machine learning. Our work proposes a new method with the goal of improving the robustness of models whilst significantly reducing the data required to achieve state of the performance.
Acknowledgments
This work supported by the EPSRC New Investigator Award FP/X03917X//; the Engineering and Physical Sciences Research Council EP/S02 Google Research Scholar award and the Google Cloud Platform Credit Award. We thank Zoubin Ghahramani, Jasper Snoek, Fei Sha, Théo Galy- Fajou, Dustin Tran, Sharat Chikkerur, Xuezhi Wang and Mike Dusenberry for helpful discussions on early versions of this work.
References
Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. PaLM 2 technical report. arXiv preprint 2305v:2305.1 10403, 2023.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. International Conference on Learning Representations, 2020.
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning, arXiv preprint arXiv:1703.06477 2017.
Emily M Bender, Timnit Gebru, Angelina McMillan-Majon and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, 2021.
10

---

Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming, Advances Neural Information Processing Systems, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in Neural Information Processing Systems, 2020.
Mateusz Buda, Atsuto Maki, and Macicj A Mazurowski. A systematic study of the class imbalance problem in convolutional neural networks. Neural networks, 2018.
Kaidi Cao, Yining Chen, Junwei Lu, Nikos Arechiga, Adrien Gaidon, and Tengyu Ma. Heteroskedas- tic and imbalanced deep learning with adaptive regularization. International Conference of Learning Representations, 2021.
George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexei A Efros, and Jun-Yan Zhu. Dataset distillation by matching training trajectories. International Conference of Computer Vision, 2022.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Robert Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non-convex objectives. Advances in Neural Information Processing Systems, 2017.
Christopher Clark, Mark Yatskar, and Luke Zettlemoyer. Don't take the easy way out: Ensemble based methods for avoiding known dataset biases. arXiv preprint arXiv:1909.03683 2019.
Cody Coleman, Christopher Ych, Stephen Mussmann, Baharan Mirzasolciman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. International Conference on Learning Representations, 2020.
Yin Cui, Menglin Jia, Tsung-Ys Yi Lin, Yang Song, and Serge Belongie. effective number of samples. International Conference on Computer Vision, 2019.
loss based on
Luke N Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey. Cinic- 10 is not imagenet or cifar-10. arXiv preprint arXivv1810.03500. 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. International Conference on Computer Vision, 2009.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep
bidirectional transformers for language understanding. Conference of the North American Chapter of the Association for Computational Linguistics, 2019.
Yoav Freund and Robert E Schapire. A -heeoiin generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 1997.
Théo Galy-Fajou and Manfred Opper. Adaptive inducing points selection for gaussian processes. arXiv preprint arXiv:2107.1006 2021.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in Neural Information Processing Systems, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leved performance on imagenet classification. International Conference on Computer Vision, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. International Conference on Computer Vision, 2016.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning, arXiv preprint arXiv: 2011.

---

Angela H Jiang, Daniel L-K Wong, Giulio Zhou, David G Andersen, Jeffrey Dean, Gregory R Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary C Lipton, al. Accelerating deep learning by focusing on the biggest losers. arXiv preprint arXiv: 1910.00762, 2019.
Jean Kaddour, Joshua Harris, Maximilian Mozes, Herbie Bradley, Roberta Raileanu, and Robert McHardy. Challenges and applications of large language models. arXiv preprini MwXXv:2307..0166 2023.
Angelos Katharopoulos and François Fleuret. Biased importance sampling for deep neural network training. arXiv preprint 1tt.:17000000443. 2017.
Kenji Kawaguchi and Haihao Lu. Ordered sgd: new stochastic optimization framework for empirical risk minimization. International Conference on Artificial Intelligence and Statistics, 2020.
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in Neural Information Processing Systems, 2019.
Andreas Kirsch, Sebastian Farquhar, Parmida Atighehchian, Andrew Jesson, Frederic Branchaud- Charron, and Yarin Gal. Stochastic batch acquisition for deep active learning. Transactions on Machine Learning Research, 2023.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. International Conference on Machine Learning. 2021.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in Neural Information Processing Systems, 2012.
Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings. Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, et al. The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale. International Journal of Computer Vision, 2020.
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. International Conference on Machine Learning, 2021.
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattem recognition, pages 1
2022.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. International Conference Learning Representations, Workshop Track, 2016.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Conference on Learning Representations, 2019.
David JC MacKay. Information-based objective functions for active data selection. Neural computa-
tion, 1992.
Sébastien Marcel and Yann Rodriguez. Torchvision the -isiin package of torch. Proceedings of the 18th ACM international conference on Multimedia, 2010.
Sören Mindermann, Jan M Braumer, 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, 2022.
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 2021.
12

---

Yonatan Oren, Shiori Sagawa, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust language modeling. arXiv preprint arXiv:1909.0206) 2019.
David Patterson, Joseph Gonzalez, Quoe Le, Chen Liang. Muii-Miiuul Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. arXiv preprint arXiv:2104. 10350, 2021.
K Philip and SJS Chan. Toward scalable learning with non-uniform class and cost distributions: A study in credit card fraud detection. Proceeding of the Fourth International Conference Knowledge Discovery and Data Mining, 1998.
Predrag Radivojac, Nitesh V Chawla, A Keith Dunker, and Zoran Obradovic. Classification and knowledge discovery in protein databases. Journal of Biomedical Informatics, 2004.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. International Conference on Machine Learning, 2015 8.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust
neural networks for group shifts: On the importance of regularization for worst-case generalization. Internation Conference on Learning Representations, 2020.
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. No-regret learning in unknown games with correlated payoffs. Neurul Information Processing Systems, 2019.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 2000.
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, 2022.
Shivakanth Sujit, Somjit Nath, Pedro HM Braga, and Samira Ebrahimi Kahou. Prioritizing samples in reinforcement learning with reducible loss. arXiv preprint arXiv:2208. 10483, 2022.
Dustin Tran, Jeremiah Liu, Michael W Dusenberry, Du Phan, Mark Collier, Jie Ren, Kehang Han, Zi Wang, Zelda Mariet, Huiyi Hu, et al. Plex: Towards reliability using pretrained large model extensions, arXiv preprint 2007 2022.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. International Conference on Computer Vision, 2018
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. International Conference on Learning Representations, 2019.
Tong Wei, Jiang-Xin Shi, Wei- Wei Tu, and Yu-Feng Li, Robust long-tailed learning under label noise. arXiv preprint arXiv:2108.1 /1569, 2021.
Adina Williams, Nikita Nangia, and Samuel Bowman.
A broad-coverage challenge corpus for sentence understanding through inference. Conference of the North American Chapter of the Association for Computational Linguistics, 2018
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Transformers: State-of-the--n natural language processing. Proceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations, 2020.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. International Conference on Computer Vision, 2015.
Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy Liang, Quoc V Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. arXiv preprint a305v 2045, 2023.
13

---

A Appendix
A.1 Online Batch Selection Pseudo-Code
For the sake convenience, we provide the pseudocode the online batch selection protocol described in Section 2
Algorithm 2 Online batch selection
1: Input: data pool D, number of training steps T', stochastic gradient descent algorithm SGD, loss function L
2: for = 1 to 7 do
3: Sample batch B, randomly from D
4: by SelectBatch B₁, 8t)
5:
L= Σ (Z..))EB, Cly [2 0c]
6:
0c+1 SGD(I,,
7:
end for
A.2 Class Irreducible Loss Model Training Pseudo-Code
Here detail the pseudo-code for training the class irreducible loss model described in Section 4.3
Algorithm Class Reference Model Training
Input: holdout dataset Dro number of training steps stochastic gradient descent algorithm SGD, a loss function L. specific class
2: for 1 to T do
3:
BiO Uniform(D, (Dio)
4: L = Σ (a.,))e Pho (1 yllle = vl) Øc]
5: Φ1+1 = SGD(L,
6: end for
7: Return Class-irreuuible loss model parameters Ør
A.3 The Amortised Class Irreducible Loss Model Approximation
The amortised class irreducible loss model is an important component in REDUCR as shown by our ablation study Figure 4a For each class e [C], we approximate the second term of Equation (6).
log p(ylæ, Dr, D(o) via the model trained using Algorithm 3 This approximation has two steps: firstly we remove dependence of the class irreducible model loss on the training dataset at time l. A similar approximation is heavily explored by Mindermann et al. [2022] in Section 3 and Section of their paper, in Appendix D their work they show that this approximation is important for the stable training of RHO-LOSs. The approximation also aligns RHO-Loss and REDUCR with other methods in the literature such as Xie et al. 2023 Oren et al. 2019 which similarly use a reference
model that does not vary during training.
Secondly we up-weight data points in the loss function when their label y [C] matches that of the specific class c. Unlike RHO-LOsS we cannot approximate the class irreducible loss as log p(y/2z D,, (()) log p(y|z, D(C) as this is a trivial model only trained on points with labels from single class and thus does not provide a suitable signal to guide point selection. We interpret the original class irreducible loss log p(y|2, jr, D,, D(e)), ), as expert model for class
this model
trains on extra points only sampled from that class, Díe). In our approximation we train on the holdout dataset which does not have excess examples of points from class c. We justify our up-weighting of points form of importance weighting [Shimodairal 2000). where by up-weighting points with labels in a specific class we are calculating a Monte Carlo approximation of the loss under distribution in which points from class are more prevalent.
14

---

90
88
Worst-Class Test Acc (%)
85
86
Acc
84
80
Average
80
70
78
Unifomm
RHO-Loss
65
Unifem
RHO-Loss REDUCR
76
60
25000
50000
75000
100000
125000
25000
50000
75000
100000
125000
Training Steps
Training Steps
(a) QQP average test accuracy
(b) QQP worst-class test accuracy
85
Worst-Clas Test Acc (%)
Average Test Acc (%6
80
80
75
75
70
70
65
60
Uniform
RHO-LosS
55
Uniform
RHO-Loss
Train Loss
REDUCR
Train Loss
REDUCR
55
50000
100000
150000
50000
100000
150000
Training Steps
Training Steps
(c) MNLI average test accuracy
(d) MNLI worst-class accuracy
Figure 7: REDUCR improves the worst-elass test accuracy the MNLI and QQP text datasets whilst maintaining strong average test accuracy performance when compared with the TRAIN Loss, RHO-LOss and UNIFORM baselines. both datasets REDUCR matches the next best performing baseline's 's mean result across runs approximately 100k training steps earlier.
A.4 The Effect of the Class-Holdout Loss on the Selection Points
The class-holdout loss term only affects the selection of points at each iteration & through the selection of the weights W,. As does not depend upon the candidate point (ær, y) E B, and weights sum to one we can remove it from line 6 of Algorithm and only include it in line 7 when update the class weights. Similarly as the model loss does not depend upon the class e we can write the selection score
Σ EEC
Wee Logp(yy
(c) (c) D.U((z,v)) = Clyl 10 0,] X
(C,c(Clylz,
Σ
Wr,o(Cly (c)
X 0.)).
cEC
GEC
(10)
A.5 Experiment Details
We provide the full code base anonymised for review purposes part of the supplementary material.
CIFARIO used half the training dataset (25k points) as holdout validation dataset for training the amortised class-irreducible loss models and calculating the class-holdout loss during the robust online batch selection. used the remaining 25k points as a training dataset and the provided test dataset (10k) for testing.
CINIC10 used the provided validation dataset for both the class holdout loss and amortised class irreducible loss models.
CIFAR100 used the provided validation dataset for both the class holdout loss and amortised class irreducible loss models.
Clothing The dataset consists of million images labelled automatically using the keywords in its surrounding text. The dataset consists of 72k 'clean' images whose labels have been hand checked, 50k, 13k and 9k are respectively sorted into clean training, validation, and test sub-dataset. To train
15

---

the amortised class irreducible loss models we use 100k points randomly sampled from the union of the validation, clean and noisy training datasets. We calculate the class-holdout loss term and validation performance during training using the clean validation dataset. Figure 8 shows how the class distribution changes between train and test times.
MNLI. The dataset [Williams et al., 2018 consists of 412k labeled sentence pairs; similarly to Sagawa
Clothing Dataset Class Distribution Shift
Percent of Dataset (%)
10-
Train
ct al. [020) we split these sentence pairs into a train
(206k), validation (164k), and labelled test (41k)
dataset.
QQP. The dataset consists of 431k labeled sentence pairs; we remove points from class to further im- balance the dataset resulting in 22% of the dataset labelled class 1. We split the remaining points into a train (148k), validation (67k), and labelled test (40k) dataset. We do not adjust the balance of the test dataset.
4-
2
10 12 13
Class
Figure 8: Clothing IM train-test class distribution
shift. The number of points in classes 4 and 7 change dramatically between the train and test sets.
ResNet-118 used for the Clothing M experiments the pretrained model available via the Torchvision [Marcel and Rodriguez 2010) model library. For the CIFARIO and CINIC10 experiments we use the adapted ResNet- 18 architecture detailed in Mindermann al. 2022
Appendix B.
Train Loss baseline taken from Loshchilov and Hutter (016) where points from the large batch B, are sampled with probability
X
exp(log(s)/ B.
(11)
Here p; is the point with the 2th highest training loss in the large batch. We set the selection pressure parameter 8. 100 and do not vary this during training as per the Experiments in Section 6. of Loshchilov and Hutter (016)].
Compute Resources and Data Sources. All models were trained GCP NVIDIA Tesla T4 GPUs. The Image datasets were sourced from pytorch via the torchvision datasets package http://///ttttbbeeatttttteeeeeee html the NLP datasets were sourced from huggingface, https: http://www...ccccaeaaeeeeeeeeeee wttpe//attteetttaaaaaaa/////////
Data Augmentation was applied to the training dataset during online batch selection and validation dataset during the training of the amortised class-irreducible loss model. We apply a random crop and random flip to the images.
A.6 Results with worst-class checkpointing
In Table 3 and Table we show the worst-class and average test accuracy respectively, when the UNIFORM, TRAIN LOSS and RHO-LOSS baselines use worst-class validation accuracy to checkpoint the model during training. REDUCR still outperforms matches the best baseline performance across all datasets. In the cases where REDUCR matches the performance of the best performing baseline, it does so in more data efficient manner. Figure 7b and Figure 7d show the mean and standard deviation worst-class test accuracy across multiple runs on the QQP and MNLI datascts. REDUCR matches the best mean performance of the best performing baseline almost 100k training steps earlier on both datasets.
A.7
Additional Experimental Results
In Appendix A.7.I we show the per class weights for the Clothing MM dataset, whilst in Ap- pendix A.7.2 we analyse the effect of the clipping term and provide some intuition behind its inclusion the algorithm.
A.7.1 Clothing1M Training Weights
The Clothing M dataset is imbalanced with respect to class 4. Figure 9 shows that REDUCR is able to consistently identify and weight the underrepresented class across model runs.
16

---

Worst-Class Test Accuracy (%) =1 std
Dataset
UNIFORM
TRAIN LOss
RHO-LOsS
REDUCR
CIFARIO (10 runs)
75.01 + 1.37
79.32 + 1.35
81.23 = 1.18
83.29 + 0.84
CINICIO (10 runs)
70.86
1.23
68.89 + 86
73.44 1.16
75.30 + 0.85
Clothing M (5 runs)
39.23
5.41
49.02 + 2.32
32.19 = 9.83
53.91 + 2.42
MNLI (5 runs)
76.88 1.21
75.75 + 0.56
78.04 = 1.73
79.45 + 0.39
QQP (5 runs)
84.50 = 0.56
85.49 + 1.32
82.60 = 1.12
86.61 = 0.49
Table 3:
Worst-class test accuracy, when RHO-LOss TRAIN Loss baselines are checkpointed using their worst-class validation error during training.
Average Test Accuracy (%) =1 std
Dataset
UNIFORM
TRAIN LOSS
RHO-LOSS
REDUCR
CIFARIO (10 runs)
85.09 + 0.52
87.74 0.50
89.43 + 0.57
90.02 + 0.44
CINICIO (10 runs)
79.57 0.75
78.21 + 0.57
81.28 0.54
81.68 + 0.47
Clothing IM (5 runs)
69.60 0.85
69.46 + 0.43
70.63 + 0.87
72.69 + 0.42
MNLI (5 runs)
78.85 + 0.38
78.50 + 0.33
80.50 0.45
80.28 = 0.33
QQP (5 runs)
85.23 + 0.36
86.24 = 0.26
86.75 + 0.37
86.99 = 0.49
Table 4: Average test accuracy, when the RHO-Loss and TRAIN Loss baselines checkpointed using their worst-class validation error during training.
A.7.2 Clipped Excess Loss Ablation Experiments
To further understand the effects of clipping in the algorithm we analyse the selection score of the se- lected points with and without clipping. As detailed in Appendix AA.4 the the selection of points via the weights w, at each time step, such record only the excess loss (the dif- ference between the model loss and class irreducible loss). Figure 10 shows the quantiles of the weighted sum of the excess losses of points selected at each training step for the non-clipped and clipped model respectively. When the excess loss is clipped, Fig- shows the selection scores smoothly decrease throughout training the model loss improves. Without clipping the excess loss decreases smoothly at the beginning of training and then shows unstable behaviour across runs later training.
1.0
class 4
0.8
class
Class Weights
loss only affects
0.6
0.4
0.0
50000
100000
250000
Training Steps
Figure 9: Clothing IM class weights
In practice we select multiple points per batch by selecting the points with the top selection scores. When multiple points have the same score, points are selected at random. We note that the clipping does not reduce the excess loss of the selected points to zero where points would be selected randomly to make up the batch.
Intuitively we posit that the clipping reduces the effect of clashing amortised class irreducible loss models in the weighted sum across the |C| selection rules. The amortised class irreducible loss models are trained such that they are an expert in a specific class c. In some cases model being an expert in specific class c' may result in it being poor predictor of classes C' \ c'. Even if this expert has a small weight Wr,e' large losses may still propagate into the selection points. Clipping the excess loss prevents point from being down-weighted in the weighted sum of class specific selection scores by a specific class too much.
A.7.3 Alternative Solutions to Robust Data Downsampling
In Section 4.1 we introduce an online solution to the robust data downsampling problem based upon the multiplicative weights method. In this section we empirically evaluate a variation of where we solve the maximin optimisation problem directly. At cach time step select small
REDUCR
17

---

3.0
quantile 97.5
quantile 97.5
2.5
quantile
2.5
quantile
Selection Scores
quantile
quantile
quantile
2.0
quantile
1.5
quantile 2.5
Selection
1.5
quantile
1.0
1.0
0.5
0.0
0.0
10000
20000
30000
40000
10000
20000
30000
40000
Training Steps
Training Steps
REDUCR Excess Loss
REDUCR Excess Loss No Clipping
Figure 10: The quantiles of the excess loss of points selected at each training step with (a) and without clipping (b) of the excess loss term
Average Test Accuracy (%)
90
80
Worst-Clas Class Test Acc
70
80
60
mwww/ M
50
40
50
Payoff CINIC10 REDUCR
CIFARIO Payoff
30
Payoff CINICIO REDUCR
Payoff
CIFAR1O REDUCR
CI REDUCR
40
20
10000
20000
30000
40000
10000
20000
30000
40000
Training Steps
Training Steps
(a) Average Test Accuracy
(b) Worst Class Test Accuracy
Figure We compare REDUCR with Algorithm in which the maximin optimisation problem approximated by solving the payoff matrix directly at each step this is labelled Payoff. REDUCR consistently outperforms this approach both in terms of (a) average test accuracy and (b) worst class test accuracy.
batch b, C Bt
by = ((,,))} = argmax min Clyla, 0.] L(yls, 0(01 Cly (c) (e) Oz), (x.w)EB,
(12)
for clarity once again write the selection rule in terms of single point. As [B << [D] and both (C) and B, are discrete sets it is feasible to solve the optimisation problem directly. To do this we first minimize the selection score for each datapoint (Ir, y) with respect class and then select the is datapoints with the greatest minimum score. The full algorithm is shown in Algorithm [ We compare this approach against REDUCR the CIFAR 10 and CINIC10 datasets. The results be seen in Figure [1 where REDUCR outperforms the direct optimisation approach in terms of both average test accuracy and worst class test accuracy.
Algorithm Robust Data Downsampling Approximated by Directly Solving the Payoff Matrix
1: Input: data pool D, holdout data Dno = Ucec D(e) ho total timesteps T/k, small batch size k
2: for E [T/k] do
3: Sample batch B, randomly from D
4: by argmax E(owee min Clyla, 0,] Llyl,,, 0(00 - (ly(1) x (x0 0c] cE|C]
Select points
with top k min scores
5: 0c11 SGD(O,, b,)
6: end for
18

---

A.8 Experiments on ConvNext Architecture
We repeated the Clothing 1M experiments using the facebook/ tonyeet-tiny 224 ConvNext model Liu et al. [2022] from HuggingFace, the results are shown in Figure [2 Here we note REDUCR maintains strong performance terms of the average test accuracy. The mean worst-class test accuracy outperforms the other baselines, however is not statistically significant.
Worst Class Test Accuracy (%)
50
Average Test Accuracy
77.5
40
75.0
72.5
70.0
20
67.5
REDUCR
RHO-Loss
REDUCR RHD-Loss
Train Loss
Train Loss
Unifarm
65.0
Uniform
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Training Steps
Training Steps
(a) Worst- Class Accuracy seeds)
(b) Average Test Accuracy (3 seeds)
Figure 12: a) REDUCR outperforms the relevant baselines in of the worst-class accuracy using the fucebook/convnettiiyyy 224 ConvNext Model [Liu et al. 2022]. we ran each experiment
seeds with
no hyperparameter tuning. bb REDUCR continues to outperform all the baseline algorithms in terms of the average test accuracy on the Clothing M dataset when training the ConvNext model. Whilst the worst-class test accuracy is noisy, the improvement REDUCR makes across multiple poorly performing classes results a large performance difference between it and the next best performing baseline.
A.9 Amortised Class Irreducible Loss Models
In Figure 13 we compare the average expert class (c E C) test accuracy and non-expert class (d' C
cc test accuracy across different values of for the amortised class-irreducible loss model train on CIFAR1O. For the model to be an expert in one class it loses performance in the non non-relevant classes. To avoid the problems described in Appendix A.7.2 we selected y for the image datasets as the performance of the non-expert class did not suffer too much.
100
Expert Class Test Accuracy (%)
Non-expert Class Test Accuracy (%)
90
Test Accuracy (%6
80
50
0.25
Figure 13: Class-irreducible loss model test accuracies on the expert class and non-expert classes. Class- irreducible loss models are trained using gradient weights {0.25, 0.5, 1.0, 0.0,9990 9.0, 19.0, 49.0, 99.0).
A.10 Hyperparameter Tuning
In this section, we test the sensitivity of REDUCR with respect to the hyperparameters introduced. In particular, we investigate the sensitivity of the learning rate 1,. used for target model training: the gradient weight 7, used for class-irreuucille loss model training; the fraction of datapoints selected for target model training [b, B,), for constant selected batch size [b,]; and the frequency with
19

---

Worst Cass Test Accuracy 196)
Worst Accuracy (%)
100
80
82
80
78
20
76
n
7=
0.0001
0.001
0.01
0.1
10
2000
4000
6000
8000
Training Steps
(a) CIFARIO 10 Final Worst-Clas Class Test Accuracy
(b) CIFARIO 10 Worst-Class Test Accuracy Curves
95.0
100
Average Test Accuracy (%)
92.5-
Average Accuracy
80
90.0-
87.5
85.0
82.5
20
A 0.0001
17
80.0
0.0001
0.001
0.01
0.1
1
10
2000
4000
6000
8000
7
Training Steps
(c) CIFARIO Final Average Test Accuracy
(d) CIFARIO Average Test Accuracy Curves
Figure 14: The average worst-class accuracy are not sensitive to the value on CIFARIO dataset. When using smaller values of y both the average and worst class test accuracy attain higher performance an earlier training step.
which the class holdout loss term is updated during training. All experiments in this section use the CIFAR10 dataset. We use ResNet-18 18 target models, trained using 7) 10 with fraction of datapoints selected //. B,| = 0.10, and ResNet- 18 class irreducible loss models trained using
y unless otherwise stated.
We find that REDUCR not sensitive to the learning rate r or the frequency of the class holdout loss term updates. We find that the performance of REDUCR is sensitive to the gradient weight at high values. Finally, we find that REDUCR not sensitive to the fraction data points selected for target model training (referred to as the percent train) for intermediate values of percent train, though performance is poor for very low fractions and very high fractions recovers uniform selection as 6, B, when //.l/ B,I 1.0 and B, is sampled uniformly from the dataset.
In summary, REDUCR is largely insensitive to the values of the newly introduced hyperparameters when trained on the CIFAR10 dataset. Sensitivity analyses on additional datasets are needed to increase the robustness of these findings. However, a gradient weight of q = and percent train of 0. 1010 perform well without additional hyperparameter tuning for several datasets, as shown in Table and Table 2 which tentatively supports the robustness of these findings.
A.10.1 Learning Rate ?
First, we perform sensitivity analysis on the learning rate 1) for values 7) (10-1,10-3,,
10-100311 10-0.10-2, 10-10 1000 10 The experimental results, shown in Figure 14, demonstrates that smaller values of 7) result in a faster improvement of the average and worst class test accuracy during training, although the final model performance similar for all values of 1) investigated. In practice, appropriately small values of 1 should be used in order to reduce computational cost. Note that what constitutes an appropriately small value depends on scale of losses in particular domain. Initial target model training runs can be done identify value of v for which class weights do not prematurely concentrate on one class 77.
A.10.2 Gradient Weight
To investigate the sensitivity of the gradient weight on the performance of REDUCR. We train
sets of class-irreuucible loss models for each 7 E {0.25, 0.5, 1.0, 4.0, 9.0, 19.0, 49.0, 99.0) and train model for each set of fass-irreducible loss models. The results, shown in Figure 15 show that
20

---

WlassCClsss Class Test Acturacy (%)
Worst Class Test Accuracy (95
100
90
60
40
Y-
Y-
Y 1.0
Worst
y 4.0
y 99.0
0.25
0.5
1.0
4.0
9.0
19.0
49.0
99.0
200D
4000
6000
8000
Training Steps
(a)
CIFARIO Final Worst- Class Test Accuracy
(b) CIFARIO Worst Class Test Accuracy Curves
95
100
Average Test Accuracy (%)
Average Test Test Accuracy
85
60
40
0.25
y=
0.5
19.0
20
1.0
y 49.0
y- 4.0
Y 99.0
0.25
0.5
1.0
4.0
9.0
19.0
49.0
99.0
0
2000
4000
6000
8000
Training Steps
(c) CIFARIO Final Average Test Accuracy
(d) CIFAR 10 Average Test Accuracy Curves
Figure 15: Average and worst-class test accuracy are sensitive to the value of the CIFAR10 dataset, though this likely reflects longer convergence times for class-irreducible loss model training when using larger values y.
values of the gradient weight above 9.0 result in faster improvement of the average and worst class test accuracy early in training, although these models converges to a lower average and worst class test accuracy the end of training. Higher gradient weights also increase the variance of the class- irreducible training loss, models trained with higher weights thus required a greater number of gradient suitable class-ireeuucible loss model. We found class irreducible loss models trained with gradient weights E {19.0, 49.0, 99.0) are selected via checkpointing before the model has converged and suspect this contributing factor in the poor test accuracy observed.
descent steps converge
This finding highlights the trade-off between fast target model training, which requires a large gradient weight; fast class irreducible loss model training, which requires smaller gradient weight; and strong final performance the model. Final average and worst class test accuracy is similar for all models trained with gradient weights 7 E {0.25, 0.5, 1.0, 4.0,9.0) 9.0).
A.10.3 Fraction of Selected Datapoints
We perform a sensitivity analysis on the fraction datapoints selected for target model training /bel/ [B)), referred to the percent train hyperparameter. We constant small selected batch size [he and vary the large batch size B, in order to vary the fraction of datapoints selected for target model training. In this setting, smaller percent train allows REDUCR to select from greater number of candidate datapoints at each training step, which results in the selection of datapoints with larger weighted reducible loss. Since datapoints with larger weighted reducible loss those from which a model can learn the most [Mindermann et al. 2022). we expect smaller percent train to result in faster improvement in target model performance.
We train target models using REDUCR for each percent train and large batch size pair (lb))/B,), BBl) in (0.05, 640), 10. 320), (0.15, 216), (0.20, 160), (0.25, 128)} and present the results in Fig- ure 16, find that percent train 0.05 attains lower final worst-class and average test accuracy, despite having most candidate datapoints to select from. This is surprising and is in contradiction with the intuition provided above. Furthermore, percent trains {0.1, 0.15,.1..... 0.2, 0.25] attain similar average test accuracy at the end of training, though larger percent trains attain slightly higher worst-class test accuracy at the end of training.
These results demonstrate that the performance of REDUCR is largely insensitive to the percent train hyperparameter for a constant selected batch size. practice, a selected batch size [by should first be chosen such that loss gradient estimates have low variance, and then large batch size [Be] should
21

---

100
Worsk dasss Test Accuracy
WorsttClBs Test Accuracy
80
80
60
40
train 0.10
percent train 0.15
60-
20
percent train 0.20
percent
0.15
0.05
5000
10000
20000
Percent Train
Time Step
(a) CIFARIO Final Worst-Class Test Accuracy
(b) CIFAR1O 10 Worst-Class Test Accuracy Curves
Average Test Accuracy (%)
Average Test Accuracy (%)
68
80
60
percent train 0.05
percent
train 0.15
82
20
percent train 0.20
percent train 0.25
0.25
0.2
0.15
0.1
0.05
0
5000
10000
15000
20000
Percent Train
Time Step
(c) CIFARIO Final Average Test Accuracy
(d) CIFARIO Average Test Accuracy Curves
Figure 16: REDUCR is broadly insensitive to changes of the percent train hyperparameter, [ba]/\Br] the CIFARIO dataset. The tinal worst class and average test accuracy is statistically similar percent train hyperparameter.
variety of values small value of percent train 0.05, the final worst class and average test accuracy suffers and REDUCR requires more gradient descent steps to match the performance of models trained with larger pereent train values. The plots show the mean and standard deviation across 10 runs.
be chosen such that the percent train is an intermediate value for example 0.10. These results also suggest that selecting datapoints with the very largest weighted reducible loss for model training may not be most appropriate for improving model performance. Instead of top-k selection a more nuanced approach that accounts for the joint distribution over all points in the selected batch could be used.
A.10.4 Frequency of Class Hold-out Loss Updating
The class holdout loss term is updated the beginning of each training epoch using the full holdout dataset. As each epoch consists of multiple gradient descent steps the actual performance of the target model the holdout dataset will vary before the class holdout loss term recalculated. In this section we investigate an alternative method in which the class holdout loss term updated at every gradient descent step.
is computationally expensive to update the class holdout loss term using the full holdout dataset at every gradient descent step. Therefore, propose alternative fast updating method, which only uses batch of holdout points to estimate term at each timestep. The class holdout loss computed in this manner is noisy. Therefore, we use exponentially-weighee holdout losses from previous timesteps to produce a smoother signal. Specifically, a batch of size 320 is sampled uniformly random from the holdout dataset at each training step. Losses are then computed for each datapoint in the sampled batch using the current target model. Finally, for each class E [C', losses of datapoints of class in the sampled batch are averaged and used update debiased exponentially-weighhe
moving average of the class
moving average with decay parameter a E [0, 1].
moving averages with decay parameters a E 0.9, 0.99 for fast updating of the class holdout loss term. The results shown in Figure 17 demonstrate REDUCR is not improved in statistically significant manner by the more complex exponentially-weighre moving average approach, both terms of the final average and worst class test ac-curacies the number of training timesteps required to reach these accuracies.
We perform experiments using exponentially-weighee
22

---

90
100
1est Accuracyy
85
Accurccy
80
80-
60
40
Updating
65
20
Fast Updating, 0.99
Updaling.
60
None Frequency Class Hold-out Loss Updating
0
2000
4000
6000
8000
Time Step
(a) CIFARIO Final Worst-Class Test Accu-
(b) CIFARIO Worst-Class Test Accuracy
racy
Curves
100
Average Teat Acturary
88
80-
86
60-
84
Fast Updating Fast Updating,
Fast Updating, 0.9
0.99 Frequency Class Hold-out Loss Updating
0.9
None
2000
4000
6000
8000
Time Stop
(c) CIFARIO Final Average Test Accuracy
(d) CIFARIO Average Test Accuracy Curves
Figure Test accuracies are not sensitive frequency with which class hold-out are updated. Plots show minimums, medians and maximum across 10 seeds.
A.11 Highly Imbalanced Datasets
We also conduct experiments with 0.25% and 0.5% percent imbalances classes 3 and 5. However, (class) irreducible loss models and target models only receive 6.25 and 12.5 datapoints of the imbalanced class during one training epoch (in expectation) with percent imbalances of 0.25% and 0.5% respectively. As a result, too few datapoints of the imbalanced class are seen during model training to achieve good performance on the imbalanced class.
23

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper introduces new methods REDUCR and claims that REDUCR improves robust data selection and sample efficiency. We provide experiments multiple domains that support this conclusion.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
24

---

Justification: As per the guidelines we discuss the limitations of our work in the Conclusion, Broader Impact and Limitations section of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: Whilst we motivate our approach from first principals we then make several approximations to develop practical and implementable algorithm. These approximations mean that do not have any theoretical results in the paper and support our conclusions empirically.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
25

---

The paper details the full experimental setup in the main body of the paper and Appendix A.5. we also include the full code used in our experiments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the datasets used in the paper are publically available and cited where relevant. The full code for our experiments is also provided in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/ mublic/guides
conddeuubmissioPooliooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
26

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We provide experimental setting details in Section 5 and Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All graphs and results the paper are repeated over multiple runs and standard deviations are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resource details are provided in Appendix A.3.
27

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the http:/ublicc/hhiccciieeeeeeee
NeurlPS Code of Ethics attpp://neurr
Answer: [Yes]
Justification: Our research does not involve human subjects. In regards to data related concerns, we use dataset that popular in academic machine learning journals and fully cite the data source, we also provide url's to the datasets as per the neurips guidelines. Our research specifically focuses upon robust methods that try to address issues with bias and discrimination by improving the performance of algorithms on these specific groups Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[Yes]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
28

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets are appropriately cited and URLs and data sources are provided in the Appendix A.3.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsswiteesseeeeeeeeee thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release dataset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
29

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "esJFgBzb8F", "reviewer": "Reviewer_L9Bs", "summary": "**Problem**: The paper addresses the challenge of efficient online batch selection while training for classification tasks. It identifies a key issue with current batch selection algorithms: they often perform poorly on underrepresented classes in the training data. The paper proposes solutions to this problem while ensuring efficient data sampling. The goal is to optimize both the worst class performance and the average class performance on classification benchmarks by selecting a subset of each batch that enhances the performance of the worst performing class.\n\n**Contributions**: The paper proposes an online batch selection algorithm that assigns priority weights to training data points in a batch based on i) class weights in training data and ii) usefulness to the model. This is done by selecting points which have the highest worst class generalization error (hence selecting underrepresented classes) and selecting those points which are learnable given more data, thus avoiding noisy and task-irrelevant points. All of these objectives are ensured by assigning selection scores to training points in a batch. These selection scores are computed based on the model loss (training loss), class-irreducible loss (training loss from a reference model training on class-specific holdout data), and class-holdout loss (training loss on holdout data). Although existing works such as RHO-LOSS employ similar reference models training on holdout datasets, they fail to optimize for underrepresented classes in the training data. Further, REDUCR is also robust to noise in the training data, by selecting points that are harder to learn from worse-performing classes over those which are easier to learn (and are already performing well at a given training point).\n\n**Experiments and Results**: REDUCR has been evaluated on both image and text classification datasets. The paper assesses both worst-class test accuracy and average test accuracy. REDUCR outperforms existing batch selection methods like RHO-LOSS by at least 3% in worst-class accuracy, while achieving comparable results to RHO-LOSS in average class performance.", "questions": "Broadly two questions on REDUCR evaluation:\n\n1. How does REDUCR compare with existing data selection algorithms (other than RHO-LOSS) aimed specifically at distributional shifts?\n2. How does REDUCR perform on large-scale classification tasks? Further, can REDUCR be applied to tasks other than classification?", "limitations": "Please refer weaknesses and questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The strengths of the paper are:\n\n1. The proposed data sampling algorithm, REDUCR, aims to optimize worst-class performance in classification tasks. REDUCR makes significant progress towards efficient data sampling algorithms that are robust to class imbalance and noise in training data.\n2. Contributions regarding improved worst-class accuracy are empirically well-supported across a wide range of classification datasets, including both text and images.\n3. The REDUCR algorithm is well-motivated in the paper, with a focus on the efficiency of data sampling.", "weaknesses": "Weaknesses of the paper:\n\n1. All experiments are conducted on small-scale datasets (with fewer than 1000 classes). The paper mentions in line 73 that the problem of robustness becomes less applicable in settings with a high number of classes. However, as the number of classes increases, the problem of class imbalance becomes more pronounced due to the power law in most datasets. Since REDUCR scales linearly with the number of classes, a thorough evaluation of the suggested approach of using super-classes would be beneficial.\n2. The paper does not compare with other approaches, such as [1], which specifically address popularity bias in training datasets and could improve worst-class performance.\n3. The paper lacks ablation experiments on hyperparameters in REDUCR, such as the fraction of data points selected for training and the number of reference models trained.\n\n\n[1] [Distributionally Robust Language Modeling](https://arxiv.org/pdf/1909.02060)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their score recognising the strengths of our paper, including the strong motivation and progress towards solving the problem setting we introduce in this work. In response to the weaknesses and questions:\n\n> W3: Ablation Experiments\n\nWe direct the reviewer to Appendix A.7 of our work where we run ablations on the gradient weight, learning rate and percent train hyperparameters. In response to this feedback we will make it clearer in Section 5.2 (Ablation Studies) that these hyperparameters studies are in the paper’s appendix. The number of reference models is the same as the number of classes if we don’t adopt superclasses. We discuss the superclass setting in the response to question “The paper mentions in line 73..”\n\n> W2/Q1: Comparison with Existing Algorithms\n\nTo the best of our knowledge we are the first work to consider the setting of **online batch selection** that is robust to issues such as distributional shifts and class imbalance. Whilst approaches such as [1] and [2] derive training objectives to address distributional shift, these approaches do not address the question of how to sub-sample the data they are trained on. REDUCR selects data and thus adjusts the distribution of classes in the loss, however [2] directly upweights the gradients of poorly performing classes in the training loss. Indeed one could apply this approach on top of REDUCR to try and further improve performance on the worst classes. This is an important direction to explore but orthogonal to the approach we introduce in REDUCR.\n\n> W1/Q2: High Number of Classes\n\nTo address the linear scaling problem, we propose the super-class approach in Section 5.3 and apply it to CIFAR100. We note that the results on CIFAR100 with super-classes are promising, CIFAR100’s worst-class average test accuracy and average test accuracy outperform all the baseline algorithms. We note in the limitations that this is one of many potential approaches to address the linear scaling problem and as such a full investigation of all these ideas is left for future work; our goal in this work is to introduce the problem setting and thoroughly investigate the base REDUCR algorithm. \n\nThe reviewer also addresses the problem of class imbalance becoming more pronounced due to the power law. This requires further investigation beyond the scope of our work to answer important questions e.g. what are the real world scenarios where introducing more classes worsens class imbalance, what datasets are representative of this, and how these questions are reflected in the model’s performance. \n\n> Q2: General Applicability of REDUCR\n\nREDUCR can potentially be applied to generative tasks or regression. One can generalise the idea of optimising the worst-class performance to optimising the worst-group performance [2]. For example, generative tasks can have different groups of problems related to math, coding, or literature etc. Regression tasks may have different groups of inputs. To apply REDUCR in this setting one needs group labels for each data point and an objective (e.g., log-likelihood) such that the REDUCR selection rule (Equation 7) can still be applied. REDUCR lays a strong foundation for future exploration in this direction, specifically in Section 5.3 where we group classes together, and show strong empirical performance on the CIFAR100 dataset with this approach.\n\n***References***\n\n[1] Yonatan Oren, Shiori Sagawa, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust language modeling. arXiv preprint arXiv:1909.02060, 2019.\n\n[2] Shiori Sagawa et al. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. Internation Conference on Learning Representations, 2020.", "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": "pOZE9ENfM0", "reviewer": "Reviewer_9L5X", "summary": "- This paper introduces a method using an online algorithm with class priority reweighting to downsample data for vision and text tasks. The experiments demonstrate that this approach can achieve robustness and efficiency in situations with imbalanced classes and poor worst-class generation performance.", "questions": "- What are the most challenging aspects when applying this new method to scaling and broader scenarios? Are there potential solutions for addressing these challenges?", "limitations": "- Further exploration is needed on the balance between compute efficiency and data downsampling efficiency among different combinations of model architectures and class group numbers.\n- Limited tasks: The work focuses on and is evaluated using a series of text and image classification tasks. However, to improve data efficiency for real-world applications and broader machine learning models, further research on the effectiveness of this method on other tasks is necessary.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality and Significance: The new online batch selection approach is robust to noise, imbalance, and distributional shifts. It can effectively preserve the worst-class generation performance, as demonstrated by the results.\n- Quality and Clarity: The work includes positive experimental results supported by sufficient formulas that recap the background, problem definition, theoretical algorithms, and justification of the method. The use of figures helps readers better understand the algorithm and evaluation results.", "weaknesses": "- The ablation studies are not elaborated upon. There are limited descriptions on how to draw conclusions about the necessity of each component for robust online batch selection, which raises curiosity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their score and recognising the originality and significance of our approach along with the quality and clarity of our manuscript. In response to the weaknesses, question, and limitations:\n\n> W: Ablation Studies\n\nIn Section 5.2 we investigate how the removal of the class holdout loss term affects the performance of the algorithm. Later in Appendix A.7.2 we also describe in detail how the clipping of the selection score stabilises the selection scores and thus motivate its inclusion in the algorithm. In response to the reviewers feedback we will look to include the following in the paper to further motivate the inclusion of the model loss and class irreducible loss model terms in the algorithm.\n\n*“In Figure 4a) we note that removing the Model Loss results in the worst performance in the set of ablation studies. This is because the Model Loss provides REDUCR with information about which points are currently not classified correctly by the model. By removing this term REDUCR only selects points which do well under the Class Irreducible Loss model and does not prioritise points the model has not yet learnt. Selecting points not yet learnt by the model is an important quality in online batch selection approaches and the main premise of the Train Loss baseline algorithm.* \n\n*Likewise by removing the Class Irreducible Loss Model term we remove the ability of the model to infer if a point can be learnt or not. In [1], the authors note that these pretrained models enable the algorithm to pick points that are learnable and do not have label noise.“*\n\n> Q: Challenges \n\nThe most challenging aspect, which we wrote in Section 6 (Limitations), is that the computational efficiency of REDUCR scales linearly with the number of classes and as such applying this method to scenarios that scale with the number of classes increases the computational cost of selecting data with REDUCR. \n\nTo begin addressing these problems we explore an approach in which we apply REDUCR to superclasses in Section 5.3. This approach shows strong results on the CIFAR100 dataset, outperforming the worst-class and average test accuracy of the baseline algorithms. On top of this we propose another direction of research in the limitations section - using smaller models to guide larger models. A variety of work (see [1][2] in our related work) has shown that smaller models can guide the training of a larger model and, as such, we think this is a promising direction of investigation for improving the algorithm’s computational complexity.\n\nWe intend to study this more rigorously in future work as the scope is beyond that of one conference paper.\n\n> L1: Generalisation of REDUCR\n\nThe compute efficiency and data downsampling efficiency are reflected in the progression of test accuracy as the number of training steps increases. In the general response, we include results on the ConvNext model architecture applied to the Clothing1M dataset. The results indicate that REDUCR can be widely applicable to more architectures. We agree with the reviewer that improving compute efficiency for a larger number of classes is a promising direction of research and address this in the Limitations section of the paper.\n\n>L2: Effectiveness of REDUCR\n\nWe respectfully disagree with the reviewer on this point. Whilst further research on applying REDUCR to non-classification tasks is a promising direction for future work, the focus of this paper is on data selection in the classification setting, introducing the robust online batch selection problem and proposing a practical solution. We demonstrate REDUCR’s performance on two different modalities of data (text and image) showing the algorithm generalises across a number of different real-world classification tasks. Classification problems are still highly relevant to practitioners (e.g. sentiment classification to ensure LLM output is safe) and as such REDUCR has numerous real-world use cases as it is described in our work. \n\nWhile it is always nice to include more tasks and more applications, we don’t consider those “necessary” for our paper, since we have already demonstrated a range of detailed results in both the main paper and appendix to support our claim that class-robust data downsampling is an important problem and REDUCR can help to solve this problem. \n\n***References***\n\n[1] Mindermann et al. Prioritized training on points that are learnable, worth learning, and not yet learnt. International Conference on Machine Learning, 2022.\n\n[2] Sang Michael Xie et al. Doremi: Optimizing data mixtures speeds up language model pretraining. arXiv preprint arXiv:2305.10429, 2023.", "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": "QMQGCQ6hNX", "reviewer": "Reviewer_75mt", "summary": "This paper proposes a data downsampling method called REDUCR which is robust to class imbalance and distribution shits. In particular, REDUCR reduces the scale of the training data while emphasizing the datapoints with the worst generalization performance. Experiments on 6  benchmarks demonstrate the effectiveness of the method.", "questions": "* Could you provide the numerical results on datasets with distribution shifts?\n* Could you discuss other kinds of model architectures such as ConvNeXt and Swin to verify the generalizability of REDUCR?", "limitations": "The authors claim the limitation of this work and that there are no negative societal impacts to be highlighted.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This paper is well-written and well-organized.\n* The motivation of this paper is clear.", "weaknesses": "* In the abstract, the authors claim that REDUCR is robust to distribution shifts. However, the experiment part does not include relevant datasets with different types of distribution shifts between the training and the test samples.\n* Although the technical novelty might be somewhat limited, I like the fact that the method is rather straightforward and effective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review, recognising the strong motivation behind our work, and that our paper is well-written. In response to the weaknesses and questions:\n\n> W1/Q1: REDUCRs Performance under Distribution Shifts\n\nIn response to the reviewer’s first question, we direct the reviewer to line 272 of the Key Results Section. Here we note that the Clothing 1M dataset sees a distribution shift between the training and test set where the worst performing class is more prevalent in the test dataset. We will emphasise this in the text and include a graph to show how the number of points per class changes between the training and test set of the Clothing1M dataset in the appendix of the paper (see the rebuttal pdf).\n\nWe also record the worst-class performance on the test set of all our datasets. The worst possible class distribution shift (defined in terms of groups in [1]) between the training and test set is one where the entire test set consists of only points from the worst performing class. As such one can consider the worst-class test accuracy as a lower bound on the performance under any class distribution shift. In Table 1, we show that REDUCR outperforms all the baselines on this metric. We will adjust the text to make this clearer in the manuscript by adding at the end of the Experiment setup (before Section 5.1):\n\n*“Finally, it is important to note that we analyse the worst-class test accuracy which can be interpreted as a lower bound on a model’s performance under all class distribution shifts. This is because the worst possible distribution shift between the training and test set is one where the entire test set consists of only points from the worst performing class.”*\n\nWhilst other types of distribution shift exist, class distribution shift is an important subset and can drastically affect the performance of algorithms - the worst-class test accuracy varies dramatically from the average test accuracy on certain datasets. Robust online batch selection to address a wider variety of types of distribution shift remains an open problem and is an interesting direction for consideration in future works. \n\n> W2: Novelty\n\nTo the best of our knowledge our work is the first to propose and address the question of robust online batch selection. Whilst the use of reference models to help point selection and a weighting strategy to improve the worst class performance are both present in the literature, using those ideas to solve the problem is non-trivial and is a novel contribution of our paper. This can be seen through the class holdout loss term and class irreducible loss model which arise only in the robust online batch selection setting and are unique to our work.\n\n> Q2: Generalizability of REDUCR\n\nWe thank the reviewer for their recommendation and have included experiment results using the Clothing1M dataset and the ConvNext architecture in the attached pdf. \n\nWe repeated the Clothing1M results using the *facebook/convnext-tiny-224*, ConvNext model architecture [2] from HuggingFace. The results are presented in the attached pdf. We note that REDUCR continues to match or outperform all the baseline approaches on the dataset. We ran each experiment for 3 seeds and used the hyperparameters from our original Clothing1M experiment. These are promising initial results and further hyperparameter tuning specific to the model architecture will improve the performance further.\n\nWe have addressed all of the reviewers points, run additional experiments to further verify the generalizability of REDUCR and included several clarifying remarks in the manuscript. In light of this we ask that the reviewer reconsider and increase their score.\n\n***References***\n\n[1] Shiori Sagawa et al. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. Internation Conference on Learning Representations, 2020.\n\n[2] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11976–11986, 2022.", "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:
We thank the reviewers and ACs for their time and work in evaluating our paper. In response to your feedback we have re-run our experiments on the Clothing1M dataset with a new model architecture to test the generalizability of REDUCR. The results can be seen in the attached PDF. REDUCR outperforms the next best baseline in terms of the mean worst-class and average test accuracy. We ran each experiment for 3 seeds, using the original hyperparameters from our original Clothing1M experiment. These are promising initial results and further hyperparameter tuning specific to the model architecture will improve the performance further.

We have also clarified several points in the manuscript. Firstly we have provided a more detailed explanation of how ablating various components of REDUCR affects the algorithm’s performance:

*“In Figure 4a) we note that removing the Model Loss results in the worst performance in the set of ablation studies. This is because the Model Loss provides REDUCR with information about which points are currently not classified correctly by the model. By removing this term REDUCR only selects points which do well under the Class Irreducible Loss model and does not prioritise points the model has not yet learnt. Selecting points not yet learnt by the model is an important quality in online batch selection approaches and the main premise of the Train Loss baseline algorithm.*

*Likewise by removing the Class Irreducible Loss Model term we remove the ability of the model to infer if a point can be learnt or not. In [1], the authors note that these pretrained models enable the algorithm to pick points that are learnable and do not have label noise.“* 

Secondly, we have clarified how by analysing the worst-class test accuracy we lower bound the performance of the trained model under a variety of class distribution shifts:

*“Finally, it is important to note that we analyse the worst-class test accuracy which can be interpreted as a lower bound on a model’s performance under all class distribution shifts. This is because the worst possible distribution shift between the training and test set is one where the entire test set consists of only points from the worst performing class.”*

Thirdly we have visualised the distribution shift in the Clothing1M dataset, we will include this in the paper and have added this plot to the attached PDF.

Finally, we will further clarify in the main text that the extensive ablation experiments we ran on the gradient weight, learning rate and percent train hyperparameters are included in the Appendix.

We look forward to engaging with the reviewers in the author reviewer discussion period.

Meta-review: This paper investigates the problem of reducing model training costs. The authors propose a novel approach that combines an online algorithm with class priority reweighting to downsample data effectively. Experiments conducted on both image and text datasets demonstrate the efficacy of the proposed method. Overall, this paper is technically novel and solid, clearly exceeding the bar for NeurIPS. All reviewers agree to accept it for publication. Please revise this paper according to the reviewers' suggestions in the final version.
Decision: Accept (poster)