MEST: Accurate and Fast Memory-Economic Sparse Training Framework on the Edge
Authors: Geng Yuan
Xiaolong Ma
Wei Niu
Zhengang Li
Zhenglun Kong
Ning Liu
Yifan Gong
Zheng Zhan
Chaoyang He
Qing Jin
Siyue Wang
Minghai Qin
Bin Ren
Yanzhi Wang
Sijia Liu
Xue Lin
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: dynamic sparse training
memory-economic training
edge device training
mobile training acceleration

Abstract: Recently, a new trend of exploring sparsity for accelerating neural network training has emerged, embracing the paradigm of training on the edge. This paper proposes a novel Memory-Economic Sparse Training (MEST) framework targeting for accurate and fast execution on edge devices. The proposed MEST framework consists of enhancements by Elastic Mutation (EM) and Soft Memory Bound (&S) that ensure superior accuracy at high sparsity ratios. Different from the existing works for sparse training, this current work reveals the importance of sparsity schemes on the performance of sparse training in terms of accuracy as well as training speed on real edge devices. On top of that, the paper proposes to employ data efficiency for further acceleration of sparse training. Our results suggest that unforgettable examples can be identified in-situ even during the dynamic exploration of sparsity masks in the sparse training process, and therefore can be removed for further training speedup on edge devices. Comparing with state-of-the-art (SOTA) works on accuracy, our MEST increases Top-1 accuracy significantly on ImageNet when using the same unstructured sparsity scheme. Systematical evaluation on accuracy, training speed, and memory footprint are conducted, where the proposed MEST framework consistently outperforms representative SOTA works. A reviewer strongly against our work based on his false assumptions and misunderstandings. On top of the previous submission, we employ data efficiency for further acceleration of sparse training. And we explore the impact of model sparsity, sparsity schemes, and sparse training algorithms on the number of removable training examples. Our codes are publicly available at: https://github.com/boone891214/MEST.

MEST: Accurate and Fast Memory-Economic Sparse Training Framework on the Edge
Geng Yuan 1,, Xiaolong Ma Wei Niu², Zhengang Li', Zhenglun Kong', Ning Liu Yifan Gong", Zheng Zhan', Chaoyang He Qing Jin', Siyue Wang', Minghai Qin, Bin Ren", Yanzhi Wang', Sijia Liu Xue Lin'
Northeastern University, 2 College of William and Mary, 3 Midea Group, 4 University of Southern California, 5 Michigan State University {yuan. geng, xue. iino@nottheateenn..
Abstract
Recently, new trend of exploring sparsity for accelerating neural network training has emerged, embracing the paradigm of training on the edge. This paper proposes novel Memory--Ecooome Sparse Training (MEST) framework targeting for accu- rate and fast execution on edge devices. The proposed MEST framework consists of enhancements by Elastic Mutation (EM) and Soft Memory Bound (&S) that ensure superior accuracy at high sparsity ratios. Different from the existing works for sparse training, this current work reveals the importance of sparsity schemes the performance of sparse training in terms of accuracy as well as training speed real edge devices. On top of that, the paper proposes employ data efficiency for further acceleration of sparse training. Our results suggest that unforgettable examples can be identified in-situ even during the dynamic exploration of sparsity masks in the sparse training process, and therefore can be removed for further training speedup
edge devices. Comparing with state-of-the-arr (SOTA) works accuracy, our MEST increases Top-1 I accuracy significantly on ImageNet when using the same unstructured sparsity scheme. Systematical evaluation on accuracy, training speed, and memory footprint are conducted, where the proposed MEST framework consistently outperforms representative SOTA works. Our codes are publicly available at: https: htt//ttttuu// com//ooone911144/ME3T
Introduction
To promote the broader applications of deep learning the edge, surge of research efforts have been devoted to removing the over-parameterization neural networks for accelerated inference. Specifically, existing works have explored various strategies such heuristics- based pruning 2
regularization-bast based pruning [3] [4. and recently prevailing network architecture search [ 6 7 g
Recently, a new trend of exploring sparsity for training acceleration of neural networks has emerged to embrace the promising training-on-the-ede paradigm. The first works in this direction use the pruning-at-initian atiiiiiaizaiiiiiioonn approach such as SNIP [9] and GraSP [TQ] that first obtains fixed sparse model structure and then follows with a traditional training process. However, the whole process is still computation- and memory-intensive, and therefore not compatible with the end-to-end edge training paradigm. Such a sparse training methodology with the pre-fixed structure also faces the problem of compromised accuracy.
These authors contributed equally.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Furthermore, sparse training with dynamic spar- sity mask such as SET [14) DeepR [[5]. DSR
78-
[3]. Rigl. [ and SNFS [22 have been pro- posed, showing great potential towards end-to- end edge training. Specifically, they start with a sparse model structure picked intuitively from the initialized (but not trained) dense model, and then heuristically explore various sparse topolo- gies the given sparsity ratio, together with the sparse model training. The underlying principle of sparse training is that the total epoch num- ber the same as dense training, but the speed of each training iteration (batch) is significantly improved, thanks to the reduced computation amount due sparsity.
Top-1 accerracy (%)
76
Rigl-St
Righ.
SNFS
DSR
Deepi
GraSP
70
SNIP
MEST+EM
MEST-EMAS
68
50
60
70
80
90
Sparsity Ratio (%)
Figure 1: Accuracy vs sparsity ratio on ImageNet using ResNet-50 dense model. Our proposed MEST framework: MEST+EM (Elastic Mutation) and MEST+EM&S (with Soft Memory Bound) are compared with the SOTA sparse training al- gorithms i.e., GraSP [0]. SNIP RigL [1] SNFS [2]. DSR 13 SET 44
This paper proposes a novel Memory-Economic Sparse Training (MEST) framework targeting for accurate and fast execution on edge devices. Specifically, we boost the accuracy with the MEST+EM (Elastic Mutation) to effectively ex- plore various sparse topologies. And we propose another enhancement through applying soft memory bound, namely, MEST+EM&S, which relaxes on the memory footprint during sparse training with the target sparsity ratio met by the end of training. In Figure [ the accuracy of the proposed MEST is compared against state-of-the-art (SOTA) sparse training algorithms under different sparsity ratios, using the same unstructured sparsity scheme.
and DeepR 15
Furthermore, as with inference acceleration, we find that sparse training closely relates to the adopted sparsity scheme such as unstructured (16), structured [17] 18), or fine-grained structured [19] scheme, which can result in varying accuracy. training speed, and memory footprint performance for sparse training. With our effective MEST framework, this paper systematically investigates the sparse training problem with respect to the sparsity schemes. Specifically, besides the directly observable model accuracy, conduct thorough analysis the memory footprint by different sparsity schemes during sparse training, and in addition, we measure the training speed performance under various schemes on the mobile edge device.
On top of that, the paper proposes to employ data efficiency for further acceleration of sparse training. The prior works [20 21 22 23 show that the amount of information provided by each training example is different, and the hardness of having an example correctly learned is also different. Some training examples can be learned correctly early in the training stage and will never be "forgotten" (i.e., misclassified) again. And removing those easy and less informative examples from the training dataset will not cause accuracy degradation on the final model. However, the research of connecting training data efficiency to a sparse training scene still missing, due to the dynamic sparsity mask. In this work, we explore the impact of model sparsity, sparsity schemes, and sparse training algorithm on the amount of removable training examples. And we also propose a data-efficient two-phase sparse training approach effectively accelerate sparse training by removing less informative examples during the training process without harming the final accuracy. The contributions of this work are summarized as follows:
A novel Seemory-Econome Sparse Training (MEST) framework with enhancements by Elastic Mutation (EM) and the soft memory bound targeting for accurate and fast execution on the edge.
A systematic investigation of the impact of sparsity scheme on the accuracy, memory footprint, as well as training speed with real edge devices, providing guidance for future edge training paradigm.
Exploring the training data efficiency in the sparse training scenario for further training acceleration, by proposing a two-phase sparse training approach for in-situ identification and removal of less informative examples during the training without hurting the final accuracy.
On CIFAR- with ResNet-32, comparing with representative SOTA sparse training works, i.e., SNIP, GraSP, SET, and DSR, our MEST increases accuracy by 1.91 %, 1.54%, 1.14%, and 1.17%;

---

achieves 1.76x, 1.65x. 1.87x, and 1.98x training acceleration rate; and reduces the memory footprint by 8.4x, 8.4x, 1.2x, and 1.2x, respectively.
2 Background and Related Work
This section introduces representative neural network sparsity schemes and their impacts memory footprint in sparse training, as well as the neural network sparse training strategies.
2.1 Sparsity Scheme
Neural network pruning has been well investigated for inference acceleration. The majority of works in this direction apply pretraining wawngggg-uungggggn pruning-retrainin flow, which is not compatible with the training- on-the-edge paradigm. According to the adopted sparsity scheme, those works can be categorized as
unstructured [66] 1 structured 24
2 25
26
29 30 3I [8] 32 [3), and fine- graiied 41 including the pattern-hased and block-based ones.
17
27 28
structured 19
35
36
37
38
39
Detailed discussion about these sparsity schemes is provided in Appendix A.
Although these sparsity schemes are mainly proposed for accelerating inference, we find that they also play important role in sparse training in terms of accuracy, memory footprint, and training speed. For memory footprint, we focus on the two major components that vary with the sparsity scheme: model representation together with gradients produced during training. The detailed analysis is provided in Appendix B.
2.2 Sparse Training
Majority of the sparse training works can be categorized into two groups: fixed-mask sparse training and dynamic-mant mask sparse training. Additionally, there exist works 42 networks in the early training stage, but they are out of scope for sparse training on the edge.
43 44 that prune dense
2.2.1 Sparse Training with Fixed Sparsity Mask
The fixed-mask approach that after pruning, the sparse model training can be executed on edge devices. SNIP (9] preserves the loss after pruning based on connection sensitivity. GraSP 10 prunes connections in a way that accounts for their role in the network's 's gradient flow. SynFlow
10 45 46
has been proposed to decouple pruning and training such
proposes iterative synaptic flow pruning, which avoids layer collapse and preserves the total flow synaptic strengths throughout the network. Since the proposed pruning algorithm does not incorporate back propagation, it achieves global pruning at initialization without data. Based on the unstructured SNIP objective, 3SP [47] further introduces computation-aware weighting of the pruning score. This actively biases pruning by removing more computation intensivve channels which either have small effect on the loss or have significant computation cost. However, the pruning maaaiing-t-initiall at-initialization process is still computation and memory- memory-intensiv intensive and therefore not compatible with the end-to-end sparse training on the edge. And these works (except 3SP) employ the unstructured sparsity scheme.
45
2.2.2 Sparse Training with Dynamic Sparsity Mask
To reduce the computation well as memory footprint during the whole training phase, sparse training is exploited in many works 15 training well maintain low memory footprint. Sparse Evolutionary Training (SET) [4] uses magnitude- based pruning and random growth at the end of each training epoch. DeepR (15 combines dynamic sparse parameterization with stochastic parameter updates for training. This method is primarily demonstrated with sparsification of fully-connected layers and applied to relatively small and shallow networks. DSR [ develops a dynamic reparameterization method achieve high parameter efficiency in training sparse deep residual networks. SNFS [2] develops sparse momentum, an algorithm which uses exponentially smoothed gradients (momentum) to identify layers and weights which reduce the error efficiently. RigL [1I] proposes to iteratively update sparse model topology during training by calculating dense gradients only the update step. Note that, though SNFS and RigL. are sparse training, they actually involve computation of all the gradients corresponding to both pruned and non-zero weights, and therefore their memory footprint equivalent to that of dense training.
14
13
12
I1I which can adjust the sparsity topology during
3

---

3 Sparse Training on the Edge
3.1 Sparsity Scheme in Sparse Training on the Edge
represent the training speed performance using the training FLOOP count. Actually, such FLOPS cannot account for the ac- tual execution overheads caused by the sparse data operations. For example, the unstructured sparsity exhibits irregular memory access pattern, leading significant execution overhead. Moreover, the dense model can take advantage of Winograd [8]] to significantly accelerate the computation speed, which may apply in sparse computation. Therefore, this paper directly measures the training speed performance on mobile device. We investigate the training acceleration performance by different sparsity schemes including unstructured, structured, and two state-of the-art fine- fine-grained structured (i.e., block and pattern), through prototype implementation on a mobile edge device. To do so, we conduct compiler-level optimizations, leveraging a computation-grage based compilation approach, including optimizations on computation graph itself, tensor optimizations, etc. More details are provided in Appendix C.
common to see that sparse training works TO
45
-tate-of-the-ar
Figure 2 shows representative training speed per- formance under various sparsity schemes, using an example CONV layer adopted from ResNet- 32. We evaluate the acceleration rate by mea- suring the total forward and backward execution time of the sparse CONV layer Samsung Galaxy S20 smartphone, and then normalizing with respect to that of the corresponding dense layer. Surprisingly, even under the same sparsity ratio, found that the acceleration rates of dif- ferent sparsity schemes are varied significantly. When the sparsity ratio below 70% and 80% for block-based sparsity and unstructured spar- sity schemes. respectively. they cannot achieve any acceleration and even slow down the com- putation speed, compared to the corresponding dense model. Thus, choosing an appropriate sparsity scheme is an essential factor for sparse training for acceleration purposes.
channel
Acceleration rale (times)
pattern
block
2.5
unstructured
dense
2.0
1.0
0.5
10
20
30
40
50
60
70
80
85
90
95
98
Sparsity Ratio (%)
Figure 2: Training acceleration rate vs sparsity ratio of different sparsity schemes. The results here are measured on a 3 xx3 CONV layer selected from ResNet-32 with 64/64 input/output channels and 16x 16 input feature map, with Samsung Galaxy S20 smartphone.
3.2 Proposed
Sparse Training (MEST) Framework
To facilitate the sparse training edge devices, our MEST framework is designed for the following objectives: 1) towards end-to-end memory-economic training by considering the resource limitation of edge devices; 2) Exploiting sparsity schemes to achieve high sparse training acceleration while maintaining high accuracy. We propose the MEST method (vanilla) to periodically remove less important non-zero weights from the sparse model and grow zero weights back during the sparse training process, which we call mutation, to explore desired sparse topologies with a specified sparsity scheme and ratio. Previous works [4 [3 directly use the weight magnitude the indicator of its importance. However, determining the weight importance only based on its magnitude is not ideal, because the weight magnitude may fluctuate significantly during the training. Therefore, in MEST, we incorporate the weight's 's current gradient an indicator for its changing trend to estimate its importance. We define the importance score as:
Scr |w-| + LA 20(W,-1,
Ow,-1
where D denotes the training data: ((W,-1, D) and de(W, 1.D) are the loss and gradient at epoch r; 8w
and À is the coefficient for the gradient. As result, three types of weights are considered relatively important, which are the weights with 1) large weight magnitude but small gradient, 2) small weight magnitude but large gradient, and 3) large weight magnitude and large gradient. The exploration of the impact of the coefficient À sparse training accuracy is shown in Appendix E.
More importantly, different from the methods (e.g., Rigl. IT] that use gradients of the dense model to find the weights to grow back, we only use sparse gradients to identify less important

---

weights to remove, then randomly select weights to grow back. In this way, our MEST strictly keeps the sparsity of weights and gradients during the entire sparse training process. This critical for memory-econome
sparse training on resource-limited edge devices. Moreover, different from previous dynamic sparse training methods that only uses unstructured sparsity, our MEST consider the constraints of different sparsity schemes into the mutation policy (more details in Appendix D).
Elastic Mutation (EM): We further propose an Elastic Mutation method to gradually reduce the mutation rate along with the training process, called Memory-Econon Economic Sparse Training with Elastic Mutation (MEST+EM). We are mainly based on two consid- erations: 1) larger mutation ratio will provide a larger search space dur- ing the dynamic sparse training pro- cess; and 2) the dramatic structural change of the network may compro- mise the training convergence. Thus, propose our EM method to gradu- ally reduce the mutation ratio during the dynamic sparse training process, which maintains a sufficient search space while making the sparse model smoothly stabilize to an optimized structure.
Algorithm 1: MEST with (Soft) Elastic Mutation
Input:
Network with uninitialized weight W in total of L layers, target sparsity ratio 8. p. 7, Ar, Tatop-
Output: A sparse model satisfying the target sparsity requirement.
Initialize W with random values and random sparse mask according to the sparsity requirements.
while T < Tstop do if MEM then if (T mod Ar) = then
do weight mutation
Decay p pf reaches a decaying milestone. for each layer weight tensor W do W t ArgRemoveTo W , 1 +p) W ArgōrovTo .s)
MEST+EM&S then
Decay p i reaches a decaying milestone. for each layer weight tensor W do
L W <- ArgGrosTo(W' :8 p)
Soft memory bound Elastic Muta- tion (EM&S): If the application sce- nario that the memory footprint could be soft constraint, we propose an enhancement with the Soft Memory Bound, namely, Memory-Fcononin Sparse Training with Soft- foft-bounded Elastic Mutation (MEST+EM&S), as an option to further improve accuracy. Different from the EM method that the less important weights will always be removed, our EM&S allows the newly grown weights be added to the existing weights and then trained, then the less important weights will be selected from all weights including the newly grown weights. This can avoid forcing the existing weights in the model to be removed if they are more important than newly grown weights. This can be considered as adding an 'undo' mechanism the mutation process. Note that even with a soft memory bound, the target sparsity ratio can still be met by the end of sparse training and keep the entire training process sparse.
Training for AT epochs;
D +++
for each layer weight tensor W do
W <- ArgRemoveTo
Continue sparse training from the epoch Tstop to Tend-
Notation and Preliminary: Consider W E N is the weights of the entire network. The number of weights in the 1-th layer W is N'. Our target sparsity ratio is denoted by s E (0, 1). We mutate on a fraction p E (0, 1) of the weights W', Suppose the total number of training epoch is Tend, then we conduct the weight mutation for the first Tstop < Tend) epochs with a frequency of Ar.
Algorithm D shows the flow of MEST+EM and MEST+EM&S. The main difference between MEST+EM and MEST+EM&S is the order that Ar ArgRemoveTo(-) and ArgGrowTo(.) are performed. In MEST+EM, we perform weight mutation for every AT epochs with following steps: first use ArgRemoveTo(WW" ( s + p) to remove x N less important weights from total of s x N non-zero weights; and then grow the model back to sparsity 8 with ArgGrowTo(W!, s), which randomly activates a number x N' of zero weights. The newly activated weights although are being zeros, will be considered as part of the sparse model and be trained. During the entire training process, the model sparsity is strictly bounded by 8, thus maintaining a hard memory bound. On the other hand, in MEST+EM&S, for every other AT epochs, we first grow the model reduce the sparsity ratio to s - by ArgGrowTo (Wi, p) and train for AT epochs, and then remove weights to increase the sparsity ratio back to by WW"" s). We also decay p at given milestone epochs until Tstop- During the entire training process, the weights are trained at sparsity ratio p, and sparsity
5

---

Unforgettable Examples Under Different Sparsity
Forgotten Examples Increased in each Epoch
20000
96
Mutation Epochy
Number of forgotten examples
Unforgettable examples
accuracy
18000
94
16000
92
Accuracy
40
unforgettable examples
14000
12000
86
10
10000
84
0.6
0.8
0.9
0.95
Sparsity
64 Epoch
72
Vanilla
MEST-EM
MEST+EMAS
Vanilla
MEST-EM
MEST-EMAS
Vanilla
MEST-EM
MEST-EMAS
(a)
(b)
Figure 3: Data efficiency investigation on ResNet-32 using CIFAR-IO. (a) The number of unforget-
table examples after the sparse training process under different sparse training algorithms and sparsity ratios; (b) The number of increased forgotten examples in each epoch (between epoch 50 80 with mutation frequency of 5 epochs).
is gradually increasing to the target sparsity ratio through the decay of p. addition, the mutation process is actually operated indices, to facilitate implementation the edge device.
4 Exploring Data Efficiency in Sparse Training
It has been proven that the amount of information provided by each training example to a network is different, and the difficulty of learning examples also varies. Some training examples are easily learned at early training stage. And once some examples are learned, they will never be "forgotten" (i.e., misclassified) again. Removing those easy and less informative examples from the training dataset will not cause accuracy degradation on the final model. More details discussed Appendix F. However, the exploration of data efficiency in sparse training scenarios is still missing. Due to the dynamic sparsity mask generation in sparse training, it is still unknown that whether the data efficiency can be leveraged for further accelerating sparse training. Therefore, need to first figure out the impact of model sparsity on the number removable training examples (c.g., unforgettable examples), and then discuss the possibility of leveraging data efficiency for accelerating sparse training.
Data efficiency has been studied for the traditional training in literature 220 21 22 23
4.1 Impact of Model Sparsity on Dataset Efficiency
In (23), they proposed to use the number of forgetting events of a training example along the entire training process to indicate the amount of information of the example. The forgetting event is defined as an individual training example transitions from being classified correctly to incorrectly over the training process. It can also be considered as the example is forgotten by the network. An example can be forgotten multiple times. An unforgettable example stands for an example that has never been forgotten once it is correctly classified, and it is considered less informative to network and easy to be learned 23 More details is shown in Appendix F.
In order to study whether data efficiency can be used to accelerate sparse training, we first explore the number unforgettable examples that can be identified after the sparse training process under different sparsity ratios. We test with our three sparse training algorithms MEST (vanilla), MEST+EM, and MEST+EM&S. The Figure We find that there is still a considerable portion (30%~~4%% of training examples in CIFAR- 10 dataset are unforgettable to a highly sparse network (under 95% sparsity). The number of unforgettable examples decreases as the model sparsity increases, and it shows a positive correlation with the model accuracy. When under a high sparsity, the network generalization performance decreases, making some easy examples harder to remember. Moreover, we also observe that a better sparse training algorithm (e.g., MESS+EM&S) leads to more unforgettable training examples, indicating the potential of removing larger portion of training examples and hence a higher acceleration.
(a) shows the results obtained on ResNet-32 32 using CIFAR-I0 dataset.

---

4.2 Will Mutation Lead to Forgetting?
It is natural question to ask that whether the structure change during the training such as our proposed Elastic Mutation will lead to severe forgetting. Thus, we evaluate the number of unforgettable examples in the epoch before and after the mutation. Figure (b), shows the number of forgotten examples increased in each training epoch, which equals the difference of unforgettable examples between two consecutive epochs. Neither the mutation in MEST+EM nor MEST+EM&S causes a notable increase in forgetting. This is because the mutated weights are least important, which have a minor impact on the model accuracy. Detailed results are shown in Appendix F.
4.3 Data-Efficies Sparse Training on the Edge
To identify the less informative training examples, prior work 23 collects the statistics of forgetting events through the entire training process. Then, using compressed dataset to train the network from scratch. Obviously, this is not an efficient, even an unaffordable solution for training on edge devices.
Different from prior works, we intend to integrate the less informative example identification and data-efficient sparse training into one single training process. Our objective is obtain similar final accuracy as a full dataset training within the same number of training epochs. Thus, we propose data-efficient training method (DE), which separate one training process into two phases. For the first training phase, the full dataset is used for a certain sparse training epochs while counting the number of forgetting events for each example. The first phase takes several epochs (c.g.. 70) obtain stable identification results. For the second training phase, partial training examples will be removed from the training dataset and obtain compressed training dataset for the rest of the training process. The number of removed examples depends on the number of examples within a forgetting events threshold. Note that the examples that only be forgotten few times (e-g.. or 2) may also relatively easy to learn, which may also be removed without harming the accuracy. Denoting the full training dataset D, the compressed training dataset D is described as:
D (ar Lrs E and f(x)) S th),,
where the x4 and f*;; represent the i-th training example in the full training dataset and its number of forgetting events occurred in the first training phase, and th is a given threshold.
The Figure 4 shows the status of final accuracy
obtained by the two-phase training approach un-
1st phase spoclss 20 30 40 50 60 70 50 100120
20
30
40
50
60 70 8D 100120
der different sparsity ratios, sparsity schemes, our proposed mutation methods, number of for- gotten thresholds, and epochs for the first phase training. The yellow grids mean that using that number of epoch for the first training phase can achieve similar accuracy as using a full dataset for the entire training process.
protrin
usstructared
block
uesbractarec
block
pallorn
sparsity 40%, t
spansity 997% th
spansity-917%
MESTICE
pattern
We have the following observations: 1) Com- pared to dense model, the sparse models takes longer to identify a good set of removable (less informative and easy) examples; 2) The larger number of examples to be removed, the more training epochs are required for the first train- ing phase. 3) Unstructured sparsity scheme re- quires fewer epochs than fine-grained sparsity schemes (block and pattern). 4) MEST+EM and MEST+EM&S require similar number of epochs. 5) Besides the unforgettable examples, examples with few forgotten times are also removable without harming the final accuracy. More results on other dataset and networks can be found in Appendix F.
uastractured
block
spanity- 95%,
sparsity- 95%%
Fed with lower
Fin with similar acconcy
Figure 4: The epoch number used for the first training phase and its corresponding final accu- racy status under sparsity ratios of 90% and 95% and threshold of 0 and 1. Results are obtained on ResNet-32 using CIFAR-10.
Experimental Results
This section evaluates the proposed MEST framework. The training speed results are obtained using Samsung Galaxy S20 smartphone with Qualcomm Adreno 650 mobile GPU. We measure the
7

---

Table 1: Accuracy comparison with SOTA works using ResNet-32 CIFAR-10 10 and CIFAR-100.
Datasel
Memory Footprint
CIFAR-10
CIFAR-100 (Dense: 74.94)
(Dense: 94.88)
Sparsity ratio
90%
95%
98%
90%
95%
98%
LT
49
dense
92.31
91.06
83.78
68.99
65.02
57.37
SNIP P
dense
92.59
91.01
87.51
68.89
65.22
54.81
GraSP
dense
92.38
91.39
88.81
69.24
66.50
58.43
DeepR 15
spurse
91.62
89.84
86.45
66.78
63,90
58.47
SET [4
sparse
92.30
90.76
88,29
69.66
67.41
62.25
DSR
sparse
92.97
91.61
88.46
69.63
68.20
61.24
MEST (vanilla)
sparse
92.12:+0.13
90.86:0.11
88.78:10.22
69 0.36
67.85
62.58:10.31
MEST+EM
sparse
92.56.10.07
91.15:10.29
89.22.
0.244:10.26
68.43 0.32
64.59
MEST+EM&S
sparse
93.27-1..4
92.44.10.13
90.511..11
71.30.10.31
70.36
67.16.10.25
computation time of round of forward- and backward- propaaaatpoopotioonnnn on a batch of 64 images to denote the training speed. The acceleration rate is the training speed of sparse training normalized to that of dense training. For accuracy, we repeat each experiment times and report the mean and standard deviation of the accuracy results on CIFAR- 10/100. For training speed, we report the average value from 100 runs. We use ResNet-32 and VGG-19 for CIFAR-10 and CIFAR 100 dataset [50), and ResNet-34 and ResNet-50 [51] for ImageNet-2012 (52). Since the ImageNet-2012 is not practical for edge training, we mainly use it for accuracy (detailed explanations are Appendix H). When combining data-efficient two-phase training method that compresses the training dataset on the second phase, we denote our methods as MEST+EM+DE and MEST+EM&S+DE..
Experimental setups: We use the same training epochs as GraSP [10], which is Tend 160 for CIFAR- 10/100 and Fend 150 for ImageNet. We use standard data augmentation, and cosine annealing learning rate schedule is used with SGD optimizer. For CIFAR, we use batch size of 64 and set the initial learning rate to 0.1. For ImageNet, we use batch size of 2048. Our learning rate is scheduled with a linear warm-up for 8 epochs before reaching the initial learning rate value of 2.048. We adopt a uniform sparsity ratio across all the CONV layers while keeping the first layer dense. The other reference works (except SET [4] and RigL [I] that use uniform sparsity) use non-uniform sparsity, which leads to a higher computation FLOPs compared to the uniform sparsity under the same sparsity ratio. An ablation study of using hybrid sparsity schemes and non- non-uniform sparsity ratio on MEST is shown in Appendix K. The hyper-paramen setting for elastic mutation are provided in Appendix G.
5.1 Accuracy Results
The MEST accuracy results are shown in Table [ We include the results at sparsity ratios of 90%. 95%, and 98% with unstructured sparsity scheme. Methods that use dynamic sparse training (DeepR, SET, and DSR) achieve slightly better results compared to fixed- mask sparse training. Compared MEST (vanilla), which uses a fixed mutation ratio along with the training process, our MEST+EM consistently achieves higher accuracy. This proves the effectiveness and importance of our elastic mutation method in sparse training. And our MEST+EM&S further improves the accuracy significantly, especially in extremely high sparsity ratio (e.g. 98%). In terms of peack memory footprint, Lottery Ticket (LT), SNIP, and GraSP are equivalent to dense training. Because the SNIP and GraSP require computing the forward and backward propagation of dense model to find a desired sparse structure. The LT method requires an iterative magnitude pruning process to find the "winning ticket" sparse structure first, it is also considered the same as the dense The VGG-19 results are in Appendix H.
CIFAR-10 and CIFAR-100:
model in an end-to-end training scenario (49 53 54].
ImageNet- Table 2 shows the accuracy results and training FLOPS using ResNet-50. RigL recent milestone of dynamic sparse training works, which has considerable improvements compared to previous works. To make a fair comparison with RigL, we scale our training epochs to have the same or less overall training FLOPs as the RigL. We also increase the training effort for MEST by 1.7x, which is 250 epochs, to compare with the Rigl. with 5x longer training, which 500 epochs as reported in [I]. With the same or less training FLOPS, our proposed MEST framework consistently outperforms other baselines. When using our data effective training method,
8

---

Table 2: Accuracy comparison using ResNet-50 on ImageNet using unstructured sparsity scheme.
Method
Training FLOPS (xel8)
Inference FLOPS
Top-1 Aceuracy (%)
Training FLOPS (xel8)
Inference FLOPS
Top-1 Accuracy (%)
(xc9)
(xe9)
Dense
4.8
76.9
Sparsity ratio
80%
SNTP 9
1.67
2.8
69.7
0.91
1.9
62.0
GraSP [10
1.67
2.8
72.1
0.91
1.9
68.1
DeepR 15
n/a
n/a
71.7
n/a
n/a
70.2
SNF$
n/a
n/a
73.8
n/a
n/a
72.3
DSR
1.28
3.3
73.3
0.96
2.5
71.6
SET
0.74
1.7
72.6
0.32
0.9
70.4
RigL.
0.74
74.6
0.39
0.9
72.0
RigLax
3.65
76.6
0.9
75.7
MEST +EM&S
0.74
1.7
75.11
0.39
0.9
72.37
OEST
0.74
75.39
0.9
72.58
MESTOSx EM&S+DE
0.70
0.9
72.36
MEST+EM
1.10
1.7
75.75
0.48
0.9
73.63
MEST+EM&S
1.27
1.7
75.73
0.65
0.9
75.00
MEST-FM&S-DE
1.17
1.7
75.70
0.60
0.9
75.10
MEST +EM
1.84
1.7
76.71
0,80
0.9
75.91
MEST +EM&S
2.15
1.7
77.19
1.11
0.9
76.13
MEST +FM&S+DR
1.96
1.7
77.11
1.01
0.9
76.08
training FLOPS can be further reduced while maintaining the same accuracy using the full dataset. Note that the RigL exploits the dense model gradients to dynamically select the model structure during the sparse training process, which requires frequent dense backpropagations to calculate the dense gradients, and it is not memory-econome for Edge devices. The more analysis and results for ResNet-34 are shown in Appendix H.
Exploring Sparsity Schemes. Figure 5 (a) and (b) illustrates the accuracy by different sparsity schemes, i.e., unstructured, structured (channel), and fine-grained structured (block and pattern) when using our MEST+EM and MEST+EM&S, respectively. block-based sparsity scheme, we set block size as (4. 1). And in pattern-based sparsity scheme, we use 8 sparse patterns according to (36).
We evaluate MEST framework with a sparsity ratio ranging from 10% 98%. Note that due to structural nature of pattern-based pruning, its sparsity ratio must be at least 55.6% (see Appendix A). To make fair comparison, we only choose the reference works that can maintain both sparse weights and gradients along the entire training process. Figure (a) and (b) shows that all other sparsity schemes outperform channel sparsity scheme as expected, but the accuracy of channel sparsity scheme can be improved with weight elastic mutation. Our MEST+EM results show that the accuracy of our unstructured scheme results are higher than reference works and our block-based and pattern- based scheme results under all sparsity. The block-based and pattern-based schemes achieve similar accuracy as our unstructured scheme when sparsity lower than 80%. With our MEST+EM&S, the accuracy of all sparsity schemes are boosted and outperforms the reference works.
5.2 Memory Footprint and Training Acceleration by Sparsity and Pata-Efficient Training
In Figure 5 (c), compare the model accuracy, training acceleration, and memory footprint among our MEST and representative SOTA works, i.c.. SET. DSR, SNIP, and GraSP. We show the results using ResNet-32 CIFAR- 100 with 90% sparsity. The training acceleration results normalized to dense training. The area of the circles represents the relative costs of the memory footprint (the smaller the better).
With unstructured sparsity, all reference works and our unstructured sparsity (without DE) results can only achieve minor training acceleration (1.04x ~ 1.27x), even under such high sparsity ratio. Because unstructured sparsity leads to irregular memory access which introduces significant execution overhead. Moreover, the dense model can take advantage of Winograd [48] to significantly accelerate the computation speed, but cannot be applied sparse model. For our block-based and pattern-based sparsity schemes, without applying data-efficient training, the acceleration

---

CIFAR-10
2,5
2.25
1.73
CLsSP
SKIP
ENIT
8.5
5012
Gudpp
Skick
DS3
Refacaas
250
69.5
71.5
MEST 150 pp
SE5T 25655 1993097
Accency (76)
GRSP MEST-EM
MEST DE
SET
MEST-EMMSS
MEST-EMAS-DDE
04)
(8)
Figure 5: Results obtained using ResNer-32 on CIFAR-100. We choose the reference works that can maintain both sparse weights and gradients along the entire training process. (a) and (b) Accuracy results of the proposed MEST framework using different sparsity schemes and sparsity. (c) Comparison with representative SOTA works in accuracy, training acceleration rate, and memory footprint. Sparsity ratio is 90% for all results. The acceleration rate is normalized with respect to
dense training. The size of the circles represents the relative cost of the memory footprint. We use th = 0 as the threshold for DE.
rates are greatly increased and achieve up 2.3x acceleration compared to the dense training while maintaining comparable accuracy. Our data-efficient training approach can effectively provide an extra speedup all our results. The speedup is from 10% 15% while not compromising the accuracy. The acceleration from data-efficient training is much higher on the CIFAR-I0 dataset 200.%%~22..5.
since more examples are unforgettable and can be removed (more details in Appendix H). Comparing with SNIP, GraSP, SET, and DSR, the rest-performant MEST increases accuracy by 1.91%, 1.54%, 1.14%, and 1.17%; achieves 1.76x, 1.65x, 1.87 x, and 1.98x x training acceleration rate; and reduces the memory footprint by 8.4x, 8.4x, 1 1.2x, and 1.2x, respectively.
From the memory footprint perspective, SNIP and GraSP involve dense model during pruning initialization, their memory footprints are considered the same as the dense model. Since the fewer indices are needed, the block-based sparsity and pattern-based sparsity under both MEST+EM and MEST+EM&S methods achieve a smaller memory footprint than all reference works and our unstructured sparsity scheme. More detailed discussion is in Appendix B. And a discussion about why it is critical to be memory-economii in edge training is shown in Appendix J.
Our results show a clearer advantage compared to the reference works. Even without DE accelera- tion, when using MEST+EM with block-based or pattern-base basten--based sparsity, or using MEST+EM&S with block-based sparsity, our results still outperform all reference works in all accuracy, training acceleration, and memory footprint aspects.
The pattern-based sparsity shows a consistently better performance in acceleration than block-based sparsity. However, the accuracy comparison between pattern-based sparsity and block-based sparsity is varied according to the sparsity ratio and dataset. Since the mattern-based sparsity is only applicable to 3x3 CONV layers, for the network with different types of layers, a layer-wise sparsity scheme assignment is desired. Investigations of hybrid sparsity schemes are provided in Appendix K.
Discussion.
On the other hand, since both dataset compression and model sparsity make the trade-off between accuracy and acceleration, is interesting to investigate the performance of different combinations of these two methods (more details in Appendix L).
Conclusion
This paper proposes a Memory-Econone Sparse Training (MEST) framework with enhancements by Elastic Mutation and Soft Memory Bound Elastic Mutation. Then, this paper systematically investigates the sparse training problem with respect to the sparsity schemes. We implement a prototype design on a mobile device to accurately measure the training speed performance. We investigate and incorporate the data-efficient training in sparse training scenario to further boost the acceleration. With MEST framework, feasible solution is provided for sparse training on edge devices with superior performance accuracy, speed, and memory footprint.
10

---

Acknowledgment
This work is partly supported by the National Science Foundation CCF-1937500, CCF- 173371,,,,, and CCF-2047516 (CAREER), Army Research Office/Army Research Laboratory via grant W91 INF. 20-1 10-1-0167 (YIP) to Northeastern University, and Jeffress Trust Awards in Interdisciplinary Research to William & Mary. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF, ARO, or Thomas F. and Kate Miller Jeffress Memorial Trust.
References
[1] Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In Advances in Neural Information Processing Systems (NeurIPS), pages 1379 1387, 2016.
[2] Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin H-i- Lai, Vlad Morariu, Xintong Han. Mingfei Gao, Ching Chng Lin, and Larry Davis. Nisp: Pruning networks using neuron importance score propagation. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 9194-9203, 2018.
[3] Wei Wen, Chunpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pages 2074-2082, 2016.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In International Conference on Learning Representations (ICLR), 2019.
[5] Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations (ICLR), 2017.
[6] Gabriel Bender, Pieter- Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le. Understanding and simplifying one-shot architecture search. In International Conference on Machine Learning (ICML), pages 550 509,5599.000 PMLR, 2018.
[7] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning (ICMI.), pages 4095-4104, PMLR, 2018.
[8] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4780-4789, 2019.
[9] Namhoon Lee, Thalaiyasingam Ajanthan. and Philip Torr. Snip: Single-sho shot network pruning based on connection sensitivity. In International Conference on Learning Representations (ICLR), 2019.
[10] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations (ICLR), 2020.
[11] Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning (ICMI., pages 2943-2952. PMLR, 2020.
[12] Tim Dettmers and Luke Zettlemoyor. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.04840, 2019.
[13] Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning (ICML), pages PMLR, 2019.
[14] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone. Phuong H Nguyen, Madeleine Gibeseu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Communications, 911):1-12, 2018.
[15] Guillaume Bellee, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep net-works. International Conference on Learning Representations (ICLR), 2018.
[16] Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representa- tions (ICLR), 2016.
[17] Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In International Conference on Machine Learning (ICML), pages 2498-2507. PMLR, 2017.
[18] Bin Dai, Chen Zhu, Baining Guo, and David Wipt. Compressing neural networks using the variational information bottleneck. In International Conference on Machine Learning (ICML), pages 1135-1144 PMLR, 2018
11

---

[19] Maurice Yang. Mahmoud Faraj, Assem Hussein, and Vincent Gaudet. Efficient hardware realization of convolutional neural networks using intra-kereel regular pruming. In 2018 IEEE 48th International Symposium on Multiple-Valeee Valued Logic (ISMVL). pages 180-185. IEEE, 2018.
[20] Yoshua Bengio, Yann LeCun, et al. Scaling learning algorithms towards ai. Large-scale kernel machines, 34(5):1-41, 2007.
[21] M Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models, In NIPS, volume 1. page 2, 2010.
[22] Yang Fan, Fei Tian, Tao Qin, Jiang Bian, and Tie- Yan Liu. Learning what data to learn. arXiv preprint 1eXivv/702.080000
2017.
[23] Mariya Toneva,
Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning, arXiv preprint 112::1812.051158 2018.
[24] Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruning method for deep neural network compression. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 5058-5066, 2017.
[25] Xuanyi Dong and Yi Yang. Network pruning via transformable architecture search. In Advances in Neural Information Processing Systems (NewrIPS), pages 759-770, 2019.
[26] Hengyuan Hu, Rui Peng, Vu-Wing Tai, and Chi-Keung Tang. Network trimming: A data-driven neuron pruning approach towards efficient deep architectures. arXiv preprint 1007v:600.0035550 2016.
[27] Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In P Proceedings of the IEEE International Conference Computer Vision (ICCV), pages 1389-1397, 2017.
[28] Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. In International Joint Conference Artificial Intelligence (IJCAI), 2018.
[29] Tuanhui Li, Baoyuan Wu, Yujiu Yang. Yanbo Fan, Yong Zhang, and Wei Liu. Compressing convolutional neural networks via facttoized convolutional filters. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3977-3986, 2019.
[30] Yang He, Ping Liu, Ziwei Wang. Zhilan Hu, and Yi Yang. Filter pruning via geometric median for deep convolutional neural networks acceleration. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4340-4349, 2019.
[31] Kirill Neklyudov, Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Structured bayesian pruning via log-normal multiplicative noise. In Advances in Neural Information Processing Systems (NeurIPS), pages 6778-67787 6787, 2017.
[32] Tianyun Zhang, Shaokai Yc, Xiaoyu Feng, Xiaolong Ma, Kaiqi Zhang, Zhengang Li, Jian Tang, Sijia Liu, Xue Lin, Yongpan Liu, al. Structadmm: Achieving ultrahigh efficiency in structured pruning for dnns. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[33] Xiaolong Ma, Sheng Lin, Shaokai Ye, Zhezhi He, Linfeng Zhang, Geng Yuan, Sia Huat Tan, Zhengang Li, Deliang Fan, Xuehai Qian, et al. Non con-sttrcttred dnn weight pruning is it beneficial in any platform? IEEE Transactions on Neural Networks and Learning Sysiems, 2021.
[34] Xiaolong Ma, Fu-Ming Guo, Wei Niu, Xue Lin, Jian Tang, Kaisheng Ma, Bin Ren, and Yanzhi Wang. Peonv: The missing but desirahle sparsity in dnn weight pruning for real-time execution on mobile devices. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5117-5124, 2020.
[35] Wei Niu, Xiaolong Ma. Sheng Lin, Shihao Wang, Xuehai Qian, Xue Lin. Yanzhi Wang. and Bin Ren. Patdnn: Achieving real-time dnn execution on mobile devices with pattern-base weight pruning. In Proceedings of the Twenty- Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 907-922, 2020.
[36] Xiaolong Ma, Wei Niu, Tianyun Zhang, Sijia Liu. Sheng Lin, Hongjia Li, Wujie Wen, Xiang Chen, Jian Tang, Kaisheng Ma, et al. An image enhancing patternbaased sparsity for real-time inference on mobile devices. In Proceedings of the European conference on computer vision (ECCV), pages 629-645. Springer, 2020.
[37] Peiyan Dong, Siyue Wang, Wei Niu, Chengming Zhang, Sheng Lin, Zhengang Li, Yifan Gong, Bin Ren, Xue Lin, and Dingwen Tao. Rimobile: Beyond real-time mobile acceleration of rans for speech recognition. In 2020 57th ACM/IEEE Design Automation Conference, pages 1-6. IEEE, 2020.
[38] Masuma Akter Rumi, Xiaolong Ma. Yanzhi Wang, and Peng Jiang. Accelerating sparse enn inference on gpus with performance-awee aware weight pruning. In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, pages 267-278, 2020.
12

---

[39] Chengming Zhang. Geng Yuan. Wei Niu, Jiannan Tian, Sian Jin, Donglin Zhuang. Zhe Jiang, Yanzhi Wang. Bin Ren, Shuaiwen Leon Song, and Dingwen Tao. Clicktrain: Efficient and accurate end-to-end deep learning training via fine-grained mnchitectur--preervvii pruning. Proceedings of the ACM International Conference on Supercomputing. ICS '21, page 266-278, New York, NY, USA, 2021. Association for Computing Machinery.
[40] Wei Niu, Zhengang Li. Xiaolong Ma, Peiyan Dong, Gang Zhou, Xuehai Qian, Xue Lin, Yanzhi Wang. and Bin Ren. Grim; A general, real-time deep learning inference framework for mobile devices based on fine-grained structured weight sparsity. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[41] Hui Guan, Shaoshan Liu, Xiaolong Ma, Wei Niu, Bin Ren, Xipeng Shen, Yanzhi Wang, and Zhao. Cocopie: enabling real-time ai on off-the-shelf mobile devices via compresioon-conplatioo co-design. Communications of the ACM, 64(6):62-68, 2021.
[42] Sangkug Lym. Esha Choukse, Siavash Zangeneh, Wei Wen, Sujay Sanghavi, and Mattan Erez. Prunetrain: fast neural network training by dynamic sparse model reconfiguration. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 2019.
[43] Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang. Xiaohan Chen, Yingyan Lin, Zhangyang Wang, and Richard G. Baraniuk, Drawing carly-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations (ICLR), 2020.
[44] Mohit Rajpal, Ychong Zhang. Bryan Kian, and Hsiang Low. Balancing training time vs. performance with bayesian early pruning. In OpenView, View, 2020.
[45] Hidenori Tanaka, Daniel Kunin, Daniel I. Yamins, and Surya Ganguli. Pruning neural networks without any data by itcratively conserving synaptic flow. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
[46] Paul Wimmer, Jens Mehnert, and Alexandru Condurache. Freezenet: Full performance by reduced storage costs. In Proceedings of the Asian Conference Computer Vision (ACCV), 2020.
2020.
[47] Joost van Amersfoort, Milad Alizadeh, Schastian Farquhar, Nicholas I Lane, and Yarin Gal. Single shot structured pruning before training. arXiv preprint arXiv:2007.00389 2020.
[48] Andrew Lavin and Scott Gray. Fast algorithms for convolutional neural networks. In Pruceedings of the IEEE Conference on Compuder Vision and Pattern Recognition (CVPR), pages 4013-4021, 2016.
[49] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. International Conference on Learning Representations (ICLR), 2019.
[50] Alex Krizhevsky, Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
[51] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[52] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scall hierarchical image database. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 248-255, 2009.
[53] Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, and Yanzhi Wang. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot?, 2021.
[54] Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: Is it desirable not? In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7011-7020 PMLR, 18-24 Jul 2021.
13


Reviews:
[{"review_id": "zjkAEB5wn0N", "reviewer": "Reviewer_HrFw", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality and significance\nThe 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.\n\n## Quality and clarity\nThe 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:\n\n(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.\n\n(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.\n\n(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.\n\n(4) To confirm some details:  \n\n(a) According to algorithm 1, will the proposed techniques be applied on gradients and activations as well?\n\n(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?\n\nI'm willing to raise my scores if the above concerns are properly addressed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the main review section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "odqoNmnPys8", "reviewer": "Reviewer_wx9R", "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. \n\nThe 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.\n\nLastly, 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. \n\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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. \n\nThis 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. \n\nIn 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?\n\nTable 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. \n\nSection 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? \n\nOn 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.\n\nIn 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?\n\nFigure 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? \n\nTo 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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. \n\nThe 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. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GrTdpJovTe0", "reviewer": "Reviewer_Knx5", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality and Significance: \nDifferent 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.\n\nI 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.\n\nAnother 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.\n\nQuality and Clarity:\nThe 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.\n\nOverall Comments:\nOverall, 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.\nTheir proposed methods seem more practical. That is why I think this paper can be impactful for both industry and academia.\n\nImprovements:\nFor 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.\n\nThere 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.\n\nQuestions：\nHow do you determine the frequency of the mutation? What is the impact if you have a higher or lower mutation frequency?\n\nI am curious about how to mutate the model topology if you avoid storing a dense model on the edge devices?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "11ER-Ywg6s", "reviewer": "Reviewer_KRc4", "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). ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nThis 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:\n\n_ 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). \n\n_ The related work on fixed sparsity (Section 2.2.1) is missing few papers which have been published well before SNIP - Ref [9].\n\n_ 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.\n\n**Quality**\n\nThe 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. \n\n**Clarity**\n\nThe 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.\n\nActually, 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. \n\n**Significance**\n\nI believe that this paper has the potential of becoming a landmark in sparse training with dynamic sparsity. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)