Exposing and Exploiting Fine-Grained Block Structures for Fast and Accurate Sparse Training
Authors: Peng Jiang
Lihan Hu
Shihui Song
Venue: NeurIPS 2022 Accept (2022)
Keywords: sparse training

Abstract: Sparse training is a popular technique to reduce the overhead of training large models. Although previous work has shown promising results for nonstructured sparse models, it is still unclear whether a sparse model with structural constraints can be trained from scratch to high accuracy. In this work, we study the dynamic sparse training for a class of sparse models with shuffled block structures. Compared to nonstructured models, such fine-grained structured models are more hardware-friendly and can effectively accelerate the training process. We propose an algorithm that keeps adapting the sparse model while maintaining the active parameters in shuffled blocks. We conduct experiments on a variety of networks and datasets and obtain positive results. In particular, on ImageNet, we achieve dense accuracy for ResNet50 and ResNet18 at 0.5 sparsity. On CIFAR10/100, we show that dense accuracy can be recovered at 0.6 sparsity for various models. At higher sparsity, our algorithm can still match the accuracy of nonstructured sparse training in most cases, while reducing the training time by up to 5x due to the fine-grained block structures in the models. 

Exposing and Exploiting Fine-Grained Block Structures for Fast and Accurate Sparse Training
Peng Jiang The University of Iowa lowa City, USA peng-jiang @ @ioowa.edu
Lihan Hu The University of Iowa Iowa City, USA lihan-hu @uiwwa.edu
Shihui Song
The University of lowa Iowa City, USA shihui-song @ uiowa.edu
Abstract
Sparse training is a popular technique to reduce the overhead of training large models. Although previous work has shown promising results for nonstructured sparse models, is still unclear whether sparse model with structural constraints can be trained from scratch high accuracy. In this work, study the dy- namic sparse training for class of sparse models with shuffled block structures. Compared nonstructured models, such fine-grained structured models are more hardware-frice -erenrrrrffeeyyyy-ee and can effectively accelerate the training process. We propose an algorithm that keeps adapting the sparse model while maintaining the active parameters in shuffled blocks. We conduct experiments on a variety of networks and datasets and obtain positive results. In particular, on ImageNet, we achieve dense accuracy for ResNer50 and ResNet1 8 at 0.5 sparsity. On CIFAR1ON 10/100, we show that dense accuracy can be recovered at 0.6 sparsity for various models. At higher sparsity, algorithm can still match the accuracy of nonstructured sparse training most cases, while reducing the training time by up to 5x due the fine-grinned block structures in the models.
Introduction
As large neural networks keep advancing the state-of-the-art in many machine learning tasks, training the models has become increasingly expensive. It is reported that training GPT-3 costs an estimated $12 million in computational resources 41. To reduce the cost, there is growing interest in developing sparse training algorithms B0 g
26 27]. By computing on small subset of parameters throughout the training process, these algorithms aim to reduce the memory and computing power consumption for large-scale neural network training.
The existing sparse training methods can be categorized as either static or dynamic. While training static sparse model from scratch is appealing, usually requires nontrivial initialization to achieve good accuracy p 2X 22 In contrast, dynamic sparse training uses simple random initialization. In every few iterations, it drops small number of 'unimportant" weights and replaces them with some new parameters. By exploring larger set of parameters than the sparse model itself, dynamic sparse training. in general, achieves higher accuracy than static sparse training
[4]
Most of the existing dynamic sparse training methods focus on nonstructured models. That is, the active parameters are scattered in the model without any constraints. Although they can retain high accuracy with much fewer parameters, the nonstructured sparse models do not necessarily accelerate the training process because the irregular computation suffers from poor data locality and low parallelism 1 39 A common way improve the efficiency of sparse models is by imposing structures on model parameters. However, current structured models have only been shown attainable by pruning and mostly beneficial to inference obtained by sparse training and in tur accelerate the training process still an open problem.
[3] 39
Whether structured models can be
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Before
After
2
3
1
drop
grow
shuffle
blocking
2
3
active
removed
added
Figure 1: Model adaptation in shuffled block dynamic sparse training: The active weights are organized in shuffled blocks before adaptation. Any weight can be dropped but new weights must be added in blocks. The new model is reorganized to ensure that all active weights are in shuffled blocks after adaptation.
Some recent work has explored fine-grained structures in sparse models for efficient training. For example, Hubara et al. [17] propose method to find N:M transposable sparsity that can benefit both the forward and backward pass. However, their method relies on specialized hardware (sparse tensor cores). Chen et al. structures. Although they show promising results that such strucstruet models can be trained to high accuracy from scratch, how to generate winning ticket without dense training remains unclear.
[ test the lottery ticket hypothesis [9] for sparse models with shuffled block
In this work, we take step forward and investigate the existence of fine-g grained block structures in sparse models with dynamic sparse training. Our idea is illustrated in Fig. I We first initialize sparse model and group the parameters in shuffled blocks. Since the shuffled blocks and their transposes can be efficiently processed by hardware, our method accelerates both the forward and backward pass. In every few iterations, we adapt the model by dropping the smallest weights and adding back the same number of new parameters. Different from previous work which selects new parameters based on dense gradients [8] dense weights [8. we select blocks of new parameters directly based on the input value and output gradient of each layer. making our algorithm purely sparse. The adapted model shuffled and blocked again ensure that the active weights are always organized in shuffled blocks.
We test algorithm variety of networks and datasets and answer the following questions:
Can randomly initialized sparse model with fine- grained block structures be trained high accuracy? We train a ResNet18 and ResNet50 of 0.5 sparsity with parameters constrained in shuffled blocks of size x on the ImageNet dataset, and we recover the accuracy of dense models. When the sparsity increases to 0.75, the accuracy drops slightly but still matches the accuracy of nonstructured models with dynamic sparse training. The result is further validated with various models on the CIFAR10/100 dataset.
2. Does the model adaptation of dynamic sparse training help improve the accuracy of sparse models with fined- grained block structures? We train sparse models with parameters shuffled blocks with and without model adaptation. For ResNet18 and ResNet50 ImageNet, the dynamic approach achieves more than 1% higher accuracy than static training. For different models on CIFARI0/100 dynamic training also achieves higher accuracy than static training, and the improvement is more noticeable when the sparsity is higher.
What the tradeoff between accuracy and hardware efficiency with different block sizes? We train sparse models with different block sizes on CIFAR10/100 As expected, models with smaller block structures achieve higher accuracy. We find that the accuracy difference is small for block size 4, 8, 16 and is more noticeable for block size 32. The sparse operations 16 x 16 can be more than 3x faster than on blocks of size 4 x 4, but the performance improvement small when the block size increases 32. This suggests that block size 16 can achieve good tradeoff' between accuracy and efficiency.
blocks of size
To the best of our knowledge, our work is the first to apply shuffled blocking of model parameters to dynamic sparse training. We believe that our findings can inspire future research on designing hardware-cfficient sparse training algorithms.

---

2
Related Work
Neural network pruning. The conflict between the ever-increasing size of neural networks and the limited computing capacity of hardware has inspired lot of research neural network pruning. Early works include [C 42 33 in which iterative and heuristic pruning methods with limited and nonstructured sparsity were proposed. These works focus reducing the size of neural networks but do not consider their performance carefully. The performance issue with nonstructured pruning is later identified in 20), where the authors propose to prune the entire input or output channels so that they can be easily accelerated on CPU and GPU. The downside of these structured pruning methods is that they suffer from notable accuracy loss when sparsity increases. To combine the benefits of structured and nonstructured pruming, hybrid pruning strategies have been proposed. Ma et al. propose pattern- based kernel pruning 2 for convolutional neural networks. The convolution kernels can only be pruned to one of several pre-defined patterns so that the pruned model contains some regular structures. Zhu et al. propose rector-wise pruning 45 They divide the weight matrix into fixed-size vectors and keep the top-K elements in each vector. In addition to vector-wiss pruning, the authors also adapt the tensor core architecture on GPUs to sparse tensor core in order to support the efficient execution of their vector-wise pruned models. Rumi et al. propose the first fine-grained block-structured pruning method for convolutional neural networks [36]. They reorder the convolution kernel matrix with a hypergraph partitioning procedure and group the nonzero weights into a number of shuffled blocks. The authors also provide a CUDA implementation of the convolution operation, and show its performance advantage over nonstructured sparse models and dense models on GPU. Recently, the shuffled blocking technique is extended for exploiting dense tensor cores on GPU to further accelerate the computation [16]. Some structured pruning methods can also reduce the computation in each iteration of the training process. However, these methods usually require much more training iterations to recover accuracy. For example, Hrank [24] prunes the convolution layers one-by-one and needs to fine-tune the model for 30 epochs after every layer is pruned. ABCPruner [245] performs end-to-end fine-tuning, but it needs run the entire training process for multiple cycles. ResRep 77 avoids fine-tuning, but it needs to add extra "compactor" parameters for selecting the channels, resulting in extra computation in each iteration. Moreover, these structured pruning methods require a pre-trained model as input.
buuffled-blok--eee
Sparse training. Pruming generates sparse models that are fast for inference; however, it does not accelerate the training process. In fact, pruning often needs to be conducted iteratively and increases the training overhead. As neural networks keep growing larger and training becomes prohibitively expensive, people start to be interested in exploiting sparsity to reduce the training cost. Mocanu et al. propose the first dynamic sparse training algorithm, Sparse Evolutionary Training (SET), which starts training with randomly initialized sparse model, prunes weights with small magnitude and adds back weights at random periodically (0). Following SET, Bellec el al. propose Deep Rewiring which augments traditional stochastic gradient descent with a random walk in parameter space 2 Mostafa et al. propose Dynamic Sparse Reparameterization (DSR) which allows the parameter budget to shift between different layers [3]]. Dettmers et al. propose Sparse Networks from Scratch (SNFS) which uses the momentum of each parameter as the criterion for growing weights [5]. Evci et al. point out that all these algorithms can be expressed with a troo-anddgrov framework and propose RigL. which uses the gradient magnitude as the grow criterion
R. An issue with RigL. is that it needs to compute the full gradient every few iterations, which may not be affordable for large models. Top-kast addresses this issue by maintaining all the weights but computing gradients on a small subset of weights in each iteration. Although these sparse training algorithms show promising results, they still have an accuracy gap with pruning methods. Recently, researchers show that this gap can be closed by using small batchsize and training for more iterations 26) or by interleaving sparse training with dense training phases M4 Besides dynamic sparse training, there has been a line of research on static sparse training. Lee et al. propose Single-Shot Network Pruning (SNIP) which finds an initial mask with one-shot pruning and keeps the sparse model fixed during training (2) In a follow-up paper, they refine their initialization method from signal propagation perspective [22] Frankle et al. propose the Lottery Ticket Hypothesis (LTH) which states that a sparse model can be trained to match the accuracy of the dense model if a good initialization is provided [9]. While appealing, the effectiveness of LTH in reducing the training cost is still unclear as obtaining the "winning ticket" is usually nontrivial 44 D..
Most of the existing sparse training algorithms (either static or dynamic) focus on nonstructured sparse models, Although they reduce the number of floating- operations, these models cannot
3

---

run efficiently on hardware due to their irregular memory access patterns and limited parallelism. This puts the practicality sparse training algorithms into doubt. Inspired by the hybrid pruning methods, researchers have worked on extracting fine-grained structures in sparse models to accelerate training. Hubara et al. propose a method to find N:M transposable sparsity [17]. Their method accelerates both the forward and backward pass in training and can be used in either static or dynamic fashion. However, the N:M sparsity relies on specialized hardware (sparse tensor cores on GPU) to deliver good performance and thus is not generally applicable to other hardware or even older GPUs. Chen et al. K adopt the shuffled blocking technique from (6) and show that a sparse model with shuffled block structures pre-train a dense model to obtain an initialization for the sparse training. Dietrich et al. K propose a dynamic sparse training algorithm with block sparsity. However, block sparsity without row/column shuffling has a very low mask diversity and achieves low model accuracy.
be trained to dense accuracy nontrivial sparsity ratio. However, they need to
show in $ and experiments,
Preliminaries
Notation. Throughout the paper, we use W IR to denote the parameters in a layer. Here, is the output channel size; C' is the input channel size (if it is linear layer), or the input channel size times the convolution kernel size (if it is a convolutional layer). We use E RCXB to denote the input and Out R. Rx B to denote the output, where B is the batch size. The gradient w.r.t W is dW and has the same dimension as W. The element at row i and column j of dW denoted as . The gradient w.r.t the output is dOut, and the gradient w.r.t. the input is dln. We use || || to denote the L norm of a matrix and use | to denote the absolute value of each element in a matrix or vector.
Algorithm 1: Dynamic sparse training
Before
Input :Network: fw. Dataset: D, Sparsity distribution:
S = (81y---:8)) Update schedule; AT, Tend
W + Randomly sparsify model parameters using S; for each training step t do
Sample batch B, ~ D:
L. ΣiEB, L(fw(z:),
drop
ift mod AT == and t Tena then
After
for each layer do
Decide drop number:
Ldrop < Select & weights to drop:
I Igrow + Select l new weights to grow;
W +- Update active weights using larop and
Igrows
Model adaptation
else W = W LwiL
Figure 3: Dynamic sparse training with drop-and-grove grow-based model adaptation.
Dynamic sparse training, Fig. illustrates the idea of dynamic sparse training. The algorithm starts with a randomly initialized sparse model. It adapts the model in every AT iterations until iteration Tend. The model adaptation involves two operations: drop and grow. The drop operation discards some weights the model, and the grow operation adds some new weights back. Different sparse training algorithms use different criteria for the two operations. For example, Rigl. [8] drops the weights with the smallest magnitudes and grows the same amount of weights with the largest gradients. Top-kast [8] maintains superset of active weights and drops and grows active weights according to their magnitudes. With the periodic model adaptation, dynamic sparse training algorithms can
explore more parameters and achieve higher accuracy than static sparse training
27 26
Computations in sparse neural networks. Many operations in dense neural network can be expressed as general matrix multiplications (GEMM). In a sparse model, the computations are sparse matrix multiplications. For example, the training of a linear layer involves three matrix multiplications: 1) in the forward pass, the input is multiplied with the sparse weight matrix to get the output (i.e., Out W Tn); 2) in the backward pass, the gradient of loss w.r.t. the input is computed by multiplying the transpose of the sparse weight matrix with the gradient w.r.t. the

---

Algorithm 2: Forward pass: Out = W. In for a shuffled block of parameters
Algorithm 3: Backward pass: dW = dOut In for a shuffled block of parameters
Input :W[S]][Sa], rowida[S1).
input :rowida [S.]. colide[So]. dou dOu(B
colida[S2]. [n[C][B]
In[C B1
Output:Outf R]
output: [d
[w In(colida]]
In' [S2]]]]]]] [Sa] I [B;
Out [S [[]]
dOul' [B] dOul (rowidde [B]:
for 0 S1 do
[S][S:][S>) = 0:
for j = 0 S2 do
for = 0 to S do
for to B do
for = 0 to S2 do
Out [kk] +=
for 0 to B do
w Iv LiB::
dw MML += dOul' [[][]] Iv [[]A]
dW [rowidax] [colidæ] dw";
Out (owwidid [B] Out';
output (i.e., dln W dOut);; 3) the gradient of loss w.r.t. the weight is computed by multiplying the gradient w.r.t the output with the transpose of input (i.e., dW dOut In='.. The first two operations are sparse-matrix matrix dense-matrix multiplication (SpMM). The last operation is a sampled dense-dens, matrix multiplication (SDDMM) because only the gradients for the active weights need to be computed.
Sparse matrix multiplication with shuffled blocks. SpMM and SDDMM were first studied for effi- cient execution on GPU the scientific computing domain 15 19 bottleneck of the two operations is the irregular access the input dense matrix, and they propose adaptive tiling and reordering techniques to improve the memory access efficiency. While they target large matrices with high sparsity, the reordering and tiling ideas have inspired shuffled blocking tech- niques to accelerate SpMM and SDDMM for smaller matrices with relatively lower sparsity sparse The idea is illustrated in Fig. 4 The nonzeros in the sparse matrix organized into small blocks. Algorithm shows the implementation of the forward pass for a shuffled block of parameters. Suppose the row indices of the block are rowidz and column indices are colidæ. The program first loads Tn (colids]
They show that the performance
neural networks 36
16 3
[ into cache In' and allocates a cache Out! for Out (roloiddd))) [ [B].
Since the values of Tn|colidar] [B] and
Out[rowidz]] [B] are repeatedly accessed in the computation and accessing cache much faster than main memory, the mem- ory access overhead is reduced. Simi- larly, Algorithm 3 shows the computation of the gradients for block of parameters. The program first loads In In[colidz]] [B] and dOut frowidxx]] into cache and reuses the data in cache throughout the computation. The larger the block size, the more data reuse the program has. The computation can be further accelerated by exploiting the matrix-multiply units in emerging hardware (e.g., tensor cores on Nvidia GPU) [6). This is why structured sparse models can deliver better performance than nonstructured models that have even fewer parameters.
0
3
2
3
shuffle 2
blocking
1
1 2
3
Figure 4: Shuffled blocking sparse matrix.
4 Proposed Algorithm
As explained in the previous section, for sparse models to run efficiently, it is important to have all
the active weights in blocks. Previous work ensures this through pruning [36] [6] or initialization B We now show that sparse models with such fine-graines block structures can also be obtained by dynamic sparse training. Fig. fillustrates the model adaptation steps in our algorithm. This section
details each of the steps.
Initialization. The algorithm starts with a randomly initialized nonstructured model. We adopt the ERK sparsity distribution BC to determine the sparsity for each layer. Then, a shuffled blocking procedure is invoked to reshape the sparse model into shuffled blocks.
5

---

Shuffled blocking, Suppose N is the number of active weights in layer and the block size is set to S₁ x S2. The shuffled blocking procedure aims to put as many active weights into [N/(S, blocks. As shown in Fig. it first reorders the rows of the sparse matrix so that similar rows are close to each other. The similarity between two rows is defined as the Jaccard similarity of the nonzero columns in the two rows (i.e., the number of common columns divided by the total number of distinct columns). Intuitively, two rows with more common columns have a larger similarity and should be put close to each other. With the definition of similarity between rows, the shufiling of rows can be achieved by a simple clustering procedure. We use the Agglomerative wwwerraaiiellsteinngggg from sklearn [3 for this task. Since row reordering is performed repeatedly during the training process, we want to keep its overhead as small as possible. We observe that most rows have small similarities with other rows, and reordering them does not improve much of the block density. Therefore, only cluster the rows that have more than g nonzeros in common columns with other rows, where (0.2 in our experiments) is hyperparameter that controls the clustering overhead. After the rows are reordered, we divide them into groups of size Sj. In Fig. D St is set to 2, and thus the four rows divided into two groups: (0,2) and (1,3). Within each row group, we select S2 columns to form a block of size S x S2. To ensure large weights are preserved, we always select the column with the largest & norm in each row group and return the block with the largest & norm among all row groups. This procedure continues until we find enough blocks.
Block-aware drop criterion. The sparse model is adapted in every AT iterations. For each layer, we compute the number of weights to be dropped in iteration t with cosine decaying function:
Large weights
Small weights that are not dropped
a.V (1 cos
A
(1)
2
Tend/
Small weights that are dropped
where a is the initial drop ratio and N is the number of active weights in the layer. Following previous dynamic sparse
Figure 5: Avoid dropping isolated small weights.
training algorithms g 26 27 I we select the k weights for removal. Before removing them, we check if these weights make up at least half of the elements in either a row weights to be dropped as n ArgTop
with the smallest magnitudes (i.e.
column of block. More specifically, in each shuffled block B, we have the
For a weight w E B Arg (orgTTpp((( (-IW), the elements in the same row of B is B (//roidds(w)) :]. and the elements in the same column of B is Bl: colidæ (.)]. We remove w if and only if B (1)o n ArgTopk(< k)) has at least 2 elements or Bl: colidæ(w)) n ArgTopK(-IW)) k) has at least S2/2 elements. If weight in Arg'l' (onl''pp((IM)) (, k) does not have enough other weights to be dropped in the same row/column of block, the weight will not be dropped. This is because even if we drop it, the weight is very likely to be added back after the blocking procedure. However, because the number of weights to be added in the grow phase is determined by the number of dropped weights, this ineffective dropping of some small weights will result in more new weights being added in the grow phase and may cause more important weights to be discarded by the following shuffled blocking procedure. Our block-aware drop criterion reduces the negative impact of such ineffective drops. Intuitively, when the small weights are concentrated in a few rows or columns, we perform more model adaptation. When the small weights are scattered in many rows and columns, we perform less aggressive adaptation. Fig. S shows an example of the block drop criterion. Suppose there are five small weights (marked with diagonal stripes) in block. Instead of dropping all the five weights, we only drop three of them that are in a row or column with at least two small weights (marked in blue). The two weights with only themselves to be dropped in their rows and columns (marked in orange) will remain active. In our experiments, we find that this block- drop criterion is critical for achieving good accuracy for shuffled-blodd dynamic sparse training (See Appendix A.2
(- (WW,k),, k).
Block-wise grow criterion. The main novelty of our method lies in how we grow the weights. Different from previous work that computes the gradients for all weights and adds the weights with the largest gradients 26 27), we use dOut and In to estimate the importance of weights. Specifically, since dW = dOut. In" dW,, = (dOut,, Ing), we have ||dW;) 11 S ||dOut;ll I1, where dOut, represents row of dOut and In, represents row j of the input. This suggests that the weights connecting the input channels of larger magnitudes to the output channels of larger gradients are of greater importance. Our grow criterion is designed based on this intuition. Suppose X represents group of S2 rows in dOut and Y represents group of S. rows in In. It is easy to that XYT is a shuffled block of size Sn x Sy in dW. Our goal is to find the blocks of weights with

---

Table 1: Mask diversity for different sparsity constraints.
Matrix Size (22 x C)
8 x
16
Sparsity
2:4
2:4
4:8
Nonstructured
18
5.8+75
N.M
4,3049 6.6044
288012
5.8c+14
3.4c+38
6,30+49
Ilo439
NM Transpocahle
4.3es8
188+13
1.8ce19
3.4e+14
9.5ex52
Nonshullled Block (S) S. 1/44)
12870
Nonshuffled Block (S; = 52 R/2)
Shullled Block (Si Sq 11/41
1.2e+18
3.7e+18
Shuffled Block (S,
K/2)
3.1c+11
1.3+429
-|YT|| as an estimate of gradient magnitude. We first sort rows of dOut and In according to their norms in descending order and divide sorted dOut. into groups of Sz rows and sorted In into groups of Sy- Then, we compute ||I|| |||"]][[] for the shuffled blocks and select the blocks with largest || ||| ||YT]|. For a dOut of size x n and input In of size y n, the FLOPS for computing the norms of rows of dOut and In is an + yn, and the FLOPS for computing the sparse gradients is no more than kn where & is the number of dropped weights in Formula ( So the total FLOPS with our proposed grow criterion is on + yn + kn. In comparison, the FLOPS for computing dense gradient is zyn. Since k is small, block-wise grow criterion has a much smaller time complexity than dense gradient computation.
the largest |XY]||. Without computing the actual gradients, we use |||||
Fig. 6 shows an example of the selection procedure with S. = 2 and 5y 1. Suppose the sorted rows of input are 2, 1, 0, 3, and the sorted rows of dOut are 0, 2, 3, 1. The selection starts from the block in the top left corner (bn) as it has the largest || || With by selected, the two blocks (b, and bu) adjacent to by are added to the frontier, and the larger one between the two will be selected in the next step. The selected block may overlap with the existing active blocks. Only the non-overlapping parameters are considered new parameters. We keep selecting new blocks and updating the frontier until new parameters exceed the drop number. In the example of Fig. D a block of new parameters ([0.2] and [2.2]) are added. Finally. we reorganize the new model into shuffled blocks. To prevent the new parameters from being discarded by the blocking procedure, we set their value to the maximum value of the active weights. After the new blocks are formed, we reset the value of the new parameters to zero so that they will not affect the output of the network.
2
0
3
Ino"
dOut
0
b
by
By
2
ba
by
current
frontier
Figure 6: Select new parame- ters in blocks.
Comparison with Transposable N:M Sparsity
Our work is closely related to the line of research that explores fine- fine-grained N:M sparsity in neural While most work focuses on accelerating inference, a recent paper shows that transposable N:M sparsity can be found in sparse models to accelerate both the forward and backward This section compares transposable N:M sparsity with shuffled block sparsity.
networks [
17 RS
pass in training
17
In 177. the authors propose measure called mask diversity to quantify how much specific structure constrains the model. Specifically, mask diversity is the total number of distinct sparse masks that satisfy certain sparsity and dimension constraints. They show positive correlation between the mask diversity and accuracy. We follow their arguments and compute the mask diversity of shuffled block sparsity. For matrix of size R x C, suppose R and C' are divisible by the block size S₁ and S2, and the sparsity is s. Since the rows are reordered and divided into disjoint groups, the number of ways to choose row groups is /!/ (S/
Once the row groups are fixed, we need to select total of RC(1 a)/S2 columns from all row groups to form the desired number of blocks. This leads to the following formula for the mask diversity of shuffled block sparsity:
R!
(RC(1-S)/
RC
block = MDsh boock
(2)
(S1))
s)/
In comparison, the mask diversity of nonshuffled block sparsity is simply choosing RC(1-&)/(G) (),(S) blocks from the total RC/(S,S2) blocks. Table [ lists the mask diversity of shuffled block sparsity
7

---

925
24.5
24
90.5
91.
94
Sperally
Spassity
Spanity
(a) WideResNe122-2
(b) ResNet18
(c) VGG16
Figure 7: Test accuracy (%) over sparsity on CIFARIO.
068
Rgg.
560-16
525-12
050-3
558-45
Deni
2010
Spaniity
Spars by
Sparsity
(a) WeeeResNet22-2
(b) ResNet18
(c) VGG16
Figure 8: Test accuracy (%) over sparsity on CIFARIOO.
along with other sparsity constraints for an 8 x 8 matrix and 16 x 16 matrix. The formula for other sparsity constraints can be found in [17]. We can see that nonstructured sparsity has the highest diversity, which explains its superior accuracy to structured sparsity. When the block size is small, shuffled block sparsity has a mask diversity close to nonstructured sparsity. For example, for the
8 x 8 matrix, when S S2 = R/4- 2, the mask diversity is of the same order of magnitude as nonstructured sparsity. When the block size increases, the mask diversity decreases. This illustrates a tradeoff between hardware efficiency and model accuracy for shuffled block sparsity. Compared to N:M sparsity which only benefits the forward pass, shuffled block sparsity benefits both the forward and backward pass and yet has higher mask diversity when S S2 < 4 and M 2. Compared to N:M transposable sparsity, shuffled block sparsity has a higher mask diversity when S = S2 S 4 and M 4.
Moreover, N:M sparsity relies on sparse- cuttrii-uulpplly units in emerging hardware (sparse tensor cores on Nvidia Ampere GPU) to deliver good performance, whereas shuffled blocking accelerates the computation on traditional computing units and can exploit dense-matrix -uuttilly units which are more broadly supported by hardware (e.g. dense tensor cores GPU, AMX on Intel CPU, MMA on IBM Power10 processor). As the current Nvidia GPU only supports sparse tensor cores with N = 2, MM 4 and dense tensor cores with S S2 4, shuffled blocking is expected to be more flexible and more efficient way to accelcrate sparse training. We can also see that shuffled block sparsity has much higher mask diversity than nonshuffled block sparsity. This is because the shuffling of rows and columns significantly increases the number of ways to form nonzero blocks.
6 Experiments
We test our algorithm with ResNet18 and ResNer50 12
the ImageNet dataset 4 and
WedeResNet22-2, Re and VGG16 37 on CIFARIO 20 and CIFARI00 dataset 21 For
Table 2: Top-1 accuracy on ImageNet. DSB represents our Dynamic Shuffled Block training, and SSB represents Static Shuffled Block training with random initialization. The number before DSB and SSB indicates sparsity, and the number after DSB and SSB is the block size. SSLT represents Structured Sparse Lottery Ticket from missing data in literature.
The number before SSLT indicates sparsity. '_' indicates
Model
Dense
0.5 DSB. 16
0.5 SSB. 16
0.51 SSLT 0.7 SSLT
0.75 DSB-16
0.75 SSB 16
0.8 Rigl.
ResNer50
76
76.33
75.83
75.65
71.5
74.04
72.76
75.1
ResNet18
69.76
69.84
65.72
8

---

60
Rg.
-0-1
-0-4g1
156-4
90
0984
wn 258-16
5085
508-28
025-
000-23
Spondty
Spondty
Spordty
(a) WereRes
(b) ResNet18
(c) VGG16
Figure 9: Test accuracy (%) over sparsity on CIFAR-10 with DSB using different block sizes. Rigl.
corresponds to DSB using block size 1.
B
Dons 01206-4
11035-4
3 188-8
Denss 5504
Spartiy
Spanihy
Spardiyy
(a) WideResNNt22-2
(b) R8
(c) VGG16
Figure 10: Average speedup of sparse convolution over dense convolution operations on CIFAR1O.
ImageNet, the models trained for 100 epochs with batch size 256. The learning rate schedule starts with a linear warm up reaching its maximum value of 0.1 at epoch which is then dropped by factor of 10 epochs 30, 70, 90. For CIFARIO/ with batch size 128. The learning rate is initialized to 0. and is decreased by a factor of 5 every 30,000 iterations. The standard SGD with momentum of 0.9 used the optimizer. For dynamic sparse training, the initial drop ratio a is set to 0.3, AT is set to 1600 for ImageNet and 100 for CIFAR10/100, and Tend is
the models are trained for 250 epochs
400000 for ImageNet and 75000 for CIFARI0/100.
Accuracy compared with other training methods. Table 2 lists the top-1 accuracy of ResNet18 and ResNet50 trained with different methods ImageNet. Our dynamic shuffled block training (DSB) recovers the accuracy of the dense models at 0.5 sparsity. In comparison, the structured sparse lottery ticket (SSLT) [3] has slight accuracy drop for ResNet50 0.51 sparsity while requiring a dense pre-training for initializing the sparse mask. The accuracy of DSB at sparsity 0.75 is also higher than that of SSLT at sparsity 0.7. Fig. 7 shows the test accuracy of Net2222 ResNet18 and VGG16 trained with different methods on CIFARIO. 10. All the experiments are run five times. The accuracies plotted in the figures are the average values. The difference in accuracy between different runs is smaller than 0.05%. We can see that our DSB recovers dense accuracy at 0.5 and 0,6 sparsity for all three models. In contrast, SSLT has a noticeable accuracy drop for WideResNer22 and ResNet18 8 (although they can achieve dense accuracy at lower sparsities nonstructured dynamic sparse training (RigL H)), our DSB has slightly lower accuracy 0.5 and 0.6 sparsity, and the accuracy gap widens the sparsity gets higher. Fig. E CIFAR 100. Again, our DSB recovers dense accuracy at 0.5 and 0.6 sparsity. For WideResNet22-2 and ResNet18, our DSB achieves slightly higher accuracy than SSLT at small sparsity (S 0.7) and almost the same accuracy at higher sparsity (> 0.7). For VGG16. SSLT achieves surprisingly higher accuracy than both dense training and our DSB, but they require dense pre-training for initialization. For all the test cases, nonshuffled block sparsity (DNSB) achieves apparently lower accuracies than other methods, which is consistent with the mask diversity shown in Table
3. Compared with
shows the test accuracy on
Importance model adaptation. The results in Table 2 and Fig. and also show that the model adaptation is critical to the accuracy of sparse training. For ResNet50 and ResNet18 on ImageNet, without model adaptation, static shuffled block training (SSB) cannot recover dense accuracy at 0.5 sparsity. Its accuracy at 0.75 sparsity is more than ResNet18, and VGG16 on CIFAR 10/100, SSB also has lower accuracy than DSB, and the accuracy gap is larger at higher sparsity.
% lower than DSB. For WideRessNe12222

---

Tradeoff between accuracy and efficiency with different block sizes. To show the effects of block size on accuracy, we rum DSB with different block sizes. The results are shown in Fig. y DSB-4,8.16 16 achieve almost the same accuracy when sparsity < 0.8. DSB-4 shows a slight advantage over DSB-8, 16 at 0.9 sparsity. When the block size increases to 32, we observe an apparent accuracy drop, and the drop is more significant at higher sparsity. To show the effects of block size on performance, we test the implementation of shuffled block convolution from [6 on an Nvidia RTX3090 GPU. Fig. [T0 shows the average speedups of shuffled block convolution with different block sizes over dense convolution. We can see that when the block size is small, the sparse convolution has almost no performance advantage over dense convolution, even at high sparsity. As the block size increases, the shuffled block convolution achieves better performance. Notably, when the block size increases from 8 to 16, the sparse computation achieves the largest marginal speedups. When the block size increases from 16 to 32, the performance improvement is small. This is because the convolution operation with 16 x 16 blocks already saturates the cache the GPU platform. The results suggest that block size 16 achieves a good tradeoff between the accuracy and efficiency of DSB.
<05B4 60394 HO53-45 BC53-32
/1/
DI0M4 IS 108 0000 DUSSHS
0.15
0.2
0.3
0.15
0.3
012
0.09
Spandiy
Spartiyy
(a) WideResNet22-2
(b) ResNet18
(c) VGG16
Figure 11: The ratio of shuffled blocking time to dense training time for different models on CIFARIO.
Overhead of shuffled blocking. Although shuffled blocking is an expensive operation, it performed only once in every AT iterations. Fig. 11 shows the overhead of shuffled blocking. The execution time of shuffled blocking accounts for 1% to 45% of total training time. We can see that, as the sparsity increases, the overhead of shuffled blocking decreases. As the block size increases, the number of blocks decreases, and the overhead also decreases. When block size is set to 16, the shuffled blocking procedure takes about 10% of the total training time. According to the speedups in Fig. 10 the overhead can be justified by the performance improvements brought by sparse computation.
7 Conclusion
We propose dynamic sparse training algorithm that extracts and exploits fine-grained block structures in sparse models. Our algorithm is designed based on the drop-and-gron model adaptation framework and features block-aware drop criterion and a block-wise grow criterion. We show that a randomly initialized sparse model with shuffled block structures can be trained to high accuracy, and the training process can be effectively accelerated.
References
[1] Brian Bartoldson, Ari Morcos, Adrian Barbu, and Gordon Erlebacher. The generalization- stability tradeoff in neural network pruning. Advances in Neural Information Processing Systems, 33:20852- 2020.
[2] Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. arXiv preprint arXiv:1711.05 2017.
[3] Tianlong Chen, Xuxi Chen, Xiaolong Ma, Yanzhi Wang, and Zhangyang Wang. Coarsening the granularity: Towards structurally sparse lottery tickets. arXiv preprint arXiv:2202.04736, 2022.
[4] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Iece, 2009.
10

---

[5] Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.04840 2019.
[6] Anastasia Dietrich, Frithjof Gressmann, Douglas Oir, Ivan Chelombiev, Daniel Justus, and Carlo Luschi. Towards structured dynamic sparse pre-training of bert. arXiv preprint arXiv:2108.000 06277, 2021.
[7] Xiaohan Ding, Tianxiang Hao, Jianchao Tan, Ji Liu, Jungong Han, Yuchen Guo, and Guiguang Ding, Resrep: Lossless enn pruning via decoupling remembering and forgetting, In Proceedings of the IEFF/CVF International Conference on Computer Vision, pages 45100-520, 2021.
[8] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. International Conference on Machine Learning, pages 2943-2952 PMLR, 2020.
[9] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse. trainable neural networks. In International Conference on Learning Representations, 2019.
[10] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 1tt::/5/0.000 15.000449 2015.
[11] Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural networks. Proceedings of the 28th International Conference on Neural Information Processing Systems- - Volume 1, NIPS 15, pages 1 1135-1143, Cambridge, MA, USA, 2015. MIT Press.
[12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[13] Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE international conference on computer vision, pages 1389-1397, 2017.
[14] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruming and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241):1-124 2021.
[15] Changwan Hong, Aravind Sukumaran- Rajam, Israt Nisa, Kunal Singh, and Sadayappan. Adaptive sparse tiling for sparse matrix multiplication. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, pages 300-314, 2019.
[16] Guyue Huang, Haoran Li, Minghai Qin, Fei Sun, Yufei Ding, and Yuan Xie. Shfl-bw: Accel- erating deep neural network inference with tensor-core aware weight pruning. arXiv preprint arXiv:2203.00 05016,, 2022.
[17] Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find m transposable masks. Advances in Neural Information Processing Systems, 34, 2021.
[18] Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33:20744- 20754, 2020.
[19] Peng Jiang, Changwan Hong, and Gagan Agrawal. A novel data transformation and execution strategy for accelerating sparse matrix multiplication on gpus. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 376-388, 2020.
[20] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced research).

---

[21] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-100 (canadian institute for advanced research).
[22] Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Torr. A signal propaga- tion perspective for pruning neural networks at initialization. arXiv preprint arXiv: (xXiv:1906.06077 2019.
[23] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXhv:1810.023340, 2018.
[24] Mingbao Lin, Rongrong Ji. Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao. Hrank: Filter pruning using high-rank feature map. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1529-1538, 2020.
[25] Minghao Lin, Rongrong Ji, Yuxin Zhang, Baochang Zhang, Yongjian Wu, and Yonghong Tian. Channel pruning via automatic structure search. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 673-679, International Joint Conferences on Artificial Intelligence Organization, 7 2020.
[26] 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. Advances in Neural Information Processing Systems, 34, 2021.
[27] Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do we actually need dense over- prrepaaramtteization?? in-time over-parameterizztoon in sparse training. International Conference on Machine Learning, pages 6989-7000. PMLR. 2021.
[28] Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang Learning efficient convolutional networks through network slimming. Proceedings of the IEEE international conference on computer vision, pages 2736-2744, 2017.
[29] Xiaolong Ma. Fu-Ming Guo, Wei Niu, Xue Lin, Jian Tang, Kaisheng Ma, Bin Ren, and Yanzhi Wang. Pconv: The missing but desirable sparsity in dnn weight pruning for real-time execution mobile devices. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34,
pages 5117-5124, 2020.
[30] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibeseu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1): 2018.
[31] Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning, pages 4646-465 PMLR, 2019.
[32] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8024 2019.
[33] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[34] Alexandra Peste, Eugenia lofinova, Adrian Vladu, and Dan Alistarh. Ac/de: Alternating compressed/decompesssdd training of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.
12

---

[35] Ao Ren, Tianyum Zhang, Shaokai Ye, Jiayu Li, Wenyao Xu, Xuehai Qian, Xue Lin, and Yanzhi Wang. Admm-nn: An aegorithm-hardwaaee co-design framework of dnns using alternating direction methods of multipliers. In Proceedings of the Twenty-Fourth Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 925-938, 2019.
[36] Masuma Akter Rumi, Xiaolong Ma. Yanzhi Wang, and Peng Jiang. Accelerating sparse emn inference on gpus with performance-awaan weight pruning. In Proceedings of the ACM International Conference Parallel Architectures and Compilation Techniques, pages 267-278. 2020.
[37] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
[38] Wei Sun, Aojun Zhou, Sander Stuijk, Rob Wijnhoven, Andrew Nelson, Henk Corporaal, et al. Dominosearch: Find layer-wise fine the-grained n: M sparse schemes from dense neural networks. Advances Neurul Information Processing Systems, 34, 2021.
[39] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016.
[40] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pages 2082-200220000 2090, USA, 2016. Curran Associates Inc.
[41] Kyle Wiggers. Openai's massive gpt-3 model is impressive, but size isn't I everything. url- caarbonnfoorrrinteestteeeee
https:/www.lleerggserro////2///0
2020.
[42] Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. A systematic dnn weight pruning framework using alternating direction method of multipliers. ECCV, 2018.
[43] Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hongsheng Li. Learning fine-gra graiind structured sparse neural networks from scratch. arXiv preprint 1ttp:2102.04010. 2021.
[44] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
[45] Maohua Zhu, Tao Zhang, Zhenyu Gu, and Yuan Xie. Sparse tensor core: Algorithm and hardware co-design for vector-wise wise sparse neural networks on modern gpus. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecctrre, pages 359-371,
2019.
13


Reviews:
[{"review_id": "qESfLdbCVDS", "reviewer": "Reviewer_eD4a", "summary": "This paper studies dynamic sparse training (DST) with fine-grained structured pruning. \nStarting with a randomly initialized nonstructured model, the shuffled blocking procedure groups active weights into several blocks. During the training interval, it drops some weights with the smallest magnitudes, and grows some weights with the proposed block-wise grow criterion. With experiments on CIFAR and ImageNet, this paper demonstrates that the proposed framework is better than structured sparse lottery ticket (SSLT) [3] and RigL [6]. \n", "questions": "This paper is an overall OK submission. Nevertheless, the lack of acceleration comparison refrains me to give a better score. I would be happy to improve my rating as long as the authors address the above weaknesses in the rebuttal.   \n", "limitations": "No, this paper does not discuss the limitation and potential negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- This paper firstly studies the DST with fine-grained structured models. Compared with previous works, the proposed method no longer requires specialized hardware (sparse tensor cores on GPU) [16] or pre-trained dense models [3]. \n- The proposed growing algorithm is novel and practical as it avoids the calculation of dense gradients and dense weights, which makes the training purely sparse. \n- This paper clearly discusses the difference between the proposed method and the Transposable N: M Sparsity [16]. \n- The paper is in general well written and easy to follow.\n\nWeaknesses\n\n- More details about the hardware acceleration should be provided. \nSince this paper focuses on sparse training with fine-grained structured pruning, the total training time saving and memory saving should be reported. Meanwhile, this paper should compare the speedup with some structured pruning methods in Figure 9. \n\n- In Table 2, Figure 6, and Figure 7, the error bar should be presented. \n \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gQt8wWAMBmc", "reviewer": "Reviewer_RD2v", "summary": "The paper proposes a sparse training method based on fine-grained block sparsity. The main insight is that shuffled block sparsity (where entries in the weight matrices are permuted to form blocks) can be hardware efficient and yield speed up. The method proposed consists of block-pruning and block- growing at regular intervals (i.e., dynamic block sparsity). Both block-pruning and block-growing can be done efficiently without computing gradient for the whole dense matrix. Experiments on ResNets & VGG on CIFAR and ImageNet show that at 0.50 sparsity, the proposed method can match the accuracy of the dense models.", "questions": "1. What is the overhead of block dropping? The paper claims it improves accuracy but there's no experiments to show this.\n", "limitations": "Limitations are discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The block-wise grow criterion is clever and well-motivated. It avoids having to compute the gradient for the entire dense matrix. Instead, it estimates the gradient magnitude by multiply the magnitude of the output gradient and the input. Maybe micro-experiment to show how close this heuristic is compared to the expensive gradient of the dense matrix would make it even more convincing.\n2. The accuracy vs block sizes ablation is informative. It reveals that block size of 16x16 can yield speedup while maintaining accuracy of the dense model.\n\nWeaknesses:\n1. Lack of validation on wallclock-time speedup. Does the benchmark use channel first or channel last? fp32 or fp16? These details significantly change the speed of the dense model.\nWhat is the overall model speedup, either in inference or training?\nThe code seems to just use mask to multiply with a dense weight matrix so I'm not sure how one could get wall-clock time speedup. \n2. Lack of comparison with existing block-sparse methods (e.g., Block Pruning For Faster Transformers. Lagunas et al. EMNLP 2021). Does the shuffled block sparsity perform better / faster than just block sparsity?\n3. The concept of shuffled block should to be explained more clearly. Is the entire 16x16 block either zero or nonzero? Or are there both zeros and nonzeros in the same block?\nHow important is the shuffle step? How does one decide which rows / columns to shuffle?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4jM20bJU945", "reviewer": "Reviewer_vhN2", "summary": "This paper proposes a hardware-friendly sparse training method with shuffled block structures, which can be accelerated by the common hardware (GPU). The acceleration can be achieved by quickly obtaining the index of the grouped weights during the forward and backward pass. The research topic is very important for the sparse training community. In spite of the promising results of dynamic sparse training (DST), a major problem of DST is that the promising efficiency can not be fully transferred to the common hardware. Therefore, any good contribution to the topic is important. However, several major concerns need to be clarified as written below.", "questions": "Please refer to the above weakness. ", "limitations": "No", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n(1) This paper proposes a structured sparse training method by grouping the unstructured elements together during training. It is surprising to see that the grouped DST can still match the performance of the dense model while achieving up to 5x acceleration. \n\n(2) The criterion used in the paper does not require to calculate the dense gradients. \n\n(3) Related work is relatively extensive.\n\n##  Weakness\n\n(1) The authors claim that they are the first to apply group sparsity to dynamic sparse training. However, I think they have missed one prior work (https://arxiv.org/pdf/2108.06277.pdf) which has explored this direction, even though the method is distinct. I suggest adjusting their claim. \n\n(2) The description of the methodology is relatively dry and hard to follow. More effort should be put to improve it.\n\n(3) My major concern is that the authors did not mention which part of the results are produced with masks and which part of the results are produced with the proposed method? It has been claimed in the abstract that the algorithm can match the accuracy while reducing training time by 5x, but no actual wall-clock training time has been reported in the paper. More specifically, (1) does the proposed method support end-to-end dynamic sparse training? As far as I understand, the dense matrix implementation in Pytorch or Tensorflow is so well-optimized, that even we can achieve acceleration by quickly selecting the index of grouped weights, it is difficult to be quicker than the mask-version DST in terms of the real wall-clock time. (2) Was the averaged speed up reported in figure 9 be evaluated with one feed-forward pass or evaluated with the end-to-end training? This question is important to verify the real contribution of the proposed method.\n\n(4) I am curious about the real speedup of the proposed grow criterion? It would be nice to provide how many flops can be saved by using this instead of calculating the dense gradient? In reality, how fast it is compared with dense gradient on GPU?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3PJLisuKux", "reviewer": "Reviewer_pyCy", "summary": "This paper explores sparse training for fine-grained block sparse models. Detailedly, the authors leverage the classic prune-and-regrow workflow in a block-aware manner with a new grow criterion that does not rely on dense gradient calculation of weights. Experiments on ImageNet and CIFAR-10/100 show that the proposed block-wise sparse training can achieve satisfying performance and noticeable speedup at moderate sparse rates. ", "questions": "1. The authors claim that DSB accelerates the computation on traditional computing units that are broadly supported by hardware. However, I notice that their provided codebase is a stimulated version, i.e., weights are multiplied with binary masks to represent pruned model. It would be nice for the authors to provide a running demo or code that can be deployed on general hardware, which could also make this paper more convincing and easy-to-implement.", "limitations": "The authors do not discuss the limitations of their work as well as the negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The reviewer appreciates the motivation and contribution of this work. The exploration of hardware-friendly sparse training is remarkable and could benefit the community a lot.\n2. The proposed block-wise growing criterion is well-designed and can effectively reduce the overhead of sparse training, despite that the ablation studies are missing. I recommend the authors compare traditional dense gradient criterion with the proposed block-wise grow criterion to further demonstrate their view.\n3. This paper is well-written and easy to follow.\n\nWeakness:\n1. The authors claim that the proposed block-wise sparsity can match the performance of unstructured sparsity in most cases. However, DSB seems to lag far behind the current state-of-the-art unstructured methods. For example, STR[1] achieves 76.12% top-1 accuracy at 81% sparsity, while DSB only achieves 74% top-1 accuracy at 75% sparsity.\n2. The core advantage of the proposed DSB falls in acceleration and computation reduction on general hardware. However, the authors only compare DSB with unstructured methods. In contrast, structured sparsity methods[2,3,4] can also eliminate the training and inference costs. Thus, it is necessary to add comparisons with structured methods to show whether the DSB can obtain a better trade-off between speedup and performance maintenance.\n\nMinor: \n1. What is SDB In Tab.2?  I recommend the authors add a relevant caption.\n\n[1] Soft Threshold Weight Reparameterization for Learnable Sparsity. In ICML,2020.\n[2] Hrank: Filter pruning using high-rank feature map. In CVPR, 2020.\n[3] Resrep: Lossless cnn pruning via decoupling remembering and forgetting. In ICCV, 2021\n[4] Channel Pruning via Automatic Structure Search. In IJCAI, 2020.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept