DominoSearch: Find layer-wise fine-grained N:M sparse schemes from dense neural networks
Authors: Wei Sun
Aojun Zhou
Sander Stuijk
Rob G. J. Wijnhoven
Andrew Nelson
Hongsheng Li
Henk Corporaal
Venue: NeurIPS 2021 Poster (2021)
Keywords: Sparsity
N:M Sparsity
Pruning.

Abstract: Neural pruning is a widely-used compression technique for Deep Neural Networks (DNNs). Recent innovations in Hardware Architectures (e.g. Nvidia Ampere Sparse Tensor Core) and N:M fine-grained Sparse Neural Network algorithms (i.e. every M-weights contains N non-zero values) reveal a promising research line of neural pruning. However, the existing N:M algorithms only address the challenge of how to train N:M sparse neural networks in a uniform fashion (i.e. every layer has the same N:M sparsity) and suffer from a significant accuracy drop for high sparsity (i.e. when sparsity > 80\%). To tackle this problem, we present a novel technique -- \textbf{\textit{DominoSearch}} to find mixed N:M sparsity schemes from pre-trained dense deep neural networks to achieve higher accuracy than the uniform-sparsity scheme with equivalent complexity constraints (e.g. model size or FLOPs). For instance, for the same model size with 2.1M parameters (87.5\% sparsity), our layer-wise N:M sparse ResNet18 outperforms its uniform counterpart by 2.1\% top-1 accuracy, on the large-scale ImageNet dataset. For the same computational complexity of 227M FLOPs, our layer-wise sparse ResNet18 outperforms the uniform one by 1.3\% top-1 accuracy. Furthermore, our layer-wise fine-grained N:M sparse ResNet50 achieves 76.7\% top-1 accuracy with 5.0M parameters. {This is competitive to the results achieved by layer-wise unstructured sparsity} that is believed to be the upper-bound of Neural Network pruning with respect to the accuracy-sparsity trade-off. We believe that our work can build a strong baseline for further sparse DNN research and encourage future hardware-algorithm co-design work. Our code and models are publicly available at \url{https://github.com/NM-sparsity/DominoSearch}.

DominoSearch: Find layer-wise fine-grained N:M sparse schemes from dense neural networks
Wei Sun
Aojun Zhou
Sander Stuijk Andrew Nelson
Rob Wijnhoven' 1
Hongsheng Li Henk Corporaal
Eindhoven University of Technology ViNotion B. V. the Netherlands
CCUHK-Sensetnngg Joint Lab, CUHK
w. wwwSuunneeee vojuzhoo@@maii..cm com
rob. wijnhoven@vinotion ml hslißee cuhk, cuhk.edu. hk {s. stuijk, nelson, corporaal
Abstract
Neural pruning is a widely-used compression technique for Deep Neural Networks (DNNs). Recent innovations in Hardware Architectures (e.g. Nvidia Ampere Sparse Tensor Core) and N:M fine-grained Sparse Neural Network algorithms (i.e. every M-weights contains N non-zero values) reveal promising research line of neural pruning. However, the existing N:M algorithms only address the challenge how train N:M sparse neural networks in a uniform fashion (i.e. every layer has the same N:M sparsity) and suffer from a significant accuracy drop for high sparsity (i.e. when sparsity 80%). To tackle this problem, DeachoSearch to find mixed N:M sparsity schemes from pre-trained dense deep neural networks achieve higher accuracy than the uniform-sparsity scheme with equivalent complexity constraints (e.g. model size or FLOPs). For instance, for the same model size with 2.1M parameters (87.5% sparsity), layer-wise N:M sparse ResNet18 outperforms its uniform counterpart by 2.1% top-1 accuracy, on the large-scale ImageNet dataset. For the same computational complexity of 227M FLOPs, our layer-wise sparse ResNet1 8 outperforms the uniform one by 1.3% top-1 accuracy. Furthermore, our layer-wise fine-grained N:M sparse ResNet50 achieves 76.7% top-1 accuracy with 5.0M parameters. This is competitive to the results achieved by layer-wise unstructured sparsity that believed to be the upper-bound of Neural Network pruning with respect to the accuracy-sparsic believe that our work can build strong baseline for further sparse DNN research and encourage future hardware-algorithm co-design work. Our code and models are publicly available at/htpss: thub. com wtwp////aaaaarrrtroomaoooeeeeee
present novel technique
tradc-off. We
Introduction
Modern deep neural networks (DNNs) achieve remarkable success in various tasks such computer vision and language processing at a cost of memory footprint, computation, energy and storage. These have all become bottlenecks of deploying DNNs commodity hardware for real-world applications. To address these challenges, many model compression techniques have been proposed to optimize DNN models. Neural network pruning is one promising technique orthogonal quantization ((33).
network architecture search [ and knowledge distillation (7-9].
Recent innovations in hardware architectures (e.g. Nvidia Ampere Sparse Tensor Core (10) and N:M fine-gra -mn-igrinedd sparse DNN pruning algorithms [1]
12 reveal a promising research line of neural
Equual contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

pruning that may achieve high sparse ratio while maintaining regular sparse structure. On the other hand, traditional unstructured sparsity can achieve higher sparse ratio but cannot maintain a regular sparse structure, which makes it difficult for acceleration [3).. Traditional structured sparsity can achieve regular sparse structure but may not achieve high compression ratio [T]. Figure] Tillustrates traditional unstructureed//truuuurrd pruning and N:M fine-grate fine-grained structured pruning.
dense matric
spars matriz
non-zero
ind
Pruning
Compriso
Pruning
Compress
(b)
Pruning
Compresoi
Figure 1: (a) Unstructured pruning treats every weight the dense matrix individually which will produce a sparse matrix with irregular non-zero data. (b) Coarse-grained pruning treats filter/channel as an atomic component and can produce a regular sparse matrix. (c) Fine- anneggrinne N:M pruning performs unstructured pruning inside each group (group size M = 4 in this example) while it enforces an additional constraint that there are at most non-zero values to be kept.
Applying uniform fine-grained N:M sparsity training. or fine-tuning to DNNs, will lead to sub- optimal solution because layers are treated equally. Modern DNNs tend have a number of layers with a highly non-uniform distribution of redundancy. This well-known phenomenon has been exploited by recent unstructured pruning methods [14 that have achieved higher accuracy than the uniform counterparts, especially for relatively high sparsity. However, the existing methods mainly focus on unstructured pruning that treats the weights within a layer individually and does not have fine-graine ane-grained position constraints, which cannot be used for fine- fine-grained N:M sparsity. As consequence, a novel method for layer-wise fine-grained N:M sparsity is needed.
Furthermore, sparsity acceleration relies on the underlying software- arcciteear system of the platform. We can make reasonable assumption that there will be more but not arbitrary N:M schemes supported in future software- architecturee designs. Although the flexibility of N and M is this still an open system design research question, we assume a policy of fixed M and flexible paper because it can provide fixed window size (i.e. size = M) for sparse weight matrix compression.
Motivated by above-mentioned challenges, this work introduces an efficient framework to find layer- wise fine-grained N:M scheme with pre-defined N:M candidates which achieves higher accuracy compared to the uniform counterpart with equivalent complexity constraint (e.g. model size or FLOPs).
We propose DominoSearch, iterative algorithm that finds layer-wise fine- mme-grained sparse schemes from pre-trained dense weights. This is achieved using a magnitude-ben based criterion [14] [8] for the pruning selection threshold, in combination with weight penalty drive values towards the threshold. DominoSearch also uses layer-wise penalty factor to balance the heuristic layer-wise redundancy of parameters (15) and layer-wise computational complexity (e.g. FL.OPs). As indicated by the name Domino, the value from the N:M ratio decrements during the search phase with the weight penalty acting as momentum.
Due to the layer-wise sparsity, our framework is able to achieve state-of-the-ar (SOTA) accuracy- model size trade-off's when compared with unstructured sparsity and accuracy-FLOPP trade-offss when compared with structured sparsity. Figure demonstrates the advantages of layer-wise N:M sparsity under both scenarios ResNet50 [19] Details can be found in Table
The major contributions of our paper can be summarized as follows: (1) We present DominoSearch A novel and easy-to-use framework to search the layer-wise sparse schemes from pre-trained dense weights with a specified model complexity constraint. Our method does not rely on expensive design space exploration such as Network Architecture Search (NAS) or Reinforcement Learning (RL).

---

Ga) Accuracy vs Medel sie
Ibi Accurscy vs FLOPS
unterumuned sparthy
seru mocutne spority
20
20
puy
71
30
1836
1.5
2.5
4.5
0.25
250
0.75
1.00
L35
Li0
175
Model sure (P8taramm)
PLOP's (2gant
Figure 2: ResNer50 on ImageNet: Compare top-1 Accuracy of our layer-wise N:M sparse models with SOTA structured/unsttrutured sparsity under various FLOPs/model sizes.
To the best of our knowledge, this is the first work on layer-wise fine-grained N:M sparsity. (2)
We propose a layer-wise penalty factor to balance the parameters redundancy that does not depend on input tensor/image size and complexity that depends on input tensor/image size (e.g. FLOPs).
The computational complexity measurement FLOPs used in this paper can easily be replaced with latency, throughput or energy consumption when deployed on specific platform. (3) We evaluate our solution on the large scale ImageNet dataset with both heavy ResNets [19] and compact RegNets [20], and the smaller scale CIFARIÓ0 100 dataset with ResNet56. Results of ResNet50 on ImageNet show that layer-wis, N:M sparsity searched by our framework achieves SOTA coaoracycoompessiooo trade-off under fine-grat grained N:M sparsity.
2 Related Work
Traditionally, sparsity of DNNs is categorized into 1) unstructured sparsity and 2) structured sparsity. Unstructured sparsity can be achieved by weight pruning and reaches relatively high sparse ratio without significant accuracy drop [14 16 18 21 22). However, unstructured sparsity has a large exccution time overhead on modern hardware due to the large overhead of handling the irregular non-zero weights in the matrix; good speed-up can only be achieved when the sparse ratio is very high (i.e., > 95%) 13). On the other hand, coarse coarse-grained structured sparsity such filter-wise sparsity and channel wiiee sparsity [23 24
Structure of sparsity:
maintain a hardware-friendly sparse structure but may not be able to achieve a high sparse ratio. In order to achieve high compression ratio and a hareware-friendll sparse structure, various fine-grained structured sparsity patterns were proposed including Tile-wise (25). intragroup sparsity structure (26) and N:M sparsity [IO]. Our paper focuses on N:M fine-grained sparsity which has demonstrated success in getting accurate N:M sparse DNNs (i.e. trained from scratch [11] or fine-tuned [27] from dense pretrained weights) and usage in commodity hardware (c.g. Nvidia Ampere Tensor Core). Figure Sosureiillsserr Iillustrates two traditional types
and fine-grained N:M sparsity.
Layer- compression:
Layer- compression is well-known concept in the DNN optimization community. The non-uniform importance of different layers in DNNs is leveraged by mixed precision quantization in which different bit-widths are allocated via NAS
28
29 or RL (3. Recent discoveries
demonstrate that by carefully selecting [14] 15) or learning [6] the layer-wise sparsity, the sparse DNNs can achieve higher accuracy than their uniform counterparts. Evei et al. (15) propose training scheme for unstructured sparse neural networks and present the Erdos-Renyl kernel (ERK) (extension of (17) heuristically select the layer-wise sparsity. Lee al. [14] propose layer- adaptive magnitude-based pruning score to choose the layer-wise sparsity, focusing on unstructured pruning and the number of survival weights of each layer without taking the layer-wise computation complexity (e.g. FLOPs) into account. Kusupati et al. (16) present Soft Threshold Reparameterization (STR) to learn the layer-wise sparsity during training. However, the target model complexity constraint (e.g. model size and FLOPs) is implicitly controlled by two srper-parameterss (A and sinie) and cannot be specified, hence users have to tune and Sinit and train multiple models to get the desired target model complexity. Our paper focuses on how to find the N:M scheme of each layer efficiently with the specified model complexity constraint. It avoids the need for time consuming hyper- parammer search.
3

---

Method DominoSearch
3.1 Problem Formulation
Given a pretrained dense model with weight tensors w ..... w associated with layers (convolution layers fully-connected layers), model complexity constraint Spe (e.g. model size or FLOPs) and candidate pool N, of sparse schemes (e.g. (1:8,2:8, 4:8,8 The problem can be formulated a
Accuracy(S(w,N))
max (w,.N)
Complexity(S(w..V) S Spr
N N
Where S()) denotes the sparse model which can be obtained with dense weights w and sparse ratio N. Complexity()) can be model size, FLOPs, real latency or even energy consumption depending on the use case and design objectives. The goal to find optimal layer-wise schemes for the whole network. Due to the large discrete design space and the training/fine- (i.e. recovering the accuracy of the sparse model), is usually not possible to handcraft the optimal solution or perform an exhaustive search.
cost of evaluating a design point
Inspired by methods used in mixed-bit bit search 3 which decouple mixed-bit policy searching and model accuracy recovering, use a two-step solution: (1) find the layer-wise sparse schemes from the candidate pool Np; (2) fine-tune/retrain sparse weights with searched sparsity (i.e. No) to recover the accuracy.
3.2 Group-wise threshold and sparsity
We first emphasise the difference between layer-wise fined-grained sparsity and layer-wise unstruc- tured sparsity. How to decide the layer-wise sparsity has been actively studied over recent years 16). However, these methods mainly focus on unstructured sparsity whose layer-wise sparsity be decided by layer-wise threshold because the weights in certain layer treated individually. In contrast, fine-graing grained N:M sparsity treats weights from a group-wise view (e.g. Figure (c)). As a consequence, we define group-wise threshold vector 7 and group-wise sparsity vector Nú where
the layer index. The length of these two vectors is K [w
|| is cardinality (i.e. the number of parameters), M is the group size and K is the number of groups. |w*| should be divisible by M.
M where
Group-wise threshold selection: Instead of using a small global value such as 1000 [22 to decide if the weights should be treated as pruned or not, we use a threshold vector T that can represent the weight distributions of each group. order to achieve this. we use the mean of the smallest (absolute value) M elements as threshold because it provides a group-wise feature in an efficient way 2
M and can mitigate the effect of outliers (e.g. values like 0.0 ). Note that use 2 elements because results in a sufficient search space and representativeness. Using more elements can result in a better representativeness because more elements because larger threshold value will lead to a smaller starting value N and vice versa. Figure shows an example of group-wise threshold selection. The larger variance of T indicates that we need group-wise threshold. On the other hand, a groupp-wse threshold will lead to group-wiss sparsity. The column vector Nj encodes the number of kept weights of each group, from which we can infer the sparsity of this layer (i.e. N:M = 3:4). practice, we can relax the requirement by using the Supermajority voting rule. Specifically, as long as the ratio of the number of in N reaches pre-defined voting ratio V,, the layer sparsity ' can be inferred
included, but results in a smaller search space
With above-mentioned group-wise definitions, we can reformulate wi and T as w and T where is the group index. We use the reformulated version in the next sections.
Without losing generalization, N equal to power-of-two search space.

---

T
N
0..010
0.0114
0.0020
0.00617
10.0041
3
0.0212
0.0748
0.0368
0.0898
0.0290
3
0.0854
0.1751
0.0406
0.0450
0.0428
3
0.0896
0.0169
0.
0.0177
0.0085
3
Figure 3: An illustrative example of dense weight matrix w and corresponding threshold vector T The values are taken from random groups in the first layer of ResNet18. N2 encodes the number of elements larger than the threshold of each group. Blue highlights values larger than threshold.
3.3 Explore the search space via layer-wise weight penalty
Before introducing our search algorithm, we consider the standard DNN training process with the Stochastic Gradient Descent (SGD) update rule:
w(t 1) w(t) - (()(((t)
(2)
with learning rate & and gradients g ((w) of w. To obtain sparse model, we need to apply mask m E {0.1} to weights w(t), resulting in a sparse model w(t) == w(t) @ m, where @ denotes element-wise product. The mask can dynamically change during training iteration and depends on the weights we- With group-wer wise and layer-wise dimensions, we can reformulate the mask m as
m (t) wi()) 7
where i is the layer index, & is the group index and T is the group-wise threshold introduced in Section 3.2 Mask mi (t) is inferred by Boolean Operator >, where means kept and m means pruned.
A popular approach is to apply an extra regularization penalty to introduce more sparsity, including L norm and Le norm [18] [2]. We periodically exploit the L2 norm [22 which can hold the group-wise feature, to find the layer-wise sparsity. Thus the update rule can be formulated as:
( + 1) = w(( - (C(( + p(t) (t) = (t))
(4)
p(t) f1, if mod kp 0.
0. otherwise.
(5)
where ()( is the layer-wise penalty factor to control the strength of penalty applied to each layer which will be introduced Section (.44 Inspired by [22), we apply periodical weight penalty which will drive the kept weights towards the threshold gradually and leave kp iterations buffer time for adjusting to the applied penalty (using p(f)). The layer-wise sparsity N and model complexity decrease during the search phase. When the model complexity reaches the search constraint Sp., we terminate the search process and fine-tune the weights based on the searched layer-wise fine-grained sparsity schemes. Algorithm 3.1
shows the search algorithm.
3.4 Layer-wise penalty factor
Modern DNNs tend to have many layers with non non-uniform distributions of both parameter redundancy and complexity contribution. Intuitively, we want encourage layers with larger redundancy and higher complexity to achieve higher sparse ratio (i.e. decrease N) faster. This can be achieved by controlling the strength of the weight penalty of each layer. The layer computational complexity (e.g. FLOPs) factor can be calculated using
f #
C:
max 1 (f+ *s))
EL
(6)
where f. is the dense FLOPs of layer and N /M is the sparsity (Line 10 in Algorithm
3.1
5

---

Algorithm 3.1 DominoSearch
1: Input: Complexity constraints Sp,, dense weights of each layer w w Dataset D.
Learning rate Ç. Interval Ke. Voting ratio Vy.
2: Init: current model complexity Sp. iterations t = O, layer-wise penalty factor ny.
3: while True do
4: for wi in w ..... w do
5:
(i + +) = (t) ( + p(t) (t(t) (t))
> Eq.
6:
if K.
then
7:
mj. (L) := w1( T
Eq.
8:
Nº ;= vote( sum(m) (t). axis=1),U,)
Sec. 3.2
9:
if N' E N2 then
10:
N = N
N tracks N N
11:
Spc ()))lexity(AV))
D Compute current model complexity
12:
if Spc 2 Spc then
Terminate search process and go to Output.
14:
end if
Update layer-wise penalty factor 17s
Sec.
3.4
16:
end if
end
18:
end for
end while
20:
Output Layer wise sparse scheme N
In order to estimate the layer-wise redundancy, we use the Erdos-Renyi kernel (ERK) [5]. ERK is heuristic method to decide the layer-wise unstructured sparsity given an overall sparsity target (i.e. model size) which does not require design space exploration ERK cannot be directly applied to select the layer-wise N:M schemes because: 1) ERK gives layer-wise sparsity in the continuous domain while N:M sparsity is discrete. 2) Layer-wise sparsity decided by ERK only depends on the overall sparsity target and layer configurations (e.g. kernel size, input/output channels).
hyper-parameter search. However,
reflect layer-wise complexity (e.g. FLOPs) which depends input tensor/image size. Thus, we use the layer-wise sparsity generated by ERK as layer-wise redundancy guidance, which be formulated as:
8;
max EL |e 8t
where e, is the sparsity of layer decided by ERK. Note that r; can be negative the current sparsity (s,) is larger than the sparsity estimated by ERK. With r; and c,, the joint layer-wise penalty factor T/ is defined as:
= 31 * + B2 *
(
where 81 and 33 are weighted coefficients (3) + =1++==1) 1). When searching under model size constraint, set 0.5, A8 0.5 and use 81 = 0.8, 82 0.2 for searching under FLOPSs constraint. Weighted coefficients 31 and B2 are used to balance the effect of FLOPs which is dependent on input ten- sor/image size and model size which is not dependent on input tensor/image size, we tend to use higher 31 when the complexity constraint is FLOPs because it can assign layers with higher FLOPs higher penalty factor. An ablation study of layer-wise penalty factor can be found Section 5.1
Experimental Results
Networks and datasets:
demonstrate the advantages of layer-wise fine-grained N:M sparsity via
various networks on the large-scale ImageNet dataset (30) including heavy ResNets [9 and compact RegNets [20]. We also demonstrate the effectiveness of our method on the smaller CIFARIOM dataset
with ResNet56 [19]

---

Training settings: We first apply DominoSearch (DS) to find the layer-wise sparse schemes from pre-trained dense models Algorithhm3.11 and iinetuneerettrin sparse weights on pre-trained dense weights with searched layer-wise schemes to recover the accuracy. Detailed settings can be found in the Supplementary Material.
4.1 ResNet18/50 with model size and FLOPs constraints
ResNet18: Table D shows that layer-wise sparse & consistently outperforms consistently outperforms the uniform baseline with both equivalent model size FLOPs. Figure 4 visualizes layer-wise sparse FLOPs distributions under two search targets and dense parameter distributions. For FLOPs-constrained search, the shallower layers, especially the first layer, allocated with higher sparsity (Figure (b)) because of their larger FLOPPs contributions caused by the larger input feature size. On the other hand, shallower layers have relatively smaller contributions to the model size (i.e. less parameters, Figure (c), resulting in lower sparsity when using the model size constraint (Figure
visurlevss the
4 (a)). This observation supports the necessity of using layer-wise penalty factor y; which is able to capture the information of FLOPs distribution from a global view and assign corresponding layers (shallower layers in this case) with relatively higher penalty factors.
Table 1:
ResNet18. Layer-wise wise sparse vs. uniform baseline with equivalent model size or FLOPs.
Dense baseline reference is from Pytorch pre-trained model Zoo
Method
#Params
FLOPs
Top1 Acc
Structure
ResNet18
11.7M
1814M
69.8
Dense
SR-STE
1.46M
227M
66.65
2:16
Equal model size
DSoours)
1.46M
329M
68.76(+2.1)
Mixed N:16
Equal FLOOPs
DS(ours)
1.29M
227M
67.98(+1.3)
Mixed N:16
M100%
(4)
FLOPs search Sarget
(0) Porons difibbttion
Figure 4: Layer-wise statistics of ResNet18: x-axis is layer index (layer 8, 13, 18 are Comv2d with
1 X kernel and layer 21 fully- fully-connected layer) and y-axis denotes FLOPs and Parameters. (a)/(b) shows the distributions of layer-wise FLOPs under model size/FLOPs search target, where dark/light means kept/pruned partition. (c) shows the layer-wist wise distribution of parameters of dense ResNet18.
ResNet50:: Table 2 shows the results for ResNet50. Layer-wise fine-grained sparsity can consistently outperform its uniform counterparts for both accuracy-sparsity (i.e. model size) and accuracy-FI.On FL.OPs trade-off. When comparing to the SOTA layer-wise unstructured sparsity (16), which is believed to be the upper-bound of Neural Network pruning with respect of -ccuracy-sparsiiy trade-off, our layer-wise fine-grained models can achieve competitive result given the same model size. Although it has higher FLOPS than unstructured sparsity (1.14G v.s. 766M), we emphasize that fine- ine-ggained sparsity maintains a regular sparse pattern which is crucial for getting deployment gains (e.g. latency). Furthermore, our layer-wise fine-grained sparsity is significantly better than structured sparsity with respect to accuracy-Fi -FOOas trade-off, which encourages a promising system design research line: efficient supports of flexible N:M sparse patterns. Considering the preliminary success of Nvidia Ampere Sparse Tensor Core (10), we believe the design overhead of supporting flexible N:M sparse patterns is affordable and worthwhile.
7

---

Table 2: ResNet50 performance. (+) denotes the topl-accurace gain compared to the uniform counterparts with equivalent model size FLOPs. (+) compares with unstructured sparsity. Reported numbers are either taken from the corresponding literature or obtained by training with open-source code [T]. Dense baseline reference from Pytorch pre-trained model zoo
Method
#Params
FLOPs
Top1 Acc
Structure
Uniform
ResNet50
25.6M
4.09G
76.1
Dense
GMP 31
5.IM
818M
75.6
Unstructured
U(niform)
DSR 52
5.1M
1.23G
71.6
Unstructured
L(ayer-wise)
DNW 33
5.IM
818M
76.2
Unstructured
GraNet
1.15G
76.2
Unstructured
L
RigL[15 155
5.1M
1.68G
75.1
Unstructured
L
STR I6
5.2M
776M
76.2
Unstructured
GMP 31
5.1M
76.5
Unstructured
L
DS(ours)
5.0M
1.14G
76.7(+0.2)
Mixed N:16
IncReg 35
1.37G
71.1
Structured
[E[36]
1.34G
71.7
Structured
L
Greg-2 22
1.34G
73.9
Structured
GDP 37
1.57G
70.9
Structured
FisherPruning 38
1.02G
73.9
Structured
META 39
1,00G
74.4
Structured
L
SR-STE
6.4M
1.02G
76.5
4:16
SR-STE
3.2M
511M
74.4
2:16
U
SR-STE
1.6M
256M
70.7
1:16
SR-STE
1.6M
256M
71.5
2:32
U
Equal model size
DS(ours)
3.2M
731M
75.7(+1.3)
Mixed N:16
L
DS(ours) 1.6M
392M
73.5(+2.0)
Mixed N:32
I.
Equal FLOPs
DS(ours)
3.3M
511M
75.4 (+1.0)
Mixed N:16
L
DS(ours) 1.7M
256M
73.4 (+1.9)
Mixed N:32
L
4.2 RegNet with FLOPs constraint
We further study our search method on the compact model: RegNet. RegNet [20] is the state-of- the-art compact network architecture searched by NAS from 10 candidates, Table 3 shows that layer-wise sparse RegNetX3.2G outperforms its uniform sparse counterpart by 1.0% and dense smaller RegNetX400M by 3.9%, given equivalent FLOPs. The results demonstrate that our method can effectively find the layer-wise sparsity even the dense model is designed to be compact.
Table 3: RegNets: Comparing sparse RegNets and dense RegNets with various FLOPs. (+) denotes the accuracy gain compared dense model with same FLOPs.
(ethork((ethod)
FLOPs
Top1 Acc
Structure
RegNetX400M
400M
72.3
Dense
RegNetX800M
800M
74.9
Dense
RegNetX1.6G
1.6G
76.8
Dense
RegNetX3.2G
3.2G
78.2
Dense
Sparse RegNetX3.2G (SR-STE)
400M
75.2
2:16
Sparse RegNetX3.2G (Ours)
400M
76.2(+1.0) (43.9)
Mixed N:16

---

consider 4.3 ResNet56 on CIFARI00
In addition evaluation performance on the ImageNet dataset, we also evaluate on the CI dataset. Results are presented in T Layer-wise N:M sparsity significantly improves the accuracy on the smaller CIFARION 100 dataset under both model-size and FL.OPs constraints.
Table 4: ResNet56 on CIFAR 100: Comparison between uniform sparsity and layer-wise sparsity. Each setting is evaluated 3 times, mean and std. of top-1 accuracy are reported. Baseline dense ResNet56 obtains 74.8% top-1 acc. with 0.85M parameters, 127M FLOPs.
Model Complexity
0.21 PrParams
0.1 M+Paramss
32M FLOPs
16M FLOPs
Acc. uniform
72.33
71.08 10.27
72.33
71.08
Acc. layer-wise
74.31 10.34
73.2610.24
74.00
72.7910.25
Acc. gain +1.98
+2.18
+1.67
+1.71
5 Ablation study
5.1 The advantage of layer-wise penalty factor
To study the effectiveness of the layer-wise penalty factor 7/2 proposed in Section 3.4
a constant penalty factor (1.0) on all layers as the baseline. (able that layer-wise schemes searched with тΙ consistently outperform the counterparts without 7j. The gap significant under complexity with small FLOPs (i.c. 16M). To achieve such a low FLOPs without 7). both shallow and deep layers are extensively pruned no matter their contributions of FLOPs, resulting in very high sparsity (92.2%) In contrast, with the guidance of 1). the sparsity is only 89.0% when achieving equivalent FLOPs. Additional experiments on ImageNet can be found in Supplementary Material.
Table 5: ResNet56 on CIFAR100: Ablation study of layer- penalty factor T):-
Model Complexity
MWarams
MPParmss
32M FLOPs
16M FLOPs
Acc. with Y
74.31 10.34
10.34
73.26
74.00
72.79
Acc. w/o 1/.
73.80+0.20
72.95
73.71 +0.14
70.39
Acc. gain
-0.51
-0.31
-0.29
-2.40
5.2
Comparing layer-wise N:M to the uniform counterpart using ASP training method
There are two existing methods train sparse N:M networks: 1) SR-STE and 2) Nvidia ASP [2] When comparing layer-wise sparse N:M to the uniform baselines in Section 4 we use the most recent SR-STE as the training method to train sparse N:M networks. SR-STE is based on dynamic masking which allows the pruned weights to re-gro re-grow during the training/fin-tuning based on fixed masking which determines the mask at the beginning. The mask is fixed and pruned weights are not allowed to re-grow through the fine-tuning stage. TJ
In contrast, Nvidia ASP
layer-wise sparse N:M networks to the uniform baselines using the ASP method. The results show that layer-wise N:M is consistently better than the uniform counterparts for both ResNet50 and ResNet18, which matches the observations under the SR-STE training setting.
Table 6: Comparing layer-wise to uniform sparsity using the ASP method.
Network
Structure
#Params
Top- Acc(%)
ResNet50 ResNet50
Uniform 2:16
87.5%
73.3
Layer-wise N:16
87.5%
74.9(+1.6)
ResNet18
Uniform 2:16
87.5%
64.2
ResNet18
Layer-wise N:16
87.5%
65.1(+0.9)

---

5.3 How N:M sparsity achieves comparable results to unstructured sparse sparsity
To study the impact of training settings and how these contribute the accuracy, we conduct a set of ablation experiments and present results in Table Where E1 and E2 are two layer-wise unstructured sparse ResNet550 baselines [16] 31). E2 E7 are ablation experiments which will be explained shortly.
Table 7: Ablation study of the impact of different training settings using ResNet50 with 80% sparsity.
Index
Structure
Top-1 Acc(%)
Epochs
Training Method
Initialization
EI
unstructured
76.5
~50
31
Random
E2
L unstructured
76,2
100
STR[16)
Random
E3
L N:M
76.1
100
SR-STE
Random
E4
LNM
76.4
120
SR-STE
Random
E5
NN:
76.7
120
SR-STE
Pre-trained
E6
LNM
76.6
90
SR-STE
Pre-trained
E7
LN:M
75.6
120
ASP(12)
Pre-trained
Weight initialization: In order to recover the accuracy of sparse neural networks, dense weight initialization is typically used [22 31]. By comparing E4 to E5, it shows that using pre-trained (dense) weight as the initialization helps layer-wise N.M sparse neural networks to reach higher accuracy.
Training epochs: Training for fine-tuning sparse neural networks usually requires more epochs for convergence [15). Experiment pairs E3 v.s. E4 and E5 v.s E6 Table [ that longer epochs can help to achieve higher accuracy, although for settings with dense weight initialization (E5 vs. E6), the accuracy gain of 30 additional epochs is minimal because using dense weights as the initialization can be seen pre-trained for certain epochs under dense training settings.
Dynamic Static Mask: Experiments E5 and E7 compare two different training methods for N:M sparsity. It shows that the dynamic mask sparse training algorithm can outperform the fixed mask training algorithm significantly.
The experimental results Table indicate that the performance of sparse neural networks can be boosted via pre-trained weight initialization, more training epochs and proper sparse training method.
Conclusions
This paper presents an efficient framework, DominoSearch, together with the proposed layer-wise penalty factor that explicitly quantifies the layer-wise wise computation complexity and parameter redun- dancy, to find the layer-wise fine-grained N:M sparsity from dense weights.
We experimentally validate the advantages of the layer-wise N:M sparsity on the ImageNet and CIFAR 100 datasets with various networks. The results of ResNet50 ImageNet show that layer- wise N:M sparsity is competitive to layer-wise unstructured sparsity which believed to be the upper bound of neural pruning with respect the accuracy-sparsic trade-off. We hope that contributions can encourage and draw attentions to flexible fine-grained N:M hardware-software system design/research.
7 Limitations
The major limitation of our work is that we did not benchmark deployment gains such as latency and throughput. To the best of our knowledge, Nvidia Ampere Tensor Core is the only commercially available architecture that supports fine-grained N:M sparse computation efficiently. However, it only supports limited options for fixed sparsity (2:4 for bfloat and 4:8 for integer). Thus, following the common practice of related work we compared to, we used theoretical computational complexity, FLOPs, to estimate the computation performance gains.
10

---

Acknowledgments and Disclosure of Funding
We thanks all anonymous reviewers for their feedback on improving this work. This work is funded by the Dutch Research Council (NWO) Perspectief program ZERO-ARM P3. We thanks for the computation resources provided by Sensetime Research and CUHK-Sensetime Joint Lab.
References
[]] Amir Gholami, Schoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. "A Survey of Quantization Methods for Efficient Neural Network Inference", In: arXiv preprint arXiv:2 200::20033/ 13630 (2021).
[2] Aojun Zhou, Aubang Yao. Yiwen Guo, Lin Xu, and Yurong Chen. "Incremental network quantization: Towards lossless cans with low-precision weights". . In: arXiv preprint wrXiv:1702.03044 (2017).
[3] Kuan Wang. Zhijian Liu, Yujun Lin, Ji Lin, and Song Han. "Haq: Hardware- automated quantization with mixed precision". In: Proceedings of the IEFF/CVF Conference on Computer Vision and Patten Recognition. 2019, pp. 8612-8620.
[4] Pengzhen Ren. Yun Xiao, Xiaojun Chang, YaoYao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. "A comprehensive survey of neural architecture search: Challenges and solutions". In: arXiv preprint arXiv:2006. 02000 (2020).
[5] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V Le. "Mnasnet: Platform- neural architecture search for mobile". In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019, pp. 2820-2828.
[6] Jiahui Yu. Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song. Ruoming Pang, and Quoc "Bignas: Scaling up neural architccture search with big single-stage models". In: European Conference on Computer Vision. Springer. 2020, pp. 702 1177
[7] Jiamping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. "Knowledge distillation: A survey". In: International Journal of Computer Vision (2021), pp. 1-31.
[8] Geoffrey Hinton. Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in a neural network". In: arXiv preprint arXiv: 1503.0253/ (2015).
[9] Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. "Fitnets: Hints for thin deep nets". In: arXiv preprint arXiv: 1412.6550 (2014).
[10] Ronny Krashinsky and Olivier Giroux et al. Nvidia Ampere Sparse Tensor Core. URL: https: developer wwwiiii.ii........ com/ blog//viddiiiiii ampere- wwwchitettuureee... ientturreinndepiee ie-thp
[11] Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, Hongsheng Li. "Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch". In: International Conference on Learning Representations. 2021.
[12] Nvidia Automatic SParsity. URI.: https
github com NVIDIA
apex
/
apex/ contrib/
[13] Ziheng Wang. "SSparsRR: Accelerating Unstructured Sparsity GPUs for Deep Learning Inference", In: Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques. 2020, pp. 31-42.
[14] Jacho Lee, Sejun Park, Sangwoo Mo, Sungsoo Ahn, and Jinwoo Shin. "Layer--daptive Sparsity for the Magnitude-based Pruning". In: International Conference on Learning Representations. 2021.
[15] Utku Evci, Trevor Gale. Jacob Menick. Pablo Samuel Castro, and Erich Elsen. "Rigging the lottery: Making all tickets winners". In: International Conference Muchine Learning. PMLR. 2020. pp. 2943- 2952.
[16] 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 on Muchine Learning. 2020.
[17] 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: Nature communicutions 9.1 (2018), pp. 1-12.
[18] Song Han, Jeff Pool, John Tran, and William Dally. "Learning both Weights and Connections for Efficient Neural Network". In: Advances in Neural Information Processing Syxtems. 2015.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. "Deep residual learning for image recog- nition". In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2016, pp. 770-778.
[20] Ilija Radosavovic, Raj Prateek Kosaraju. Ross Girshick, Kaiming He. and Piotr Dollár. "Designing network design spaces". In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020, pp. 10428-10438 -048-.
[21] Yiwen Guo, Anbang Yao, and Yurong Chen. "Dynamic network surgery for efficient dnns". In: arXiv preprint arXiv: /608 04499 (2016).

---

[22] Huan Wang, Can Qin. Yulun Zhang, and Yun Fu, "Neural Pruning via Growing Regularization". In: arXiv preprint ar1h::2012.09244 (2020).
[23] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. "Learning structured sparsity in deep neural networks". In: arXiv preprint 1608::6600003663 (2016).
[24] Hao Li. Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. "Pruning filters for efficient convnets". In: International Conference on Learning Reprexentations. 2017.
[25] Cong Guo, Bo Yang Hsueh, Jingwen Leng. Yuxian Qiu, Yue Guan, Zehuan Wang. Xiaoying Jia, Xipeng Li, Minyi Guo, and Yuhao Zhu. "Accelerating sparse dnn models without hardware-suppor via tile-wise sparsity". In: arXiv preprint ar Xiv: 133066 (2020).
[26] Xundong Wu, Xiangwen Liu, Wei Li, and Qing Wu. "Improved expressivity through dendritic neural networks". In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, pp. 8068 8079.
[27] Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Seffi Naor, and Daniel Soudry. "Accelcrated Sparse Neural Training: Provable and Efficient Method to Find N: M. Transposable Masks". In: arXiv preprint urXiv:2102.055 20..0.2.1122 24 (2021).
[28] Mingzhu Shen, Feng Liang, Chuming Li. Chen Lin, Ming Sun, Junjie Yan, and Wanli Ouyang. Once Quantized for All: Progressively Searching for Quantized Efficient Models. 2020. arXiv: 20100. 04354
[cs.CV]
[29] Zhaowei Cai and Nuno Vasconcelos. "Rethinking differentiable search for mixed- seeed-precision neural networks". In: Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition. 2020, pp. 2349-2358.
[30] Olga Russakovsky. Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. "emageNet Large Scale Visual Recognition Challenge", In: International Journal of Computer Vision (IJCV) 115.3 (2015), pp. 21 1-252. DO1: 10. 1007 10111113-011-0000 0816-y
[31] Trevor Gale, Erich Elsen, and Sara Hooker. "The state of sparsity in deep neural networks". In: arXiv preprint a90iv: 09574 (2019).
[32] Hesham Mostafa and Xin Wang. "Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization" In: International Conference on Machine Learning. PMLR. 2019, pp. 4646-4655.
[33] Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. "Discovering neural wirings". In: arXiv preprint arXiv:1906.0055 (2019).
[34] Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy. Zhangyang Wang, and Decebal Constantin Mocanu. "Sparse Training via Boosting Pruning Plasticity with Neuroregeneration" In: arXiv preprint arXiv:2 106. 10404 (2021).
[35] Huan Wang, Xinyi Hu, Qiming Zhang, Yuehai Wang. Yu, and Haoji Hu. "Structured pruning for efficient convolutional neural networks via incremental regularization". In: IEEE Journal of Selected Topics in Signal Processing 14.4 (2019). pp. 775-788.
[36] Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. "Importance estimation for neural network pruning". In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognation. 2019, pp- 12244-12722
[37] Shaohui Lin, Rongrong Ji, Yuchao Li, Yongjian Wu, Feiyue Huang, and Baochang Zhang. "Accelerating Convolutional Networks via Global & Dynamic Filter Pruning." " In: IJCAI. 2018. pp. 3425-2432.
[38] Liyang Liu, Shilong Zhang. Zhanghui Kuang, Aojun Zhou, Jing Hao Xue, Xinjiang Wang, Yimin Chen, Wemming Yang. Qingmin Liao, and Wayne Zhang. "Group Fisher Pruning for Practical Network Compression".. In: Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research. PMLR, 2021.
[39] 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 IEEF/CVF International Conference on Computer Vision. 2019, pp. 3296-3305.
12


Reviews:
[{"review_id": "WmEMC7nAvbE", "reviewer": "Reviewer_WkEA", "summary": "1) The paper proposes a novel layer-wise mixed N:M sparsification method, i.e., each group in a kernel can have different N. Compared to traditional layer-wise uniform sparsification methods, main techniques include group-wise threshold and layer-wise penalty (FLOPS and layer-wise redundancy).\n2) Experiments on ResNet18 and ResNet50 show that for equal model size, the proposed methed achieves higher FLOPS compared to a most recent uniform N:M method [5]; for equal FLOPS, the proposed method achieves a smaller parameter number compared to [5].", "questions": "", "limitations": "", "rating": 6, "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": "Pros.\n1) The proposed method adopts a novel mixed N:M scheme, while a most recent N:M method [5] adopts uniform scheme. As shown in Experiments (Section 4.1), the proposed mixed scheme significantly improves compression ratio, compared to the traditional uniform scheme.\n2) The proposed layer-wise penalty factor in Section 3.4 explicitly quantifies contribution of layer-wise complexity (FLOPS) and layer-wise redundancy, while previous methods [5,19] do not explicitly quantify the penalty factor as such.\n\nCons.\nMy major concern is that technical details of the proposed method are similar with recent N:M methods [5][19]:\n1) In Section 3.2, the paper adopts \"the mean of the smallest M/2 elements as threshold\". However, a similar M/2 scheme is also adopted in a recent N:M method [19].  The authors need to explain differences between these two M/2 schemes.\n2) In Section 3.3, the proposed weight update rule in Equation (4) is similar as the update rule adopted in a recent N:M method [5] (See Equation (4) in the paper [5]). Both these two update rules set regularization for the pruned parameters. The authors need to explain differences between these two weight update rules.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In Section 6, the authors state two limitations. For the first limitation on \"did not benchmark deployment gains ...\", I agree that adopting theoretical computation complexity (FLOPS) is an appropriate solution. For the second limitation about no experiments on Transformer, I think the current experiments on CNNs are sufficient already.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Ot-Yub5qaV2", "reviewer": "Reviewer_avap", "summary": "This work proposed a training algorithm that allows models to use different sparity levels in different network layers under the N:M sparsity setting.", "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": "This paper tested the scheme that allows network layers in a single model to have different sparsity levels under the N:M sparsity setting. Their experiment results clearly show that their proposed scheme is working. However, the results are well expected given what we have observed in the earlier works. Therefore, the significance of this work is limited. I also suggest the authors improve the clarity of the manuscript, especially the method section. Please also see the following detailed comments.\n\nDetailed comments:\n\nP3,L89: N:M sparsity was originally proposed in ref1(called intragroup sparsity there). Nvidia first made the idea working on the real hardware. I think ref1 still deserves some credit.\n\nFig 3: the last row of T^i should be 0.0089 instead of 0.0085\n\nP4: Section on \"group-wise threshold selection\": The reasoning in this part is very confusing, please try to clean it up.\n\nP5, L161: why the L_2 norm can hold a group-wise feature?\n\nEquation (5): k_p mentioned in L165 but not clearly defined, Seems it is switch to K_c\n\nSuggestion: There are too many different N defined, maybe try to avoid overload it.\n\nAlgorithm 3.1: t is always 0 according to the pseudo-code. v_r and the voting process not clearly described. L8: The >= should be reversed.\n\nIt appears that the word sparsity has been used to describe various notions, such as sparsity level, sparsity pattern. Please clear them up.\n\n\nTable 2, the accuracy rate for the dense ResNet50 is much lower than the one provided in the original ResNet paper\n\nref1:  \nWu X, Liu X, Li W & Wu Q. Improved Expressivity Through Dendritic Neural Networks. NeurIPS 2018\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JZowgG0J8e9", "reviewer": "Reviewer_6z8t", "summary": "The abstract and title of the paper convey the summary accurately. This paper proposes to improve the recently proposed work on N:M sparsity by Zhou et al., ICLR 2021. The former work results in models that have N:M unstructured sparsity that can be used in newer accelerators like Ampere but are handicapped by the fact that all the layers have the same sparsity ratios. This results in the inability to optimize for FLOPs for a given # parameter count thus having a knob for tuning the tradeoffs. \n\nThis paper proposes to fix that by proposing an iterative scheme called DominoSearch to find layer-wise fine-grained schemes/rations for N:M sparsity providing much-needed flexibility. DominoSearch operates on pre-trained models with a budget constraint and overtime figures out the good-enough mixed N:M scheme along with layer-wise sparsity for all the weight tensors on the network (layers). This is achieved with weight penalty as well as explicit layer-wise penalties combined with standard group-wise sparsity used for N:M scheme. The layer-wise penalty factor helps in trading off accuracy, FLOPs and model size is based on the sparsity achieved iteratively + a prefixed scheme like ERK for measuring redundancy. \n\nWith one caveat that all the baselines (except Zhou et al ICLR 2021) are trained from scratch and sparsity is induced during that time, while this paper works on pre-trained models. The experimental section is super strong and has strong practical implications along with a clear Pareto dominance on the baselines. ", "questions": "", "limitations": "", "rating": 7, "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": "The brevity of the review should not be taken as a negative for this paper as I have very few things to comment on and the paper is very clear on what it is trying to do. I think I summarized the strengths in the summary but will try to cover if there any I missed. I have a couple of concerns/comments that will help me understand and place the empirical evaluation in context while also improving the paper even further. I will be going sequentially. \n\nStrengths:\n1) The motivation is super clear. N:M sparsity is useful, but uniform layer-wise nature is restrictive, so figure out the mixed scheme with varied N:M along with varying layer-wise sparsity to tune for the tradeoff if needed and further increase accuracy for fixed resource costs compared to the uniform scheme. \n2) Related work is extensive and puts things in context.\n3) Alg 3.1 is clean and helps understand the scheme well.\n4) I like the ERK-based redundancy estimate in Eq 8, that is novel as far as I know and can also be used for RL-based search if needed. \n5) The practical implications of the results, be it constant FLOPs or constant params are impressive coupled with the accuracy gains.\n6) extensive experimentation and the ablations should be commended. \n7) The authors also do a good job in addressing limitations, except one thing which I will mention later. \n\nWeaknesses:\nPlease include a short primer on N:M sparsity if possible to have a sense of completeness to the reader. \n1) The abstract can be condensed and also the claim that STR being the upper bound for compression accuracy should be removed (that would be an overarching claim). \n2) The math in the method section for group-wise threshold should be made much clearer and the same goes with the weight penalty. The layer-wise penalty is very clean and would expect something of that state for the other two. It is slightly hard to parse through in the current form. \n3) I think I have only one concern and it is kind of a major one, even though it doesn't take away the benefits this method brings to the table. \nI am not completely clear on why this method can't be applied for training from scratch. Even with the pre-trained model, after the search, the retraining still needs 120 epochs for ImageNet which is even more than the normal training of imageNet. The training costs are something that isn't clearly discussed and do fit into limitations as this is a very expensive scheme, maybe better than RL, but still an expensive scheme to get to the final model via the retraining phase. I would like the authors to comment on these issues 1) training overheard, 2) why not train from scratch and why do we need the pre-trained models. Lastly, a simple RL-based scheme would be a strong addition to the baselines which will do the same kind of search but show why the greedy approach proposed in much more efficient. \n\nAddressing these concerns will further improve the paper and will lead me to improve the rating. Even though the training overhead is a lot, I believe the final models are worth it, however, if this can be done during training (not on pre-trained models) that also improves the training overhead and other things involved. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Mentioned above. The authors need to talk about training overhead and sort of unfair comparison by using pre-trained models for N:M schemes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hrs"}, "extra_text": {}}, {"review_id": "E7_0452Tl0C", "reviewer": "Reviewer_Mirr", "summary": "The authors propose combining two existing techniques, N:M sparsity and per-layer (rather than uniform/global) pruning rates.  By allowing each layer to choose a particular N:M pair, the network can find a configuration that is not constrained to sharing a single N:M.  The solution is DominoSearch, an algorithm which starts with pretrained (dense) weights and determines a pruning threshold for each group of M weights based on the initial values.  Some number of iterations of fine-tuning adjust the weights gradually lower, in turn reducing each layer's chosen N.  Once some complexity target (either parameter or FLOP count) is hit, the network's layer-wise N:M are frozen, and the weights are finally fine-tuned.  A layer-wise penalty factor adjusts the overall complexity metric to account for layers which have relatively more or fewer FLOPs.  Empirical results show compelling reductions in FLOPs and parameters when compared to training with unstructured sparsity or uniform N:M sparsity.", "questions": "", "limitations": "", "rating": 6, "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": "## Originality\n\nThe idea to start with a high N that drops over time is akin to iterative magnitude pruning for unstructured sparsity, but I haven't seen a principled approach for N:M sparsity that doesn't rely on sweeping hyperparameters, etc.  Similarly, pruning different layers to different amounts is nothing new, but it is when applied to N:M structured sparsity.\n\n## Quality\n\nI'm concerned that the comparisons used to make claims like \"… [the proposed result] is competitive to accuracy of the state-of-the-art layer-wise unstructured-sparsity model\" aren't fair.  Particularly, the problem being solved: DominoSearch is an algorithm to choose N:M values per layer of an already-trained dense network, but all comparisons are to algorithms which induce sparsity \"from scratch,\" i.e. during the initial training process, without first training a dense network.  Looking instead at a result for 80% sparsity (roughly matching the 25.6->5 Mparams result from Table 2) from Figure 5 in [1], the accuracy is 76.52%, barely reduced from the baseline of 76.69%.  (This result is two years old, so the SOTA may have advanced since then.)  Does it make sense that accuracy for structured sparsity would be higher than accuracy for unstructured sparsity?  If this is the case, then is it due to regularization, suggesting that the dense model was poorly trained to begin with?  If, as you point out, unstructured sparsity is believed to be the upper bound, but you find that it isn't, I'd expect some discussion of why this commonly-held belief is not true.\n\t\nSimilarly, for the uniform N:M case, the comparison seems to be against SR-STE, which is a method to find N:M masks during training (with no fine-tuning).  Instead, a better comparison would be to use the method implemented in the submission's [6] (or, the more recent whitepaper[2], which may be a better source than [6] and [4] (which is not titled appropriately in the bibliography)), which uses the same \"start with a dense model, determine a mask, and fine-tune while enforcing the mask\" process as this submission.\n\t\nIf we set aside the comparisons to inappropriate baselines, the algorithm does seem to work as advertised: the ability to optimize for either FLOPs or number of parameters is great, and Table 4 suggests that for a small data set, layer-wise N:M is superior to uniform N:M at a given FLOPs or parameter target.  (Unless, of course, these results also use SR-STE for the \"uniform\" representation; it's not clear from the Table, but all other results do use SR-STE.)   Further, there's no catastrophic accuracy loss, so the resulting models are plausibly useful, particularly when compared to a dense model with equivalent complexity.\n\t\nA comparison of the layer-wise N:M vs. uniform N:M at the same accuracy (as dense) would be useful.  For example, from the results in Table 3, the user must make hard decisions.  Would it be better to start with RegNetX1.6 and prune by an overall factor of 4x (FLOPs) to reach the 400MFLOPs target?  If accuracy were the same as the unpruned RegNetX3.2, the choice is easy - there's no downside to pruning RegNetX3.2, and RegNetX1.6 cannot reach that accuracy.  Existing results for uniform 2:4 sparsity show that accuracy is maintained (at 50% parameters), so if DominoSearch cannot achieve this same accuracy/sparsity target, there will be obvious room for improvement; if it is able to improve upon the parameter reduction while maintaining accuracy, then its superiority will be obvious.\n\n## Clarity\nThe submission is generally well-written.  There were some details that should be included in the main text, though:\n- How much fine-tuning is utilized after the layer-wise N:M search completes?\n- How is kp chosen?\n\nThe hyperparameter kp is confusing in the presence of 'k' as the group index.\n\t\nI have to admit that I don't follow the motivation for the name, even with the description on lines 59-60: \"As indicated by the name Domino, the N value from the N:M ratio decrements during the search phase with the weight penalty acting as momentum.\"\n\t\nFigure 4(c) shows the parameter distribution for which search target?\n\t\nGDP and META are missing units in the FLOPs column in Table 2.\n\n## Significance\nThis work won't lead to an immediate performance speedup, but that's just fine.  Instead, it seeks to guide future N:M sparse architecture designs.  If the results hold up after comparing to reasonable baselines (prune then finetune, rather than sparse from scratch), then hardware that supports variable N:M may be well-motivated.\n\t\nHowever, some of the N:M settings used in this submission may be on the extreme side.  If 2:4 is what is supported today, extending to M=32 may not be reasonable from a hardware complexity standpoint.  Reducing the size of M and showing compelling results would be a stronger argument for supporting such a design.\t\n\n---\n\n[1] \"The State of Sparsity in Deep Neural Networks,\" Gale et al., https://arxiv.org/abs/1902.09574\n\n[2] \"Accelerating Sparse Deep Neural Networks,\" Mishra et al., https://arxiv.org/abs/2104.08378", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a methodology for finding layer-wise fine-grained N:M sparse weights from a dense neural network. The reviewer discussion was very thorough, as was the authors' rebuttal. Overall, I think this paper is above the bar and I would like to see it published, although I think reviewer concerns about measuring against proper baselines should be addressed in the final version.
Decision: Accept (Poster)