Learn from the Past: Dynamic Data Pruning with Historically Weighted Bernoulli Sampling

We thank the reviewer for the feedback.

The paper lacks novelty and originality. The optimal sampling distribution has already been derived more rigorously and investigated more deeply in previous works for various settings. Some relevant earlier references are listed below, and there have been additional developments since then.

We thank the reviewer for pointing us to these sources.

The main contribution of this paper is to model the problem of data selection as finding the optimal sampling distribution and making it practical through adaptations, rather than simply deriving the optimal distribution itself.

For the two papers you mentioned, they focus on the general problem of estimation through sampling. Their experiments focus on a one time static estimation where the statistics are available. In contrast, dynamic data selection has the following two prominent features:

1. Multi-turn selection: Dynamic data selection resamples data for every epoch instead of a simple one time selection.
2. Unavailability (Cost) of statistics: The cost of directly computing the gradients defeat the purpose of data selection.

The second feature is one of the main challenges for dynamic data selection. In [1], they use an approximate gradient from the current epoch with a mechanism to estimate if the cost is worth it. For [2][3], they rely on stale information from previous samplings. In [2], they use the ranking of loss to decide the sampling probability, while [3] shows that a simple thresholding mechanism can also work.

We argue that our novelty over these state-of-the-art methods lies in two parts. First, the awareness for the use of the optimal sampling distribution rather than some heuristics. Second, there is effort from us to make the method practical. As we can see from Table 5, without EMA, using stale information for the optimal sampling distribution actually does not have much improvement over Infobatch [2], a simple thresholding mechanism, while removing probability smoothing will make the performance a lot worse.

[1] Katharopoulos, A., & Fleuret, F. (2018, July). Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning (pp. 2525-2534). PMLR.

[2] Jiang, A. H., Wong, D. L. K., Zhou, G., Andersen, D. G., Dean, J., Ganger, G. R., ... & Pillai, P. (2019). Accelerating deep learning by focusing on the biggest losers. arXiv preprint arXiv:1910.00762.

[3] Qin, Z., Wang, K., Zheng, Z., Gu, J., Peng, X., Zhou, D., ... & You, Y. InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning. In The Twelfth International Conference on Learning Representations.

The statement "in practice we can keep sampling until a fixed batch size is reached" is scientifically incorrect. Doing so changes the distribution of the selected samples, rendering all theoretical results invalid.

We are sorry for the ambiguity of the sentence and we have revised it in the paper. As mentioned in Sec 3.3, what we really mean by that statement is the following: Yes, they are theoretically different. However, in practice we observe their performance to be similar as shown in the following table, where we compare the version of Omission with/without fixed batch size:

As mentioned in the paper, a huge part of this work is to make the optimal distribution “inspired” sampling practical. In the process, there are many approximations being made without affecting the convergence such as using the approximated gradient and the EMA on stale information. This is yet another approximation to make our method more useful. Specifically, this makes the method easier to use (the sampling logic can be more separated in code), while also being slightly faster due to the use of a fixed batch size.

We have revised Sec 3.3 to make it more clear in the paper.

We thank the reviewer for the positive feedback!

Section 3.2.1 EXPONENTIAL MOVING AVERAGE OF GRADIENT NORM SQUARED is not clearly written. This reviewer has difficulty seeing the value of this subsubsection. It should be better motivated.

The motivation of this section is that to avoid the cost for data selection one has to use historical data. However, historical data can be noisy and largely varying in scale. Thus, unlike [1][2], which simply uses the data from the last sampling, we propose to use the exponential moving average on the squared gradient norm with scale normalization.

We have revised Sec 3.2.1 to make it clearer.

[1] Jiang, A. H., Wong, D. L. K., Zhou, G., Andersen, D. G., Dean, J., Ganger, G. R., ... & Pillai, P. (2019). Accelerating deep learning by focusing on the biggest losers. arXiv preprint arXiv:1910.00762.

[2] Qin, Z., Wang, K., Zheng, Z., Gu, J., Peng, X., Zhou, D., ... & You, Y. InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning. In The Twelfth International Conference on Learning Representations.

In theorem 1 and 2, the determination of p_i requires ||g_i||, for all i=1,\ldots, n (or B), which may not be realistic. It seems that this will be the limitation of the proposed approach. The authors tend to address it in the paper. However, there doesn't seem to be a convincing solution. If one can't compute ||g_i|| for all observations (samples), then the proposed method doesn't seem sensible. Nevertheless, I am unsure how we should consider this in our evaluation…

Yes, this is one of the challenges we aim to solve in the paper. To make it practical, we use the historical data with an exponential moving average to avoid the computational cost. Additionally, the adoption of probability smoothing not only ensures biasedness, but also ensures that everyone is being sampled with some frequency so that the historical data will not be too out-dated.

Thanks for the positive feedback!

The observed performance gains of Omission, which are not always significantly large with respect to the error bars, may be induced by the randomness of trials. Would the empirical performance gains of Omission remain stable when the number of trials is increased?

Yes, the performance gains of Omission remain stable when the number of trials is increased.

We show the result of 12 trials in the following table.

Why is the performance of full training not provided for the experiments reported in Table 4? And what is the pruning ratio used in these experiments?

Thank you for the suggestion.

It is worth noticing that full training is the same as the baseline (“Reducing Epoch”, which does not employ any data selection) but simply with a different number of training steps.

For Cifar10 and Cifar100, people usually define full training as 100 epochs. However, for the experiment in Table 4, there is no such an establishment.

Instead, we select the training steps that are the best for the baseline (250 steps) and also use it for Infobatch and Omission for comparison. As we can see from the following table, increasing the number of training steps actually degrades the baseline performance.

We rename the “Reducing Epoch” in Table 4 to “No Data Selection” to improve clarity. Thanks again for the suggestion.

As for the sampling ratio, we follow Infobatch [1] and set it to 50%, which chooses 50% of the samples for each pass of the training set.

[1] Qin, Z., Wang, K., Zheng, Z., Gu, J., Peng, X., Zhou, D., ... & You, Y. InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning. In The Twelfth International Conference on Learning Representations.

Dear AC,

We are in the middle of writing the rebuttal response. Experiments on LLM is slightly time consuming due to our limited resources. Thanks for your patience!

Sincerely yours, Submission8998 Authors