Provable Filter Pruning for Efficient Neural Networks
Authors: Lucas Liebenwein
Cenk Baykal
Harry Lang
Dan Feldman
Daniela Rus
Venue:  (2020)
Keywords: theory
compression
filter pruning
neural networks

Abstract: We present a provable, sampling-based approach for generating compact Convolutional Neural Networks (CNNs) by identifying and removing redundant filters from an over-parameterized network. Our algorithm uses a small batch of input data points to assign a saliency score to each filter and constructs an importance sampling distribution where filters that highly affect the output are sampled with correspondingly high probability. 
In contrast to existing filter pruning approaches, our method is simultaneously data-informed, exhibits provable guarantees on the size and performance of the pruned network, and is widely applicable to varying network architectures and data sets. Our analytical bounds bridge the notions of compressibility and importance of network structures, which gives rise to a fully-automated procedure for identifying and preserving filters in layers that are essential to the network's performance. Our experimental evaluations on popular architectures and data sets show that our algorithm consistently generates sparser and more efficient models than those constructed by existing filter pruning approaches. 

PROVABLE FILTER PRUNING FOR EFFICIENT NEURAL NETWORKS
Lucas Liebenwein CSAIL, MIT lucas 1esmmmmtt....m edu
Cenk Baykal* CSAIL, MIT ba baykal eeykka@mit.... 1@mit.edu
Harry Lang CSAIL, MIT harryl Prry1mmiteed
Dan Feldman
Daniela Rus CSAIL, MIT
University of Haifa dannyf.
post Saanyf.post@e
gma com
rusêcsail mit.mimte......
ABSTRACT
We present a provable, sampling- based approach for generating compact Convo- lutional Neural Networks (CNNs) by identifying and removing redundant filters from an werr-parameterized network. Our algorithm uses a small batch of input data points assign saliency score each filter and constructs an importance sampling distribution where filters that highly affect the output are sampled with correspondingly high probability. In contrast to existing filter pruning approaches, our method is simultaneously data-informed, exhibits provable guarantees the size and performance of the pruned network, and is widely applicable to varying network architectures and data sets. Our analytical bounds bridge the notions of compressibility and importance of network structures, which gives rise to a fully-automated procedure for identifying and preserving filters in layers that are essential to the network's s performance. Our experimental evaluations on popular ar- chitectures and data sets show that our algorithm consistently generates sparser and more efficient models than those constructed by existing filter pruning approaches.
INTRODUCTION
Despite widespread empirical success, modern networks with millions of parameters require excessive amounts of memory and computational resources to store and conduct inference. These stringent requirements make it challenging and prohibitive to deploy large neural networks on resource resource-limited platforms. A popular approach to alleviate these practical concerns is to utilize pruning algorithm to remove redundant parameters from the original, ever-parameterized network. The objective of network pruning to generate a sparse, efficient model that achieves minimal loss in predictive power relative to that of the original network.
common practice to obtain small, efficient network architectures is to train an wer-parameterized network, prune it by removing the least significant weights, and re-train the pruned network (Gale et al. 2019: Frankle Carbin 2019) Han et al. 2015) Baykal et al. 2019b). This prune-retrain cycle often repeated iteratively until the network cannot be pruned any further without incurring a significant loss in predictive accuracy relative to that of the original model. The computational complexity of this iterative procedure depends greatly the effectiveness of the pruning algorithm used in identifying and preserving the essential structures of the original network. To this end, diverse of smart pruning strategies have been proposed in order generate compact, accurate neural network models in a computationally efficient way.
However, modern pruning approaches are generally based on heuristics (Han et al. 2015 Ullrich
et al. 2017: He et al., 2018 Luo et al. [017 Li et al. 2016 Lee et al. 2019 Yu et al. 201 7a) that lack guarantees on the size and performance of the pruned network, require cumbersome ablation
studies (Li et al., 2016 He et al. 2018) manual hyper-parameter tuning (Luo et al. 201 7), or
"These authors contributed equally to this work.
We refer the reader Sec. A the appendix for additional details about the related work.

---

Data batch
Compute filter sensitivity in each layer
Prune filters and output compressed net
W
af
0.20
Per-Layer Filter Pruning
0.15
0.10
W
0.05
0.00
Filter sensitivity s) from feature map importance
Sample filter with probability p$ sj
Figure Overview of our pruning method. We use small batch of data points to quantify the relative importance sf of cach filter W in layer & by considering the importance of the corresponding feature map af = d(2f) in computing the output 2+1 of layer + 1, where Φ(-) is the non-linear activation function. We then prune filters by sampling each filter j with probability proportional to sf and removing the filters that were not sampled. We invoke the filter pruning procedure each layer to obtain the pruned network (the prune step); we then retrain the pruned network (retrain step), and repeat the prine- retrain cycle iteratively.
heavily rely on assumptions such that parameters with large weight magnitudes are more important which does not hold general (Ye et al., 2018: Li al. 2016 Yu et al., 7017a| Han et al.! 2015).
In this paper, we introduce a data-informed algorithm for pruning redundant filters in Convolutional Neural Networks while incurring minimal loss the network's accuracy (see Fig. [ for an overview). At the heart of our method lies novel definition of filter importance, i.c.. filter sensitivity, that is computed by using a small batch of input points. We prove that by empirically evaluating the relative contribution of each filter to the output of the layer, can accurately capture its importance with respect to the other filters in the network. We show that sampling filters with probabilities proportional to their sensitivities leads to importance sampling scheme with low variance, which enables us to establish rigorous theoretical guarantees on the size and performance of the resulting pruned network. Our analysis helps bridge the notions of compressibility and importance of each network layer: layers that are more compressible are less important for preserving the output of the original network, and versa. Hence, we obtain and introduce fully-automated sample size allocation procedure for properly identifying and preserving critical network structures corollary.
Unlike weight pruning approaches that lead to irregular sparsity patterns - requiring specialized libraries or hardware to enable computational speedups our approach compresses the original network to a slimmer subnetwork by pruning filters, which enables accelerated inference with any off-the-shelf deep learning library and hardware. We evaluate and compare the effectiveness of our approach in pruning diverse set of network architectures trained on real-world data sets. Our empirical results show that our approach generates sparser and more efficient models with minimal loss accuracy when compared to those generated by statc-of-the-an filter pruning approaches
SAMPLING- BASSED FILTER PRUNING
In this section, we introduce the network pruning problem and outline our sampling sampling-based based filter pruming procedure and its theoretical properties. We extend the notion of empirical sensitivity (Baykal et al., 2019a) to quantify the importance of each filter using small set of input points. We show that our importance criterion enables to construct a low- variance importance sampling distribution over the filters each layer. conclude by showing that our approach can eliminate a large fraction of filters while ensuring that the output of each layer is approximately preserved.
"oode available at http://///gghhthtcc////////a////
2

---

2.1 PRELIMINARIES
Consider a trained L layer network with parameters 0 (W1, "y'....."),, where W denotes the 4-dimensional tensor in layer & E [T.. W filter j E [n/), and of the number of filters in layer f. Moreover, let W be channel j of tensor W4+1 that corresponds to filter Wy. We let X C R and y c R denote the input and output space, respectively. The marginal distribution over the input space is given by D. For an input z E X to the network, we let 2x() and a (x)) ((=((x)) denote the pre-activation and activation of layer L, where & is the activation function (applied entry-wise). The jth feature map of layer l is given by (x) (( (see Fig. L. For given input E X, the output of the neural network with parameters 0 is given by [0
Our overarching goal is to prune filters from each layer [4] by random sampling to generate a compact reparameterization of 0, (Wi1.... ..... W2, where the number of filters in the pruned weight tensor W is a small fraction of the number of filters in the original (uncompressed) tensor W'. Let size(0) denote the total number of parameters in the network, i.e., the sum of the number of weights over each W E (W ..... W
Pruning Objective For a given e, 6 E (0, 1), our objective is to generate compressed network with parameters 9 such that size < siz) and P (fa(()) E (1 = fo)))) 2 - 6, where fa()) E (1 + f) (x) denotes an entry-wise guarantee over the output neurons fz), fo(x) E y.
2.2 BAMSL PRUNING
Our sampling-based filter pruning algorithm for an arbitrary layer L E [Z] is depicted as Alg. []] The sampling procedure takes as input the set of of channels in layer é + 1 that con- stitute the weight tensor W i.e. W =
Algorithm 1 PRUNECHANNELS (W++1 e, s*)
Input: w.++1 [W W.+ J: original chan-
one
nels; e: relative error; 8: failure prohability; s': fcature map sensitivities as in []]
[W1+1 ,..., ay as well as the desired rela- tive error and failure probability, e, E (0, 1). respectively. In Line 2 we construct the im- portance sampling distribution over the feature maps corresponding to the channels by lever- aging the empirical sensitivity of each feature map.j E In') as defined in ( and explained in detail in the following subsections. Note that initially prune channels from W but as we simultane-
Output: WiF+1; pruned channels
I: S + Eienn sf (where 2i is as in ①
2: př ss/s² Vjj Vjell [nf]
3: m² + |66+ 2*) K log(4%,/8)e 18)) =1
4: Wett +- [O.....0) 0] [same dimensions as W
5: for E [m"]] do
6: c(k) + random draw from p' =pii.....
7: Wett + :o(k: + Withh/mfpea Ppcm
prune channels from W ously prune the corresponding filters in W
end for
9: return Wh [W:4+
We subsequently set the sample complexity m as a function of the given error (e) and failure probability (d) parameters in order to ensure that, after the pruning (i.e., sampling) procedure, the approximate output with respect the sampled channels li of the layer will approximate the true output of the layer - with respect to the original tensor up to multiplicative factor of least 8. Intuitively, more samples are required to achieve a low
(1 +). with probability specified error with low failure probability 8, and vice-versa. We then proceed to sample m' times with replacement according to distribution p (Lines 8) and reweigh each sample by a factor that is inversely proportional to its sample probability to obtain an unbiased estimator for the layer's s output (see below). The unsampled channels in w and the corresponding filters in W are subsequently discarded, leading reduction in the layer's size.
2.3 A
ESTIMATOR
We now turn our attention to analyzing the influence of the sampled channels W (as in Alg. 1 on layer f + 1. For case of presentation, will henceforth assume that the layer is linear and will omit
"The extension CNNs follows directly outlined Sec. B of the supplementary material.
3

---

explicit references the imput whenever appropriate. Note that the pre-activation of layer l + is given by zf+1 W a², and the approximate pre-activation with respect to W is given by gf+1 We+1 a.. By construction of W in Alg. | equivalently have for each entry i [n [f|1]
Yas
where
Y
W sc(k) P((k)
(c(k) c(k)
vk.
By reweighing our samples, we obtain an unbiased estimator for each entry of the true pre-activation output, i.e., B [= 2 = which follows by the linearity of expectation and the fact that [Yxx] 2t L+1 for each & E [m] and so we have for the entire vector E 1 | far, we have shown that in expectation, our channel sampling procedure incurs zero error owing to its unbiasedness. However, our objective is to obtain high probability bound on the entry-wise deviation g 2 I for each entry i, which implies that we have to show that our estimator s/+1 is highly concentrated around its mean 2, To do so, we leverage the following standard result.
2 So
Theorem (Bernstein's 's inequality (Vershynin 2016)). Let YI.... Y. a sequence of m i.i.d. random variables satisfying maXke[m] LE E
[Y&]] S R. and let Y >m Ys denote their sum.
Then, for every 2 0, 8 E (0, 1), we have that P ((1 m E [T&]] 2 &E (E) S 6 for
log(2/6)
VVr(Yr)) 2
m 2 [V
Letting i E [nf be arbitrary and applying Theorem to the mean of the random variables (Yu) [e[]] i.e., to øf-1, we observe that the number of samples required for a sufficiently high concentration around the mean is highly dependent on the magnitude and variance of the random variables (Yx)).- By definition of Yike observe that these expressions are explicit functions of the sampling distribution p². Thus, to minimizq" the number of samples required to achieve high concentration we require a judiciously defined sampling distribution that simultaneously minimizes both R, and Var(Yx For example, the naive approach of uniform sampling, i.e., P` 1/7/ for each j E [n²]] also leads to an unbiased estimator, however, for uniform sampling we have Var(Yx) v7 E [Y and R2 As rf mmxx (wft aa)) and so Var(Yw), E 2(7F) in the general case, leading to a linear sampling complexity m E 12(7²) by Theorem
2.4 EMPIRICAL SENSITIVITY (ES)
To obtain better sampling distribution, we extend the notion of Empirical Sensitivity (ES) introduced by Baykal et al. (2019)) to prune channels. Specifically, for W 2 0 (the generalization can be found in Appendix let the sensitivity sf of feature map j in be defined
w (+1 ax))
max max ZES +E( EKE(P
Wik (x)
where is a set of f independent and identically (i..d.) points drawn from D. Intuitively, the sensitivity of feature map j E [7/]] is the maximum (over [1)++]) relative impact that feature map. had on any pre-activation in the next layer 2+1 We then define the probability of sampling each channel as in Alg. j E [n/]] as P, = /5/5,, where S = E3 sy is the sum sensitivities. Under a mild assumption on the distribution that satisfied by wide class of distributions, such as the Uniform, Gaussian, Exponential, among others- of activations (Asm. in Sec. [ of the supplementary), ES enables us to leverage the inherent stochasticity in the draw 2 ~ D and establish 7 in Sec. B) that with high probability (over the randomness in S and x)) that
(see Lemmas 5 6 and
Var(Ya) E ((SB(ra)) and Rt E ((aE
and that the sampling complexity is given by m E O log(2/8) by Theorem
We note that ES does not require knowledge of the data distribution and is easy to compute in practice by randomly drawing small set of input points S from the validation set and passing
'We define the minimization with respect to sample complexity from Theorem 1 which serves sufficiently good proxy Bernstein's 's inequality is tight up logarithmic factors (Tropp et al. 2015).
4

---

the points in S through the network. This stands in contrast with the sensitivity framework used in state-of-the-aie coresets constructions (Braverman et al.) [016; Bachem et al. (017). where the sensitivity is defined to be with respect to the supremum over all E supp(D) (D) in instead of a maximum over I E S. As also noted by |Bakal et al. (2099)), ES inherently considers data points that likely to be drawn from the distribution D in practice, leading more practical and informed sampling distribution with lower sampling complexity.
Our insights from the discussion in this section culminate in the core theorem below (Thm. 2). which establishes that the pruned channels W (corresponding to pruned filters in W generated by Alg. [ is such that the output of layer 8 + 1 is well-approximatee for each entry.
Theorem 2. Lete,õ E (0, 1), [L]. and let S be set of (log (n-/6)) i..dd samples drawn from D. Then, W contains at most O 1o)( 2)) channels and for D, with probability at least 1 8, we have g--1 (1 + e)2f+1 (entry-wise), where 1). maX ""
Theorem can be generalized to hold for all weights and applied iteratively to obtain layer-wise approximation guarantees for the output of each layer. The resulting layer-wise error can then be propagated through the layers obtain guarantee the final output of the compressed network. In particular, applying the error propagation bounds of Baykal et al. (2019)). we establish our main compression theorem below. The proofs and additional details can be found in the appendix (Sec. B).
Theorem 3. Let E, ô E (0, 1) be arbitrary, let S C. X denote the set of K log (417 i..d points drawn from D, and suppose
given network with parameters 0 (W the set of parameters θ = (W),.. ..... WT) generated by pruning channels of according Alg. for each L [L]. Then, 0 satisfies P8 AND (fo(z) E (1+tt =(fo()) 2 Ø is bounded by O Et La (a 2- 325 se loR(n/0)
WL). Consider
6, and the number of filters in
RELATIVE LAYER IMPORTANCE
vgg16, BN, CIFAR10
224.2200 8 224 208-226668
Percentage Total Budget
15
Fixed Prune Ratio
Ours
1x3x 1000
5
covelldoo--iee posing fuly noctod-Reus
softree
0
2
4
8
10
12
14
Layer Index
(a) VGG16 architecture
(b) Budget Allocation for VGG16
Figure 2: Early layers of VGG are relatively harder to approximate due their large spatial dimensions as shown (a). Our bounds naturally bridge layer compressibility and importance and enable automatically allocate relatively more samples early layers and less latter layers shown (b). The final layer due its immediate influence on the output is also automatically assigned a large portion of the sampling budget.
In the previous sections, we established the sampling complexity of our filter pruning scheme for any user-specified e and 8. However, in practice, it is more common for the practitioner to specify the desired pruning ratio, which specifies the resulting size of the pruned model. Given this sampling budget, practical question that arises is how to optimally ration the sampling budget across the network's 's layers to minimize the error of the pruned model. A naive approach would be to uniformly allocate the sampling budget N that the same ratio of filters is kept in each layer. However, this allocation scheme implicitly assumes that each layer of the network is of equal importance to retaining the output, which is virtually never the case in practice, exemplified by Fig. 2(a).
turns out that our analytical bounds on the sample complexity per layer (m in Alg. 1 naturally capture the importance of each layer. The key insight lies in bridging the compressibility and
5

---

importance of each layer: if layer is not very important, i..,, it does not heavily influence output of the network, then we expect to be highly compressible, and vice-versa. This intuition is precisely captured by sampling complexity bounds that quantify the difficulty of layer's compressibility.
We leverage this insight to formulate a simple binary search procedure for judiciously allocating the sampling budget N as follows. Let ō E (0. 1) be user-specified, pick random 0, and compute the sampling complexity m' as in Alg. together with the resulting layer size n'. If L n' N, we are done, otherwise, continue searching for an appropriate E on smaller interval depending whether Ee n' is greater or less than N. The allocation generated by this procedure (see Fig. b for an example) ensures that the maximum layer-wise error incurred by pruning is at most E.
4 RESULTS
In this section, we evaluate and compare our algorithm's 's performance to that of state-of-the-ar pruning schemes in generating compact networks that retain the predictive accuracy of the original model. Our evaluations show that our approach generates significantly smaller and more efficient models compared to those generated by competing methods. Our results demonstrate the practicality and wide-spread applicability of our proposed approach: across all of our experiments, our algorithm took on the order of a minute to prune a given network required no manual tuning of its hyper- parameters, and performed consistently well across diverse set of pruning scenarios. Additional results, comparisons, and experimental details can be found in Sec. E of the appendix.
4.1 EXPERIMENTAL SETUP
We compare our algorithm to that of the following filter pruning algorithms that we implemented and alongside our algorithm: Filter Thresholding (FT, Li et al. (201)),, SoftNet (He al.) (0018). and ThiNet (Luo et al., (017). We note that FT and SoftNet are both (weight) magnitude- based filter pruning algorithms, and this class of pruning schemes has recently been reported to be state-of-the art (Gale et al., 2019 Pitas et al. 2019; Yu et al. 2018) (see Sec. Tf the appendix for details of the compared methods). Additional comparisons other state-of-the-ar channel and filter pruning methods can be found in Tables 6 and 8 in Appendix E.4 and E.6 respectively.
Our algorithm only requires two inputs in practice: the desired pruning ratio (PR) and failure probability 5 E (0, 1). since the number of samples in each layer is automatically assigned by our allocation procedure described in Sec. Following the conventional data partioning ratio, we reserve 90% of the training data set for training and the remaining 10% for the validation set (Lee et al.) 2019)
For each scenario, we prune the original (pre-trained) network with a target prune ratio using the respective pruning algorithm and fine-tune the network by retraining for specified number epochs. We repeat this procedure iteratively to obtain various target prune ratios and report the percentage of parameters pruned (PR) and the percent reduction in FLOPS (FR) for each target prune ratio. The target prune ratio follows hyperharmonic sequence where the 7t PR is determined by 1 1/(i+1)", where a is an experinent-depender tuning parameter. We conduct the prune-retrain cycle for a range of 10 - 20 target prune ratios, and report the highest PR and FR for which the compressed network achieves commensurate accuracy, i.e., when the pruned model's 's test accuracy is within 0.5% of the original model. The quantities reported are averaged over trained models for each scenario, unless stated otherwise. The full details of our experimental setup and the hyper-parametee used can be found in the appendix (Sec.
4.2 LENET ARCHITECTURES ON MNIST
As our first experiment, we evaluated the performance of our pruning algorithm and the comparison methods on LeNet300-100 (LeCun et al. 1998), a fully-connected network with two hidden layers of size 300 and 100 hidden units, respectively, and convolutional counterpart, LeNet-5 (LeCun et al., 1998), which consists of two convolutional layers and two fully-connected layers. Both networks were trained on MNIST using the syper-parameter specified in Sec.
FExcluding the time required for the fine-tuning step, which was approximately the same across all methods

---

Table the performance of each pruning algorithm in attaining the sparsest possible network that achieves com- mensurate accuracy for the LeNet architectures. In both scenarios, our algorithm generates significantly sparser net- works compared to those generated by the competing filter pruning approaches. In fact, the pruned LeNet-5 model generated by our algorithm by removing filters achieves a prune ratio of z 90%, which is even competitive with the accuracy of the sparse models generated by state-of-thh-arr weight pruning algorithms (Lee et al. 2019) 6 In addition to evaluating the sparsity the generated models subject to the commensurate accuracy constraint, we also investigated the performance the pruning algorithms for extreme (i.c..
[%]
Method
Err.
PR
LeNet-300- 100
Unpruned
1.59
Ours
+0.41
84.32
FT
+0.35
81.68
SoftNet
+0,41
81.69
ThiNet
+10.58
75.01
Unpruned
0.72
LeNet-5
Ours
+0.35
92.37
FT
+0.47
85.04
SoftNet
+0.40
80.57
ThiNet
+0.12
58.17
around 5%) pruning ratios (see Fig. 3(a) ((a)). We that algorithm's 's performance relative to those competing algo- rithms is strictly better for wide range of target prune ratios. For LeNet-5 Fig. ((a) shows that our algorithm's 's favorable performance is even more pronounced at extreme sparsity levels (at == 95% prune ratio).
Table 1: The prune ratio (PR) and the cor- responding test error (Err.) of the sparsest network with commensurate accuracy generated by each algorithm.
4.3 CONVOLUTIONAL NEURAL NETWORKS ON CIFAR-10
Next, we evaluated the performance of each pruning algorithm on significantly larger and deeper Convolutional Neural Networks trained on the CIFAR-10 data set: VGG16 with BatchNorm (ST monyan Zisserman 2015), ResNer20, ResNet56, ResNetl 10 (He et 2016). DenseNet22 (Huang et 2017), and WideResNerl 6-8 (Zagoruyko & Komodakis 2016). For CIFAR-10 experiments, we use the standard data augmentation techniques: padding 4 pixels on each side, random crop to 32x32 pixels, and random horizontal flip. Our results summarized in Table 2 and Figure 3 Similar to the results reported in Table D in the previous subsection, Table 2 shows that our method is able to achieve the most sparse model with minimal loss in predictive power relative the original network. Furthermore, by inspecting the values reported for ratio of Flops pruned (FR), we observe that the models generated by our approach are not only more sparse in terms of the number of total parameters, but also more efficient in terms of the inference time complexity.
Orig.
Ours
FT
SoftNet
ThiNet
[%)]
Err.
Err.
PR
FR
Err.
PR
FR
Err.
PR
FR
Err.
PR
FR
ResNer20
8.60
+0.49
62.67
45.46
+0.43
42.65
44.59
+0.50
46.42
49.40
+2.10
32.90
32.73
ResNet56
7.05
+0.28
88.98
84.42
+0.48
81.46
82.73
+0.36
81.46
82.73
+1.28
50.08
50.06
ResNet110
6.43
+0.36
92.07
89.76
+0.17
86.38
87.39
+0.34
86.38
87.39
+0.92
49.70
50.39
VGGI6
7.11
+0.50
94.32
85.03
+1.11
80.09
80.14
+0.81
63.95
63.91
+2.13
63.95
64.02
DenseNet22
10.07
+0.46
56.44
62.66
+0.32
29.31
30.23
+0.21
29.31
30.23
+4.36
50.76
51.06
WRN16-8
4.83
+0.46
66.22
64.57
+0.40
24.88
24.74
+0.14
16.93
16.77
+0.35
14.18 14.09
Table 2: Overview of the pruning performance of each algorithm for various CNN architectures. For each algorithm and network architecture, the table reports the prune ratio (PR, %) and pruned Flops ratio (FR, %) of pruned models when achieving test accuracy within 0.5% of the original network's 's accuracy (or the closest result when the desired test accuracy was not achieved for the range of tested PRs). Our results indicate that our pruning algorithm generates smaller and more efficient networks with minimal loss in accuracy. when compared to competing approaches.
Fig. 3 depicts the performance of the evaluated algorithms for various levels of prune ratios. Once again, we see the consistently better performance of our algorithm in generating sparser models that approximately match exceed the predictive accuracy of the original uncompressed network. In addition, Table (see Appendix E.6 for more details) provides further comparisons to state-of-the-a
"Weight pruning approaches can generate significantly sparser models with commensurate accuracy than filter pruning approaches since the set of feasible solutions to the problem of filter pruning is subset of the feasible set for the weight pruning problem
7

---

Lenet 5, MNIST
resnet56, CIFAR10
resnet110, CIFARLO
Reference Net Ours
Raference Not
Referance Net
2,00
Ours
1.75
FT
Test Error 1%
1.50
SoftNet
SoftNet
SoftNitt
1.25
1.00
0.75
10
15
20
25
30
10
20
30
40
50
10
20
30
40
50
Retained Parameters (75)
Retained Parameters (%)
Retained Parameters (25)
(a) LeNet5
(b) ResNet56
(c) ResNetl 10
vggl6, CIFARIO
densenel22. CIFARIO
wm16,, 8, CIFARIO
11
Reference Net
12
Reference
1.0
11
Test 8
Ours
Test Error (%6)
9
SoftNet
Test Error
10
SoftNet
0
Reference Net
6
SoftNvet
10
15
20
25
30
35
40
50
60
70
20
40
60
Retained Parameterss (%)
Retained Parameters 0%)
Retained Parameters (%)
(d) VGG16
(c) DenseNet22
WRNI6-8
Figure 3: The accuracy of the generated pruned models for the evaluated pruning schemes for various target prune ratios. Note that the x axis the percentage parameters retained, i.c., (1 pruneratio). ThiNet was omitted from the plots for better readability. Our results show that our approach generates pruned networks with minimal loss in accuracy even for high prune ratios. Shaded regions correspond to values within one standard deviation of the mean.
filter pruning methods where we compare the performance of our approach to the results for various ResNets and VGG16 reported directly in the respective papers. The comparisons in Table reaffirm that our algorithm can consistently generate simultancously sparser and more accurate networks compared to competing methods.
In view of our results from the previous subsection, the results shown in Table 2 Fig. S and Table highlight the versatility and broad applicability of our method, and seem to suggest that our approach fares better relative to the compared algorithms on more challenging pruning tasks that involve large-scale networks. We suspect that these favorable properties are explained by the data-informed evaluations of filter importance and the corresponding theoretical guarantees of our algorithm - which enable robustness to variations in network architecture and data distribution.
4.4 CONVOLUTIONAL NEURAL NETWORKS ON IMAGENET
We consider pruning convolutional neural networks of varying size ResNet18, ResNet50, and ResNet101 - trained on the ImageNet (Russakovsky et al. 2015) data set. For this dataset, we considered two scenarios: (i) iterative pruming without retraining and (ii) iterative prune-retrain with a limited amount of iterations given the eesource-intessii nature of the experiments. The results of these experiments are reported in Section E.4 of the appendix. Our results on the ImageNet data set follow a similar trend as those in the previous subsections and indicate that our method readily scales larger data sets without the need of manual hyerrparameter tuning. This improves upon existing approaches (such as those in He et al. (2018); Li et al. (2016) that generally require tedious, task-specific intervention or manual parameter tuning by the practitioner.
4.5 APPLICATION TO REAL-TIME REGRESSION TASKS
Real-time applications of neural networks, such as their use in autonomous driving scenarios, require network models that are not only highly accurate, but also highly efficient, i.e., fast, when it comes to inference time complexity (Amini et al. 2018). Model compression, and in particular, filter pruning has potential to generate compressed networks capable of achieving both of these objectives. To evaluate and compare the effectiveness of our method on pruning networks intended for regression
8

---

tasks and real-time systems, evaluated the various prun- ing approaches on the DeepKnight network (Amini et al. 2018). regression network deployed on autonomous vehicle in real time to predict the steering angle of the hu-
deepknight, Driving
Reference Net Ours
man driver (see E.5 in appendix for experimental details).
Test Loss
3
FT
SoftNet
Fig. 4 depicts the results of our evaluations and compar- isons the DeepKnight network without the fine-tuning step. We omitted the iterative fine-tuning step for this sce- nario and instead evaluated the test loss for various prune ratios because (i) the evaluated algorithms were able to generate highly accurate models without the retraining step and (ii) in order to evaluate and compare the perfor- mance of solely the core pruning procedure. Similar the results obtained in the preceding pruning scenarios, Fig. 4 shows that our method consistently outperforms competing approaches for all of the specified prune ratios.
1
0.5
2.0 Retained Parameters (96
1.0
1.5
2.5
3.0
3.5
Figure 4: The performance of the compared algorithms on pruning a lightweight network for a real-time regression task (Amini et al.) 2018).
4.6 DISCUSSION
In addition to the favorable empirical results of our algorithm, approach exhibits various ad- vantages over competing methods that manifest themselves our empirical evaluations. For one, algorithm does not require any additional hyper- param-errsmeters other than the pruning ratio and the desired failure probability. Given these sole two parameters, our approach automatically allocates the number of filters sample for each layer. This alleviates the need perform time-intensive ablation studies (He et al. 2018) and to resort to uninformed (i.e., uniform) sample allocation strategies, e.g., removing the same percentage of filters each layer (Li al. 2016), which fails to consider the non-uniform influence of each layer on the network's 's output (see Sec. B Moreover, our algorithm is simple-to- to-implemmetttt and computationally efficient both in theory and practice: the computational complexity is dominated by the (S] forward passes required to compute the sensitivities ((S S 256 in practical settings) and in practice, our algorithm takes on the order minute to prune the network.
CONCLUSION
We presented to the best of our knowledge the first filter pruning algorithm that generates pruned network with theoretical guarantees on the size and performance of the generated network. Our method is data-informed, simple-to-implement and efficient both in theory and practice. Our approach can also be broadly applied to varying network architectures and data sets with minimal hyper-paramette tuming necessary. This stands in contrast to existing filter pruming approaches that are generally data-oblivious, rely on heuristics for evaluating the parameter importance, or require tedious dyper-paramest tuning. Our empirical evaluations data sets reaffirm the favorable theoretical properties of our method and demonstrate its practical effectiveness in obtaining sparse, efficient networks. We envision that besides its immediate use for pruning state-of-the-at models, our approach can also be used as a sub-procedure in other deep learning applications, e-g., for identifying winning lottery tickets (Frankle & Carbin 2019) and for efficient architecture search (Liu et al. 2019b).
popular network architectures and
ACKNOWLEDGMENTS
This research was supported in part by the U.S. National Science Foundation (NSF) under Awards 1723943 and 1526815, Office of Naval Research (ONR) Grant N00014-18-1-2880 Microsoft, and JP Morgan Chase.
REFERENCES
Dimitris Achlioptas, Zohar Karnin, and Edo Liberty. Matrix entry-wise sampling: Simple is best. Submitted KDD, 2013(1.1):144, 2013.

---

Jose M Alvarez and Mathieu Salzmann. Compression-aware training of deep networks. In Advances in Neural Information Processing Systems, pp. 856-867, 2017.
Alexander Amini, Liam Paull, Thomas Balch, Sertac Karaman, and Daniela Rus. Learning steering bounds for parallel autonomous systems. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 1-8. IEEE, 2018.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference Machine Learning, pp. 254-263, 2018.
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv preprint
2017.
Cenk Baykal, Lucas Liebenwein, Igor Gilittchennki, Dan Feldman, and Daniela Rus. Data-dependent coresets for compressing neural networks with applications to generalization bounds. In Interna- tional Conference Learning Representations, 2019a. URL URRl:hhtts:://eeeeeee
net/
Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. Sipping neural networks: Sensitiity-iiffrmeed provable pruning of neural networks. arXiv preprint arXiv:1910.05422, 2019b.
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. arXiv preprint arXiv:1612.00SS: 2016.
Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In International conference on machine learning, pp. 2285-2294, 2015.
Anna Choromanska, Krzysztof Choromanski, Mariusz Bojarski, Tony Jebara, Sanjiv Kumar, and Yann LeCun. Binary embeddings with structured hashed projections. In International Conference on Machine Learning, pp. 344 1-33,, 2016.
Emily L Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances neural information processing systems, pp. 1269-1277, 2014.
Xuanyi Dong, Junshi Huang, Yi Yang, and Shuicheng Yan. More less: A more complicated network with less inference complexity. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pp. 5840-5848, 2017.
Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via matrix- valued bernstein inequality. Information Processing Letters, 1 111(8)338--89 2011.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 569-578. ACM, 2011.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:
//openreview.co
net. hwt.:/ent/fooooooe http://ormmmmimmmomoooo http:/oooom------------------
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574 2019.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In Advances In Neural Information Processing Systems, pp. 1379-1387, 2016.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning. trained quantization and huffman coding. CoRR, abs/1510.00149, 2015. URL
10

---

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, 2016.
Yang He, Guoliang Kang, Xuanyi Dong. Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. In Proceedings of the 27th International Joint Conference Artificial Intelligence, pp.
AAAT Press, 2018
Yang He, Ping Liu, Ziwei Wang, Zhilan Hu, and Yi Yang. Filter pruning via geometric median for deep convolutional neural networks acceleration. In Proceedings of the IEEE Conference on 2019.
Computer Vision and Pattern Recognition, pp.
Yihui He, Xiangyu Zhang, and Jian Sun, Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE International Conference Computer Vision, pp. 1389-1397, 2017.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Qiangui Huang, Kevin Zhou, Suya You, and UIrich Neumann. Learning to prune filters in convo- lutional neural networks. In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 709-718. IEEE, 2018
Yani Ioannou, Duncan Robertson, Jamie Shotton, Roberto Cipolla, and Antonio Criminisi. Training cnns with low-rank filters for efficient image classification. arXiv preprint 1.1.0:151, 2015.
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. In Proceedings of the British Machine Vision Conference. BMVA Press, 2014.
Abhisek Kundu and Petros Drineas. A note on randomized element-wise matrix sparsification. arXiv preprint arXiv: 0320, 2014.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-598889 605, 1990.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):2278-23)) -2224, 1998.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2019. URL
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXiv:1608.08770, 2016.
Yawei Li, Shuhang Gu, Lue Van Gool, and Radu Timofte. Learning filter basis for convolutional neural network compression. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5623-5632, 2019.
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In International Conference on Learning Representations, 2020. URL
.nt/ htwp://wwwwww.eeeouuuuttaaaeeeee Forum:id=-Jmmmmm
Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang. Kwang-Ting Cheng, and Jian Sun. Metapruning: Meta learning for automatic neural network channel pruning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3296-3305, 2019a.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In International Conference on Learning Representations, 2019b. URL
net htt.ee/ee//ooormmm...oo...11

---

Jian-Hao Luo and Jianxin Wu. Autopruner: An end-to-end trainable filter pruning method for efficient deep model inference. arXiv preprint 1rXiv:1805.08941, 2018.
Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruning method for deep neural network compression. In Proceedings of the IEEE international conference on computer vision, pp. 5058-5066, 2017.
Shannon McCurdy. Ridge regression and provable deterministic ridge leverage score sampling. In Advances in Neural Information Processing Systems, pp. 2463-2472, 2018.
Dimitris Papailiopoulos, Anastasios Kyrillidis, and Christos Boutsidis. Provable deterministic leverage score sampling. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 997-1006. ACM, 2014.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS- W, 2017.
Konstantinos Pitas, Mike Davies, and Pierre Vandergheynst. Revisiting hard thresholding for dnn pruning. arXiv preprint 19Xiv:9055008740 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 (3):211-2522 2015, doi: 10.1007/s1 1261000-1.....
Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vishwanathan. Hash kernels for structured data. Journal of Machine Learning Research, ((Novv)226152631) 2009.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409. 1556, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
Karen Ultrich, Edward Meeds, and Max Welling. Soft weight-sharing for neural network compression. arXiv preprint arXiv: 1702.0000 2017.
Ramon van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
Roman Vershynin. High-dimensional probability. An Introduction with Applications, 2016.
Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning, pp. 1113-1120 2009.
Jianbo Ye, Xin Lu, Zhe Lin, and James Z. Wang. Rethinking the maaller-nomm-es--infornaitt assumption in channel pruning of convolution layers. In International Conference on Learning Representations, 2018
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching- Yung Lin, and Larry S Davis. Nisp: Pruning networks using neuron importance score propagation. Preprint https://arxiv. arg/abs/1711.55900 2017a.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui- Jui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching- Yung Lin, and Larry S Davis. Nisp: Pruning networks using neuron importance score propagation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9194-9203, 2018.
12

---

Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7370-7379, 2017b.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 16Xiv:1605.07144 2016.
Liang Zhao, Siyu Liao, Yanzhi Wang, Zhe Li, Jian Tang, and Bo Yuan. Theoretical properties for neural networks with weight matrices of low displacement rank. In Proceedings of the 34th International Conference Machine Cetrninn-Volumee 70, pp. 4082-4090. JMLR. org, 2017.
13

---

A
RELATED WORK
General network compression The need to tame the excessive storage requirements and costly inference associated with large, over-parameterized networks has led to rich body of work in network pruning and compression. These approaches range from those inspired by classical tensor decompositions (Yu et al.
2017b Jaderberg al. 2014 Denton et al. 2014), and random projections and hashing (Arora et al. 2018 Ullrich et al. 2017 Chen et al. 2015; Weinberger et al.) [2099]
Shi et al. 2009) that compress a pre-trained network, to those approaches that enable sparsity by embedding sparsity an objective directly in the training process (loannou et al. 2015| Alvarez Salzmann 2017) or exploit tensor structure to induce sparsity (Choromanska et al. [0166] Zhao
et 2017). Overall, the predominant drawback of these methods is that they require laborious hyperparameter tuning, lack rigorous theoretical guarantees on the size and performance of the resulting compressed network, and/or conduct compression in a data oblivious way.
Weight-based pruning A large subset of modern pruning algorithms fall under the general approach of pruning individual weights of the network by assigning each weight saliency score, e.g., its magnitude (Han et al. (2015), and subsequently inducing sparsity by deterministically removing those
weights below certain saliency score threshold (Guo al. 2016 Han et al.) 2015 Lee al. 2019 LeCun et al. 1990). These approaches are heuristics that do not provide any theoretical performance guarantees and generally require with the exception of (Lee et al. 2019) computationally expensive train- ceen-prunne-eetee returnn cycles and tedious hyper-pare parameter tuning. Unlike our approach that enables accelerated inference (i.e., reduction in FLOPS)) on any hardware and with any deep learning library by generating a smaller subnetwork, weight- based pruning generates a model with non-structured sparsity that requires specialized hardware and sparse linear algebra libraries in order to speed up inference.
Neuron pruning Pruning entire neurons in FNNs and filters CNNs particularly appealing as it shrinks the network into its slimmer counterpart, which leads to alleviated storage requirements and improved inference-time performance on any hardware. Similar to the weight-basce baaed approaches, approaches in this domain assign an importance score each neuron filter and remove those with a score below a certain threshold (He et al. 2018 Li et al., 2016 Yu et al. (017a)) These approaches generally take the E, norm -with p 11 as popular choices- of the filters to assign filter importance and subsequently prune unimportant filers. These methods are data-oblivious heuristies that heavily rely on the assumption that filters with large weight magnitudes are more important, which may not hold in general YYe et al. 2018).
In general, prior work on neuron and filter pruning has focused on approaches that lack theoretical guarantees and a principled approach to allocating the sampling budget across layers, requiring tedious ablation studies or settling for naive uniform allocation across the layers. In contrast to prior approaches, our algorithm assigns data-informed saliency scores to filters, guarantees an error bound, and leverages our theoretical error bounds to automatically identify important layers and allocate the user-specified sampling budget (i.e., pruning ratio) across the layers.
Our work most similar to that of (Baykal et al., 2019a|b) b), which proposed an weight pruning algorithm with provable guarantees that samples weights of the network in accordance to an empirical notion of parameter importance. The main drawback of their approach is the limited applicability to only fully- tully-connected networks, and the lack of inference- time acceleration due to non-structured sparsity caused by removing individual weights. Our method is also sampling-bard based and relies on data-infe inta-informed notion of importance, however, unlike (Baykal al., 22199 b), our approach can be applied to both FNNs and CNNs and generates sparse, efficient subnetworks that accelerate inference.
B ALGORITHMIC AND ANALYTICAL DETAILS
Algorithm 2 is the full algorithm for pruning features, i.e., neurons in fully-connected layers and channels in convolutional layers. For notational simplicity, we will derive our theoretical results for linear layers, i.c., neuron pruning. We remind the reader that this result also applies to CNNs by taking channels of a weight tensor in place of neurons. The pseudocode is organized for clarity of exposition rather than computational efficiency. Recall that 0 is the full parameter set of the net,
14

---

where 8 E R R is the weight matrix between layers & - and and &. W refers the hth neuron of W
Algorithm 2 PRUNECHANNELSSO,..CC
extended version
Input: trained net; &' [Z]: layer; S C supp(D): sample of inputs; e (0, 1): accuracy: 8 e (0, 1): failure probability
Output: W filter-redueed weight tensor for layer é: W channel reduced, weight tensor for layer
1: for j E [n/]]
2:
for i E [7/ []
I and E S do
3:
I + [JE In'l w (x) 2 0}
4:
r - /
13000
5:
(x) t max
Exer "i (x))
end for
7: of maxxes /r 9i5 (x))
end for
9: 5t + +E Ej
10: for E In" do
11: PS + 8//5"
12: end for
13: K value from Assumption
m [6 + 2c) St K 1o
15: H distribution on [ny'] assigning probability pl to index j
16: H (0.-..,,) 0) (same dimensions W')
17: W e+ + (0...., 0) |same dimensions as W W+++1
18: for [m] do
19: c(k) + random draw from 71
20:
W. c(() + Wa( (no reweighing or considering multiplicity of drawing index c(k) multiple times)
wi++
21:
We+1 W +
(reweighing for unbiasedness of pre-activation in layer E-
:o(k) ((k))
22:
end for
23: return We [W W W [W5+]
W
Recall that 2, +x) (x) denotes the pre-activation of the 7th neuron in layer + given input x, and the activation (x) max zx)))
Definition (Edge Sensitivity (Baykal et al. 2019a).. Fixing a layer &. E [4]. let wij of edge (j.i) In'] x [n] The empirical sensitivity of weight entry wff with respect input
1+1 be the weight
x E X is defined to be
e+1 ax((x) Wij
(x) max 9
IE(1-
Eker Wik [f(())
where 1+ edges, respectively.
T+= = (j [nf] w
at 2 0) and T (n') \ I+ denote the set of positive and negative
Algorithm 2 uses empirical sensitivity compute the sensitivity of neurons Lines 12
Definition (Neuron Sensitivity). The sensitivity of a neuron j E [nf]] in layer is defined as
max max gij xES (-()++11
(x)
In this section, we prove that Algorithm yields good approximation of the original net. We begin with mild assumption to ensure that the distribution of our input is not pathological.
Assumption 1. There exist universal constants K, K' > 0 such that for any layer & and all j E (n*). the CDF of the random variable max 93j (xx) for ~ D, denoted by F, (-), satisfies (M//K) exp (-1/k),
where MG min 1]: F, 11)
15

---

Note that the analysis is carried out for the positive and negative elements of W separately, which also considered in the definition of sensitivity (Def. For ease of exposition, we will thus assume that throughout the section W > 0 (element-wise), i.c., I+ [n]], and derive the results for this case. However, we note that we could equivalently assume W < and the analysis would hold regardless. By considering both the positive and negative parts of W in Def. 1 we can carry out the analysis for weight tensors with positive and negative elements.
Theorem 2. Let E, E (0, 1), l E [ and S be set of Ollo (n./6)) ii.d. samples drawn from D. Then, W contains at most O(S 1og(n,/5)e= (()=-))))))))))))))))))))))))))) channels and x ~ D, with probability at least 1 8, we have 2f-1 (1 + e) (enlry-wise), where T/. -maxee14) n/.
The remainder of this section builds towards proving Theorem 2 We begin by fixing layer l [L] and neuron [n/+ Consider the random variables (Yx [e(m) where (x() mpy
e+1 (x()
where Algorithm 2 selected index j [ny]] on the hthh iteration of Line 19 Note that 23 (x)
Ejelo'] w. af (x) and so we may also write Isj (x) w af((x)
(x) when it is more
convenient.
Lemma 4. For each x X and & [m]. E [Xx((x)]
2 2(+1 (x)/m. /m.
Proof. Y, is drawn from distribution H. defined on Line 13
so we compute the expectation directly.
E+1
og (x)
E [[y
Σ
Wik
Pk.
m Pke
kE(v9)
Wik a (x)
6+1
m kE(n9
f+1 (x)
m
To bound the variance, we use an approach inspired by Baykal et al. (2019a) where the main idea is to use the notion of empirical sensitivity to establish that particular useful inequality holds with high probability over the randomness of the input point x ~ D. Given that the inequality holds we can establish favorable bounds on the variance and magnitude of the random variables, which lead to a low sampling complexity.
For random input point x ~ DD let G denote the event that the following inequality holds (for all neurons):
(+) S Css VE(n
Vj E In''
max
where C maxx33, 1} and K is defined as in Assumption We now prove that under Assump- tion 1 event 9 occurs with high probability. From now on, to ease notation, we will drop certain superscriptsssubseripss with the meaning clear. For example, 2(x) will refer to 2 2+1 (x).
Lemma 5. If Assumption holds, PP()) > - 8/2nf. Here the probability is over the randomness of drawing x ~ D.
Proof. Since maxie (z) is just function of the random variable x D. for any j E [n''] we can let D be distribution over max (z) and observe that since 8j maxxes maxie(net (x), the negation of event G for single neuron j E [n]]] can be expressed as the event
X C max X KE[[S]]
where X D and X X d.d.d.
D since the points in S were drawn i..d. from D. Invoking Lemma 8 from Baykal et al. (2019a) in conjunction with Assumption [ we obtain for any arbitrary
IP max (i)(x) > C(s)) = P(X C max Xx) - exp(-IS1/R3 kE[[S|]
16

---

with the K' from Assumption Since choice of neuron arbitrary, the inequality above holds for all neurons, therefore we can apply the union bound to obtain:
(g) --P E In'l
max gi5(2) Css))
:Elv
2 1 Σ
P max (is(() C3))
iElyet
jE(nf]
2 1 n exp( (8)/K)
5
2 1 2n e+
where the last line follows from the fact that [S] 2 log (2nf(1(11/6)
Lemma 6. For any such that event G occurs, then (Yx(x) - B|Y((x)]I - CS2/m. Here the expectation is over the randomness of Algorithm
Proof. Recall that S = Eje(n 8j. Let neuron j [n]]] be selected on iteration k of Line 19 For
any & [m]] we have:
(ija,(x)
(x(x)
mp
S (x)a,(x)
msj
S CS (x)
maxy gin (x)
(x)a;(x)
S CS mig (x)
CS2
where the first inequality follows by the inequality of event G. the second by the fact that
maxy (x) 2 (x)(x) for any i, and the third equality by definition of 9x)(x) = Wija (x) /0/22xx (x).
This implies that Y E [Y& = V = E [-2/m, CS2/m] by Lemma and since Y& 2 0. The result follows since C,S 1.
Lemma 7. For any x such that event G occurs, then Var(Yr(x)) < CS22/m/2 /m²². Here the expectation over the randomness of Algorithm
Proof. We can the same inequality obtained by conditioning & to bound the variance of our estimator.
Var(Yx(x)) E (x)) (E (+)())))
(x)
(x) (x) )
Σ
Ps
by definition of Y₁
mpj
jE(T9
S
(x))a;(x))²
since p; s,/$
m
8j
JE(N
CS
(x))
by occurrence of event G
m
max (x)
JEIm9
CS z
Σ (x)a((x)
since (x)( = (x)a((x)22(x)
m²
jE(nf)
CS2
m?
17

---

We are now ready to prove Theorem
Proof of Theorem 2 Recall the form Bernstein's inequality that, given random variables Xm,...,Xm such that for each & [m]] we have E [Xx] 0 and [&ll M almost surely, then
-112 [kElm B + Mt/3
P
Σ ke[m]
X 2t t
S exp
We apply this with X₁ Y m
We must take the probability with respect the randommess of
both drawing x ~ DD and Algorithm 2 By Lemma E x 0. Let assume that event & occurs.
By Lemma we may set M CS2/m. m. By Lemma the inequality with & E2.
Σ Eeemmi
E [X2] S CS22 /m2 We will apply
Observe that Exe(m) Xx= = - z. Plugging in these values, and taking both tails of the inequality, obtain:
-²2 /2
P([ - 2/ E2 :9) S exxp
CSS22 /m m + CSSEz? /
E² m
= 2 exp
(-SK (6 + 2s)
since C I 3K
< 8
by definition of
21
Removing dependence on event G, we write:
8
(1
P( - 2| 2 σz) 2 P( 22
:)
2
(1-
20pet1
++
5
2
where we have applied Lemma This implies the result for any single neuron, and the theorem follows by application of the union bound over all e neurons in layer L.
B. BOOSTING SAMPLING VIA DETERMINISTIC CHOICES
Importance sampling schemes, such the one described above, are powerful tools with numerous
applications in Big Data settings, ranging from sparsifying matrices (Baykal et al. 2019a Achlioptas al. 2013; Drineas & Zouzias 2011 Kundu & Drineas 20144] Tropp et al. 2015) to constructing coresets for machine learning problems (Braverman al.] 201d; & Langberg 2011 Bachem ctt al.) 2017). However, by the nature of the exponential decay in probability associated with importance sampling schemes (see Theorem D. sampling schemes perform truly well when the sampling pool and the number of samples is sufficiently large (Tropp et al. 2015). However, under certain conditions
the sampling distribution, the size of the sampling pool, and the size of the desired sample m, it has been observed that deterministically picking the m samples corresponding the highest probabilities may yield an estimator that incurs lower error (McCurdy 2018 Papailiopoulos et al. 2014).
To this end, consider hybrid scheme that picks & indices deterministically (without reweighing) and samples m' indices. More formally, let Caet. C [n] be the set of & unique indices (corresponding to weights) that are picked deterministically. and define
Edet
Wijaf,
JECa..
where we note that the weights are not reweighed. Now let Crand set of m' indices sampled from the remaining indices i.e., sampled from [m] Caet. with probability distribution g (q,,... 94))
18

---

To define the distribution q. recall that the original distribution p is defined to be p: s:/S for each [n]. Now, q is simply the normalized distribution resulting from setting the probabilities associated with indices in Cast to be 0, i.c.
if Caets
S-
otherwise
where S& - Ejecaa 8j is the sum of sensitivities of the entries that were deterministically picked.
Instead of doing combinatorial search over all (2) choices for the deterministic set Cdet. for computational efficiency, we found that setting Cdea to be the indices with the top k sensitivities was most likely set to satisfy the condition above.
We state the general theorem below.
Theorem 8. It is better to keep l feature maps, Caet S |n7'), |Cdeal k, deterministically and sample mn [6 + 26) (St - -S)) K (og(8n/88e-- features from [n/]] Cdst if
Σ
8j 5 Sk
83
m
log (2/22)) + m²)
+
5
2
jRCas
j=l
where = [6+ 2c) 5t K log(4n/ 15)e 26) 27, Sv Ejecn. 8, and n. max 1ff
Proof. Let m 2 [66 + 2c) St K log(4n,/00- as in Lemma 2 and note that from Lemma we know that if is our approximation with respect to sampled set of indices, C, we have
P(E) S
where E is the event that the inequality
xf+1(x) 2. ++1 (x) < E2 (2f+((())
Vie in'*1]
holds. Henceforth, will let i E [n] be arbitrary neuron and, similar to before, consider the problem of approximating the neuron's value z f+1 (x) (subsequently denoted by z) by
approximating 2!+ (x) (subsequently denoted by 2).
Similar to our previous analysis of our importance sampling scheme, we let Crand (ci,.... Cml denote the multiset m' neuron indices that are sampled with respect to distribution q and for each j E [m']] define Y, úic, 4c, and let Y = Eye(m Yj. For clarity of exposition, we define 2rand = Y be our approximation with respect to the random sampling procedure, i.e.,
grand
Wijaz =
j.ECoand
Thus, estimator under this scheme is given by
z' = 2 + 2rand
Now we want to analyze the sampling complexity of our new estimator E' so that
P( - 2 22) s 8/2.
Establishing the sampling complexity for sampling with respect to distribution q is almost identical to the proof of Theorem First, note that IE [ x] Edet E [2rand] x] since ådet is a constant (conditioned on a realization x x D). Now note that for any j E [m]]]
[Y, x]
Σ Re(a
m kElnf]/Cau
19

---

Zdet
171
and E [Erand]
x] I8 (Y|
x] ådett
This implies that E [3]] Edet + (z Edet) = and so our estimator remains unbiased. This also yields
Y Y E Y
x] gradd E [erand]
= 1&rand + Edet 2|
2|,
which implies that all we have to to bound the failure probability of the event |z' - 2| 2 ez is to apply Bernstein's inequality to our estimator årand = Y, just as we had done in the proof of The only minor change is the variance and magnitude of the random variables Y2, for k [m') since the distribution is now with respect to q and not p. Proceeding in the proof of
Theorem 2
Lemma 6 we have
úxzj, (x) (x)a;(x) (S Sk) Wijay (x)
m' q3 (S - Sz)C
m' 8j
ml
Now, to bound the magnitude of the random variables note that
Edet
(S Sx
E
Y
x
Σ
Wijas
I
m
m
m
The result above combined with this fact yields for the magnitude of the random variables
(S - Sz)Cz
R' max JE(m)
Y E [Y
x||
<
m'
where we observe that the only relative difference to the bound of Lemma is the term Sk appears, where S = Ejecam Sj, instead of S
Similarly, for the variance of a single Y,
(waak (x))²
Var(Y, x, x,9) <
m²2 9k
kE(no]/Caes
S - Sk
(w))a((x)2
m22
8k
C(S Sx)
wx)a(((
m²²
KE k
C(S 2
min(1,C(5 Sk)
m22
where the last inequality follows by the fact that Eketr wx)a((x) S z and by the sensitivity inequality from the proof of Lemma 7
Wipa (x) S Oz
Σ
sy= C2(S- St).
jEln
This implies by Bernstein's 's inequality and the argument in proof of Theorem 2 that if we sample
m' = [66 + 2x) (S* - S K
-
times from the distribution g, then we have
IP(|E' 2 > EZ) < 8/2.
and of course the sampling complexity is m' instead of
20

---

Now let p (P1.. ..... ,P.) be the probability distribution and let C denote the multi-set of indices sampled from [n|] when m samples are taken from [n]] with respect to distribution p. For each index j E [n]] let Uy (m. p) [ C] be the indicator random variable of the event that index is sampled at least once and let (m, p) = Ei= (,(,,)) p). Note that U a random variable that denotes the number of unique samples that result from the sampling process described above, and its expectation
is given by
E [m,
Σ E EmU,(m,P)) = Σ P(i EC)
=
1=1
P(j is sampled at least once)
(1 P(j is not sampled))
j=1
n (1 pz)
Now we want to establish the condition for which U(m', q) < U(m,p), p), which, if it holds, would imply that the number of distinct weights that we retain with the deterministic sampling ap- proach is lower and still achieves the same error and failure probability guarantees, making it the overall better approach. To apply a strong concentration inequality, let C' Caet U Crand (c...., de 1'+11.... c denote the set of indices sampled from the deterministic + sampling (with distribution q) approach, and let = {ei,.... Cm be the indices of the random samples obtained by sampling from distribution p. Let f(d,,... ..., Snn, CI...., Gm) denote the difference U(m', 9) Umm. p) in the number of unique samples in C' and C. Note that f satisfies the bounded difference inequality with Lipschitz constant since changing the index of any single sample in C C' can change I by at most 1. Moreover, there are m' + m random variables, thus, applying McDiarmid's inequality (van Handel| 2014), we obtain
-2f2 (--2212
([m,)(mp)) - Ummm, q)l (U(m. Umm' .g)) 2 S <exp (-mm+ + ml)
this implies that for L log(2 (2522/8)mnmm''
2
E (m, U'm', 4)) S U(m,)) Umm', +
with probability at least 1 8/2. Thus, this means that if EIU (m, p)] EE [U 9)l > then pmm,p) > U(m',q) .))
More specifically, recall that
E [(U(m, = =n- n- Σ (1-
p3) n2
Σ jml
89 (1
S
jml
and
ElU(m', g)1 = k Σ (1- (1 - (1
j:9, 30
k (n k)
Σ (1 m'
Σ (1
15) ym
= n
14;20
m'
8j
n
S
Sk
jdC
21

---

Lenet 300, 100, MNIST
Lenet 300, 100, MNIST
10
Reference Net
Reference Net Ours (derand)
Ours (derand)
Test Error 1%6
(rand)
Error (%)
Ours (rand)
40
Ours (partial)
Ours (partial)
30
20
10
10
20
30
40
50
60
70
10
15 Retained Parameters (%)
20
25
30
35
40
Retained Parameters (%)
(a) Before retraining
(b) After retraining
Figure The performance of approach on LeNet300-10 100 architecture trained MNIST with no derandomization (denoted by "rand"), with partial derandomization (denoted by "partial"), and with complete derandomization (denoted by "derand"). The plot in (a) and (h) show the resulting test accuracy for various percentage of retained parameters 1 (pruneratio) before and after retraining, respectively. The additional error of the derandomized algorithm can be neglected in practical settings, especially after retraining.
Thus, rearranging terms, we conclude that is better to conduct the deterministic + sampling scheme if
Σ
1 1-
83
m
n j=1
2/ m s
log (2/5)(m m²)
5- Sk
2
@dCdet
Putting all together, and conditioning on the above inequality holding, we have by the union bound
P( - =| 2 e2 UU .) > U (m,,)) p)) < 8,
this implies that with probability at least 5: (i) 3' E (1 + E) and (ii) U(m' .q) < Umm p). implying that the deterministic + sampling approach ensures the error guarantee holds with smaller number of unique samples, leading to better compression.
B.1.1 EXPERIMENTAL EVALUATION OF DERANDOMIZATION
To evaluate our theoretical results of derandomization, we tested the performance of our algorithm with respect to three different variations of sampling:
1. No derandomization ("rand"): We apply Alg. and sample channels with probability proportional to their sensitivity.
2. Partial derandomization ("partial")) We apply Theorem as a preprocessing step to keep the top l channels and then sample from the rest according to Alg. 2
3. Complete derandomization ("derand"): We simply keep the top channels until our sampling budget is exhausted.
The results of our evaluations on LeNet300- 100 architecture trained on MNIST can be seen in Fig. 5 As visible from Fig. ((a), the process of partial derandomization does not impact the performance of our algorithm, while the complete derandomization of our algorithm has a slightly detrimental effect on the performance. This is in accordance to Theorem 8 which predicts that that it is best to only partially derandomize the sampling procedure. However, after we retrain the network, the additional error incurred by the complete derandomization is negligible as shown in Fig. 5(b). Moreover, it appears that especially for extremely low sampling regime- the completely derandomized approach seems incur slight performance boost relative the other approaches. We suspect that simply keeping the top channels may have a positive side effect on the optimization landscape during retraining, which would like further investigate in future research.
22

---

C MAIN COMPRESSION THEOREM
Having established layer-wise approximation guarantees in Sec. B all that remains establish guarantees on the output of the entire network is to carefully propagate the error through the layers as was done in Baykal al. 2019a). For each i [nf [1 and [L]. define
(x) = (x) (+))))))))))
where (x) Exer+ Wik (x) and 2; (x) = Exer wik of (x) are positive and negative components of (x), respectively, with I and I as in Alg. 2 For each f E [4], let A be constant defined as function of the input distribution D 8 such that with high probability over Af. Finally, let A II
D, A 2 max
Generalizing Theorem to obtaín a layer-wise bound and applying error propagation bounds of Baykal et al. 2019a), establish main compression theorem below.
Theorem 3. Let e, ō E (0.1) 1) be arbitrary, let S X denote the set of lo'log (4n/8)1 i.i.d. points drawn from D, and suppose we are given a network with parameters 0 = (W (W?,..., W Consider the set of parameters = (W1 ..... WL generated by pruning channels of 0 according to Alg. 2 for
each l E [L]. Then, @ satisfies aD (fa(x) E (1+t) 2 1 6, and the number of filters in Ô is bounded by O EE La (2 5 log(n/6)
D EXTENSION TO CNNS
To extend our algorithm to CNNs, we need to consider the fact that there is implicit weight sharing involved by definition of the CNN filters. Intuitively speaking, to measure the importance of a feature map (i.e. neuron) in the case of FNNs we consider the maximum impact it has on the preactivation (x). In the contribution of a feature map af (zr, which is now a two-dimensional image instead of a scalar neuron, to the pre-activation 2 (x)) in layer t 1. Thus, adapt our algorithm to prune channels in CNNs, we modify the definition of sensitivity slightly, by also taking the maximum over the patches p P (i.e., sliding windows created by convolutions). In this context, each activation of (a:) also associated with patch E P, which we denote by d'p- In particular, the slight change the following:
of CNNs the same intuition holds, that is want capture the maximum
1+1 w
(x)
max max max #ES vE[g PEP
++1 Exe(pg)
With
a (I)
where a.p corresponds to the activation window associated with patch E P. Everything else remains the same and the proofs are analogous.
E EXPERIMENTAL DETAILS AND ADDITIONAL EVALUATIONS
For our experimental evaluations, we considered a variety of data sets (MNIST, CIFAR-10, 10, ImageNet) and neural network architectures (LeNet, VGG, ResNet, NeteResNet, DenseNet) and compared against several state-of-the-art filter pruning methods. We conducted all experiments on either single NVIDIA RTX 2080Ti with 1 1GB RAM NVIDIA Tesla V100 with 16GB RAM and implemented them in Py PoTcch (Paszke et al. 2017). Retraining with ImageNet was conducted on cluster of 8 NVIDIA Tesla V100 GPUs.
In the following, we summarize our hyperparameters for training and give an overview of the comparison methods. All reported experimental quantities are averaged over three separately trained and pruned networks.
'Ir A (z:) is a Lub-Exxonential random variable (Vershynin, 2016 with parameter À = 0(1), then for failure probability: A A'OEE, z [ (x)) + log(1/8)) (Baykal al. 2019a Vershynin 2016
23

---

E.1 COMPARISON METHODS
We further evaluated the performance of algorithm against variety of state-of-the-art methods in filter pruning as listed below. These methods were re-implemented for our own experiments to ensure an objective comparison method between the methods and we deployed the same iterative pruning and fine-tune strategy as is used in our method. Moreover, we considered a fixed pruning ratio of filters in each layers as none of the competing methods provide an automatic procedure to detect relative layer importance and allocate samples accordingly. Thus, the differentiating factor between the competing methods is their respective pruning step that we elaborate upon below.
Filter Thresholding (FT, ei (0016) Consider the set of filters W [W1.... ...... W in layer oye
l and let ||W:ill,,> denote the untry-wise l- nnomm of W (or Frobenius norm). Consider desired sparsity level of 1%, i.e., we want to keep only 1% the filters. We then simply keep the filters with the largest norm until satisfy our desired level of sparsity.
SoftNet (He et al. 2018)
The pruning procedure of He et al. (2018) is similar in nature to the work L. et al. (201)) except the saliency score used the entrywise & norm || of filter map
WJ. During their fine-tuning scheme they allow pruned filters to become non-zero again and then repeat the pruning procedure. As for the other comparisons, however, we only employ one-shot prune and fine-tune scheme.
ThiNet (Luo al. 2017) Unlike the previous two approaches, which compute the saliency score of the filter W by looking at its entry-wise norm, the method of Luo et al. (2017) iteratively and greedily chooses the feature map (and thus corresponding filter) that incurs the least error in an absolute sense in the pre-activation of the next layer. That is, initially, the method picks filter j such
that j" = argmin max.es (x(+((r)
_++1 (x) where (x+ denotes the pre-activation of f+1 =[G]
layer f+ 1 for some input data point x, LJ] (z) the pre-activation when only considering feature map in layer É, and 8 a set of input data points. We note that this greedy approach is quadratic in both the size ny of layer l and the size S of the set of data points S, thus rendering it very slow in practice. In particular, we only use a S of cardinality comparable our own method, i.e., around 100 data points in total. On the other hand, Luo et al. report to use 100 data points per output class resulting 1000 data points for CIFARIO.
E.2 LENET ARCHITECTURES ON MNIST
We evaluated the performance of our pruning algorithm and the comparison methods on LcNe1300-100 (LeCun et al.) 1998). a fully-connected network with two hidden layers of size 300 and 100 hidden units, respec- tively, and its convolutional coun- terpart, LeNet-5 (LeCun al.) 1998), which consists of two con- volutional layers and two fully- connected layers. Both networks were trained on MNIST using the hyper-parametts Table 3 We trained on a sin- gle GPU and during retraining füne-tunine, we maintained the same hyperparameters and only adapted the ones specifically men- tioned in Table 3
LeNet-300-100
LeNet-5
test error
1.59
0.72
loss
cross-entropy
cross-entropy
optimizer
SGD
SGD
epochs
40
40
Train
batch size
64
64
LR
0.01
0.01
LR decay
0.1@ (30)
0.1 @ (25,
momentum
0.9
0.9
weight decay
1.0c-4
1.0c-4
1.0e-12
1.0e-12
Prune
a
not iterative
1.18
epochs LR decay
30
40
Fine-tune
0.1 @ [20, 28)
0.1 (25, 35)
specified in
We report the hyperparameters used during MNIST training. pruning, and fine-tuning for the LeNet architectures. LR hereby denotes the learning rate and LR decay denotes the learning rate decay that we deploy after a certain number of epochs. During fine-tuning we used the same hyperparameters except for the ones indicated in the lower part of the table.
Table 3:
24

---

E.3 CONVOLUTIONAL NEURAL NETWORKS ON CIFAR-10
We further evaluated the performance of our algorithm on a variety of convolutional neural network architectures trained on CIFAR-IO. 10. Specifically, tested it VGG16 with batch norm (Simonyan & Zisserman 2014), ResNer20 (He et al. 2016). DenseNer22 (Huang et al. 2017). and Wide ResNet- 16-8 (aaoruyko & Komodakis 2016). For residual networks with skip connections, we model the interdependencies between the feature maps and only prune feature map if it does not get used as an input in the subsequent layers. We performed the training on a single GPU using the same hyperparameters specified in the respective papers for CIFAR training. During fine-tuning we kept the number of epochs and also did not adjusted the learning rate schedule. We summarize the set of hyperparameters for the various networks in Table
VGGI6
ResNct20/56/110 10
DenseNet22
WRN-16-8
test error Ioss
7.11
8.59/7.05/6.43
10.07
4.81
cross-entropy
cross-entropy
cross-entropy
cross-entropy
optimizer
SGD
SGD
SGD
SGD
epochs
300
182
300
200
Train
batch size
256
128
64
128
LR
0.05
0.1
0.1
LR decay
0.5 (30,
0.1 @ (91, 136) 0.9
0.1 (150, 225} 0.9
0.2 (60, ...
momentum
0.9
0.9
Nesterov
X
x 1.0e-4
V
weight decay
5,0e-4
1.0e-4
5.0e-4
1.0c-16
1.0c- 16
1.0c- 16
1.0c-16
Prune
1.50
0.50/0.79/0.79
0.40
0,36
Fine-tune
epochs
150
182
300
200
Table We report the hyperparameters used during training, pruning, and fine-tuning for various convolutional architectures on CIFAR- 10. LR hereby denotes the learning rate and LR decay denotes the learning rate decay that we deploy after a certain number of epochs. During fine-tuning we used the same hyperparameters except for the ones indicated in the lower part of the table. (30,...) denotes that the learning rate is decayed every 30 epochs.
E.4 CONVOLUTIONAL NEURAL NETWORKS ON IMAGENET
We consider pruning convolutional neural net- works of varying size ResNet18, ResNet50, and ResNet101 trained on the ImageNet (Rus- sskoossyy et al. 2015) data set. The hyper- parameters used for training and for our pruning algorithm are shown in Table For this dataset, considered two scenarios: (i) iterative prun- ing without retraining and (ii) iterative prune- retrain with limited amount of iterations given the resource-intensivv nature of the experiments.
ResNet 8/50/101
top-1 test top-5 test error loss
30.26/23.8722.663
10.93/7.13/6.4
cross-entropy
optimizer epochs batch size
SGD
90
Train
256
LR
0.1
L.R decay
0. @ (30, 60)
momentum
0.9
Nesterov
X
weight decay
1.0e-4
In the first scenario, evaluate the baseline effectiveness of each pruning algorithm without fine-tuning by applying the same iterative prune- scheme, but without the retraining step. The results of these evaluations can be seen Fig. 66] Fig. @lshows that our algorithm outperforms the competing approaches generating compact, more accurate networks. We suspect that by reevaluating the data-informed filter importance (empirical sensitivity) after each iteration our approach is capable of more precisely capturing the detendeeeydyncy between layers that alter the relative importance of filters and layers with each pruning step. This is in contrast competing approaches, which predominantly rely on weight-based criteria of filter importance, and thus can only capture this inter-dependency after retraining (which subsequently alters the magnitude of the weights).
1.0c-16 16
Prune
0.43/0.50/0.50
Fine-tune
epachs
90
Table 5: The pruning residual networks trained on the ImageNet data set.
used for training and
25

---

resne118, ImageNet
resnet50, ImageNet
resnet101, ImageNet
Reference Net
100
Reference Net
Reference Net
Ours
Ours
80
Test Erorr (56)
80
Ter Lrror (66)
Softhet
Softhet
Emarr
60
SoftNet
60
80
40
20
20
90 Retained Parameters (96)
90
95
85
Retained Parameters (96)
Retained Parameters (56
(a) ResNet18
(b) ResNet50
ResNet101
Figure 6: The results of our evaluations of the algorithms in the prune-only scenario, where the network is iteratively pruned down specified target prune ratio and the fine-tuning step omitted. Note that the axis the percentage of parameters retained, i.e., (1 pruneratio).
Top-1 Err. (%)
Top-5 Err. (%)
Model
Method
PR (%)
FR (%)
Orig.
Pruned
Diff.
Orig.
Pruned
Diff.
Ours (within 4.0% top- 1)
30.26
34.35
+4.09
10.93
13.25
+2.32
60.48
43.12
Ours (within 2.0% top-1)
30.26
32.62
+2.36
10.93
12.09
+1.16
43.80
29.30
Ours (lowest top-1 emr)
30.26
31.34
+1.08
10.93
11.43
+0.50
31.03
19.99
Resnet18
He et al.
2018 (SoftNet)
29.72
32.90
+3.18
10.37
12.22
+1.85
41.80
Hc
2019
29.72
31.59
+1.87
10.37
11.52
+1.15
N/A
41.80
Dong al. 20177
30.02
33.67
+3.65
10.76
13.06
+2.30
N/A
33.30
Ours (within 1.0% top- 1)
23.87
24.79
+0.92
7.13
7.57
+0.45
44.04
30.05
Ours (lowest
top-1 em.)
23.87
24.09
+0.22
7.13
7.19
+0.06
18.01
10.82
He et al.
2018
(SoftNet)
23.85
25.39
+1.54
7.13
7.94
+0.81
N/A
41.80
Luo et al.
2201
(ThiNet)
27.12
27.96
+0.84
8.86
9.33
+0.47
33.72
36.39
Resnet50
Hc ct al.
2019
23.85
25.17
+1.32
7.13
7.68
+0.55
N/A
53.50
He et al.
2017
N/A
N/A
7.80
9.20
+1.40
N/A
50.00
Luo & Wu 2018
23.85
25.24
+1.39
7.85
+0.72
48.70
et
2019a
23.40
24.60
+1.20
N/A
N/A
N/A
N/A
51.22
Ours (within 1.0% top-1)
22.63
23.57
+0.94
6.45
6.89
+0.44
50.45
45.08
Ours (lowest
top-1 emr)
22.63
23.22
+0.59
6.45
6.74
+0.29
33.04
29.38
He et al.
2018
(SoftNet)
22.63
22.49
-0.14
6.44
6.29
-0.15
N/A
42.20
Resnet101
He ct al. 2019
22.63
22.68
+0.05
6.44
6.44
+0.00
N/A
42.20
Ye et al.
2018
23.60
24.73
+1.13
N/A
N/A
N/A
47.20
42.69
Table Comparisons of the performance of various pruning algorithms ResNets trained ImageNet (Rus-
sakovvsyy et al.) (2055). The reported results for competing algorithms were taken directly from the corre- sponding papers. For each network architecture, the hest performing algorithm for each evaluation metric, i.c.,
Pruned Err., Err. Diff, PR, and FR, is shown in bold.
Next, we consider pruning the networks using the standard iterative prune-retrain procedure as before (see Sec. E) with only limited number of iterations (2-3 iterations per reported experiment). The results our evaluations are reported in Table 6 with respect to the following metrics: the resulting error of the pruned network (Pruned Err.), the difference in model classification error (Err. Diff), the percentage of parameters pruned (PR), and the FLOP Reduction (FR). We would like to highlight that despite the limited resources used during the experiments produce compressed networks that are accurate and compact as the models generated by competing approaches (obtained by significantly more prune-retrain iterations than allotted our algorithm).
method able to
E.5 APPLICATION TO REAL-TIME REGRESSION TASKS
In the context of autonomous driving and other real-time applications of neural network inference, fast inference times while maintaining high levels accuracy are paramount to the successful deployment of such systems (Amini et al. 2018). The particular challenge of real-time applications stems from
26

---

the fact that in addition the conventional trade-off between aceuracy and model efficiency inference has to conducted in real-time. In other words, there a hard upper bound on the allotted computation time before answer needs be generated by the model. Model compression, and in particular, filter compression can provide a principled approach to generating high accuracy outputs without incurring high computational cost. Moreover, the provable nature of our approach is particularly favorable for real-time applications, as they usually require extensive performance guarantees before being deployed, e.g., autonomous driving tasks.
To evaluate the empirical performance of our fil- ter pruning method on real-time systems, we implemented and tested the neural network of Amini et al. (2018), which is regression neural network deployed on autonomous ve-
Deepknight
test loss
4.9e-5
loss
MSE
optimizer
Adam
hicle in real time to predict the steering angle of the human driver. We trained the network Amini et al. (018)) denoted by Deepknight, with the driving data set provided alongside, ing the hyperparameters summarized Table
epochs
100
Train
batch size
32
LR
Ie-4
LR decay
0.1 @ (50, 90)
momentum
0.9
weight decay
1.0c-4
The results of our compression be found in Fig. 7 where we evaluated and compared the performance of our algorithm to those of other SOTA methods (see Sec. E.6). We note that these results were achieved without retraining as our experimental evaluations have shown that even without retraining we can achieve signif- icant pruning ratios that lead to computational speed-ups practice. apparent from Fig. 7 we can again outperform other SOTA methods in terms performance vs. prune ratio. Note that since this is regression task, we used test loss (mean-squared error on the test data set) as performance criterion.
Prune
1.0e322
Ox
not iterative
Fine-tune
epochs
0
Table 7: We report the hyperparameters used for training and pruning the driving network of[Amini al. (2018) together with the provided data set. No fine-tuning was conducted for this architecture. LR hereby denotes the learning rate, LR decay denotes the learning rate decay that deploy after certain number of epochs, and MSE denotes the mean mean-squared error.
deepknight, Driving
Reference Net Ours
Test Loss
SoftNet
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Retained Parameters (%)
(a) Example driving image from Amini et al. 2018)
(b) Pruning performance before retraining
Figure 7: The performance of our approach on a regression task used to infer the steering angle for an autonomous driving task (Amini et al. [2018). (a) An exemplary image taken from the data set. (b) The performance of our pruning procedure before retraining evaluated the test loss and compared competing filter pruning methods. Note that æ axis is percentage of parameters retained, i.e. (pruneratio).
Finally, we would like to highlight that our filter pruning method may serve principled subpro- cedure during the design neural network architectures for real-time applications. In particular, given inference time budget T, one can design and train much larger architectures with favorable performance which, however, violate the given budget T. Our filter pruning method can then be leveraged to compress the network until the given budget T is satisfied, thus reducing the burden the practitioner to design a simultancously accurate and computationally--ffici neural network architecture.
27

---

E.6 COMPARISONS ADDITIONAL METHODS ON CIFAR-10
We evaluate the performance of our algorithm on pruning modern convolutional and residual bench- mark network architectures ResNet20, ResNet56, ResNetl 10, and VGG16 trained CIFAR-10 and compare it to the results reported by state-of-the-art filter pruning approaches. The results are obtained by iteratively pruning and fine-tuning the resulting model (starting from the original pre-trained network) in a hyperharmonic sequence of prune ratios as described in Sec. 4.1 For our algorithm, in addition reporting the pruned model that achieves commensurate accuracy ("within 0.5% err.") as in Sec. 4 we report the model that (i) closest matches the accuracy of the original network ("orig. err.") and (ii) achieves the lowest classífication error possible ("lowest err.") which for nearly all of the models considered, is lower than that of the original model.
Table summmariee our results and depicts the performance of each pruning algorithm with respect to various metries: the resulting error of the pruned network (Pruned Err.), the difference in model classification eπror (Err. Diff), the pereentage of parameters pruned (PR), and the FLOP Reduction (FR). Our results show that our algorithm outperforms competing approaches in virtually all of the considered models and pertinent metrics, especially when the overall quality of the pruned model is taken into account.
For ResNet20 for instance, our algorithm generates a model that is simultaneously the sparsest (>43% PR) and the most accurate (8.64% Err., 0.04% Err. Diff) despite starting from pre-trained model with the highest error of 8.60% (Orig. Err.) among the reported results. The method of He et al. (2019) does achieve higher FR than our method, however, this is achieved at the cost of nearly 2% degradation in classification accuracy (compared to 0.04% for ours).
For larger networks such ResNetl 10, our algorithm's favorable performance is even more pro- nounced: the models generated by our algorithm are not only the sparsest (PR) and most efficient (PR), but they are also the most accurate. nearly identical trend holds for the results pertaining to VGGI6 and ResNet56: the models generated by our method tend to be the overall sparsest and most accurate, even when starting from pre-trained models with higher classification error.
28

---

Model
Method
Orig. Err. (%)
Pruned Err. (%)
Err. Diff. (%)
PR (%)
FR (9)
Ours (within 0.5% err))
8.60
9.09
+0.49
62.67
45.46
Ours (orig. err.)
8.60
8.64
43.16
32.10
Ours (lowest eTT.
8.60
8.64
+0.04
43.16
32.10
ResNet20
He al.
2018
(SoftNet)
7.80
8.80
+1.00
N/A
29.30
He al.
2019
7.80
9.56
+1.76
N/A
54.00
Ye et al.
2018
8.00
9.10
+1.10
37.22
N/A
Lin ct al.
(2020)
7.52
9.72
42,20
40,00
N/A
Ours (within 0.5% err.)
7.05
7.33
+0,28
88.98
84,42
Ours (orig. err.)
7.05
7.02
-0.03
86.00
80.76
Ours (lowest eTT.
7.05
6.36
-0.69
72.10
67.41
et
2016
(FT)
6.96
6.94
-0.02
27.60
ResNet56
Me et al.
2018
(SoftNet)
6.41
6.65
+0.24
N/A
52.60
He al.
2019
6.41
6.51
+0.10
N/A
52.60
He et al.
2017
7.20
8.20
+1.00
N/A
50.00
Li ct al.
2019)
6.28
6.60
+0.32
78.10
50.00
Lin et al.
(2020)
5.49
5.97
+0.48
40.00
N/A
Ours (within 0.5% err.)
6.43
6.79
+0,36
92.07
89.76
Ours (orig. err.
6.43
6.35
-0.08
89.15
86.97
Ours (lowest em:)
6.43
5.42
71.98
ResNet110
et
2016) (FT)
6.47
6.70
+0.23
32.40
38.60
He al.
2018
(SoftNet)
6.32
6.14
-0.18
N/A
40.80
He ct al.
2019
6.32
6.16
-0.16
N/A
52.30
Dong al.
(0177)
6,37
6.56
+0.19
N/A
34.21
Ours (within 0.5% err.)
7.28
7.78
+0,50
94.32
85.03
Ours (orig. err.)
7.28
7.17
-0.11
87.06
70.32
Ours (lowest emr.)
7.28
7.06
-0.22
80.02
59.21
VGG16
el. 2016) (FT)
6.75
6.60
64.00
34.20
Huang 2018
7.23
7.83
+0.60
83.30
45.00
He et al.
2019
6.42
6.77
+0.35
N/A
35,90
Li 2019
5.98
6.18
+0.20
78.20
76.50
Table The performance of our algorithm and that state-of-the art filter pruning algorithms on modern CNN architectures trained on CIFAR- 10. The reported results for the competing algorithms were taken directly from the corresponding papers. For each network architecture, the best performing algorithm for each evaluation metric, i.c., Pruned Er.. Err. Diff, PR, and FR, is shown in bold. The results show that our algorithm consistently outperforms state-of-the-art pruning approaches in nearly all of the relevant pruning metrics.
29


Reviews:
[{"review_id": "S1e1rr3e9S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper attacks the problem of pruning neural networks to obtain sparser models for deployment. In introduces a principled importance sampling approach for which independence of samples allows one to obtain bounds easily. These bounds can be used to control the accuracy of the method. \n\nThe proposal mechanism is very smart. The authors use a measure of the sensitivity of the network outputs to the channels in a particular layer (eqn 1).\n\nThe paper is very well written, but it would help to add a picture where all the symbols in section 2.1 appear. At times it is hard to keep track of the channels and features. It might alternatively be a good idea to specify the equation of a layer (eg what eventually ends up happening at the bottom of page 3) in section 2.1 and then explain the symbols in the equation. This will make life easier for anyone reading the paper for the first time.  \n\nThe experiments are well execute and include reasonable baselines. I would in addition recommend this recent paper:\nhttps://arxiv.org/abs/1902.09574  \n\nIt would also be nice to relate the work to this best paper this year.\nhttps://openreview.net/forum?id=rJl-b3RcF7", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gqAUOxqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the tasks of pruning filters, a provable, sampling-based approach for generating compact Convolutional Neural Networks (CNNs). This paper gives rise to a fully-automated procedure for identifying and preserving the filters in layers that are essential to the network’s performance.  In general, this paper is very well written and organized.\n\n1, The key concerns come from the Lottery papers [1,2]. One can find sparse structure from an overparameterized model.  The results of pruned network should be improved, rather than getting worse, since some redundant filters/params are removed from original network. In contrast, all the results of this method gets worse results; this is less desirable.\n\n2, the theoretical analysis is very good;  it is worthy publishing themselves. But ever since the \"lottery\" papers, I think it makes sense in locating the sparse and representative pruned structure, which can achieve better performance than full overparameterized model. \nso it’s quite a borderline paper.  \n\n\n[1] THE LOTTERY TICKET HYPOTHESIS: FINDING SPARSE, TRAINABLE NEURAL NETWORKS. ICLR 2019.\n[2] RETHINKING THE VALUE OF NETWORK PRUNING. ICLR 2019.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1ehHpGjqS", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n \nIn this paper, the author propose a provable pruning method, and also provide a bound for the final pruning error.  Among most heuristics prune method,  pruning with mathematics guarantee is indeed more convincing. We expect this work can help people devoting some effort into more solid theoretical study in understanding the over-parameterized training.\n\nIntuitively speaking, the sensitive neuron has greater contribution for the final output, reusing the corresponding filter and carefully rescale its value require many empirically attempts. To achieve a more reasonable algorithm, author prune the redundant channel by controlling the deviation of the summation statistically small,  and reusing the filter by important sampling the given channel. Experiment show that this method can reach a competitive prune radio against other pruning algorithm, and show robustly in retained parameters vs error experiment.\n\n\nWeakness:\n\n1. experiment is too weak\n\nImageNet model has great impact on most CV problem, and the current release models are flooding in the open source world. Author should at least provide a imagenet model and make this work more convincing. Besides, Author should also consider an experiment in modern lightweight network, vgg and resnet like model are out of fashion and so big that any one can make a sound result on it. \n\n2. lack of a comparing experiment for random select the top-k norm. \n\nImportant sampling require an input of probability [p1, p2, p3, ... pn],  if those probabilities are nearly uniform, important sampling will behave like a random sampling method. In most case, if we want to prune the large channel network,  picking the top-1 significant filter or random sampling top-k filter will almost do the same thing.  \n\n3. lack of further theory consideration\n\nauthor only consider the single layer reconstruction, without discussing the overall accumulative error. Unlike the other deterministic method, sampling skill suffer variance propagation problem, the pre-layer variance will affect the sampling probability of next layer, how this pruning work if we change status of the pre-layer,  I didn't find any theoretical guarantee and only find a proof of single layer reconstruction bound.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a sampling-based approach for generating compact CNNs by pruning redundant filters. One advantage of the proposed method is a bound for the final pruning error.

One of the major concerns during review is the experiment design. The original paper lacks the results on real work dataset like ImageNet. Furthermore, the presentation is a little misleading. The authors addressed most of these problems in the revision.

Model compression and purring is a very important field for real world application, hence I choose to accept the paper.

Decision: Accept (Poster)