KAKURENBO: Adaptively Hiding Samples in Deep Neural Network Training
This paper proposes a method for hiding the least-important samples during
the training of deep neural networks to increase efficiency, i.e., to reduce
the cost of training. Using information about the loss and prediction
confidence during training, we adaptively find samples to exclude in a given
epoch based on their contribution to the overall learning process, without
significantly degrading accuracy. We explore the converge properties when
accounting for the reduction in the number of SGD updates. Empirical results on
various large-scale datasets and models used directly in image classification
and segmentation show that while the with-replacement importance sampling
algorithm performs poorly on large datasets, our method can reduce total
training time by up to 22% impacting accuracy only by 0.4% compared to the
baseline. Code available at https://github.com/TruongThaoNguyen/kakurenbo
Truong Thao Nguyen, Balazs Gerofi, Edgar Josafat Martinez-Noriega, François Trahay, Mohamed Wahib
# KAKURENBO: Adaptively Hiding Samples in Deep Neural Network Training

###### Abstract

This paper proposes a method for hiding the least-important samples during the training of deep neural networks to increase efficiency, i.e., to reduce the cost of training. Using information about the loss and prediction confidence during training, we adaptively find samples to exclude in a given epoch based on their contribution to the overall learning process, without significantly degrading accuracy. We explore the converge properties when accounting for the reduction in the number of SGD updates. Empirical results on various large-scale datasets and models used directly in image classification and segmentation show that while the with-replacement importance sampling algorithm performs poorly on large datasets, our method can reduce total training time by up to 22% impacting accuracy only by 0.4% compared to the baseline. Code available at [https://github.com/TruongThaoNguyen/kakurenbo](https://github.com/TruongThaoNguyen/kakurenbo)

## 1 Introduction

Empirical evidence shows the performance benefits of using larger datasets when training deep neural networks (DNN) for computer vision, as well as in other domains such as language models or graphs [1]. More so, attention-based models are increasingly employed as pre-trained models using unprecedented dataset sizes, e.g. the JFT-3B dataset consists of nearly three billion images, annotated with a class-hierarchy of around 30K labels [2], LIAON-5B provides 5,85 billion CLIP-filtered image-text pairs that constitute over 240TB [3]. A similar trend is also observed in scientific computing, e.g., DeepCAM, a climate simulation dataset, is over 8.8TB in size [4]. Furthermore, the trend of larger datasets prompted efforts that create synthetic datasets using GANS [5] or fractals [6]. The downside of using large datasets is, however, the ballooning cost of training. For example, it has been reported that training models such as T5 and AlphaGo cost $1.3M [7] and $35M [8], respectively. Additionally, large datasets can also stress non-compute parts of supercomputers and clusters used for DNN training (e.g., stressing the storage system due to excessive I/O requirements [9; 10]).

In this paper, we are focusing on accelerating DNN training over large datasets and models. We build our hypothesis on the following observations on the effect of sample quality on training: a) _biased with-replacement sampling_ postulates that not all samples are of the same importance and a biased, with-replacement sampling method can lead to faster convergence [11; 12], b) _data pruning_ methods show that when select samples are pruned away from a dataset, the predication accuracy
that can be achieved by training from scratch using the pruned dataset is similar to that of the original dataset [13; 14; 15; 16]. Our hypothesis is that if samples have a varying impact on the learning process and their impact decreases as the training progresses, then we can in real-time, adaptively, exclude samples with the least impact from the dataset during neural network training.

In this paper, we dynamically hide samples in a dataset to reduce the total amount of computing and the training time, while maintaining the accuracy level. Our proposal, named KAKURENBO, is built upon two pillars. First, using combined information about the loss and online estimation of the historical prediction confidence (see Section 3.1) of input samples, we adaptively exclude samples that contribute the least to the overall learning process on a per-epoch basis. Second, in compensation for the decrease in the number of SGD steps, we derive a method to dynamically adjust the learning rate and the upper limit on the number of samples to hide in order to recover convergence rate and accuracy.

We evaluate performance both in terms of reduction in wall-clock time and degradation in accuracy. Our main results are twofold: first, we show that decaying datasets by eliminating the samples with the least contribution to learning has no notable negative impact on the accuracy and convergence and that the overhead of identifying and eliminating the least important samples is negligible. Second, we show that decaying the dataset can significantly reduce the total amount of computation needed for DNN training. We also find that state-of-the-art methods such as importance sampling algorithm [11], pruning [13], or sample hiding techniques [17; 18] performs poorly on large-scale datasets. To the contrary, our method can reduce training time by \(10.4\%\) and \(22.4\%\) on ImageNet-1K [19] and DeepCAM [4], respectively, impacting Top-1 accuracy only by \(0.4\%\).

## 2 Background and Related Work

As the size of training datasets and the complexity of deep-learning models increase, the cost of training neural networks becomes prohibitive. Several approaches have been proposed to reduce this training cost without degrading accuracy significantly. Table 1 summarizes related work against this proposal. This section presents the main state-of-the-art techniques. Related works are detailed in the Appendix-E.

**Biased with-Replacement Sampling** has been proposed as a method to improve the convergence rate in SGD training [11; 12]. Importance sampling is based on the observation that not all samples are of equal _importance_ for training, and accordingly replaces the regular uniform sampling used to draw samples from datasets with a biased sampling function that assigns a likelihood to a sample being

\begin{table}
\begin{tabular}{|p{56.9pt}|p{113.8pt}|p{113.8pt}|p{113.8pt}|p{113.8pt}|p{113.8pt}|} \hline
**Approach** & **Method** & \multicolumn{2}{c|}{**Merits (+)**} & \multicolumn{1}{p{113.8pt}|}{**Oline/ Offline (Bottleneck)**} & \multicolumn{1}{p{113.8pt}|}{**Practical Overhead (Constr)**} \\ \hline
**Biased w/** **Replacement Sampling** & Importance Sampling [11] & * Theoretically faster convergence & Offline & Sorting samples & O(\(N_{\textit{log}}(N)\)) \\ \cline{3-6}  & & & No demonstrated speedup on large datasets (Section 4) & Online & Sorting samples & O(\(N_{\textit{log}}(N)\)) \\ \cline{3-6}  & & & No demonstrated speedup & & & \\ \hline
**Data** & Engineers Scores [13] & * Robust & & & & \\
drawn proportional to its importance; the more important the sample is, the higher the likelihood it would be selected. The with-replacement strategy of importance sampling maintains the total number of samples the network trains on. Several improvements over importance sampling have been proposed for distributed training [22], or for estimating the importance of samples [12; 23; 24; 25; 26].

Overall, biased with-replacement sampling aims at increasing the convergence speed of SGD by focusing on samples that induce a measurable change in the model parameters, which would allow a reduction in the number of epochs. While these techniques promise to converge in fewer epochs on the whole dataset, each epoch requires computing the importance of samples which is time-consuming.

**Data Pruning techniques** are used to reduce the size of the dataset by removing less important samples. Pruning the dataset requires training on the full dataset and adds significant overheads for quantifying individual differences between data points [27]. However, the assumption is that the advantage would be a reduced dataset that replaces the original datasets when used by others to train. Several studies investigate the selection of the samples to discard from a dataset[13; 15; 14; 16][28].

Pruning the dataset does reduce the training time without significantly degrading the accuracy [13; 14]. However, these techniques require fully training the model on the whole dataset to identify the samples to be removed, which is compute intensive.

**Selective-Backprop**[17] combines importance sampling and online data pruning. It reduces the number of samples to train on by using the output of each sample's forward pass to estimate the sample's importance and cuts a fixed fraction of the dataset at each epoch. While this method shows notable speedups, it has been evaluated only on tiny datasets without providing any measurements on how accuracy is impacted. In addition, the authors allow up to 10% reduction in test error in their experiments.

**Grad-Match**[18] is an online method that selects a subset of the samples that would minimize the gradient matching error. The authors approximate the gradients by only using the gradients of the last layer, use a per-class approximation, and run data selection every \(R\) epochs, in which case, the same subsets and weights will be used between epochs. Due to the infrequent selection of samples, Grad-Match often needs a larger number of epochs to converge to the same validation accuracy that can be achieved by the baseline [29]. Moreover, Grad-Match is impractical in distributed training, which is a de facto requirement in large dataset and models. Distributed Grad-Match would require very costly collective communication to collect the class approximations and to do the matching optimization. This is practically a very high cost for communication per epoch that could even exceed the average time per epoch.

Figure 1: **Overview of KAKURENO. At each epoch, samples are filtered into two different subsets, the training list and the hidden list, based on their loss, prediction accuracy (PA), and prediction confidence (PC), with a maximum hidden fraction of \(F\). PA and PC are used to drive sample move back decisions. Samples in the training list are processed using uniform sampling without replacement. The loss and the prediction accuracy, calculated from the training process, are reused to filter samples in the next epoch. For samples on the hidden list, KAKURENO only calculates the loss and PA by performing the forward pass at the end of each epoch.**
## 3 KAKURENBO: Adaptively Hiding Samples

In this work, we reduce the amount of work in training by adaptively choosing samples to hide in each epoch. We consider a model with a loss function \(\ell(\mathbf{w},\mathbf{x}_{n},\mathbf{y}_{n})\) where \(\left\{\mathbf{x}_{n},\mathbf{y}_{n}\right\}_{n=1}^{N}\) is a dataset of \(N\) sample-label pairs (\(x_{n}\in X\)), and \(G:X\to X\) is a function that is applied to hide certain samples during training, e.g., by ranking and cut-off some samples. Using SGD with a learning-rate \(\eta\) and batch size of \(B\), the update rule for each batch when training with original full dataset is

\[\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\frac{1}{B}\sum_{n\in\mathcal{B}\left(k \left(t\right)\right)}\nabla_{\mathbf{w}}\ell\left(\mathbf{w}_{t},\mathbf{x}_ {n},\mathbf{y}_{n}\right) \tag{1}\]

where \(k\left(t\right)\) is sampled from \(\left[N/B\right]\triangleq\left\{1,\ldots,N/B\right\}\), \(\mathcal{B}\left(k\right)\) is the set of samples in batch \(k\) (to simplify, \(B\) is divisible by \(N\)). We propose to hide \(M\) examples by applying the a hiding function \(G\). We modify the learning rule to be

\[\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\frac{1}{B}\sum_{n\in\mathcal{B}\left(k \left(t\right)\right)}\nabla_{\mathbf{w}}\ell\left(\mathbf{w}_{t},G(\mathbf{x }_{n}),\mathbf{y}_{n}\right) \tag{2}\]

using \(B\) batch at each step, which is composed of \(N/B\) steps. Since we exclude \(M\) samples, the aggregate number of steps is reduced from \(N/B\) to become \(\left(N-M\right)/B\), i.e., fixing the batch size and reducing the number of samples reduces the number of SGD iterations that are performed for each epoch.

Sample hiding happens before presenting the input to each epoch. The training set that excludes the hidden samples (\(N-M\)) is then shuffled for the training to process with the typical w/o replacement uniform sampling method.

Based on the above training strategy, we propose KAKURENBO, a mechanism to dynamically reduce the dataset during model training by selecting important samples. The workflow of our scheme is summarized in Figure 1. First, (B.1) we sort the samples of a dataset according to their loss. We then (B.2) select a subset of the dataset by _hiding_ a fixed fraction \(F\) of the data: the samples with the lowest loss are removed from the training set. Next, (B.3) hidden samples that maintain a correct prediction with high confidence (see Section 3.1) are moved back to the epoch training set. The training process (C) uses uniform sampling without replacement to pick samples from the training list. KAKURENBO adapts the learning rate (C.2) to maintain the pace of the SGD. At the end of the epoch, we perform the forward pass on samples to compute their loss and the prediction information on the up-to-date model (D). However, because calculating the loss for all samples in the dataset is prohibitively compute intensive [11], we propose to reuse the loss computed during the training process, which we call _lagging_ loss (D.2). We only recompute the loss of samples from the hidden list (D.1). In the following, we detail the steps of KAKURENBO.

### Hidden Samples Selection

We first present our proposed algorithm to select samples to hide in each epoch. We follow the observation in [11] that not all the samples are equal so that not-too-important samples can be hidden during training. An important sample is defined as the one that highly contributes to the model update, e.g., the gradient norm \(\nabla_{\mathbf{w}}\ell\left(\mathbf{w}_{t},\mathbf{x}_{n},\mathbf{y}_{n}\right)\) in Equation 1. Removing the fraction \(F\) of samples with the least impact on the training model from the training list could reduce the training time, i.e., the required computing resource, without affecting the convergence of the training process. Selecting the fraction \(F\) is arbitrary and driven by the dataset/model. If the fraction \(F\) is too high, the accuracy could drop. In contrast, the performance gained from hiding samples will be limited if \(F\) is small, or potentially less than the overhead to compute the importance of samples. In this work, we aim to design an adaptive method to select the fraction \(F^{*}\) in each epoch. We start from a tentative maximum fraction \(F\) at the beginning of the training process. We then carefully select the hidden samples from \(F\) based on their importance and then move the remaining samples back to the training set. That is, at each epoch a dynamic hiding fraction \(F^{*}\) is applied.

It is worth noting that the maximum fraction number \(F\) does not need to be strictly accurate in our design; it is a maximum ceiling and not the exact amount of samples that will be hidden. However, if the negative impact of hiding samples, i.e., becomes too high, it could
significantly affect the accuracy. For example, when a high maximum fraction \(F\) is set and/or when most of the samples have nearly the same absolute contribution to the update, e.g., at the latter epoch of the training process. We investigate how to choose the maximum hiding fraction in each epoch in Section 3.3.

**Moving Samples Back:** since the loss is computed in the forward pass, it is frequently used as the metric for the importance of the sample, i.e. samples with high loss contribute more to the update and are thus important [11; 22]. However, the samples with the smallest loss do not necessarily have the least impact (i.e., gradient norm) on the model, which is particularly true at the beginning of the training, and removing such high-impact samples may hurt accuracy. To mitigate the misselection of important samples as unimportant ones, we propose an additional rule to filter the low-loss samples based on the observation of historical prediction confidence [13]. The authors in [13] observed that some samples have a low frequency of toggling back from being classified correctly to incorrectly over the training process. Such samples can be pruned from the training set eternally. Because estimating the per-sample prediction confidence before training (i.e., offline) is compute-intensive, in this work, we perform an online estimation to decide whether an individual sample has a history of correct prediction with high confidence or not in a given epoch. Only samples that have low loss and sustain correct prediction with high confidence in the current epoch are hidden in the following epoch.

A sample is correctly predicted with high confidence at an epoch \(e\) if it is predicted correctly (**PA**) and the prediction confidence (**PC**) is no less than a threshold \(\tau\), which we call the _prediction confidence threshold_, at the previous epoch. In addition to the prediction confidence of a given sample (\(x\), \(y\)) is the probability that the model predicts this sample to map to label \(y\):

\[\begin{split} out=model(\mathbf{w}_{e},x,y)\\ PC=\max_{k}(\sigma(out_{k}))\end{split} \tag{3}\]

where \(\sigma\) is a sigmod (softmax) activation function. In this work, unless otherwise mentioned, we set the prediction confidence threshold to \(\tau=0.7\) as investigated in Section 4.3.

### Reducing the Number of Iterations in Batch Training: Learning Rate Adjustment

After hiding samples, KAKURENBO uses uniform without replacement sampling to train on the remaining samples from the training set. In this section, we examine issues related to convergence when reducing the number of samples and we provide insight into the desirable convergence properties of adaptively hiding examples.

Implicit bias in the SGD training process may lead to convergence problems [30]: when reducing the total number of iterations at fixed batch sizes, SGD selects minima with worse generalization. We examine the selection mechanism in SGD when reducing the number of iterations at a fixed batch size. For optimizations of the original datasets, i.e., without example hiding, we use loss functions of the form

\[f\left(\mathbf{w}\right)=\frac{1}{N}\sum_{n=1}^{N}\ell\left( \mathbf{w},\mathbf{x}_{n},\mathbf{y}_{n}\right)\,, \tag{4}\]

where \(\left\{\mathbf{x}_{n},\mathbf{y}_{n}\right\}_{n=1}^{N}\) is a dataset of \(N\) data example-label pairs and \(\ell\) is the loss function. We use SGD with batch of size \(B\) and learning-rate \(\eta\) with the update rule

\[\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\frac{1}{B}\sum_{n\in\mathcal{B}(k(t))} \nabla_{\mathbf{w}}\ell\left(\mathbf{w}_{t},\mathbf{x}_{n},\mathbf{y}_{n} \right)\,. \tag{5}\]

for without replacement sampling, \(B\) divisible by \(N\) (to simplify), and \(k\left(t\right)\) sampled uniformly from \(\left\{1,\dots,N/B\right\}\). When using an over-parameterized model as is the case with deep neural networks, we typically converge to a minimum \(\mathbf{w}^{*}\) that is a global minimum on all data points \(N\) in the training set [31; 14]. Following Hoffer et al. [32], linearizing the dynamics of Eq. 5 near \(\mathbf{w}^{*}\) (\(\forall n:\nabla_{\mathbf{w}}\ell\left(\mathbf{w}^{*},\mathbf{x}_{n},\mathbf{ y}_{n}\right)=0\)) gives

\[\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\frac{1}{B}\sum_{n\in\mathcal{B}(k(t))} \mathbf{H}_{n}\mathbf{w}_{t}\, \tag{6}\]
where we assume \(\mathbf{w}^{*}=0\) since the models we target are over-parameterized (i.e., deep networks) leading to converge to a minimum \(\mathbf{w}^{*}\). We also assume \(\mathbf{H}_{n}\triangleq\nabla_{\mathbf{w}}^{2}\ell\left(\mathbf{w},\mathbf{x}_ {n},\mathbf{y}_{n}\right)\) represents the per-example loss Hessian. SGD can select only certain minima from the many potential different global minima for the loss function of a given the full training set \(N\) (and without loss of generality, for the training dataset after hiding samples \(N-M\)). The selection of minima by SGD depends on the batch sizes and learning rate through the averaged Hessian over batch \(k\)

\[\left\langle\mathbf{H}\right\rangle_{k}\triangleq\frac{1}{B}\sum_{n\in\mathcal{ B}(k)}\mathbf{H}_{n}\]

and the maximum over the maximal eigenvalues of \(\left\{\left\langle\mathbf{H}\right\rangle_{k}\right\}_{k=1}^{N/B}\)

\[\lambda_{\max}=\max_{k\in[N/B]}\max_{\forall\mathbf{v}:\|\mathbf{v}\|=1} \mathbf{v}^{\top}\left\langle\mathbf{H}\right\rangle_{k}\mathbf{v}. \tag{7}\]

This \(\lambda_{\max}\) affects SGD through the Theorem proved by Hoffer et al. [32]: the iterates of SGD (Eq. 6) will converge if

\[\lambda_{\max}<\frac{2}{\eta}\]

The theorem implies that a high learning rate leads to convergence to be for global minima with low \(\lambda_{\max}\) and low variability of \(\mathbf{H}_{n}\). Since in this work we are fixing the batch size, we maintain \(\lambda_{\max}\), the variability of \(\left\langle\mathbf{H}\right\rangle_{k}\). Therefore, certain minima with high variability in \(\mathbf{H}_{n}\) will remain accessible to SGD. Now SGD may converge to these high variability minima, which were suggested to exhibit worse generalization performance than the original minima [33].

We mitigate this problem by reducing the delta by which the original learning rate decreases the learning rate (after the warm-up phase [34]). That way we make these new minima inaccessible again while keeping the original minima accessible. Specifically, KAKURENBO adjusts the learning rate at each epoch (or each iteration) \(e\) by the following rule:

\[\eta_{e}=\eta_{base,e}\times\frac{1}{1-F_{e}} \tag{8}\]

where \(\eta_{base,e}\) is the learning rate at epoch \(e\) in the non-hiding scenario and \(F_{e}\) is the hiding fraction at epoch \(e\). By multiplying the base learning rate with a fraction \(\frac{1}{1-F_{e}}\), KAKURENBO is independent of the learning rate scheduler of the baseline scenario and any other techniques related to the learning rate.

### Adjusting the Maximum Hidden Fraction \(F\)

Merely changing the learning rate may not be sufficient, when some minima with high variability and low variability will eventually have similar \(\lambda_{\max}\), so SGD will not be able to discriminate between these minima.

To account for this, we introduce a schedule to reduce the maximum hidden fraction. For the optimum of the set of hidden samples, \(\mathbf{w}_{\mathbf{M}}=G(\mathbf{x}_{n})\) and an overall loss function \(F(\cdot)\) that acts as a surrogate loss for problems which are sums of non-convex losses \(f_{i}(\mathbf{w})\), where each is individually non-convex in \(\mathbf{w}\). With Lipschitz continuous gradients with constant \(L_{i}\) we can assume

\[\|\nabla f_{i}(\mathbf{w}_{\mathbf{1}})-\nabla f_{i}(\mathbf{w}_{\mathbf{2}}) \|\leq L_{i}\|\mathbf{w}_{\mathbf{1}}-\mathbf{w}_{\mathbf{2}}\|\]

Since we are hiding samples when computing the overall loss function \(F(\cdot)\), we assume each of the functions \(f_{i}(.)\) shares the same minimum value \(\min_{\mathbf{w}}f_{i}(\mathbf{w})=\min_{\mathbf{w}}f_{j}(\mathbf{w})\ \forall\ i,j\). We extend the proof of the theorem on the guarantees for a linear rate of convergence for smooth functions with strong convexity [35] to the non-convex landscape obtained when training with hidden samples (proof in Appendix A)

**Lemma 1**.: _Let \(F(\mathbf{w})=\mathbb{E}[f_{i}(\mathbf{w})]\) be non-convex. Set \(\sigma^{2}=\mathbb{E}[\|\nabla f_{i}(\mathbf{w}_{\mathbf{M}})\|^{2}]\) with \(\mathbf{w}^{*}:=argminF(\mathbf{w})\). Suppose \(\eta\leq\frac{1}{\sup_{i}L_{i}}\). Let \(\Delta_{t}=\mathbf{w}_{\mathbf{t}}-\mathbf{w}\). After \(T\) iterations, SGD satisfies:_

\[\mathbb{E}\left[\|\Delta_{T}\|^{2}\right]\leq(1-2\eta\hat{C})^{T}\|\Delta_{0} \|^{2}+\eta R_{\sigma} \tag{9}\]

_where \(\hat{C}=\lambda(1-\eta\sup_{i}L_{i})\) and \(R_{\sigma}=\frac{\sigma^{2}}{\hat{C}}\)._
Since the losses \(f_{i}(\mathbf{w})\) are effectively dropping for individual samples, driven by the weight update, we thus drop the maximum fraction that can be hidden to satisfy Eq. 9. Specifically, we suggest selecting a reasonable number that is not too high at the first epoch, e.g, \(F=0.3\). We then adjust the maximum fraction per epoch (denoted as \(F_{e}\)) to achieve \(F_{e}\). We suggest using step scheduling, i.e., to reduce the maximum hiding fraction gradually with a factor of \(\alpha\) by the number of epochs increases. For example, we set \(\alpha\) as [1, 0.8, 0.6, 0.4] at epoch [0, 30, 60, 80] for ImageNet-1K and [0, 60, 120, 180] for CIFAR-100, respectively.

### Update Loss and Prediction

Our technique is inspired by an observation that the importance of each sample of the local data does not change abruptly across multiple SGD iterations [22]. We propose to reuse the loss and historical prediction confidence, computed during the training process, and only recompute those metrics for samples from the hidden list. Specifically, the loss and historical prediction confidence of samples are computed only one time at each epoch, i.e., when the samples are fed to the forward pass. It is not re-calculated at the end of each epoch based on the latest model. Therefore, only samples of the last training iteration of a given epoch have an up-to-date loss. Furthermore, if we re-calculate the loss of hidden samples, i.e., only skip the backward and weight update pass of these samples, the loss of hidden samples is also up-to-date. For instance, if we cut off 20% of samples, we have nearly 20% up-to-date losses and 80% of not-up-to-date losses at the end of each epoch As the result, in comparison to the baseline scenario, KAKURENBO helps to reduce the total backward and weight update time by a fraction of \(F_{e}\) while it does not require any extra forward time

## 4 Evaluation

We evaluate KAKURENBO using several models on various datasets. We measure the effectiveness of our proposed method on two large datasets. We use Resnet50 [36] and EfficientNet [37] on ImageNet-1K [19], and DeepCAM [4], a scientific image segmentation model with its accompanying dataset. To confirm the correctness of the baseline algorithms we also use WideResNet-28-10 on the CIFAR-100 dataset. Details of experiment settings and additional experiments such as ablation studies and robustness evaluation are reported in Appendix-B and Appendix-C. We compare the following training strategies:

* **Baseline**: We follow the original training regime and hyper-parameters suggested by their authors using uniform sampling without replacement.
* **Importance Sampling With Replacement**[11] **(ISWR)**: In each iteration, each sample is chosen with a probability proportional to its loss. The with-replacement strategy means that a sample may be selected several times during an epoch, and the total number of samples fed to the model is the same as the baseline implementation.
* **FORGET** is an online version of a pruning technique [13]: instead of fully training the model using the whole dataset before pruning, we train it for 20 epochs, and a fraction \(F\) of forgettable samples (i.e. samples that are always correctly classified) are pruned from the dataset1. The training then restarts from epoch \(0\). We report the total training time that includes the 20 epochs of training with the whole dataset, and the full training with the pruned dataset. Footnote 1: We choose the samples to remove by increasing number of forgetting events as in [13].
* **Selective Backprop (SB)**[17] prioritizes samples with high loss at each iteration. It performs the forward pass on the whole dataset, but only performs backpropagation on a subset of the dataset.
* **Grad-Match**[18] trains using a subset of the dataset. Every \(R\) epoch, a new subset is selected so that it would minimize the gradient matching error.
* **KAKURENBO**: our proposed method where samples are hidden dynamically during training.

It is worth noting that we follow the hyper-parameters reported in [38] for training ResNet-50, [39] for training WideResNet-28-10, [37] for training EfficientNet-b3, and [4] for DeepCAM. We show the detail of our hyper-parameters in Appendix B. We configure ISWR, and FORGET to remove the same fraction \(F\) as KAKURENBO. For SB, we use the \(\beta=1\) parameter that results in removing \(50\%\) of samples. Unless otherwise mentioned, our default setting for the maximum hidden fraction
\(F\) for KAKURENBO is \(30\%\), except for the CIFAR-100 small dataset, for which we use \(10\%\) (see below).

To maintain fairness in comparisons between KAKURENBO and other state-of-the-art methods, we use the same model and dataset with the same hyper-parameters. This would mean we are not capable of using state-of-the-art hyper-parameters tuning methods to improve the accuracy of ResNet-50/ImageNet (e.g., as in [40]). That is since the state-of-the-art hyper-parameters tuning methods are not applicable to some of the methods we compare with. Particularly, we can not apply GradMatch for training with a large batch size on multiple GPUs. Thus, we compare KAKURENBO with GradMatch using the setting reported in [18], i.e., CIFAR-100 dataset, ResNet-18 model.

### Accuracy

The progress in the top-1 test accuracy with a maximum hiding fraction of \(0.3\) is shown in Figure 2. Table 2 summarizes the final accuracy for each experiment. We present data on the small dataset of CIFAR-100 to confirm the correctness of our implementation of ISWR, FORGET, and SB. Table 3 reports the single GPU accuracy obtained with Grad-Match because it cannot work on distributed systems. For CIFAR-100, we report similar behavior as reported in the original work on ISWR [11], SB [17], FORGET [13], and Grad-Match [18]: ISWR, FORGET, and Grad-Match degrade accuracy by approximately 1%, while SB and KAKURENBO roughly perform as the baseline. KAKURENBO on CIFAR-100 only maintains the baseline accuracy for small fractions (e.g. \(F=0.1\)). When hiding a larger part of the dataset, the remaining training set becomes too scarce, and the model does not generalize well.

On the contrary, on large datasets such as ImageNet-1K, ISWR and KAKURENBO slightly improve accuracy (by \(0.2\)) in comparison to the baseline, while FORGET and SB degrade accuracy by \(1.2\%\) and \(3.5\%\), respectively. On DeepCAM, KAKURENBO does not affect the accuracy while ISWR degrades it by \(2.4\%\) in comparison to the baseline2. Table 4 reports the accuracy obtained for transfer learning. We do not report Grad-Match results because we could not apply it to this application. Using SB significantly degrades accuracy compared to the baseline, while ISWR, FORGET, and KAKURENBO maintains the same accuracy as the baseline. Especially, as reported in Figure 3, the testing accuracy obtained by KAKURENBO are varied when changing the maximum hiding fraction. We observe that for small hiding fractions, KAKURENBO achieves the same accuracy as

\begin{table}
\begin{tabular}{l|r r|r r|r r} \hline \hline \multirow{2}{*}{**Setting**} & \multicolumn{2}{c|}{**CIFAR-100**} & \multicolumn{3}{c}{**ImageNet-1K**} \\  & \multicolumn{2}{c|}{**WN-28-10**} & \multicolumn{2}{c|}{**ResNet-50**} & \multicolumn{2}{c|}{**EfficientNet-33**} & \multicolumn{2}{c}{**DeepCAM**} \\ \hline  & **Acc.** & **Diff.** & **Acc.** & **Diff.** & **Acc.** & **Diff.** & **Acc.** & **Diff.** \\ \hline Baseline & 77.49 & & 74.89 & & 76.63 & & 78.14 \\ \hline ISWR & 76.51 & (-0.98) & 74.91 & (+0.02) & N/A & & 75.75 & (-2.39) \\ \hline FORGET & 76.14 & (-1.35) & 73.70 & (-1.20) & N/A & N/A & \\ \hline SB & 77.03 & (-0.46) & 71.37 & (-3.52) & N/A & N/A & \\ \hline KAKURENBO & 77.21 & (-0.28) & 75.15 & (+0.26) & 76.23 & (-0.5) & 77.42 & (-0.9) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Max testing accuracy (Top-1) in percentage of KAKURENBO in the comparison with those of the Baseline and other SOTA methods. **Diff.** represent the gap to the Baseline.

\begin{table}
\begin{tabular}{l|r r} \hline \hline \multirow{2}{*}{**Setting**} & \multicolumn{2}{c}{**CIFAR-100**} \\  & \multicolumn{2}{c}{**ResNet-18**} \\ \hline  & \multicolumn{2}{c}{**Acc. Time (sec)**} \\ \hline Baseline & 77.98 & 856 \\ \hline Grad-Match-0.3 & \begin{tabular}{r} 76.87 \\ (-1.11) \\ \end{tabular} & \begin{tabular}{r} 8104 \\ (-5.3\%) \\ \end{tabular} \\ \hline KAKURENBO-0.3 & \begin{tabular}{r} 77.05 \\ (-0.93) \\ \end{tabular} & 
\begin{tabular}{r} 8784 \\ (+2.7\%) \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table}
Table 3: Comparison with Grad-Match in a single GPU (cutting fraction is set to \(0.3\).

Figure 2: Convergence and speedup of KAKURENBO and importance sampling (ISWR).
the baseline. When increasing hiding fractions, as expected, the degradation of the testing accuracy becomes more significant.

### Convergence Speedup and Training Time

Here we discuss KAKURENBO's impact on training time. Figure 2 reports test accuracy as the function of elapsed time (note the X-axis), and reports the training time to a target accuracy. Table 4 reports the upstream training time of DeiT-Tiny-224. The key observation of these experiments is that KAKURENBO reduces the training time of Wide-ResNet by \(21.7\%\), of ResNet-50 by \(23\%\), of EfficientNet by \(13.7\%\), of DeepCAM by \(22.4\%\), and of DeiT-Tiny by \(15.1\%\) in comparison to the baseline training regime.

Surprisingly, Importance Sampling With Replacement (ISWR) [11] introduces an overhead of \(34.8\%\) on WideNet, of \(41\%\) on ImageNet-1K and offers only a slight improvement of \(2.5\%\) on DeepCAM. At each epoch, ISWR processes the same number of samples as the baseline. Yet, it imposes an additional overhead of keeping track of the importance (i.e., the loss) of all input samples. While on DeepCAM it achieves a modest speedup due to its faster convergence, these experiments reveal that ISWR's behavior is widely different on large datasets than on the smaller ones previously reported [11; 17].

FORGET increases the training time of WideResNet by \(46.1\%\) because of the additional 20 epochs training on the whole dataset needed for pruning the samples. When the number of epoch is large, such as for ResNet50 that runs for 600 epochs, FORGET decreases the training time by \(17.9\%\), and for DeiT by \(14.4\%\). However, this reduction of training time comes at the cost of degradation of the test accuracy. On WideResNet and ResNet, SB performs similarly to KAKURENBO by reducing the training time without altering the accuracy. However, SB significantly degrades accuracy compared to the baseline for ImageNet and DeiT.

It is worth noting that KAKURENBO has computation overheads for updating the loss and prediction (Step D in Figure 1), and sorting the samples based on the loss (Step A in Figure 1). For example, Figure 4 reports the measured speedup per epoch as compared to the baseline epoch duration. The speedup follows the same trend as the hiding rate. This is because reducing the number of samples in the training set impacts the speed of the training. The measured speedup does not reach the maximum hiding rate because of the computation overhead. The performance gain from hiding samples will be limited if the maximum hiding fraction \(F\) is small, or potentially less than the overhead to compute the importance score of samples. In experiments using multiple GPUs, those operations are performed in parallel to reduce the running time overhead. When using a single GPU on CIFAR-100 with ResNet-18 (Table 3), the computational overhead is bigger than the speedup gained from hiding

\begin{table}
\begin{tabular}{l|l|l|r r r r r} \hline \hline  & Dataset & Metrics & Baseline & ISWR & FORGET & SB & KAKUR. \\ \hline Up & \multirow{2}{*}{Fractal-3K} & Loss & 3.26 & 3.671 & 3.27 & 4.18 & 3.59 \\ stream & & Time (min) & 623 & 719 & 533 & 414 & 529 \\  & & Impr. & - & (+15.4\%) & (-14.4\%) & (-33.5\%) & (-15.1\%) \\ \hline Down & \multirow{2}{*}{CIFAR-10} & Acc. (\%) & 95.03 & 95.79 & 95.85 & 93.59 & 95.28 \\ stream & & Diff. & - & (+0.76) & (+0.82) & (-1.44) & (+0.25) \\ \cline{2-7}  & \multirow{2}{*}{CIFAR-100} & Acc. (\%) & 79.69 & 79.62 & 79.95 & 76.98 & 79.35 \\  & & Diff. & - & (-0.07) & (+0.26) & (-2.71) & (-0.34) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Impact of KAKURENBO in transfer learning with DeiT-Tiny-224 model.

Figure 3: Test accuracy vs. epoch of KAKURENBO with different maximum hiding fractions \(F\).
samples. Thus, KAKURENBO takes more training time in this case. In short, KAKURENBO is optimized for large-scale training and provides more benefits when running on multiple GPUs.

### Ablation Studies

**Impact of prediction confidence threshold \(\tau\).** Higher prediction confidence threshold \(\tau\) leads to a higher number of samples being moved back to the training set, i.e., fewer hidden samples at the beginning of the training process. At the end of the training process, when the model has is well-trained, more samples are predicted correctly with high confidence. Thus the impact of the prediction confidence threshold on the number of moved-back samples becomes less (as shown in Figure 4). The result in Table 5 shows that when we increase the threshold \(\tau\), we obtain better accuracy (fewer hidden samples), but at the cost of smaller performance gain. We suggest to set \(\tau=0.7\) in all the experiments as a good trade-off between training time and accuracy.

**Impact of different components of KAKURENBO.** We evaluate how KAKURENBO's individual internal strategies, and their combination, affect the testing accuracy of a neural network. Table 6 reports the results we obtained when training ResNet-50 on ImageNet-1K3 with a maximum hiding fraction of \(40\%\). The results show that when only HE (Hiding Examples) of the \(40\%\) lowest loss samples is performed, accuracy slightly degrades. Combining HE with other strategies, namely MB (Move-Back), RF (Reducing Fraction), and LR (Learning Rate adjustment) gradually improves testing accuracy. In particular, all combinations with RF achieve higher accuracy than the ones without it. For example, the accuracy of v110 is higher than that of v1100 by about \(0.59\%\). We also observe that using LR helps to improve the training accuracy by a significant amount, i.e., from \(0.46\)% to \(0.83\)%. The MB strategy also improves accuracy. For example, the accuracy of v1010 is \(72.81\%\), compared to v1110 which is \(72.96\%\). This small impact of MB on the accuracy is due to moving back samples at the beginning of the training, as seen in Appendix C.3. By using all the strategies, KAKURENBO achieves the best accuracy of \(73.6\%\), which is very close to the baseline of \(73.68\%\).

Footnote 3: We use the ResNet-50 (A) configuration in this evaluation as shown in Appendix-B

## 5 Conclusion

We have proposed KAKURENBO, a mechanism that adaptively hides samples during the training of deep neural networks. It assesses the importance of samples and temporarily removes the ones that would have little effect on the SGD convergence. This reduces the number of samples to process at each epoch without degrading the prediction accuracy. KAKURENBO combines the knowledge of historical prediction confidence with loss and moves back samples to the training set when necessary. It also dynamically adapts the learning rate in order to maintain the convergence pace. We have demonstrated that this approach reduces the training time without significantly degrading the accuracy on large datasets.

\begin{table}
\begin{tabular}{l|c c c c|c} \hline \hline  & \multicolumn{4}{c|}{**Component**} & \multicolumn{1}{c}{**Accuracy**} \\  & HE & MB & RF & LR & \\ \hline Baseline & \(\times\) & \(\times\) & \(\times\) & \(\times\) & 73.68 \\ \hline v1000 & ✓ & \(\times\) & \(\times\) & \(\times\) & 72.25 (-1.8\%) \\ v1001 & ✓ & \(\times\) & \(\times\) & ✓ & 73.08 (-0.7\%) \\ v1010 & ✓ & \(\times\) & ✓ & \(\times\) & 72.81 (-1.1\%) \\ v1011 & ✓ & \(\times\) & ✓ & ✓ & 73.27 (-0.4\%) \\ v1100 & ✓ & ✓ & \(\times\) & \(\times\) & 72.37 (-1.7\%) \\ v1101 & ✓ & ✓ & \(\times\) & ✓ & 73.09 (-0.7\%) \\ v1110 & ✓ & ✓ & ✓ & \(\times\) & 72.96 (-0.9\%) \\ KAKUR. (v1111) & ✓ & ✓ & ✓ & ✓ & 73.6 \\ \hline \hline \end{tabular}
\end{table}
Table 6: The impact of different components of KAKURENBO on testing accuracy including **HE**: Hiding \(F\)% lowest-loss examples, **MB**: Moving Back, **RF**: Reducing the Fraction by epoch, **LR**: Adjusting Learning Rate. Numbers inside the (.) indicate the gap in percentage compared to the full version of KAKURENBO.

Figure 4: Reduction of hiding fraction, per epoch, and the resulting speedup.
Acknowledgments

This work was supported by JSPS KAKENHI under Grant Numbers JP21K17751 and JP22H03600. This paper is based on results obtained from a project, JPNP20006, commissioned by the New Energy and Industrial Technology Development Organization (NEDO). This work was supported by MEXT as "Feasibility studies for the next-generation computing infrastructure" and JST PRESTO Grant Number JPMJPR20MA.

We thank Rio Yokota and Hirokatsu Kataoka for their support on the Fractal-3K dataset.
