InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning

Q3: Did the authors experiment with a pruning probability that depends on the sample score? A3: Thanks for the question. To improve data efficiency, we use the percentile method to prune part of the data (20%) with a more aggressive ratio r (0.75) as the default setting on several datasets, as claimed in section 3.1.

By doing so, a higher pruning ratio can be achieved without performance loss. In Table 6 with this improvement, CIFAR-100 ResNet-50 can achieve 41.3% saving ratio, compared to 33% in Table 5 with uniform r.

A theoretical related analysis is in Appendix B.3 (updated revision B.4), suggesting that $\mathbb{E}\_\text{rescaled}[G\_{z}^2/(1-\mathcal{P}\_t(z))]\leq {\mathbb{E}}\_{\mathcal{D}}[G_z^2]$ could be a condition for healthy rescaling. This indicates that we can prune and rescale more aggressively for samples with low loss (gradients).

To better illustrate the effect of using different pruning probabilities depending on the sample score, we verified different combinations as follows:

Setting: InfoBatch on CIFAR-100 ResNet-50 with different thresholding method. All results are averaged across three runs with std reported. We report their acc and pruning ratio here.

Analysis:

• Adaptive r with [0%,20%):0.75,[20%,85%):0.5 gets the 41.3% saving ratio with lossless performance.
• Adaptive r depending on the score could require a corresponding parameter search.
• Moving thresholds rightward would cause degraded performance.

Conclusions:

• A pruning probability depends on sample score could further improve data efficiency.
• It is not straightforward to find a better adaptive r with manually tuning

Future work: To easily find adaptive r values, we plan to propose a cheap estimator for gradient G and try setting adaptive r based on it ensuring $\mathbb{E}\_\text{rescaled}[G\_{z}^2/(1-\mathcal{P}\_t(z))]\leq {\mathbb{E}}\_{\mathcal{D}}[G_z^2]$.

Q4: Summarize 2.3 and increase the figures.

A4: Thanks for the comments. We shortened the 2.3 and rearranged the layout to enlarge the figures (in the updated revision). The corresponding change is as follows:

• Sec 1, we enlarge Fig 1 and move it to the top of the page.
• Sec 2.3, we shorten the Theoretical analysis and move part of the proof to B.1.
• Sec 3, we put the previous Fig 3 and Fig 4 together to the top, making them no longer surrounded by text.
• Sec 3.5, we increase the size of Table 8 and Table 9.

Q5: Overhead acceleration not significant compared to current dynamic pruning with sort

A5: Thanks for the question. Sort is O(NlogN) for full data and amortized O(logN) for each sample, ours is O(N) and amortized O(1). We design the operation considering it could differ in a large factor when N is very big, as shown in Appendix D table 11.

The overhead saving of operation compared to UCB is 10 times (0.03h to 0.0028h) on ImageNet-1K; however we agree it is not a significant improvement compared to training time saving (17.5h->10h). Our main saving comes from saving the forward and backward computation, which is shown in the table below:

Setting: ResNet-50 on CIFAR-100. All results are averaged across three runs with std reported. We report their acc and pruning ratio here.

Analysis:

• At lossless performance of ResNet-50 on CIFAR-100, InfoBatch can save 41% cost compared to 20% of UCB. The saved time is a 100% (800s->1600s) improvement.
• At the same saving ratio, UCB has a much higher performance degradation

We degraded the claim of the part on time complexity, which can be visible in the new revision. The main modifications can be summarized as:

1. in section 4 related works, we change "which could be a non-negligible overhead" -> "which could be an overhead"

We sincerely thank the reviewer DemB for the careful review and valuable comments/questions. For the concerns and questions, we make responses as follows.

Q1: Idea similar to other dynamic pruning approaches, not providing a different point of view in the matter.

A1: Thanks for the comment. In section 1 paragraph 5, we stated:

• "Directly pruning data may lead to a biased gradient estimation as illustrated in Fig. 1a, which affects the convergence result. This is a crucial factor that limits their performance, especially under a high pruning ratio (corresponding results in Tab. 1)"

To better illustrate the difference, we show a table here for comprehensive analysis:

Analysis:

• Previous methods don't use soft pruning. It could lead to a biased gradient direction (see Appendix B.1, or B.2 in the updated revision).
• Previous methods don't use rescaling. This leads to a lack in total update, which is more severe at a higher pruning ratio.
• Previous methods don't use annealing. Therefore a remaining bias could be left (Appendix B.2 or updated revision B.3 further discussed annealing).
• Previous methods mainly focus on classification. InfoBatch can be applied to a broader range of tasks.

Conclusion: InfoBatch proposes a probabilistic framework aiming to achieve unbiased dynamic pruning (with soft pruning, rescaling, and annealing), which differs from other dynamic pruning works that propose metrics and use sort to select more important samples.

Q2: Ablation of threshold selection.

A2: Thanks for the comment. We conduct these ablations on CIFAR-100 ResNet-50 as follows:

Setting: All results are averaged across three runs with std reported. We report their acc and pruning ratio here.

Analysis:

• mean + c*std as a threshold with c>0 can achieve a higher saving ratio but with degraded performance.
• percentile threshold selection can also lead to a reasonable performance.
• Specifically, the <75% threshold gets a similar saving ratio and performance as using mean.
• <85% threshold achieves both higher saving ratio and performance than mean+0.5*std

Discussions:

• According to the inference in 2.3, the unbiasedness doesn't depend on the threshold selection. The experiment result matches the theoretical analysis as using the 75 percentile threshold also gives a lossless result.
• std factor is not preferred, properly because entropy loss is not Gaussian and long-tailed at convergence (we add a visualization in revised Appendix E.1).
• if assuming Gaussian distribution for some other metrics behind loss, percentile of loss can do the same thing as using means + c*std.

Conclusion: InfoBatch is robust to different threshold selection methods. Empirically, the std factor is not preferred for loss. Percentile thresholds could also be a choice.

Thank you for the advice. We agree that ethical issue should be studied with care and not overstated. We would evaluate the ethical issue carefully with extended experiments in final revision. We add a disclaimer in limitations (in the updated revision), claiming the potential bias should be considered when applying this research:

• In Section 5 limitations, we add "Removing samples may cause bias in model predictions. It is advisable to consider this limitation when applying InfoBatch to ethically sensitive datasets."

We are welcome to further discussions if there are further questions.

Q10: How to set r and $\delta$ on a new dataset/architecture?

A10: Thanks for the good question.

We consider the r value in the future work (see it in Appendix B.4), we plan to use $\mathbb{E}\_\text{rescaled}[G\_{z}^2/(1-\mathcal{P}\_t(z))]\leq {\mathbb{E}}\_{\mathcal{D}}[G_z^2]$ to find near-optimal r. We theoretically analyze the reasonableness of choosing r according to this equation.

• Our proposed procedure is to measure the $\mathop{\mathbb{E}}_{\mathcal{D}}[G_z^2]$ (or some cheaper indicator values instead) after warmup, then use the statistics to quickly select near optimal r values.

For delta, our default value 0.875 is actually corresponding to the annealing stage of the one cycle scheduler we used for the learning rate schedule. It corresponds to a drop in loss during normal training. In general, it is the last 17.85% of a cosine annealing. As cosine annealing is prominent in many tasks, we suggest last 0.1785 fraction of cosine annealing could be used as default.

Q4: Add a full data baseline with reduced epochs and adjusted learning rate. A4: Thanks for the question. Here we add the tuned learning rate baseline with reduced epoch numbers.

Analysis

• InfoBatch outperforms the tuned baseline. This is properly because higher loss samples are more sensitive to learning rate scaling as discussed in Appendix B.3.
• Based on that, when scaling the learning rate to match the original training progress, scaling lower loss samples is still preferred than higher loss samples.

Conclusions:

• With the same computation, InfoBatch has higher performance than the tuned baseline.
• According to the table and the point above, the improvement of InfoBatch is not caused by a lack of tuning of the benchmark.

Q5: Purpose of 2.3

A5: Thanks for the question. Previously, considering the different backgrounds of reviewers, we wrote 2.3 with more detailed steps. We summarize it to make it brief (in the updated revision), the changes are as follows:

• We merge previous Eqn. (6) and (7) to revised Eqn. (6), and move the middle step to B.1.
• We merge previous Eqn. (8) and (9) to revised Eqn. (7).

Q6: "Info" and "lossless" in the title

A6: Thanks for the comment.

• We call our method "InfoBatch" because it takes advantage of the current learning status (loss) to do selective data pruning. It is "informative" instead of purely random.
• We achieve lossless results on many tasks with substantial savings, which is an important milestone. It is true InfoBatch cannot guarantee a lossless result in all settings, but the empirical hyperparameters have already achieve lossless results on image classification, semantic segmentation, image generation, and language model finetuning.

We are welcome to further discussion on this problem during the author reviewer discussion period.

Q7: What fraction of the data are soft-pruned throughout training?

A7: Thanks for the question. We plot the saving fraction curve of InfoBatch in CIFAR-10 ResNet-50 training in revised Appendix E.1 Fig.6.

For entropy loss, InfoBatch (mean) usually starts with a relatively lower ratio, and then the ratio keeps increasing till the end. This is probably because maximizing log probability tends to converge to a long-tailed loss distribution.

We show the loss distribution visualization during training in revised Appendix E.1 Fig.7. We can see the loss distribution is initially right-skewed and finally left-skewed.

We sincerely thank the review 8u8Q for the meticulous review and responsible attitude. We fix those typos in the revised PDF, thank you.

For the concerns and questions, here are our responses:

Q1: Are rescaling and annealing all the key points of InfoBatch?

A1: Thanks for the question. This is partially right. Only with soft (probabilistic) pruning, recaling can take effect with no bias. Rescaling for hard pruning would harm the performance. Annealing can be used in all settings, which helps to achieve lossless performance when rescaling is unbiased. To verify this, we conduct the following experiment on CIFAR-100 ResNet-50.

Note: training on the whole dataset achieves 80.6% acc.

Conclusion: Soft pruning is important to unbiased rescaling and achieving lossless results.

This question is not fully answered yet at this point. The further insight of InfoBatch's sample selection is discussed in answer A2 and A3.

Q2: (Generalization) Results for other dynamic baselines with annealing and rescaling A2: Thanks for the question. The random in Table 5 (CIFAR-100 ResNet-50) is the random* with annealing and rescaling. Its result is improved as expected over table 4, since random* is also a kind of soft pruning.

However on UCB which uses (sort and) hard pruning, the thing is different. The rescaling can only be applied to all remaining samples which are all higher score samples, being statistically different from pruned samples. We show the corresponding experimental results here:

Setting: Train ResNet-50 on CIFAR-100 using UCB and random*. We report their acc and pruning ratio here.

Analysis:

• UCB's performance is increased by annealing using the same saving ratio (by controlling the pruning fraction), but much lower than InfoBatch
• Rescaling with annealing improves the performance of random* using the same saving ratio; but adding rescaling leads to degraded performance of UCB

Conclusion: Annealing could help to improve performance on a broader range of sample selection methods, but rescaling can only take effect if it is using soft pruning.

Q3: Point beyond soft pruning, rescaling, and annealing

A3: Thanks for the comment.

It is possible to use different (static or dynamic) thresholds with different pruning ratios

• According to the proof in Section 2.3, the expectation rescale equation would hold independent of the threshold selection and probability.

It is possible to use a more aggressive ratio r on lower score (gradient) samples.

• According to Appendix B.3 (B.4 in revised version), $\mathop{\mathbb{E}}\_{rescaled}[G\_{z}^2/(1-\mathcal{P}\_t(z))]\leq \mathop{\mathbb{E}}\_{\mathcal{D}}[G_z^2]$ could potentially lead to health rescaling.
• We use the percentile method to prune part of the data (20%) with a more aggressive ratio r (0.75) as the default setting as claimed in 3.1. This leads to a higher pruning ratio without performance loss. In Table 6 with this improvement, CIFAR-100 ResNet-50 can achieve 41.3% saving ratio, compared to 33% in Table 5 using uniform r.

Summarization:

• Rescaling (w/ soft pruning) and annealing are our contributions which do generalize to difference threshold selection
• We further explore better data efficiency with better utilization of scores from both theoretical and experimental aspects.

Dear Reviewer 8u8Q,

Thanks for acknowledging our work. We agree with the advice, and we are running the corresponding experiments to report the observations (how much does loss-guided pruning differ from random pruning in performance under our framework) as follows:

1. With various architectures, we plan to evaluate the performance on CIFAR-10 with random/loss-guided pruning + rescaling + annealing at default saving ratio

Note: * denotes running experiment waiting for the result. We will keep updating the results till the end of the reviewer-author discussion period. We will discuss these results in the revision.

2. On various datasets, we plan to evaluate the performance with ResNet-50 at default saving ratio

Note: * denotes running experiment waiting for the result. We will keep updating the results till the end of the reviewer-author discussion period. We will discuss these results in the revision.

3. For higher saving ratios, we plan to evaluate the corresponding performance on CIFAR-10 ResNet-18 (using the aforementioned quantile method to control the ratio for loss-guided pruning)

Note: * denotes running experiment waiting for the result. We will keep updating the results till the end of the reviewer-author discussion period. We will discuss these results in the revision.

Once again, we appreciate the insightful and constructive comments on our work. We will be glad to improve our work if there is any following advice. Thanks again for your comments and time.

We sincerely thank the reviewer Nce2 for pointing out the missing references as well as a potential improvement. We make responses as follows.

Q1: Add missing references.

A1: Thanks for the advice. We update the section 1 and 4 to add those references(see the revision). The main changes are:

• Sec 1, paragraph 2: add reference " Park et al., 2022; Xia et al., 2023; Zheng et al., 2023"
• Sec 4, paragraph 1: add "AL (Park et al., 2022) propose to use active learning methods to select a coreset. Moderate (Xia et al., 2023) proposed to use the median of different scores as a less heuristic metric. Coverage-centric Coreset Selection (Zheng et al.,2023) additionally considers distribution coverage beyond sample importance. "
• Sec 4, paragraph 2: add "Mindermann et al. (2022) propose Reducible Holdout Loss Selection which prioritizes samples neither too easy nor too hard. It emphasizes training learnable samples."

Q2: How to illustrate the gradient trajectory with landscape in Fig 1? Is it an illustration or a real plot on some dataset?

A2: Thanks for the question. Fig 1 is an illustration instead of a real plot. To avoid misunderstanding, we modify the caption "visualiztion" -> "illustration". The corresponding accuracy values are from Table 1 CIFAR100 experiment, comparing InfoBatch and EL2N-2 at 50% pruning ratio.

Improvement Plan: We notice that there could be a potential improvement of this illustration using the method proposed in [1]. It would express the same idea but with a more accurate visualization. We found in [2] Fig 1 they show the gradient sketch on such a loss landscape. We are welcome to further discussion on this in the auther reviewer discussion period (whether change our Fig 1 like that).

[1] Li, Hao, et al. "Visualizing the loss landscape of neural nets." Advances in neural information processing systems 31 (2018). [2] Liu, Zhuang, et al. "Dropout Reduces Underfitting." arXiv preprint arXiv:2303.01500 (2023).

Q3: Which dataset is used for Table 4?

A3: Thanks for the comment. In section 3.4 first paragraph, we claim: if not stated, the experiments are conducted on CIFAR-100 by default. Table 4 is conducted on CIFAR100 as default dataset for ablation. We update its caption to make it more clear in the updated revision.

Q5: Further clarification of how annealing contributes to stabilization

A5: Thanks for the question. We found Table 4 with a low number of precision digits is hard to illustrate this point clearly. We draw a plot in the revised E.2 Fig.8. All experiments use the same saving ratio.

Analysis: In this plot, compared to only rescaling, adding annealing leads to an increased mean performance and slightly reduced performance variance.

Conclusion: This plot indicates how annealing helps stabilize the training.

Q6: Necessity of using loss value A6: Thanks for the comment.

By reasonably utilizing loss, we can further improve data efficiency, based on the inference in Appendix B.3 (revised version B.4).

Noted that in Table 5 (CIFAR-100 R-50), the lossless pruning ratio using mean is 33%. In Section 3.1 experiment details we claim to use a more aggressive pruning probability r(0.75) for smaller loss samples (lowest 20%) on CIFAR-100; that leads to a 41.3% saving ratio in Table 6.

We conduct the following experiment to elaborate:

Setting: InfoBatch on CIFAR-100 ResNet-50 with increased r for certain samples. All results are averaged across three runs with std reported. We report their acc and pruning ratio here.

Analysis:

• Using a higher pruning ratio r for higher loss samples significantly degrades performance.
• A related discussion is in Appendix B.3 (revised version B.4) about why lower-loss samples are preferred. $\mathbb{E}\_\text{rescaled}[G\_{z}^2/(1-\mathcal{P}\_t(z))]\leq {\mathbb{E}}\_{\mathcal{D}}[G_z^2]$ could be the condition for a healthy rescaling.
• Compared to random selection, there is almost no overhead to use loss, as it can be obtained with no extra cost.

Conclusions:

• Loss is preferred, especially when using an adaptive high pruning ratio which further improves data efficiency.
• The overhead of loss is negligible, so its improvement is of almost no cost and thus also preferred in settings without adaptive high pruning ratio.

Q7: How many random seeds are used throughout the experiments

A7: Thanks for the question. For CIFAR-10/100 experiments, we measured at least 3 trials for those values with std.

We sincerely thank the reviewer nCAL for the valuable questions and comments. For the concerns and questions, here are our responses:

Q1: Overhead cost saving over UCB seems negligible compared to training

A1: Thanks for the question. Sort is O(NlogN) for full data and amortized O(logN) for each sample, ours is O(N) and amortized O(1). We design the operation considering it could differ by a large factor when N is very big.

This overhead saving of operation compared to UCB is 10 times (0.03h to 0.0028h) on ImageNet-1K; however we agree it is not a significant improvement compared to training time saving (17.5h->10h). Our main saving comes from saving the forward and backward computation, which is shown in the table below:

Setting: ResNet-50 on CIFAR-100. All results are averaged across three runs with std reported. We report their acc and pruning ratio here.

Analysis:

• At lossless performance, InfoBatch can save 41% compared to 20% of UCB. The saved time is a 100% improvement.
• At the same saving ratio, UCB has a much higher performance degradation

We degraded the claim of the part on time complexity, which can be visible in the new revision. The main modifications can be summarized as:

1. in section 4 related works, we change "which could be a non-negligible overhead" -> "which could be an overhead"

Q2: How was the overall saved cost calculated in Tables 6 and 7

A2: Thanks for the question. As the overhead is negligible compared to training, we measured wall clock time and found the sample iteration saving is basically the same as wall clock saving. So the overall saved cost is both wall clock time and sample iteration.

Q3: Is annealing taken into account for saving?

A3: Thanks for the question. The answer is yes. Our time = overhead + pruned training time + annealing training time. For table 1, InfoBatch saves slightly more cost than reported, with annealing already taken into account.

Q4: Using full dataset at warmup

A4: Thanks for the question. Only in the experiment of Timm Swin-Tiny training, we warmup with the full dataset for 5 epochs to avoid training instability.

On other tasks,the initial pruning ratio is lower, which serves as a pruning warmup for CNN-based experiments. A fraction is visualized in revised Appendix E.1 Fig.6. It is properly due to early stage loss distribution is right-skewed and later left-skewed, which is visualized in revised Appendix E.1 Fig.7. ViT-based networks seem more sensitive to this warmup stage than CNN-based ones.

Thank you for pointing it out, we make the following modification to make it more clear:

• In sec A.3 paragraph 2, add "We also warmup InfoBatch for 5 epochs, only recording scores without pruning."

Dear reviewer nCAL:

Thanks so much again for the time and effort in our work. According to the comments and concerns, we conduct the corresponding experiments and further discuss the related points. Besides, we have revised our claim of overhead compared to dynamic methods. We also provided visualization plots in Appendix E.1 to further illustrate how annealing contributes to stabilization.

As the discussion period is nearing its end, please feel free to let us know if there are any other concerns. Thanks again for your time and efforts.