Title: PROVABLE FILTER PRUNING FOR EFFICIENT 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. * These authors contributed equally to this work. 1 We refer the reader to Sec. A of the appendix for additional details about the related work. … … Data batch Compute filter sensitivity in each layer Prune filters and output compressed net Filter sensitivity s j from feature map importance Sample filter j with probability p j ∼ s j Per-Layer Filter Pruning 0.00 0.

1. 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-limited platforms. A popular approach to alleviate these practical concerns is to utilize a pruning algorithm to remove redundant parameters from the original, over-parameterized network. The objective of network pruning is to generate a sparse, efficient model that achieves minimal loss in predictive power relative to that of the original network.

A common practice to obtain small, efficient network architectures is to train an over-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 is 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 on the effectiveness of the pruning algorithm used in identifying and preserving the essential structures of the original network. To this end, a diverse set of smart pruning strategies have been proposed in order to generate compact, accurate neural network models in a computationally efficient way.

However, modern pruning approaches 1 are generally based on heuristics (Han et al., 2015; Ullrich et al., 2017; He et al., 2018; Luo et al., 2017; Li et al., 2016; Lee et al., 2019; Yu et al., 2017a ) that lack guarantees on the size and performance of the pruned network, require cumbersome ablation studies (Li et al., 2016; He et al., 2018) or manual hyper-parameter tuning (Luo et al., 2017) , or : Overview of our pruning method. We use a small batch of data points to quantify the relative importance s j of each filter W j in layer by considering the importance of the corresponding feature map a j = φ(z j ) in computing the output z +1 of layer + 1, where φ(•) is the non-linear activation function. We then prune filters by sampling each filter j with probability proportional to s j 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 prune-retrain cycle iteratively.

heavily rely on assumptions such that parameters with large weight magnitudes are more importantwhich does not hold in general (Ye et al., 2018; Li et al., 2016; Yu et al., 2017a; 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 in the network's accuracy (see Fig. 1 for an overview). At the heart of our method lies a novel definition of filter importance, i.e., 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, we 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 an 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 vice-versa. Hence, we obtain and introduce a fully-automated sample size allocation procedure for properly identifying and preserving critical network structures as a 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 a 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 in accuracy when compared to those generated by state-of-the-art filter pruning approaches.2 

2. SAMPLING-BASED FILTER PRUNING:

In this section, we introduce the network pruning problem and outline our sampling-based filter pruning procedure and its theoretical properties. We extend the notion of empirical sensitivity (Baykal et al., 2019a) to quantify the importance of each filter using a small set of input points. We show that our importance criterion enables us to construct a low-variance importance sampling distribution over the filters in each layer. We conclude by showing that our approach can eliminate a large fraction of filters while ensuring that the output of each layer is approximately preserved.

2.1. PRELIMINARIES:

Consider a trained L layer network with parameters θ = (W 1 , . . . , W L ), where W denotes the 4-dimensional tensor in layer ∈ [L], W j filter j ∈ [η ], and η the number of filters in layer . Moreover, let W +1 :j be channel j of tensor W +1 that corresponds to filter W j . We let X ⊂ R d and Y ⊂ R k denote the input and output space, respectively. The marginal distribution over the input space is given by D. For an input x ∈ X to the network, we let z (x) and a (x) = φ(z (x)) denote the pre-activation and activation of layer , where φ is the activation function (applied entry-wise). The j th feature map of layer is given by a j (x) = φ(z j (x)) (see Fig. 1 ). For a given input x ∈ X , the output of the neural network with parameters θ is given by f θ (x).

Our overarching goal is to prune filters from each layer ∈ [L] by random sampling to generate a compact reparameterization of θ, θ = ( Ŵ 1 , . . . , Ŵ L ), where the number of filters in the pruned weight tensor Ŵ is a small fraction of the number of filters in the original (uncompressed) tensor W . Let size(θ) denote the total number of parameters in the network, i.e., the sum of the number of weights over each W ∈ (W 1 , . . . , W L ).

Pruning Objective For a given ε, δ ∈ (0, 1), our objective is to generate a compressed network with parameters θ such that size( θ) size(θ) and P x∼D, θ (f θ (x) ∈ (1 ± ε)f θ (x)) ≥ 1 -δ, where f θ (x) ∈ (1 ± ε)f θ (x) denotes an entry-wise guarantee over the output neurons f θ (x), f θ (x) ∈ Y.

2.2. SAMPLING-BASED PRUNING:

Algorithm 1 PRUNECHANNELS(W +1 , ε, δ, s )

Input: W +1 = [W +1

:1 , . . . , W +1 :η ]: original channels; ε: relative error; δ: failure probability; s : feature map sensitivities as in (1) Output: Ŵ +1 : pruned channels 1: S ← j∈[η ] s j {where s j is as in (1)} 2:

p j ← s j/S ∀j ∈ [η ] 3: m ← (6 + 2ε) S K log(4η * /δ)ε -2 4: Ŵ +1 ← [0, . . . , 0] {same dimensions as W +1 } 5: for k ∈ [m ] do 6: c(k) ← random draw from p = (p 1 , . . . , p η ) 7: Ŵ +1 :c(k) ← Ŵ +1 :c(k) + W +1 :c(k)/m p c(k) 8: end for 9: return Ŵ +1 = [ Ŵ +1 :1 , . . . , Ŵ +1 :η ];

Our sampling-based filter pruning algorithm for an arbitrary layer ∈ [L] is depicted as Alg. 1. The sampling procedure takes as input the set of η channels in layer + 1 that constitute the weight tensor W +1 , i.e., W +1 = [W +1 :1 , . . . , W +1 :η ] as well as the desired relative error and failure probability, ε, δ ∈ (0, 1), respectively. In Line 2 we construct the importance sampling distribution over the feature maps corresponding to the channels by leveraging the empirical sensitivity of each feature map j ∈ [η ] as defined in (1) and explained in detail in the following subsections. Note that we initially prune channels from W +1 , but as we prune channels from W +1 we can simultaneously prune the corresponding filters in W .

We subsequently set the sample complexity m as a function of the given error (ε) and failure probability (δ) parameters in order to ensure that, after the pruning (i.e., sampling) procedure, the approximate output -with respect to the sampled channels Ŵ +1 -of the layer will approximate the true output of the layer -with respect to the original tensor -up to a multiplicative factor of (1 ± ε), with probability at least 1 -δ. Intuitively, more samples are required to achieve a low specified error ε with low failure probability δ, and vice-versa. We then proceed to sample m l times with replacement according to distribution p ( Lines 5-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 output (see below). The unsampled channels in W +1 -and the corresponding filters in W -are subsequently discarded, leading to a reduction in the layer's size.

2.3. A TIGHTLY-CONCENTRATED ESTIMATOR:

We now turn our attention to analyzing the influence of the sampled channels Ŵ +1 (as in Alg. 1) on layer + 1. For ease of presentation, we will henceforth assume that the layer is linear 3 and will omit explicit references to the input x whenever appropriate. Note that the true pre-activation of layer + 1 is given by z +1 = W +1 a , and the approximate pre-activation with respect to Ŵ +1 is given by ẑ +1 = Ŵ +1 a . By construction of Ŵ +1 in Alg. 1, we equivalently have for each entry i ∈

[η +1 ] ẑ +1 i = 1 m m k=1 Y ik , where Y ik = W +1 ic(k) a c(k) p c(k) , c(k) ∼ p ∀k.

By reweighing our samples, we obtain an unbiased estimator for each entry i of the true pre-activation output, i.e., E [ẑ

+1 i ] = z +1 i

-which follows by the linearity of expectation and the fact that

E [Y ik ] = z +1 i for each k ∈ [m]

-, and so we have for the entire vector E Ŵ +1 [ẑ +1 ] = z +1 . So far, we have shown that in expectation, our channel sampling procedure incurs zero error owing to its unbiasedness. However, our objective is to obtain a high probability bound on the entry-wise deviation ẑ +1 i -z +1 i for each entry i, which implies that we have to show that our estimator ẑ +1 i is highly concentrated around its mean z +1 i . To do so, we leverage the following standard result. Theorem 1 (Bernstein's inequality (Vershynin, 2016) 

). Let Y 1 , . . . , Y m be a sequence of m i.i.d. random variables satisfying max k∈[m] |Y k -E [Y k ]| ≤ R, and let Y = m k=1 Y k denote their sum.

Then, for every ε ≥ 0, δ ∈ (0, 1), we have that

P (| Y /m -E [Y k ]| ≥ ε E [Y k ]) ≤ δ for m ≥ log(2/δ) (εE[Y k ]) 2 Var(Y k ) + 2 3 ε E [Y k ]R . Letting i ∈ [η +1

] be arbitrary and applying Theorem 1 to the mean of the random variables

(Y ik ) k∈[m] , i.e., to ẑ +1 i

, 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 (Y ik ) k . By definition of Y ik , observe that these expressions are explicit functions of the sampling distribution p . Thus, to minimize4 the number of samples required to achieve high concentration we require a judiciously defined sampling distribution that simultaneously minimizes both R i and Var(Y ik ). For example, the naive approach of uniform sampling, i.e., p j = 1 /η for each j ∈ [η ] also leads to an unbiased estimator, however, for uniform sampling we have

Var(Y ik ) ≈ η E [Y ik ] 2 and R i ≈ η max k (w +1

ik a k ) and so Var(Y ik ), R ∈ Ω(η ) in the general case, leading to a linear sampling complexity m ∈ Ω(η ) by Theorem 1.

2.4. EMPIRICAL SENSITIVITY (ES):

To obtain a better sampling distribution, we extend the notion of Empirical Sensitivity (ES) introduced by Baykal et al. (2019a) to prune channels. Specifically, for W +1 ≥ 0 (the generalization can be found in Appendix B) we let the sensitivity s j of feature map j in be defined as

EQUATION

)

where S is a set of t independent and identically (i.i.d.) points drawn from D. Intuitively, the sensitivity of feature map j ∈ [η ] is the maximum (over i ∈ [η +1 ]) relative impact that feature map j had on any pre-activation in the next layer z +1 i . We then define the probability of sampling each channel as in Alg. 1: j ∈ [η ] as p j = s j /S , where S = j s j is the sum of sensitivities. Under a mild assumption on the distribution -that is satisfied by a wide class of distributions, such as the Uniform, Gaussian, Exponential, among others -of activations (Asm. 1 in Sec. B of the supplementary), ES enables us to leverage the inherent stochasticity in the draw x ∼ D and establish (see Lemmas 5, 6, and 7 in Sec. B) that with high probability (over the randomness in S and x) that

Var(Y ik ) ∈ Θ(S E [Y ik ] 2 ) and R ∈ Θ(S E [Y ik ]) ∀i ∈ [η +1 ]

and that the sampling complexity is given by m ∈ Θ(S log(2/δ) ε -2 ) by Theorem 1.

We note that ES does not require knowledge of the data distribution D and is easy to compute in practice by randomly drawing a small set of input points S from the validation set and passing the points in S through the network. This stands in contrast with the sensitivity framework used in state-of-the-art coresets constructions (Braverman et al., 2016; Bachem et al., 2017) , where the sensitivity is defined to be with respect to the supremum over all x ∈ supp(D) in (1) instead of a maximum over x ∈ S. As also noted by Baykal et al. (2019a) , ES inherently considers data points that are likely to be drawn from the distribution D in practice, leading to a 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 Ŵ +1 (corresponding to pruned filters in W ) generated by Alg. 1 is such that the output of layer + 1 is well-approximated for each entry. Theorem 2. Let ε, δ ∈ (0, 1), ∈ [L], and let S be a set of Θ(log (η * /δ)) i.i.d. samples drawn from D. Then, Ŵ +1 contains at most O(S log(η * /δ)ε -2 )) channels and for x ∼ D, with probability at least 1 -δ, we have ẑ +1 ∈ (1 ± ε)z +1 (entry-wise), where η * = max ∈[L] η .

Theorem 2 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 to obtain a guarantee on the final output of the compressed network.

In particular, applying the error propagation bounds of Baykal et al. (2019a) , we establish our main compression theorem below. The proofs and additional details can be found in the appendix (Sec. B). Theorem 3. Let ε, δ ∈ (0, 1) be arbitrary, let S ⊂ X denote the set of K log (4η/δ) i.i.d. points drawn from D, and suppose we are given a network with parameters θ = (W 1 , . . . , W L ). Consider the set of parameters θ = ( Ŵ 1 , . . . , Ŵ L ) generated by pruning channels of θ according to Alg. 2 for each ∈

[L]. Then, θ satisfies P θ, x∼D f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 -δ, and the number of filters in θ is bounded by O L =1 L 2 (∆ → ) 2 S log(η/δ) ε 2

. Figure 2 : Early layers of VGG are relatively harder to approximate due to their large spatial dimensions as shown in (a). Our error bounds naturally bridge layer compressibility and importance and enable us to automatically allocate relatively more samples to early layers and less to latter layers as shown in (b). The final layer -due to its immediate influence on the output -is also automatically assigned a large portion of the sampling budget.

3. RELATIVE LAYER IMPORTANCE:

In the previous sections, we established the sampling complexity of our filter pruning scheme for any user-specified ε and δ. 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, a practical question that arises is how to optimally ration the sampling budget across the network's layers to minimize the error of the pruned model. A naive approach would be to uniformly allocate the sampling budget N so 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, as exemplified by Fig. 2(a) .

It 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 importance of each layer: if a layer is not very important, i.e., it does not heavily influence output of the network, then we expect it to be highly compressible, and vice-versa. This intuition is precisely captured by our sampling complexity bounds that quantify the difficulty of a layer's compressibility.

We leverage this insight to formulate a simple binary search procedure for judiciously allocating the sampling budget N as follows. Let δ ∈ (0, 1) be user-specified, pick a random ε > 0, and compute the sampling complexity m as in Alg. 1 together with the resulting layer size n . If n = N , we are done, otherwise, continue searching for an appropriate ε on a smaller interval depending on whether n is greater or less than N . The allocation generated by this procedure (see Fig. 2 (b) for an example) ensures that the maximum layer-wise error incurred by pruning is at most ε.

4. RESULTS:

In this section, we evaluate and compare our algorithm's performance to that of state-of-the-art 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 network5 , required no manual tuning of its hyperparameters, and performed consistently well across a 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 ran alongside our algorithm: Filter Thresholding (FT, Li et al. (2016) ), SoftNet (He et al., 2018) , and ThiNet (Luo et al., 2017) . 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-theart (Gale et al., 2019; Pitas et al., 2019; Yu et al., 2018 ) (see Sec. E.1 of the appendix for details of the compared methods). Additional comparisons to other state-of-the-art 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 δ ∈ (0, 1), since the number of samples in each layer is automatically assigned by our allocation procedure described in Sec. 3. 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 a specified number of 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 a hyperharmonic sequence where the i th PR is determined by 1 -1 /(i+1) α , where α is an experiment-dependent 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 test accuracy is within 0.5% of the original model. The quantities reported are averaged over 3 trained models for each scenario, unless stated otherwise. The full details of our experimental setup and the hyper-parameters used can be found in the appendix (Sec. E).

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 its 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 hyper-parameters specified in Sec. E. Table 1 depicts the performance of each pruning algorithm in attaining the sparsest possible network that achieves commensurate accuracy for the LeNet architectures. In both scenarios, our algorithm generates significantly sparser networks 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 ≈ 90%, which is even competitive with the accuracy of the sparse models generated by state-of-the-art weight pruning algorithms (Lee et al., 2019) 6 . In addition to evaluating the sparsity of the generated models subject to the commensurate accuracy constraint, we also investigated the performance of the pruning algorithms for extreme (i.e., around 5%) pruning ratios (see Fig. 3(a) ). We see that our algorithm's performance relative to those of competing algorithms is strictly better for a wide range of target prune ratios.

For LeNet-5 Fig. 3 (a) shows that our algorithm's favorable performance is even more pronounced at extreme sparsity levels (at ≈ 95% prune ratio).

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 (Simonyan & Zisserman, 2015), ResNet20, ResNet56, ResNet110 (He et al., 2016) , DenseNet22 (Huang et al., 2017), and WideResNet16-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 are summarized in Table 2 and Figure 3 . Similar to the results reported in Table 1 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 to 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. 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 or exceed the predictive accuracy of the original uncompressed network. In addition, Table 8 (see Appendix E.6 for more details) provides further comparisons to state-of-the-art Figure 3 : The accuracy of the generated pruned models for the evaluated pruning schemes for various target prune ratios. Note that the x axis is the percentage of parameters retained, i.e., (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 8 reaffirm that our algorithm can consistently generate simultaneously 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. 3 , and Table 8 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 pruning without retraining and (ii) iterative prune-retrain with a limited amount of iterations given the resource-intensive 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 to larger data sets without the need of manual hyperparameter 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 tasks and real-time systems, we evaluated the various pruning approaches on the DeepKnight network (Amini et al., 2018) , a regression network deployed on an autonomous vehicle in real time to predict the steering angle of the human driver (see E.5 in appendix for experimental details).

Fig. 4 depicts the results of our evaluations and comparisons on the DeepKnight network without the fine-tuning step. We omitted the iterative fine-tuning step for this scenario 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 performance of solely the core pruning procedure. Similar to 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.

4.6. DISCUSSION:

In addition to the favorable empirical results of our algorithm, our approach exhibits various advantages over competing methods that manifest themselves in our empirical evaluations. For one, our algorithm does not require any additional hyper-parameters other than the pruning ratio and the desired failure probability. Given these sole two parameters, our approach automatically allocates the number of filters to sample for each layer. This alleviates the need to 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 in each layer (Li et al., 2016) , which fails to consider the non-uniform influence of each layer on the network's output (see Sec. 3). Moreover, our algorithm is simple-to-implement and computationally efficient both in theory and practice: the computational complexity is dominated by the |S| forward passes required to compute the sensitivities (|S| ≤ 256 in practical settings) and in practice, our algorithm takes on the order of a minute to prune the network.

5. CONCLUSION:

We presented -to the best of our knowledge -the first filter pruning algorithm that generates a 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-parameter tuning necessary. This stands in contrast to existing filter pruning approaches that are generally data-oblivious, rely on heuristics for evaluating the parameter importance, or require tedious hyper-parameter tuning. Our empirical evaluations on popular network architectures and 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-art 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 

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 a rich body of work in network pruning and compression. These approaches range from those inspired by classical tensor decompositions (Yu et al., 2017b; Jaderberg et 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., 2009; Shi et al., 2009) that compress a pre-trained network, to those approaches that enable sparsity by embedding sparsity as an objective directly in the training process (Ioannou et al., 2015; Alvarez & Salzmann, 2017) or exploit tensor structure to induce sparsity (Choromanska et al., 2016; Zhao et al., 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 a saliency score, e.g., its magnitude (Han et al., 2015) , and subsequently inducing sparsity by deterministically removing those weights below a certain saliency score threshold (Guo et al., 2016; Han et al., 2015; Lee et 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-prune-retrain cycles and tedious hyper-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 in CNNs is 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-based approaches, approaches in this domain assign an importance score to each neuron or filter and remove those with a score below a certain threshold (He et al., 2018; Li et al., 2016; Yu et al., 2017a) . These approaches generally take the p norm -with p = {1, 2} as popular choices-of the filters to assign filter importance and subsequently prune unimportant filers. These methods are data-oblivious heuristics that heavily rely on the assumption that filters with large weight magnitudes are more important, which may not hold in general (Ye 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 is most similar to that of (Baykal et al., 2019a; 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-connected networks, and the lack of inference-time acceleration due to non-structured sparsity caused by removing individual weights. Our method is also sampling-based and relies on a data-informed notion of importance, however, unlike (Baykal et al., 2019a; 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.e., 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 θ is the full parameter set of the net, where W ∈ R η ×η +1 is the weight matrix between layers -1 and and . W k refers to the k th neuron of W .

Algorithm 2 PRUNECHANNELS(θ, , S, ε, δ) -extended version Input: θ: trained net; ∈ [L]: layer; S ⊂ supp(D): sample of inputs; ε ∈ (0, 1): accuracy; δ ∈ (0, 1): failure probability Output: Ŵ : filter-reduced weight tensor for layer ; Ŵ +1 : channel reduced, weight tensor for layer + 1 1:

for j ∈ [η ] do 2: for i ∈ [η +1

] and x ∈ S do 3:

I + ← {j ∈ [η ] : w +1 ij a j (x) ≥ 0} 4: I -← [η ] \ I + 5: g +1 ij (x) ← max I∈{I + ,I -} w +1 ij a j (x) k∈I w +1 ik a k (x)

6: end for 7:

s j ← maxx∈S max i∈[η +1 ] g +1 ij (

x) 8: end for 9: S ← j∈[η ] s j 10: for j ∈ [η ] do 11: p j ← s j /S 12: end for 13: K ← value from Assumption 1 14: m ← (6 + 2ε) S K log(2 η +1 /δ)ε -2 15: H ← distribution on [η ] assigning probability p j to index j 16: Ŵ ← (0, . . . , 0) {same dimensions as W } 17: Ŵ +1 ← (0, . . . , 0) {same dimensions as Recall that z +1 i (x) denotes the pre-activation of the i th neuron in layer + 1 given input x, and the activation a j (x) = max{0, z j (x)}.

W +1 } 18: for k ∈ [m] do 19: c(k) ← random draw from H 20: Ŵ c(k) ← W c(k) {no

Definition 1 (Edge Sensitivity (Baykal et al., 2019a) ). Fixing a layer ∈

[L], let w +1 ij be the weight of edge (j, i) ∈ [η ] × [η +1 ].

The empirical sensitivity of weight entry w +1 ij with respect to input x ∈ X is defined to be

EQUATION

where

I + = {j ∈ [η ] : w +1 ij a j (x) ≥ 0} and I -= [η ] \ I + denote

the set of positive and negative edges, respectively.

Algorithm 2 uses empirical sensitivity to compute the sensitivity of neurons on Lines 9-12. Definition 2 (Neuron Sensitivity). The sensitivity of a neuron j ∈ [η ] in layer is defined as

EQUATION

In this section, we prove that Algorithm 2 yields a good approximation of the original net. We begin with a 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 ∈ [η ], the CDF of the random variable max

i∈[η +1 ] g +1 ij (x) for x ∼ D, denoted by F j (•), satisfies F j ( Mj /K) ≤ exp (-1 /K ) , where M j = min{y ∈ [0, 1] : F j (y) = 1}.

Note that the analysis is carried out for the positive and negative elements of W +1 separately, which is also considered in the definition of sensitivity (Def. 1). For ease of exposition, we will thus assume that throughout the section W +1 ≥ 0 (element-wise), i.e., I + = [η ], and derive the results for this case. However, we note that we could equivalently assume W +1 ≤ 0 and the analysis would hold regardless. By considering both the positive and negative parts of W +1 in Def. 1 we can carry out the analysis for weight tensors with positive and negative elements. Theorem 2. Let ε, δ ∈ (0, 1), ∈ [L], and let S be a set of Θ(log (η * /δ)) i.i.d. samples drawn from D. Then, Ŵ +1 contains at most O(S log(η * /δ)ε -2 )) channels and for x ∼ D, with probability at least 1 -δ, we have ẑ +1 ∈ (1 ± ε)z +1 (entry-wise), where η * = max ∈[L] η .

The remainder of this section builds towards proving Theorem 2. We begin by fixing a layer ∈ [L] and neuron i ∈

[η +1 ]. Consider the random variables {Y k } k∈[m] where Y k (x) = 1 mpj w +1 ij a j (x) where Algorithm 2 selected index j ∈ [η ] on the k th iteration of Line 19. Note that z +1 i (x) = j∈[η ] w +1 ij a j (x)

and so we may also write

g +1 ij (x) = w +1 ij a j (x)/z +1 i (x) when it is more convenient. Lemma 4. For each x ∈ X and k ∈ [m], E [Y k (x)] = z +1 i (x)/m.

Proof. Y j is drawn from distribution H defined on Line 15, so we compute the expectation directly.

E [Y j (x)] = k∈[η ] w +1 ik a k (x) m p k • p k = 1 m k∈[η ] w +1 ik a k (x) = z +1 i (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 a 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 a random input point x ∼ D, let G denote the event that the following inequality holds (for all neurons):

max i∈[η +1 ] g +1 ij (x) ≤ C s j ∀j ∈ [η ]

where C = max{3K, 1} and K is defined as in Assumption 1. We now prove that under Assumption 1, event G occurs with high probability. From now on, to ease notation, we will drop certain superscripts/subscripts with the meaning is clear. For example, z(x) will refer to z +1 i (x).

Lemma 5. If Assumption 1 holds, P(G) > 1 -δ/2η . Here the probability is over the randomness of drawing x ∼ D.

Proof. Since max i∈[η +1 ] g ij (x) is just a function of the random variable x ∼ D, for any j ∈ [η ] we can let D be a distribution over max i∈[η +1 ] g ij (x) and observe that since s j = max x∈S max i∈[η +1 ] g ij (x), the negation of event G for a single neuron j ∈ [η ] can be expressed as the event

X > C max k∈[|S|] X k ,

where X ∼ D and X 1 , . . . , X |S| i.i.d.

∼ D since the points in S were drawn i.i.d. from D. Invoking Lemma 8 from Baykal et al. (2019a) in conjunction with Assumption 1, we obtain for any arbitrary j

P( max i∈[η +1 ] g ij (x) > C s j ) = P(X > C max k∈[|S|] X k ) ≤ exp(-|S|/K )

with the K from Assumption 1. Since our choice of neuron j was arbitrary, the inequality above holds for all neurons, therefore we can apply the union bound to obtain:

P x∼D (G) = 1 -P(∃j ∈ [η ] : max i∈[η +1 ] g ij (x) > C s j ) ≥ 1 - j∈[η ] P( max i∈[η +1 ] g ij (x) > C s j ) ≥ 1 -η exp(-|S|/K ) ≥ 1 - δ 2η +1

where the last line follows from the fact that |S| ≥ K log 2 η η +1 /δ . Lemma 6. For any x such that event G occurs, then

|Y k (x) -E [Y k (x)]| ≤ CSz/m.

Here the expectation is over the randomness of Algorithm 2.

Proof. Recall that S = j∈[η ] s j . Let neuron j ∈ [η ] be selected on iteration k of Line 19. For any k ∈ [m] we have:

Y k (x) = w ij a j (x) mp j = S w ij a j (x) m s j ≤ C S w ij a j (x) m max i g i j (x) ≤ C S w ij a j (x) m g ij (x) = C S z m ,

where the first inequality follows by the inequality of event G, the second by the fact that max i g i j (x) ≥ g ij (x) for any i, and the third equality by definition of g ij (x) = w ij a j (x)/z(x). This implies that Lemma 7. For any x such that event G occurs, then Var(Y k (x)) ≤ CSz 2 /m 2 . Here the expectation is over the randomness of Algorithm 2.

|Y k -E [Y k ]| = Y k -z m ∈ [-z/m,

Proof. We can use the same inequality obtained by conditioning on G to bound the variance of our estimator.

Var(Y k (x)) = E [Y 2 k (x)] -(E [Y k (x)]) 2 ≤ E [Y 2 k (x)] = j∈[η ] w ij a j (x) m p j 2 • p j by definition of Y k = S m 2 j∈[η ] (w ij a j (x)) 2 s j since p j = s j /S ≤ CS m 2 j∈[η ] (w ij a j (x)) 2 max i ∈[η +1 ] g i j (x) by occurrence of event G ≤ CS z m 2 j∈[η ] w ij a j (x) since g ij (x) = w ij a j (x)/z(x) = CSz 2 m 2 .

We are now ready to prove Theorem 2.

Proof of Theorem 2. Recall the form of Bernstein's inequality that, given random variables X 1 , . . . , X m such that for each k ∈

[m] we have E [X k ] = 0 and |X k | ≤ M almost surely, then P   k∈[m] X k ≥ t   ≤ exp -t 2 /2 k∈[m] E [X 2 k ] + M t/3

We apply this with X k = Y k -z m . We must take the probability with respect to the randomness of both drawing x ∼ D and Algorithm 2. By Lemma 4, E[X k ] = 0. Let us assume that event G occurs. By Lemma 6, we may set M = CSz/m. By Lemma 7, k∈[m] E [X 2 k ] ≤ CSz 2 /m. We will apply the inequality with t = εz.

Observe that k∈[m] X k = ẑ -z. Plugging in these values, and taking both tails of the inequality, we obtain:

P(|ẑ -z| ≥ εz : G) ≤ 2 exp -ε 2 z 2 /2 CSz 2 /m + CSεz 2 /3m = 2 exp - ε 2 m SK (6 + 2ε) since C ≤ 3K ≤ δ 2η +1

by definition of m

Removing dependence on event G, we write:

P(|ẑ -z| ≥ εz) ≥ P(|ẑ -z| ≥ εz : G) P(G) ≥ 1 - δ 2η +1 1 - δ 2η +1 ≥ 1 - δ η +1

where we have applied Lemma 5. This implies the result for any single neuron, and the theorem follows by application of the union bound over all η +1 neurons in layer .

B.1 BOOSTING SAMPLING VIA DETERMINISTIC CHOICES:

Importance sampling schemes, such as the one described above, are powerful tools with numerous applications in Big Data settings, ranging from sparsifying matrices (Baykal et al., 2019a; Achlioptas et al., 2013; Drineas & Zouzias, 2011; Kundu & Drineas, 2014; Tropp et al., 2015) to constructing coresets for machine learning problems (Braverman et al., 2016; Feldman & Langberg, 2011; Bachem et al., 2017) . However, by the nature of the exponential decay in probability associated with importance sampling schemes (see Theorem 1), 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 on 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 to the highest m probabilities may yield an estimator that incurs lower error (McCurdy, 2018; Papailiopoulos et al., 2014) .

To this end, consider a hybrid scheme that picks k indices deterministically (without reweighing) and samples m indices. More formally, let C det ⊆ [n] be the set of k unique indices (corresponding to weights) that are picked deterministically, and define

ẑdet = j∈C det w ij a j ,

where we note that the weights are not reweighed. Now let C rand be a set of m indices sampled from the remaining indices i.e., sampled from [n] \ C det , with probability distribution q = (q 1 , . . . , q n ).

To define the distribution q, recall that the original distribution p is defined to be p i = s i /S for each i ∈ [n]. Now, q is simply the normalized distribution resulting from setting the probabilities associated with indices in C det to be 0, i.e.,

q i = si S-S k if i / ∈ C det , 0 otherwise ,

where S k = j∈C det s j is the sum of sensitivities of the entries that were deterministically picked.

Instead of doing a combinatorial search over all n k choices for the deterministic set C det , for computational efficiency, we found that setting C det to be the indices with the top k sensitivities was the most likely set to satisfy the condition above.

We state the general theorem below. Theorem 8. It is better to keep k feature maps,

C det ⊆ [η ], |C det | = k, deterministically and sample m = (6 + 2ε) (S -S k ) K log(8η * /δ)ε -2 features from [η ] \ C det if j / ∈C det 1 - s j S -S k m > η j=1 1 - s j S m + log(2/δ)(m + m ) 2 ,

where m = (6 + 2ε) S K log(4η * /δ)ε -2 , S k = j∈C det s j and η * = max η .

Proof. Let m ≥ (6 + 2ε) S K log(4η * /δ)ε -2 as in Lemma 2 and note that from Lemma 2, we know that if ẑ is our approximation with respect to sampled set of indices, C, we have

P(E) ≤ δ

where E is the event that the inequality

ẑ +1 i (x) -z +1 i (x) ≤ εz +1 i (x) ∀i ∈ [η +1 ]

holds. Henceforth, we will let i ∈ [η +1 ] be an arbitrary neuron and, similar to before, consider the problem of approximating the neuron's value z +1 i (x) (subsequently denoted by z) by our approximating ẑ +1 i (x) (subsequently denoted by ẑ).

Similar to our previous analysis of our importance sampling scheme, we let C rand = {c 1 , . . . , c m } denote the multiset of m neuron indices that are sampled with respect to distribution q and for each j ∈ [m ] define Y j = ŵicj a cj and let Y = j∈[m ] Y j . For clarity of exposition, we define ẑrand = Y be our approximation with respect to the random sampling procedure, i.e., ẑrand = j∈C rand ŵij a j = Y. Thus, our estimator under this scheme is given by ẑ = ẑdet + ẑrand Now we want to analyze the sampling complexity of our new estimator ẑ so that

P(|ẑ -z| ≥ εz) ≤ δ/2.

Establishing the sampling complexity for sampling with respect to distribution q is almost identical to the proof of Theorem 2. First, note that E

[ẑ | x] = ẑdet + E [ẑ rand | x] since ẑdet is a constant (conditioned on a realization x of x ∼ D). Now note that for any j ∈ [m ] E [Y j | x] = k∈[η ]\C det ŵik a k • q k = 1 m k∈[η ]\C det w ik a k = z -ẑdet m ,

and so

E [ẑ rand | x] = E [Y | x] = z -ẑdet .

This implies that E [ẑ ] = ẑdet + (z -ẑdet ) = z, and so our estimator remains unbiased. This also yields

|Y -E [Y | x]| = |ẑ rand -E [ẑ rand ]| = |ẑ rand + ẑdet -z| = |ẑ -z| ,

which implies that all we have to do to bound the failure probability of the event |z -z| ≥ εz is to apply Bernstein's inequality to our estimator ẑrand = Y , just as we had done in the proof of Theorem 2. The only minor change is the variance and magnitude of the random variables Y k for k ∈ [m ] since the distribution is now with respect to q and not p. Proceeding as in the proof of Lemma 6, we have

ŵij a j (x) = w ij a j (x) m q j = (S -S k ) w ij a j (x) m s j ≤ (S -S k )C z m .

Now, to bound the magnitude of the random variables note that

E [Y j | x] = z -ẑdet m = 1 m j / ∈C det w ij a j ≤ (S -S k )C z m .

The result above combined with this fact yields for the magnitude of the random variables

R = max j∈[m ] |Y j -E [Y j | x]| ≤ (S -S k )C z m ,

where we observe that the only relative difference to the bound of Lemma 6 is the term S -S k appears, where S k = j∈C det s j , instead of S7 

Similarly, for the variance of a single

Y j Var(Y j | x, G) ≤ k∈[η ]\C det (w ik a k (x)) 2 m 2 q k = S -S k m 2 k∈[η ]\C det (w ik a k (x)) 2 s k ≤ C(S -S k ) z m 2 k∈[η ]\C det w ik a k (x) ≤ C(S -S k )z 2 min{1, C(S -S k )} m 2 ,

where the last inequality follows by the fact that k∈[η ]\C det w ik a k (x) ≤ z and by the sensitivity inequality from the proof of Lemma 7

k∈[η ]\C det w ik a k (x) ≤ Cz j∈[η ]\C det s j = Cz(S -S k ).

This implies by Bernstein's inequality and the argument in proof of Theorem 2 that if we sample

m = (6 + 2ε) (S -S k ) K log(8η * /δ)ε -2

times from the distribution q, then we have

P(|ẑ -z| ≥ εz) ≤ δ/2.

Now let p = (p 1 , . . . , p n ) 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 ∈ [n] let U j (m, p) = 1 [j ∈ C

] be the indicator random variable of the event that index j is sampled at least once and let U (m, p) = n i=j U j (m, p). Note that U is 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 [U (m, p)] = n j=1 E [U j (m, p)] = n j=1 P(i ∈ C) = n j=1 P(j is sampled at least once) = n j=1 (1 -P(j is not sampled)) = n - n j=1 (1 -p j ) m .

Now we want to establish the condition for which U (m , q) < U (m, p), which, if it holds, would imply that the number of distinct weights that we retain with the deterministic + sampling approach 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 = C det ∪ C rand = {c 1 , . . . , c k , c k+1 , . . . , c m } denote the set of indices sampled from the deterministic + sampling (with distribution q) approach, and let C = {c 1 , . . . , c m } be the indices of the random samples obtained by sampling from distribution p. Let f (c 1 , . . . , c m , c 1 , . . . , c m ) denote the difference U (m , q) -U (m, p) in the number of unique samples in C and C. Note that f satisfies the bounded difference inequality with Lipschitz constant 1 since changing the index of any single sample in C ∪ C can change f by at most 1. Moreover, there are m + m random variables, thus, applying McDiarmid's inequality (van Handel, 2014) , we obtain

P(E [U (m, p) -U (m , q)] -(U (m, p) -U (m , q)) ≥ t) ≤ exp - -2t 2 (m + m ) , this implies that for t = log(2/δ)(m+m ) 2 , E [U (m, p) -U (m , q)] ≤ U (m, p) -U (m , q) + t with probability at least 1 -δ/2. Thus, this means that if E[U (m, p)] -E [U (m , q)] > t, then U (m, p) > U (m , q).

More specifically, recall that The performance of our approach on a LeNet300-100 architecture trained on 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 (b) 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.

E [U (m, p)] = n - n j=1 (1 -p j ) m = n - n j=1 1 - s j S m and E [U (m , q)] = k + j:qj >0 (1 -(1 -q j ) m ) = k + (n -k) - j:qj >0 (1 -q j ) m = n - j:qj >0 (1 -q j ) m = n - j / ∈C det 1 - s j S -

Thus, rearranging terms, we conclude that it is better to conduct the deterministic + sampling scheme if

j / ∈C det 1 - s j S -S k m > n j=1 1 - s j S m + log(2/δ)(m + m ) 2 .

Putting it all together, and conditioning on the above inequality holding, we have by the union bound

P (|ẑ -z| ≥ εz ∪ U (m , q) > U (m, p)) ≤ δ,

this implies that with probability at least 1 -δ: (i) ẑ ∈ (1 ± ε)z and (ii) U (m , q) < U (m, p), implying that the deterministic + sampling approach ensures the error guarantee holds with a 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. 2 and sample channels with probability proportional to their sensitivity.

2. Partial derandomization ("partial"): We apply Theorem 8 as a preprocessing step to keep the top k 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 a LeNet300-100 architecture trained on MNIST can be seen in Fig. 5 . As visible from Fig. 5 (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 to incur a slight performance boost relative to the other approaches. We suspect that simply keeping the top channels may have a positive side effect on the optimization landscape during retraining, which we would like to further investigate in future research.

C MAIN COMPRESSION THEOREM:

Having established layer-wise approximation guarantees as in Sec. B, all that remains to establish guarantees on the output of the entire network is to carefully propagate the error through the layers as was done in Baykal et al. (2019a) . For each i ∈ [η +1 ] and ∈ [L], define

∆ i (x) = (z + i (x)+z - i (x)) /|zi(x)|, where z + i (x) = k∈I + w +1 ik a k (x) and z - i (x) = k∈I -w +1 ik a k (x)

are positive and negative components of z +1 i (x), respectively, with I + and I -as in Alg. 2. For each ∈ [L], let ∆ be a constant defined as a function of the input distribution D8 , such that with high probability over

x ∼ D, ∆ ≥ max i∈[η +1 ] ∆ i . Finally, let ∆ → = L k= ∆ k .

Generalizing Theorem 2 to obtain a layer-wise bound and applying error propagation bounds of Baykal et al. (2019a) , we establish our main compression theorem below.

Theorem 3. Let ε, δ ∈ (0, 1) be arbitrary, let S ⊂ X denote the set of K log (4η/δ) i.i.d. points drawn from D, and suppose we are given a network with parameters θ = (W 1 , . . . , W L ). Consider the set of parameters θ = ( Ŵ 1 , . . . , Ŵ L ) generated by pruning channels of θ according to Alg. 2 for each ∈

[L]. Then, θ satisfies P θ, x∼D f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 -δ, and the number of filters in θ is bounded by O L =1 L 2 (∆ → ) 2 S log(η/δ) ε 2

.

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 z +1 (x). In the case of CNNs the same intuition holds, that is we want to capture the maximum contribution of a feature map a j (x), which is now a two-dimensional image instead of a scalar neuron, to the pre-activation z +1 (x) in layer + 1. Thus, to 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 a j (x) is also associated with a patch p ∈ P, which we denote by a jp . In particular, the slight change is the following:

s j = max x∈S max i∈[η +1 ] max p∈P w +1 ij a jp (x) k∈[η ] w +1 ik a kp (x)

, where a •p corresponds to the activation window associated with patch p ∈ 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, ImageNet) and neural network architectures (LeNet, VGG, ResNet, WideResNet, DenseNet) and compared against several state-of-the-art filter pruning methods. We conducted all experiments on either a single NVIDIA RTX 2080Ti with 11GB RAM or a NVIDIA Tesla V100 with 16GB RAM and implemented them in PyTorch (Paszke et al., 2017) . Retraining with ImageNet was conducted on a 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.

E.1 COMPARISON METHODS:

We further evaluated the performance of our algorithm against a 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, Li et al. (2016) Consider the set of filters W = [W 1 , . . . , W η ] in layer and let W j 2,2 denote the entry-wise 2 -norm of W j (or Frobenius norm). Consider a desired sparsity level of t%, i.e., we want to keep only t% of the filters. We then simply keep the filters with the largest norm until we 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 of Li et al. (2016) except the saliency score used is the entrywise 1 -norm W j 1,1 of a filter map W j . 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 et al., 2017) Unlike the previous two approaches, which compute the saliency score of the filter W j 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 j∈[η ] max x∈S z +1 (x) -z +1

[j] (x) , where z +1 (x) denotes the pre-activation of layer + 1 for some input data point x, z +1

[j] (x) the pre-activation when only considering feature map j in layer , and S a set of input data points. We note that this greedy approach is quadratic in both the size η of layer and the size |S| of the set of data points S, thus rendering it very slow in practice. In particular, we only use a set S of cardinality comparable to our own method, i.e., around 100 data points in total. On the other hand, Luo et al. report 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 its convolutional counterpart, LeNet-5 (LeCun et al., 1998) , which consists of two convolutional layers and two fullyconnected layers. Both networks were trained on MNIST using the hyper-parameters specified in Table 3 . We trained on a single GPU and during retraining (fine-tunine) we maintained the same hyperparameters and only adapted the ones specifically mentioned in Table 3 .

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-10. Specifically, we tested it on VGG16 with batch norm (Simonyan & Zisserman, 2014) , ResNet20 (He et al., 2016) , DenseNet22 (Huang et al., 2017), and Wide ResNet-16-8 (Zagoruyko & Komodakis, 2016) . For residual networks with skip connections, we model the interdependencies between the feature maps and only prune a 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 In the first scenario, we evaluate the baseline effectiveness of each pruning algorithm without fine-tuning by applying the same iterative prunescheme, but without the retraining step. The results of these evaluations can be seen in Fig. 6 . Fig. 6 shows that our algorithm outperforms the competing approaches in 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 inter-dependency between layers that alter the relative importance of filters and layers with each pruning step. This is in contrast to 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). Figure 6 : The results of our evaluations of the algorithms in the prune-only scenario, where the network is iteratively pruned down to a specified target prune ratio and the fine-tuning step is omitted. Note that the x axis is the percentage of parameters retained, i.e., (1 -pruneratio). sakovsky et al., 2015) . 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.e., 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 a limited number of iterations (2-3 iterations per reported experiment). The results of 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 -our method is able to produce compressed networks that are as accurate and compact as the models generated by competing approaches (obtained by significantly more prune-retrain iterations than allotted to our algorithm).

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 of accuracy are paramount to the successful deployment of such systems (Amini et al., 2018) . The particular challenge of real-time applications stems from the fact that -in addition to the conventional trade-off between accuracy and model efficiencyinference has to be conducted in real-time. In other words, there is a hard upper bound on the allotted computation time before an answer needs to 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 filter pruning method on real-time systems, we implemented and tested the neural network of Amini et al. (2018) , which is a regression neural network deployed on an autonomous vehicle in real time to predict the angle of the human driver. We trained the network of Amini et al. (2018) , denoted by Deepknight, with the driving data set provided alongside, using the hyperparameters summarized in Table 7 .

The results of our compression can 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 significant pruning ratios that lead to computational speed-ups in practice. As apparent from Fig. 7 , we can again outperform other SOTA methods in terms of performance vs. prune ratio. Note that since this is a regression task, we used test loss (mean-squared error on the test data set) as performance criterion. Finally, we would like to highlight that our filter pruning method may serve as a principled subprocedure during the design of neural network architectures for real-time applications. In particular, given an 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 on the practitioner to design a simultaneously accurate and computationally-efficient neural network architecture.

E.6 COMPARISONS TO ADDITIONAL METHODS ON CIFAR-10:

We evaluate the performance of our algorithm on pruning modern convolutional and residual benchmark network architectures -ResNet20, ResNet56, ResNet110, and VGG16 -trained on 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 to reporting the pruned model that achieves commensurate accuracy ("within 0.5% err.") as in Sec. 4, we the model that (i) closest matches the accuracy of the original network ("orig. err.") and (ii) achieves the lowest classification error possible ("lowest err.") -which for nearly all of the models considered, is lower than that of the original model.

Table 8 summarizes our results and depicts the performance of each pruning algorithm with respect to various 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). 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 a 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 a 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 as ResNet110, our algorithm's favorable performance is even more pronounced: the models generated by our algorithm are not only the sparsest (PR) and most efficient (PR), but they are also the most accurate. A nearly identical trend holds for the results pertaining to VGG16 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. Table 8 : The performance of our algorithm and that of 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.e., Pruned Err., 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.

:

Code available at https://github.com/lucaslie/provable_pruning

The extension to CNNs follows directly as outlined Sec. B of the supplementary material.

We define the minimization with respect to sample complexity from Theorem 1, which serves as a sufficiently good proxy as Bernstein's inequality is tight up to logarithmic factors(Tropp et al., 2015).

Excluding the time required for the fine-tuning step, which was approximately the same across all methods

Weight pruning approaches can generate significantly sparser models with commensurate accuracy than can filter pruning approaches since the set of feasible solutions to the problem of filter pruning is a subset of the feasible set for the weight pruning problem

and of course the sampling complexity is m instead of m

If ∆i(x) is a sub-Exponential random variable(Vershynin, 2016) with parameter λ = O(1), then for δ failure probability: ∆ O(E x∼D [maxi ∆i(x)] + log(1/δ))(Baykal et al., 2019a;Vershynin, 2016)

Figures and Tables:

Figure1: Overview of our pruning method. We use a small batch of data points to quantify the relative importance s j of each filter W j in layer by considering the importance of the corresponding feature map a j = φ(z j ) in computing the output z +1 of layer + 1, where φ(•) is the non-linear activation function. We then prune filters by sampling each filter j with probability proportional to s j 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 prune-retrain cycle iteratively.

Figure4: The performance of the compared algorithms on pruning a lightweight network for a real-time regression task(Amini et al., 2018).

reweighing or considering multiplicity of drawing index c(k) of pre-activation in layer + 1} 22: end for 23: return Ŵ = [ Ŵ 1 , . . . , Ŵ η ]; Ŵ +1 = [ Ŵ +1 :1 , . . . , Ŵ +1 :η ]

CSz/m] by Lemma 4 and since Y k ≥ 0. The result follows since C, S ≥ 1.

Figure5: The performance of our approach on a LeNet300-100 architecture trained on 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 (b) 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.

Figure7: 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 on the test loss and compared to competing filter pruning methods. Note that the x axis is percentage of parameters retained, i.e., 1 -(pruneratio).

The prune ratio (PR) and the corresponding test error (Err.) of the sparsest network -with commensurate accuracygenerated by each algorithm.

Table content: <table><tr><td colspan="2">[%] Method</td><td>Err.</td><td>PR</td></tr><tr><td>LeNet-300-100</td><td>Unpruned Ours FT SoftNet ThiNet</td><td colspan="2">1.59 +0.41 84.32 +0.35 81.68 +0.41 81.69 +10.58 75.01</td></tr><tr><td/><td>Unpruned</td><td>0.72</td></tr><tr><td>LeNet-5</td><td>Ours FT SoftNet</td><td colspan="2">+0.35 92.37 +0.47 85.04 +0.40 80.57</td></tr><tr><td/><td>ThiNet</td><td colspan="2">+0.12 58.17</td></tr></table>

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 test 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.

Table content: <table><tr><td>[%]</td><td>Orig. Err. Err.</td><td>Ours PR</td><td>FR</td><td>Err.</td><td>FT PR</td><td>FR</td><td>Err.</td><td>SoftNet PR</td><td>FR</td><td>Err.</td><td>ThiNet PR</td><td>FR</td></tr><tr><td colspan="13">ResNet20 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</td></tr><tr><td colspan="13">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</td></tr><tr><td colspan="13">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</td></tr><tr><td>VGG16</td><td colspan="12">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</td></tr><tr><td colspan="13">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</td></tr><tr><td colspan="13">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</td></tr></table>

). 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 arXiv:1605.07146, 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 on Machine Learning-Volume 70, pp. 4082-4090. JMLR. org, 2017.

Table content: <table/>

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 content: <table/>



Table content: <table><tr><td/><td/><td/><td>.</td><td/><td/></tr><tr><td/><td/><td>VGG16</td><td>ResNet20/56/110</td><td>DenseNet22</td><td>WRN-16-8</td></tr><tr><td/><td>test error</td><td>7.11</td><td>8.59/7.05/6.43</td><td>10.07</td><td>4.81</td></tr><tr><td/><td>loss</td><td>cross-entropy</td><td>cross-entropy</td><td>cross-entropy</td><td>cross-entropy</td></tr><tr><td/><td>optimizer</td><td>SGD</td><td>SGD</td><td>SGD</td><td>SGD</td></tr><tr><td/><td>epochs</td><td>300</td><td>182</td><td>300</td><td>200</td></tr><tr><td>Train</td><td>batch size</td><td>256</td><td>128</td><td>64</td><td>128</td></tr><tr><td/><td>LR</td><td>0.05</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td/><td colspan="2">LR decay 0.5@{30, . . . }</td><td>0.1@{91, 136}</td><td colspan="2">0.1@{150, 225} 0.2@{60, . . . }</td></tr><tr><td/><td>momentum</td><td>0.9</td><td>0.9</td><td>0.9</td><td>0.9</td></tr><tr><td/><td>Nesterov</td><td/><td/><td/><td/></tr><tr><td/><td>weight decay</td><td>5.0e-4</td><td>1.0e-4</td><td>1.0e-4</td><td>5.0e-4</td></tr><tr><td>Prune</td><td>δ α</td><td>1.0e-16 1.50</td><td>1.0e-16 0.50/0.79/0.79</td><td>1.0e-16 0.40</td><td>1.0e-16 0.36</td></tr><tr><td>Fine-tune</td><td>epochs</td><td>150</td><td>182</td><td>300</td><td>200</td></tr></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.

Table content: <table><tr><td colspan="3">E.4 CONVOLUTIONAL NEURAL NETWORKS ON IMAGENET</td></tr><tr><td>We consider pruning convolutional neural net-works of varying size -ResNet18, ResNet50, and ResNet101 -trained on the ImageNet (Rus-sakovsky et al., 2015) data set. The hyper-parameters used for training and for our pruning algorithm are shown in Table 5. For this dataset,</td><td>Train</td><td colspan="2">ResNet18/50/101 top-1 test error 30.26/23.87/22.63 top-5 test error 10.93/7.13/6.45 loss cross-entropy optimizer SGD epochs 90 batch size 256</td></tr><tr><td>we considered two scenarios: (i) iterative prun-</td><td/><td>LR</td><td>0.1</td></tr><tr><td>ing without retraining and (ii) iterative prune-</td><td/><td>LR decay</td><td>0.1@{30, 60}</td></tr><tr><td>retrain with a limited amount of iterations given</td><td/><td>momentum</td><td>0.9</td></tr><tr><td>the resource-intensive nature of the experiments.</td><td/><td>Nesterov</td></tr><tr><td/><td/><td>weight decay</td><td>1.0e-4</td></tr><tr><td/><td>Prune</td><td>δ α</td><td>1.0e-16 0.43/0.50/0.50</td></tr><tr><td colspan="2">Fine-tune</td><td>epochs</td><td>90</td></tr><tr><td colspan="4">Table 5: The hyper-parameters used for training and</td></tr><tr><td colspan="4">pruning residual networks trained on the ImageNet data</td></tr><tr><td>set.</td><td/><td/></tr></table>

Comparisons of the performance of various pruning algorithms on ResNets trained on ImageNet (Rus-

Table content: <table><tr><td>Model</td><td>Method</td><td colspan="5">Top-1 Err. (%) Orig. Pruned Diff. Orig. Pruned Diff. Top-5 Err. (%)</td><td>PR (%) FR (%)</td></tr><tr><td/><td colspan="6">Ours (within 4.0% top-1) 30.26 34.35 +4.09 10.93 13.25 +2.32 60.48</td><td>43.12</td></tr><tr><td/><td colspan="6">Ours (within 2.0% top-1) 30.26 32.62 +2.36 10.93 12.09 +1.16 43.80</td><td>29.30</td></tr><tr><td/><td>Ours (lowest top-1 err.)</td><td colspan="5">30.26 31.34 +1.08 10.93 11.43 +0.50 31.03</td><td>19.99</td></tr><tr><td>Resnet18</td><td colspan="6">He et al. (2018) (SoftNet) 29.72 32.90 +3.18 10.37 12.22 +1.85 N/A</td><td>41.80</td></tr><tr><td/><td>He et al. (2019)</td><td colspan="5">29.72 31.59 +1.87 10.37 11.52 +1.15 N/A</td><td>41.80</td></tr><tr><td/><td>Dong et al. (2017)</td><td colspan="5">30.02 33.67 +3.65 10.76 13.06 +2.30 N/A</td><td>33.30</td></tr><tr><td/><td colspan="4">Ours (within 1.0% top-1) 23.87 24.79 +0.92 7.13</td><td colspan="2">7.57 +0.45 44.04</td><td>30.05</td></tr><tr><td/><td>Ours (lowest top-1 err.)</td><td colspan="3">23.87 24.09 +0.22 7.13</td><td colspan="2">7.19 +0.06 18.01</td><td>10.82</td></tr><tr><td/><td colspan="4">He et al. (2018) (SoftNet) 23.85 25.39 +1.54 7.13</td><td colspan="2">7.94 +0.81 N/A</td><td>41.80</td></tr><tr><td/><td colspan="4">Luo et al. (2017) (ThiNet) 27.12 27.96 +0.84 8.86</td><td colspan="2">9.33 +0.47 33.72</td><td>36.39</td></tr><tr><td>Resnet50</td><td>He et al. (2019)</td><td colspan="3">23.85 25.17 +1.32 7.13</td><td colspan="2">7.68 +0.55 N/A</td><td>53.50</td></tr><tr><td/><td>He et al. (2017)</td><td>N/A</td><td>N/A</td><td>N/A 7.80</td><td colspan="2">9.20 +1.40 N/A</td><td>50.00</td></tr><tr><td/><td>Luo &amp; Wu (2018)</td><td colspan="3">23.85 25.24 +1.39 7.13</td><td colspan="2">7.85 +0.72 N/A</td><td>48.70</td></tr><tr><td/><td>Liu et al. (2019a)</td><td colspan="3">23.40 24.60 +1.20 N/A</td><td>N/A</td><td>N/A</td><td>N/A</td><td>51.22</td></tr><tr><td/><td colspan="4">Ours (within 1.0% top-1) 22.63 23.57 +0.94 6.45</td><td colspan="2">6.89 +0.44 50.45</td><td>45.08</td></tr><tr><td/><td>Ours (lowest top-1 err.)</td><td colspan="3">22.63 23.22 +0.59 6.45</td><td colspan="2">6.74 +0.29 33.04</td><td>29.38</td></tr><tr><td>Resnet101</td><td colspan="4">He et al. (2018) (SoftNet) 22.63 22.49 -0.14 6.44 He et al. (2019) 22.63 22.68 +0.05 6.44</td><td colspan="2">6.29 6.44 +0.00 N/A -0.15 N/A</td><td>42.20 42.20</td></tr><tr><td/><td>Ye et al. (2018)</td><td colspan="3">23.60 24.73 +1.13 N/A</td><td>N/A</td><td>N/A</td><td>47.20</td><td>42.69</td></tr></table>



Table content: <table><tr><td/><td/><td>Deepknight</td></tr><tr><td/><td>test loss</td><td>4.9e-5</td></tr><tr><td/><td>loss</td><td>MSE</td></tr><tr><td/><td>optimizer</td><td>Adam</td></tr><tr><td/><td>epochs</td><td>100</td></tr><tr><td>Train</td><td>batch size</td><td>32</td></tr><tr><td/><td>LR</td><td>1e-4</td></tr><tr><td/><td colspan="2">LR decay 0.1@{50, 90}</td></tr><tr><td/><td>momentum</td><td>0.9</td></tr><tr><td/><td>weight decay</td><td>1.0e-4</td></tr><tr><td>Prune</td><td>δ α</td><td>1.0e-32 not iterative</td></tr><tr><td>Fine-tune</td><td>epochs</td><td>0</td></tr></table>

Peer review (iclr2020):
Summary: In 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. Intuitively 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. Weakness: 1. experiment is too weak ImageNet 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. 2. lack of a comparing experiment for random select the top-k norm. Important 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. 3. lack of further theory consideration author 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.