Lottery Tickets can have Structural Sparsity
Authors: Tianlong Chen
Xuxi Chen
Xiaolong Ma
Yanzhi Wang
Zhangyang Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: Lottery Ticket Hypothesis
Structural Winning Tickets

Abstract: The lottery ticket hypothesis (LTH) has shown that dense models contain highly sparse subnetworks (i.e., $\textit{winning tickets}$) that can be trained in isolation to match full accuracy. Despite many exciting efforts being made, there is one  "commonsense" seldomly challenged: a winning ticket is found by iterative magnitude pruning (IMP) and hence the resultant pruned subnetworks have only unstructured sparsity. That gap limits the appeal of winning tickets in practice, since the highly irregular sparse patterns are challenging to accelerate on hardware. Meanwhile, directly substituting structured pruning for unstructured pruning in IMP damages performance more severely and is usually unable to locate winning tickets. 

In this paper, we demonstrate $\textbf{the first positive result}$ that a structurally sparse winning ticket can be effectively found in general. The core idea is to append ``post-processing techniques" after each round of (unstructured) IMP, to enforce the formation of structural sparsity. Specifically, we first ``re-fill" pruned elements back in some channels deemed to be important, and then ``re-group" non-zero elements to create flexible group-wise structural patterns. Both our identified channel- and group-wise structural subnetworks win the lottery, with substantial inference speedups readily supported by practical hardware. Extensive experiments, conducted on diverse datasets across multiple network backbones, consistently validate our proposal, showing that the hardware acceleration roadblock of LTH is now removed. Specifically, the structural winning tickets obtain up to $\{64.93\%, 64.84\%, 64.84\%\}$ running time savings at $\{36\%\sim 80\%, 74\%, 58\%\}$ sparsity on CIFAR, Tiny-ImageNet, ImageNet, while maintaining comparable accuracy. All the codes and pre-trained models will be publicly released.

Under review as a conference paper at ICLR 2022
LOTTERY TICKETS CAN HAVE STRUCTURAL SPARSITY
Anonymous authors Paper under double-blind review
ABSTRACT
The lottery ticket hypothesis (LTH) has shown that dense models contain highly sparse subnetworks (i.e., winning tickets) that can be trained in isolation to match full accuracy. Despite many exciting efforts being made, there one "common- sense" seldomly challenged: pruning (IMP) and hence the resultant pruned subnetworks have only unstructured sparsity. That gap limits the appeal of winning tickets in practice, since the highly irregular sparse patterns are challenging to accelerate on hardware. Meanwhile, directly substituting structured pruning for unstructured pruning in IMP damages performance more severely and is usually unable to locate winning tickets.
winning ticket is found by iterative magnitude
In this paper, we demonstrate the first positive result that a structurally sparse winning ticket can be effectively found in general. The core idea is to append "post-processing techniques" after each round of (unstructured) IMP, to enforce the formation of structural sparsity. Specifically, we first "re-fill" pruned elements back in some channels deemed to be important, and then "re-group" non-zero elements to create flexible group-wise structural patterns. Both our identified channel- and group-wise structural subnetworks win the lottery, with substantial inference speedups readily supported by practical hardware. Extensive experi- ments, conducted on diverse datasets across multiple network backbones, consis- tently validate our proposal, showing that the hardware acceleration roadblock of LTH is now removed. Specifically, the structural winning tickets obtain up to f64.93%, 64.84%, 64.84%] running time savings at (36% ~ 80%, 74%, 58%) sparsity (CIFAR, Tiny-ImageNet, ImageNet), while maintaining comparable accuracy. All the codes and pre-trained models will be publicly released.
INTRODUCTION
Recently, the machine learning research community has devoted considerable efforts and financial outlay to scaling deep neural networks (DNNs) to enormous sizes (175 billion parameter-counts in GPT-3 (Brown et al. 2020)). Although such overparameterizzaton simplifies the training of DNNs and dramatically improves their generalization (Bartlett et al.) 2021 Du et al.) [2018] Kaplan et al. 2020), it may severely obstruct the practical usage on limitee platforms like mobile devices, due to its large memory footprint and inference time (Hoefler et al.) 202T). Pruning as one of the effective remedies can be dated back to LeCun et al. (1990): it can eliminate substantial redundant model parameters and boost the computational and storage efficiency of DNNs.
Such benefits drive numerous interests in designing model pruning algorithms (Han al. 2015a bj
Ren et al.) 2018 He et al. 2017, Liu et al.] (017). Among this huge family, an emerging repre- sentative studies the prospect of training sparse subnetworks in lieu of the full dense models with- out impacting performance (Frankle & Carbin 2019, Chen et al.) 2020b). For instance, Frankle & Carbin] (219)) demonstrates that dense models contain sparse, matching subnetworks (Frankle et 2020a) (a.k.a. winning tickets) capable of training in isolation from the original initialization to match or even surpass the full accuracy. This phenomenon is referred to as the lottery tickets hypothesis (LTH), which indicates several impressive observations: (i) usually extreme sparsity lev- els (c.g., 90%, 95%) can be achieved without sacrificing the test accuracy; (iz) the located winning ticket maintains undamaged expressive power its dense counterpart, and can be easily trained from scratch or carly-epoch weights (Renda et al,, 2020; Frankle et al.) 2020a) to recover the full performance. These advances positive signs about the substantial potential of sparse DNNs.

---

Under review as a conference paper at ICLR 2022
However, almost all LTH literature investigates unstructured sparsity only. In practical scenarios, it brings little hardware efficiency benefits due to the poor data locality and low parallelism (He) et al. 2017: Mao et al., 2017; Wen et al.] 2016) caused by highly irregular sparse patterns. Mcan- while, most of the accelerators are optimized for dense matrix operations (Han et al. 2016). which means there is limited speedup for unstructured pruned subnetworks even the sparsity level exceeds 95% (Wen et al. (2116). Structural pruning (He et al. 2017; Liu et al., (017) as an alternative to exploring sparse subnetworks, removes the entire filter or channel in DNNs gain more com- putational efficiency at the cost of (more) accuracy degradation. As shown in Figure [1 traditional channel-wise structural pruning approaches (He al.) 2017; Liu et. Bartollonn al., a 2019] Molchanov et al. 2019) quickly degrade performance and cannot lead to winning tickets, which was also echoed You et al. (2020).
In our paper, we present the first study into the structural lottery tickets, which explores hardware- friendly structural sparsity (including channel-wise and group-wise patterns) in order to find lottery tick- ets. Specifically, we start from unstructured sparse subnetworks, and then adopt proposed refilling tech- niques create channel-wise structural sparsity by growing back the pruned elements within the most important channels and abandoning the rest. Our results (Section 4 show such refined channel-wise structural subnetworks win the lottery at moderate sparsity level with ~ 50% running time savings on an Nvidia 2080 TI. In order push the compression ra- tio higher, we introduce regrouping algorithm based on hypergraph partitioning (Rumi et al., (0200) to es- tablish group-wise structural patterns which more amenable to pruning due to the shape flexibility of grouped dense blocks. These group-wise structural winning tickets achieve ~ 60% running time savings at 50% ~ 80% sparsity without any performance degradation compared the dense models. Our main contributions lie in the following aspects:
(ResNet-18, CIFAR-10)
95
93
Acurracy
Unstructured w. W eights
Structural N Network Slimming
91
Structural w. &2 of Weights
Structural w. E of Features
90
Structural E of Features
Structural Saliency Scores
89
Dense Netwerk
88
20
40
60
80
100
Sparsity
Figure 1: Achieved test accuracy over different sparsity levels of diverse unstructured and struc- tural subnetworks. Sparse models from classical channel-wise structural pruning algorithms (He
et al. 2017 Liu al.
2017 Bartoldson al. Molchanov et al.
2019
2019 can not match the
full accuracy of the dense model (dash line).
To our best knowledge, we are the first to demonstrate the existence of structurally sparse winning tickets at non-trivial sparsity levels (i.e.. > 30%), and with both channel-wise and group-wise sparse patterns.
We propose the refilling technique and introduce the regrouping algorithm to form channel- wise and group-wise structural sparsity, respectively. Such refined structural subnetworks match the trainability and expressiveness dense networks, while enabling the inference speedup on practical hardware platforms like GPU machines.
Extensive experiments validate our proposal on diverse datasets (i.e., CIFAR-10/100, Tiny- ImageNet, and ImageNet) across multiple network architectures. including ResNets, VGG, and MobileNet. Specifically, our structural winning tickets achieve 53.75% 75% ~ 64.93% GPU running time savings at 45% ~ 80% channel- and group-wise sparsity.
2 RELATED WORK
Pruning. Network pruning is technique that aims at eliminating the unnecessary model param-
eters (Blalock et al. 2020), which can effectively shrink models for the deployment on resource-
constrained devices (LeCun et al.) 1990. Hanson & Pratt 1988). Pruning algorithms are roughly
categorized into two groups: (1) unstructured pruning (LeCCnn al. 1990; Han al. 2015a b)) Ren
ct al.) [2188] Zhang et al.) 2018) with irregular sparse patterns; (2) structural pruning (He al. 2017
Liu et al., 2017; Li et al. 2016 Hu et al. 2016 Wen et al. 2016; Hong et al. (0188) with structural sparse patterns such channel- -wise, block column wise, etc..
Within the group of unstructured pruning, Han et al. 2015a b) remove insignificant connections of models in the post- toss-training stage, with respect certain heuristics like weight/gradient magnitudes; during training sparsification is also another popular trend for pruning by leveraging 4n regular-
ization (ouiizos et al. 2017) or alternating direction method of multipliers (ADMM) (Ren et al.)
2

---

Under review as a conference paper at ICLR 2022
2018 Zhang et al., 2018). Recently, several pruning-at-initiaizzn at-initialization methods (Wang et al. 2020 Lee et al. 2019b; Tanaka et al. 2020) are proposed to identify critical unstructured connections for gradient- flow preserving, without any training. Although the unstructured sparse model has supe- rior performance, it usually suffers from poor data locality and low parallelism (He et al. 2017 Mao
et al. 2017 Wen al. 2016), which make hard to speed up in real-world applications.
On the contrary, structural pruning is more hardware- -riinndly at the cost of notable accuracy loss when the compression ratio increases. He al. (2017): Liu et al. (2017) slim the network channels via & regularization, and Barttldsoo et al. (2019) selects important channels according to heuristics of feature maps. To combine the benefits of structural and unstructured pruning, hybrid pruning strategies have been introduced to pursue more general structural spares patterns which are also capable of acceleration. For example, convolution kernels with half regular sparsity (Chen et al. 2018) or bhitern-basdd structural sparsity (Ma et al. 2020) or vector-wise (Zhu et al. 2019) and group-wise (Rumi et al. (020)) regular sparsity.
The lottery tickets hypothesis (LTH), The lottery ticket hypothesis (LTH) (Frankle & Carbin 2019) conjectures that there exists sparse subnetwork called winning ticket within dense network, whose performance can match with the dense network when training from the same initialization. With the assistance of weight rewinding techniques (Renda et al.] 2020; Frankle et al. 2020a), the original LTH can be scaled up to larger networks and datasets. The existence of winning tickets broadly verified under diverse contexts, such as image classification (Frankle & Carbin 2019
Liu et al. 2019 Wang et al.] 2020; Evei et al.] 2019
Frankle et al. 2020b) Savarese et al. 2020
You et al. 2020 Ma et al. 2021a Chen et al. (020a),
object detection Girish et al. | (2020), natural
language processing Gale et al. (2019): Yu et al. (2020): Prasanna et al. (2020): Chen et al. (2020b c)
|Chen
generative adversarial networks Chen et al.J (2021d); Kalibhat al. (2020) : Chen et al. (202la),
graph neural networks Chen et al. (2021b). reinforcement learning Yu et al. (2020), and life-long
learning Chen et al.] (2021c). However, all of the above L.TH literature only locate unstructured sparse winning tickets, which can hardly bring hardware efficiency boost on real-world applications.
As the most related work, You et al. (2020) finds structural winning tickets at only low sparsity levels around 30% in few cases. It again reveals the complication and difficulty of identifying computation-friendfi sparse patterns. Another concurrent work (Alabdulmohsin et al. (202T) inves- tigates generalized LTH with weight space factorization, which is orthogonal to our work.
Sparse convolutional neural network (CNN) acceleration on GPU. Previous works have ex- plored the acceleration of sparse convolution operations in two different directions. One direction is to design efficient implementation of unstructured pruned networks for improved data locality and utilization of hardware (Chen) 2018 Park et al., 2016). For example, Dong et al. (2019) pro- poses "Acorns" accelerate the sparse computations of convolution kernels with an input sparsity. Peng et al. (017) has proposed matrix splitting algorithm for efficient CNN inference. Nvidia's cuSPARSE library contains various efficient sparse matrix computation algorithms like SpMM on GPUs, drawing great attention in efficient scientific computing. Furthermore, advanced approaches are developed based on SpMM, such as Adaptive Sparse Tiling (ASpTT) (Hong et al. 2019). ASpT significantly improves the data usage of SpMM and achieves the current state-of-ther art performance among SpMM implementation variants. Another direction focuses on more hardware-friendly prun- ing methods (Chen et al.) 2018 Ma et al. 2020; Niu et al.) (022)) During the model pruning, these works aim to maintain certain regular sparse patterns, which benefit the hardware process- ing/computing of corresponding sparse matrices. However, Chen et al. (2018) achieves unsatisfac- tory compression ratio, while the pruning methods used in Ma et al. (2020) and Niu et al. (2020)
require dedicated compiler optimization to accelerate network execution.
METHODOLOGY
3.1 NOTATIONS AND PRELIMINARIES
Sparse subnetworks and pruning methods. In this paper, we mainly follow the routine notations
in Frankle & Carbin 2019 Renda et al. 2020). For a network f(x; 0) with input samples æ and model parameters B, a sparse subnetwork is a network f(x; m @ 8) with a binary pruning mask
m E 10 where @ is the wlement-wise product. In other words, it is a copy of dense network

---

Under review as a conference paper at ICLR 2022
f(; 0) with some weights fixed to O. If the non-fixed remaining weights are distributed irregularly, we call it unstructured sparse patterns (c.g,, Figure 2 left): they are clustered into channels or groups, we name it structural sparse patterns (e.g.. Figure right).
To obtain the desired sparse subnetworks, we consider and benchmark multiple classical pruning algorithms: (1) random pruning (RP) which usually works necessary baseline for the sanctity check (Frankle & Carbin 2019); (2) one-shot magnitude pruning (OMP) by eliminating a part of model parameters with the globally smallest magnitudes (Han et al. 2015a); (3) the lottery ticket hypothesis (Frankle& & Carbin 2019) with iterative weight magnitude pruning (LTH IMP or IMP for simplicity) (Han et 20115p. As adopted in LTH literature (Frankle & Carbin 2019), we identify the sparse lottery tickets by iteratively removing the 20% of remaining weight with the globally smallest magnitudes, and rewinding model weights to the original random initialization (Frankle & Carbin 2019) or early training epochs (Frankle et al. 20206 Chen et al. 2020a). In this paper, the model weights are rewound to the eighth epoch (i.e.. the 5% of the entire training process) for all CIFAR, Tmny-ImageNet, and ImageNet experiments. (4) pruming at initialization mechanisms. We choose several representative approaches such as SNIP (Lee et al. 2019a), GrasP (Wang et al, 2020). and SynFlos low (Tanaka et al. 2020). which explore sparse patterns at random initialization with some gradient flow based criterion. (5) Alternating Direction Method of Multipliers (ADMM) for punning. It is well-known optimization-basse 2018), which can obtain superior compression ratios with little performance degradation for deep neural networks. Note that all pruning approaches are mainly conducted over networks without counting their classification heads (Frankle & Carbin 2019 Ma et al. 2021b).
pruning method (Niu et al. 2020: Zhang al.)
Structural winning tickets. We begin by extending the original lottery tickets hypothesis to the context of structural sparse patterns. A subnetwork f fa: @ 0) is a structural winning ticket for an algorithm A! if it satisfies: @ training subnetworks [(;; m @ 0) with algorithm A² results in performance measurement on task T no lower than training dense networks [ax; 0) with algorithm AT. where f is the original random initialization Og or early rewound weights like 05,, and t is the training iterations; @ the non-zero elements in pruning mask m are clustered as channels, groups or other gardware-friendly structural patterns.
Implementation details. We conduct experiments on diverse combinations of network architec- tures and datasets. Specifically, we adopt WWide-ResNet-32-. (Zagoruyko & Komodakis] (2016) (or WRN-32-2), ResNet-18 (He et al., (016) (or RN-18), MobileNet-vi (or MBNet-v1) (Howard et al., 2017) and VGG-16 (Simonyan & Zisserman 2014) on both CIFAR-10 (Krizhevsky et al.) 2009) and CIFAR-100 datasets. ResNet-50 (or RN-50) is evaluated on both Tiny-ImageNet (Le & Yang.
2015) and ImageNet (Deng et al. 2009) datasets. Table D includes more training and evaluation
details of our experiments.
Table 1: Implementation details which follow the standard settings in Ma et al. (202Tb)
Settings
CIPAR-10
CIFAR-100
Tiny- ImageNer
Image Net
WRN-32-2
RN-18
MRNer-v1
VGG-16
WRN-32.2
RN-18
MBNet-vi
VGG-16
RN-50
RN-50
Butch Size
128
128
128
128
64
Weight Decay
1x
10-1
1x
2x
2
xx 10
5x 10
6xx 10-
Leurning Rate
0.1:00.1
80,120 epech of 160 epochs
Optimizer
SGD Rudder (200)] with momentum of 0.9
Model Size
1.80
11.22 M
3.21 M
M4.72M
1.86 M
M
3.21 M
14.72
25.56 M
25.56 M
3.2 REFILLING FOR STRUCTURAL PATTERNS
is well-known that the irregular sparsity patterns from unstructured magnitude pruning block the acceleration practical hardware devices. To overcome the limitation, we propose simple refill- ing strategy to reorganize the unstructured sparse patterns and to make them more hardware friendly. Specifically, we first select important channels from the unstructured subnetwork according cer- tain criteria. The number of picked channels are depended on the desired sparsity level. Then, the pruned elements are grown back to be trainable (i.e., unpruned) and are reset to the same random initialization or early rewound weights. Lastly, the rest parameters in the remaining insignificant channels will be removed. In this way, we refill important channels and empty the rest to create a channel-wist -wine structural sparse pattern that essentially brings computational reductions. Note that the picking criterion can be the number of remaining weights in the channel, or the channel's weight statistics or feature statistics or salience scores, which are comprehensively investigated in the ab- lation (Section A2). The complete pipeline and illustration are summarized in Algorithm 2 and Figure 2 respectively.
4

---

Under review as a conference paper at ICLR 2022
Initial Unstructured Sparse Mask
Channel-wise Structural Sparse Mask
Kwad
Kerad
Refilling Refilling
Kwad
Group-wise Structural Sparse Mask
Hight
tepet
Regrouping
Remaining Weights
Refilled Weights
Refilled Channel Refillingt
Pruned Weights
Overview of proposals including refilling, refilling+ and regrouping, which turn unstructured sparse mask into thannel-wise and group-wise structured sparse masks.
Figure 2:
Algorithm 1: IMP with rewinding step
Algorithm 3: IMP Regroup
Input: [x; fo), unstructured sparsity s
Input: f(;; 3 0.) with unstructured sparsity from Algorithm
Output: [a; @ 0,)
Set the pruning mask m E R!
hyperparameters 11, 12, b1, and by Output: f(x; m)) O Og with group-wise structural mask mn at sparsity
Train (ax 0n) to rewinding step
f(x; 02) = (f(x;0) 0o))
while not reach sparsity do
while dense block can be found do
Train f(x; m O 0,) to step
2
Divide the rows the sparse pruning mask into t1 groups using hypergraph partitioning (hMETIS
[xx; m @ 0.) = AT 0,)) Pruning 20% remaining weight of @ 8,, and update
for group c; {c1, C2,,..,................. Ct2y do if c; has 2 61 rows then Select columns & that has no less than l2 non-zero items if 2 by columns are selected then Group and Refill the selected columns as well as rows to dense block, and update
.end
Algorithm 2: IMP AMP-Refill
Input:
f(; m @ 0,) with unstructured
sparsity from Algorithm
Output: f(x; m @ 0z) with channel-wise
sparsity structural mask
end end
Calculate importance scores of each channel according certain criterion Pick top-k channels in m, refill back their 0 (pruned) elements with 1 (trainable) and update maintaining š ~ Pick and refill back extra channels m with 8+ Optional for Refill+
end
end
Set other elements out of dense blocks to
fattp://gLaros dtc. umn edu/çkhone
metis/ htw.tttttttteeeeeeeeeeeeeteeeeee
Here provide detailed description of how many and which channels choose to refill. Our main experiments adopt the é norm of channel weights as the picking criterion to score the channel importance due its superior performance. Let 0' X denotes the parameters of the volutional layer I, where Cout is the number of output channel and n is the continued product of the number of input channel, channel height and weight, as shown Figure 2 0 IR" represents the
weights in the ith kernel and m, E {0, 1316 the corresponding mask. We first calculate the & norm m @ 0% which is summation the absolute value of remaining weights in the kernel Then we use to pick the top-k scored kernels, which will be fully refilled. [s] x Cout X n where s' is the original layerwise sparsity and Cout x is the total number of weights in kernel Meanwhile, the rest Cout k kernels are dropped for efficiency gains.
Furthermore, propose soft version, refilling+, make redemption for the aggressive nature of wiping out all remaining channels. picks and re-actives an extra proportion of channels to slow down the network capacity reduction, as indicated by shallow blue blocks in Figure

---

Under review as a conference paper at ICLR 2022
3.3 REGROUPING FOR STRUCTURAL PATTERNS
Although proposed refilling(+) reorganizes the unstructured mask and produces useful channel- wise structural subnetworks, it is rigid and inelastic since the smallest manageable unit is a kernel. In other words, the dense matrices in identified structural patterns have a restricted shape where one dimension must align with the kernel size n. i.c., the continued product of the number of input channels, channel height and weight. Motivated by Rumn et al. (2020), we introduce a regrouping strategy (Figure 2 to create more fine-grained group-wiss wise structural patterns with flexible shapes for remaining dense matrices.
How to perform regrouping? Regrouping aims to find and extract dense blocks of non-prunee elements in the sparse weight matrix. These blocks have diverse shapes, as demonstrated in Figure which are usually smaller size compared to the original sparse matrix. Note that a channel/kernel can be regarded as special case of the dense block.
As described in Algorithm 3 to achieve the goal, we first need to find similar rows and columns, and then bring them together. Specifically, We adopt the Jaccard similarity (Rumi et al. 2020 Jiang et al. 2020) among non-zero columns as the similarity between two rows in the sparse matrix, which calculated as a cardinality ratio of the intersections the union of non-zero columns. For instance, kernel 1 and kernel 2 in Figure 2 (upper left) share three columns in eight non-zero distinct columns, and their similarity is S. Then, if two rows have larger similarity, it can form denser block when we group them together. Take Figure 2 as an example. We can group kernel 1, 2, 3's non-zero columns 1, 3, 6, 11 with at least two elements together, which leads to the first orange dense block.
More precisely, we take the hypergraph partitioning in the regrouping algorithm to generate dense blocks. It treats each row and column from the sparse matrix as a node and hyperedge in the hyper- graph, where hyperedge (i.e., column) connects the corresponding nodes (i.e., row). Then, the pair- wise similarity is leveraged locate an optimal partitioning, which can be achieved with h More details are referred to Rumi et al. (2020). After obtaining the desired dense blocks, we enable all their parameters to trainable by refilling the corresponding pruned elements. Note that refilling these pruned weights does not cause any efficiency loss since the size of the blocks is fixed, while it potentially maximizes the usage of these blocks and brings accuracy gains. Meanwhile, the rest pa- rameters not included in the dense blocks will be discarded, i.e., setting the corresponding position in binary mask m to zero, for reducing the computational overhead as illustrated in Figure [ It is because any parameters outside the dense blocks require extra weights loading and have little data reuse (Rumi et al. 2020), which harms the trade-off of accuracy and efficiency.
How refilled/ regrouped dense blocks be beneficial? We notice that the common tools like cuDNN (Chetlur et al. 2014) have a significant drawback that the inference time does not linearly change with the number of kernels, since they are only optimized for kernel matrices with a multiple of 32 rows (Radu et al.) 2019). For example, as stated in Rumi et al. (2020). a convolutional layer with 10 kernels might have a similar inference time with a convolutional layer with 32 kernels. However, the number of kernels in these dense blocks is almost arbitrary, so more sophisticated GEMM-based efficient implementation (Rumi et al., 2020) is needed to accelerate better our refilled / regrouped structural patterns. Following Rumi et al. (2020), we split kernel with rows into two parts: one has [r/32] x 32 rows and the other one has r mod 32 rows. First, we directly apply the standard GEMM- based convolution algorithm with shared memory to cache the input and output matrix. For the second part, due to the poor data reuse of input matrices, we choose caching the kernel and output matrices for improved cache hit rate and overall performance. More details referred to Rumi et al. (2020).
4 THE EXISTENCE OF STRUCTURAL WINNING TICKETS
ImageNna and ImageNet. In this section, we reveal the existence of our proposed structural winning tickets on ImageNet and Tiny-ImageNet with ResNet-50 backbone. Results of unstructured IMP, channel-wise structural IMP-Refill (+), and group-wise structural IMP-Re- WMP-Regroup are collected in the Figure 3 The end-to-end inference inffrrencc of obtained structural winning tickets with
http:: / aros, dt.c. umn http://uuummmddgeeeeee/eeeeee/ee h/mmet s/ /vverview
"Torcheerf (https: httpg//gttbt..t// com htmm///wwn/////// ctrro is adopted as our tool to henchmark both the end-to-end and layer-wise running time GPU devices.

---

Under review as a conference paper at ICLR 2022
extreme sparsity levels are presented, which is calculated on a single 2080 TI GPU with batch size of 64. Extreme sparsity is defined as maximum sparsity when the subnetwork has superior accuracy than its dense counterpart.
(ResNet-50, Tiny-ImageNet) Time Saving
(Res. Nees.Net-50, ImageNet)
$9.0
Time Saving
$5.0
75.0
53.
DMP
$2.
45.0
Reffle
Belll
$3.0
Strectural
Sparsity
Accuracy
61.0
Begreep
Dease
100
Scructural
Spursity
Accuracy
Sparnity
Sparsity
Figure 3: (Curve plats) Testing accuracy (%) over network sparsity levels (%) on Tiny-ImageNet and Im- ageNet datasets with ResNet-50 (25.56 M). (Radar plots) The end-to-end inference time saving of extreme structural winning tickets. Note that unstructured subnetworks or dense models do not have structural sparsity, and thus they are plotted as dots in the axes of accuracy in the corresponding radar plot. The rightmost plot includes three extreme regroup tickets with accuracy drop < 1%, where "RG S: =% indicates unstructured sparsity before regrouping.
From Tiny- ImageNett results in Figure 3 (left), several positive observations can be drawn: Struc- tural winning tickets with 60% channel-wiss structural sparsity and 74% group-wise structural spar- sity are located by IMP- -i-f-iiill fill and IMP MMMP-Regee Regroup respectively, which validate the effective- ness of our proposals. @ Although at the high sparsity levels (i.e., > 50%), IMP-Refill+ outperforms IMP-Re filll if they are from the same unstructured IMP subnetworks. Consider- ing the overall trade-off between channel-wise strcutural sparsity and accuracy, IMP-Refill ap- pears a clear advantage. A possible explanation is that refilling+ seems to bring undesired channels performs better high sparsities. It is within expectation since fine-grained group-wise structural patterns tend to make the networks be more amenable to pruning. ! Extreme channel- / group-wise structural win- ning tickets with 45% 50% 74% sparsity from AMP-Refill (+) / WMMP-Rerrup achieve 57. 07.53% ~ 61. 79% / 64.84% GPU running time savings, without sacrificing accuracies.
which potentially result in a degraded performance trade-off @
As for large-scale ImageNet experiments, the conclusion are slightly different: 1 There is almost no difference between the performance of IMP-Refill and IMP-Refill+ and both can not find channel-wise structural winning tickets. But seems to suggest our picking rule (i.e., channel weights" ε norm) provides great estimation for channel importance, although it is too aggressive for ImageNet experiments. @ The group-wiss structural winning ticket at 31% sparsity is still exist in (RN-50, ImageNet), while the low sparsity brings limited 1% time savings. For better efficiency and performance trade-off, IMP- SMP--RegE -ee-Reo is capable of locating structural subnetworks at 51% / 58% sparsity with 53. 33.75% / 64.84% time savings and 0.33% / 0.95% accuracy drop.
CIFAR with diverse network architectures. We then validate our approaches on CIFAR- 10/100 (C10/100) with diverse network backbones including and R88 Based on the extensive results in Figure and we find: O On ((WRN-32-2,C10), (WRN-32-2. 2,0000, (MBNet-vi,C1O), (MBNet-v1,C100) (VGG-16,C10), (VGG-16,C100), (RN- 18,C10), (8N-1), schemes, we consistently disclose the existence of structural winning tick- ets with (53%, 28%, 67%, 0%, 60%, 40%, 50%, 0%) channel- sparsity and {66%, 36%, 72%, 56%, 80%, 80%, 78%, 78%) group-wise sparsity from IMP-RefiL (+). and IMP- MMP-Regroup, respectively. @ With the same network, pursuing channel-wise sparse patterns on CIFAR-100 more challenging than it on CIFAR- 10, possibly due to the larger dataset complexity. On the same dataset, larger networks tend to have larger extreme sparsities for both channel- and group-wise structural winning tickets, with the exception of IMP-Re fill (+) on (RN-18, C100). @ At the middle sparsity levels (i.e., < 50%), SMMP-RegrOUS IMP Regroup has a superior performance at high sparsity levels. 4 Up to (57.75% 60.60%, 55.45%. 64.98% GPU running time savings are obtained by group-wise wise structural winning tickets (NN-88,C10))
MobileNet-vl, VGG-16,
behaves closely to IMP-Refill (+), while
with undamaged performance on ((VGG- which surpass IMP, IMP Refill (+), and dense models by a significant efficiency margin. A exception is that IMP- Re f 11 on (VGG-16,C10) achieves the best time savings, i.e., 63.11%
LVGG-16,CION
(RN-18.C10),
7

---

Under review as a conference paper at ICLR 2022
(WRN--2-22, C10)
(WRN-32-2, C100)
(MBNet-vl, C10)
(MBNei-v1. C100)
2401
40.0
7207
46.0
Accersay
Accureey
700
IHP
14P Rral KcEa" Rearvey
Ad31
R:08
11.
6611
RetE
Kudil
Hegrepp
Doine
60
Duare
193
Spansit
Sparsity
Spurddyy
Figure 4: Testing accuracy (%) over network sparsity levels (%) on CIFAR-10/100 with small models Wide-
ResNet-3222 (1.86 M) and MobileNet-vl (3.21 M).
(VGG-16, CIFAR-10)
(VGG-16, CIFAR-100)
Time Saving
Time Saving
-8.0
93.
DMP
INP
Reil
65.0
Ruml
Relli
Buf
Reg
$2.0
Doner
46
Structural
Sparsity
Accuracy
Structural
Sparsity
Sparsity
Sparsity
(ResNet-18, CIFAR-10)
(ResNet-18, CIFAR-I00)
Time Saving
Time Saving
74.0
Accuracy
13.0
-XC-
DMP
78.0
IMP
Hell
Hell-
$1.0
Doar
Structural
Sparsity
Accuracy
Structural
Sparsity
Accurncy
Sparsity
Spanity
Figure 5: (Curve plots) Testing accuracy (%) over network sparsity levels (%) CIFAR- 10/100 with large models VGG-16 (14.72 M) and RN-18 (11.22 M). (Radar plots) The end-to-end inference time saving of extreme structural winning tickets. Note that unstructured subnetworks dense models do not have structural sparsity, and thus they are plotted as dots in the axes of accuracy in the corresponding radar plot.
Layer-wise speedups. Figure 6 shows the layer-wise speedup performance of convolution oper- ations in VGG-16's extreme structured winning tickets from different algorithms. IMP Mee-RReroon roup presents impressive layer-wise speedups up to 6.67x compared to others, especially on the last a few layers (e.g., conv. 12). The possible reasons lie in two aspects: (i) the latter layers reach a larger compression ratio and have greater potentials for acceleration; convolutional layers (i.e., latter layers in VGG-16 with a larger number of kernels which benefits to group appropriate dense blocks, as also suggested by Rumi et al. (2020).
(ii) the regrouping algorithm prefers
B4
IMP-Re1Di
Megnop
12.55
C: 12.9
7.5-
3+
1:1011
10.08.5
C: 32.68
Speedup
59 50
5.0
2
6:6.25
C: 18,59
4:479
10.32
2.5
C: 4.25
0.0
Cons
Cocv 8
Con 9
Cony
Conv 11
Cocy 12 Cony 13
Cons 7
Canv 8
Cone
Com 10 Carv 11 Cons 12 Corv 13
Figure 6: The layer-wise performance of convolution operations in extreme structural winning tickets of (VGG-16, C10). first six conv. operations are omitted since there is no meaningful speedup, coincided with Rumi al. (2020.. Marks like "C: 2.77" indicate the layer-wise compression ratio of ReP-Regroup.
8

---

Under review as a conference paper at ICLR 2022
94.5
94.5
Accuracy
94.0
OMP
Rewiad 5%
Accuracy
93.5
Rewiad 10%
94.0
SNIP
Rewiad 20%
03.0
GraSp
00.0
Rewind 50%
SynPlom
93.5
Regrouping
ADMM
Random Reinit
Group-Awar IMP
Dense
Network
Deuse Network
92.0
$2.0
93.0
Spursity
Sparsity
Spursity
Figure 7: (Left) Performance of structural tickets grouped from diverse initial unstructured masks. (Middle)
Performance of group-wise structural tickets with different weight rewinding. (Right) Performance compar- isons between IMP AMP-Reep Ree--eggrooee gu and group-aware IMP as described in Algorithm Testing accuracies (%) over network sparsity levels (%) are reported on (RN-18,C10).
5 ABLATION STUDY AND VISUALIZATION
Different sources of unstructured masks. Intuitively, the initial unstructured sparse mask should plays an essential role in the achievable performance our proposed "post-proesssing techniques". We therefore conduct comprehensive ablation study about the various sources of the initial sparse masks in Figure 7 including IMP, OMP, RP, SNIP, GraSP, SynFlow, and ADMM. The details of comparison methods are included in Section 3.1 We observe that IMP and OMP provide initial unstructured masks with the top-2 highest quality for our regrouping algorithm, terms of the caa---foo--aatttee accuracy of grouped structural subnetworks.
Different initialization for the re-training. Initializa- tion (Frankle Carbin 2019 Renda et al.) (2200) an- other key factor in LTH, also contributes significantly the existence of winning tickets. To exhaustively in-
INP
vestigate the effect from different initialization (e.g., re-
wound weights), we launch experiments started from di-
180-2e1111
verse rewound weights (15%, 10,, 20%, 50%, 100%} of total training epochs) as well as a random re- initialization. As shown in Figure 7 using 50% rewound weight reach the overall best performance; other weight rewinding se- tups perform similarly and clearly surpass random re- initializing at sparsity levels 30%.
IPP Regroup
Group-aware IMP This work mainly focuses on the post post-processing of unstructured sparse masks. Another possibility is integrating regrouping into TMP by alter- natively performing unstructured magnitude pruning and regrouping, which we term as group-aware IMP. From Fig. 7 has a worse performance due to the stricter con- straint on sparse patterns, compared to IMP-Regroup.
Figure 8: Sparse mask visualizations of the extreme winning tickets from IMP (unstruc- tured), IMP-Refill (chamnel-wise struc- tural), and IMP-Regroup (group-wise structural) on (VGG-16,C10). The darker color indicates the remaining unpruned ele- ments. (a.b.c) are the three conv. layers.
Visualization of sparse masks. Figure visualizes different types of obtained sparse masks from (VGG-16,C10), Sub-figures (a.b,c) plot the mask matrices of size Cout n for certain layers. Similar the illustration in Figure IMP-RefiLl iill masks show clear kernel-wise sparse patterns across the rows, and IMP-Regron roup masks present fine-grained structural sparse patterns capable of forming neat dense blocks after regrouping.
CONCLUSION
In this paper, we challenge the "common sense" that an identified IMP winning ticket can only have unstructured sparsity, which severely limits its practical usage due to the irregular patterns. We for the first time demonstrate the existence of structural winning tickets by leveraging post-processing techniques, i.e., refilling(+) and regrouping. The located channel- and group-wise structural sub- networks achieve significant inference speedups up to 6.67x on hardware platforms. In this sense, positive results bridge the gap between the lottery ticket hypothesis and practical accelerations in real-world scenarios. We would be interested in examining LTH with more effective structural sparsity for real-time mobile computing in future work.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ibrahim Alabdulmohsin, Larisa Markeeva, Daniel Keysers, and Ilya Tolstikhin. A generalized lot- tery ticket hypothesis. arXiv preprint arXiv:2107.06825, 2021.
Peter I. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. arXiv preprint www.:v:2133091777. 2021.
Brian R Bartoldson, Ari S Morcos, Adrian Barbu, and Gordon Erlebacher. The generalization-
stability tradeoff in neural network pruning. arXiv preprint arXiv: 03728, 2019.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? arXiv preprint arXiv:2003.03033. 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. /4165, 2020.
Chun-Fu Chen, Jinwook Oh, Quanfu Fan, and Marco Pistoia. Sc-conv: Sparse-complementary convolution for efficient model utilization cnns. In 2018 IEEE International Symposium on Multimedia (ISM), pp. 97-100. IEEE, 2018.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. arXiv preprint arXiv:20/2.06908, 2020a.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint WwXiv:2007112233 2020b.
Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, and Zhangyang Wang. Ultradata-efffiieet gan training: Drawing lottery ticket first, then training toughly. arXiv preprint arXiv:2103.00397, 2021a.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks, 2021b.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Long live the lottery: The existence of winning tickets in lifelong learning. In International Conference on Learning Representations, 2021c.
Xiaohan Chen, Yu Cheng, Shuohang Wang. Zhe Gan, Zhangyang Wang. and Jingjing Liu. Earlybert: Efficient bert training via early-bird lottery tickets. arXiv preprint arXiv: 101. 101.00063, 2020c.
Xuhao Chen. Escort: Efficient sparse convolutional neural networks on gpus. arXiv preprint 1eX2v 2018
Xuxi Chen, Zhenyu Zhang, Yongduo Sui, and Tianlong Chen. {GAN)s can play lottery tick- ets too. In International Conference on Learning Representations, 2021d. URL https:
//openreview.
_jERR
Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catan- zaro, and Evan Shelhamer. cudnn: Efficient primitives for deep learning. arXiv preprint arXiv:1410.0759, 2014.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 245..55. leee, 2009.
Xiao Dong, Lei Liu, Peng Zhao, Guangli Li, Jiansong Li, Xueying Wang, and Xiaobing Feng. Acoms: A framework for accelerating deep neural networks with input sparsity. In 2019 28th International Conference on Parallel Architectures and Compilation Techniques (PACT), pp. 178- 191. IEFE, 2019.
10

---

Under review as a conference paper at ICLR 2022
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018.
Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint arXiv:
10732, 197.0222 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:// openreview net/ Saeerummdd:rJ--3336
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode con- nectivity and the lottery ticket hypothesis. In International Conference Machine Learning, pp- 3259-3269. PMLR, 2020a.
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. The early phase of neural network training. In International Conference Learning Representations, 2020b. URL https:
//openrevies net./formm/ forum? d=Hk WiRNEWS
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09577 2019.
Sharath Girish, Shishira R Maiya, Kamal Gupta, Hao Chen, Larry Davis, and Abhinav Shrivastava.
The lottery ticket hypothesis for object recognition. arXiv preprint arXiv:2012.04645 2020.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint IrXivv 20151
2015a. Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights and connections for efficient neural networks. arXiv preprint arXiv: 52..000002666... 2015b.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark Horowitz, and William Dally. Eie: efficient inference engine on compressed deep neural network. In ISCA, 2016.
Stephen Hanson and Lorien Pratt. Comparing biases for minimal network construction with back- propagation. Advances in neural information processing systems, 1:177-185, 1988.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp.
1389-1397, 2017.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. arXiv preprint 4rX1v:2102.00554, 2021.
Changwan Hong, Aravind Sukumaran MakuumrrnnRRajmm Bortik Bandyopadhyay. Jinsung Kim, Süreyya Emre Kurt, Israt Nisa, Shivani Sabhlok, Ümit V. Çatalyürek, Srinivasan Parthasarathy, and Sadayap- pan. Efficient sparse-matrix Effciinntsparss-mmatt 2018.
multi-vector product gpus. Association for Computing Machinery,
Changwan Hong. Aravind Sukumaran Rajjam, Israt Nisa, Kunal Singh, and P Sadayappan. Adaptive sparse tiling for sparse matrix multiplication. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, pp. 300-314, 2019.
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 2017.
Hengyuan Hu, Rui Peng, Yu-Wing Tai, and Chi- Chi-Keung Tang. Network trimming: A data-driven neuron pruning approach towards efficient deep architectures. arXiv preprint arXiv: 1607:0667.002500 2016.
11

---

Under review as a conference paper at ICLR 2022
Peng Jiang, Changwan Hong, and Gagan Agrawal. A novel data transformation and execution strat- egy for accelerating sparse matrix multiplication on gpus. PPoPP '20. Association for Computing Machinery, 2020.
Neha Mukund Kalibhat, Yogesh Balaji, and Soheil Feizi. Winning lottery tickets in deep generative models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7:7,2015. 2015.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr Snip: Single-shot network pruning based connection sensitivity. In International Conference Learning Representations (ICLR), 2019a.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity, International Conference on Learning Representations, 2019b. URL net/
https:
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint /rXiv:1608. 1608.08800 2016.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learn- ing efficient convolutional networks through network slimming. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2736-2744, 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In 7th International Conference Learning Representations, 2019.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1. 0 regularization. arXiv preprint 1rXiv:1712.011 1712.01 3/2,11222,, 12, 2017.
Haoyu Ma. Tianlong Chen, Ting-Kuei Hu, Chenyu You, Xiaohui Xie, and Zhangyang Wang. Good students play big lottery better. arXiv preprint www.:i:2X00.0330000 2021a.
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 dan weight pruning for real-time execution mobile devices. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5117-1244,4 2020.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Ming- hai Qin, Sijia Liu, Zhangyang Wang, et al. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? arXiv preprint arXiv:2107.00166, 2021b
Huizi Mao, Song Han, Jeff Pool, Wenshuo Li, Xingyu Liu, Yu Wang, and William Dally. Exploring the regularity of sparse structure in convolutional neural networks. arXiv preprint arXiv: 1705.00700 2017.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 11264-11272. 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-bat basedd weight pruning, arXiv preprint 2800022001.00/38, 2020.
12

---

Under review as a conference paper at ICLR 2022
Jongsoo Park, Sheng Li, Wei Wen, Ping Tak Peter Tang, Hai Li, Yiran Chen, and Pradeep Dubey- Faster cnns with direct sparse convolutions and guided pruning. In International Conference on Learning Representations, 2016.
Kuo- You Peng, Sheng- Yu Fu, Yu-Ping Liu, and Wei-Chung Hsu. Adaptive runtime exploiting spar- sity in tensor of deep learning neural network on heterogeneous systems. In 2017 International Conference on Embedded Compuler Systems: Architectures, Modeling, and Simulation (SAMOS),
pp. 105-112. IEEE, 2017.
Sai Prasanna, Anna Rogers, and Anna Rumshisky. When bert plays the lottery, all tickets are win- ning. arXiv preprint arXiv:2005. 00060, 2020.
Valentin Radu, Kuba Kaszyk, Yuan Wen, Jack Turner, José Cano, Elliot J Crowley, Björn Franke, Amos Storkey, and Michael O' Boyle. Performance aware convolutional neural network channel pruning for embedded gpus. 2019 IEEE International Symposium on Workload Characteriza- tion (HSWC), pp. 24-34. IEEE, 2019.
Ao Ren, Tianyun Zhang, Shaokai Yc, Jiayu Li. Wenyao Xu, Xuchai Qian, Xue Lin, and Yanzhi Wang. Admm-nn: An seorithm-hardwaar co-design framework of dnns using alternating diree- tion method of multipliers, 2018.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In 8th International Conference on Learning Representations, 2020.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint 04747, 2016.
Masuma Akter Rumi, Xiaolong Ma, Yanzhi Wang, and Peng Jiang. Accelerating sparse enn infer- ence on gpus with performance-aware weight pruning. In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, pp. 267- 2020.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. In Advances in Neural Information Processing Systems 33 pre-proceedings, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems 33 pre pre-proceedings, 2020.
Chaoqi Wang. Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. In International Conference Learning Representations, 2020. URL
/tttps://openreee ew net / www.:/eeeeoottioeeeoooeoo.m. forumm?dd=Sksscc/E..
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in neural information processing systems (NeurIPS), pp. 2074-2082, 2016.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations, 2020. URL https:
7/openzeview. saapen/reveww.ee//orrmeee wttp:/etttoooommeecce....see
Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S. Morcos. Playing the lottery with rewards
and multiple languages: lottery tickets in rl and nip. In 8th International Conference on Learning Representations, 2020.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016.
Wide residual
networks.
arXiv preprint
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 multipliers. In ECCV, 2018.
13

---

Under review as a conference paper at ICLR 2022
Maohua Zhu, Tao Zhang, Zhenyu Gu, and Yuan Xie. Sparse tensor core: Algorithm and hardware co-design for vector wise sparse neural networks on modern gpus. In Proceedings of the 52nd Anmual IEEE/ACM International Symposium on Microarchitectuure pp- 359-371, 2019.
A1 MORE IMPLEMENTATION DETAILS
Group-aware IMP Here provides the detailed procedures of group-aware IMP in Algorithm 4
Intuitively, it embeds regrouping (Algorithm B into IMP (Algorithm I by performing regrouping on the unstructured mask from each IMP round.
Algorithm 4: Group-aware IMP
Input: f(; Bu), group-wii wise structural sparsity
Output: (a; m O 8,) with group-wise structural sparse mask
Set the pruning mask m
R!9
Train f(a; 0o) to rewinding step i: (2;00) AT
while reach sparsity do
Train [x;; m @ 0;) to step t: [a;; m @ 0.) = (1
Pruning 20% of remaining weight of m @ 02, and update m
Refining the unstructured mask m by performing regrouping, as shown in Algorithm 3
end
Profiling. To compute the GPU running time of regrouped convolution layers, we adopt their CUDA C/C++ implementation. Our results do not include the running time of normalization and activation layers, following the standard in Rumi et al. (2020). For a fair calculation, we feed the same input features convolution layers that belong to the same model. For ResNet-18 and VGG- 16, the size of the input features is (64, 64, 127, 127). For ResNet-50, the size of input features is (64, 64, 64, 64). The GPU use for profiling is NVIDIA RTX 2080 TI, with CUDA version of 10.2 and a cuDNN (Chetlur et al.) 2014) version of 7.6.5.
A2 MORE EXPERIMENT RESULTS
Different channel picking criterion for refilling. We ablation the channel picking criterion for IMP-Re (+), including ! the & norm of channel's remaining weight, @ the E or & norms of channel's feature map, K the number of remaining weights in the channel, + the channel's saliency score (Molchanov et al. 2019). Experiment results are collected Figure A9 which demonstrate
the superior performance of IMP -ffill l of channel weights (yellow curve).
(ResNet-18, CIFAR-10)
95
94
Unstructured w. 4 of Weights
Accuracy
Refilling 21 of Weights
93
Refilling w. f1 of Features
Refilling 82 Features
92
Refilling w. Remaining Weights
Refilling w. Saliency Scores
Dense Network
91
20
40
60
80
100
Sparsity
Figure A9: Performance of structural tickets refilled by diverse channel picking criterion. Testing accuracies (%) over network sparsity levels (%) reported (RN-18,C10).
A14

---

Under review as a conference paper at ICLR 2022
All sections of newly added results and discussions highlighted.
A3 APPLICATION TO OTHER TICKETS
We further study whether methods rely types of random initialization. We first identify tickets ResNet-50 on ImageNet, and then transfer the tickets we have found to CIFAR-10. The test accuracy of the un-pruned (dense) ResNet-50 sults from IMP-RefiL ill IMP-Regroup and are reported in Table A2 We can see from Ta- ble A2 that IMP-Re fill can locate structured winning tickets the sparsity around 36%, and IMP Regroup can locate structured winning tickets at higher sparsity (more than 56.00%). These results suggest that our refill and regroup method can work on another kind of tickets (i.e., pre- training tickets)
CIFAR-10 is 95.37%. Multiple
Table A2:
Testing accuracy and percentage of remaining weights on ResNet-50 with CIFAR-10. and Reg-Rugr are evaluated. The baseline (test accuracy
Different methods of the dense network) is 95.37%.
IMP Refill
IMP uep-Rerroup
Remaining Weight
Accuracy
Remaining Weight
Accuracy
64.14%
95.81
77.28%
94,94
51.37%
95.14
71.40%
96.28
41.01%
94.51
67.60%
94.09
32.76%
94.38
59.43%
95.65
26.17%
94.19
51.84%
95.39
20.97%
94.11
43.99%
95.51
A4 RESULTS UNDER DIFFERENT TRAINING SETTINGS
To provide more experimental results, we launch experiments under different settings with VGG-16, 22,, and ResNet-50. The changes of training settings summarized below:
1. For VGG-16, we increase the number of training epochs to 240, and we decay the learning rate at 150th, 180th, and 210th epoch.
did not split the official training set into the training and a validation set as other experiments did. We also report the best validation accuracy instead of the best test accuracy. We also increase the number of training epochs to 240 and decay the learning rate at 150th, 180th, and 210th epoch.
For WideResNet-322.
3. For ResNet-50, we replace the first convolution layer to be of kernel size 3, padding size 1, and strides 1.
VGG-16 on CIFAR-100. The proportion of remaining weights and testing accuracy of (VGG- 16,C100) are shown in Table A3 From the table we can see that our conclusions still hold: IMP-Regroup can locate structured winning tickets at very high sparsity (> 75%).
The proportion of remaining weights and testing accuracy of (WRN-32-2.C100)) are shown Table From the table we can see that our conclusions still hold: IMP IMP-Regroup can locate structured winning tickets at about 75% sparsity, and IMP-Refil can locate structured winning tickets 20% sparsity.
WideResNett32-22 on CIFAR-100.
The proportion of remaining weights and testing accuracy of (RN-50, Imay-ImageNet) are shown in Table A3 From the table we can see that our conclu- sions still hold: IMP-Regroup locate structured winning tickets at about 42% sparsity, and IMP-Re f 11 can locate structured winning tickets at 20% sparsity.
ResNet-50 Nmag-
A15

---

Under review as a conference paper at ICLR 2022
Table A3: Testing accuracy and percentage of remaining weights CIFAR-I00 with VGG-16.
Different methods (IMP, IMP-Refil Refill, and (MP-Regroup) are evaluated. The baseline (test accuracy of the dense network) 73.43%.
IMP
IMP-Refill
IMP IMP-Regroup
Round
Remaining Weight
Accuracy
Remaining Weight
Accuracy
Remaining Weight
Accuracy
1
80.00%
73.64
80.17%
73.43
82.36%
73.63
2
64.00%
73.80
64.06%
72.87
80.00%
73.81
3
51.20%
73.67
51.31%
72.67
69.46%
74.31
4
40.96%
74.01
41.08%
71.37
62.61%
73.94
5
32.77%
74.27
32.85%
70.79
56.09%
75.05
6 26.21% %
74.56
26.33%
71.07
46.53%
74.98
7
20.97%
74.58
21.03%
69.42
38. 18%
75.24
16.78%
74.52
16.94%
68.75
30.98%
74.68
13.42%
74.42
13.42%
67.25
25.27%
75.25
Table A4: Testing accuracy and percentage of remaining weights on CIFAR- 100 with WideResNet- 32-2. Different methods (IMP, IMP Reffllg and IMP Regroup) are evaluated. The baseline (validation accuracy of the dense network) is 75.53%.
Round
1MP
1MF Refill
1MP Regroup
Remaining Weight
Accuracy
Remaining Weight
Accuracy
Remaining Weight
Accuracy
80.00%
76.21
80.00%
75.46
75.98
2
64.00%
75.78
64.06%
74.59
64.00%
76.19
3
51.20%
76.02
51.51%
73.53
$1.20%
76.
4
40,96%
75.92
41.51%
72.95
40.96%
75.88
5
32.77%
76.07
32.84%
72.12
32.99%
75.98
26.21% %
75.74
26.53%
70.91
26.27%
75.78
7 20.97%
75.92
21.11%
69.55
21.76%
74.74
8 16.78%
75.87
17.11%
67.74
18.14%
73.85
13.42% 9
75.41
13.67%
65.73
14.85%
72.99
Table AS: Testing accuracy and percentage of remaining weights on Tiny-mmageNet with ResNet- 50 (second implementation). Different methods (IMP, IMP IMP-Refill. and IMP-Regroup) are evaluated. The baseline (test accuracy the dense network) is 65.33%.
Round
IMP
IMP Refill
IMP Regroup
Remaining Weight
Accuracy
Remaining Weight
Accuracy
Remaining Weight
Accuracy
1
80.00%
65.44
80.30%
65.27
80.15%
65.51
2
64.00%
65.69
64.16%
63.40
68.25%
65.16
3
51.20%
65.50
51.42%
61.89
58.19%
65.21
4
40.96%
65.73
41.08%
60.43
$4.19%
64.42
5
32.77%
65.23
32.85%
59.64
51.75%
64.52
A16

---

Under review as a conference paper at ICLR 2022
A5 FLOPS RESULTS
We calculate the FLOPs of VGG-16 on CIFAR-10 processed with different methods. The FLOPs of the dense VGG-16 16 is about 0.314G. We select models with similar sparsity for better comparison. The sparsities of IMP-Refill IMP-Refill+, and IMP- Reg-Rugroup are {32.84%, 46.41%, 20.12% spectively, and the FLOPs are (0.089G, 0.122G, 0.093G), respectively. is noteworthy that Refill and Refil++ will lower the input and the output channel of a convolution layer while Regroup cannot, so Refill and Refil++ can save more FLOPs under the same level of sparsity.
A6 OTHER VISUALIZATION
From Figure A10 we can see that, similar IMP-Refill, IMP- MMP-Refil++ masks also show kernel-wise sparse patterns across the rows.
8
IMP IMP Re--Rfill++
8
Figure A10: Sparse mask visualizations of the extreme winning tickets from IMP-Refill- (channel-wise structural), and (VGG-16,C10). The darker color indicates the remaining un- pruned elements. (a,b,c) are the last three conv. layers.
Except radar plots, also include histograms to demonstrate the triads Sparsity, Speedup, and Accuracy, which are shown in Figure A11 In each histogram, we report the metrics of four methods: Dense, IMP-Re f fill, IMP-Re 11+ and IMP-Reg speedup, so the corresponding bars are always unseen from the charts.
Dense has sparsity and no
(ResNei-IK, CIFAR-IB)
(ResNet-18, CIFAR-100)
(RecNet 50, Tiny- ImageNet)
(ReaNet-50. ImageNett
Figure All: The sparsity, speedup, and test accuracy of various models (ResNet-18, VGG-19, ResNet-50) various datasets (CIFAR-100-100, Tiny ImageNet, ImageNet).
A17


Reviews:
[{"review_id": "ztCLzxBIzWu", "reviewer": "Reviewer_7uex", "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": "# Strength:\n\nThe structural sparsity and unstructured sparsity are not new. However, in previous works about the lottery ticket hypothesis (LTH), the winning tickets are typically unstructured. Therefore, the idea of finding structural winning tickets is meaningful, and the existence of structural winning tickets fills in a crucial piece of the puzzle for the LTH. In this work, the authors propose a method to find structural winning tickets. Extensive experiments on various datasets and network structures show the method is effective and efficient.\n\n# Weakness:\n\n1. In some experiments (such as Figs. 3 and 5), the authors report time-saving when using a specific GPU and batch size. The time saving might vary when other GPUs or batch sizes are used. Therefore, I believe it would be better to also include the number of FLOPs in the results.\n2. IMP-Refill and IMP-Refill+ generate different results. Why only IMP-Refill is included in Fig. 8?\n3. In Figs. 3, 4, and 5, it seems different methods stop at different percentages of sparsity. Why don't they all prune to the same percentage?", "summary_of_the_paper": "This work proposes a method to effectively find structurally sparse winning tickets. It consists of some post-processing techniques that can be added to each round of standard iterative magnitude pruning (IMP) methods. Starting from unstructured sparse sub-networks, the method uses a \"re-filling and re-grouping\" manner to enforce the formation of structural sparsity.", "summary_of_the_review": "This work demonstrate that lottery tickets can not only be unstructured but also be structural, which makes it a novel and interesting work. There are minor issues in experiments.", "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": "YdyFpAsly7F", "reviewer": "Reviewer_iox5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is well known that lottery tickets so far are only successfully found with unstructured pruning. This paper challenges this commonsense, and its positive finding could be of broad interest and impact. Instead of directly adopting structural pruning, the authors propose the postprocessing techniques to accompany IMP, namely, the refilling/regrouping algorithm to form channel-wise and group-wise structural sparsity, respectively. These algorithms are simple and intuitive, yet novel and convincing.  The paper for the first time achieves high sparsity (up to 80%) with structure in the lottery ticket literature and shows practical GPU hardware runtime savings at around 50-60%.\n\nI suggest the authors to tone down their claims. There definitely exist similar works in relevant problem domains, such as sparse training with structures: for example, “Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch” ICLR 2021, should be discussed and compared. \nBesides the scientific interest, I am not sure if I understand from a practical point of view, why we really need particularly pursue a structurally sparse lottery ticket, in contrast to directly using a structurally pruned NN. \nAlso, how this work compares to using NAS to search for channel numbers?\nI don't understand for ImageNet, why the current results can show \"our picking rule (i.e., channel weights l1 norm) provides a great estimation for channel importance\"\nNo theoretical insight on why the proposed algorithm can work is provided. But for an empirical pilot study, this is fair and acceptable.\n", "summary_of_the_paper": "This work demonstrates the existence of structural winning tickets for the first time by leveraging post-processing techniques.", "summary_of_the_review": "The contribution of this paper is solid. I hope the authors could clarify the weak points.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Kf-IYur-3mv", "reviewer": "Reviewer_YWUh", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths\n\n●\tUp to date, LTH has not been shown valid on structured pruning (I mean, filter pruning or channel pruning). This paper is meant to bridge this gap, which could be a significant step forward.\n\n●\tThey propose several post-processing techniques, which deliver practical speedup. Potentially, they can be very useful.\n\nWeaknesses\n\n1.\tOne contribution this paper keeps emphasizing is that they find structural winning tickets for the first time. However, some important concepts, baseline results are either not established or (potentially) flawed. I do not think the presented results can faithfully support their claimed contribution.\n\nFirst, one important property of LTH is that, if the subnet is trained using randomly re-initialized weights instead of the winning tickets, the subnet cannot achieve full accuracy. This paper does not have this kind of comparison at all. For example, Fig. 3, for channel sparsity (refill and refill+, not regroup), what are the accuracies when you train the pruned network from scratch (I mean, fully randomly reinit all the weights in the pruned network)? Without this comparison, we cannot tell if the initial weights can be identified as “winning tickets” in the first place.\n\nSecond, the presented results are (potentially) flawed. Many baseline accuracies are far below the average reported by other papers. E.g., in Fig. 3, ResNet50 on TinyImageNet, others typically can get ~67% accuracy (see [1*]), while this paper only got a little bit over 53% at sparsity 0. More than 10% gap.\n\nSimilar issue: Fig 3, ResNet50 on ImageNet. The typical top-1 accuracy is around 76.1% (see torchvision models), while this paper reports 75.2%. Nearly 1 point top-1 accuracy drop on ImageNet is quite big. Fig 4, their WRN-32-2 on CIFAR100 only achieves 72%, while even WRN-16-2 (much smaller than WRN-32-2) can achieve 73.26% (see [2*]). Fig 5, their VGG16 on CIFAR100 only archives less than 72%, while VGG13 can achieve over 74% (see [2*]).\n\nI thus deeply doubt the validity of these experiments -- Note, the accuracy of dense models is important in validating LTH because it is the baseline accuracy that subnets are going to compare against. Using a lower baseline accuracy, of course it would be easy to achieve high sparsity “without performance drop”. \n\n-- I think this is also why in many plots, the accuracy of pruned models can strangely surpass their dense counterparts even at a large sparsity.\n\n2.\tThey do not really achieve what they claimed.\n\nIn pruning literature, structured pruning typically narrowly means filter or channel pruning,  while this paper actually also refers to a more fine-grained sparsity structure (see the “Group-wise Structural Sparse Mask” in Fig. 2). This actually make it much less interesting, because this kind of sparsity still needs customized implementation (“a more sophisticated GEMM-based efficient implementation (Rumi et al., 2020) is needed to accelerate better our refilled / regrouped structural patterns”). How to get practical speedup is actually unknown from this paper (they defer many important details to (Rumi et al., 2020)). \n\nThen, only look at the channel sparsity. Fig. 3, ResNe50 on ImageNet, Refill and Refill+ start to drop accuracy even at a marginal sparsity. This means they do not find winning tickets. They also admitted this in the paper: “There is almost no difference between the performance of IMP-Refill and IMP-Refill+, and both can not find channel-wise structural winning tickets”. \n\nWhat attracted me at the first sight of this paper is that they validate LTH on filter/channel pruning. Unfortunately, they do not really achieve what they claimed. \n\n3.\tFrom the methodology perspective, the proposed techniques are “post-processing”. Most structured pruning methods are independent from unstructured pruning. While here, they blend them together with “post-processing” instead of proposing a really independent technique to find winning tickets for filter/channel sparsity. I would say, it doesn't look like an elegant neat scheme (although “elegant” may not be really important).\n\n4.\tMinor issue. Presentation: Fig. 3, radar plots. It is pretty hard to read the radar plots. In Particular, some dots are overlapping and pretty small. They are barely recognizable in print. They can be presented in a better way.\n\n[1*] https://openaccess.thecvf.com/content_CVPR_2020/papers/Yuan_Revisiting_Knowledge_Distillation_via_Label_Smoothing_Regularization_CVPR_2020_paper.pdf\n\n[2*] https://arxiv.org/pdf/1910.10699.pdf, ICLR 2020\n", "summary_of_the_paper": "LTH (lottery ticket hypothesis) was mainly proposed for unstructured pruning. This paper shows it can also be validated on structured pruning, for the first time. The key for them to achieve so is the newly proposed post-processing techniques, refilling(+) and regrouping. They show by these techniques, structural winning tickets can be found, with up to 6.67x on hardware platforms.", "summary_of_the_review": "Important baseline results are missing. Experiments are potentially flawed. They claimed what is not really realized in the paper.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": {}}, {"review_id": "H-KXaxpj66", "reviewer": "Reviewer_TFc4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors explored hardware-friendly structural sparsity (including channel-wise and group-wise patterns) to find lottery tickets. They propose new refilling techniques based on the classical iterative unstructured pruning process to create channel-wise structural sparsity by growing back the pruned elements within the most important channels and abandoning the rest. \n\nOn top of that, they introduce another regrouping algorithm based on hypergraph partitioning (Rumi et al., 2020) to establish group-wise structural patterns which are more amenable to pruning due to the shape flexibility of grouped blocks. \n\nThe authors reported many experiments on CIFAR-10, CIFAR-100, TinyImageNet, and ImageNet, using various backbones like ResNets, VGGs, and MobileNets. Overall, the structural winning tickets are shown to achieve 53.75% ∼ 64.93% GPU running time savings at 45% ∼ 80% channel- or group-wise sparsity. \n\nOne should note that the sparsity level discussed in this work is not as the usual high as in unstructured tickets (often >95%), but the hardware acceleration is way more apparent. The ablation studies and visualization are thorough. \n\nI have just a few clarifications or curiosity questions:\n- It seems the acceleration effect on the structural ticket (especially after regrouping) requires some specific hardware accelerator and efficient implementations such as GEMM. It is then unclear whether the comparison with vanilla LTH is fair or not: could unstructured tickets also benefit from those? How much performance gain of the reported numbers comes from hardware specialization (Rumi 2020)?\n- Whether the same techniques can be applied to lottery tickets found not from random initialization, e.g., how about the pre-trained model lottery tickets as in (Chen et al., 2020b)? Will the refilling/regrouping rely on random weight initialization anyhow?\n- How much is the extra overhead of refilling/regrouping compared to the IMP cost?", "summary_of_the_paper": "The paper presents an exciting new finding – by properly reorganizing elements during the IMP process, it’s possible to achieve structurally sparse winning tickets at high sparsity levels that can be easily hardware accelerated.", "summary_of_the_review": "The paper is in a good shape that displays the first set of positive results bridging the gap between the lottery ticket hypothesis and practical accelerations on real-world hardware. Algorithm details, as well as results, are sufficient and convincing.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ### Summary

This work demonstrates that it is possible to identify lottery tickets with some manner of structural sparsity. The work finds success through refilling (perhaps better termed infilling) and regrouping, two techniques that have found previous homes in other parts of the literature. 

### Discussion

#### Strengths

- Tackles an interesting problem. 

- At face value, I believe the paper achieves its claimed goal, though not with full clarity as written.

#### Weaknesses

- There is room to clarify the atypical form of structure here for readers. The suggested title change would appropriately set expectations. However, refinements in the text as well would be welcomed.

- As I discuss below, the claims should be settled with respect to the strongest baselines.

- Random reinitialization should play a primary role in the presentation of the text. As the authors note, the original lottery ticket paper did not require besting the performance of random reinitialization. However, the random reinitialization results are central to the main figures of the original paper and demonstrate that the result is not merely happenstance. This paper should follow that practice.

### Recommendation

I recommend Reject and I do not do so lightly, given the scores. The work here is promising because finding a path to better-performing lottery tickets remains an open challenge. However, Reviewer YWUh has voiced reasonable concerns about the evaluation methodology. 

I've read the detailed authors' responses and agree with the authors that the presented results may depend on choices in the hyperparameters and training strategy. Having said that, it is critically important for the paper to include in the primary text the strongest baselines available, despite this dependence. On such baselines, the results are worse than originally reported and hence, the primary claims must either be revised to be these results or revised to include these results, with the primary claims providing a range of results. Though the authors offer to make revisions for the camera-ready, the required revisions here are substantial enough to require additional review, which is out of the scope of the current process.

An additional oversight in this methodology -- at least as reported -- is that the primary target of the lottery ticket hypothesis is sparse training, not sparse inference. Evaluating solely the inference performance -- rather than training performance, which includes both the forward and backward pass -- is, therefore, inconsistent with the purpose of lottery tickets. This methodological error will too need to be repaired in the final version of this work.
Decision: Reject