REDUCR: Robust Data Downsampling using Class Priority Reweighting

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 16:37:21

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\%.

Main paper: 
 introduction: 
 The abundance of data has had a profound impact on machine learning (ML), both positive and negative. On the one hand, it has enabled ML models to achieve unprecedented performance on a 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 et al., 2023) . On the other hand, training models on such large datasets can be computationally expensive and time-consuming (Kaddour et al., 2023) , making it unsustainable in some situations (Bender et al., 2021; Patterson et al., 2021) . Additionally, the high speed at which streaming data is collected can make it infeasible to train on all of the data before deployment. To tackle these issues, various methods have emerged to selectively choose training data, either through pre-training data pruning (Sorscher et al., 2022; Bachem et al., 2017) or online batch selection techniques (Loshchilov & Hutter, 2016; Mindermann et al., 2022) , ultimately reducing data requirements, improving training efficiency, and enabling ML models to handle otherwise unmanageable large and complex datasets.However, in real-world settings, a variety of factors can affect the selection of datapoints, such as 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 & Chan, 1998; Radivojac et al., 2004) . Online selection methods can exacerbate these problems by further reducing the number of datapoints from underrepresented classes, which can degrade the performance of the model on those classes (Buda et al., 2018; Cui et 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 are overrepresented at test time.In this work, we introduce REDUCR, which is 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 1 illustrates the intuition on how the method works. REDUCR can effectively reduce the training data and improve training efficiency while preserving the worst-class generalization performance of the model. For example, on the Clothing1M dataset (Xiao et al., 2015) , Figure 2 shows that, compared to the best performing online batch selection methods, REDUCR achieves around a 15% boost in performance for the worst-class test accuracy. We propose the REDUCR algorithm, which is equipped with a new robust selection rule that evaluates how much a datapoint will affect the generalization error of a specific class ( §4.2). ( 3) We evaluate our algorithm on a series of text and image classification tasks and show that it achieves strong worst-class test accuracy while frequently surpassing state-of-the-art methods in terms of average test accuracy( §5).Related work. Mindermann et al. (2022) have developed an online batch selection method called RHO-LOSS, which uses a reference model trained on a holdout dataset to guide the selection of points during training. Certain extensions of this work have focused on using a reference model in different settings such as reinforcement learning (Sujit et al., 2022) . However, to our knowledge, none have focused on improving the worst-class generalisation performance. Other batch selection methods (Loshchilov & Hutter, 2016; Jiang et al., 2019; Kawaguchi & Lu, 2020) use the training loss of points under the model or an approximate gradient norm (Katharopoulos & Fleuret, 2017) to select challenging points. We observe that these methods (e.g., see Loshchilov & Hutter (2016) in Figure 2 ) exhibit greater consistency in terms of worst-class generalization error in imbalanced datasets. Nevertheless, Loshchilov & 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 a holdout dataset to train robust models. Oren et al. (2019) ; Liu et al. (2021) ; Clark et al. (2019) use a reference model to identify difficultto-learn groups (or points, or biases) during training. Han et al. (2018) use two models which act as a reference model for the other to remove noisy points from the training data. Cao et al. (2021) ; Ren et al. (2018) use a 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 on 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 selection strategies. Xie et al. (2023) use both weights update rules and a reference model to find mixtures of corpora in LLM pretraining resulting in improved performance and training speed. Besides the problem setup, our method differs in three ways: i) we focus upon online batch selection; ii) we use multiple reference models; iii) and we use a class-holdout loss term (see Equation ( 7)) to reweight batches.Finally, efficient data selection is a well-explored problem with various approaches, including active learning methods when label information is unknown (MacKay, 1992; Houlsby et al., 2011; Kirsch et al., 2019; 2023; Ash et al., 2020) ; data pruning and coreset techniques for pre-training data selection (Sorscher et al., 2022; Bachem et al., 2017; Borsos et al., 2020; Coleman et al., 2020) ; data distillation approaches (Cazenavette et al., 2022; Nguyen et al., 2021) ; and non-parametric inducing point methods (Galy-Fajou & Opper, 2021) . 
background: 
 We consider a C-way classification task and denote a model as p(y | x, θ), where x denotes an input and y ∈ [C] the corresponding class label; the model is parameterized by θ. For any training dataset D = {(x i , y i )} N i=1 with N datapoints, we use a point estimate of θ to approximate the posterior model as p(y | x, D) ≈ p(y | x, θ). This estimate θ can be obtained by running stochastic gradient descent (SGD) to optimize the cross-entropy loss over training dataset D.The goal of data downsampling is to select a dataset D T ⊂ 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 a separate holdout dataset D ho = {(x ho,i , y ho,i )} N ho i=1 as follows:EQUATIONwhere the inputs and their labels are x ho = [x i,ho ] N ho i=1 and y ho = [y i,ho ] N ho i=1 , respectively. Here, the likelihood of the holdout dataset is used as a proxy for the generalisation error. The problem is computationally prohibitive due to its combinatorial nature. Moreover, for a massive (or streaming) training dataset D, it is not computationally possible to load D all at once and it is common to loop through the data by iteratively loading subsets.Online batch selection is a practical streaming setup to approximate the data downsampling problem, where at each timestep t, the model observes a training data subset B t ⊂ D, and the goal is to iteratively select a small batch b t ⊂ B t for the model to take gradient steps. A standard solution to this problem is to design a 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 t . See Algorithm 2 in Appendix A.1 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 t, RHO-Loss selectsEQUATIONwhereD t = t-1τ =1 b τ is the cumulative training data the model has encountered until iteration t. 
problem formulation: 
 In this work, we introduce the robust data downsampling problem, where the goal is to select a training dataset D T of size T such that worst-class performance is optimized. Let the holdoutdataset with class c ∈ [C] be D (c) ho = {(x, y) ∈ D ho | y ≡ c} = {(x (c) ho,i , y (c) ho,i )} N (c) hoi=1 . We can write the objective of robust data downsampling asEQUATIONwherex (c) ho = [x (c) ho,i ] N (c) ho i=1 and y (c) ho = [y (c) ho,i ] N (c) hoi=1 correspond to the collections of inputs and labels in the class-specific holdout dataset D (c) ho . Compared to Equation (1), the objective in Equation ( 3) is even more challenging because of the maximin optimisation that involves C discrete classes. In fact, solving Equation ( 3) is known to be NP-hard, even when the objectives (each p(y(c) ho |x (c) ho , •), c ∈ [C]) are submodular set functions. Chen et al. (2017) demonstrate the application of zero-sum game no-regret dynamics, where a learner employs a (1 -1/e)-near-optimal greedy strategy and an adversary seeks to find a distribution over loss functions that maximizes the learner's loss. In this scenario, a single set is identified, which, although larger than size T , achieves a constant-factor approximation.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 t ⊂ D at each timestep t. The goal is to select a small batch b t ⊂ B t 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 a practical algorithm for its implementation. 
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 selection strategy of REDUCR relates the effect of training on a batch of candidate points b t to the generalization error of a specific class in the holdout dataset.To solve Equation (3) in an online manner, we propose to use class priority reweighting, a variant of the multiplicative weights update method (Freund & Schapire, 1997; Cesa-Bianchi & Lugosi, 2006) . At the beginning of training we initialise a weight vector w 0 over a C dimensional simplex,∆ = {w = [w c ] C c=1 ∈ R C | C c=1 w c = 1}. Each element of w 0 is initialised to be w 0,c = 1/C. For each iteration t, small batch b t ⊂ B t is chosen by maximising the weighted sum of the C different class-specific scoring functions (i.e., by best-responding to the current class-weights w t ),EQUATIONwhere .D t = t-1 τ =1 b τ , w t = [w t,c ] C c=1 ∈ ∆,(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), η is a learning rate that adjusts how concentrated the probability mass is in the resulting distribution. Figure 1 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). We next introduce how to compute the likelihoods for class-specific holdout sets, i.e., p(y(c) ho |x (c) ho , D t ∪ b) in Equation (4).Given the current dataset D t at timestep t and additional datapoints b ⊂ B t , we would like to compute the likelihood of the holdout dataset that belongs to class c. For simplicity, we consider the case where the small batch to be selected only includes a single datapoint, i.e., b = {(x, y)}. We express the objective using the Bayesian perspective introduced in Section 2, i.e., log p(y We use L[y|x, θ] = -log p(y | x, θ) to denote the cross-entropy loss for any model parameters θ, and we re-write Equation (6) as follows, log p(y(c) ho | x (c) ho , Dt ∪ {(x, y)}) = log p(y|x,D (c) ho ,D t )p(y (c) ho |x (c) ho ,x,D t ) p(y|x,x (c) ho ,D t ) = log p(y|x,D (c) ho ,D t )p(y (c) ho |x (c) ho ,D t ) p(y|x,D t ) = -log p(y | x, Dt) + log p(y | x, Dt, D (c) ho ) + log p(y (c) ho | x (c) ho , Dt).(c) ho | x (c) ho , D t ∪ {(x, y)}) ≈ L[y|x, θ t ] model loss -L[y|x, θ (c) t ] class-irreducible loss -L[y (c) ho |x (c) ho , θ t ]class-holdout loss .(7)We name the three terms in Equation ( 7) the model loss, class-irreducible loss and class-holdout loss, respectively. We define the term excess loss as the difference of the model loss and class-irreducible loss. The excess loss is the improvement in loss for point (x, y) by observing more data from class c (i.e., Dho ). The class-irreducible loss and the class-holdout loss both depend on the class c. Intuitively, if two data points are from different classes, REDUCR will take into account the weight of the worst-performing class, which is reflected by the class-holdout loss. This ensures that RE-DUCR is focusing on improving the performance of the model on the classes that are most difficult to learn. In a 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 ( 7) is far more tractable than naively re-training a new model (i.e., log p(y(c) ho |x (c) ho , D t ∪ {(x, y)}))for each possible candidate point (x, y). The model loss and the class-holdout loss only require evaluating the cross-entropy losses of some datapoints on the target model. More generaly, if batch b can include more than one point, we can simply change the x and y to a list of inputs and labels instead. Next, we further improve the efficiency of REDUCR by approximating the class-irreducible loss model.For each selected batch b t under the current selection rule in Equation ( 7), we need to update C class-irreducible loss models to compute the class-irreducible losses. We propose to approximate these models using amortised class-irreducible loss models, which are trained for each class at the beginning of REDUCR and do not need to be updated at future timesteps.We interpret the class irreducible loss term as an expert model at predicting the label of points from a specific class c due to the extra data from the holdout dataset this term has available. To create an approximation of this expert model, we train the amortised class-irreducible loss models using an adjusted loss function in which points with a label from the class c are up-weighted by a parameter γ ∈ (0, +∞) (set in Section 5):EQUATIONHere we define I[•] as the indicator function. Equation ( 8) optimizes over the parameters of the amortised class-irreducible loss model for class c, and obtain ϕ c to approximate θ(c) t in Equation (7), i.e., L[y|x, θ (c) t ] ≈ L[y|x, ϕ c ].Algorithm 3 details the full amortised class-irreducible loss model training procedure in Appendix A.2. We further motivate our approximation in Appendix A.3.We use the selection objective in Equation ( 7) along with the amortised class-irreducible 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 1 for a full description of the REDUCR method.At each iteration, the top k points are selected (Line 6) according to the weighted sum of Equation ( 7) for each class c ∈ C, thus efficiently approximating the combinatorial problem from Equation (4). As the class-holdout loss does not depend on the selected points b t 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 t (in Line 7 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. Compute the objective value for every class c ∈ C:α c ← (x,y)∈bt max(0, L[y|x, θ t ] -L[y|x, ϕ c ]) -L[y (c) ho |x (c) ho , θ t ] 8:Update class weights for every class c ∈ C: w t+1,c = w t,c exp(-ηαc) j∈C wt,j exp(-ηαj ) 9:θ t+1 ← SGD(θ t , b t ) 10: end forWhen 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 & Hutter, 2016; Kawaguchi & 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-irrelevant points may be selected. In contrast, REDUCR addresses both of these issues by identifying underrepresented classes and using the class-irreducible 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 reweight 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 5. 
experiments: 
 In this section, we present empirical results to showcase the performance of REDUCR on largescale vision and text classification tasks. Datasets. We train and test REDUCR on image and text datasets. We use CIFAR10 (Krizhevsky et al., 2009 ), CINIC10 (Darlow et al., 2018 ), Clothing1M (Xiao et al., 2015) , the Multi-Genre Natural Language Interface (MNLI), and the Quora Question Pairs (QQP) datasets from the GLUE NLP benchmark (Wang et al., 2019) . Each dataset is split into a labelled training, validation and test dataset (for details see Appendix A.5), the validation dataset is used to train the class-irreducible loss models and evaluate the class-holdout loss during training. The Clothing1M dataset uses 100k 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 t from dataset D at each timestep. Models. For the experiments on image datasets (CIFAR10, CINIC10 and Clothing1M) all models use a ResNet-18 model architecture (He et al., 2016) . For the Clothing1M dataset we use a ResNet-18 model pretrained on the imagenet dataset (Deng et al., 2009) . The networks are optimised with AdamW (Loshchilov & Hutter, 2019) and the default Pytorch hyperparameters are used for all methods except CINIC10 for which the weight decay is set to a value of 0.1. For the NLP dataset we use the bert-base-uncased (Devlin et al., 2019) 1 , demonstrate the significant advantage of REDUCR to improve the worst-class accuracy while maintaining the strong average-case performance.Baselines. We benchmark our method against the state-of-the-art RHO-LOSS (Mindermann et al., 2022) and Loshchilov & Hutter (2016) , an online batch selection method that uses the training loss to select points. We refer to the latter baseline as TRAIN LOSS. We also compare against UNIFORM where points are chosen at random from the large batch at each training step. 1 All experiments are run multiple times and the mean and standard deviation across runs calculated. Unless stated otherwise 10% of batch B t is selected as the small batch b t , and we set η = 1e -4. γ = 9 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 of γ and η on REDUCR further in Appendix A.9. For full details of the experimental setup see Appendix A.5.2 The worst-class and average test accuracy for the datasets and model are shown in Table 1 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 also surprising because the primary goal of REDUCR is not to optimize the overall average (over classes) performance.REDUCR performs particularly strongly on the Clothing1M dataset: Table 1 shows REDUCR improves the worst-class test accuracy by around 15% when compared to TRAIN LOSS, the next best-performing baseline, and by around 26% when compared to RHO-LOSS, the overall best-performing baseline across datasets. Figure 3b shows that REDUCR also achieves this performance in 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 CINIC10 dataset as shown in Figure 3c and Figure 3d and the MNLI and QQP datasets as detailed in Figure 6 .The Clothing1M dataset also sees a 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 its performance impact the average test accuracy significantly. Figure 3a shows the impact of this distribution shift as the improved performance of the model on the worst-class results in an improved average test accuracy to the state-of-the-art RHO-LOSS baseline.To further motivate the selection rule in Equation ( 7), 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 on CIFAR10, with 1%, 2.5%, 10.0% percent imbalances (percentage of training data that belong to the imbalanced class). REDUCR significantly reduces the deterioration in performance, showing that target models trained using our method are more robust to class imbalance than models trained using the RHO-LOSS and UNIFORM baselines.of REDUCR on the CINIC10 dataset when the model loss, amortised class-irreducible loss and class-holdout loss terms of the algorithm were individually excluded from the selection rule. We note that all three terms in Equation ( 7) are required to achieve a strong worst-class test accuracy.The removal of the class-holdout loss term affects the ability of REDUCR to prioritise the weights of the model correctly. In Figure 4 we compare the class weights of REDUCR and an ablation model without the class-holdout loss term. The standard model clearly prioritises classes 3, 4 and 5 during training across all 5 runs, whilst the ablation model does not consistently weight the same classes across multiple runs. We also conducted an ablation study on the clipping of the excess loss to motivate its inclusion in the algorithm, this is also shown in Figure 4a , we note that this stabilises the model performance towards the end of training and investigate further in Appendix A.7.2.In this section, we investigate the performance of models trained using REDUCR on imbalanced datasets. We artificially imbalance the CIFAR10 dataset such that a datapoint of the imbalanced class is sampled with probability p ∈ (0, 1/C] (referred to as the percent imbalance) and datapoints from the remaining classes are sampled with probability (1 -p)/(C -1) during model training. We only artificially imbalance the training and validation sets and not the test set. We conduct experiments with 1.0%, 2.5% and 10.0% percent imbalances on classes 3 and 5. Note that a percent imbalance of 10.0% is equivalent to the original (balanced) CIFAR10 training and validation sets. We repeat the experiments 10 times and plot the median values in Figure 5 , and the error bars denote the best accuracy and the worst across 10 runs.We find that the performance of models trained using REDUCR deteriorates less than those trained with the RHO-LOSS or UNIFORM baselines as the percent imbalance of a particular class decreases (see Figure 5 ). For example, when class 3 is imbalanced, in the most imbalanced case (1.0%) the median performance of 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. 
conclusion and future work: 
 In summary, we identified the problem of class-robust data downsampling and proposed a new method, REDUCR, to solve this problem using class priority reweighting. ho . 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 as a form of importance weighting (Shimodaira, 2000) , where by upweighting points with labels in a specific class we are calculating an approximation of the loss under a distribution in which points from class c are more prevalent. 
 
 Appendix: The class-holdout loss term only affects the selection of points at each iteration t through the selection of the weights w t . As it does not depend upon the candidate point (x, y) ∈ B t and the weights sum to one we can remove it from line 6 of Algorithm 1 and only include it in line 7 when we update the class weights. Similarly as the model loss does not depend upon the class c we can write the selection score as c∈C w t,c log p(y QQP. The dataset consists of 431k labeled sentence pairs; we remove points from class 1 to further imbalance 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.(c) ho |x (c) ho , D t ∪({x, y})) = L[y|x, θ t ]- c∈C w t,c (L[y|x, θ (c) t ])- c∈C w t,c (L[y (c) ho |x (c) ho , θ t ]).ResNet-18 used for the Clothing1M experiments is the pretrained model available via the Torchvision (Marcel & Rodriguez, 2010) Train Loss baseline is taken from Loshchilov & Hutter (2016) where points from the large batch B t are sampled with probabilityEQUATION)Here p i is the point with the i th highest training loss in the large batch. We set the selection pressure parameter s e = 100 and do not vary this during training as per the Experiments in Section 6. of Loshchilov & Hutter (2016) .Compute. All models were trained on NVIDIA Tesla T4 GPUs.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.In Table 3 and Table 4 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 check-point the model during training. REDUCR still outperforms or 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 a more data efficient manner. Figure 6b and Figure 6d In Appendix A.7.1 we show the per class weights for the Clothing1M dataset, whilst in Appendix A.7.2 we analyse the effect of the clipping term and provide some intuition behind its inclusion in the algorithm.The Clothing1M dataset is imbalanced with respect to class 4. Figure 7 shows that REDUCR is able to consistently identify and weight the underrepresented class across model runs.To further understand the effects of clipping in the algorithm we analyse the selection score of the selected points with and without clipping. As detailed in Appendix A.4 the class-holdout loss only affects the selection of points via the weights w t at each time step, as such we record only the excess loss (the difference between the model loss and class irreducible loss). Figure 8 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, Figure 8a shows the selection scores smoothly decrease throughout training as the model loss improves. Without clipping the excess loss decreases smoothly at the beginning of training and then shows unstable behaviour across runs later in training.In practice we select multiple points per batch by selecting the points with the top k 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. All experiments in this section use the CIFAR10 dataset. We use ResNet-18 target models (trained using η = 10 -4 and with a percent train of 0.10) and ResNet-18 class irreducible loss models (trained using γ = 9) unless otherwise stated.We find that REDUCR's performance is not sensitive to the learning rate η and the frequency of class hold-out loss updating. We find that REDUCR's performance is sensitive to the gradient weight γ, though this is because a larger gradient weight increases the variance of loss gradients and slows model training. REDUCR's performance is not sensitive to the gradient weight at smaller In summary, REDUCR's performance is largely insensitive to the values of newly-introduced hyper-parameters on the CIFAR10 dataset. Sensitivity analyses on additional datasets are needed to increase the robustness of these findings. However, a gradient weight of γ = 9 and a percent train of 0.10 perform well without additional hyper-parameter tuning for several datasets, class irreducible loss model architectures and target model architectures in our main experiments, which tentatively suggests the robustness of these findings.A.9.1 LEARNING RATE η First, we perform a sensitivity analysis on the learning rate η. We train target models using RE-DUCR for each η ∈ {10 -4 , 10 -3 , 10 -2 , 10 -1 , 10 0 , 10 1 }. A.9.2 GRADIENT WEIGHT γ Next, we perform sensitivity analysis on the gradient weight γ. We train sets of class-irreducible loss models for each γ ∈ {0.25, 0.5, 1.0, 4.0, 9.0, 19.0, 49.0, 99.0} and train target models trained using REDUCR for each set of class-irreducible loss models.Experimental results show that increases in the gradient weight above 9.0 result in faster improvement in target model performance early in training, though target model performance converges to a lower value later in training for larger gradient weights γ ∈ {19.0, 49.0, 99.0}.Higher gradient weights increases the variance of loss gradients, which requires a greater number of training epochs for class-irreducible loss model training. In our experiments, class irreducible loss models trained with gradient weights γ ∈ {19.0, 49.0, 99.0} do not converge before the end of training. Poor target model performance for larger gradient weights γ ∈ {19.0, 49.0, 99.0} is therefore the result of pre-convergence class-irreducible loss models. This finding highlights the trade-off between fast target model training (which requires a large gradient weight) and fast class irreducible loss model training (which requires a smaller gradient weight). Regardless, final target model performance is similar providing class irreducible loss models reach convergence, as is the case for gradient weights γ ∈ {0.25, 0.5, 1.0, 4.0, 9.0}.We next perform sensitivity analysis on the fraction of datapoints selected for target model training n b /n B (referred to as the percent train). In particular, we use a constant selected batch size n b and vary the original batch size n B in order to vary the fraction of datapoints selected for target model training. Intuitively, a smaller percent train allows REDUCR to select from a greater number of candidate datapoints at each training step, which results in the selection of datapoints with larger weighted reducible loss all else the same. Since datapoints with larger (weighted) reducible loss are those from which a model can learn the most (Mindermann et al., 2023) , we expect a smaller percent train to result in a faster improvement in target model performance. We train target models using REDUCR for each percent train, batch size pair in {(0.05, 640), (0.10, 320), (0.15, 216), (0.20, 160), (0.25, 128)} (i.e., we train all target models using a selected batch size of 32). We find that a percent train of 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, 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.Experimental results demonstrate the performance of REDUCR is largely insensitive to the percent train (for a constant selected batch size) for non-extreme percent trains (recall uniform selection corresponds to a percent train of 1.0). Therefore, in practice, a selected batch size n b should first be chosen such that loss gradient estimates have a low variance, and then a batch size n B should be chosen such that the percent train n b /n B is an intermediate value (e.g., 0.10).Experimental 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, some form of soft selection may result in better model performance.A.9.4 FREQUENCY OF CLASS HOLD-OUT LOSS UPDATINGIn our experiments, class hold-out losses are updated at the end of each training epoch using the full hold-out set. However, target model performance may improve on some classes significantly more than others during a training epoch (especially early in training). We therefore perform a sensitivity analysis on the frequency with which class hold-out losses are updated.It is computationally expensive to update class hold-out losses using the full hold-out set. To reduce the computational cost of more frequent class hold-out loss updating, it is therefore necessary to update class hold-out losses using only a small subset (e.g., a single batch) of the full hold-out set at each update. However, class hold-out losses computed using a small subset of hold-out set datapoints are noisy. We therefore use an exponentially-weighted moving average of class hold-out losses computed on batches of hold-out set datapoints. In particular, a batch of size n B is sampled uniformly at random from the hold-out set at each training step. Losses are then computed for each datapoint in the sampled batch using the current target model. Finally, for each class c ∈ [C],losses of datapoints of class c in the sampled batch are averaged and used to update a de-biased exponentially-weighted moving average with decay parameter a ∈ [0, 1].We perform experiments using exponentially-weighted moving averages with decay parameters a ∈ 0.9, 0.99 for fast updating of class hold-out losses. Experimental results demonstrate REDUCR's performance is not sensitive to the frequency of class hold-out loss updating.A.10 HIGHLY IMBALANCED DATASETSWe also conduct experiments with 0.25% and 0.5% percent imbalances on classes 3 and 5. However, (class) irreducible loss models and target models only receive 6. We use training step and timestep interchangeably.Code available at: https://anonymous.4open.science/r/REDUCR-24D3 


Decision: 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.

Reviews: review: paper_summary: paper_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.

**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).

**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.
strength_weakness: strength_weakness: Weaknesses of the paper:

1. 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.
2. 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.
3. 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.


[1] [Distributionally Robust Language Modeling](https://arxiv.org/pdf/1909.02060)
questions: questions: Broadly two questions on REDUCR evaluation:

1. How does REDUCR compare with existing data selection algorithms (other than RHO-LOSS) aimed specifically at distributional shifts?
2. How does REDUCR perform on large-scale classification tasks? Further, can REDUCR be applied to tasks other than classification?
limitations: limitations: Please refer weaknesses and questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: 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: 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.
- 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* Although the technical novelty might be somewhat limited, I like the fact that the method is rather straightforward and effective.
questions: questions: * Could you provide the numerical results on datasets with distribution shifts?
* Could you discuss other kinds of model architectures such as ConvNeXt and Swin to verify the generalizability of REDUCR?
limitations: limitations: The authors claim the limitation of this work and that there are no negative societal impacts to be highlighted.

Comments: comment: Thank you for your feedback on our work and for raising your score.
We would like to thank the reviewer for their remarks and raising their score.
Thank you for your response. It has addressed most of my concerns. Therefore, I chose to raise my score.
Thanks for the comprehensive responses, especially regarding the challenges. I have updated the rating to 7 and look forward to the future work.