Pruning Deep Neural Networks from a Sparsity Perspective
Authors: Enmao Diao
Ganghua Wang
Jiawei Zhang
Yuhong Yang
Jie Ding
Vahid Tarokh
Venue: ICLR 2023 poster (2023)
Keywords: Adaptive Pruning
Model Collapse
Sparsity
Model Compression
Deep Learning

Abstract: In recent years, deep network pruning has attracted significant attention in order to enable the rapid deployment of AI into small devices with computation and memory constraints. Pruning is often achieved by dropping redundant weights, neurons, or layers of a deep network while attempting to retain a comparable test performance. Many deep pruning algorithms have been proposed with impressive empirical success. However, existing approaches lack a quantifiable measure to estimate the compressibility of a sub-network during each pruning iteration and thus may under-prune or over-prune the model. In this work, we propose PQ Index (PQI) to measure the potential compressibility of deep neural networks and use this to develop a Sparsity-informed Adaptive Pruning (SAP) algorithm. Our extensive experiments corroborate the hypothesis that for a generic pruning procedure, PQI decreases first when a large model is being effectively regularized and then increases when its compressibility reaches a limit that appears to correspond to the beginning of underfitting. Subsequently, PQI decreases again when the model collapse and significant deterioration in the performance of the model start to occur. Additionally, our experiments demonstrate that the proposed adaptive pruning algorithm with proper choice of hyper-parameters is superior to the iterative pruning algorithms such as the lottery ticket-based pruning methods, in terms of both compression efficiency and robustness.

Published as a conference paper at ICLR 2023
PRUNING DEEP NEURAL NETWORKS FROM A SPARSITY PERSPECTIVE
Enmao Diao
Ganghua Wang"
Jiawei Zhang
Department of Electrical and Computer Engineering Duke University Durham, NC 27705, USA enmao. diao@duke. edu
School of Statistics
School of Statistics
University of Minnesota Minneapolis, MN 55455, USA wang 901 9mumn edu
University of Minnesota
Minneapolis, MN 55455, USA zhan43628 2 umn.umn. edu
Yuhong Yang
Jie Ding
Vahid Tarokh
School Statistics University of Minnesota Minneapolis, MN 55455, USA yangx37 6 umn. edu
School of Statistics
Department of Electrical and Computer Engineering Duke University
University of Minnesota Minneapolis, MN 55455, USA ding jingjeumn.. edu
Durham, NC 27705, USA vahid. tarkh@dukkk edu
ABSTRACT
In recent years, deep network pruning has attracted significant attention in order to enable the rapid deployment of AI into small devices with computation and memory constraints. Pruning is often achieved by dropping redundant weights, neurons, or layers of deep network while attempting retain comparable performance. Many deep pruning algorithms have been proposed with impressive empirical success. However, existing approaches lack quantifiable measure estimate the compressibility of a sub-network during each pruning iteration and thus may under- prune or over-prune the model. In this work, we propose PQ Index (PQI) measure the potential compressibility of deep neural networks and use this to develop a infoomed Adaptive Pruning (SAP) algorithm. Our extensive experiments corroborate the hypothesis that for generic pruning procedure, PQI decreases first when large model is being effectively regularized and then increases when its compressibility reaches limit that appears to correspond to the beginning underfitting. Subsequently, PQI decreases again when the model collapse and significant deterioration in the performance of the model start occur. Additionally, our experiments demonstrate that the proposed adaptive pruning algorithm with proper choice of hyper-parameterss is superior the iterative pruning algorithms such as the lottery ticket-based pruning methods, in terms of both compression efficiency and robustness. Our code is available here
INTRODUCTION
Over-parameterized deep neural networks have been applied with enormous success a variety of
fields, including computer vision (Krizhevsky al. 2012, He al. 2016b; Redmon al. 2016).
natural language processing (Devlin et al. 2018) Radford et al.) 2018), audio signal processing (Oord
al. 2016 Schneider al.
2019: Wang al. 2020), and distributed learning (Konečný et al. 2016
Ding et al. 2022 Diao et al. 2022).
These deep neural networks have significantly expanded in size.
For example, LeNet-5 (LeCun
1998)
(1998; image classification) has 60 thousand parameters
whereas GPT-3 (Brown et al. 2020) (2020; language modeling) has 175 billion parameters. This rapid growth in size has necessitated the deployment of vast amount of computation, storage, and energy resources. Due to hardware constraints, these enormous model sizes may be barrier to deployment in some edge devices such mobile phones and virtual assistants. This has greatly increased interest in deep neural network compression/pruning To this end, various researchers have developed empirical methods of building much simpler networks with similar performance based
"Equally contributed

---

Published as a conference paper at ICLR 2023
Performance
Performance
Performance 1
Sparsity
Sparsht
Sparsity
Regularization
Compression
Collapse
Figure I: An illustration of our hypothesis on the relationship between sparsity and compressibility of neural networks. The width of connections denotes the magnitude of model parameters.
on pre-trained networks (Han et al., 2013; Frankle & Carbin 2018). For example, Han et al. (0115) demonstrated that AlexNet (Krizhevsky al. 2017) could be compressed to retain only 3% of the original parameters on the ImageNet dataset without impacting classification accuracy.
important topic of interest is the determination of limits of network pruning. An overly pruned model may not have enough expressivity for the underlying task, which may lead to significant performance deterioration (Ding et al., (018). Existing methods generally monitor the prediction performance on validation dataset and terminate pruning when the performance falls below pre-specified threshold. Nevertheless, quantifiable measure for estimating the compressibility of sub-network during each pruning iteration is desired. Such quantification of compressibility can lead to the discovery of the most parsimonious sub-networks without performance degradation.
In this work, we connect the compressibility and performance of neural network to its sparsity. In highly wver-parameterized network, one popular assumption that the relatively small weights are considered redundant non-influential and may be pruned without impacting the performance. Let us consider the sparsity of a non-negative vector w = [wi...., wa). since sparsity is related only to the magnitudes of entries. Suppose Sww) is sparsity measure, and larger value indicates higher sparsity. Hurley & Rickard (2009) summarize six properties that an ideal sparsity measure should have, originally proposed in economies (Dalton 1920 Rickard Fallon 2004). They are
(DI) Robin Hood. For any > Wj and E (w; w2)/2), we have S([wI,... W. O,...,, W/ + a,..., wal) < S(w).
(D2) Scaling. S(aw) (w) for any a > 0.
(D3) Rising Tide. 5(w ai) < S(w) for any a > 0 and w; not all the same.
(D4) Cloning. S(w) S(w, w[w.
(PI) Bill Gates. For any i = 1,.... d. there exists 3 > 0 such that for any a >> O we have
S([W)..... W/ + 3 + a,..., wal) > S ([wi..... we + S wal).
(P2) Babies. S([I)....... Wa, 0J) S(w) for any non-zero
Hurley & Rickard (2009) point out that only Gini index satisfies all six criteria among a comprehensive list sparsity measures. this work, we propose measure of sparsity named PQ Index (PQI). To the best of our knowledge, PQI is the first measure related to the norm of a vector that satisfies all the six properties above. Therefore. PQI is an ideal indicator of vector sparsity and of its own interest. We suggest using PQI to infer the compressibility of neural networks. Furthermore, we discover the relationship between the performance and sparsity of iteratively pruned models as illustrated in Figure M Our hypothesis is that for generic pruning procedure, the sparsity will first decrease when a large model is being effectively regularized, then increase when its compressibility reaches a limit that corresponds the start of underfitting, and finally decrease when the model collapse occurs, i.e. the model performance significantly deteriorates.
Our intuition is that the pruning will first remove redundant parameters. As result, the sparsity of model parameters will decrease and the performance may be improved due to regularization. When the model is further compressed, part of the model parameters will become smaller when the
2

---

Published as a conference paper at ICLR 2023
model converges. Thus, the sparsity will increase and the performance will moderately decrease. Finally, when the model collapse starts to occur, all attenuated parameters are removed and the remaining parameters become crucial to maintain the performance. Therefore, the sparsity will decrease and performance will significantly deteriorate. Our extensive experiments on pruning algorithms corroborate the hypothesis. Consequently, PQI can infer whether model is inherently compressible. Motivated by this discovery, we also propose the Sparsity-informed Adaptive Pruning (SAP) algorithm, which can compress more efficiently and robustly compared with iterative pruning algorithms such as the lottery ticket-base based pruning methods. Overall, our work presents a new understanding of the inherent structures of deep neural networks for model compression. Our main contributions are summarized below.
1. We propose a new notion of sparsity for vectors named PQ Index (PQI), with a larger value indicating higher sparsity. We prove that PQI meets all six properties proposed by (Dalton 1920; Rickard & Fallon 2004), which capture the principles a sparsity measure should obey. Among 15 commonly used sparsity measures, the only other measure satisfying all properties is Gini Index (Hurley & Rickard 2009). Thus, norm-based based PQI is an ideal sparsity/equity measure and may be of independent interest to many areas, e.g., signal processing and economics.
2. We develop a new perspective on the compressibility of neural networks. In particular, we measure the sparsity of pruned models by PQI and postulate the above hypothesis the relationship between sparsity and compressibility of neural networks.
3. Motivated by our proposed PQI and hypothesis, we further develop a Sparsity-informer Adaptive Pruning (SAP) algorithm that uses PQI to choose the pruning ratio adaptively. In particular, the pruning ratio at each iteration decided based on PQI-related inequality. In contrast, Gini Index does not have such implications for the pruning ratio.
4. We conduct extensive experiments to measure the sparsity of pruned models and corroborate our hypothesis. Our experimental results also demonstrate that SAP with proper choice of hyper-paramette can compress more efficiently and robustly compared with iterative pruning algorithms such as the lottery ticket-based pruning methods.
2 RELATED WORK
Model compression The goal of model compression is to find a smaller model that has comparable performance the original model. smaller model saves storage and computation resources, boosts training, and facilitates the deployment of the model to devices with limited capacities, such as mobile phones and virtual assistants. Therefore, model compression is vital for deploying deep neural networks with millions or even billions of parameters. Various model compression methods have been proposed for neural networks. Among them, pruning is one of the most popular and effective approach (LeCun et al. 1989 Hagiwara 1993, Han et al., 2015 Hu et al. 2016 Luo et al. 2017 Frankle Carbin 2018 Lee et al. 2018: He et al. 2017). The idea of pruning is the sparsity assumption that many redundant non non-inflenntaa neuron connections exist in over- ver-parameterized model. Thus, we can remove those connections (c.g., weights, neurons, or neuron-like structures such as layers) without sacrificing much test accuracy. Two critical components of pruning algorithms a pruning criterion that decides which connection to be pruned and a stop criterion that determines when stop pruning and thus prevent underfitting and model collapse. There are many pruning criteria motivated by different interpretations of redundancy. A widely-used criterion removes the parameters with the smallest magnitudes, assuming that they are less important (Hagiwara) 1993 Han et al., 2015). Besides magnitude- based pruning, one may prune the parameters based on their sensitivity or contribution to the network output (LeCun et al. 1989 Lee al. 2018 Hu et al. 2016 Soltani et al.] (021) or restrict different model components to share large proportion of neural weights (Diao et al. 2019 202T). As for the stop criterion, the common choice validation: to stop pruning once the test accuracy on a validation dataset falls below given threshold.
While pruning is a post-processing method that requires a pre-trained model, there are also pre- processing and in-processing methods based the sparsity assumption. For example, one can add explicit sparse constraints on the network, such as forcing the parameters to have a low-rank structure and sharing weights. Alternatively, as adding a sparsity penalty (c.g., L nnrmm) to the parameters. In contrast to those sparsity- compression methods, which find sub-network of the original one, researchers have also proposed
can implicitly force the trained model to be sparse, such
3

---

Published as a conference paper at ICLR 2023
compressing the model by finding smaller model with different architecture. The efforts include knowledge distillation (Hinton et al. 2013) and architecture search (Mushtag et al. [02T]. We refer the reader to (Hoefler et al.)) 2021) for comprehensive survey of model compression.
Theory of model compression In practice, the compressibility of model depends on the network architecture and learning task. The pruning usually involves lot of ad hoc hyppe-parameter fine- tuning. Thus, an understanding of model compressibility is urgently needed. There have been some recent works show the existence of or find a sub-network with guaranteed performance. [Arora et al.) (2018) show that a model is more compressible if it is more stable to the noisy inputs and provides generalization error bound of the pruned model. Yang et al. (2022) propose a backward pruning algorithm inspired by approximating functions using Ey norm (Wang et al. 2014), and quantify its generalization error. [aakal et al. (2018); Mussay et al. (019)) utilize the concept of coreset to prove the existence of pruned network with similar performance. The main idea is to sample the parameters based on their importance, and thus selected parameters could preserve the output of the original network. Ye et al. (2020) propose greedy selection algorithm to reconstruct a network and bound the generalization error for two-layer neural networks. Our work develops a new perspective on the compressibility of neural networks by directly measuring the sparsity of pruned models to reveal the relationship between the sparsity and compressibility of neural networks.
Sparsity measure Sparsity is crucial concept in many fundamental fields such as statistics and signal processing [Tibshirani 1996. Donoho 2006 Akçakaya & Tarokh| 2008). Intuitively, sparsity means that the most energy concentrated in few elements. For example, widely-used assumption in nigh-dimensional machine learning is that the model has an underlying sparse representation. Various sparsity measures have been proposed in the literature from different angles. One kind of sparsity measure originates from sociology and economics. For example, the well-known Gini Index (Gini 1912) can measure the inequality in a population's 's wealth or welfare distribution. A highly wealth-concentrater population forms a sparse vector if the vector consists of the wealth of each person. In addition, to measure the diversity in a group, entropy-based measures like Shannon entropy and Gaussian entropy are often used (lost 2006). Another kind of sparsity measure has been studied in mathematics and engineering for long time. A classic measure is the hard sparsity, also known as 4o-norm, which is the number of non-zero elements in A small hard sparsity implies that only a few vector elements are active or effective. However, a slight change in the rero-valued element may cause significant increase in the hard sparsity, which can be undesirable. Thus, its relaxations such as E,, nn-norm (0 < p I 1) are also widely used. For example, ε f--nomm-base constraints or penalties are used for function approximation (Barron 1993), model regularization and variable selection (Tibshirani 1996 Chen et al. 200T). Our work proposes the first measure of sparsity related vector norms that satisfies all the properties shared by the Gini Index (Hurley & Rickard 2009) and an adaptive pruning algorithm based on our proposed measure of sparsity.
3
PRUNING WITH PQ INDEX
3.1 PQ INDEX
We will prove all the six properties (DI)-(D4) and (P1), (P2), which are mentioned in the introduction, hold for our proposed PQ Index (PQI). Definition (PQ Index). For any < < g, the PQ Index of non-zero vector w E Rd is
In = 1 di
(1)
[wlly
where I|l|p EE and drop the dependency on p and when the context clear.
1 /PPP is the Ey-norm of w for any p > O. For simplicity, we will use I(w)
Theorem 1. We have 0 S Lp.g(w) S -11-6 d -b, and a larger (w) indicates a sparser vector. Furthermore, (w) satisfies all the six properties (DI)-(D4) and (P1), (P2).
Remark 1 (Sanity check). For the densest or most equal situation, we have w; = cc 1,..,, d. where c is a non-zero constant. It can be verified that Ip.q (w) = 0. In contrast, the sparsest or most unequal case is that w, 's are all zeros except of them, and corresponding lp.g(w) = d Note that I(w) for an all-zero vector is not defined. From the perspective of the number of important elements, an all- all-zero vector is sparse; however, it is dense from the aspect of energy distribution.
4

---

Published as a conference paper at ICLR 2023
Remark 2 (Insights). The form of 1p.q is not a random thought but inherently driven by properties (D1)-(D4). Why do we need the ratio of two norms? It is essentially decided by the requirement of (D2) Scaling. If ((w) involves only single norm, then S(w) is not scale- invariant. However, since ey-norm is homogeneous for all r > 0, the ratio of two norms is inherently scale-invariant. Why is there additional scaling constant - This is necessary to satisfy (D4) Cloning. Inspired by the well-known Root Mean Squared Error (RMSE), we found out that the additional scaling constant is the correct term to help 1p.g be independent of the vector length. It is essentially appealing for comparing the sparsity of neural networks with different model parameters. Why do we require p q? We find it plays a central role in meeting (DI) and (D33. The insight is that |/l|p decreases faster than |llll when a vector becomes sparser, thus guaranteeing a larger PQ Index.
Theorem 2 (PQI-bound on pruning). Let M, denote the set of r indices of w with the largest magnitudes, and Th be the smallest value such that EigM, |w/|p S T/r ΣiEM, [ws]P. Then, we have
2 d(1 + (00))//(1110 P) I(w)
(2)
Remark 3. The PQI-bound is inspired by Yang et al. 2022) that proposed to use /|w||///l aoll:: q E (0, 1) measure of sparsity. We use similar techniques to derive the bound based on our proposed PQ Index. It is worth mentioning that |//|l// || ll does not satisfy properties (D2), (D4), (PI), and (P4), which an ideal sparsity measure should have Hurley & Rickard (2009). Consequently, cannot use it to compare the sparsity of models of different sizes. The merit of the PQI-bound is that it applies iterative pruning of models that involve different numbers of model parameters.
Recall that the pruning is based on the assumption that parameters with small magnitudes are removable. Therefore, suppose we know I(w) and 7/., then we immediately have a lower bound for the retaining ratio of the pruning from Theorem [ Thus, we can adaptively choose the pruning ratio based on I(w) and 77, which inspires our Sparsity-informer Adaptive Pruning (SAP) algorithm in the following subsection. In practice, ah is unavailable before we decide the pruning ratio. Therefore, in our experiments. Since 1)-- non- non-increasing with respect to r, a larger 7), means that we assume the model is more compressible and leads to a higher pruning ratio. Experiments show that it is safe to choose 7)- O.
we treat as
3.2 SPARSITY-INFORMED ADAPTIVE PRUNING
In this section, we introduce the Sparsity-informed Adaptive Pruning (SAP) algorithm as illustrated in Algorithm M Our algorithm is based on the well-known lottery ticket pruning method (Frankle & Carbin 2018). The lottery ticket pruning algorithm proposes to prune and retrain the model iteratively. Compared with one shot pruning algorithm, which does not retrain the model at each pruning iteration, the lottery ticket pruning algorithm produces pruned models of better performance with the same percent of remaining model parameters. However, both methods use fixed pruning ratio P at each pruning iteration. As a result, they may under-prune or over-prumt the model at earlier or later pruning iterations, respectively. The under-pruned models with spare compressibility require more pruning iterations and computation resources to obtain the smallest neural networks with satisfactory performance. The over- verr-ruuned model suffers from underfitting due to insufficient compressibility to maintain the desired performance. Therefore, we propose SAP to adaptively determine the number of pruned parameters at each iteration based on the PQI-bound derived in Formula
2 Furthermore, we introduce two additional hyper- paremmear,etesss the scaling factor y and the maximum pruning ratio 3, to make our algorithm further flexible and applicable.
Next, we walk through our SAP algorithm. Before the pruning starts, we randomly generate model parameters Wini- We will use Wini to initialize retained model parameters at each pruning iterations. The lottery ticket pruning algorithm shows that the performance of retraining the subnetworks from Wint is better than from scratch. Then, we initialize the mask mg with all ones. Suppose we have T' number of pruning iterations. For each pruning iteration f = 0, 1, ... T, we first initialize the model parameters i and compute the number of model parameters de as follows
Wiit C M,
de |mel
(3)
where O is the Hadamard product. After training the model parameters w, with m, by freezing the gradient for E epoch, we arrive at trained model parameters wy. Upon this point, our algorithm has no difference from the classical lottery ticket pruming algorithm. The lottery ticket pruning algorithm will then prune d' P parameters from m, according to the magnitude of w and finally create new mask m4+1-
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 Sparsity-informed Adaptive Pruning (SAP)
Input:
model parameters w, mask m, norm p < g. compression hyper--aranne T/, scaling factor maximum pruning ratio 3, number of epochs E, and number of pruning iterations T.
Randomly generate model parameters Wimi Initialize mask mh with all ones
for each pruning iteration = 1, 0,..2....TOO
Initialize model parameters wi - Winit 3 my Compute the number of model parameters d, |mell
Train the model parameters W, with my for E epochs and arrive at w/
Compute PQ Index I(wx,) = d;
|elll
Wele
Compute the lower bound of the number of retained model parameters
T1 de(1 (r))-//(o-p)///)) [ I(w,,) )=
Compute the number of pruned model parameters
C. [d. min(?(1 ())]
Prune Cr model parameters with the smallest magnitude based on we and m.
Create new mask m4+1
end
Output: The pruned model parameters wr and mask mrr
After arriving at wr, our proposed SAP will compute the PQ Index, denoted by I(we), and the lower bound of the number of retrained model parameters, denoted by Tt, as follows
Ro llp I(w+) 1 - de |
r: = ===111 + n.) --)--/(--000p0) () I(wx))
(4)
Then, we compute the number of pruned model parameters c Id. (1 Here, introduce accelerate or decelerate the pruming initial pruning iterations. Specifically, y 1 or < encourages the pruning ratio to be larger or smaller than the pruning ratio derived from the PQI-bound, respectively. As the retraining of pruned models is time-consuming, it is appealing to efficiently obtain the smallest pruned model with satisfactory performance for a small number of pruning iterations. In addition, we introduce the maximum pruning ratio avoid excessive pruning because we will compress more than the PQI-bound if > 1 and may completely prune all model parameters. If we set y 1, 9 can be safely omitted. In our experiments, we set 0.9 only to provide minimum protection from excessive pruning at each pruning iteration. Finally, we prune e. model parameters with the smallest magnitude based on wi and m, and finally create new mask M for the next pruning iteration.
EXPERIMENTAL STUDIES
4.1 EXPERIMENTAL SETUP
We conduct experiments with FaSS (Xiao et al. 2017). CIFARIO, CIFARIO0 Krizhevsky
сt al. 2009), and TinylmageNet (Le & Yang 2015) datasets. Our backbone models are Linear, Multi- Layer Perceptron (MLP), Convolutional Neural Network (CNN). ResNet18, ResNet50 (He) al. 201 and Wide ResNet28x8 (WResNe128x8) (Zagoruyko & Komodakis 2016). We run experiments for T = 30 pruning iterations with Linear, MLP, and CNN, and T 15 pruning iterations with ResNet18. We compare the proposed SAP with two baselines, including 'One Shot' and 'Lottery Ticket' (Frankle & Carbin 2018) pruning algorithms. The difference between 'One Shot' and 'Lottery Ticket' pruning algorithms is that "One Shot' prunes d P model parameters at each pruning iteration from instead of w, We have P = 0.2 throughout our experiments. We compare the proposed PQ Index (p- 0.5, g = 1.0) with the well-known Gini Index (Ginil 1912) to validate its effectiveness in evaluating sparsity. Furthermore, we perform pruning on various pruning scopes, including 'Neuron-wise Pruning," "Layer-wise Pruning," and 'Global Pruning.' In particular, 'Global Pruning" gather all model parameters as a vector for pruning, while "Neuron-wise Pruning' and LLayer-wise Pruning' prune each neuron and layer model parameters separately. The number of neurons at each layer is equal to the output size of that layer. For example, 'One Shot' and 'Lottery Ticket methods with "Neuron-win Pruning' prune d, model parameters of each neuron, where d, refers to the size of each neuron. Similarly, SAP computes the PQ Index and the number of pruned

---

Published as a conference paper at ICLR 2023
1.0
-3
60
P3 13dee
Die Brddee
70
20
0.0
20
30
20
30
10
20
30
20
[a] Retrained models
ACC noy DPoeeTC
0.15
0.3
0.2
Takee (--02)
0.0
0.00
50
10
20
10
30
10
20
(b) models
Figure 2: Results of (a) retrained and (b) pruned models at each pruning iteration for 'Global Pruning" with FashionMNIST and MLP, where (a) is obtained from the models after retraining and (b) is directly from those after pruning.
Senwerro tiagge
0.8
0.8
60
2-12
Oe y
3.0
10
Perstion
Beration17
bension
bemaion
models
ACC mey Dreene--e -c
244
15 15
507
2-
(b) Pruned models
Figure 3: Results of (a) retrained and (b) pruned models at each pruning iteration for 'Global Pruning' with CIFARIO and ResNet18.
model parameters for neuron Details of the model architecture and learning hyper-papn parameters included in the Appendix. We conducted four random experiments with different seeds, and the standard deviation is shown in the error bar of all figures. Further experimental results can be found in the Appendix.
4.2 EXPERIMENTAL RESULTS
Retrained models We demonstrate the results of retrained models (w, mm,) at each pruning iteration in Figure a) and Ja). In particular, illustrate the performance, percent of remaining weights, PQ Index, and Gini Index at each pruning iteration. these experiments, П) and y are set to 0 and 1 to prevent interference. The 'Lottery Ticket' method outperforms "One Shot' expected. SAP (p 1.0, 2.0) compresses more aggressively than SAP (p 0.5, 1.0). Recall that SAP adaptively adjusts the pruning ratio based the sparsity of models, while "One Shot' and Lotttry Ticket' have fixed pruning ratio at each pruning iteration. In Figure 2 a)) SAP (p 1.0, g = 2.0) at around 10 achieves similar performance as 'Lottery Ticket' around
25. Furthermore. SAP (p 0.5. 1.0) and 'Lottery Ticket' have similar pruning ratio before T = 10, but SAP (p = 0.5, 9 1.0) adaptively lowers the pruning ratio and thus prevents the performance from deteriorating like 'Lottery Ticket' does after T - 25. In Figure 3 a). we observe similar fast pruning phenomenon of SAP (p- = 1.0, 2.0). Meanwhile, SAP (p = O.5, q = 1.0) performs similar to 'Lottery Ticket' but prunes more than 'Lottery Ticket' does. Consequently, by carefully choosing and q, SAP can provide more efficient and robust pruning. As for the sparsity of retrained models, the result of the PQ Index is aligned with the Gini Index, which experimentally demonstrates that the PQ Index can effectively measure the sparsity model parameters. Furthermore, the dynamics of the sparsity also corroborates our hypothesis, shown by 'One Shot' in Figure 2 aa) and SAP
7

---

Published as a conference paper at ICLR 2023
Neuron-wise Pruning
Layer-wise Pruning
Global Pruning
Accuracy
Accunauy
Accuracy
80
80
80
SMP to to- 0.5.0- 1.0.0
SMP jo- 1.0 2.00
Lutiery Tickst (.2
One Shot (h-
100
100
80
100
Percent Remaining Weights
Fercent Remaining Weights
Percent of Remaining Weights
(a) Compression Trade-off
Porcent of Remaining Weights
Nouron wish Pruning
Percent of nemaainin Weights
Layer wise Pruning
Percent of Remainingg Weights
Global Pruning
100
Rist layer
100
100
Mascle layee
Lnd layst
20
10
20
0
10
20
10
20
30
Iteration
Iteration (T)
Iteration (T)
(b) Layer-wise Percent of Remaining Weights
Nauron wise Pruning
Layer-wise Pruning
Global Pruning
0.5
PQ Intox
PO Indllxx
PQ Index
0.2
0.3
0.3
Fost laver
0.2
Middie byyt
layer
0.1
0.2
10
20
10
20 30
10
20
30
lteration IT)
Iteration (T)
Iteration
(c) Layer-wise PQ Index
Figure 4: Results of various pruning scopes regarding (a) compression trade-off, (b) layer-wise percent of remaining weights, and (c) layer-wise PQ Index for CIFAR1O and CNN. (b, c) are performed with
SAP (p = 0.5, 1.0).
(p = 1.0, g 2.0) in Figure Baa.. The results show that an ideal pruning procedure should avoid rapid increase in sparsity.
Pruned models We demonstrate the results of pruned models at each pruning iteration in Figure (b) 3J). In particular, we illustrate the performance, performance difference, PQ Index, and PQ Index difference at each pruning iteration. The performance and PQ Index are computed directly from the pruned models without retraining. The performance and PQ Index difference is between the retrained (wo @ m, for 'One Shot' and wt @ m, for 'Lottery Ticket' and SAP) and pruned models (wo m+++1 for 'One Shot' and W/ ① M++1 for 'Lottery Ticket' and SAP). The results of performance difference show that the performance pruned models without retraining from SAP can perform close that of retrained models. Furthermore, the sparsity of pruned models shows that iterative pruning generally decreases the sparsity of pruned models. Meanwhile, the sparsity difference of pruned models provides a sanity check by showing that pruning at each pruning iteration decreases the sparsity of retrained models.
Pruning scopes We demonstrate various pruning scopes regarding compression trade-off, layer-wise percent of remaining weights, and layer-wise PQ Index in Figure The results of the compression trade-off show that SAP with 'Global Pruning' may perform worse than 'One Shot' and 'Lottery Ticket' when the percent of remaining weights is small. As illustrated in the "Global Pruning' of is because SAP with 'Global Pruning"
Figure (b), the first layer has not been pruned enough. measures the sparsity of all model parameters in vector, and the magnitude of the parameters of the first layer and other layers may not be at the same scale. As a result, the parameters of the first layer will not be pruned until late pruning iterations. However, SAP with 'Neuron-wise Pruning' and Layer-wiie Pruning' perform better than 'One Shot' and 'Lottery Ticket.' SAP can adaptively adjust the pruning ratio of each neuron and layer, but 'One Shot' and 'Lottery Ticket' may over-prunt specific neurons and layers because they adopt fixed pruning ratio. Interestingly, the parameters of the first layer are pruned more aggressively by "Neuron-wise Pruning' than 'Global Pruning' in the
8

---

Published as a conference paper at ICLR 2023
14
0.8
83
0.2
20
10
Peration
beration
Eeration
83
8
8
PO Fr0m
Cral
6.2
70
10
20
30
10
70
30
Karatio
[b]p
1.0
Figure 5: Ablation studies of and for global pruning with CIFARIO IO and CNN.
100
8
Ciea trodes
PO
22
20
0.01
0.0
20
30
20
30
10
20
30
10
20
Earation1
Larabon
(4) 1.0
100
Cre Ieskes
2.2
Reration 11)
Eeration:
Reration
Eeration (T)
Figure 6: Ablation studies of and y for global pruning with CIFAR1O and CNN.
[bl
early pruning iterations. However, they are not pruned by "Neuron-wise Pruning" in the late pruning iterations, while 'Global Pruning' still prunes them aggressively. It aligns with the intuition that the initial layers of CNN are more important to maintain the performance, e.g., Gale et al. (2019) observed that the first layer often more important to model quality and pruned less than other layers. Furthermore, the PQ Index of 'Ncuron wise Pruning" is also more stable than the other two pruning scopes, which indicates that 'Neuron-wise Pruning' is more appropriate for SAP, the PQ Index is computed more precisely.
Ablation studies We demonstrate ablation studies of p and q in Figure In Figure 5 a), fix == 1.0 and study the effect of p. The results show that SAP prunes more aggressively when = 1.0 and is close g. In Figure 5 b). fix p 1.0 and study the effect of q. The results show that SAP prunes more aggressively when = 1.0 and is distant from p. We demonstrate ablation studies of пパ and y in Figure 6 In Figure ((a). a). we fix 7 1.0 and study the effect of 77, The results show that SAP prunes more aggressively when > O. In Figure G(b), we fix 7) 0.0 and study the effect of y. The results show that SAP prunes more aggressively when y > Interestingly, the performance of our results roughly follows logistic decay model due to the adaptive pruning ratio, and the inflection point corresponds to the peak of the sparsity measure. Moreover, the dynamics of the sparsity measure of SAP with various ablation studies also corroborate our hypothesis.
CONCLUSION
We proposed new notion of sparsity for vectors named PQ Index (PQI), which follows the principles a sparsity measure should obey. We develop a new perspective on the compressibility of neural networks by measuring the sparsity of pruned models. We postulate hypothesis on the relationship between the sparsity and compressibility of neural networks. Motivated by our proposed PQI and hypothesis, further develop a Sparsity-ifformed Adaptive Pruning (SAP) algorithm that uses PQI to choose the pruning ratio adaptively. Our experimental results demonstrate that SAP can compress more efficiently and robustly than state-of-the-ar algorithms.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported in part by the Office of Naval Research (ONR) under grant number N00014-21-1-2590.
REFERENCES
Mehmet Akçakaya and Vahid Tarokh. A frame construction and universal distortion bound for sparse representations. IEEE Transactions on Signal Processing, 56(6):2443- 2008
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Proc. ICML, pp. 254-263, 2018.
Andrew Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information Theory, 39(3):33-9945, 1993.
Cenk Baykal, Lueas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. Data-dependent coresets for compressing neural networks with applications to generalization bounds. arXiv preprint urXiv:18044 1804.05345, 2018
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Proc. NeurIPS, 1877-1999,, 2020.
Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):122-1555) 2001.
Hugh Dalton. The measurement the inequality incomes. The Economic Journal, 30(119):
348-361, 1920.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
Enmao Diao, Jie Ding, and Vahid Tarokh. Restricted recurrent neural networks. In IEEE International Conference on Big Data, pp. 56-63. IEEE, 2019.
Enmao Diao, Jie Ding, and Vahid Tarokh. HeteroFL: Computation and communication efficient federated learning for heterogeneous clients. International Conference Learning Representations (ICLR), 2021.
Enmao Diao, Jie Ding, and Vahid Tarokh. GAL: Gradient assisted learning for decentralized multi- organization collaborations. Conference on Neurul Information Processing Systems (NeurIPS), 2022.
Jie Ding, Vahid Tarokh, and Yuhong Yang. Model selection techniques: An overview. IEEE Signal Processing Magazine, 35(6):16 34, 2018.
Jie Ding, Eric Tramel, Anit Kumar Sahu, Shuang Wu, Salman Avestimehr, and Tao Zhang. Federated learning challenges and opportunities: An outlook. In JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8752 8756. IEEE, 2022.
David L Donoho. 2006.
Compressed sensing. IEEE Transactions Information Theory, 1284):1289-1300
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiy preprint arXiv:1803.03633 2018
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks, arXiv preprint arXiv: 1002:/902.009 09574, 2019.
10

---

Published as a conference paper at ICLR 2023
Corrado Gini. Variabilità mutabilità: contributo allo studio delle distribucioni e delle relazioni statistiche. (Facc. I.J. Tipogr. di P. Cuppini, 1912.
Masafumi Hagiwara. Removal of hidden units and weights for back propagation networks. In Proc. IJCNN, volume 1, pp. 351-354, 1993.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 1rXiv::510.01144 2015.
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, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Proc. ECCV, pp. 635-645. Springer, 2016b.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proc. ICCV, pp. 1389-1397, 1397, 2017.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint arXiv:1503.022
2015.
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. Mach. Learn. Res., 22(241):1-124, 2021.
Hengyuan Hu, Rui Peng, Yu- Yu-Wing Tai, and Chi-Keung Tang. Network trimming: data-driven neuron pruning approach towards efficient deep architectures. arXiv preprint arXiv.1607.03250. 2016.
Niall Hurley and Scott Rickard. Comparing measures of sparsity. IEEE Transactions on Information Theory, 55(10):4723-444 2009.
Lou Jost. Entropy and diversity. Oikos, 113(2):333-755 2006.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05442, 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Proc. NeurIPS, 25, 2012.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60(6):84-90, 2017.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Proc. NeurlPS, 2, 1989.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, (6(11):2278-233) 1998.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based connection sensitivity, arXiv preprint arXiv: 1810002300 2018.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint /60.v:/608.0339 2016.
Hao Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruning method for deep neural network compression. Proc. ICCV, pp. 5058-5066, 2017.
Erum Mushtaq, Chaoyang He, Jie Ding, and Salman Avestimehr. Spider: Searching personalized neural architecture for federated learning. arXiv preprint arXiv:21 /2, 13939, 2021.
11

---

Published as a conference paper at ICLR 2023
Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feldman. Data- independent neural pruning via coresets. arXiv preprint arXiv: 2019.
Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint (7Xiv:660900349)) 2016.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training. 2018.
Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unified, real-time object detection. In Proc. CVPR, pp- 779-788, 2016.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint arXiv:2003.023:3 2020.
Scott Rickard and Maurice Fallon. The gini index of speech. In Proceedings of the 38th Conference on Information Science and Systems (CISS'04) 2004.
Steffen Schneider, Alexei Baevski, Ronan Collobert, and Michael Auli. wav2vee: Unsupervised pre-training for speech recognition. arXiv preprint 1rX4h::904.05000 2019.
Mohammadreza Soltani, Suya Wu, Jie Ding, Robert Ravier, and Vahid Tarokh. On the information of feature maps and pruning of deep neural networks. In Proc. ICPR, pp. 6988-6995, 2021.
Robert Tibshirani. Regression shrinkage and selection via the lasso. J. Royal Stat. Soc. B, 58(1): 267-288, 1996.
Jianyou Wang, Michael Xue, Ryan Culhane, Enmao Diao, Jie Ding, and Vahid Tarokh. Speech emotion recognition with dual-sequence Istm architecture. In JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6478.6478. IEEE, 2020.
Zhan Wang, Sandra Paterlini, Fuchang Gao, and Yuhong Yang. Adaptive minimax regression estimation over sparse 1,-hulls. J. Mach. Learn. Res., 151):1165--171,, 2014.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Wenjing Yang, Ganghua Wang, Jie Ding, and Yuhong Yang. A theoretical understanding of neural network compression from sparse linear approximation. arXiv preprint arXiv:2206.0560 2022.
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, and Qiang Liu. Good subnetworkss provably exist: Pruning via greedy forward selection. In Proc. ICML., pp. 10820-10830, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.07146. 2016.
12


Reviews:
[{"review_id": "yZlc_mOUWbf", "reviewer": "Reviewer_UD4g", "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": "", "summary_of_the_paper": "In this work, the authors proposed PQ Index (PQI) to measure the potential compressibility of deep neural networks and it is used to develop a Sparsity-informed Adaptive Pruning (SAP) algorithm.", "summary_of_the_review": "This paper proposed a new sparsity measure: PQ index, and they developed SAP for pruning. However, some details of the SAP algorithm are missing, and there are no experiments for large-scale datasets and models.", "strength_and_weaknesses": "+The authors developed the PQ index, which satisfies the properties of an ideal sparsity measure.\n\n+They further proposed the sparsity-informed adaptive pruning method based on the PQ index.\n\n-It's unclear how SAP can reach a pre-defined pruning rate given some iterations since SAP is an adaptive pruning algorithm. Many hyperparameters are related to the pruning rate per iteration, like $\\eta_r$, $\\beta$, and $\\gamma$.\n\n-Authors mentioned that \"pruning is based on the assumption that parameters with small magnitudes are removable.\" However, this is not always the case, many methods use other criteria to measure the importance of each weight besides its magnitude. \n\n-The paper didn't include large-scale datasets and models. As a result, the scalability of this method is not clear. Large models like ResNet-50 on ImageNet should also be added. The initial version of the lottery ticket can not work for large models, and the authors should show that SAP does not have the same problem. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "xKsmV3J3v9m", "reviewer": "Reviewer_dVA5", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper introduces a norm based metric (PQ-Index) to quantify weight sparsity of a neural network. The metric is designed to satisfy the six properties proposed by earlier research in economy similar to the Gini Index. PQ-Index is then used to decide how much a neural network can be pruned at a given time during the training. Authors compare their method to Lottery-ticket style iterative pruning on CIFAR and Fashion-MNIST.", "summary_of_the_review": "Overall quite interesting work, my concerns lie in experimental evaluations of the work. More specifically contributions 2 and 4 in introduction are not well supported:\n- Relationship between PQI and compressibility is not measured directly. This can be done with one-shot pruning experiments (See Suggestion above).\n- \"SAP can compress more efficiently than SOTA algorithms\" is also not well supported since, Lottery style iterative magnitude pruning is far from being a SOTA algorithm and most plots doesn't show improved performance (or hard to read). \n\nI recommend authors to focus on showing the utility of the metric they developed and understand its strengths and limitations. I think such contribution alone would make a good paper. If proposing a pruning algorithm, experiments/plots/validation needs to be improved/clarified.", "strength_and_weaknesses": "# Strengths\n- Proposal of a grounded sparsity metric. As far as I know, this part is novel and the most exciting part of this work. I appreciate the utilization of cross-domain knowledge.\n\n# Weakness\n- Experimental results are not clear and convincing. Lottery ticket pruning does as good or better than proposed method in many plots. Do you do hyper-parameter search for different methods? A fair comparison should include different fraction values for lottery style pruning. Similarly when different p/q values are selected one probably needs to pick different hyper-parameters. Also, plots needs to be improved to highlight the differences between methods. Using log on the y axis (Figure-2/3) can help with this I think.\n- \"sota algorithms such as LT-based pruning\" This statement is not correct. See [1], which show rewinding the weights is a bad choice and [2] which shows gradual magnitude pruning often achieves best results. It's fine not to have SOTA results/algorithms but this statement is not correct and needs to be changed. I recommend using another pruning algorithm like gradual magnitude pruning with or without learning rate recycling (see [2]).\n- Authors say in the introduction \"the sparsity will first decrease when a large model is being effectively regularized\", however I haven't seen any evidence for this claim. Have I missed a plot? It would be nice to show this in a regular training run (like resnet in cifar-10 with learning rate decay and 200 epochs of training). Similarly one could think of experiment that show the usefulness of the PQ-Index at predicting pruning rates. Can PQ-Index predict maximum pruning rate over the course of the training? How well this compare to using a fix magnitude threshold? \n\n# Questions\n- Looking at Theorem-2, n_r=0 seems to imply removing only zeros. Is that accurate? If so, would be nice to make this clear.\n- Do you include pruned connections (zeros) in your PQI calculations? \n- Figure:5-a there is a peak on the PQ-Index at T=20. Why is this? With a high score like this I would expect performance not to drop after pruning. \n\n# Suggestions\n- When p=0.5 and q=1, sparsity would be equal to PQ-metric if I understand correctly. d=100, one-hot, sparsity=PQ-index=0.99. It would be nice to do experiments on pretrained models at different widths and sparsities (this can be achieved with different regularization coefficients) and show how well PQ-index provide maximum pruning rate without significant performance drop. It is very difficult to make conclusion in the LT-rewinding setting since, pruning is repeated multiple times and it is not clear a decision was good or not.\n\n# Minor\n- (Page 8: \"It aligns with the intuition..\") [2] shows that early layers are often better kept dense.\n- It would be nice to compare the final sparsity distributions found by PQI with the ones provided by the ERK distribution [3]. \n- \"pruning is the most popular and effective approach\" probably quantization had much more impact on this due to the int8 support on many recent hardware. \n- Remark 3 \"... does not satisfy the six properties\" -> which of the six? I think some of them are satisfied. It would be nice to be more specific here.\n- Lottery ticket prunes p% of the remaining weights. So the #weights pruned at each iteration decreases over time.\n- Figure:3, it is not clear which methods does better (like many others).\n\n## After Rebuttal\nI thank authors for their extensive response. After reading their response and checking the changes indicated with blue; I decided to keep my score as it is. That's being said, I wouldn't oppose acceptance. Overall I find the the metric quite interesting, however experimental evaluation for proposed pruning method needs to be improved. I recommend authors to focus on showing the utility of PQI directly using the same model but different metrics (e.g. measuring exactly how close it gets to the max-prune rate). Similarly I think the fixed-pruning rate needs to be searched-over for the LT baseline (like trying P=0.2,0.1,0.3) just to make sure gains are not due to better rate average rate (first point in weakness section). Also I like to re-iterate switching the log-scale for plots, as it is still very difficult to compare different curves at the moment. \n\n[1] https://arxiv.org/abs/2003.02389\n[2] https://arxiv.org/abs/1902.09574\n[3] https://arxiv.org/abs/1911.11134", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cLBR_YlCxVE", "reviewer": "Reviewer_fMpo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "summary_of_the_paper": "The proposed work emphasizes the problem that during pruning there isn't a concrete way to estimate the compressability of a sub-network, which may lead to over- or under-pruning. The PQIndex is proposed to measure this concept and by extension is used to define the Sparsity-informed Adaptive Pruning (SAP) algorithm. Overall, the proposed work measures the trends in sparsity and how it fluctuates during different levels of pruning.", "summary_of_the_review": "The novelty of the proposed PQI measure and the pruning algorithm are of keen interest. However, the results could be further improved to make it more comparable to state-of-the-art approaches.", "strength_and_weaknesses": "Strengths\n- A well rounded explanation of the various properties of a sparsity measure and how PQI satisfies them.\n- The scope of ablation and results presented analyze the given method well.\n\nWeaknesses\n- I encourage the authors to put forward the general notion of sparsity that is assumed across the paper (as defined in $S(w)$) early on in the introduction so that reader can follow the ideas put forward in Fig. 1.\n- One of the major issues in the context of pruning literatures' results is the use of MNIST, FashionMNIST and CIFAR10 to evaluate the performance of the proposed model. I encourage the authors to further expand the set of dataset-DNN pairs they experiment on in order to incorporate more real-world data and ensure their observations remain consistent.\n- From a more practical perspective, could the authors discuss the absolute limit up to which they can push the sparsity limit of various networks? (Since that is the ultimate goal)\n- By extension, could the authors discuss difference in performance values and PQI at the extreme end of sparsity (highlight in existing results)?\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TyG86QduirX", "reviewer": "Reviewer_Tdbq", "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": "", "summary_of_the_paper": "The paper introduces a pruning quality index (PQI) that satisfies desired properties (according to previous work) which can be used to set sparsity ratios. They use PQI to obtain sparsity ratios in the lottery ticket algorithm and show improved results.", "summary_of_the_review": "The introduced PQI index is novel and would be valuable to the community. The benefits are demonstrated in the experiments. However, the necessity of additional hyperparameters raises some questions about the practical value. \n\n## Post rebuttal\nI thank the authors for the response. As mentioned by reviewer dVA5, the practical implementation of the method is cumbersome due to additional hyperparameters. Nevertheless, the introduced PQI has value and I'm keeping the marginal-accept score.", "strength_and_weaknesses": "## Strengths\n1. The problem of identifying sparsity ratios is important and it is valuable for many pruning algorithms. The introduced PQI has desirable properties and shows improved performance when used to adaptively set sparsity ratios while pruning.\n2. The paper is well-written and the claims are backed by theory and experiments\n\n## Weaknesses\n1. The final algorithm introduces additional hyperparameters (eg., \\eta_r, \\gamma, \\beta) and is not clear about the necessity and if they are necessary raises concerns about the introduced PQI. Specifically if \\eta_r is a hyperparameter then how is it different to having r as a hyperparameter? I presume the algorithm is not sensitive to the value of \\eta_r too much but it would be good to clarify this. \n2. The argument made in fig.1 is handwavy and not clear how it helps the narrative of the paper. To me, it was a distraction while reading the paper and it would be better to introduce PQI as early as possible.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster