Efficient Backpropagation with Variance Controlled Adaptive Sampling

We‘d like to thank the reviewer for acknowledging the effectiveness of our work and for the constructive criticism. Below we address reviewer's concerns:

Q1. Limited literature review on sparsity-based training methods

Thanks for pointing out relevant works on sparse training. However, we'd like to place our work on another closely related field of online batch selection that discards less informative data, but not prunes weights or neurons as is typical in sparse training. The main difference comes in two ways:

• Wall-clock time reduction: Online batch selection methods can always translate FLOPs reduction into time reduction since they neatly wipe the entire datum out. While few sparse training works report time reduction usually for the lack of supportive hardware, especially for unstructured sparsity.
• Biasedness: In online batch selection, importance sampling is usually adopted which assures unbiasedness. While in sparse training, pruning methods typically cannot guarantee unbiased gradients. Using unbiased gradients for SGD is critical for the algorithm to converge properly.

Moreover, sparse training and online batching selection should be orthogonal since they reduce computation along different dimensions (data vs. model) and the speedup could be multiplicative.

Nevertheless we agree with the reviewer that the paper can be improved with more discussion on sparse training methods. We have added the discussion to Related Work.

Q2. Limited baseline evaluations

VCAS can translate FLOPs reduction into time reduction which is rare for sparse training methods. We compare VCAS with the official codebases of methods mentioned by the reviewer:

For Back Razor, we tested on BERT-large finetuning on MNLI. We find though Back Razor can reduce up to 90% FLOPs, it cannot reduce training time with its unstructured sparsity, and the accuracy drops a lot.

Tab. Comparison of VCAS with Back Razor

SWAT seems close to our work since it conducts a fine-grained pruning on weight and activation and implements a structured sparsity version that uniformly prune channels.

Since the official codebase of SWAT only supports CNNs, we compare SWAT with VCAS on WideResNet18 with widen factor $k=4$ on CIFAR100. We find VCAS can reduce training time while preserving accuracy, while SWAT is even slower than exact (dense) training due to its high overhead.

Tab. Comparison of VCAS with SWAT

Q3.Additional hyperparameters and insufficient ablations

First we'd like to emphasize that we employ the same set of hyperparameters in all our experiments across pretraining and finetuning, CV and NLP, and all get decent FLOPs reduction and accuracy. We believe it can already reflect the insensitivity. As said by Reviewer MWbo in "Strength", "the ablation studies on a few hyperparameters are very important. I see only very few of the papers in this domain have done this before".

From the experimental perspective, we agree with the reviewer that more experiments will help to justify our statement. So we have done all ablations again for BERT-base finetuning on SST-2. Please refer to Appendix A for the results.

Q4. Clarity of design choices in Section 5

Sorry for the confusion. To make our algorithm clearer we've added an algorithm table at the end of Section 5. Hope it can relieve your puzzle.

How to derive the provided equation from the mentioned zeroth-order algorithm?

The zeroth-order algorithm is embarassingly simple: since the variance increase monotonically with the drop ratio, our algorithm simply decrease the drop ratio by a constant if the variance is too large, and increase the drop ratio if the variance is too small. The only learning signal utilized is whether the variance is higher than the desired threshold. For a more intuitive view of the update, please refer to figures in Appendix C

Q5. Lack of proof on the unbiasedness of VCAS

Thank you for posing the vital problem of the unbiasedness of VCAS! We've added our proof in Appendix E.

Proof sketch: since our sampling is unbiased, we just need to prove the unbiasedness preserves in BP. As BP proceeds, linear operations like matmul, convolution and layernorm can obviously preserve unbiasedness. Nonlinear operations like ReLU incur Hadamard product with Jacobian matrix that is determined in forward pass, and thus also preserve unbiasedness. By induction we derive VCAS being unbiased.

We sincerely hope our response can solve your confusion and we would appreciate it pretty much if you could reevaluate our work. Thank you!

We thank reviewer d6vC for assessing our method as simple and highly applicable and for the valuable questions. Below we respond to the questions.

Q1. Relationship between Eval Acc and FLOPs reduction.

Thank you for posing the question that strikes at the heart. Actually that's where VCAS differs from previous sampling methods in essence.

In previous sampling methods, we typically first determine a sample ratio(FLOPs reduction ratio) $r$ and then apply sampling algorithms with it. However, many recent works $1,2$ that reflect the efficient training community have pointed out that this pipeline is indeed unfairly trading accuracy for efficiency. The sample ratio $r$ actually contains prior knowledge for the incoming training by telling the model how much percentage of the dataset is less informative.

VCAS distinguishes from previous sampling methods in that it eliminates the need of determining sample ratios. With VCAS, we use the variance thresholds to determine proper sample ratios adaptively. And to our best knowledge, we are the first to conduct adaptive unbiased sampling in training while preserving performance under theoretical guarantee.

Now we can answer your question: There is no direct relation between Eval Acc and FLOPs reduction in VCAS. They are connected with variance thresholds $\tau$ in the following way: FLOPs reduction will consistently climbs up as $\tau$ goes larger since we can tolerate a more radical sampling scheme. While for Eval Acc, when $\tau$ is not that large, like 0.025 in our setting, it won't change too much compared with exact training. But as $\tau$ goes larger, the extra sampling variance becomes unignorable, thus the convergence is affected and Eval Acc will drop.

Q2. More detail in Table 2 or 3.

For Table 2 now moved to Table 5, we are varying variance threshold $\tau$ . The FLOPs reduction consistently increases with bigger $\tau$. The Eval Acc keeps within 0.1% fluctuation of exact result when $\tau\le0.05$ which means the extra variance is no more than 10% and can be neglected, but drops a lot when $\tau\ge0.1$ which means more than 20% variance is introduced that affects convergence.

For Table 3 now moved to Table 7, we are varying update frequency $F$. As $F$ increases, we will conduct fewer updates, so the FLOPs reduction first increases due to reduced overhead caused by update process, and then decreases due to insufficient number of updates to converge on adequate sample ratios. The Eval Acc shows no much difference across $F$ since it's theoretically guaranteed to produce a similar result with the exact training with a low $\tau$, like $\tau=0.025$ here.

Q3. Is the recommending FLOPs reduction ratio for VCAS around 40%? How VCAS will perform under a 50% or greater reduction?

As discussed above, the FLOPs reduction of VCAS is not tuned manually but learned in the training process. So the FLOPs reduction ratio of VCAS varies among models and datasets and can be learned automatically, reflecting how much FLOPs can be "safely" saved under given variance budget.

Indeed, we can still trade accuracy for efficiency with a much larger variance in VCAS. For example, we test with BERT-large finetuning on MNLI with a big $\tau=0.5$ that provides a 50% FLOPs reduction, which means introducing 100% extra variance actually. For comparison we also tested SB and UB with FLOPs reduction of 50%. The results are as follows:

Table. Different methods with FLOPs reduction of 50%, strikethrough indicates divergence

We can see that the performance of VCAS drops a lot compared to exact training, which is actually predicted by the large $\tau$ value. However, the performance of VCAS is still much better than baselines like SB and UB both of which do not converge under this setting, owing to the fine-grained sampling and adaptive sample ratios across different training phases.

Q4. Effectiveness of time to reach target accuracy.

We list the effectiveness of time to reach target accuracy for BERT-base finetuning on MNLI below: (exact training results in Final Eval Acc of 84.33 and total steps of 36816)

Table. Number of steps to reach target accuracy with different methods

We can find VCAS similar with exact and much better than SB and UB.

For more insights on the effectiveness of VCAS, please refer to Fig.6b where we presented the Eval Acc curve of these methods.

Reference

[1]"The Efficiency Misnomer." ICLR.2021.

[2]"No train no gain: Revisiting efficient training algorithms for transformer-based language models." arXiv.2023.

We thank reviewer Dd1x for acknowledging the effectiveness of our work and for the insightful questions. Below we respond to the questions. We would highly appreciate it if the reviewer agree with our response and consider to raise the score. Thank you so much!

Q1. Training time reduction.

Thanks for the suggestion. To compare wall-clock training time, we choose two tasks with the longest training time: BERT-large finetuning on MNLI and ViT-large finetuning on ImageNet. The results are as follows:

Tab. BERT-large finetuning on MNLI

Tab. ViT-large finetuning on ImageNet

We find VCAS can translate FLOPs reduction into wall-clock time reduction as effectively as simpler online-batch sampling methods like UB and SB that drop part of data one-time in a whole, while enjoying mirrored performance with the exact training under theoretical guarantee.

Our current implementation of VCAS is purely based on Python and PyTorch. The gap between FLOPs reduction and time reduction can be further narrowed by optimizing the implementation with CUDA or Triton.

We have added the wall-clock time results to Section 6.2, thanks again for the suggestion!

Q2. Insights on sampling ratio updates.

Thanks for the constructive suggestion. We've added a few figures in Appendix B recording the update process of our sample ratios. For all variance thresholds $\tau$ from 0.01 to 0.5, gradient norm preserve ratio $s$ first drops rapidly and then slowly. Activation ratios $\rho_l$ gradually decrease with training. Weight ratios $\nu_l$ first drop and then fluctuate around a certain value that is different across $l$.

Q3. Figure/Table clarity.

Sorry for the confusion. Now we've added more explanations in Fig.2. The bold formatting in Tab.1 originally highlights the highest Eval Acc / (1-FLOPs reduction) which is a balance between performance and efficiency. Now we've changed it to indicate the best of each metric for better clarity. In Tab.1 we also added underlines to mark Eval Acc that is less than 0.1% off the exact training for a more intuitive look.

Q4. For Table 1, how significant is the relative improvement over baselines?

As in Tab.1, the FLOPs improvement is relatively marginal compared with UB and SB in our conservative settings of variance tolerance ratio $\tau=0.025$. But the accuracy improvement is significant, where the train loss and eval accuracy of VCAS are much closer to exact training.

However, it should be noted that the usage of VCAS is different from existing sampling baselines like UB and SB. For UB and SB, we need to preset a sample ratio $r$ carefully and pray for a decent outcome. While for VCAS, we just need to set a variance tolerance ratio $\tau$ far less than 1, and then it can adaptive learn the proper fine-grained sample ratios which can keep the training curve closely to that of exact training. Therefore, two more important improvements are that VCAS is tuning-free for sample ratios and the FLOPs reduction achieved by VCAS is "safer" with theoretical guarantee compared to other baselines.

Q5. Limitations should be discussed.

Thanks for the constructive advice. We've added a detailed discussion of the limitations of VCAS in Appendix G.

Regarding to the limitations on applicable model architecture, base optimizer, dataset, theoretically, there will not be such limitations. But the performance of VCAS is closely related with the "redundancy" of architectures and datasets. Nevertheless, in such scenario, VCAS can learn to keep all data to control the variance (i.e., fall back to exact training), and the accuracy will not be harmed. On the other hand, other online batch sampling methods are likely to fail.

We thank reviewer MWbo for acknowledging the effectiveness of our work and for the constructive questions. Below we respond to the questions.

Q1. Add an algorithm table.

We appreciate it a lot for your constructive advice. We've now added an algorithm table in Algorithm 1 at the end of Section 5. Thank you!

Q2. Report wall-clock time reduction.

Thanks for your insightful advice. As you can see, not many papers report the wall-clock time reduction, mainly because the wall-clock time is highly dependent on hardware and implementation. FLOPs reduction, however, is a high-level metric directly reflecting the real power of algorithm. Each metric has its own pros and cons.

Though, we agree that wall-clock time is indispensable since that's what we really want to accelerate and FLOPs reduction can not always translate into equal wall-clock time reduction, not only because of the overhead introduced, but also due to parallelizability, hardware friendliness, and compatibility to many other minor but crucial parts in the training procedure.

For this metric we choose two tasks with the longest training time, which are most worthy of acceleration: BERT-large finetuning on MNLI and ViT-large finetuning on ImageNet. The results are as follows:

Tab. BERT-large finetuning on MNLI:

Tab. ViT-large finetuning on ImageNet:

From these tables, we can find that VCAS can translate FLOPs reduction into wall-clock time reduction as effectively as simpler online-batch sampling methods like UB and SB that drop part of data one-time in a whole, while enjoying mirrored performance with the exact training under theoretical guarantee.

Our current implementation of VCAS is purely based on Python and PyTorch. The gap between FLOPs reduction and time reduction can be further narrowed by optimizing the implementation with CUDA or Triton.

We have added the wall-clock time results to Section 6.2, thanks again for the suggestion!

Q3. Lack discussions of related paper.

Thanks for your advice! We have added more discussions on these papers as well as many other papers in Section 2 of Related Work in our paper.

Overall, we are addressing the problem of sampling in a new way to the best of our knowledge. VCAS differs from all these sampling algorithms in that it doesn't need a carefully tuned sample ratio and is always sure to provide a similar result with exact training under theoretical guarantee.

Specifically for the two methods mentioned by the reviewer, the loss based method OBFTF samples data by minimizing the distance of average losses between the whole batch and the sampled batch. Its theoretical guarantee and stability are not strong enough since it is sensitive to the absolute value of losses. It is also sensitive to batch size for solving a combinatorial optimization problem that will explode when batch size is large.

The adaptive method AdaSelection is an ensemble of SB, UB, uniform sampling and other methods by adaptively assigning weights among them. It is different from VCAS in the way of adaption: VCAS adaptively find the proper sample ratios, while AdaSelection still needs to preset a sample ratio and simply adapt weights of each method under the ratio. Thus VCAS is more tuning-free, more effective with finer sampling granularity, and provides more theoretical guarantee.

Q4. Clarity of notations.

Sorry for the confusion. $h^{(l)}$ means the function of calculating input gradient with output gradient, input and weight. For example for linear layers, we have input gradient equals to output gradient multiplied by weight. The same with $g^{(l)}$ for weight gradient.

We have now added more explanations on every notations in Section 4 and 5. Hope it can relieve your puzzle!