Title: SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY

Abstract: Pruning large neural networks while maintaining their performance is often desirable due to the reduced space and time complexity. In existing methods, pruning is done within an iterative optimization procedure with either heuristically designed pruning schedules or additional hyperparameters, undermining their utility. In this work, we present a new approach that prunes a given network once at initialization prior to training. To achieve this, we introduce a saliency criterion based on connection sensitivity that identifies structurally important connections in the network for the given task. This eliminates the need for both pretraining and the complex pruning schedule while making it robust to architecture variations. After pruning, the sparse network is trained in the standard way. Our method obtains extremely sparse networks with virtually the same accuracy as the reference network on the MNIST, CIFAR-10, and Tiny-ImageNet classification tasks and is broadly applicable to various architectures including convolutional, residual and recurrent networks. Unlike existing methods, our approach enables us to demonstrate that the retained connections are indeed relevant to the given task.

1. INTRODUCTION:

Despite the success of deep neural networks in machine learning, they are often found to be highly overparametrized making them computationally expensive with excessive memory requirements. Pruning such large networks with minimal loss in performance is appealing for real-time applications, especially on resource-limited devices. In addition, compressed neural networks utilize the model capacity efficiently, and this interpretation can be used to derive better generalization bounds for neural networks (Arora et al. (2018) ).

In network pruning, given a large reference neural network, the goal is to learn a much smaller subnetwork that mimics the performance of the reference network. The majority of existing methods in the literature attempt to find a subset of weights from the pretrained reference network either based on a saliency criterion (Mozer & Smolensky (1989) ; LeCun et al. (1990) ; Han et al. (2015) ) or utilizing sparsity enforcing penalties (Chauvin (1989) ; Carreira-Perpiñán & Idelbayev (2018) ). Unfortunately, since pruning is included as a part of an iterative optimization procedure, all these methods require many expensive prune -retrain cycles and heuristic design choices with additional hyperparameters, making them non-trivial to extend to new architectures and tasks.

In this work, we introduce a saliency criterion that identifies connections in the network that are important to the given task in a data-dependent way before training. Specifically, we discover important connections based on their influence on the loss function at a variance scaling initialization, which we call connection sensitivity. Given the desired sparsity level, redundant connections are pruned once prior to training (i.e., single-shot), and then the sparse pruned network is trained in the standard way. Our approach has several attractive properties: • Simplicity. Since the network is pruned once prior to training, there is no need for pretraining and complex pruning schedules. Our method has no additional hyperparameters and once pruned, training of the sparse network is performed in the standard way. • Versatility. Since our saliency criterion chooses structurally important connections, it is robust to architecture variations. Therefore our method can be applied to various architectures including convolutional, residual and recurrent networks with no modifications. i

• Interpretability. Our method determines important connections with a mini-batch of data at single-shot. By varying this mini-batch used for pruning, our method enables us to verify that the retained connections are indeed essential for the given task.

We evaluate our method on MNIST, CIFAR-10, and Tiny-ImageNet classification datasets with widely varying architectures. Despite being the simplest, our method obtains extremely sparse networks with virtually the same accuracy as the existing baselines across all tested architectures. Furthermore, we investigate the relevance of the retained connections as well as the effect of the network initialization and the dataset on the saliency score.

2. RELATED WORK:

Classical methods. Essentially, early works in network pruning can be categorized into two groups (Reed (1993) ): 1) those that utilize sparsity enforcing penalties; and 2) methods that prune the network based on some saliency criterion. The methods from the former category (Chauvin (1989) ; Weigend et al. (1991) ; Ishikawa (1996) ) augment the loss function with some sparsity enforcing penalty terms (e.g., L 0 or L 1 norm), so that back-propagation effectively penalizes the magnitude of the weights during training. Then weights below a certain threshold may be removed.

On the other hand, classical saliency criteria include the sensitivity of the loss with respect to the neurons (Mozer & Smolensky (1989) ) or the weights (Karnin ( 1990)) and Hessian of the loss with respect to the weights (LeCun et al. (1990) ; Hassibi et al. (1993) ). Since these criteria are heavily dependent on the scale of the weights and are designed to be incorporated within the learning process, these methods are prohibitively slow requiring many iterations of pruning and learning steps.

Our approach identifies redundant weights from an architectural point of view and prunes them once at the beginning before training.

Modern advances. In recent years, the increased space and time complexities as well as the risk of overfitting in deep neural networks prompted a surge of further investigation in network pruning. While Hessian based approaches employ the diagonal approximation due to its computational simplicity, impressive results (i.e., extreme sparsity without loss in accuracy) are achieved using magnitude of the weights as the criterion (Han et al. (2015) ). This made them the de facto standard method for network pruning and led to various implementations (Guo et al. (2016) ; Carreira-Perpiñán & Idelbayev ( 2018)). The magnitude criterion is also extended to recurrent neural networks (Narang et al. (2017) ), yet with heavily tuned hyperparameter setting. Unlike our approach, the main drawbacks of magnitude based approaches are the reliance on pretraining and the expensive pruneretrain cycles. Furthermore, since pruning and learning steps are intertwined, they often require highly heuristic design choices which make them non-trivial to be extended to new architectures and different tasks. Meanwhile, Bayesian methods are also applied to network pruning (Ullrich et al. (2017) ; Molchanov et al. (2017a) ) where the former extends the soft weight sharing in Nowlan & Hinton (1992) to obtain a sparse and compressed network, and the latter uses variational inference to learn the dropout rate which can then be used to prune the network. Unlike the above methods, our approach is simple and easily adaptable to any given architecture or task without modifying the pruning procedure.

Network compression in general. Apart from weight pruning, there are approaches focused on structured simplification such as pruning filters (Li et al. (2017) ; Molchanov et al. (2017b) ), structured sparsity with regularizers (Wen et al. (2016) ), low-rank approximation (Jaderberg et al. (2014) ), matrix and tensor factorization (Novikov et al. (2015) ), and sparsification using expander graphs (Prabhu et al. (2018) ) or Erdős-Rényi random graph (Mocanu et al. (2018) ). In addition, there is a large body of work on compressing the representation of weights. A non-exhaustive list includes quantization (Gong et al. (2014) ), reduced precision (Gupta et al. (2015) ) and binary weights (Hubara et al. (2016) ). In this work, we focus on weight pruning that is free from structural constraints and amenable to further compression schemes.

3. NEURAL NETWORK PRUNING:

The main hypothesis behind the neural network pruning literature is that neural networks are usually overparametrized, and comparable performance can be obtained by a much smaller network (Reed (1993) ) while improving generalization (Arora et al. (2018) ). To this end, the objective is to learn a sparse network while maintaining the accuracy of the standard reference network. Let us first formulate neural network pruning as an optimization problem.

Given a dataset D = {(x i , y i )} n i=1 , and a desired sparsity level κ (i.e., the number of non-zero weights) neural network pruning can be written as the following constrained optimization problem:

EQUATION

s.t. w ∈ R m , w 0 ≤ κ .

Here, (•) is the standard loss function (e.g., cross-entropy loss), w is the set of parameters of the neural network, m is the total number of parameters and • 0 is the standard L 0 norm.

The conventional approach to optimize the above problem is by adding sparsity enforcing penalty terms (Chauvin (1989) ; Weigend et al. (1991) ; Ishikawa (1996) ). Recently, Carreira-Perpiñán & Idelbayev (2018) attempts to minimize the above constrained optimization problem using the stochastic version of projected gradient descent (where the projection is accomplished by pruning). However, these methods often turn out to be inferior to saliency based methods in terms of resulting sparsity and require heavily tuned hyperparameter settings to obtain comparable results.

On the other hand, saliency based methods treat the above problem as selectively removing redundant parameters (or connections) in the neural network. In order to do so, one has to come up with a good criterion to identify such redundant connections. Popular criteria include magnitude of the weights, i.e., weights below a certain threshold are redundant (Han et al. (2015) ; Guo et al. (2016) ) and Hessian of the loss with respect to the weights, i.e., the higher the value of Hessian, the higher the importance of the parameters (LeCun et al. (1990) ; Hassibi et al. (1993) ), defined as follows:

EQUATION

Here, for connection j, s j is the saliency score, w j is the weight, and H jj is the value of the Hessian matrix, where the Hessian H = ∂ 2 L/∂w 2 ∈ R m×m . Considering Hessian based methods, the Hessian matrix is neither diagonal nor positive definite in general, approximate at best, and intractable to compute for large networks.

Despite being popular, both of these criteria depend on the scale of the weights and in turn require pretraining and are very sensitive to the architectural choices. For instance, different normalization layers affect the scale of the weights in a different way, and this would non-trivially affect the saliency score. Furthermore, pruning and the optimization steps are alternated many times throughout training, resulting in highly expensive prune -retrain cycles. Such an exorbitant requirement hinders the use of pruning methods in large-scale applications and raises questions about the credibility of the existing pruning criteria.

In this work, we design a criterion which directly measures the connection importance in a datadependent manner. This alleviates the dependency on the weights and enables us to prune the network once at the beginning, and then the training can be performed on the sparse pruned network. Therefore, our method eliminates the need for the expensive prune -retrain cycles, and in theory, it can be an order of magnitude faster than the standard neural network training as it can be implemented using software libraries that support sparse matrix computations.

4. SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY:

Given a neural network and a dataset, our goal is to design a method that can selectively prune redundant connections for the given task in a data-dependent way even before training. To this end, we first introduce a criterion to identify important connections and then discuss its benefits.

4.1. CONNECTION SENSITIVITY: ARCHITECTURAL PERSPECTIVE:

Since we intend to measure the importance (or sensitivity) of each connection independently of its weight, we introduce auxiliary indicator variables c ∈ {0, 1} m representing the connectivity of parameters w.1 Now, given the sparsity level κ, Equation 1 can be correspondingly modified as:

EQUATION

.t. w ∈ R m , c ∈ {0, 1} m , c 0 ≤ κ ,

where denotes the Hadamard product. Compared to Equation 1, we have doubled the number of learnable parameters in the network and directly optimizing the above problem is even more difficult. However, the idea here is that since we have separated the weight of the connection (w) from whether the connection is present or not (c), we may be able to determine the importance of each connection by measuring its effect on the loss function.

For instance, the value of c j indicates whether the connection j is active (c j = 1) in the network or pruned (c j = 0). Therefore, to measure the effect of connection j on the loss, one can try to measure the difference in loss when c j = 1 and c j = 0, keeping everything else constant. Precisely, the effect of removing connection j can be measured by,

EQUATION

where e j is the indicator vector of element j (i.e., zeros everywhere except at the index j where it is one) and 1 is the vector of dimension m.

Note that computing ∆L j for each j ∈ {1 . . . m} is prohibitively expensive as it requires m + 1 (usually in the order of millions) forward passes over the dataset. In fact, since c is binary, L is not differentiable with respect to c, and it is easy to see that ∆L j attempts to measure the influence of connection j on the loss function in this discrete setting. Therefore, by relaxing the binary constraint on the indicator variables c, ∆L j can be approximated by the derivative of L with respect to c j , which we denote g j (w; D). Hence, the effect of connection j on the loss can be written as:

∆L j (w; D) ≈ g j (w; D) = ∂L(c w; D) ∂c j c=1 = lim δ→0 L(c w; D) -L((c -δ e j ) w; D) δ c=1 .

(5) In fact, ∂L/∂c j is an infinitesimal version of ∆L j , that measures the rate of change of L with respect to an infinitesimal change in c j from 1 → 1 -δ. This can be computed efficiently in one forward-backward pass using automatic differentiation, for all j at once. Notice, this formulation can be viewed as perturbing the weight w j by a multiplicative factor δ and measuring the change in loss. This approximation is similar in spirit to Koh & Liang (2017) where they try to measure the influence of a datapoint to the loss function. Here we measure the influence of connections. Furthermore, ∂L/∂c j is not to be confused with the gradient with respect to the weights (∂L/∂w j ), where the change in loss is measured with respect to an additive change in weight w j .

Notably, our interest is to discover important (or sensitive) connections in the architecture, so that we can prune unimportant ones in single-shot, disentangling the pruning process from the iterative optimization cycles. To this end, we take the magnitude of the derivatives g j as the saliency criterion. Note that if the magnitude of the derivative is high (regardless of the sign), it essentially means that the connection c j has a considerable effect on the loss (either positive or negative), and it has to be preserved to allow learning on w j . Based on this hypothesis, we define connection sensitivity as the normalized magnitude of the derivatives:

EQUATION

)

Once the sensitivity is computed, only the top-κ connections are retained, where κ denotes the desired number of non-zero weights. Precisely, the indicator variables c are set as follows:

EQUATION

where sκ is the κ-th largest element in the vector s and 1[•] is the indicator function. Here, for exactly κ connections to be retained, ties can be broken arbitrarily.

We would like to clarify that the above criterion (Equation 6) is different from the criteria used in early works by Mozer & Smolensky (1989) or Karnin (1990) which do not entirely capture the Regular training 7: w * ← c w * connection sensitivity. The fundamental idea behind them is to identify elements (e.g. weights or neurons) that least degrade the performance when removed. This means that their saliency criteria (i.e. -∂L/∂w or -∂L/∂α; α refers to the connectivity of neurons), in fact, depend on the loss value before pruning, which in turn, require the network to be pre-trained and iterative optimization cycles to ensure minimal loss in performance. They also suffer from the same drawbacks as the magnitude and Hessian based methods as discussed in Section 3. In contrast, our saliency criterion (Equation 6) is designed to measure the sensitivity as to how much influence elements have on the loss function regardless of whether it is positive or negative. This criterion alleviates the dependency on the value of the loss, eliminating the need for pre-training. These fundamental differences enable the network to be pruned at single-shot prior to training, which we discuss further in the next section.

4.2. SINGLE-SHOT PRUNING AT INITIALIZATION:

Note that the saliency measure defined in Equation 6 depends on the value of weights w used to evaluate the derivative as well as the dataset D and the loss function L. In this section, we discuss the effect of each of them and show that it can be used to prune the network in single-shot with initial weights w.

Firstly, in order to minimize the impact of weights on the derivatives ∂L/∂c j , we need to choose these weights carefully. For instance, if the weights are too large, the activations after the non-linear function (e.g., sigmoid) will be saturated, which would result in uninformative gradients. Therefore, the weights should be within a sensible range. In particular, there is a body of work on neural network initialization (Goodfellow et al. (2016) ) that ensures the gradients to be in a reasonable range, and our saliency measure can be used to prune neural networks at any such initialization. Furthermore, we are interested in making our saliency measure robust to architecture variations. Note that initializing neural networks is a random process, typically done using normal distribution. However, if the initial weights have a fixed variance, the signal passing through each layer no longer guarantees to have the same variance, as noted by LeCun et al. (1998) . This would make the gradient and in turn our saliency measure, to be dependent on the architectural characteristics. Thus, we advocate the use of variance scaling methods (e.g., Glorot & Bengio (2010) ) to initialize the weights, such that the variance remains the same throughout the network. By ensuring this, we empirically show that our saliency measure computed at initialization is robust to variations in the architecture.

Next, since the dataset and the loss function defines the task at hand, by relying on both of them, our saliency criterion in fact discovers the connections in the network that are important to the given task. However, the practitioner needs to make a choice on whether to use the whole training set, or a mini-batch or the validation set to compute the connection saliency. Moreover, in case there are memory limitations (e.g., large model or dataset), one can accumulate the saliency measure over multiple batches or take an exponential moving average. In our experiments, we show that using only one mini-batch of a reasonable number of training examples can lead to effective pruning.

Finally, in contrast to the previous approaches, our criterion for finding redundant connections is simple and directly based on the sensitivity of the connections. This allows us to effectively identify and prune redundant connections in a single step even before training. Then, training can be performed on the resulting pruned (sparse) network. We name our method SNIP for Single-shot Network Pruning, and the complete algorithm is given in Algorithm 1. Figure 1 : Test errors of LeNets pruned at varying sparsity levels κ, where κ = 0 refers to the reference network trained without pruning. Our approach performs as good as the reference network across varying sparsity levels on both the models.

5. EXPERIMENTS:

We evaluate our method, SNIP, on MNIST, CIFAR-10 and Tiny-ImageNet classification tasks with a variety of network architectures. Our results show that SNIP yields extremely sparse models with minimal or no loss in accuracy across all tested architectures, while being much simpler than other state-of-the-art alternatives. We also provide clear evidence that our method prunes genuinely explainable connections rather than performing blind pruning.

Experiment setup For brevity, we define the sparsity level to be κ = (m -κ)/m • 100 (%), where m is the total number of parameters and κ is the desired number of non-zero weights. For a given sparsity level κ, the sensitivity scores are computed using a batch of 100 and 128 examples for MNIST and CIFAR experiments, respectively. After pruning, the pruned network is trained in the standard way. Specifically, we train the models using SGD with momentum of 0.9, batch size of 100 for MNIST and 128 for CIFAR experiments and the weight decay rate of 0.0005, unless stated otherwise. The initial learning rate is set to 0.1 and decayed by 0.1 at every 25k or 30k iterations for MNIST and CIFAR, respectively. Our algorithm requires no other hyperparameters or complex learning/pruning schedules as in most pruning algorithms. We spare 10% of the training data as a validation set and used only 90% for training. For CIFAR experiments, we use the standard data augmentation (i.e., random horizontal flip and translation up to 4 pixels) for both the reference and sparse models. The code can be found here: https://github.com/namhoonlee/snip-public.

5.1. PRUNING LENETS WITH VARYING LEVELS OF SPARSITY:

We first test our approach on two standard networks for pruning, LeNet-300-100 and LeNet-5-Caffe. LeNet-300-100 consists of three fully-connected (fc) layers with 267k parameters and LeNet-5-Caffe consists of two convolutional (conv) layers and two fc layers with 431k parameters. We prune the LeNets for different sparsity levels κ and report the performance in error on the MNIST image classification task. We run the experiment 20 times for each κ by changing random seeds for dataset and network initialization. The results are reported in Figure 1 .

The pruned sparse LeNet-300-100 achieves performances similar to the reference (κ = 0), only with negligible loss at κ = 90. For LeNet-5-Caffe, the performance degradation is nearly invisible. Note that our saliency measure does not require the network to be pre-trained and is computed at random initialization. Despite such simplicity, our approach prunes LeNets quickly (single-shot) and effectively (minimal accuracy loss) at varying sparsity levels.

5.2. COMPARISONS TO EXISTING APPROACHES:

What happens if we increase the target sparsity to an extreme level? For example, would a model with only 1% of the total parameters still be trainable and perform well? We test our approach for extreme sparsity levels (e.g., up to 99% sparsity on LeNet-5-Caffe) and compare with various pruning algorithms as follows: LWC (Han et al. (2015) ), DNS (Guo et (Dong et al. (2017) ). The results are summarized in Table 1 .

We achieve errors that are comparable to the reference model, degrading approximately 0.7% and 0.3% while pruning 98% and 99% of the parameters in LeNet-300-100 and LeNet-5-Caffe respectively. For slightly relaxed sparsities (i.e., 95% for LeNet-300-100 and 98% for LeNet-5-Caffe), the sparse models pruned by SNIP record better performances than the dense reference network. Considering 99% sparsity, our method efficiently finds 1% of the connections even before training, that are sufficient to learn as good as the reference network. Moreover, SNIP is competitive to other methods, yet it is unparalleled in terms of algorithm simplicity.

To be more specific, we enumerate some key points and non-trivial aspects of other algorithms and highlight the benefit of our approach. First of all, the aforementioned methods require networks to be fully trained (if not partly) before pruning. These approaches typically perform many pruning operations even if the network is well pretrained, and require additional hyperparameters (e.g., pruning frequency in Guo et al. (2016) , annealing schedule in Carreira-Perpiñán & Idelbayev ( 2018)). Some methods augment the training objective to handle pruning together with training, increasing the complexity of the algorithm (e.g., augmented Lagrangian in Carreira-Perpiñán & Idelbayev (2018), variational inference in Molchanov et al. (2017a) ). Furthermore, there are approaches designed to include architecture dependent constraints (e.g., layer-wise pruning schemes in Dong et al. (2017) ).

Compared to the above approaches, ours seems to cost almost nothing; it requires no pretraining or additional hyperparameters, and is applied only once at initialization. This means that one can easily plug-in SNIP as a preprocessor before training neural networks. Since SNIP prunes the network at the beginning, we could potentially expedite the training phase by training only the survived parameters (e.g., reduced expected FLOPs in Louizos et al. (2018) ). Notice that this is not possible for the aforementioned approaches as they obtain the maximum sparsity at the end of the process.

5.3. VARIOUS MODERN ARCHITECTURES:

In this section we show that our approach is generally applicable to more complex modern network architectures including deep convolutional, residual and recurrent ones. Specifically, our method is applied to the following models:

• AlexNet-s and AlexNet-b: Models similar to Krizhevsky et al. (2012) in terms of the number of layers and size of kernels. We set the size of fc layers to 512 (AlexNet-s) and to 1024 (AlexNet-b) to adapt for CIFAR-10 and use strides of 2 for all conv layers instead of using pooling layers. • VGG-C, VGG-D and VGG-like: Models similar to the original VGG models described in Simonyan & Zisserman (2015) . VGG-like (Zagoruyko (2015) ) is a popular variant adapted for CIFAR-10 which has one less fc layers. For all VGG models, we set the size of fc layers to 512, remove dropout layers to avoid any effect on sparsification and use batch normalization instead. • WRN-16-8, WRN-16-10 and WRN-22-8: Same models as in Zagoruyko & Komodakis (2016) . Table 2 : Pruning results of the proposed approach on various modern architectures (before → after). AlexNets, VGGs and WRNs are evaluated on CIFAR-10, and LSTMs and GRUs are evaluated on the sequential MNIST classification task. The approach is generally applicable regardless of architecture types and models and results in a significant amount of reduction in the number of parameters with minimal or no loss in performance.

• LSTM-s, LSTM-b, GRU-s, GRU-b: One layer RNN networks with either LSTM (Zaremba et al. (2014) ) or GRU (Cho et al. (2014) ) cells. We develop two unit sizes for each cell type, 128 and 256 for {•}-s and {•}-b, respectively. The model is adapted for the sequential MNIST classification task, similar to Le et al. (2015) . Instead of processing pixel-by-pixel, however, we perform rowby-row processing (i.e., the RNN cell receives each row at a time).

The results are summarized in Table 2 . Overall, our approach prunes a substantial amount of parameters in a variety of network models with minimal or no loss in accuracy (< 1%). Our pruning procedure does not need to be modified for specific architectural variations (e.g., recurrent connections), indicating that it is indeed versatile and scalable. Note that prior art that use a saliency criterion based on the weights (i.e., magnitude or Hessian based) would require considerable adjustments in their pruning schedules as per changes in the model.

We note of a few challenges in directly comparing against others: different network specifications, learning policies, datasets and tasks. Nonetheless, we provide a few comparison points that we found in the literature. On CIFAR-10, SVD prunes 97.9% of the connections in VGG-like with no loss in accuracy (ours: 97% sparsity) while SWS obtained 93.4% sparsity on WRN-16-4 but with a non-negligible loss in accuracy of 2%. There are a couple of works attempting to prune RNNs (e.g., GRU in Narang et al. (2017) and LSTM in See et al. (2016) ). Even though these methods are specifically designed for RNNs, none of them are able to obtain extreme sparsity without substantial loss in accuracy reflecting the challenges of pruning RNNs. To the best of our knowledge, we are the first to demonstrate on convolutional, residual and recurrent networks for extreme sparsities without requiring additional hyperparameters or modifying the pruning procedure.

5.4. UNDERSTANDING WHICH CONNECTIONS ARE BEING PRUNED:

So far we have shown that our approach can prune a variety of deep neural network architectures for extreme sparsities without losing much on accuracy. However, it is not clear yet which connections are actually being pruned away or whether we are pruning the right (i.e., unimportant) ones. What if we could actually peep through our approach into this inspection?

Consider the first layer in LeNet-300-100 parameterized by w l=1 ∈ R 784×300 . This is a layer fully connected to the input where input images are of size 28 × 28 = 784. In order to understand which connections are retained, we can visualize the binary connectivity mask for this layer c l=1 , by averaging across columns and then reshaping the vector into 2D matrix (i.e., c l=1 ∈ {0, 1} 784×300 → R 784 → R 28×28 ). Recall that our method computes c using a minibatch of examples. In this experiment, we curate the mini-batch of examples of the same class and see which weights are retained for that mini-batch of data. We repeat this experiment for all classes viii Published as a conference paper at ICLR 2019 (i.e., digits for MNIST and fashion items for Fashion-MNIST) with varying sparsity levels κ. The results are displayed in Figure 2 (see Appendix A for more results).

The results are significant; important connections seem to reconstruct either the complete image (MNIST) or silhouettes (Fashion-MNIST) of input class. When we use a batch of examples of the digit 0 (i.e., the first column of MNIST results), for example, the parameters connected to the foreground of the digit 0 survive from pruning while the majority of background is removed. Also, one can easily determine the identity of items from Fashion-MNIST results. This clearly indicates that our method indeed prunes the unimportant connections in performing the classification task, receiving signals only from the most discriminative part of the input. This stands in stark contrast to other pruning methods from which carrying out such inspection is not straightforward.

5.5. EFFECTS OF DATA AND WEIGHT INITIALIZATION:

Recall that our connection saliency measure depends on the network weights w as well as the given data D (Section 4.2). We study the effect of each of these in this section.

Effect of data. Our connection saliency measure depends on a mini-batch of train examples D b (see Algorithm 1). To study the effect of data, we vary the batch size used to compute the saliency (|D b |) and check which connections are being pruned as well as how much performance change this results in on the corresponding sparse network. We test with LeNet-300-100 to visualize the remaining parameters, and set the sparsity level κ = 90. Note that the batch size used for training remains the same as 100 for all cases. The results are displayed in Figure 3 .

Effect of initialization. Our approach prunes a network at a stochastic initialization as discussed.

We study the effect of the following initialization methods: 1) RN (random normal), 2) TN (truncated random normal), 3) VS-X (a variance scaling method using Glorot & Bengio (2010) ), and 4) VS-H (a variance scaling method He et al. (2015) ). We test on LeNets and RNNs on MNIST and run 20 sets of experiments by varying the seed for initialization. We set the sparsity level κ = 90, and train with Adam optimizer (Kingma & Ba (2015) ) with learning rate of 0.001 without weight decay. Note that for training VS-X initialization is used in all the cases. The results are reported in Figure 3 .

For all models, VS-H achieves the best performance. The differences between initializers are marginal on LeNets, however, variance scaling methods indeed turns out to be essential for complex RNN models. This effect is significant especially for GRU where without variance scaling initialization, the pruned networks are unable to achieve good accuracies, even with different optimizers.

Overall, initializing with a variance scaling method seems crucial to making our saliency measure reliable and model-agnostic. Table 3 : The effect of initialization on our saliency score. We report the classification errors (±std).

Variance scaling initialization (VS-X, VS-H) improves the performance, especially for RNNs. Given true labels, both the reference (red) and pruned (blue) models quickly reach to almost zero training loss. However, the reference model provided with random labels (green) also reaches to very low training loss, even with an explicit L2 regularizer (purple), indicating that neural networks have enough capacity to memorize completely random data. In contrast, the model pruned by SNIP (orange) fails to fit the random labels (high training error). The potential explanation is that the pruned network does not have sufficient capacity to fit the random labels, but it is able to classify MNIST with true labels, reinforcing the significance of our saliency criterion. It is possible that a similar experiment can be done with other pruning methods (Molchanov et al. (2017a) ), however, being simple, SNIP enables such exploration much easier. We provide a further analysis on the effect of varying κ in Appendix B.

5.6. FITTING RANDOM LABELS:



6. DISCUSSION AND FUTURE WORK:

In this work, we have presented a new approach, SNIP, that is simple, versatile and interpretable; it prunes irrelevant connections for a given task at single-shot prior to training and is applicable to a variety of neural network models without modifications. While SNIP results in extremely sparse models, we find that our connection sensitivity measure itself is noteworthy in that it diagnoses important connections in the network from a purely untrained network. We believe that this opens up new possibilities beyond pruning in the topics of understanding of neural network architectures, multi-task transfer learning and structural regularization, to name a few. In addition to these potential directions, we intend to explore the generalization capabilities of sparse networks. The effect of varying sparsity levels (κ). The lower κ becomes, the lower training loss is recorded, meaning that a network with more parameters is more vulnerable to fitting random labels. Recall, however, that all pruned models are able to learn to perform the classification task without losing much accuracy (see Figure 1 ). This potentially indicates that the pruned network does not have sufficient capacity to fit the random labels, but it is capable of performing the classification.

C TINY-IMAGENET Table 4 : Pruning results of SNIP on Tiny-ImageNet (before → after). Tiny-ImageNet2 is a subset of the full ImageNet: there are 200 classes in total, each class has 500 and 50 images for training and validation respectively, and each image has the spatial resolution of 64×64. Compared to CIFAR-10, resolution is doubled, and to deal with this, the stride of the first convolution in all architectures is doubled, following the standard practice for this dataset. In general, the Tiny-ImageNet classification task is considered much more complex than MNIST or CIFAR-10. Even on Tiny-ImageNet, however, SNIP is still able to prune a large amount of parameters with minimal loss in performance. AlexNet models lose more accuracies than VGGs, which may be attributed to the fact that the first convolution stride for AlexNet is set to be 4 (by its design of no pooling) which is too large and could lead to high loss of information when pruned.

:

Multiplicative coefficients (similar to c) were also used for subset regression inBreiman (1995).

https://tiny-imagenet.herokuapp.com/

Figures and Tables:

SNIP: Single-shot Network Pruning based on Connection Sensitivity Require: Loss function L, training dataset D, sparsity level κ Refer Equation 3 Ensure: w * 0 ≤ κ 1: w ← VarianceScalingInitialization Refer Section 4.2 2: D b = {(x i , y i )} b i=1 ∼ D Sample a mini-batch of training data 3: s j ← |gj(w;D b )| m k=1 |g k (w;D b )| , ∀j ∈ {1 . . . m} Connection sensitivity 4: s ← SortDescending(s) 5: c j ← 1[s j -sκ ≥ 0] , ∀ j ∈ {1 . . . m} Pruning: choose top-κ connections 6: w * ← arg min w∈R m L(c w; D)

Figure 2: Visualizations of pruned parameters of the first layer in LeNet-300-100; the parameters are reshaped to be visualized as an image. Each column represents the visualizations for a particular class obtained using a batch of 100 examples with varying levels of sparsity κ, from 10 (top) to 90 (bottom). Bright pixels indicate that the parameters connected to these region had high importance scores (s) and survived from pruning. As the sparsity increases, the parameters connected to the discriminative part of the image for classification survive and the irrelevant parts get pruned.

Figure 3: The effect of different batch sizes: (top-row) survived parameters in the first layer of LeNet-300-100 from pruning visualized as images; (bottom-row) the performance in errors of the pruned networks. For |D b | = 1, the sampled example was 8; our pruning precisely retains the valid connections. As |D b | increases, survived parameters get close to the average of all examples in the train set (last column), and the error decreases.

Figure 4: The sparse model pruned by SNIP does not fit the random labels.

Figure 5: Results of pruning with SNIP on inverted (Fashion-)MNIST (i.e., dark and bright regions are swapped). Notably, even if the data is inverted, the results are the same as the ones on the original (Fashion-)MNIST in Figure 2.

Figure6: Results of pruning with ∂L/∂w on the original and inverted (Fashion-)MNIST. Notably, compared to the case of using SNIP (Figures2 and 5), the results are different: Firstly, the results on the original (Fashion-)MNIST (i.e., (a) and (c) above) are not the same as the ones using SNIP (i.e., (a) and (b) in Figure2). Moreover, the pruning patterns are inconsistent with different sparsity levels, either intra-class or inter-class. Furthermore, using ∂L/∂w results in different pruning patterns between the original and inverted data in some cases (e.g., the 2 nd columns between (c) and (d)).

al. (2016)), LC (Carreira-Perpiñán & Pruning results on LeNets and comparisons to other approaches. Here, "many" refers to an arbitrary number often in the order of total learning steps, and "soft" refers to soft pruning in Bayesian based methods. Our approach is capable of pruning up to 98% for LeNet-300-100 and 99% for LeNet-5-Caffe with marginal increases in error from the reference network. Notably, our approach is considerably simpler than other approaches, with no requirements such as pretraining, additional hyperparameters, augmented training objective or architecture dependent constraints.

Table content: <table><tr><td>Method</td><td>Criterion</td><td colspan="2">LeNet-300-100 κ (%) err. (%)</td><td colspan="2">LeNet-5-Caffe κ (%) err. (%)</td><td>Pretrain</td><td># Prune</td><td colspan="3">Additional Augment hyperparam. objective constraints Arch.</td></tr><tr><td>Ref.</td><td>-</td><td>-</td><td>1.7</td><td>-</td><td>0.9</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>LWC</td><td>Magnitude</td><td>91.7</td><td>1.6</td><td>91.7</td><td>0.8</td><td/><td>many</td><td/><td/><td/></tr><tr><td>DNS</td><td>Magnitude</td><td>98.2</td><td>2.0</td><td>99.1</td><td>0.9</td><td/><td>many</td><td/><td/><td/></tr><tr><td>LC</td><td>Magnitude</td><td>99.0</td><td>3.2</td><td>99.0</td><td>1.1</td><td/><td>many</td><td/><td/><td/></tr><tr><td>SWS</td><td>Bayesian</td><td>95.6</td><td>1.9</td><td>99.5</td><td>1.0</td><td/><td>soft</td><td/><td/><td/></tr><tr><td>SVD</td><td>Bayesian</td><td>98.5</td><td>1.9</td><td>99.6</td><td>0.8</td><td/><td>soft</td><td/><td/><td/></tr><tr><td>OBD</td><td>Hessian</td><td>92.0</td><td>2.0</td><td>92.0</td><td>2.7</td><td/><td>many</td><td/><td/><td/></tr><tr><td>L-OBS</td><td>Hessian</td><td>98.5</td><td>2.0</td><td>99.0</td><td>2.1</td><td/><td>many</td><td/><td/><td/></tr><tr><td>SNIP (ours)</td><td>Connection sensitivity</td><td>95.0 98.0</td><td>1.6 2.4</td><td>98.0 99.0</td><td>0.8 1.1</td><td/><td>1</td><td/><td/><td/></tr><tr><td colspan="11">Idelbayev (2018)), SWS (Ullrich et al. (2017)), SVD (Molchanov et al. (2017a)), OBD (LeCun et al.</td></tr><tr><td colspan="2">(1990)), L-OBS</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 Post rebuttal update/comment: I thank the authors for the revision and have updated the score (twice!) One genuinely perplexing result to me is that the method behaves better than random pruning, yet after selecting the salient neurons the weights can be reinitialized, as per the rebuttal: > # Initialization procedure - It is correct that the weights used to train the pruned model are possibly different from the ones used to compute the connection sensitivity. Given (variance scaled) initial weights, SNIP finds the architecturally important parameters in the network, then the pruned network is established and trained in the standard way. First, there is work which states quite the opposite (e.g. https://arxiv.org/abs/1803.03635). Please relate to it. Fundamentally, if you decouple weight pruning from initialization it also means that: - the first layer will be pruned out of connections to constant pixels (which is seen in the visualizations), this remains meaningful even after a reinitialization - the second and higher layers will be pruned somewhat randomly - even if the connections pruned were meaningful with the original weights, after the reinitialization the functions computed by the neurons in lower layers will be different, and have no relation to pruned weights. Thus the pruning will be essentially random (though possibly from a very specific random distribution). In other words - then neurons in a fully connected layer can be freely swapped, each neuron in the next layer behaves on al of them anyway we are thinking here about the uninitialized neurons, with each of them having a distribution over weights and not a particular set of sampled weights, this is valid because we will reinitialize the neurons). Because of that, I wouldn*t call any particular weight/connection architecturally important and find it strange that such weights are found. I find this behavior really perplexing, but I trust that your experiments are correct. however, please, if you have the time, verify it. Original review: The paper presents an intriguing result in which a salient, small subset of weights can be selected even in untrained networks given sensible initialization defaults are used. This result is surprising - the usual network pruning procedure assumed that a network is pretrained, and only then important connections are removed. The contributions of the paper are two-fold: 1) it reintroduces a multiplicative sensitivity measure similar to the Breiman garotte 2) and shows which other design choices are needed to make it work on untrained networks, which is surprising. While the main idea of the paper is clear and easy to intuitively understand, the details are not. My main concern is that paper differentiates between weights and connections (both terms are introduced on page iv to differentiate from earlier work). However, it is not clear what are the authors referring to: - a conv layer has many repeated applications of the same weight. Am I correct to assume that a conv layer has many more connections, than weights? Furthermore, are the dramatic sparsities demonstrated over connections counted in this manner? This is important - on MNIST each digit has a constant zero border, all connections to the border are not needed and can be trivially removed (one can crop the images to remove them for similar results). Thus we can trivially remove connections, without removing weights. - in paragraph 5.5 different weight initialization schemes are used for the purpose of saliency estimation, but the paragraph then says "Note that for training VS-X initialization is used in all the cases." Does it mean that first a set of random weights is sampled, then the sensitivities are computed, then a salient set of connections is established and the weights are REINITIALIZED from a distribution possibly different than the one used to compute the sensitivity? The fact that it works is very surprising and again suggests that the method identifies constant background pixels rather than important weights. - on the other hand, if there is a one-to-one correspondence between connections and weights, then the differentiation from Karnin (1990) at the bottom of p. iv is misleading. I would also be cautious about extrapolating results from MNIST to other vision datasets. MNIST has dark backgrounds. Let f(w,c) = 0*w*c. Trivially, df/dw = df/dc = 0. Thus the proposed sensitivity measure picks non-background pixels, which is also demonstrated in figure 2. However, this is a property of the dataset (which encodes background with 0) and not of the method! This should be further investigated - a quick check is to invert MNIST (make the images black-on-white, not white-on-black) and see if the method still works. Fashion MNIST behaves in a similar way. Thus the only non-trvial experiments are the ones on CIFAR10 (Table 2), but the majority of the analysis is conducted on white-on-black MNIST and Fashion-MNIST. Finally, no experiment shows the benefit of introducing the variables "c", rather than using the gradient with respect to the weights. let f be the function computed by the network. Then: - df/d(cw) is the gradient passed to the weights if the "c" variables were not introduced - df/dw = df/d(cw) d(cw)/dw = df/d(cw) * c = df/d(cw) - df/dc = df/d(cw) d(cw)/dc = df/d(cw) * w Thus the proposed change seems to favor a combination of weight magnitude and the regular df/dw magnitude. I*d like to see how using the regular df/dw criterion would fare in single-shot pruning. In particular, I expect using the plain gradient to lead to similar selections to those in Figure 2, because for constant pixels 0 = df/d(cw) = df/dc = df/dw. Suggested corrections: In related work (sec. 2) it is pointed that Hessian-based methods are unpractical due to the size od the Hessian. In fact OBD uses a diagonal approximation to the hessian, which is computed with complexity similar to the gradient, although it is typically not supported by deep learning toolkits. Please correct. The description of weight initialization schemes should also be corrected (sec. 4.2). The sentence "Note that initializing neural networks is a random process, typically done using normal distribution with zero mean and a fixed variance." is wrong and artificially inflates the paper*s contribution. Variance normalizing schemes had been known since the nineties (see efficient backprop) and are the default in many toolkits, e.g. Pytorch uses the Kaiming rule which sets the standard deviation according to the fan-in: https://github.com/pytorch/pytorch/blob/master/torch/nn/modules/linear.py#L56. Please enumerate the datasets (MNIST, Fashion-MNIST, CIFAR10) in the abstract, rather than saying "vision datasets", because MNIST in particular is not representative of vision datasets due to the constant zero padding, as explained before. Missing references: - Efficient Backprop http://yann.lecun.com/exdb/publis/pdf/lecun-98b.pdf discusses variance scaling initialization, and approximations to the hessian. Since both are mentioned in the text this should be cited as well. - the Breiman non-negative garotte (https://www.jstor.org/stable/1269730) is a similar well-known technique in statistics Finally, I liked the paper and wanted to give it a higher score, but reduced it because of the occurrence of many broad claims made in the paper, such as: 1) method works on MNIST => abstract claims it generally works on vision datasets 2) paper states "typically used is fixed variance init", but the popular toolkits (pytorch, keras) actually use the variance scaling one by default 3) the badly explained distinction between connection and weight and the relation that it implies to prior work. I will revise the score if these claims are corrected.