Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes several techniques to boost DNNs' training efficiency on edge devices from the mutation rate schedule and data efficiency perspective. It's good to see the improvements in the training speed and memory footprint measured on real mobile devices, which may practically help the community.
main_review: ## Originality and significance
The proposed techniques are evaluated on real mobile devices with non-trivial improvements in training speed and memory footprint, which is appreciated in DNN acceleration works and may positively help the community. However, most of the techniques are built on top of previous works with marginal novelty, which is my main concern for this paper. For example, considering both weight magnitude and gradient as the pruning metric is widely adopted in previous pruning works. In addition, the proposed EM/EM&S is more like engineering tricks built on top of existing sparse training works which lack motivating analysis to support their general effectiveness, so is the two-phase data efficient training. Therefore, the novelty of this work needs to be better justified.

## Quality and clarity
The paper conduct extensive experiments to validate the effectiveness of the proposed methods, which is solid. However, the following concerns may influence the quality of this paper:

(1) The writing can be better organized. As the data efficient training has been discussed in many previous works like E2Train (Y. Wang, NeurIPS'19) as well as [20][21][22][23] cited by this paper, the two-phase training is marginally different from previous solutions which can be simplified. Instead, Sec. 3.2 is too concise and many details in the appendix are necessary for demonstrating the proposed techniques. It may be better to re-balance the length of each technique in this paper.

(2) Although the evaluation shows impressive improvements, the motivation and rationale behind each technique are not well-analyzed, especially in Sec. 3.2. This may limit the insights provided by this paper.

(3) The paper mainly considers ResNet-32/VGG-19 for experiments on CIFAR-10/100 and it may strength the evaluation to evaluate the proposed technique on (a) MobileNetV2, as compact models may suffer more from high sparsity, and (b) deeper ResNet like ResNet-110, as deeper networks may suffer more from gradient explosion/vanishing problems under compression techniques.

(4) To confirm some details:  

(a) According to algorithm 1, will the proposed techniques be applied on gradients and activations as well?

(b) Considering the unforgettable examples may be less on ImageNet, how many data will be discarded by MEST + EM&S + DE on ImageNet in Table 2? It seems w/ and w/o DE makes trivial difference?

I'm willing to raise my scores if the above concerns are properly addressed.
limitations_and_societal_impact: The limitations are discussed in the main review section.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes the memory-economic sparse training (MEST) framework that targets efficient sparse training on edge devices. The author proposes an elastic mutation (EM) and a soft memory bound algorithm for sparse training. Their training methods can keep the entire training process sparse and avoiding involve dense forward/backward computation. This paper also investigates the impact of different sparsity schemes on sparse training performance in accuracy and speed acceleration. Besides, the paper also introduces data-efficient training in sparse training scenes. Compared to previous works, this work is more hardware friendly and can achieve similar even higher accuracy. These proposed methods are more hardware-friendly and achieve higher accuracy. The proposed framework is promising to be implemented for real-world sparse training acceleration. This paper can be impactful for both the community of academia and industry.
main_review: Originality and Significance: 
Different from previous DST works that focus more on the accuracy, this paper investigates the sparse training problem from the perspective of memory economic. There is a trend that sparse training works tend to utilize dense model computation more or less, (e.g., obtain dense gradients and select a new subnetwork based on that). This paper avoids that and only uses sparse computation through the entire sparse training process. This is critical when considering the realistic implementation, especially on edge devices. The proposed EM and soft memory-bound methods are not complicated, but the results look impressively good.

I think one important contribution of this work is that they investigate the performance of different sparsity schemes in adynamic sparse training scenes. The difficulty of unstructured sparsity to achieve actual acceleration is a well-known challenge. There is a long-standing gap between theoretical research and actual implementation of sparse training acceleration, because the research mainly focuses on unstructured sparsity. This work may provide a new direction for the sparse training community to investigate more sparsity schemes that can achieve both acceleration and high accuracy. I always expect to see some works like this one trying to close this gap.

Another contribution of this paper is to introduce data-efficient training, which only uses a partial training dataset, into the dynamic sparse training process, while the accuracy can also be maintained. The data-efficient training itself is not a new concept, but it is novel to be combined with dynamic sparse training and different sparsity schemes. The author also provides a thorough study on how their proposed EM method, algorithms, and sparsity schemes will affect the performance of data-efficient training such as final accuracy and number of unforgettable examples, etc., which is interesting.

Quality and Clarity:
The paper contains quite a lot of content within a 9 pages paper. But overall, the paper is well written and easy to follow. The motivation and contribution of the paper are clearly stated. The experiments are able to support their claims and conclusions. And the superior results show the effectiveness of the proposed methods.

Overall Comments:
Overall, this is a good paper. It investigates sparse training from different angles compared to previous works. It is valuable that this paper takes into account many practical problems in the design, such as memory bound and efficiency of sparse computations, rather than based on pure theoretical analysis. These are critical in real implementation but easy to be ignored in research.
Their proposed methods seem more practical. That is why I think this paper can be impactful for both industry and academia.

Improvements:
For the Data-efficient Sparse Training on the Edge Section (Section 4.2), it would be better if you can draw a figure to show the flow of your two-phase data-efficient sparse training process.

There is a typo in the caption of figure 3. You mentioned the threshold is 1 and 2, where the figure shows th=0 and 1.

Questions：
How do you determine the frequency of the mutation? What is the impact if you have a higher or lower mutation frequency?

I am curious about how to mutate the model topology if you avoid storing a dense model on the edge devices?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Training Deep Neural Networks on limited resource (memory/power) edge devices is a challenging problem considering the memory and computational complexity of the training algorithm. This paper presents, MEST, a novel memory economic DNN training framework which exploits model sparsity (scheme and ratio) to speed up the training process without significant accuracy loss. 

The Authors present two improvements on the vanilla MEST algorithm in the form of Elastic mutation and soft memory bound which further enables increase in training speed while improving the training accuracy. Sparsity scheme and ratio are critical in determining the accuracy and training speedup derived from the proposed solution, the Authors discuss this dependence in detail.

Lastly, the paper also exploits data efficiency by capitalizing on unforgettable examples during training.  The Authors propose a strategy for identifying a set of unforgettable examples in-situ on the edge device and skipping it during part of the training process to improve training speed up. 

The Authors present a detailed set of experiments for a few DNN models on a few target benchmarks while measuring accuracy, training speedup and memory footprint of the proposed algorithms.

main_review: The paper is well written and presents related work along with the key concepts utilized in the paper. This juxtaposition of past work and the proposed ideas improves readability and helps distinguish the new ideas. 

The Authors propose MEST a novel DNN training algorithm that claims to support end-to-end training on edge devices. MEST utilizes sparsity schemes and ratios along with a magnitude + gradient weighted, weight mutation to train DNNs with speedup over dense baseline and small accuracy losses. They further add Elastic Mutation and Soft Memory Bound updates to the algorithm. These novel updates enhance the training speedup achieved by the vanilla algorithm with improvements in accuracy. 

This paper also presents the first analysis on the combination of Data efficiency techniques for training speedup through skipping of unforgettable examples with dynamic sparse model-based training. The combination of the two approaches enables a shrinkage in memory footprint on top of MEST based approaches while adding more training speedup. The experiments conducted show the superiority of the MEST approaches in terms of improved accuracy, training speed and memory footprint. 

In the introduction Authors use the term accuracy performance, this is confusing, and it would be great if the Authors could define it. Is it the product of accuracy and performance (training speed) or just accuracy?

Table 1 shows a comparison of MEST family of training algorithms and past approaches for training ResNet-32 on CIFAR-10/100. I don’t understand the authors choice of going with a qualitative description of the memory footprint for the different approaches instead of a quantitative metric. Quantitative description could help understand the added memory footprint impact of Soft Memory Bound optimization. This increase in memory footprint can be visualized in Figure 4c). If the Authors could clearly state, the expected memory footprint deterioration for utilizing the Soft Memory Bound update to MEST. This could help the users of MEST make an informed choice about trading off higher accuracy for said memory footprint cost. 

Section 5 defines the training speed measurement as the computation time for forward/backward pass on a batch of 64 images. What is the significance of selecting this batch of images? The choice of 64 images seems quite low compared to the dataset required to achieve the accuracies quoted in the experiments. This begs the question that whether the MEST framework, despite showing solid improvements against past work, enables end-to-end training of target DNNs (ResNet-32, VGG-19 etc.) for the target datasets (CIFAR-10, CIFAR-100 …) on edge devices? 

On multiple instances in the paper the Authors utilize the term “not practical/compatible for edge training” (e.g., line 306, 359). It would be helpful if the Authors could state what criteria limits the practicality/compatibility of these approaches. Specifically, what is the threshold of memory footprint identified by the Authors for edge devices. This question also impacts the interpretation of Figure 4c), which highlights the superiority of MEST solutions over prior art. Are MEST solutions small enough to fit on actual edge devices? Also, the choice of 90% sparsity ratio for figure 4c) seems to present the MEST+EM solution more optimistically than the 95% sparsity ratio where a few past approaches show comparable accuracy. Showing the worst case comparison for MEST will shed better light on MEST benefits.

In Section 3.1 the Authors correctly state that FLOPs don’t account for execution overheads from irregular memory access for sparse data ops. However, the Authors still utilize FLOPs as the normalizing factor for Table 2 to compare the accuracy benefits of MEST solutions compared to prior art. Could the Authors justify why its suitable to use FLOPs in this context?

Figure 2 elucidates the significance of selecting the correct sparsity scheme on the training speed. While channel sparsity provides significant speed improvements later results highlighted in Figure 4 a) and b) show that the accuracy penalty of channel sparsity is also the highest. Authors mention on line 349 that weight elastic mutation can help alleviate this poor accuracy result for channel sparsity. Do Authors have any results for this claim? Does this optimization bring channel sparsity within Figure 4 c)’s range? 

To improve the readability of the results on accuracy, training speedup and memory footprint it would be nice if Authors reworded “the best-performant MEST” to “the best-performant MEST for the metric”. Since it gives the impression that a single configuration of MEST provides the reported improvements, which doesn’t seem obvious from the presented figures.

limitations_and_societal_impact: A quantitative comparison on the memory footprint costs of the prior art and proposed training algorithms would be handy to understand the tradeoffs between different MEST variants. 

The selection of training time speedup doesn’t give clarity on whether the edge training devices used can support end-to-end DNN training with MEST algorithm. If such end-to-end training cannot fit on the edge device then the Authors’ claim that MEST makes training on the edge feasible might not be completely accurate.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper is conceived in the true spirit of sparse training (i.e., start with a sparse neural network; train at any moment in time  a sparse neural network and don’t use information from non-existing connections; do inference with the trained sparse neural network) to enable neural networks training at the edge on low-resource devices. In order to do so, the paper proposes a new sparse training algorithm with dynamic sparsity, named MEST, with a couple of variations for various settings (e.g., hard or soft memory constraints). Also, MEST, in contrast with the typical sparse training algorithms,  introduces the magnitude combined with the gradient as a metric to detect unimportant connections. Nevertheless, the paper is also considering data efficiency for the first time in sparse training (up to my knowledge). The extensive and rigorous empirical validation shows that MEST and its variants reach state-of-the-art performance in sparse training. Notably, even if it is not one of the paper claims, it seems that MEST can outperform dense training on convolutional neural networks using just half of the computational resources. Convolutional layers being perhaps the last type of neural network layer on which it is still arguable in the literature if truly sparse training can outperform dense training (see for details Table 2, left column, ResNet-50 on ImageNet). 
main_review: **Originality**

This paper has an excellent level of originality and proposes several innovations on several dimensions for various settings which improves state-of-the-art performance. Remarkable, the proposed innovations are simple and efficient. Related work is well discussed. As minor comments:

_ I suggest changing the order of introducing Sparse Evolutionary Training (SET) and DeepR (e.g., lines 122-129), as SET has been released in 2017 with a couple of months before DeepR (see https://arxiv.org/abs/1707.04780). 

_ The related work on fixed sparsity (Section 2.2.1) is missing few papers which have been published well before SNIP - Ref [9].

_ The related work on dynamic sparsity (Section 2.2.2) shall discuss also a method like Top-KAST (https://arxiv.org/abs/2106.03517) which is an improvement over RigL  - Ref [14] in terms of memory efficiency.

**Quality**

The submission and the proposed methods are technically sound. The empirical validation is well executed. For me, this looks like a complete solid piece of work. 

**Clarity**

The paper has a very good structure, and it is clear and well written.  I believe that the paper together with the Appendix and the released code can help any interested reader to easily reproduce the results. As a minor comment, perhaps you can consider bringing some parts of Appendix E (e.g., Equation 5) to the main paper as it looks to me as an interesting contribution which may have a good influence on the results.

Actually, my only question for the rebuttal is related with Appendix E. Have you tried to assess systematically the influence of Equation 5 on the learning behavior? My hypothesis is that it helps MEST to speed up its learning process in comparison with other sparse training methods which use just magnitude to identify unimportant weights. It seems that Table 2 supports somehow this idea (see MEST 0.5x) and makes MEST to learn even faster than RigL in the context where MEST uses just random growth and not gradient growth (Am I right here?). Do you have the learning curves (e.g. training epoch versus accuracy - or similar) during training. If the space permit, it would be great if you can put one example of learning curves in the rebuttal, and perhaps more examples in the Appendix of the final paper. 

**Significance**

I believe that this paper has the potential of becoming a landmark in sparse training with dynamic sparsity. 

limitations_and_societal_impact: While within the whole paper its limitations and advantages seem fairly discussed, a self-contained paragraph where the limitations are clearly enumerated is missing. In my opinion, adding such a paragraph will just increase the paper quality.
review_title: null

Meta-review: This paper proposes the memory-economic sparse training (MEST) framework for efficient sparse training on edge devices. The author proposes an elastic mutation (EM) and a soft memory bound algorithm for sparse training. Their training methods can keep the entire training process sparse and avoiding involve dense forward/backward computation. This paper also investigates the impact of different sparsity schemes on sparse training performance in accuracy and speed acceleration. Besides, the method also introduces data-efficient training in sparse training scenarios.

The rebuttal has resolved most reviewers' concerns. All reviewers are quite possible on this paper.
Decision: Accept (Spotlight)