Effective Model Sparsification by Scheduled Grow-and-Prune Methods
Authors: Xiaolong Ma
Minghai Qin
Fei Sun
Zejiang Hou
Kun Yuan
Yi Xu
Yanzhi Wang
Yen-Kuang Chen
Rong Jin
Yuan Xie
Venue: ICLR 2022 Poster (2022)

Abstract: Deep neural networks (DNNs) are effective in solving many real-world problems. Larger DNN models usually exhibit better quality (e.g., accuracy) but their excessive computation results in long inference time. Model sparsification can reduce the computation and memory cost while maintaining model quality. Most existing sparsification algorithms unidirectionally remove weights, while others randomly or greedily explore a small subset of weights in each layer for pruning. The limitations of these algorithms reduce the level of achievable sparsity. In addition, many algorithms still require pre-trained dense models and thus suffer from large memory footprint. In this paper, we propose a novel scheduled grow-and-prune (GaP) methodology without having to pre-train a dense model. It addresses the shortcomings of the previous works by repeatedly growing a subset of layers to dense and then pruning them back to sparse after some training. Experiments show that the models pruned using the proposed methods match or beat the quality of the highly optimized dense models at 80% sparsity on a variety of tasks, such as image classification, objective detection, 3D object part segmentation, and translation. They also outperform other state-of-the-art (SOTA) methods for model sparsification. As an example, a 90% non-uniform sparse ResNet-50 model obtained via  GaP achieves 77.9% top-1 accuracy on ImageNet, improving the previous SOTA results by 1.5%. Code available at: https://github.com/boone891214/GaP.

Published as a conference paper at ICLR 2022
EFFECTIVE MODEL SPARSIFICATION BY SCHEDULED METHODS
Xiaolong Ma Minghai Qin Fei Sun Zejiang Hou?, Kun Yuan?, Yi Xu',
Yanzhi Wang', Yen-Kuang Chen', Rong Jin", Yuan Xie
Northeastern University 2 DAMO Academy, Alibaba Group Princeton University
4 Dalian University of Technology
ABSTRACT
Deep neural networks (DNNs) are effective in solving many real-world problems. Larger DNN models usually exhibit better quality (c.g., accuracy) but their exces- sive computation results in long inference time. Model sparsification can reduce the computation and memory cost while maintaining model quality. Most existing sparsification algorithms unidirectionally remove weights, while others randomly or greedily explore a small subset of weights in each layer for pruning. The lim- itations of these algorithms reduce the level of achievable sparsity. In addition, many algorithms still require pre-trained dense models and thus suffer from large memory footprint. In this paper. we propose a novel scheduled grow-and- -runn (GaP) methodology without having to pre-train a dense model. It addresses the shortcomings of the previous works by repeatedly growing a subset of layers to dense and then pruning them back to sparse after some training. Experiments show that the models pruned using the proposed methods match or beat the quality of the highly optimized dense models at 80% sparsity on a variety of tasks, such as image classification, objective detection, 3D object part segmentation, and translation. They also outperform other of-thh--rrttt (SOTA) methods for model sparsifica- tion. As an example, a 90% non-uniform sparse ResNet-50 model obtained via GaP achieves 77.9% top-1 accuracy on ImageNet, improving the previous SOTA results by 1.5%. Code available at: https:/ htt///gtttubbu wegpthuu.cmm//oooooooooo. http:/oooo//oe1211111111
INTRODUCTION
Deep neural networks (DNNs) have achieved great performance in many real-world scenarios. However, the large computation and memory requirements of deep neural networks discourage them from being applied to broader applications on resource-limited devices. Model compression via weight pruning is a popular research topic, where a large proportion of weights are set to zero, leading to significant reduction in both memory and computation. The introduction of sparse tensor cores in the NVIDIA A100 GPU NVIDIA 2020b) brings weight pruning into mainstream.
Early works on weight pruning generally follow prune-from-denss methodology (Guo et al. 2016 Yu et al.) 2018 Wen et al. 2016; Liu et al., 2201bb] Pham et al./ 2018 Real et al. 2019). which usually requires phases of training: pre-train dense model, prune it to sparse, and fine-tune it. In such methodologies, the one-shot or iteratively pruning from a well-trained DNN can only remove weights, which lacks the flexibility of growing back weights that considered unimportant early in the training process but showed to be significant later in training. On the other hand, early-stage pruning methods (Lee al. 2019 Wang et al.) 2020 You al. 2020 avoid training dense models to converge. However, those sparse masks (i.c.. the binary matrix in which zero value removes the corresponding weight entry from the model) are prematurely fixed, resulting in inferior model quality. Methods based on sparse mask exploration, such as DeepR (Bellec et al. 2018), SET (Mocanu al. 2018), DSR (Mostafa & Wang 2019), and RigL. (Evei et al.) (2200) maintain the target sparsity in all layers throughout the training process and selectively explore small fraction of the weights
Equal Contribution.
This work is partially done during Xiaolong Ma's internship and Yi Xu's working period at Alihaba Group

---

Published as a conference paper at ICLR 2022
Initialization
C-GaP Training
Step
Step 3
dense
sparse
Random Weights Mask
park2
(very low accuracy model)
part 3
Prune
port-
Grow
par-11
Trained weights + updated mask (high accuracy model)
layers divide into partitions
Step
pan-
DNN weights
Mask
output
Figure 1: Overview of the cyclic GaP (C-GaP) training method. We assume 4 partitions in model are grown and pruned in a cyclic order. Only one partition is kept dense during training. After K steps, the dense partition is pruned and the whole model is fine-tuned obtain the sparse model.
periodically. The explored weights are chosen based random greedy heuristics, leading to limited coverage of sparse patterns and consequentially sub-optimal model quality.
In order to overcome the shortcomings of the previous solutions, we propose scheduled grow-and- prune (GaP) methodology. does not require a dense model any time during the training process, leading to largely-reduue
memory footprints. Meanwhile, the sparse mask of layer is updated after exploring all weights in the same layer, resulting in better mask-update efficiency. It targets to obtain the best quality sparse model under runtime budget. Since some large models may be compressed below target latency before being deployed in the wild to thousands of devices and inferenced billions of times per day (Hazelwood al. 2018 Wu al. 2019). spending a bit more time in training to find a better model is well rewarded.
The scheduled GaP methodology divides DNN into several partitions composed of contiguous layers. During model training, one of the sparse partitions is grown to dense while the rest remain sparse. After some epochs of training, the previously dense partition is pruned to sparse, and an alternate partition is grown to dense. This process is repeated so that all partitions are grown to dense and pruned back to sparse multiple times. If the partitions are grown dense one by one sequentially, it is called the cyclic GaP method (as shown in Figure I.. If the model is replicated to multiple machines with different dense partitions, is called the parallel GaP method.
The GaP methods are carefully scheduled to explore all weights efficiently, which is not guaranteed in the existing mask exploration methods. We illustrate their differences by an example in Figure 2 In the scheduled GaP methods, all weights to be grown (or be pruned) belong the same partition. All weights in the model are explored when every partition is grown to dense and pruned to sparse. On the other hand, in the random greedy exploration methods, the grown and pruned weights are distributed across all layers and they do not guarantee that all weights are explored, e.g. the connection between 1st input neuron and 3rd neuron in the first layer is not explored in Fb Random sparse mask exploration and our scheduled GaP methods are like sampling operations with replacement and without replacement (Basu 1958). The former requires a lot more samples to achieve the same weight coverage as the latter. Please see Appendix [ for an illustrative example.
The contribution of this paper summarized as follows.
We propose two GaP methods such that they do not require to train dense models any time throughout the training process, reducing the training memory footprints.
Sparse models obtained by the proposed GaP methods outperform the SOTA sparsification algo- rithms on a wide variety of deep learning tasks, including 2D image recognition, object detection, 3D object part segmentation, and machine translation.
For all four tasks, the proposed GaP methods surprisingly generate sparse models that match or even exceed the dense counterparts at 80% sparsity.
We provide theoretical guarantees for the GaP method and clarify its convergence property. In particular, we justify the influence of the mask-induced emror.
2

---

Published as a conference paper at ICLR 2022
Step
Step2 2
Step 3
Stee
Grow
Train
Prune
Grow
Prune
Grow
Prune
(a) Scheduled mask exploration
prune
Grown
Random/Greedy mask exploration
Figure 2: Comparison between (a) the scheduled mask exploration and (b) the random/greedy mask exploration. In (a), the weights to be grown (or pruned) are in the same layer and the growing phase covers all weights in that layer. In (b), they may be in different layers and the growing phase does not guarantee coverage during training.
Algorithm 1: C-GaP training flow.
Input: An L-layer model with uninitialized weight O pruning ratio r. Output: An L-layer sparse model satisfying the target sparsity requirement.
Initialize fa;; O m) with random weights θ and random masks m that satisfy the sparsity requirement.
Divide all layers into partitions, denoted by S,, E K.
step =
while step < K do
Partition to grow index i step mod partition to prune index j <- (step 1) mod s.
Prune @ and update m by (0%, m²] ArgPruneTo("",,
Grow 0 by m +- ArgGrowTo(@
Train the model fa;; e @ m) for 7 epochs.
step step +
10 Denote final dense partition by Sa-
Prune 9 and update na by [@Su, m&]] ArgPruneto(0 r).
12 Fine-tune [æ; θ @ m) for T' epochs.
2 METHODOLOGY
In this section, we describe the scheduled grow-and-prune (GaP) methods in detail. The process starts from a randomly initialized model. First, weights are pruned randomly to reach the target sparsity, iec a random sparse mask is applied to the weights. Then, the model is divided into k partitions and each partition is grown and pruned separately. the following two sub-sections, two variants of the GaP methods are described in detail.
2.1 CYCLIC GAP
As shown in Figure [ the cyclic GaP (C-GaP) method rotates the dense partitions among all partitions (k 4 in Figure Starting from all partitions with random sparse masks, the first partition grown to a dense one. All weights in the first partition and the masked weights in the remaining partitions
trained for a few epochs (Step 1). Then, the first partition is pruned to sparse (Step 2). Next, we apply the same strategy to the second partition, then continue iterating over all partitions. When all layers are eyclically grown and pruned once after k steps, we call it one round. This process is repeated K times.
Algorithm describes this process in more detail. In Line we use f(r; θ) represent an L-layer deep neural network model, where ② E R are M trainable weights and ir are training samples. is
sparse model is denoted as fa; θ O m), where denotes element- wise multiplication. binary mask m E 1),1)AM where a zero in m means that the corresponding weight in is fixed to be zero and in means that the corresponding weight in O is free be updated.

---

Published as a conference paper at ICLR 2022
Inisalization
P-GaP Training
dense
Rendom Weighte Mark
sparse
model)
pat5
pat1
Gutput current step
Duplicate
Node
Trained welghts - updated mask (Nih accuracy model)
n layara partitonss
yes
Maki
Shop K
p4114
DNN weights
Mask
Fine-lune output
Step
Figure 3: Overview of the parallel GaP (P-GaP) training method. We assume 4 training nodes are used for the 4 partitions, which are grown in parallel for T epochs. At the end of each step, the dense parts in the nodes are combined, followed by a pruning back to a sparse model. After K steps, the model is fine-tuned.
In the C-GaP, all layers of the model (1, L} are divided into x subsets S1, ,...S......-....... Sx-1-
where N is an integer between I and L, as shown in Line 2. Let o and m2 denote the subset of trainable weights and their masks. Consequently, θ is divided into partitions, denoted by g SSe-1. For the i-th partition @5, we denote its mask by m
Then the grow and prune process is iterated K times (Line 4). First, the indices of the partitions to grow and prune are calculated (Line 5). They are determined in a cyclic order. Then, the selected dense partition is pruned to sparse (Line 6). It prunes the partition @ with a pruning ratio r. In the mean time, the next sparse partition is grown to dense (Line 7). It sets the mask m to be all ones such that all weights @ are free to be updated during training. After that, the model is trained for T' epochs (Line 8). After the entire grow-and -nn-und-rrune process is finished, the final dense partition is pruned to sparse (Line 11) and the model is fine-tuned get the final trained sparse model (Line 12).
2.2 PARALLEL GAP
In this section, we introduce the parallel GaP (P-GaP) as a flexible and highly efficient complement the C-GaP sparse training method when sufficient training resources are available, as described in Figure 3 Unlike the C-GaP method where partitions are grown and pruned serially in one machine, the G-GaP method distributes the model to K machines. Each grows different partition to dense and trains the model in parallel. Then, the trained dense partitions are combined to a dense model and pruned to a sparse one again. As a result, the P-GaP method utilizes k more machines, but its training time is also times shorter than the C-GaP method. Since each server trains the model independently, the inter-server communication only occurs when the dense parts are combined to synchronize their learned weights once every few epochs. Thus its impact performance is negligible. Each pair of distribution and combining form one round in the P-GaP. Unlike C-GaP, one round of P-GaP consists of only one step. The detailed P-GaP method is shown in Algorithm 2 and illustrated in Figure 4 (b) in Appendix D
Some of the differences between the parallel GaP and the conventional distributed training are listed as follows.
1. In P-GaP, data communicates across different server nodes every T epochs of training. It is far less frequent than conventional distributed training, which requires communications and synchronization in every mini-batch. Therefore, the data bandwidth between the nodes remains minimal.
2. In P-GaP, each node can use the single-node hyper-parameters to train the sparse models. It does not require excessively large batch-size fully utilize the computing resource.
3. Different from data parallelism, model parallelism, and pipeline parallelism, the P-GaP explores another dimension of parallelism when training sparse models, which we call it mask parallelism. This implies that masks in different partitions are less correlated and can be searched separately.
4

---

Published as a conference paper at ICLR 2022
Table Results of sparse ResNet-50 models ImageNet.
Sparsity ratio: 80%
Sparsity ratio: 90%
Total
Method
Distribution
epochs
Top-1 (%)
FLOPS (xe9)
Top-1 Ace (%)
FLOPS
(xe9)
Dense
NVIDIA
2020a
Top-1 accuracy: 78.2, FLOPS: 8.2xc9
Prune-fe from-
uniform
750/1250*
77.1
75.8
0.8
SNTP
Lee et al. 2019
uniform
100
72.0
1.7
67.2
0.8
SET
Mocanu et al. 2018
uniform
100
72.9
1.7
69.6
0.8
SET
uniform
1200
76.4
1.7
74.5
0.8
RigL
Evci et al. 2020
uniform
100
74.6
1.7
72.0
0.8
RigL.
uniform
100
74.6
72.5
0.8
RigLsx
Evei ct al. 2020
uniform
500
76.6
75.7
0.8
RigLsx"
uniform
500
76.9
0.8
RigL1zx"
uniform
1200
76.0
0.8
C-GaP
uniform
990
77,9
76.3
0.8
P-GaP
uniform
1110
77.5
76.1
0.8
GMP Gale et al.
2019
non non-uni uniform
135
76.5
n/a
75.0
n/a
SNIP
Lee et al. 2019
non-uniform
100
69.7
61.9
1.9
GraSP
Wang ct al. 2020
non- non-uniform
150
72.1
1.9
DeepR
[Bellec el al.
non- non-uniform
71.7
n/a
SET
Mocanu al.
non-uniform
100
72.6
70.4
0.8
DSR
Mostata Wang
2019
uno-uniform
100
73.3
2.9
71.6
0.8
DPF
2020b
uon-uniform
90
75.1
n/a
n/a
RigL EEver 2020
ERK
100
75.1
3,4
73.0
2.0
Rigl.
ERK
100
75.4
3.4
73.9
2.0
RigLsx
[Evci et al 2020
ERK
500
77.1
3.4
76.4
2.0
Riglaxx
ERK
500
77.4
3.4
76.3
2.0
RigLi2x"
ERK
1200
77.4
3.4
76.8
2.0
C-GaP
non-uniform
990
78.1
2.7
77.9
2.0
750 epochs for 80% sparsity and 1250 epochs for 90% sparsity (plcase see Appendix B.1 For details).
Our implementation (please refer to Appendix B.2 for implementation details).
Following the convention in (Evci al. 2020 multiplication and addition counted as two operations.
3 EXPERIMENTAL RESULTS
This section evaluates the proposed C-GaP and P-GaP sparse training methods on different machine learning tasks. Since goal is to search for the optimal sparse models to speed up inference, report the best model accuracy obtained using the GaP methods for all models. We compare our GaP method with the state-of otherwise specified, all prune-from-dee from-dense are implemented using magnitude-bart based iterative pruning schedule described in GMP (Zhu & Gupta 2017 Gale et al. 2019). More ablation experiments partition number, partition scheme, different sparsity granularity using GaP, and FC layer pruning are shown in Appendix
ootiee-fffhheaatttt arts, well as implemented prune- prune-from-
results. If not
All of our experimental results are trained and inferenced using PyTorch in the machines with NVIDIA-VIO0 GPUs. The cyclic GaP is trained in one training node and the parallel GaP trained in & training nodes, where is the number of model partitions. In the pruning stage of the GaP method, the weights with the lowest magnitudes are pruned zero. Note that our experiments. only the weights for convolution. matrix- The weights related to biases and batch-normalizzttoo are kept dense, as they are critical for model quality but only contribute to tiny fraction of the inference FLOPs. For uniform sparsity, we prune individual layer separately by sorting all weights the layer based on their magnitudes, and prune away any weight whose magnitude is below the percentile described as the sparsity level. Thus, all layers receive the same sparsity. For non-uniform sparsity, the pruning process similar, but the weights in the entire model are sorted together. Thus, the sparsity level in different layers may differ, with the more important layers pruned less than the trivial layers. We list the implementation details and
and matrix-matee matrix multiplications are made sparse.
settings for all tasks in Appendix B
5

---

Published as a conference paper at ICLR 2022
3.1 IMAGE CLASSIFICATION RESNET-50 ON IMAGENET
Table I compares the accuracy between using the GaP methods and the previous works. The ResNet- 50 is divided into four partitions by the last three downsampling stages. For non-uniform sparsity, all layers are sparsified. For the uniform sparsity, the first convolutional layer with 7 x kernels is kept dense, the same in Evei et al. (2020). The fully connected (FC) layer only contributes 0.5% of FLOPs, thus it is also kept dense (sparse FC layer has similar accuracy with dense FC layer, please check the ablation results in Appendix A
To ensure fair comparison, we perform the following demonstrations in addition to the original baseline results. We include the SNIP (Lee et al., 2019) and SET (Mocanu et al. 2018) results in uniform sparsity that are reproduced in Evci et al. (020). We also implement the RigL and Rigl-sx (Evei et al. 2020) using our code base on Py (please refer to Appendix [..2 for details). In Table our reproduction achieves equivalent or higher accuracy than the reported the paper. Based on that, we extend the RigL training time by 12x to match the GaP method. Additionally, SET shares similar method with RigL, thus also implement and extend SET training by 12x.
We observe that the improvement over RigLax (Evci et al. 2020 is 1.3% (77.9% vs. 76.6%) at uniform 80% sparsity, and 0.6% at 90% uniform sparsity. The C-GaP is also better than re- implementation of the prune- frome--ro--eesee method using ADMM (Ren et al, 2019). For non-uniform sparse ResNet-50 model, the improvement and 90% sparsity, respectively. Note that the 80% sparse ResNer-50 model can almost match the accuracy of the dense model reported by NVIDIA (2020a). We also observe that, when we extend the training time for the SOTA methods such as SET and RigL to match the GaP training efforts, their accuracies still lag behind. As an example, the model at 80% non-uniform sparsity trained using the C-GaP method outperforms the re- re-implementaton of the ERK RigL12x model with 0.7% accuracy increase and FLOPS reduction (2.7 GFLOPS vs. 3.4 GFLOPS). The 90% non-ume non-uniform sparsity model achieves 1.1% accuracy increase at the same FLOPS.
RigLsx (Evci al. 2020 1.0% and 1.5% at 80%
Comparing the C-GaP and P-GaP pruning methods with same training epochs, we find that C- GaP achieves 0.4% and 0.2% higher accuracy at 80% and 90% uniform sparsity, respectively. We conjecture the reason is that P-GaP converges slower than C-GaP. In C-GaP, the weight values in the sparse partitions are continuously trained get better model accuracy when the dense partition is explored, while the P-GaP method only keeps the dense partition and discards the sparse partitions when combining all dense partitions to the updated model.
3.2 OBJECT DETECTION: SSD ON COCO-2017
We divide the SSD network into 4 partitions with three in the backbone and one in the detection head. We train the model using syclic-partitionel C-GaP with a uniform weight sparsity of 90% on all layers except for the last output layer, which is kept dense. We report the accuracy of the best model searched within 40 GaP steps. As shown in Table in the mean average precision category mAP@ [55:95], the sparse model obtained using our C-GaP method exceeds the dense model by 0.7 mAP (25.9 vs 25.2). 2). It also exceeds the best sparse model iteratively pruned from the dense model by 1.6 mAP (25.9 24.3).
Table 2: Results of sparse SSD models for object detection on COCO-2017.
Sparsity ratio
AP, loU:
AP, Areu:
AR, #Des:
AR, Area:
Method
0.5:0.95
0.5
0.75
S
M
L
1
10
100
M
L
Dense NVIDIA 2020a
25.2
42.7
25.8
7.3
27.1
40.8
23.8
34,5
36.1
11.7
39.6
56.1
Prune- Trune-from-dee from-dense
90%
24.3
41.1
24.8
6.8
26.3
40.0
23.3
34.0
35.8
11.1
39.4
55.7
C-GaP
90%
25.9
42.3
26.9
8.0
28.1
42.6
24.7
35.9
37.8
12.7
41.5
58.5
3.3 3D OBJECT PART SEGMENTATION: POINTNET++ ON STIAPENET
We divide the PointNet++ model into 4 partitions with three in the backbone and one in the segmenta- tion head. We apply the C-GaP and G-GaP methods with uniform sparsity of 80% and 90% all layers, respectively. We report the accuracy of the best model searched within 40 GaP steps. Table 3 compares them with the dense model and the best sparse model pruned from the dense model using

---

Published as a conference paper at ICLR 2022
the ADMM algorithm. The results show that on the class and instance mAP categories, the pruned model using the C-GaP method easily beats the model pruned from dense at both sparsities. even beats the dense model 80% sparsity. The pruned model using the P-GaP method also beats the model pruned from dense at 80% sparsity and not far behind at 90% sparsity.
Table 3: Results of sparse PointNet++ models for 3D part segmentation ShapeNet
Sparsity ratio: 80%
Sparsity ratio: 90%
Method
Poonnt
Class mloU (%)
Instance mloU (%)
Class mloU (%)
Instance mIoU (%)
Dense Yan 2019
2k
Class mloU: 82.5, Instance mloU: 85.4
Prune-from-des from-dense
2k
79.1
84.5
77.1
84,0
C-GaP
2k
82.9
85,8
79,5
85,1
P-GaP
2k
80.8
85,5
74.0
83.7
3.4 TRANSLATION: TRANSFORMER ON WMT-14 EE-DE DATASET
In this part, we evaluate the C-GaP and the P-GaP methods on the translation task based on Trans- former (Vaswani et al. 2017). We train the Transformer models on the W4 En-De dataset and evaluate the SacreBI.EU score (Post 2018).
We cqually divide the Transformer models into three or six partitions with the decoder containing 2 partitions the encoder. We apply the C-GaP and P-GaP methods with uniform sparsity of 80% and 90% on all layers, respectively.
report the best SacreBLEU scores on the validation dataset in Table within GaP steps. The models trained using both C-GaP and P-GaP methods significantly improve over the sparse models obtained by pruning from the dense counterparts. They exceed the dense model quality at 80% sparsity, and the model using three-partition C-GaP method even outperforms the dense model at 90% sparsity.
Table 4: Results of sparse Transformer models for the translation task WMT14 En-De.
Sparsity ratio: 80%
Sparsity ratio: 90%
Method
3
6
==
3
6
Dense (NVIDIA 2020a]
SacreBLEU: 27.6
Prune-from-dense
27.1
25.7
C-GaP
27.6
27.6
27.7
P-GaP
27.9
27.7
27.3
26.9
THEORETICAL JUSTIFICATION
We now provide the convergence guarantee for the veliicpprtitionee C-GaP algorithm. We let F(O) = E (æ:; θ) be the loss function of the deep learning task where D is the data distribution. In addition, we let my be the mask at the start of the q-th round, O, be the learned model weights after rounds, and 6 grown and trained for T epochs. Proposition I shows that C-GaP converges to neighborhood around the stationary solution at rate ((1/vQ) when learning rate is set properly. Due to the space limitation, put its proof in Appendix
1, ..... K be the learned weights in the q-th round after the i-th partition
Proposition (C-GAP CONVERGENCE). Suppose the loss function F(O) is partition-wi wise L- smooth, the sampled stochastic gradient is unbiased and has bounded variance, and the relative error introduced by each mask is bounded by 82 E [0, 1), i.e., ||0, O O myll < 82 & the learning rate ? 1/(4kLT /Q), the sparse models generated by the C-GaP method after Q rounds will converge as follows:
Q
G
82 Q
K
+ E VF o m2))l² =
(1)
7

---

Published as a conference paper at ICLR 2022
where G is a constant related the gradient noise and the initialized model weights.
We make several remarks for Proposition 1 as follows.
Remark 1. If there is no pruning in the training process, then it holds that 5² = 0. Substitutinn it into equation [ we find that C-GaP will converge exactly to stationary solution, i.e., EIIV as Q increases to infinity. This implies C-GaP is also an effective algorithm even for dense training. Remark 2. When a sparse mask is utilized, holds that 8² + O. In this scenario, the mask-induced error will inevitably inftuence the accuracy of the trained model. A smaller lead to a more accurate model that C-GaP can converge to.
error will
Remark 3. In our proofs, we find that cycling through all partitions so that all weights can be trained per round is critical to guarantee the convergence of C-GaP. Note that previous works update weights either greedily (e.g. Rigl. (Evci el al.) (0200) or randomly (e.g. SET (Mocanu et al. (2018) and DSR (Mostafa & Wang (019)). It may take numerous training steps for these algorithms have each weight explored and updated. This may explain why C-GaP achieves better accuracy than RigL. SET, and DSR (see T.. This intuition is consistent with (Güärbizbalaban al. [019 Yiig et al. 2018) which theoretically establish that sampling data cyclically converges faster than uniformly randomly in SGD training.
RELATED WORKS
Pruning from pre-trained dense models: Among various pruning algorithms, one-shot pruning (Le
Cun et al.) 1990 Xu et al. (02T) zeros out given percentage of the trained weights with the smallest magnitude. Based on the magnitude-based one-shot pruning, the gradual magnitude pruning (GMP)
(Zhu & Gupta 2017 Gale et al. 2019) proposes an iterative pruning method that progressively prune models to the target pruning ratio. However, those methods suffer from significant accuracy drop and relatively long training time. Besides magnitude- based pruning, other approaches (Wen et al. 2016
He et al. 2017 Zhang et al. 2021a) adapt mathematiic-orrinnted egguarization-basse algorithms to
generate sparsity. Later works (Zhag et al. [2018b] [Ren et al., 2019 Ma et al.,, 22000 Niu et al.
2020; | Rumi et al. 2020; Ma et al.) 2021a Zhang et al. 2021b Huang et al., [022] utilizes
dynamic regularization penalty such as ADMM to solve the pruning problem as an optimization problem and maintaining high accuracy. Several methods (Zhou et al. 2021 Srinivas et al. 2017]] Molchanov et al. (017)) work in probability space. Other works such as HRank (Lin et al., (020a)).
SCOP (Tang et al. 2020), DMCP (Guo et al. 2020), MetaPruning (Liu et al. 2019a) use complicated
rules to generate the sparsity distribution in the channel level. Since pre-training a dense model from
which to select critical weights consumes large memory space, our work differs substantially from them such that we do not rely on a pre-trained dense model.
Pruning at an early stage: A new trend of exploring sparsity at early stage (Lee et al. 2019 Wang et al. 2020 Tanaka et al.) 2020; Wimmer et al. 2020 van Amersfoort et al. 2020 Ma et al. 202 Liu al. 2021) has emerged to embrace the promising sparse training paradigm. SNIP (Lee ct al. 2019) finds the sparse masks based on the saliency score of each weight that is obtained after training the dense model for only few iterations. GraSP (Wang et al.) (2200) prunes weights based on preserving the gradient flow in the model. FarlyBird (You et al. 2020) conducts a retraining process after searching sub-network topology for few epochs. Prune Train (Lym et al. 2019) integrates structured pruning in the pretraining process. However, pruning at an early stage fails to achieve acceptable accuracy on ImageNet (Deng et al., 2009)). We recognize the underlying reason is that the single-shot pruning criterion is based on the information from few muni--bathh of training samples, which cannot accurately represent the rich features of large-scale dataset. The proposed GaP methods repeatedly update the sparse masks and hence overcome their drawbacks.
Sparse mask exploration: To satisfy the condition of low computation cost as well as low mem- ory footprint, many works have incorporated the fowpinn-froom-ppre----iie
paradigm, and optimize the network by sparse mask exploration. DeepR (Bellec et al. 2018) proposes to train a sparse network at initialization, and dynamically adjust the sparse topology by pruning the weights that flip the sign and randomly growing new weights during training. However, DeepR is primarily demonstrated with sparsification of fully-connected layers and applied to relatively small and shallow networks. Sparse Evolutionary Training (SET) (Mocanu et al.] (018)) and MEST (Yuan et al.) (021a) uses layer-wise magnitude-basee based pruning and random growth at the end of each training epoch.
8

---

Published as a conference paper at ICLR 2022
DSR (Mostafa & Wang 2019) and STR (Kusupati et al. (2200) designs dynamic reparameterization method that allows weights to be re-distributed across layers by providing an effective and trainable way to allocate the sparsity across all layers. Similarly, DNW (Wortsman al. (019)) trains a sparse model and keeps dense gradients to dynamically adjust the network connections. SNFS (Dettmers & Zettlemoyer 2019) develops sparse momentum to identify the importance of weights. Rigl. (Evei et 2020) and NT (Dai et al., 2019) propose to use magnitude-basee pruning and gradient- flow-based growth that update sparse model topology during training. Yuaan et al. (202Ib) uses continuous relaxation and optimization method to dynamically update the structural masks of DNN models. All of the mentioned works update the sparse masks based on heuristics and there is little or no training at the mask update stage. Our work differs from them in that the mask updating rule of the GaP methods more optimized by training a subset of layers into dense and then pruned.
6 SOCIETAL IMPACT AND LIMITATIONS
Societal Impact. The scheduled GaP methods target to obtain the best quality of the pruned model under runtime budget. Based on the researches in Facebook (Hazelwood et al. 2018) Wu et al. 2019), many models are inferenced many billions of times per day, which makes the cost of pruning such models tiny fraction of the inference cost in one day. Thus, better pruning algorithm resulting to a smaller model may save lot more computation on the inference side, which is of high value for the community and society to achieve Green AI (Schwartz et al., 2020). On the other hand, our method cannot prevent the possible malicious usage, which may cause negative societal impact.
Limitations. In this work, we focus the unstructured sparsity to demonstrate the algorithm- innovations of our proposed GaP methods, and we only preliminarily include a block sparsity example in Table of Appendix AA.3 to demonstrate its applicability to structured sparsity and its potential to improve the inference speed. More detailed analysis still a work in progress.
The scheduled GaP methods require more training time than conventional pruning methodology, which may potentially limit its applicability when the training compute resources are limited. Thus, the scheduled GaP methods are mostly beneficial to models whose benefit of the reduced inference time and/or improved accuracy out weigh the cost of the moderately longer training time.
The key hyper-parameter settings such as partition numbers or partition strategies are determined heuristically. In this work, we try to divide the models to partitions with similar parameter counts or computation. We also intuitively group consecutive layers to the same partition, based on our hypothesis that adjacent layers are tighter correlated than more distant layers.
Our analysis in Proposition cannot be directly extended to cover P-GaP since the analysis is built on the partition-wise cyclic updating structure of C-GaP. We will leave the analysis for P-GaP as future work.
The prediction results from the sparse models are generally biased comparing with the dense models they are pruned from (Hooker et al.) 2019). This is a general problem on sparse model architectures, and our GaP methodology cannot reduce such biases.
CONCLUSIONS
Sparsity based model compression is gaining traction in research and industry to reduce the memory footprint and inference runtime. However, conventional compression approaches result to noticeable accuracy loss during the pruning process. In this paper, we propose scheduled grow-and methodology to obtain sparse models. It divides a model into several partitions, grows and prunes each partition cyclically model quality far better than previous works. In all four experimented tasks, the GaP method matches even beats the dense solution at 80% sparsity. In addition, the GaP method does not require pre-traine trained dense model and can continuously searching sparsity masks with new data, showing its flexibility and practical potential.
(GaP)
in parallel. The experimental results show that this method preserves the

---

Published as a conference paper at ICLR 2022
8 ACKNOWLEDGEMENT
This work was supported by Alibaba Group through Alibaba Research Intern Program, and was partly supported by the National Science Foundation CCF-1937500. 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
REFERENCES
D Basu. On sampling with and without replacement. In Sankhyā: The Indian Journal of Statistics, pp. 287-294, 1958.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Train- ing very sparse deep networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
Xiaoliang Dai, Hongxu Yin, and Niraj K Jha. Nest: A neural network synthesis tool based on grow-and-prume paradigm. In Proceedings of the IEEE Transactions on Computers, volume 68, pp. 1487-1497, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 248-255, 2009.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2019.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of the International Conference on Machine Learning (ICML), pp. 2943-2952, 2020.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint 19t::0092209744 2019.
Shaopeng Guo, Yujie Wang. Quanquan Li, and Junjie Yan. DMCP: Differentiable Markov channel pruning for neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition (CVPR), pp. 1539-1547, 2020.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient DNNs. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pp. 1379-1387, 2016.
Mert Gürbüizbalaban, Asu Ozdaglar, and Pablo A Parrilo. Why random reshuffling beats stochastic gradient descent. In Proceedings of the Mathematical Programming, pp. 1-36, 2019.
Kim Hazelwood, Sarah Bird, David Brooks, Soumith Chintala, Utku Diril, Dmytro Dzhulgakov, Mohamed Fawzy, Bill Jia, Yangqing Jia, Aditya Kalro, et al. Applied machine learning facebook: A datacenter infrastructure perspective. In Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA). pp. 620-629, 2018.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE International Conference Computer Vision (ICCV), pp. 1399-1397, 2017.
Sara Hooker, Aaron Courville, Gregory Clark, Yann Dauphin, and Andrea Frome. What do com- pressed deep neural networks forget? arXiv preprint arXiv: 19/ 1.05248, 2019.
Shaoyi Huang. Dongkuan Xu, Ian EH Yen, Sung-en Chang, Bingbing Li. Shiyang Chen, Mimi Xie, Hang Liu, and Caiwen Ding. Sparse progressive distillation: Resolving overfitting under pretrain-and-fmeturr paradigm. arXiv preprint arXiv:2/10.088 2021.
10

---

Published as a conference paper at ICLR 2022
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft threshold weight reparameterization for learnable sparsity, In Proceedings of the International Conference Machine Learning (ICML), pp. $544-5555 2020.
Yann LeCun, John Denker, and Sara A Solla. Optimal brain damage. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pp. 598-605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: Single-shot network pruning based on connection sensitivity. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Mingbao Lin, Rongrong Ji, Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao. Hrank: Filter pruning using high-rank feature map. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 1529-1538, 2020a.
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In Proceedings of the International Conference on Learning Representations (ICLR), 2020b.
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: it desirable or not? In International Conference Machine Learning (ICML), pp. 7011-7020. PMLR, 2021.
Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang, Kwang- Ting Cheng, and Jian Sun. MetaPruning: Meta learning for automatic neural network channel pruning. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 3296-3305, 2019a.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell, Rethinking the value of network pruning. In Proceedings of the International Conference on Learning Representations (ICLR), 2019b.
Iya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Sangkug Lym, Esha Choukse, Siavash Zangeneh, Wei Wen, Sujay Sanghavi, and Mattan Erez. PruneTrrain: fast neural network training by dynamic sparse model reconfiguration. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-13, 2019.
Xiaolong Ma, Fu-Ming Guo, Wei Niu, Xue Lin, Jian Tang, Kaisheng Ma, Bin Ren, and Yanzhi Wang. PCONV: The missing but desirable sparsity in DNN weight pruning for real-time execution on mobile devices. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pp. 5117-5124, 2020a.
Xiaolong Ma, Wei Niu, Tianyun Zhang, Sijia Liu, Sheng Lin, Hongjia Li, Wujie Wen, Xiang Chen, Jian Tang, Kaisheng Ma, al. image enhancing pattern- based sparsity for real-time inference on mobile devices. In Proceedings of the European conference computer vision (ECCV), pp. 629-645. Springer, 2020b.
Xiaolong Ma, Sheng Lin, Shaokai Ye, Zhezhi He, Linfeng Zhang, Geng Yuan, Sia Huat Tan, Zhengang Li, Deliang Fan, Xuehai Qian, et al. Non-structured dnn weight pruning-is it beneficial in any platform? IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2021a.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, et al. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? Advances in Neural Information Processing Systems (NeurIPS), 34, 202
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. In Proceedings of the Nature Communications, volume 9, pp. 1-12, 2018.
11

---

Published as a conference paper at ICLR 2022
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In Proceedings of the International Conference on Machine Learning (ICML), pp- 2498-2507,220 2017.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In Proceedings of the International Conference on Machine Learning (ICML), pp. 4646-4655, 2019.
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- weight pruning. In Proceedings the Twenty- International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 907-922, 2020.
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 (TPAMI), 2021.
NVIDIA. http://gtthbbbomm///D/DDDcgceeee
2020a.
NVIDIA. NVIDIA A100 tensor core GPU architecture. Technical report, 2020b.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Proceedings of the International Conference on Machine Learning (ICML), pp. 4095-4106 2018
Matt Post. A call for clarity in reporting BLEU scores. In Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 186-191, 2018.
Charles R Qi, Li Yi, Hao Su, and Leonidas Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. arXiv preprint arXiv: 02413, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. Proceedings of the AAAI Conference on Artificial Intelligence 2019.
(AAAI), volume 33, pp.
Ren, Tianyun Zhang, Shaokai Ye, Jiayu Li, Wenyao Xu, Xuehai Qian, Xue Lin, and Yanzhi Wang. ADMM-NN: An algorithm-hardwanl co-design framework of DNNs using alternating direction methods of multipliers. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 925-938, 2019.
Masuma Akter Rumi, Xiaolong Ma, Yanzhi Wang, and Peng Jiang. Accelerating sparse enn inference on gpus with performance-aware weight pruning. In Proceedings of the ACM International Conference on Purallel Architectures and Compilation Techniques (PACT), pp. 267-278, 2020.
Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. Green ai. In Proceedings of the Communications of the ACM, volume 63, pp. 54-63, 2020.
Suraj Srinivas, Akshayvarun Subramanya, and R Venkatesh Babu. Training sparse neural networks. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition workshops (CVPR workshop). pp. 138-145, 2017.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS). volume 33, 2020.
Yehui Tang, Yunhe Wang. Yixing Xu, Dacheng Tao. Chunjing Xu, Chao Xu, and Chang Xu. Scop: Scientific control for reliable neural network pruning. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), 2020.
Joost van Amersfoort, Milad Alizadeh, Sebastian Farquhar, Nicholas Lane, and Yarin Gal. Single shot structured pruning before training. arXiv preprint arXiv:2007.00388, 2020.
12

---

Published as a conference paper at ICLR 2022
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the Advances Neural Information Processing Systems (NeurIPS), pp.
2017.
Chaoqi Wang. Guodong Zhang, and Roger Grosse. Picking winning tickets before training by pre- serving gradient flow. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), pp. 2074-2082, 2016.
Paul Wimmer, Jens Mehnert, and Alexandru Condurache. Freezenet: Full performance by reduced storage costs. Proceedings of the Asian Conference on Computer Vision (ACCV), 2020.
Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. Discovering neural wirings. In Pro- ceedings of the Advances in Neural Information Processing Systems (NeurIPS), volume 32, pp. 2684-2694, 2019.
Carole-Jean Wu, David Brooks, Kevin Chen, Douglas Chen, Sy Choudhury, Marat Dukhan, Kim Hazelwood, Eldad Isaac, Yangqing Jia, Bill Jia, et al. Machine learning facebook: Understanding inference at the edge. In Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 331-344, 2019.
Dongkuan Xu, Ian EH Yen, Jinxi Zhao, and Zhibin Xiao. Rethinking network pruning-under the pre-train and fine-tune paradigm. NAACL, 2021.
Xu Yan. Pointnet/pointnert* pytorch. https://ggthub..comaaaa//////ono Pointnet2 pytorch 2019.
Li Yi, Vladimir Kim, Duygu Ceylan, I-Chao Shen, Mengyan Yan, Hao Su, Cewu Lu, Qixing Huang, Alla Sheffer, and Leonidas Guibas. A scalable active framework for region annotation in 3D shape collections. In Proceedings of the ACM Transactions on Graphics (ToG), volume 35, pp. 1-12, 2016.
Bicheng Ying, Kun Yuan, Stefan Vlaski, and Ali Sayed. Stochastic learning under random reshufiling with constant step-sizes. In Proceedings of the IEEE Transactions on Signal Processing, volume 67, pp.
2018
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Yingyan Lin, Zhangyang Wang, and Richard G. Baraniuk. Drawing early-bird tickets: Toward more effi- cient training of deep networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad Morariu, Xintong Han, Mingfei Gao, Ching- Yung Lin, and Larry S Davis. NISP: Pruming networks using neuron importance score propagation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.
9203, 2018
Geng Yuan, Xiaolong Ma, Wei Niu, Zhengang Li, Zhenglun Kong, Ning Liu, Yifan Gong, Zheng Zhan, Chaoyang He, Qing Jin, et al. Mest: Accurate and fast framework on the edge. Advances Neural Information Processing Systems (NeurIPS), 34, 2021a
sparse training
Xin Yuan, Pedro Henrique Pamplona Savarese, and Michael Maire. Growing efficient deep networks by structured continuous sparsification. In Proceedings of the International Conference Learning Representations (ICLR), 2021b.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez- Paz. mixup: Beyond empirical risk minimization. In Proceedings of the International Conference on Learning Representations (ICLR), 20.8a.
Lozez-Paz.
Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. A systematic DNN weight pruning framework using alternating direction method of multipliers. In Proceedings of the European Conference Computer Vision (ECCV), pp. 184-199, 2018b.
13

---

Published as a conference paper at ICLR 2022
Tianyun Zhang, Xiaolong Ma, Zheng Zhan, Shanglin Zhou, Caiwen Ding, Makan Fardad, and Yanzhi Wang. A unified dnn weight pruning framework using reweighted optimization methods. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pp. 493 498.. IEEE, 2021a.
Tianyun Zhang, Shaokai Ye, Xiaoyu Feng, Xiaolong Ma, Kaiqi Zhang, Zhengang Li, Jian Tang, Sijia Liu, Xue Lin, Yongpan Liu, et al. Structadmm: Achieving ultrahigh efficiency in structured pruning for dnns. IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2021b.
Xiao Zhou, Weizhong Zhang, Hang Xu, and Tong Zhang. Effective sparsification of neural networks with global sparsity constraint. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition (CVPR), pp. 3599-3608, 2021.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy pruning for model compression, XrXiv preprint arXiv: 17100078, 2017.
14

---

Published as a conference paper at ICLR 2022
A
ABLATION STUDY
In this section, we present some ablation study on the proposed GaP methods.
A.1 NUMBER OF PARTITIONS FOR GAP
The number of partitions in GaP methods play key role in obtaining better results. As compared in 3 and Table 6 one partition is not sufficient to preserve the best quality. Too many partitions may reduce quality as well (as shown in the model with six partitions in Table (6). Empirically, small number of equal partitions that naturally follow the structures of the models usually perform well. For example, ResNet-50 model is composed of four blocks, each sub-samples from the previous block. Thus four- four-partitie partition GaP is natural choice, Transformer model contains an encoder and decoder, with the decoder twice the number of attention blocks the encoder. It is naturally divided to three partitions.
Table 5: The effect of different number of partitions for ResNet-50 models on ImageNet.
Method
Sparsity Ratio
Distribution
Num, Partitions
Top-I Ace (%)
C-GaP 90% C-GaP
uniform uniform
75.9
90%
76.3
Table 6: The effect of different number of partitions for Transformer models WMT-14 En-De.
Method
Sparsity Ratio
Distribution
Num. Partitions x
SacreBLEU
C-GaP
90%
uniform
1
26.8
C-GaP
90%
uniform
3
27.7
C-GaP
90%
uniform
6
27.1
A.2 PARTITION THE MODEL IN A RANDOM MANNER
In the main text, each partition the model consists contiguous layers and they are eyclically grown and pruned. We also explore random partition strategy for each step in the C-GaP for sparse ResNet-50 and Transformer models. Unlike the cyclic partition, a random partition chooses uniformly random subset of layers to grow in each step of the GaP process. On the results for ResNet-50 described in Table the random partition slightly worse than the cyclic partition but still better than all previous existing solutions. On the results for Transformer described in Table 8 however, the accuracy gap is much larger. At 90% sparsity, Transformer model can achieve 27.7 SacreBLEU score in uniform sparsity with partitions using C-GaP. When random 3-partition is applied to 90% sparsity Transformer, the SacreBLEU score is reduced to 27.0 and 26.9 for uniform and non- aon-unfform sparsity, respectively. We conjecture that different model structures may result to different accuracy gaps. For ResNet-50, the correlations between neighboring layers may be small so each layer may optimized independently. However, for Transformer, the inter-layer weight correlation is stronger (c.g., the W Wkey W "quurr. Woatue in the same attention block have very strong correlation since they process the same input sequence for the self-attention computation)
This analysis shows that the partition mechanism affects the final model accuracy. Our scheduled GaP methods minimize the chance that the neighboring layers belong to different partitions, and have achieved superior accuracy.
Table 7: Different partition strategies for ResNet-50 models on ImageNet.
Method
Sparsity Ratio
Distribution
Num. Partitions
Partition strategy
Top-1 Acc (%)
C-GaP 90%
non-uniform non-uniform
Cyclic Random
77.9
C-GaP
90%
77.8
15

---

Published as a conference paper at ICLR 2022
Table Different partition strategies for Transformer models on WMT- En-De.
Method
Sparsity Ratio
Distribution
Num. Partitions
Partition strategy
SacreBLEU
C-GaP
90%
uniform
Cyclic Random
27.7
C-GaP
90%
uniform
27.0
C-GaP
90%
non-uniform
3
Random
26.9
A.3 GENERALIZATION TO OTHER SPARSE GRANULARITY
We use unstructured sparsity throughout the paper. In this section, we demonstrate that the GaP method is also applicable to other coarse saars--rrained sparse granularity such as block-wise sparsity. The unit for the block-wise sparsity in this experiment many 1 X 8 blocks, then the sparsity ratio of the matrix is defined as the ratio of all-zero blocks. It often believed that the accuracy would be impacted severely when the block size is 8 or greater. comparess Table compares the SacreBleu scores of the sparse Transformer models obtained by applying the 3-partition cyclic C-GaP and the prune-from-dent from-dense methods. is observed that the GaP method improves over the from-ffrm--dese method significantly (27.21 26.21). This further validates the benefits mask updating strategy brought by the GaP method.
x 8, i.e., if the weight matrix viewed as
Table 9; Different sparsifying methods for the Transformer models with structured sparsity on WMT- 14 En-De.
Method
Sparsity Ratio
sparse granularity
Num. Partitions x BLEU
prune prune-from-des from-dense
80%
block
26.
C-GaP
80%
block x 8
27.2
A.4 PRUNING THE FULLY CONNECTED LAYER THE RESNET-50 MODEL
In the main context, the last fully connected (FC) layer of the ResNet-50 model is kept dense in the uniform sparsity distribution since contributes to less than 1% of the FLOPs. In Table IO we perform additional experiments to supplement Table by pruning the last FC layer using the C-GaP method and comparing them with Evei et al. (220). The results in Table TO and Table [ indicate that the accuracy of the ResNet-50 models with sparse and dense FC layers are similar, and both of them outperform the state-of-the-art results in Evci al. (2020). Please note that models with the non-uniform sparsifying distribution in Table alrrady have the last FC layer pruned, thus the experiment setup is the same the ones in Evei al. (2020).
Table 10: Results of sparse ResNet-50 models on ImageNet.
Method
Distribution
Sparsity ratio: 80%
Sparsity ratio: 90%
Top-1 Acc (%)
FLOPS (xc9)
Top-1 Ace (%)
FLOPS (xc9)
RigL Evei al. 2020
uniform
74.6
1.7
72.0
0.8
RigLax Ever et al. 2020
uniform
76.6
1.7
75.7
0.8
C-GaP (dense FC
uniform
77.9
1.7
76.3
0.8
C-GaP (sparse FC)
uniform
77.8
1.7
76.4
0.8
B EXPERIMENT SETUP
Most training scripts and Identical hyper-parameters are applied to each GaP step and the final fine tune stage. For example, the initial learning rate of each step is restored the same value. This parammee restoration avoids pre-determen retedenernnnng the total number of epochs before training and enables the GaP methods to continuously search for sparse masks.
are inherited from NVIDIA (020a) and Yan 20119)
16

---

Published as a conference paper at ICLR 2022
B.1 IMAGE CLASSIFICATION, RESNET-50 ON IMAGENET
In the image classification task, we standard data augmentation, batch size of 2048, cosine annealing learning rate schedule, SGD optimizer with a momentum of 0.875, and a weight decay of 3.05e-5. The learning rate is scheduled with linear warm-up for epochs before reaching the initial learning rate of 2.048. Each GaP step with non-uniform and uniform sparsity includes 30 of training, respectively. The final fine-tuning includes 150 epochs. For C-GaP, we train for 28 steps (i.e.. 7 rounds with 4 partitions), and for P-GaP, we train for 32 steps (i.e., 8 rounds with 4 partitions). After the GaP step, we prune the dense partition(s) and fine-tune the model.
For the prune-from-dee from-dense method, we use iterative ADMM pruning. We first pretrain a dense model using 250 epochs, and perform ADMM regularization training for 250 epochs. Then we prune the model to 80% sparsity and finetune for another 250 epochs. Thus, the total number of epochs for 80% sparsity is 750 epochs. Starting from the 80% sparse model, we iteratively prune to 90% sparsity by firstly training the 80% sparse model with ADMM regularization for 250 epochs, and then prune to 90% sparsity and finetune 250 epochs. It takes a total of 1250 epochs to train a 90% sparsity model.
B.2 OUR IMPLEMENTATION DETAILS OF RIGL
In this section, we provide the implementation details of the RigL (Evei et al. 2020). For the experiments with 100 training epochs, Most of the important hyper-paramters can be found in Evei et al. (202)) We adopt the settings in our PyTorch code base and the accuracy of RigL. in 80% and 90% sparsity can be reproduced, both in uniform and ERK sparsity distributions, respectively. As shown in Table our implementation has slightly higher accuracy, which indicates that our code base in PyTorch comparable with the original implementation in Evei et al. (2020), and can be used for reproducing and extending the training of RigL. without causing fairness issue.
Based on the above implementation, we reproduce the RigL results with 500 training epochs. However, Evci et al. (2020) doesn't ' provide detailed perform extensive experiments and find out that using the same step learning rate decay scheduler can not reproduce the accuracy claimed in the original RigL. paper, regardless of the learning rate decay factor or decay epochs. We change the step learning rate decay scheduler to the cosine annealing learning rate scheduler (Loshchilov & Hutter 2017). and add mixup technique (Zhang et al. [20 8a) with the hyper-parameter 0.2 to improve the generalization ability of the network. We find that the 500-epoch accuracy can be reproduced in these settings. We conjecture that the cosine annealing learning rate schedule and the mixup technique reconcile the overfitting problem that casily occurs in long period training. We inherit the RigL training recipe used in our 500-epoch training, and extend the training to 1200 epochs. The reproduced results are shown in Table
settings for 500-epoch training. We
B.3 OBJECT DETECTION: SSD ON COCO-2017
To train SSD on COCO-2017 dataset, we use an input size of 300 x 300 pixels, a batch size of 64, step learning rate schedule, SGD optimizer with momentum of 0.9, and weight decay of 5e-4. The learning rate is 2.6e-3 with 300 iterations of linear warm-up. Each GaP step includes 32 epochs of training and the final fine-tuning includes 65 epochs.
For the prune-from-denss method, we report the mAP of 24.3 by iteratively pruning. We first pretrain a dense model using 65 epochs, then we prune iteratively to 50% - 70% - 80% - 87.5% - 90%. For each pruning iteration, we train the sparse model for 65 epochs. It takes 390 epochs to get the final 90% sparsity model. Please note that directly pruning 90% sparsity model only results to 21.98 mAP, which is significantly lower than the 24.3 mAP using the iterative pruning method. The model pruned using C-GaP method can achieve 25.9 mAP.
B.4 3D OBJECT PART SEGMENTATION POINENET+ ON SHAPENET
When training PointNet++ Qqi et al. 2017 Yan 2019) model on ShapeNet et et al., 2016) dataset, use batch size of 32, step learning rate schedule with an initial learning rate of 0.001, SGD optimizer with a momentum of 0.9, and a weight decay of le-4. We pretrain a dense model using 250 epochs. Each step of GaP includes 25 epochs of training. The final fine-tuning includes 250 epochs.
17

---

Published as a conference paper at ICLR 2022
umproned DNN model
Input: unpruned
Apply random sparse model
Apply random sparse
randomly pruned madel
randornly prumed modal
Divide into parttions
Divide into partitonss and copy to i.machines
Stspel Round-0
Round-0
Grow part-O,
Grow part-), part-O keep other spars
Grow paré-fi- 1), part((i-2) and keep other parts sparss
Grow part-ff) on machine itl, and train the model on all machines. 1 (0, 1, 1,2,...e 1)
part-fic- 1) other parts sparss
Trals
Supa1
part into
No
Finetune
model?
Pinetune Modwl?
Roundr1
Prune park 1). Finetune model
Prune and finetune model
BNN
DNN
(a) Workflow of C-GaP
(b) Workflow of P-GaP
Figure 4: Training workflow the (a) C-GaP and (b) P-GaP. In C-GaP (left), the model is partitioned and trained machine for multiple rounds. In each round, the sparse mask for each partition is grown and pruned cyclically. Each round has A steps when the model is partitioned into x parts. In P-GaP (right), randomly initialized and sparsified model is copied and distributed when partitioned into x parts. Fach round contains one step since all machines train the corresponding copy in parallel. An optimized model can be collected from the process and pruned to the desired sparsity scheme, then finetuned to restore accuracy.
machines
B.5 TRANSLATION: TRANSFORMER ON WMT-14 EN-DE DATASET
We use a batch size of 5120, inverse square-root scheduler with an initial learning rate of 0.000846, and Adam optimizer. Each step in GaP includes 10 epochs of training, and the final fine-tuning includes 40 epochs. We pretrain dense model using 40 epochs. For prune from dense method, we use one-shot magnitude-ball baased pruning to prune Transformer directly to 80% and 90% sparsity.
C THE DIFFERENCE BETWEEN SCHEDULED GAP AND RANDOM SPARSE MASK EXPLORATION
In our scheduled GaP algorithm, intend to use all information in model. i.e., explore all weights efficiently. One may argue that when trained sufficiently long, all weights will be explored even for random mask exploration. However, random sparse mask exploration and our scheduled GaP methods are like sampling operations with replacement and without replacement (Basu 1958) and their required training time to get the same weight coverage differs a lot.
If we consider a very small model with only 10 weights, and each time we only train one weight and keep the remaining weights the same. When we apply the scheduled GaP algorithm (without replacement), each weight is guaranteed to be trained after 10 steps (one step indicates training one weight). This is because the scheduled GaP alternates the weight to train. The already trained weight guaranteed not to be re-trained again until all the remaining weights are trained. On the other hand, if a random weight selected to train in each step (with replacement), may take 29 steps to be fairly confident that all weights trained. That is almost 3 times more training time than the scheduled GaP. Please note, our example, we only have 10 weights. A real neural network contains millions of weights and is more difficult to guarantee full exploration.
18

---

Published as a conference paper at ICLR 2022
Algorithm 2: P-GaP training flow.
Input: An L-layer model with uninitialized weight O pruning ratio
Output:
An L-layer sparse model satisfying the target sparsity requirement.
Divide all layers into ş partitions, denoted by S., i E (0, ( 1}.
Initialize f(x; è @ m) with random weights è and random masks m that satisfy the sparsity requirement.
step= =
while step < do
Send identical copies of [e, m] all x nodes and denote them by ( and mi) on the node.
parfor E (0....,K K } do
Grow S, by updating the mask m1)) S ArgGrowToo(((())))
Train the model fa;; (i) O m()) for epochs.
Collect the dense partition ((1) from the i-th machine.
Combine all ( S. into dense model GSUU..J8.-1 with the updated weights.
Prune θ and update by [0, m] ArgPrurn TrgPruneTc(O,1)
12 step = step +
13 Fine-tune f (2; O 2 m) for T epochs.
D A DETAILED WORKFLOW OF THE CYCLIC GAP AND PARALLEL GAP
this section, we show the general flow of parallel GaP in Algorithm 2 and demonstrate the detailed workflow of the proposed cyclic GaP and parallel GaP method in Figure as supplement to the Algorithm and Algorithm
E PROOF OF PROPOSITION
F. PROBLEM FORMULATION
Training deep neural networks can be formulated into minimizing the following problem:
min GERd
F(O) EE= θ)]
where θ E Rd is the model parameter to be learned, and f(z; Q) is smooth non-convex cost function in terms of The random variable denotes the data samples that follow the distribution
D. [+] denotes the expectation over the random variable
E.2 NOTATION
We first clarify the notions used the convergence analysis. To characterize how GaP updates model parameters in partition-wise manner, we introduce matrices U2 E Rdxd: i 1, for which the identity matrix Ia E dd can be represented as
la =
U.).
- = Rdd is the model parameter the i-th partition (i.e., partition S.).
S E Rdd is the mask for the i-th partition.
Tf(=;) e dd and VF(O) E dd are the complete stochastic and accurate gradients in
terms of θ respectively.
Vif(z; U. v (x; +) dd is the stochastic gradient for the i-th partition RRd. is the gradient for the i-th partition.
=
E Rd denotes the complete model parameter in which its i-th partition (i.e., 1e R&.)) is newly updated at the q-th round and t-th inner iteration while the other partitions remain unchanged.
(
mg E Rd a complete mask vector for the i-th partition q-th round.
(i)
(3) x is the data sampled g-th round and 1-th inner iteration update the i-th partition.
19

---

Published as a conference paper at ICLR 2022
E.3 ALGORITHM REFORMULATION
In this subsection we reformulate the cyclic GaP (C-Gap) in Algorithm the convergence analysis more easily. With the notations in Sec. E.2 the C-Gap Algorithm can be reformulated as
1 in a way that can present
Algorithm 3: C-GaP Algorithm (A math-friendly version)
Initialize 0 and m randomly. Initialize pruning ratio r.
for round q- 1, ... Q.,,,QQ do
for partition 1, 2.... h do
Generate mask my (1)
Ga GaPMask (i-1)
9,00 myg
:r);
1,.,, for 1 ..... T do
Update (1)
0
(4)
(1) 1U,
g.--1 o )
9.t
9.-
9.1-11
Update (( (0)
4.0
q.7
Update 6
o (x+1) and m m m4
(0)
4.r
Output: θ 0(0) 2 mm
(n)
In GaPMask 9:0: ma
(i-1)
r), the partition of [mm]ss is updated as:
Prune (i-1)-th partition:
update [m, (1 t ArgPruneTo((o) 1,r) for pruning ratio r
Grow i-th partition:
Let [mg (0 I1d, E Rd4
Other j-th partition:
(my (mss [my 1),, (for all j * i and + i 1)
and my (4)
[mg]]
(1) UUS.uuus.
E.4 ASSUMPTIONS
We now introduce several assumptions on the cost function and the gradient noise, which are standard in the literature.
Assumption 1 (SMOOTINESSS). We assume the cost function F(O) is partition- L-smooth, i.e. |V + Uthh) V.F()) < T.[lhell. V hy E Rd.
(4)
The above assumption implies that
[VF(()) VF(+)] s L| +11, VO,
(5)
or equivalently.
F( - F(D) < (VF()), :) + + 10 क12 V
(6)
Assumption (GRADIENT NOISE), We assume for any k. t, and that
E -V) v,F()).
E EV (1) θe
where a > 0 is constent. Moreover, assume the data sample 2. is independent of each other for any k, i, and i.
This assumption implies that the stochastic partition-gradient is unbiased and has bounded variance. Assumption 3 (MASK-INCURRED ERROR). It is assumed that
||0(0) 9 ml( 0 0001111 8 11 (1 where 8 E (0, 1).
20

---

The arguments to Published as a conference paper at ICLR 2022
Note that [mgg S, 1 and only the i-th partition in O is got updated during iterations
(g, 1), (g T), we have
|0 N @ - - 91-111 110 o my ①
0 & d² 10100
(10)
E.5 CONVERGENCE ANALYSIS
Now we are ready establish the convergence property of C-GaP in Algorithm establish the convergence are strait-forward:
First, we need to establish the function value B[F(O) will decrease to ([))) up to an error term caused by the gradient noise and mask pruning, after each inner-iteration t when updating the i-th partition (See Lemma T
Based the above fact, next prove E[F(O g0) ] will decrease to ([F(O(())) when T Ttsepp training of the i-th partition is completed (See Lemma 2
Finally, with the second fact, show that B[F(O will decrease E[F g+10) after the k-th outer round (See Lemmas 3 and 4. Since the function value decreases for each
round k, we can prove that C-GaP will converge stationary solution after sufficiently large Q rounds (See Theorem
Next we present the detail analysis. Lemma (DESCENT LEMMA AFTER EACH INNER-ITERATION). Under Assumptions 7 for each k, i, and & that
it holds
EIF s E[F 2 9.1-1)1 202 2y
(1I)
Remark is observed in Lemma that the function value will decrease by V 1 II for each inner-iteration t. But such decrement suffers from two error terms: one is caused by stochastic gradient noise, and the other is by inexact pruning.
Proof. Since F(Q) is L-smooth (see Assumption I it holds that
F(e < ((e ((0))))) ( ()) - @ +
T ( (0
2 92
FF (1))) <V
V.
9.1- o mm))))
-
L
+ /V
(8)
0
(3)
2 (0)
(12)
2
9.t-1
9-1-1
With Assumption it is easy to verify that
E(V. 9.1-1.. vzf(2
g.t-1 9--1 o mm!"))
(1)
Eg 6
(1)
v.f( (1)
V
f 9.
m
(1) 10
[1-
9.4-1
equation 7
E(V 9.1-1), V ( 4 1 m()))
(13)
Using similar way, prove, with equation that
(+) ( - 9 @ m. )2 EEJV
9.-11 3 (2)
(14)
By taking the expectation over equation 12 and substituting equation 13 and equation 14 into
equation [2] we achieve
E E[F(O
( (0) & E (
(1 - EE
E q.t ) V (()
gi- o ml!)))
2
m )1 Lo2
E
(
2
2
L2
=E 91-11
E 2 + 2
E
()
O (.(i))12
94-1
2
21

---

Published as a conference paper at ICLR 2022
BB B 0m( -. 9
(15)
Note that
E =m
3 m )1?
(1 (1 - VF
9111 o m (5) )|²
equation
2B
(1)
2 m
0 9-1-11
equation
2
V. +
(16)
and, similarly,
R 9.6 9. -. u
m - V.F 9.1-1))
9.
B 121
v (O
1)?
1,202
VA
E V a ))
E
9.0
(9
(17)
2
Substituting equation and equation
17 into equation and by setting 7 S <1/(6L), we have
7(1 -
Lo?
E[F(O E[F (c)
111
E
V
2
7 (1 + L)
E
2
2
27
E[F (
9---1
12
2
+
3
E1
9.0
(
12.
(18)
Lemma 2 (DESCENT LEMMA AFTER RACH PARTITION UPDATE). Under Assumptions for each and that
3
it holds
E[F
( SFFO
(1-)))
2.0
7 Σ
3
4 (1-)) 2
Lo
2T
3
θ
4.0
(4)
(19)
Proof. Summing the inequality over equation
I| for 1 = 1,... ,,, we achieve
,,
L2
27L2877
E B F(O (1)
2111111 < Σ B 91-1) ((6(1)))
E
2
Lo
22
(
(()( [1
E
(
(20)
3
which completes the proof.
Lemma (DESCENT LEMMA AFTER EACH ROUND). Under Assumptions
it holds for each
that
E[F(O & ((F((
(41,0))
ΣΣ
R V. F (
1112)11
1=1 t=1
LLLLTT
2T
+
E
e (1) 9.0
(21)
2
22

---

Published as a conference paper at ICLR 2022
Proof. Summing the inequality in equation 19 over i 1, K, have
E V F
3
Σ
BIF(O - F(O 37 Lo 22228TT Σ
Ele@ (1)
9.0 12
(22)
On the other hand, by the updating rule of ((0
9.0, we have
B -
F(O
(0-)) Σ
B[F(O!)) ((0
B[F(O(
9.0 - F(O (+1,0)) +
E[F
F(O
9.0)
9.0
F (1
(23)
Substituting equation 23 into equation
22
we achieve
V (
9.
+ 3T +
(IF(O F(O
((O
-222281
IE
(1) 9.0
12
(24)
2
1=1
which completes the proof.
To finish the convergence proof, we still need establish the relation between the decrement E E BI 91-1)) and EI|V ((O))) so that Lemma (DESCENT LEMMA II AFTER EACH ROUND). Under Assumptions and learning rate ixLT it holds for each l that
B[F(O < B(FO
7T
Lo
22
E
(i)
Il?
9.0
12
6
3
(25)
Proof. In the following we lower bound the term E Recall Algorithm that
E B
V
(1-1)1 in equation 21
θ (r+1) (1+1)
((()
-UU
V Vef(I 9.
( (
4,t 10m11mmp m))))
(26)
4.0
9.0
θ q.1
(i)
UU: Σ
V
1
9.0 ;: (1)
2 m.)
(27)
9.0
9.
With these relations, it holds for i > and 2 1 that
[| 0.1 @01222
[ 4. ( + (1)
(+-1))
( 00
+
9.0
9.0
9.0
(0) E (1) @00 +
(1)
( + B|(@(2) 4.0 - (1) |2
4.0
T
(M)
Vif(2
m
(
1| +
9 2 mm())112
6.0
9
#=1
t=1
(c)
S 7 ?B Σ
VF (1)
ml
(i))))) 11)
2 Σ
V
F
(
3
m
(1) )1 20
9.8-1
23

---

Published as a conference paper at ICLR 2022
(d)
i-1 T 7
S
2 E
E
BIFF 9 ml + 19202
9.--
8=1
/=1
BI g. &
B|
2 T
VF E
+ (3)
2.111)1 + 2
B|[0 + x220²
9
j=1
j=1
= 2
E
+ BIVF
9.1
+ 12 5²
B| 0,0ll + x2200²
(28)
j=1
where (a) holds because e (5)
9.0 + ( and θ
2.0 - are orthogonal to each other when i + j.
(b) holds because of equation 26 and equation 27 (c) holds because of Assumption 2 and (d) holds
because of the Jensen's inequality. With the above inequality, it holds for t E [1, that
V.
< 2E| V
2E (F
V.F(O 12)
2F
2F
VF(O 11
equation
S
2E
2E
V.
q.t
equation
2E
V,F(6
|| + 2 2T
E
(F (1)
2
+ 2 82
B1 9.0 + 2m
(29)
Summing the above inequality over to = 0,1, ,T, we have
V + 47 T
( 2 2
(F 11-1)
t=1
B1 1112 + 2
(30)
j=1
Summing the above incquality over I,... Kc we have
T
T
E v
(.0)
12
22
E BI (--111
i=
+ 4
E
5 2 L
9.0
T
(1122332k+2
V
F( (8)
1-1
t=1
+ 7
E
(31)
9.0
Combining equation 24 and equation 31 we have
E V. (FF (1
1=1
< (4T212 + 2) ( 3 (E(F(O()) - F(O + 3yLoTTH
+ 212 2
>
El
9.0 12)
2
24

---

Published as a conference paper at ICLR 2022
1,21
Σ
B| =229720212T
(0)
12
EFF 9.0) - F(O (1 + (6yLTH + L
(4.21.7978x + 8120
(
12
9.0) - F(0 + & + 10 (
Σ
B|
9.0l 1?
(32)
t=1
where (a) and (b) use the facts that
12 1
(it is enough to set - /2x1.
(33)
L S 7LTK
(it is enough to set 7 S xf.
(34)
Then the inequality equation 32 becomes
B 12 & TT
(EI
F(O ((111100)) + 8yyno² + 10L Σ
BIO
(35)
Finally we establish the convergence of the C-Gap algorithm as follows: Theorem 1 (C-GAP CONVERGENCE), Under Assumptions VNLTVQ it holds that
if learning rate is y
G
10T2T82
Q
BIVF m S
(36)
Q
VQ
Q
1=1
where G (6x + o² is constant.
Proof. Since
(F E
4.0
o m (f)) 2F) +
2L 2
4.0
(37)
we thus have
V
E
① mm )1)
9.0
equation
24
(E(F(O()) (.0) F(O ((0 + 88L2882 Σ
Bllo (0.1 4y + 22222"1106
7T
24 (BIT(O
- (1) (+1,))))) + 10 T882
E 12 LT
(38)
7T
9.0
Summing the above inequality over 1, Q and taking its average, we achieve
1
(1) VF
4.0 m
1
<
24
E (
10L
ΣΣ
E f0ll
Ly
Q
TTQ
Q
(39)
If we let ILLTVQ the above inequalities becomes
VF o m 2
96*
VQ
[[F(
+
VQ
o² +
10T.7662
Q
ΣΣ
Q
E|
(
9.0
(40)
q=1 1=1
which completes the proof.
25


Reviews:
[{"review_id": "zaT93Xd_drz", "reviewer": "Reviewer_Saw3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "I will go sequentially starting with general comments followed by strengths and weaknesses.\n\nThe paper is hard to read and would benefit from a revision from a writing perspective. The ideas can be further simplified while explanation (the verbatim has changed a bit from the NeurIPS version but it can still be implied). The illustrations are very helpful, but the text and the language often made me feel lost (the only reason, I am comfortable right now is due to the conversation with reviewers that made me understand more). I would strongly recommend the authors revise the write-up for the next version (again).\n\nStrengths:\n\n1) Figure 1 and Figure 2 are very very clear and basically give the idea of what is being done in the paper completely.\n2) The motivation for GaP is well explained.\n3) The pseudo code and method section is clear.\n4) The idea is simple yet seems to be effective. It is sort of a greedy way (even though scheduled) to sparsify the network, where the dense portion is like dense gradient update of multiple methods in the literature (eg., RigL) but also the classical iterative hard thresholding. The idea makes sense, fits well into the greedy growing NAS literature.\n5) Parallel Gap is a nice engineering solution to make use of parallelization of GPUs and shows that the costs saved are worth it. I really like the new figure illustrating P-GaP, this helps more people understand its potential.\n6) The experimental results are good and move past the usual image classification benchmarks to object detection, 3D object part segmentation, and transformers.\n7) The ablations on the # partitions are interesting.\n8) The related work did improve from the previous version, I appreciate the authors for taking time and reviewing more papers to put things in perspective. \n9) I am extremely happy to see the training costs as part of the tables. This was very much lacking in the previous revisions and puts things into perspective. The cost of training is a trade-off in this case which is at least presented to the readers. I have some issues with the costs involved which I will mention in the weaknesses, but this is very promising. \n\nI am not an expert on theory so I will defer to other reviewers on that aspect. However, I don't think theory is needed to justify this paper, if this is a theory for the sake of theory, I would suggest moving it to the appendix and use the space to make compelling cases and use cases for the algorithm itself. \n\nWeaknesses:\n1) The major concern, similar to last time, is the computational costs involved. Is the trade-off worth it? I can see this paper as just pushing the limits on the inference end, getting the best models that are sparse, but the gain of 2% with say 800 additional epochs is something I am not sure how to weigh.\n2) Table 1 is not informative at all, and space could be used for something else. This is a very subjective table, I have no idea what better or good means here. I don't think it is worthy of the space. \n3) The non-uniform sparsity scheme for GaP is missing (again). This was explained to be done using global sparsity (in the rebuttal), but it is not present in the paper. \n4) While I agree FLOPs definition in this paper is correct, taking a line to explain why previous papers were reporting it the incorrect way would be great. \n\nOverall, the paper makes sense and has improved to an extent from the previous version as I mentioned above. However, I would like to have a discussion with the authors about the questions I mentioned above. I was also promised a \"limitations and societal impact\" section trying to explain the trade-offs and issues which was not delivered. I am looking forward to it. \n\nI think the paper is publishable but can be made stronger after the rebuttal.\n", "summary_of_the_paper": "Note: I have previously reviewed this paper for NeurIPS 2021 and I will be reusing my review from then and add the additional comments along the way based on how the paper has been updated along with the promised updates from the previous revisions. \n\nThis paper proposes a way to obtain sparse neural networks by repeatedly growing and pruning parts of the model in a scheduled fashion. Figure 1 gives a good idea of the whole technique. It basically divides the whole network into K parts and only one of these K parts is dense while the rest are sparse. The dense part keeps cycling ensuring over-parameterized learning when needed. The paper proposes that these scheduled routines help in improving the accuracy of the sparse neural network models compared to other sparsity-inducing techniques.\n\nThe paper has extensive experimental evaluation on tasks like classification, object detection, 3D object part segmentation, and Transformers. The authors also try to provide some theoretical explanations to these proposed ideas.\n\nThe paper has updated visualizations to make the algorithm much more clearer from the earlier version which is commendable. ", "summary_of_the_review": "I have reviewed this paper for NeurIPS 2021 and gave it a score of 6. But the paper had a bunch of issues making it not ready for publication. \n\nThis time, the authors tried to put things in perspective. The empirical performance of the method is strong but I would like to see the limitations of the method along with a discussion of trade-offs. \n\nI am giving it a score of 6 but will be willing to increase it to 8 if the authors respond back with valid explanations for weaknesses. \n\n---------------------------------------------\nAfter rebuttal:\n\nI am convinced about the contributions of the paper and I would be arguing for the acceptance of the same during the internal discussions. Increasing score to an 8.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "xdHOLlHj50o", "reviewer": "Reviewer_Zewc", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:   \n1. This study provides one model compression method. With theoretical analysis, authors proved the correctness of this method.    \n2. This method shows preferable performance in constrast to prevent methods in various experiments.     \n   \nWeakness:  \n1. The creativety of this method is somewhat weak. The pruning-rewiring-pruning method have already been used in several papers, such as \"DSD: Dense-Sparse-Dense Training for Deep Neural Networks\" and some papers in the references.    \n2. Batch normalization layer is used to compute the statistics in current network. Wheter this kind of layer should be managed specially?   \n3. In experiments, the epochs of this method is much larger, even $10$ times more than other methods, which has negative societal impact and will limit its  applications.  \n4. The sparsity is very high, under 80\\% -90 \\% sparsity, the model maintains high accuracy.  However, the FLOPs has minor relations with inference speed. Unstructured pruning methods have limited befits to the memory even considering the storage mode of sparse matrix. So, what's the real gain by this method?", "summary_of_the_paper": "This study takes use of pruning-rewiring-pruning method to get a high unstructured sparse model. Broadly, this is one dropout regularization method. With step-by-step growing and pruning, most of the weights are close to $0$ and will be pruned in the next step. Experiments show that this training method can improve the sparsity and performance for a wide range of architectures and applications,", "summary_of_the_review": "This study provides one new training method of sparse model by scheduled grow-and-prune (GaP) methodology. The authors provides  a series of experiments. However, this study requires additional comparions, particularly some moden pruning methods under same experiment settings, such as SCOP, HRank, etc. Alternatively, the authors should include more information about the gains of this method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fyNwx-I07ri", "reviewer": "Reviewer_xnEk", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\n+ The key contribution of this paper is the grow-and-prune schedule that does not need the dense pre-training initially. Such a design can help to reduce the time/computation cost during training.\n\n+ Such a proposed design has ensured that all the weights could be updated during training, which is essential to the model convergence. Moreover, the authors provide the theoretical analysis, and it makes sense intuitively.\n\n+ There are rich and solid experiments provided in this paper. It has been verified on both 2D/3D vision and NLP tasks which are quite strong to show the effectiveness of the proposed method. And there is a detailed ablation study in the appendix, which is also helpful.\n\n+ This paper is written with clear logic and is easy to follow. The discussion of related works is comprehensive to include most of the recent and classic works.\n\nConcerns/Questions:\n\n1.\tTo verify the major claim in training efficiency, some of the important baselines are missing. It should be compared with the dense pre-trained model pruning in the time cost. For instance, the baseline’s total time should include pre-training time + pruning time + finetuning time. And please compare yours (pruning time + finetuning time) with it. Moreover, the performance of dense pre-trained model pruning is better provided for comparison.\n2.\tSince it has been claimed that the superiority of the proposed method comes from updating all the weights, I am not quite convinced about this point. As shown in Fig.2, it seems that the random mask exploration has not been limited within certain regions, which indicates that any parameters of the network can be updated. Although such a random mask exploration has not guaranteed that all the weights will be updated within some rounds, it looks like all of them will be updated in the end if there are enough epochs for exploration. Does this randomness destroy the convergence? Could you please explain more on this point?\n3.\tThe partitions of parameters seem tricky in both partitions number and boundaries. Could you do more ablations on such two factors (and ResNet-50 may be a good choice for this ablation study)? And it will be better to share some high-level instructions on how to set such two hyper-parameters.\n4.\tWhat is the reason for the performance divergence between P-GaP and C-GaP? And how much time/computation costs have been saved comparing P-GaP with C-GaP.\n5.\tAblation study on different sparsity (0%:10%:90%) may also be necessary. Any datasets are welcome.\n6.\tThe last “s” of “previous works” of Remark 3 in Page 8 is red.\n7.\tPlease make sure all the references are in the same format.", "summary_of_the_paper": "This paper presents a new framework for model pruning. Unlike most previous pruning works, this framework does not require pre-training a dense model initially. They have proposed a schedule grow-and prune strategy to fulfill such a goal where the whole network has been split into multiple partitions. There will be an alternation of pruning and growing during the pruning, which ensures that all network parameters are updated in certain loops. Moreover, the authors provide theoretical insight behind such a design that all the weights trained per round are crucial for convergence. To accelerate the pruning process, this paper presents a parallel version that the growing and pruning of multiple partitions would be computed simultaneously. The accuracy and efficiency of the proposed framework have been verified on multiple tasks, including 2D images classification/detection, 3D detection, and text understanding.", "summary_of_the_review": "I recommend borderline reject due to the missing of important baselines and I will consider changing my rating after seeing strong rebuttal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "C8pBQoL-Mj", "reviewer": "Reviewer_XG8a", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengthes:\n1. The empirical results demonstrate the intuition that exploring all the weights could produce a better pruning result compared to a random selection of weights that an algorithm would explore. I am curious when a random selection algorithm is used, if we apply heuristics such as recording the selected weight to make sure all the weights are explored, would that lead to a similar result?\n2. A key variable of the proposed approach is the number of partition. Some empirical studies are done and presented in the supplementary results and a four-partition GaP is suggested. I wonder when the network size is big, whether the grow-and-prune process is slow within each partition?\n\nWeakness:\n1. The approach has several key variables and those variables are likely to impact the results. This makes it not easy for later studies to build upon this work.\n2. As presented in Supplementary results A2, Table 8, it seems that partition strategy doesn’t matter much. Does that mean any approach that could guarantee a complete transverse of the weights, it would produce a better pruning result? \n", "summary_of_the_paper": "This paper presents a scheduled grow-and-prune approach to produce a sparse CNN model. In particular, a sparse model is achieved by repeatedly growing and prune subsets of layers during network training. The main difference between this approach and other approaches that do pruning during the training time is that this approach guarantees that all the weights are explored when a pruning decision is made.\n\nIn the paper, two variations of the approaches are discussed: C-GaP and P-GaP. The theoretical convergence of the C-GaP is analyzed.\nExperimental results on various datasets and tasks are presented, which shows improvement compared to baseline approaches. Additionally, key variables such as partition number are explored and empirical results are provided in the supplementary results. ", "summary_of_the_review": "Empirical results and conclusions that are presented in this paper are interesting. Even if some of the theoretical analyses were made, the experiments are mostly empirical. Therefore, I believe the paper is useful for researchers in this area to read, but this approach doesn't make a breakthrough. Therefore, I rate it 6.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a methodology for alternatively growing and pruning a subset of layers within a network in order to eventually produce a trained, sparse model.  After discussion, all reviewers favor accept.  Empirical performance of the sparse models appears strong, but requires significant computational expense during training to achieve.
Decision: Accept (Poster)