What are the differences between zero-order and first-order methods for neural network pruning?
Pruning methods focus on identifying and re- moving unimportant weights from the model. Zero- order methods and first-order methods are widely used to prune PLMs. For zero-order methods, mag- nitude pruning (Han et al., 2015) simply prunes based on absolute value of their weights. For first-order methods, which are based on first-order Taylor expansion to make pruning decision, L0 regularization (Louizos et al., 2017) adds the L0 norm regularization to decrease remaining weights by sampling them with hard-concrete distribution. Movement pruning (Sanh et al., 2020) uses straight- through estimator (Bengio et al., 2013) to calculate first-order informantion.
Learning both Weights and Connections for Efficient Neural Networks
Neural networks are both computationally intensive and memory intensive, making them difficult to deploy on embedded systems. Also, conventional networks fix the architecture before training starts; as a result, training cannot improve the architecture. To address these limitations, we describe a method to reduce the storage and computation required by neural networks by an order of magnitude without affecting their accuracy, by learning only the important connections. Our method prunes redundant connections using a three-step method. First, we train the network to learn which connections are important. Next, we prune the unimportant connections. Finally, we retrain the network to fine tune the weights of the remaining connections. On the ImageNet dataset, our method reduced the number of parameters of AlexNet by a factor of 9x, from 61 million to 6.7 million, without incurring accuracy loss. Similar experiments with VGG16 found that the network as a whole can be reduced by 13x, again with no loss of accuracy.
[{"first":"Song","last":"Han","middle":[]},{"first":"Jeff","last":"Pool","middle":[]},{"first":"John","last":"Tran","middle":[]},{"first":"William","last":"Dally","middle":["J."]}]
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Magnitude pruning is a widely used strategy for reducing model size in pure supervised learning; however, it is less effective in the transfer learning regime that has become standard for state-of-the-art natural language processing applications. We propose the use of movement pruning, a simple, deterministic first-order weight pruning method that is more adaptive to pretrained model fine-tuning. We give mathematical foundations to the method and compare it to existing zeroth- and first-order pruning methods. Experiments show that when pruning large pretrained language models, movement pruning shows significant improvements in high-sparsity regimes. When combined with distillation, the approach achieves minimal accuracy loss with down to only 3% of the model parameters.
[{"first":"Victor","last":"Sanh","middle":[]},{"first":"Thomas","last":"Wolf","middle":[]},{"first":"Alexander","last":"Rush","middle":["M."]}]
Learning Sparse Neural Networks through $L_0$ Regularization
We propose a practical method for $L_0$ norm regularization for neural networks: pruning the network during training by encouraging weights to become exactly zero. Such regularization is interesting since (1) it can greatly speed up training and inference, and (2) it can improve generalization. AIC and BIC, well-known model selection criteria, are special cases of $L_0$ regularization. However, since the $L_0$ norm of weights is non-differentiable, we cannot incorporate it directly as a regularization term in the objective function. We propose a solution through the inclusion of a collection of non-negative stochastic gates, which collectively determine which weights to set to zero. We show that, somewhat surprisingly, for certain distributions over the gates, the expected $L_0$ norm of the resulting gated weights is differentiable with respect to the distribution parameters. We further propose the \emph{hard concrete} distribution for the gates, which is obtained by"stretching"a binary concrete distribution and then transforming its samples with a hard-sigmoid. The parameters of the distribution over the gates can then be jointly optimized with the original network parameters. As a result our method allows for straightforward and efficient learning of model structures with stochastic gradient descent and allows for conditional computation in a principled way. We perform various experiments to demonstrate the effectiveness of the resulting approach and regularizer.
[{"first":"Christos","last":"Louizos","middle":[]},{"first":"Max","last":"Welling","middle":[]},{"first":"Diederik","last":"Kingma","middle":["P."]}]
Pruning Pre-trained Language Models Without Fine-Tuning
To overcome the overparameterized problem in Pre-trained Language Models (PLMs), pruning is widely used as a simple and straightforward compression method by directly removing unimportant weights. Previous first-order methods successfully compress PLMs to extremely high sparsity with little performance drop. These methods, such as movement pruning, use first-order information to prune PLMs while fine-tuning the remaining weights. In this work, we argue fine-tuning is redundant for first-order pruning, since first-order pruning is sufficient to converge PLMs to downstream tasks without fine-tuning. Under this motivation, we propose Static Model Pruning (SMP), which only uses first-order pruning to adapt PLMs to downstream tasks while achieving the target sparsity level. In addition, we also design a new masking function and training objective to further improve SMP. Extensive experiments at various sparsity levels show SMP has significant improvements over first-order and zero-order methods. Unlike previous first-order methods, SMP is also applicable to low sparsity and outperforms zero-order methods. Meanwhile, SMP is more parameter efficient than other methods due to it does not require fine-tuning.
[{"first":"Ting","last":"Jiang","middle":[]},{"first":"Deqing","last":"Wang","middle":[]},{"first":"Fuzhen","last":"Zhuang","middle":[]},{"first":"Ruobing","last":"Xie","middle":[]},{"first":"Feng","last":"Xia","middle":[]}]
Learning both Weights and Connections for Efficient Neural Networks
Neural networks have become ubiquitous in applications ranging from computer vision [1] to speech recognition [2] and natural language processing [3]. We consider convolutional neural networks used for computer vision tasks which have grown over time. In 1998 Lecun classified handwritten digits with less than 1M parameters [4], while in 2012, Krizhevsky et al. [1] won the ImageNet competition with 60M parameters. Deepface classified human faces with 120M parameters [5], and Coates et al. [6] scaled up a network to 10B parameters.
Learning both Weights and Connections for Efficient Neural Networks
While these large neural networks are very powerful, their size consumes considerable storage, memory bandwidth, and computational resources. For embedded mobile applications, these resource demands become prohibitive. Figure 1 shows the energy cost of basic arithmetic and memory operations in a 45nm CMOS process [7]. From this data we see the energy per connection is dominated by memory access and ranges from 3.5pJ for 32b coefficients in on-chip SRAM to 640pJ for 32b coefficients in off-chip LPDDR2 DRAM. Large networks do not fit in on-chip storage and hence require the more costly DRAM accesses. Running a 1G connection neural network, for example, at 20Hz would require (20Hz)(1G)(640pJ) = 12.8W just for DRAM access -well beyond the power envelope of a typical mobile device. Our goal in pruning networks is to reduce the energy required to run such large networks so they can be run in real time on mobile devices.
Learning both Weights and Connections for Efficient Neural Networks
To achieve this goal, we present a method to prune network connections in a manner that preserves the original accuracy. After an initial training phase, we remove all connections whose weight is lower than a threshold. This pruning converts a dense, fully-connected layer to a sparse layer. This first phase learns the topology of the networks -learning which connections are important and removing the unimportant connections. We then retrain the sparse network so the remaining connections can compensate for the connections that have been removed. The phases of pruning and retraining may be repeated iteratively to further reduce network complexity. In effect, this training process learns  Figure 1: Pyramid shaped energy table: memory access is 3 orders of magnitude more energy expensive the network connectivity in addition to the weights -much as in the mammalian brain [8] [9], where synapses are created in the first few months of a child's development, followed by gradual pruning of little-used connections, falling to typical adult values.
Learning both Weights and Connections for Efficient Neural Networks
Our pruning method employs a three-step process, as illustrated in Figure 2, which begins by learning the connectivity via normal network training. Unlike conventional training, however, we are not learning the final values of the weights, but rather we are learning which connections are important.
Learning both Weights and Connections for Efficient Neural Networks
Prune Connections Train Weights The second step is to prune the low-weight connections. All connections with weights below a threshold are removed from the network -converting a dense network into a sparse network, as shown in Figure 3.
Learning both Weights and Connections for Efficient Neural Networks
The final step retrains the network to learn the final weights for the remaining sparse connections. This step is critical, however, if the pruned network is used without retraining, accuracy is significantly impacted.
Learning both Weights and Connections for Efficient Neural Networks
Choosing the correct regularization impacts the performance of pruning and retraining. L1 regularization penalizes non-zero parameters resulting in more parameters near zero. This gives better accuracy after pruning, but before retraining. However, the remaining connections are not as good as with L2 regularization, resulting in lower accuracy after retraining.
Learning both Weights and Connections for Efficient Neural Networks
Dropout is widely used to prevent over-fitting, and this also applies to retraining. During retraining, however, the dropout ratio must be adjusted to account for the change in model capacity. Hinton's dropout [19] can be regarded as a "soft dropout," since each parameter is dropped with a probability, not definitely dropped out. Pruning can be regarded as a "hard dropout," where parameters are dropped forever after pruning and have no chance to come back. As the parameters get sparse, the classifier will select the most informative predictors and thus have much less prediction variance, which reduces over-fitting. As pruning already reduced model capacity, the retraining dropout ratio should be smaller.
Learning both Weights and Connections for Efficient Neural Networks
Quantitatively, let C i be the number of connections in layer i, C io for the original network, C ir for the network after retraining, N i be the number of neurons in layer i. Since dropout works on neurons, and the C i has a square relationship with the N i , according to equation 1 thus the dropout ratio after pruning the parameters should follow equation 2, where D o represent the original dropout rate, D r represent the dropout rate during retraining.
Learning both Weights and Connections for Efficient Neural Networks
During retraining, it is better to retain the weights from the initial training phase for the connections that survived pruning than it is to re-initialize the pruned layers. [25] shows that CNNs contain fragile co-adapted features: gradient descent is able to find a good solution when the network is initially trained, but not after re-initializing some layers and retraining them. So if we re-initialize the pruned layer, we have to retrain the whole network; if we retrain just the pruned layers, we need to retrain while retaining the surviving parameters.
Learning both Weights and Connections for Efficient Neural Networks
Retraining the pruned layers starting with retained weights requires less computation because we don't have to back propagate through the entire network. Also, neural networks are prone to suffer the vanishing gradient problem [26] as the networks get deeper, which makes pruning errors harder to recover for deep networks. To prevent this, we fix the parameters for part of the network and only retrain a shallow network by reusing the surviving parameters, which already co-adapted well with the un-pruned layers during initial training.
Learning both Weights and Connections for Efficient Neural Networks
Learning the right connections is an iterative process. Pruning followed by a retraining is one iteration, after many such iterations the minimum number connections could be found. Without loss of accuracy, this method can boost pruning rate from 5× to 9× on AlexNet compared with single-step aggressive pruning. Each iteration is a greedy search in that we find the best connections. We also experimented with probabilistically pruning parameters based on their absolute value, but this gave worse results.
Learning both Weights and Connections for Efficient Neural Networks
After pruning connections, neurons with zero input connections or zero output connections may be safely pruned. This pruning is furthered by removing all connections to or from a pruned neuron. The retraining phase automatically arrives at the result where dead neurons will have both zero input connections and zero output connections. This occurs due to gradient descent and regularization.
Learning both Weights and Connections for Efficient Neural Networks
A neuron that has zero input connections(or zero output connections) will have no contribution to the final loss, leading the gradient to be zero for its output connection(or input connection), respectively. Only the regularization term will push the weights to zero. Thus the dead neurons will be automatically removed during retraining.
Learning both Weights and Connections for Efficient Neural Networks
We implemented network pruning on Caffe [27]. Caffe was modified to add a mask for all the weight tensors, which disregards pruned parameters during network operation. The pruning threshold is chosen as a quality parameter multiplied by the standard deviation of a layer's weights. We carried out the experiments on Nvidia TitanX and GTX980 GPUs.
Learning both Weights and Connections for Efficient Neural Networks
We pruned 4 networks: 2 on MNIST and 2 on ImageNet datasets. The network parameters and accuracy 1 before and after pruning are shown in Table 1. 
Learning both Weights and Connections for Efficient Neural Networks
We first experimented on MNIST dataset with LeNet-300-100 and LeNet-5 network [4]. LeNet-300-100 is a fully connected network with two hidden layers, with 300 and 100 neurons each, which achieves 1.6% error rate on Mnist. LeNet-5 is a convolutional network that has two convolutional layers and two fully connected layers, which achieves 0.8% error rate on Mnist. After pruning, the network is retrained with 1/10 of the original network's original learning rate.    An interesting byproduct of network pruning is that it detects visual attention regions. Figure 4 shows the sparsity pattern of the first fully connected layer of LeNet-300-100, which is of size 784 * 300 (the image size is 28 by 28 and the hidden layer size is 300). It has a banded structure with 28 bands, each band is of size 28, corresponding to the 28 × 28 input pixels. The colored regions of the figure, which means non-zero parameters, correspond to the center of the image. Because digits are written in the center of the image, these are the important parameters. The graph is sparse on the left and right as well, corresponding to the less important regions on the top and bottom of the image. After pruning, the neural network finds the center of the image more important, and the connections to the peripheral regions are more heavily pruned.
Learning both Weights and Connections for Efficient Neural Networks
We further examine the performance of pruning on the ImageNet ILSVRC-2012 dataset, which has 1.2M training examples and 50k validation examples. We use the AlexNet Caffe model as the reference model, which has 61 million parameters across 5 convolutional layers and 3 fully connected layers. The AlexNet Caffe model achieved a top-1 accuracy of 57.2% and a top-5 accuracy of 80.3%. The original AlexNet took 450K iterations to train [27]. After pruning, the whole network is retrained with 1/100 of the original network's initial learning rate. 900K and 700K iterations were required to retrain the fully connected and convolutional layers, respectively. Table 1 shows that AlexNet can be    Table 5: Saving break down for each layer of AlexNet. Pruning finds the essential connections, reducing weights to 11% and computation to 30%. Most of the parameter savings come from the fully connected layers pruned to 1/9 of its original size without impacting accuracy and computation can be reduced by 3×.
Learning both Weights and Connections for Efficient Neural Networks
The pruning is most effective on the fully-connected layers.
Learning both Weights and Connections for Efficient Neural Networks
We experimented with L1 and L2 regularization before and after retraining, together with iterative pruning to give the five accuracy v.s parameter trade off curves shown in Figure 5. The green and dotted purple lines show the importance of retraining the network after pruning. The purple line shows the accuracy of the network after pruning but before retraining. Without retraining we can still prune the network considerably: half of AlexNet could be pruned without impacting the accuracy much. However, accuracy begins dropping much sooner -with 1/3 of the original connections, rather than with 1/10 of the original connections. Without retraining we are only able to reduce the number of connections by 2× before losing accuracy, while with retraining we are ably to reduce connections by 9×.   Figure 5: Trade-off curve for parameter reduction and loss in top-5 accuracy. L1 regularization performs better than L2 at learning the connections without retraining, while L2 regularization performs better than L1 at retraining. Iterative pruning gives the best result L1 regularization gives better accuracy than L2 directly after pruning (dotted blue and purple lines) since it pushes more parameters closer to zero. However, comparing the yellow and green lines shows that L2 outperforms L1 after retraining, since there is no benefit to further pushing values towards zero. One extension is to use L1 regularization for pruning and then L2 for retraining, but this did not beat simply using L2 for both phases. Parameters from one mode do not adapt well to the other.
Learning both Weights and Connections for Efficient Neural Networks
The biggest gain comes from iterative pruning (solid red line with solid circles). Here we take the pruned and retrained network (solid green line with circles) and prune and retrain it again. The leftmost dot on this curve corresponds to the point on the green line at 80% (5× pruning) pruned to 8×. There's no accuracy loss at 9×. Not until 10× does the accuracy begin to drop.
Learning both Weights and Connections for Efficient Neural Networks
Two points achieve slightly better accuracy than the original model after pruning and retraining 2 . We believe this small accuracy improvement is due to pruning reducing the capacity of the network and hence reducing overfitting.
Learning both Weights and Connections for Efficient Neural Networks
Both fully connected layers and convolutional layers can be pruned. Fully connected layers occupy the majority of the parameters and could be pruned as much as (11×) compared to convolution layers (3×). The details of pruning each layer are shown in Table 5.
Learning both Weights and Connections for Efficient Neural Networks
Network pruning not only saves parameter's memory access but also saves floating point operations, given appropriate hardware support. If either the weight or the activation is zero, the multiply and add operations can be saved. An estimation of computation savings assumes independent distribution of non-zero weights and non-zero activations. The FLOP column is derived by multiplying the non-zero parameter ratio of the current layer with the non-zero activation ratio of the previous layer, since the input of this layer is the output of the previous layer. Although fully connected layer has more parameters and parameter savings, the convolutional layers are more computationally intensive. Thus, the FLOP savings is determined by the convolutional layers, which is 3×.   Figure 6 shows the sensitivity of each layer to network pruning. The figure shows how accuracy suffers as parameters are pruned on a layer-by-layer basis. The convolutional layers (on the left) are more sensitive to pruning than the fully connected layers (on the right). The first convolutional layer, which interacts with the input image directly, is most sensitive to pruning. We suspect this sensitivity is due to the input layer having only 3 channels and thus less redundancy than the other convolutional layers. We used these results to find each layer's threshold. The smallest threshold was applied to the most sensitive layer, which is the first convolutional layer, etc. 
Learning both Weights and Connections for Efficient Neural Networks
With promising results on AlexNet, we also looked at a larger, more recent network, VGG16 [30], on the same ILSVRC-2012 dataset. VGG16 has far more convolutional layers but still only three fully-connected layers. Following a similar methodology, we aggressively pruned both convolutional and fully-connected layers to realize a significant reduction in the number of weights, shown in Table 6. Specifically, we used five iterations of pruning on the pre-trained network from Caffe. The VGG16 results are, like those for AlexNet, very promising. The network as a whole has been reduced to 7.5% of its original size. In particular, note that the two largest fully-connected layers can each be pruned to less than 4% of their original size. This reduction is critical for real time image processing, where there is little reuse of these layers across images (unlike batch processing). The reduced layers will fit in an on-chip SRAM and have modest bandwidth requirements. Without the reduction the bandwidth requirements are prohibitive.
Learning both Weights and Connections for Efficient Neural Networks
We have presented a method to improve the efficiency of neural networks without affecting accuracy by finding the right connections. Our method, motivated in part by how learning works in the mammalian brain, operates by learning which connections are important, pruning the unimportant connections, and then retraining the remaining sparse network. We highlight our experiments on AlexNet on ImageNet, showing that both fully connected layer and convolutional layer can be pruned, reducing the number of connections by 9× without loss of accuracy. We show similar results for VGG16 and LeNet networks got pruned by 13× without accuracy loss. This leads to smaller memory capacity and bandwidth requirements for real-time image processing.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Large-scale transfer learning has become ubiquitous in deep learning and achieves state-of-the-art performance in applications in natural language processing and related fields. In this setup, a large model pretrained on a massive generic dataset is then fine-tuned on a smaller annotated dataset to perform a specific end-task. Model accuracy has been shown to scale with the pretrained model and dataset size [Raffel et al., 2019]. However, significant resources are required to ship and deploy these large models, and training the models have high environmental costs [Strubell et al., 2019].
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Sparsity induction is a widely used approach to reduce the memory footprint of neural networks at only a small cost of accuracy. Pruning methods, which remove weights based on their importance, are a particularly simple and effective method for compressing models to be sent to edge devices such as mobile phones. Magnitude pruning [Han et al., 2015[Han et al., , 2016, which preserves weights with high absolute values, is the most widely used method for weight pruning. It has been applied to a large variety of architectures in computer vision [Guo et al., 2016], in language processing [Gale et al., 2019], and more recently has been leveraged as a core component in the lottery ticket hypothesis [Frankle et al., 2019].
Movement Pruning: Adaptive Sparsity by Fine-Tuning
While magnitude pruning is highly effective for standard supervised learning, it is inherently less useful in the transfer learning regime. In supervised learning, weight values are primarily determined by the end-task training data. In transfer learning, weight values are mostly predetermined by the original model and are only fine-tuned on the end task. This prevents these methods from learning to prune based on the fine-tuning step, or "fine-pruning."
Movement Pruning: Adaptive Sparsity by Fine-Tuning
In this work, we argue that to effectively reduce the size of models for transfer learning, one should instead use movement pruning, i.e., pruning approaches that consider the changes in weights during fine-tuning. Movement pruning differs from magnitude pruning in that both weights with low and high values can be pruned if they shrink during training. This strategy moves the selection criteria from the 0th to the 1st-order and facilitates greater pruning based on the fine-tuning objective. To test this approach, we introduce a particularly simple, deterministic version of movement pruning utilizing the straight-through estimator [Bengio et al., 2013].
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We apply movement pruning to pretrained language representations (BERT) [Devlin et al., 2019, Vaswani et al., 2017 on a diverse set of fine-tuning tasks. In highly sparse regimes (less than 15% of remaining weights), we observe significant improvements over magnitude pruning and other 1st-order methods such as L 0 regularization [Louizos et al., 2017]. Our models reach 95% of the original BERT performance with only 5% of the encoder's weight on natural language inference (MNLI) [Williams et al., 2018] and question answering (SQuAD v1.1) [Rajpurkar et al., 2016]. Analysis of the differences between magnitude pruning and movement pruning shows that the two methods lead to radically different pruned models with movement pruning showing greater ability to adapt to the end-task.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Magnitude pruning can be seen as utilizing zeroth-order information (absolute value) of the running model. In this work, we focus on movement pruning methods where importance is derived from first-order information. Intuitively, instead of selecting weights that are far from zero, we retain connections that are moving away from zero during the training process. We consider two versions of movement pruning: hard and soft.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
For (hard) movement pruning, masks are computed using the Top v function: M = Top v (S). Unlike magnitude pruning, during training, we learn both the weights W and their importance scores S. During the forward pass, we compute for all i, a i = n k=1 W i,k M i,k x k . Since the gradient of Top v is 0 everywhere it is defined, we follow Ramanujan et al. [2020], Mallya and Lazebnik [2018] and approximate its value with the straight-through estimator [Bengio et al., 2013]. In the backward pass, Top v is ignored and the gradient goes "straight-through" to S. The approximation of gradient of the loss L with respect to S i,j is given by
Movement Pruning: Adaptive Sparsity by Fine-Tuning
This implies that the scores of weights are updated, even if these weights are masked in the forward pass. We prove in Appendix A.1 that movement pruning as an optimization problem will converge.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We also consider a relaxed (soft) version of movement pruning based on the binary mask function described by Mallya and Lazebnik [2018]. Here we replace hyperparameter v with a fixed global threshold value τ that controls the binary mask. The mask is calculated as M = (S > τ ). In order to control the sparsity level, we add a regularization term R(S) = λ mvp i,j σ(S i,j ) which encourages the importance scores to decrease over time 1 . The coefficient λ mvp controls the penalty intensity and thus the sparsity level.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Finally we note that these approaches yield a similar update L 0 regularization based pruning, another movement based pruning approach [Louizos et al., 2017]. Instead of straight-through, L 0 uses the hard-concrete distribution, where the mask M is sampled for all i, j with hyperparameters b > 0, l < 0, and r > 1:
Movement Pruning: Adaptive Sparsity by Fine-Tuning
The expected L 0 norm has a closed form involving the parameters of the hard-concrete: an end-to-end fashion to minimize the sum of the training loss L and the expected L 0 penalty. A coefficient λ l0 controls the L 0 penalty and indirectly the sparsity level. Gradients take a similar form:
Movement Pruning: Adaptive Sparsity by Fine-Tuning
At test time, a non-stochastic estimation of the mask is used:M = min 1, ReLU (r − l)σ(S) + l and weights multiplied by 0 can simply be discarded. Table 1 highlights the characteristics of each pruning method. The main differences are in the masking functions, pruning structure, and the final gradient form.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
In movement pruning, the gradient of L with respect to W i,j is given by the standard gradient derivation: ∂L ∂Wi,j = ∂L ∂ai M i,j x j . By combining it to Eq (2), we have ∂L ∂Si,j = ∂L ∂Wi,j W i,j (we omit the binary mask term M i,j for simplicity). From the gradient update in Eq (2), S i,j is increasing when ∂L ∂Si,j < 0, which happens in two cases:
Movement Pruning: Adaptive Sparsity by Fine-Tuning
It means that during training W i,j is increasing while being positive or is decreasing while being negative. It is equivalent to saying that S i,j is increasing when W i,j is moving away from 0. Inversely, S i,j is decreasing when ∂L ∂Si,j > 0 which means that W i,j is shrinking towards 0. While magnitude pruning selects the most important weights as the ones which maximize their distance to 0 (|W i,j |), movement pruning selects the weights which are moving the most away from 0 (S i,j ). For this reason, magnitude pruning can be seen as a 0th order method, whereas movement pruning is based on a 1st order signal. In fact, S can be seen as an accumulator of movement: from equation (2), after T gradient updates, we have Figure 1 shows this difference empirically by comparing weight values during fine-tuning against their pre-trained value. As observed by Gordon et al. [2020], fine-tuned weights stay close in absolute value to their initial pre-trained values. For magnitude pruning, this stability around the pre-trained values implies that we know with high confidence before even fine-tuning which weights will be pruned as the weights with the smallest absolute value at pre-training will likely stay small and be pruned. In contrast, in movement pruning, the pre-trained weights do not have such an awareness of the pruning decision since the selection is made during fine-tuning (moving away from 0), and both low and high values can be pruned. We posit that this is critical for the success of the approach as it is able to prune based on the task-specific data, not only the pre-trained value.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Transfer learning for NLP uses large pre-trained language models that are fine-tuned on target tasks [Ruder et al., 2019, Devlin et al., 2019, Radford et al., 2019]. We experiment with taskspecific pruning of BERT-base-uncased, a pre-trained model that contains roughly 84M parameters. We freeze the embedding modules and fine-tune the transformer layers and the task-specific head.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We perform experiments on three monolingual (English) tasks, which are common benchmarks for the recent progress in transfer learning for NLP: question answering (SQuAD v1.1) [Rajpurkar et al., 2016], natural language inference (MNLI) [Williams et al., 2018], and sentence similarity (QQP) [Iyer et al., 2017]. The datasets respectively contain 8K, 393K, and 364K training examples. SQuAD is formulated as a span extraction task, MNLI and QQP are paired sentence classification tasks.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
For a given task, we fine-tune the pre-trained model for the same number of updates (between 6 and 10 epochs) across pruning methods 2 . We follow Zhu and Gupta [2018] and use a cubic sparsity scheduling for Magnitude Pruning (MaP), Movement Pruning (MvP), and Soft Movement Pruning (SMvP). Adding a few steps of cool-down at the end of pruning empirically improves the performance especially in high sparsity regimes. The schedule for v is:
Movement Pruning: Adaptive Sparsity by Fine-Tuning
where t f is the number of cool-down steps.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We compare our results against several state-of-the-art pruning baselines: Reweighted Proximal Pruning (RPP)  combines re-weighted L 1 minimization and Proximal Projection [Parikh and Boyd, 2014] to perform unstructured pruning. LayerDrop [Fan et al., 2020a] leverages structured dropout to prune models at test time. For RPP and LayerDrop, we report results from authors. We also compare our method against the mini-BERT models, a collection of smaller BERT models with varying hyper-parameters [Turc et al., 2019].
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Figure 2 displays the results for the main pruning methods at different levels of pruning on each dataset. First, we observe the consistency of the comparison between magnitude and movement pruning: at low sparsity (more than 70% of remaining weights), magnitude pruning outperforms all methods with little or no loss with respect to the dense model whereas the performance of movement pruning methods quickly decreases even for low sparsity levels. However, magnitude pruning performs poorly with high sparsity, and the performance drops extremely quickly. In contrast, first-order methods show strong performances with less than 15% of remaining weights. Table 2 shows the specific model scores for different methods at high sparsity levels. Magnitude pruning on SQuAD achieves 54.5 F1 with 3% of the weights compared to 73.6 F1 with L 0 regularization, 76.3 F1 for movement pruning, and 79.9 F1 with soft movement pruning. These experiments indicate that in high sparsity regimes, importance scores derived from the movement accumulated during fine-tuning induce significantly better pruned models compared to absolute values.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Next, we compare the difference in performance between first-order methods. We see that straightthrough based hard movement pruning (MvP) is comparable with L 0 regularization (with a significant gap in favor of movement pruning on QQP). Soft movement pruning (SMvP) consistently outperforms Figure 2: Comparisons between different pruning methods in high sparsity regimes. Soft movement pruning consistently outperforms other methods in high sparsity regimes. We plot the performance of the standard fine-tuned BERT along with 95% of its performance. hard movement pruning and L 0 regularization by a strong margin and yields the strongest performance among all pruning methods in high sparsity regimes. These comparisons support the fact that even if movement pruning (and its relaxed version soft movement pruning) is simpler than L 0 regularization, it yet yields stronger performances for the same compute budget.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Finally, movement pruning and soft movement pruning compare favorably to the other baselines, except for QQP where RPP is on par with soft movement pruning. Movement pruning also outperforms the fine-tuned mini-BERT models. This is coherent with [Li et al., 2020]: it is both more efficient and more effective to train a large model and compress it afterward than training a smaller model from scratch. We do note though that current hardware does not support optimized inference for sparse models: from an inference speed perspective, it might often desirable to use a small dense model such as mini-BERT over a sparse alternative of the same size.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Distillation further boosts performance Following previous work, we can further leverage knowledge distillation [Bucila et al., 2006, Hinton et al., 2014 Figure 4: Magnitude pruning and movement pruning leads to pruned models with radically different weight distribution.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
loss on the output distributions. Figure 3 shows the results on SQuAD, MNLI, and QQP for the three pruning methods boosted with distillation. Overall, we observe that the relative comparisons of the pruning methods remain unchanged while the performances are strictly increased. Table 3 shows for instance that on SQuAD, movement pruning at 10% goes from 81.7 F1 to 84.3 F1. When combined with distillation, soft movement pruning yields the strongest performances across all pruning methods and studied datasets: it reaches 95% of BERT-base with only a fraction of the weights in the encoder (∼5% on SQuAD and MNLI).
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Movement pruning is adaptive Figure 4a compares the distribution of the remaining weights for the same matrix of a model pruned at the same sparsity using magnitude and movement pruning. We observe that by definition, magnitude pruning removes all the weights that are close to zero, ending up with two clusters. In contrast, movement pruning leads to a smoother distribution, which covers the whole interval except for values close to 0.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Figure 4b displays each individual weight against its associated importance score in movement pruning. We plot pruned weights in grey. We observe that movement pruning induces no simple relationship between the scores and the weights. Both weights with high absolute value or low absolute value can be considered important. However, high scores are systematically associated with non-zero weights (and thus the "v-shape"). This is coherent with the interpretation we gave to the scores (section 4): a high score S indicates that during fine-tuning, the associated weight moved away from 0 and is thus non-null.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Local and global masks perform similarly We study the influence of the locality of the pruning decision. While local Top v selects the v% most important weights matrix by matrix, global Top v uncovers non-uniform sparsity patterns in the network by selecting the v% most important weights in Figure 5: Comparison of local and global selections of weights on SQuAD at different sparsity levels. For magnitude and movement pruning, local and global Top v performs similarly at all levels of sparsity. Figure 6: Remaining weights per layer in the Transformer. Global magnitude pruning tends to prune uniformly layers. Global 1st order methods allocate the weight to the lower layers while heavily pruning the highest layers.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
the whole network. Previous work has shown that a non-uniform sparsity across layers is crucial to the performance in high sparsity regimes [He et al., 2018]. In particular, Mallya and Lazebnik [2018] found that the sparsity tends to increase with the depth of the network layer. Figure 5 compares the performance of local selection (matrix by matrix) against global selection (all the matrices) for magnitude pruning and movement pruning. Despite being able to find a global sparsity structure, we found that global did not significantly outperform local, except in high sparsity regimes (2.3 F1 points of difference with 3% of remaining weights for movement pruning). Even though the distillation signal boosts the performance of pruned models, the end performance difference between local and global selections remains marginal. Figure 6 shows the remaining weights percentage obtained per layer when the model is pruned until 10% with global pruning methods. Global weight pruning is able to allocate sparsity non-uniformly through the network, and it has been shown to be crucial for the performance in high sparsity regimes [He et al., 2018]. We notice that except for global magnitude pruning, all the global pruning methods tend to allocate a significant part of the weights to the lowest layers while heavily pruning in the highest layers. Global magnitude pruning tends to prune similarly to local magnitude pruning, i.e., uniformly across layers.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We consider the case of pruning of pretrained models for task-specific fine-tuning and compare zeroth-and first-order pruning methods. We show that a simple method for weight pruning based on straight-through gradients is effective for this task and that it adapts using a first-order importance score. We apply this movement pruning to a transformer-based architecture and empirically show that our method consistently yields strong improvements over existing methods in high-sparsity regimes. The analysis demonstrates how this approach adapts to the fine-tuning regime in a way that magnitude pruning cannot. In future work, it would also be interesting to leverage group-sparsity inducing penalties [Bach et al., 2011] to remove entire columns or filters. In this setup, we would associate a score to a group of weights (a column or a row for instance). In the transformer architecture, it would give a systematic way to perform feature selection and remove entire columns of the embedding matrix.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
A.1 Guarantees on the decrease of the training loss
Movement Pruning: Adaptive Sparsity by Fine-Tuning
As the scores are updated, the relative order of the importances is likely shuffled, and some connections will be replaced by more important ones. Under certain conditions, we are able to formally prove that as these replacements happen, the training loss is guaranteed to decrease. Our proof is adapted from [Ramanujan et al., 2020] to consider the case of fine-tuable W.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We suppose that (a) the training loss L is smooth and admits a first-order Taylor development everywhere it is defined and (b) the learning rate of W (α W > 0) is small. We define the TopK function as the analog of the Top v function, where k is an integer instead of a proportion. We first consider the case where k = 1 in the TopK masking, meaning that only one connection is remaining (and the other weights are deactivated/masked). Let's denote W i,j this sole remaining connection at step t. Following Eq (1), it means that ∀1 ≤ u, v ≤ n, S
Movement Pruning: Adaptive Sparsity by Fine-Tuning
i,j . We suppose that at step t + 1, connections are swapped and the only remaining connection at step t + 1 is (k, l). We have:
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Eq (6) gives the following inequality: S
Movement Pruning: Adaptive Sparsity by Fine-Tuning
i,j . After re-injecting the gradient update in Eq (2), we have:
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Moreover, the conditions in Eq (6) lead to the following inferences: a
Movement Pruning: Adaptive Sparsity by Fine-Tuning
k )|| 2 is also small. Because the training loss L is smooth, we can write the 1st order Taylor development of L in point (a 
Movement Pruning: Adaptive Sparsity by Fine-Tuning
The first term is null because of inequalities (6) and the second term is negative because of inequality (7). Thus L(a
Movement Pruning: Adaptive Sparsity by Fine-Tuning
k ): when connection (k, l) becomes more important than (i, j), the connections are swapped and the training loss decreases between step t and t + 1.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Similarly, we can generalize the proof to a set E = { (a i , b i ), (c i , d i ) ; i ≤ N } of N swapping connections.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We note that this proof is not specific to the TopK masking function. In fact, we can extend the proof using the Threshold masking function M := (S >= τ ) [Mallya and Lazebnik, 2018]. Inequalities (6) are still valid and the proof stays unchanged.
Movement Pruning: Adaptive Sparsity by Fine-Tuning
Last, we note these guarantees do not hold if we consider the absolute value of the scores |S i,j | (as it is done in Ding et al. [2019] for instance). We prove it by contradiction. If it was the case, it would also be true one specific case: the negative threshold masking function (M := (S < τ ) where τ < 0).
Movement Pruning: Adaptive Sparsity by Fine-Tuning
We suppose that at step t + 1, the only remaining connection (i, j) is replaced by (k, l):
Movement Pruning: Adaptive Sparsity by Fine-Tuning
The inequality on the gradient update becomes: −α S ∂L ∂a k W (t) k,l x l < −α S ∂L ∂ai W i,j x j and following the same development as in Eq (8) We proved by contradiction that the guarantees on the decrease of the loss do not hold if we consider the absolute value of the score as a proxy for importance.
Learning Sparse Neural Networks through $L_0$ Regularization
Deep neural networks are flexible function approximators that have been very successful in a broad range of tasks. They can easily scale to millions of parameters while allowing for tractable optimization with mini-batch stochastic gradient descent (SGD), graphical processing units (GPUs) and parallel computation. Nevertheless they do have drawbacks. Firstly, it has been shown in recent works (Han et al., 2015; that they are greatly overparametrized as they can be pruned significantly without any loss in accuracy; this exhibits unnecessary computation and resources. Secondly, they can easily overfit and even memorize random patterns in the data (Zhang et al., 2016), if not properly regularized. This overfitting can lead to poor generalization in practice.
Learning Sparse Neural Networks through $L_0$ Regularization
A way to address both of these issues is by employing model compression and sparsification techniques. By sparsifying the model, we can avoid unnecessary computation and resources, since irrelevant degrees of freedom are pruned away and do not need to be computed. Furthermore, we reduce its complexity, thus penalizing memorization and alleviating overfitting.
Learning Sparse Neural Networks through $L_0$ Regularization
A conceptually attractive approach is the L 0 norm regularization of (blocks of) parameters; this explicitly penalizes parameters for being different than zero with no further restrictions. However, the combinatorial nature of this problem makes for an intractable optimization for large models.
Learning Sparse Neural Networks through $L_0$ Regularization
In this paper we propose a general framework for surrogate objectives to L 0 regularization. It is realized by smoothing the expected L 0 norm with continuous distributions in a way that can maintain the exact zeros in the parameters while still allowing for efficient gradient based optimization. This Figure 1: L p norm penalties for a parameter θ according to different values of p. It is easily observed that both weight decay and Lasso, p = 2 and p = 1 respectively, impose shrinkage for large values of θ. By gradually allowing p < 1 we observe that the shrinkage is reduced and at the limit of p = 0 we observe that the penalty is a constant for θ = 0.
Learning Sparse Neural Networks through $L_0$ Regularization
is achieved by transforming continuous random variables (r.v.s) with a hard nonlinearity, the hardsigmoid. We further propose and employ a novel distribution obtained by this procedure; the hard concrete. It is obtained by "stretching" a binary concrete random variable (Maddison et al., 2016;Jang et al., 2016) and then passing its samples through a hard-sigmoid. We demonstrate the effectiveness of this simple procedure in various experiments.
Learning Sparse Neural Networks through $L_0$ Regularization
2 MINIMIZING THE L 0 NORM OF PARAMETRIC MODELS One way to sparsify parametric models, such as deep neural networks, with the least assumptions about the parameters is the following; let D be a dataset consisting of N i.i.d. input output pairs {(x 1 , y 1 ), . . . , (x N , y N )} and consider a regularized empirical risk minimization procedure with an L 0 regularization on the parameters θ of a hypothesis (e.g. a neural network) h(·; θ):
Learning Sparse Neural Networks through $L_0$ Regularization
where |θ| is the dimensionality of the parameters, λ is a weighting factor for the regularization and L(·) corresponds to a loss function, e.g. cross-entropy loss for classification or mean-squared error for regression. The L 0 norm penalizes the number of non-zero entries of the parameter vector and thus encourages sparsity in the final estimates θ * . The Akaike Information Criterion (AIC) (Akaike, 1998) and the Bayesian Information Criterion (BIC) (Schwarz et al., 1978), well-known model selection criteria, correspond to specific choices of λ. Notice that the L 0 norm induces no shrinkage on the actual values of the parameters θ; this is in contrast to e.g. L 1 regularization and the Lasso (Tibshirani, 1996), where the sparsity is due to shrinking the actual values of θ. We provide a visualization of this effect in Figure 1.
Learning Sparse Neural Networks through $L_0$ Regularization
Unfortunately, optimization under this penalty is computationally intractable due to the nondifferentiability and combinatorial nature of 2 |θ| possible states of the parameter vector θ. How can we relax the discrete nature of the L 0 penalty such that we allow for efficient continuous optimization of Eq. 1, while allowing for exact zeros in the parameters? This section will present the necessary details of our approach.
Learning Sparse Neural Networks through $L_0$ Regularization
Consider the L 0 norm under a simple re-parametrization of θ:
Learning Sparse Neural Networks through $L_0$ Regularization
where the z j correspond to binary "gates" that denote whether a parameter is present and the L 0 norm corresponds to the amount of gates being "on". By letting q(z j |π j ) = Bern(π j ) be a Bernoulli distribution over each gate z j we can reformulate the minimization of Eq. 1 as penalizing the number of parameters being used, on average, as follows:
Learning Sparse Neural Networks through $L_0$ Regularization
where corresponds to the elementwise product. The objective described in Eq. 3 is in fact a special case of a variational bound over the parameters involving spike and slab (Mitchell & Beauchamp, 1988) priors and approximate posteriors; we refer interested readers to appendix A. While the second term of the r.h.s. of Eq. 3 is straightforward to minimize, the first term is problematic for π due to the discrete nature of z, which precludes efficient gradient based optimization. While in principle gradient estimators such as the REINFORCE (Williams, 1992) estimator or the straight-through (Bengio et al., 2013) estimator could be employed, they suffer from high variance and biased gradients respectively. Nevertheless, it should be mentioned that there is encouraging work on improving upon the high variance gradients of REINFORCE with control variates (Mnih & Gregor, 2014;Mnih & Rezende, 2016;Tucker et al., 2017), which however usually requires multiple evaluations of the model.
Learning Sparse Neural Networks through $L_0$ Regularization
Fortunately, there is an alternative way to smooth the objective such that we allow for efficient gradient based optimization of the expected L 0 norm along with zeros in the parameters θ in a simple way. Let s be a continuous random variable with a distribution q(s) that has parameters φ. We can now let the gates z be given by a hard-sigmoid rectification of s 1 , as follows:
Learning Sparse Neural Networks through $L_0$ Regularization
This would then allow the gate to be exactly zero and, due to the underlying continuous random variable s, we can still compute the probability of the gate being non-zero (active). This is easily obtained by the cumulative distribution function (CDF) Q(·) of s:
Learning Sparse Neural Networks through $L_0$ Regularization
i.e. it is the probability of the s variable being positive. We can thus smooth the binary Bernoulli gates z appearing in Eq. 3 by employing continuous distributions in the aforementioned way:
Learning Sparse Neural Networks through $L_0$ Regularization
Notice that this is a close surrogate to the original objective function in Eq. 3, as we similarly have a cost that explicitly penalizes the probability of a gate being different from zero. Now for continuous distributions q(s) that allow for the reparameterization trick (Kingma & Welling, 2014;Rezende et al., 2014) we can express the objective in Eq. 7 as an expectation over a parameter free noise distribution p( ) and a deterministic and differentiable transformation f (·) of the parameters φ and :
Learning Sparse Neural Networks through $L_0$ Regularization
which allows us to make the following Monte Carlo approximation to the (generally) intractable expectation over the noise distribution p( ):
Learning Sparse Neural Networks through $L_0$ Regularization
where z (l) = g(f (φ, (l) )) and (l) ∼ p( ).
Learning Sparse Neural Networks through $L_0$ Regularization
L E corresponds to the error loss that measures how well the model is fitting the current dataset whereas L C refers to the complexity loss that measures the flexibility of the model. Crucially, the cost in Eq. 9 is now differentiable w.r.t. φ, thus allowing for efficient stochastic gradient based optimization, while still allowing for exact zeros at the gates. One price we pay is that now the gradient of the log-likelihood w.r.t. the parameters φ of q(s) is sparse due to the rectifications; nevertheless this should not pose an issue considering the prevalence of rectified linear units in neural networks. Furthermore, due to the stochasticity at s the hard-sigmoid gate z is smoothed to a soft version on average, thus allowing for gradient based optimization to succeed, even when the mean of s is negative or larger than one. An example visualization can be seen in Figure 2b. It should be noted that a similar argument was also shown at Bengio et al. (2013), where with logistic noise a rectifier nonlinearity was smoothed to a softplus 2 on average.
Learning Sparse Neural Networks through $L_0$ Regularization
The framework described in Section 2.1 gives us the freedom to choose an appropriate smoothing distribution q(s). A choice that seems to work well in practice is the following; assume that we have a binary concrete (Maddison et al., 2016;Jang et al., 2016) random variable s distributed in the (0, 1) interval with probability density q s (s|φ) and cumulative density Q s (s|φ). The parameters of the distribution are φ = (log α, β), where log α is the location and β is the temperature. We can "stretch" this distribution to the (γ, ζ) interval, with γ < 0 and ζ > 1, and then apply a hard-sigmoid on its random samples:
Learning Sparse Neural Networks through $L_0$ Regularization
This would then induce a distribution where the probability mass of qs(s|φ) on the negative values, Qs(0|φ), is "folded" to a delta peak at zero, the probability mass on values larger than one, 1 − Qs(1|φ), is "folded" to a delta peak at one and the original distribution qs(s|φ) is truncated to the (0, 1) range. We provide more information and the density of the resulting distribution at the appendix.
Learning Sparse Neural Networks through $L_0$ Regularization
Notice that a similar behavior would have been obtained even if we passed samples from any other distribution over the real line through a hard-sigmoid. The only requirement of the approach is that we can evaluate the CDF ofs at 0 and 1. The main reason for picking the binary concrete is its close ties with Bernoulli r.v.s. It was originally proposed at Maddison et al. (2016); Jang et al.
Learning Sparse Neural Networks through $L_0$ Regularization
(2016) as a smooth approximation to Bernoulli r.vs, a fact that allows for gradient based optimization of its parameters through the reparametrization trick. The temperature β controls the degree of approximation, as with β = 0 we can recover the original Bernoulli r.v. (but lose the differentiable properties) whereas with 0 < β < 1 we obtain a probability density that concentrates its mass near the endpoints (e.g. as shown in Figure 2a). As a result, the hard concrete also inherits the same theoretical properties w.r.t. the Bernoulli distribution. Furthermore, it can serve as a better approximation of the discrete nature, since it includes {0, 1} in its support, while still allowing for (sub)gradient optimization of its parameters due to the continuous probability mass that connects those two values. We can also view this distribution as a "rounded" version of the original binary concrete, where values larger than 1−γ ζ−γ are rounded to one whereas values smaller than −γ ζ−γ are rounded to zero. We provide an example visualization of the hard concrete distribution in Figure 2a.
Learning Sparse Neural Networks through $L_0$ Regularization
The L 0 complexity loss of the objective in Eq. 9 under the hard concrete r.v. is conveniently expressed as follows:
Learning Sparse Neural Networks through $L_0$ Regularization
At test time we use the following estimator for the final parameters θ * under a hard concrete gate: Figure 2: (a) The binary concrete distribution with location log α = 0 and temperature β = 0.5 and the hard concrete equivalent distribution obtained by stretching the concrete distribution to (γ = −0.1, ζ = 1.1) and then applying a hard-sigmoid. Under this specification the hard concrete distribution assigns, roughly, half of its mass to {0, 1} and the rest to (0, 1). (b) The expected value of the afforementioned concrete and hard concrete gate as a function of the location log α, obtained by averaging 10000 samples. We also added the value of the gates obtained by removing the noise entirely. We can see that the noise smooths the hard-sigmoid to a sigmoid on average.
Learning Sparse Neural Networks through $L_0$ Regularization
While the L 0 norm leads to sparse estimates without imposing any shrinkage on θ it might still be desirable to impose some form of prior assumptions on the values of θ with alternative norms, e.g. impose smoothness with the L 2 norm (i.e. weight decay). In the following we will show how this combination is feasible for the L 2 norm. The expected L 2 norm under the Bernoulli gating mechanism can be conveniently expressed as:
Learning Sparse Neural Networks through $L_0$ Regularization
where π j corresponds to the success probability of the Bernoulli gate z j . To maintain a similar expression with our smoothing mechanism, and avoid extra shrinkage for the gates z j , we can take into account that the standard L 2 norm penalty is proportional to the negative log density of a zero mean Gaussian prior with a standard deviation of σ = 1. We will then assume that the σ for each θ is governed by z in a way that when z = 0 we have that σ = 1 and when z > 0 we have that σ = z. As a result, we can obtain the following expression for the L 2 penalty (whereθ = θ σ ):
Learning Sparse Neural Networks through $L_0$ Regularization
2.4 GROUP SPARSITY UNDER AN L 0 NORM For reasons of computational efficiency it is usually desirable to perform group sparsity instead of parameter sparsity, as this can allow for practical computation savings. For example, in neural networks speedups can be obtained by employing a dropout (Srivastava et al., 2014) like procedure with neuron sparsity in fully connected layers or feature map sparsity for convolutional layers (Wen et al., 2016;Louizos et al., 2017;Neklyudov et al., 2017). This is straightforward to do with hard concrete gates; simply share the gate between all of the members of the group. The expected L 0 and, according to section 2.3, L 2 penalties in this scenario can be rewritten as:
Learning Sparse Neural Networks through $L_0$ Regularization
where |G| corresponds to the number of groups and |g| corresponds to the number of parameters of group g. For all of our subsequent experiments we employed neuron sparsity, where we introduced a gate per input neuron for fully connected layers and a gate per output feature map for convolutional layers. Notice that in the interpretation we adopt the gate is shared across all locations of the feature map for convolutional layers, akin to spatial dropout (Tompson et al., 2015). This can lead to practical computation savings while training, a benefit which is not possible with the commonly used independent dropout masks per spatial location (e.g. as at Zagoruyko & Komodakis (2016)).
Learning Sparse Neural Networks through $L_0$ Regularization
Compression and sparsification of neural networks has recently gained much traction in the deep learning community. The most common and straightforward technique is parameter / neuron pruning (LeCun et al., 1990) according to some criterion. Whereas weight pruning (Han et al., 2015; is in general inefficient for saving computation time, neuron pruning (Wen et al., 2016;Louizos et al., 2017;Neklyudov et al., 2017) can lead to computation savings. Unfortunately, all of the aforementioned methods require training the original dense network thus precluding the benefits we can obtain by having exact sparsity on the computation during training. This is in contrast to our approach where sparsification happens during training, thus theoretically allowing conditional computation to speed-up training (Bengio et al., 2013;.
Learning Sparse Neural Networks through $L_0$ Regularization
Emulating binary r.v.s with rectifications of continuous r.v.s is not a new concept and has been previously done with Gaussian distributions in the context of generative modelling (Hinton & Ghahramani, 1997;Harva & Kabán, 2007;Salimans, 2016) and with logistic distributions at (Bengio et al., 2013) in the context of conditional computation. These distributions can similarly represent the value of exact zero, while still maintaining the tractability of continuous optimization. Nevertheless, they are sub-optimal when we require approximations to binary r.v.s (as is the case for the L 0 penalty); we cannot represent the bimodal behavior of a Bernoulli r.v. due to the fact that the underlying distribution is unimodal. Another technique that allows for gradient based optimization of discrete r.v.s are the smoothing transformations proposed by Rolfe (2016). There the core idea is that if a model has binary latent variables, then we can smooth them with continuous noise in a way that allows for reparametrization gradients. There are two main differences with the hard concrete distribution we employ here; firstly, the double rectification of the hard concrete r.v.s allows us to represent the values of exact zero and one (instead of just zero) and, secondly, due to the underlying concrete distribution the random samples from the hard concrete will better emulate binary r.v.s.
Learning Sparse Neural Networks through $L_0$ Regularization
We validate the effectiveness of our method on two tasks. The first corresponds to the toy classification task of MNIST using a simple multilayer perceptron (MLP) with two hidden layers of size 300 and 100 (LeCun et al., 1998), and a simple convolutional network, the LeNet-5-Caffe 3 . The second corresponds to the more modern task of CIFAR 10 and CIFAR 100 classification using Wide Residual Networks (Zagoruyko & Komodakis, 2016). For all of our experiments we set γ = −0.1, ζ = 1.1 and, following the recommendations from Maddison et al. (2016), set β = 2/3 for the concrete distributions. We initialized the locations log α by sampling from a normal distribution with a standard deviation of 0.01 and a mean that yields α α+1 to be approximately equal to the original dropout rate employed at each of the networks. We used a single sample of the gate z for each minibatch of datapoints during the optimization, even though this can lead to larger variance in the gradients (Kingma et al., 2015). In this way we show that we can obtain the speedups in training with practical implementations, without actually hurting the overall performance of the network.
Learning Sparse Neural Networks through $L_0$ Regularization
For these experiments we did no further regularization besides the L 0 norm and optimization was done with Adam (Kingma & Ba, 2014) using the default hyper-parameters and temporal averaging. We can see at Table 1 that our approach is competitive with other methods that tackle neural network compression. However, it is worth noting that all of these approaches prune the network post-training using thresholds while requiring training the full network. We can further see that our approach minimizes the amount of parameters more at layers where the gates affect a larger part of the cost; for the MLP this corresponds to the input layer whereas for the LeNet5 this corresponds to the first fully connected layer. In contrast, the methods with sparsity inducing priors (Louizos et al., 2017;Neklyudov et al., 2017) sparsify parameters irrespective of that extra cost (since they are only encouraged by the prior to move parameters to zero) and as a result they achieve similar sparsity on all of the layers. Nonetheless, it should be mentioned that we can in principle increase the sparsification on specific layers simply by specifying a separate λ for each layer, e.g. by increasing the λ for gates that affect less parameters. We provide such results at the "λ sep." rows.  3-12-192-500 1.0 SBP (Neklyudov et al., 2017) 3-18-284-283 0.9 BC-GNJ (Louizos et al., 2017) 8-13-88-13 1.0 BC-GHS (Louizos et al., 2017) 5-10-76-16 1.0 L 0 hc , λ = 0.1/N 20-25-45-462 0.9 L 0 hc , λ sep. 9-18-65-25 1.0
Learning Sparse Neural Networks through $L_0$ Regularization
To get a better idea about the potential speedup we can obtain in training we plot in Figure 3 the expected, under the probability of the gate being active, floating point operations (FLOPs) as a function of the training iterations. We also included the theoretical speedup we can obtain by using dropout (Srivastava et al., 2014) networks. As we can observe, our L 0 minimization procedure that is targeted towards neuron sparsity can potentially yield significant computational benefits compared to the original or dropout architectures, with minimal or no loss in performance. We further observe that there is a significant difference in the flop count for the LeNet model between the λ = 0.1/N and λ sep. settings. This is because we employed larger values for λ (10/N and 0.5/N ) for the convolutional layers (which contribute the most to the computation) in the λ sep. setting. As a result, this setting is more preferable when we are concerned with speedup, rather than network compression (which is affected only by the number of parameters).
Learning Sparse Neural Networks through $L_0$ Regularization
For WideResNets we apply L 0 regularization on the weights of the hidden layer of the residual blocks, i.e. where dropout is usually employed. We also employed an L 2 regularization term as described in Section 2.3 with the weight decay coefficient used in Zagoruyko & Komodakis (2016). For the layers with the hard concrete gates we divided the weight decay coefficient by 0.7 to ensure that  a-priori we assume the same length-scale as the 0.3 dropout equivalent network. For optimization we employed the procedure described in Zagoruyko & Komodakis (2016) with a minibatch of 128 datapoints, which was split between two GPUs, and used a single sample for the gates for each GPU.   As we can observe at Table 2, with a λ of 0.001/N the L 0 regularized wide residual network improves upon the accuracy of the dropout equivalent network on both CIFAR 10 and CIFAR 100. Furthermore, it simultaneously allows for potential training time speedup due to gradually decreasing the number of FLOPs, as we can see in Figure 4. Finally, we observe that by further increasing λ we obtain a model that has a slight error increase but can allow for a larger speedup.
Learning Sparse Neural Networks through $L_0$ Regularization
We have described a general recipe that allows for optimizing the L 0 norm of parametric models in a principled and effective manner. The method is based on smoothing the combinatorial problem with continuous distributions followed by a hard-sigmoid. To this end, we also proposed a novel distribution which we coin as the hard concrete; it is a "stretched" binary concrete distribution, the samples of which are transformed by a hard-sigmoid. This in turn better mimics the binary nature of Bernoulli distributions while still allowing for efficient gradient based optimization. In experiments we have shown that the proposed L 0 minimization process leads to neural network sparsification that is competitive with current approaches while theoretically allowing for speedup in training. We have further shown that this process can provide a good inductive bias and regularizer, as on the CIFAR experiments with wide residual networks we improved upon dropout.
Learning Sparse Neural Networks through $L_0$ Regularization
As for future work; better harnessing the power of conditional computation for efficiently training very large neural networks with learned sparsity patterns is a potential research direction. It would be also interesting to adopt a full Bayesian treatment over the parameters θ, such as the one employed at ; Louizos et al. (2017). This would then allow for further speedup and compression due to the ability of automatically learning the bit precision of each weight. Finally, it would be interesting to explore the behavior of hard concrete r.v.s at binary latent variable models, since they can be used as a drop in replacement that allow us to maintain both the discrete nature as well as the efficient reparametrization gradient optimization. 
Learning Sparse Neural Networks through $L_0$ Regularization
The objective function described in Eq. 3 is in fact a special case of a variational lower bound over the parameters of the network under a spike and slab (Mitchell & Beauchamp, 1988) prior. The spike and slab distribution is the golden standard in sparsity as far as Bayesian inference is concerned and it is defined as a mixture of a delta spike at zero and a continuous distribution over the real line (e.g. a standard normal):
Learning Sparse Neural Networks through $L_0$ Regularization
Since the true posterior distribution over the parameters under this prior is intractable, we will use variational inference (Beal, 2003). Let q(θ, z) be a spike and slab approximate posterior over the parameters θ and gate variables z, where we assume that it factorizes over the dimensionality of the parameters θ. It turns out that we can write the following variational free energy under the spike and slab prior and approximate posterior over a parameter vector θ:
Learning Sparse Neural Networks through $L_0$ Regularization
KL(q(z j )||p(z j ))+ + |θ| j=1 q(z j = 1)KL(q(θ j |z j = 1)||p(θ j |z j = 1))+ + q(z j = 0)KL(q(θ j |z j = 0)||p(θ j |z j = 0))
Learning Sparse Neural Networks through $L_0$ Regularization
where the last step is due to KL(q(θ j |z j = 0)||p(θ j |z j = 0)) = 0 4 . The term that involves KL(q(z j )||p(z j )) corresponds to the KL-divergence from the Bernoulli prior p(z j ) to the Bernoulli approximate posterior q(z j ) and KL(q(θ j |z j = 1)||p(θ j |z j = 1)) can be interpreted as the "code cost" or else the amount of information the parameter θ j contains about the data D, measured by the KL-divergence from the prior p(θ j |z j = 1).
Learning Sparse Neural Networks through $L_0$ Regularization
Now consider making the assumption that we are optimizing, rather than integrating, over θ and further assuming that KL(q(θ j |z j = 1)||p(θ j |z j = 1)) = λ. We can justify this assumption from an empirical Bayesian procedure: there is a hypothetical prior for each parameter p(θ j |z j = 1) that adapts to q(θ j |z j = 1) in a way that results into needing, approximately, λ nats to transform p(θ j |z j = 1) to that particular q(θ j |z j = 1). Those λ nats are thus the amount of information the q(θ j |z j = 1) can encode about the data had we used that p(θ j |z j = 1) as the prior. Notice that under this view we can consider λ as the amount of flexibility of that hypothetical prior; with λ = 0 we have a prior that is flexible enough to represent exactly q(θ j |z j = 1), thus resulting into no code cost and possible overfitting. Under this assumption the variational free energy can be re-written as:
Learning Sparse Neural Networks through $L_0$ Regularization
whereθ corresponds to the optimized θ and the last step is due to the positivity of the KL-divergence. Now by taking the negative log-probability of the data to be equal to the loss L(·) of Eq. 1 we see that Eq. 22 is the same as Eq. 3. Note that in case that we are interested over the uncertainty of the gates z, we should optimize Eq. 21, rather than Eq. 22, as this will properly penalize the entropy of q(z). Furthermore, Eq. 21 also allows for the incorporation of prior information about the behavior of the gates (e.g. gates being active 10% of the time, on average). We have thus shown that the expected L 0 minimization procedure is in fact a close surrogate to a variational bound involving a spike and slab distribution over the parameters and a fixed coding cost for the parameters when the gates are active.
Learning Sparse Neural Networks through $L_0$ Regularization
As mentioned in the main text, the hard concrete is a straightforward modification of the binary concrete (Maddison et al., 2016;Jang et al., 2016); let q s (s|φ) be the probability density function (pdf) and Q s (s|φ) the cumulative distribution function (CDF) of a binary concrete random variable s:
Learning Sparse Neural Networks through $L_0$ Regularization
Q s (s|φ) = Sigmoid((log s − log(1 − s))β − log α).
Learning Sparse Neural Networks through $L_0$ Regularization
Now by stretching this distribution to the (γ, ζ) interval, with γ < 0 and ζ > 1 we obtains = s(ζ − γ) + γ with the following pdf and CDF:
Learning Sparse Neural Networks through $L_0$ Regularization
and by further rectifyings with the hard-sigmoid, z = min(1, max(0,s)), we obtain the following distribution over z: q(z|φ) = Qs(0|φ)δ(z) + (1 − Qs(1|φ))δ(z − 1) + (Qs(1|φ) − Qs(0|φ))qs(z|s ∈ (0, 1), φ),
Learning Sparse Neural Networks through $L_0$ Regularization
which is composed by a delta peak at zero with probability Qs(0|φ), a delta peak at one with probability 1 − Qs(1|φ), and a truncated version of qs(s|φ) in the (0, 1) range.
Learning Sparse Neural Networks through $L_0$ Regularization
In case th 21 is to be optimized with a hard concrete q(z) then we have to compute the KL-divergence from a prior p(z) to q(z). It is necessary for the prior p(z) to have the same support as q(z) in order for the KL-divergence to be valid; as a result we can let the prior p(z) similarly be a hard-sigmoid transformation of an arbitrary continuous distribution p(s) with CDF Ps(s): p(z) = Ps(0)δ(z) + (1 − Ps(1))δ(z − 1) + (Ps(1) − Ps(0))ps(z|s ∈ (0, 1))
Learning Sparse Neural Networks through $L_0$ Regularization
Since both q(z) and p(z) are mixtures with the same number of components we can use the chain rule of relative entropy (Cover & Thomas, 2012;Hershey & Olsen, 2007) in order to compute the KL-divergence:
Learning Sparse Neural Networks through $L_0$ Regularization
KL(q(z)||p(z)) = Qs(0) log Qs(0) Ps(0) + (1 − Qs(1)) log 1 − Qs(1) 1 − Ps(1) + + (Qs(1) − Qs(0)) E qs(z|s∈(0,1)) [log qs(z) − log ps(z)],
Learning Sparse Neural Networks through $L_0$ Regularization
wheres corresponds to the the pre-rectified variable. Notice that in case that the integral under the truncated distribution q(s|s ∈ (0, 1)) is not available in closed form we can still obtain a Monte Carlo estimate by sampling the truncated distribution, on e.g. a (γ, ζ) interval, via the inverse transform method:
Learning Sparse Neural Networks through $L_0$ Regularization
u ∼ U(0, 1), z = Q −1 s Qs(γ) + u(Qs(ζ) − Qs(γ)) ,
Learning Sparse Neural Networks through $L_0$ Regularization
where Q −1 s (·) corresponds to the quantile function and Qs(·) to the CDF of the random variables. Furthermore, it should be mentioned that KL(q(z)||p(z)) = KL(q(s)||p(s)), since the rectifications are not invertible transformations.
Pruning Pre-trained Language Models Without Fine-Tuning
Pre-trained Language Models (PLMs) like BERT (Devlin et al., 2019) have shown powerful performance in natural language processing by transferring the knowledge from large-scale corpus to downstream tasks. These models also require large-scale parameters to cope with the large-scale corpus in pretraining. However, these large-scale parameters are overwhelming for most downstream tasks , which † Corresponding Author. results in significant overhead for transferring and storing them.
Pruning Pre-trained Language Models Without Fine-Tuning
To compress PLM, pruning is widely used by removing unimportant weights and setting them to zeros. By using sparse subnetworks instead of the original complete network, existing pruning methods can maintain the original accuracy by removing most weights. Magnitude pruning (Han et al., 2015) as a common method uses zeroth-order information to make pruning decisions based on the absolute value of weights. However, in the process of adapting to downstream tasks, the weight values in PLMs are already predetermined from the original values. To overcome this shortcoming, movement pruning (Sanh et al., 2020) uses firstorder information to select weights based on how they change in training rather than their absolute value. To adapt PLMs for downstream tasks, most methods like movement pruning perform pruning and fine-tuning together by gradually increasing the sparsity during training. With the development of the Lottery Ticket Hypothesis (LTH) (Frankle and Carbin, 2018) in PLMs, some methods Liang et al., 2021) find certain subnetworks from the PLM by pruning, and then fine-tune these subnetworks from pre-trained weights. Moreover, if the fine-tuned subnetwok can match the performance of the full PLM, this subnetwork is called winning ticket .
Pruning Pre-trained Language Models Without Fine-Tuning
In this work, we propose a simple but efficient first-order method. Contrary to the previous pruning method, our method adapts PLMs by only pruning, without fine-tuning. It makes pruning decisions based on the movement trend of weights, rather than actual movement in movement pruning. To improve the performance of our method, we propose a new masking function to better align the remaining weights according to the architecture of PLMs. We also avoid fine-tuning weights in the task-specific head by using our head initialization method. By keeping the PLM frozen, we can save half of the trainable parameters compared to other first-order methods, and only introduce a binary mask as the new parameter for each downstream task at various sparsity levels. Extensive experiments on a wide variety of sparsity demonstrate our methods strongly outperform state-of-the-art pruning methods. Contrary to previous first-order methods (Sanh et al., 2020), which show poor performance at low sparsity, our method is also applied to low sparsity and achieves better performances than zero-order methods.
Pruning Pre-trained Language Models Without Fine-Tuning
Let a = Wx refer to a fully-connected layer in PLMs, where W ∈ R n×n is the weight matrix, x ∈ R n and a ∈ R n are the input and output respectively. The pruning can be represented by
Pruning Pre-trained Language Models Without Fine-Tuning
We first review two common pruning methods in PLMs: magnitude pruning (Han et al., 2015) and movement pruning (Sanh et al., 2020). Magnitude pruning relies on the zeroth-order information to decide M by keeping the top v percent of weights according to their absolute value M = Top v (S). The importance scores S ∈ R n×n is:
Pruning Pre-trained Language Models Without Fine-Tuning
i,j is the importance score corresponding to W (T ) i,j after T steps update, L and α w are learning objective and learning rate of W i,j . Magnitude pruning selects weights with high absolute values during fine-tuning.
Pruning Pre-trained Language Models Without Fine-Tuning
For movement pruning, it relies on the first-order information by learning the importance scores S with gradient. The gradient of S is approximated with the staight-through estimator (Bengio et al., 2013), which directly uses the gradient from M. According to (Sanh et al., 2020), the importance scores S is:
Pruning Pre-trained Language Models Without Fine-Tuning
where α s is the learning rate of S. Compared to magnitude pruning, movement pruning selects weights that are increasing their absolute value.
Pruning Pre-trained Language Models Without Fine-Tuning
To achieve target sparsity, one common method is automated gradual pruning (Michael H. Zhu, 2018). The sparsity level v is gradually increased with a cubic sparsity scheduler starting from the
Pruning Pre-trained Language Models Without Fine-Tuning
During training, these methods update both W and S to perform pruning and fine-tuning simultaneously. Since fine-tuned weights stay close to their pre-trained values (Sanh et al., 2020), the importance scores of magnitude pruning is influenced by pre-trained values, which limits its performance at high sparsity. However, magnitude pruning still outperforms movement pruning at low sparsity.
Pruning Pre-trained Language Models Without Fine-Tuning
In this work, we propose a simple first-order pruning method called Static Model Pruning (SMP). It freezes W to make pruning on PLMs more efficient and transferable. Based on movement pruning (Sanh et al., 2020), our importance scores S is:
Pruning Pre-trained Language Models Without Fine-Tuning
increases the absolute value of W i,j . For removed weight W ′ i,j = 0, it means that movement trending encourages 0 to close W i,j .
Pruning Pre-trained Language Models Without Fine-Tuning
To get masks M based on S, we consider two masking functions according to the pruning structure: local and global.
Pruning Pre-trained Language Models Without Fine-Tuning
For the local masking function, we simply apply the Top v function to each matrix: M = Top v (S), which selects the v% most importance weights according to S matrix by matrix.
Pruning Pre-trained Language Models Without Fine-Tuning
For the global masking function, ranking all importance scores together (around 85M in BERT base) is computationally inefficient, which even harms the final performance in section 6.1. To this end, we propose a new global masking function that assigns sparsity levels based on the overall score of each weight matrix. Considering the architecture of BERT, which has L transformer layers, each layer contains a self-attention layer and a feed-forward layer. In lth self-attention block, W l Q , W l K , W l V , and W l O are the weight matrices we need to prune. In the same way, W l U and W l D are the matrices to be pruned in the lth feed-forward layer. We first calculate the sparsity level of each weight matrix instead of ranking all parameters of the network.
Pruning Pre-trained Language Models Without Fine-Tuning
The sparsity level of each weight matrix v l (·) is computed as follows:
Pruning Pre-trained Language Models Without Fine-Tuning
is the importance socres of weight W l (·) , and (·) can be one of {Q, K, V, O, U, D}. The sparsity level is determined by the proportion of important scores to the same type of matrix in different layers.
Pruning Pre-trained Language Models Without Fine-Tuning
Instead of training the task-specific head from scratch, we initialize it from BERT token embedding and keep it frozen during training. Inspired by current prompt tuning methods, we initialize the task-specific head according to BERT token embeddings of corresponding label words following (Gao et al., 2021). For example, we use token embeddings of "great" and "terrible" to initialize classification head in SST2, and the predicted pos-
Pruning Pre-trained Language Models Without Fine-Tuning
is the final hidden state of the special token [CLS] and e great is the token embeddings of "great".
Pruning Pre-trained Language Models Without Fine-Tuning
To prune the model, we use the cubic sparsity scheduling (Michael H. Zhu, 2018) without warmup steps. The sparsity v t at t steps is:
Pruning Pre-trained Language Models Without Fine-Tuning
we gradually increase sparsity from 0 to target sparsity v f in the first N steps. After N steps, we keep the sparsity v t = v f . During this stage, the number of remaining weights remains the same, but these weights can also be replaced with the removed weights according to important scores. We evaluate our method with and without knowledge distillation. For the settings without knowledge distillation, we optimize the following loss function:
Pruning Pre-trained Language Models Without Fine-Tuning
where L CE is the classification loss corresponding to the task and R (S) is the regularization term with hyperparameter λ R . Inspired by softmovement (Sanh et al., 2020), it uses a regularization term to decrease S to increase sparsity with the thresholding masking function.We find the regularization term is also important in our method. Since λ R is large enough in our method, the most important scores in S are less than zero when the current sparsity level v t is close to v f . Due to the gradient ∂R(S)
Pruning Pre-trained Language Models Without Fine-Tuning
∂S i,j increases with the increase of S i,j when S i,j < 0, scores corresponding to the remaining weights will have a larger penalty than removed weights. It encourages the M to be changed when v t is almost reached or reached v f .
Pruning Pre-trained Language Models Without Fine-Tuning
For the settings with knowledge distillation, we simply add a distillation loss L KD in L following (Sanh et al., 2020;Xu et al., 2022):
Pruning Pre-trained Language Models Without Fine-Tuning
where D KL is the KL-divergence. p s and p t are output distributions of the student model and teacher model.
Pruning Pre-trained Language Models Without Fine-Tuning
To show the effectiveness of our method, we use three common benchmarks: nature language inference (MNLI) (Williams et al., 2018), question similarity (QQP) (Aghaebrahimian, 2017) and question answering (SQuAD) (Rajpurkar et al., 2016) following Sanh et al. Moreover, we also use GLUE benchmark (Wang et al., 2019) to validate the performance of our method at low sparsity.
Pruning Pre-trained Language Models Without Fine-Tuning
Following previous pruning methods, we use bert-base-uncased to perform task-specific pruning and report the ratio of remaining weight in the encode. For the task-specific head, we initial it according to the label words of each task following (Gao et al., 2021). For SQuAD, we use "yes" and "no" token embeddings as the weights for starting and ending the classification of answers. We freeze all weights of BERT including the task-specific head and only fine-tuning mask. The optimizer is Adam with a learning rate of 2e-2. The hyperparameter λ R of the regularization term is 400. We set 12 epochs for MNLI and QQP, and 10 epochs for SQuAD with bath size 64. For tasks at low sparsity (more than 70% remaining weights), we set N in cubic sparsity scheduling to 7 epochs. For tasks at high sparsity, we set N to 3500 steps.
Pruning Pre-trained Language Models Without Fine-Tuning
We also report the performance of bert-base-uncased and roberta-base with 80% remaining weights for all tasks on GLUE with the same batch size and learning rate as above. For sparsity scheduling, we use the same scheduling for bert-base-uncased and a linear scheduling for roberta-base. N in sparsity scheduling is 3500. For the large tasks: MNLI, QQP, SST2 and QNLI, we use 12 epochs. For the small tasks: MRPC, RTE, STS-B and COLA, we use 60 epochs. Note that the above epochs have included pruning steps. For example, we use around 43 epochs to achieve target sparsity in MRPC. We search the pruning structure from local and global.
Pruning Pre-trained Language Models Without Fine-Tuning
We compare our method with magnitude pruning (Han et al., 2015), L 0 -regularization (Louizos et al., 2018), movement pruning (Sanh et al., 2020) and CAP (Xu et al., 2022). We also compare our method with directly fine-tuning and super tickets (Liang et al., 2021) on GLUE. For super tickets, it finds that PLMs contain some subnetworks, which can outperform the full model by fine-tuning them. Table 1 shows the results of SMP and other pruning methods at high sparsity. We implement SMP with the local masking function (SMP-L) and our proposed masking function (SMP-S).
Pruning Pre-trained Language Models Without Fine-Tuning
SMP-S and SMP-L consistently achieve better performance than other pruning methods without knowledge distillation. Although movement pruning and SMP-L use the same local masking function, SMP-L can achieve more than 2.0 improvements on all tasks and sparsity levels in Table 1. Moreover, the gains are more significant at 3% remaining weights. For soft-movement pruning, which assigns the remaining weights of matrix nonuniformly like SMP-S, it even underperforms SMP-L.
Pruning Pre-trained Language Models Without Fine-Tuning
Following previous works, we also report the results with knowledge distillation in  Table 1: Performance at high sparsity. SMP-L and SMP-S refer to our method with local masking function and our masking function. θ M is the size of binary mask M, which is around 2.7M parameters and can be further compressed. 1 Since other pruning methods freeze the embedding modules of BERT (Sanh et al., 2020), the trainable parameters of first-order methods are the sum of BERT encoder (85M), importance scores S (85M) and task-specific head (less than 0.01M). For zero-order pruning methods like magnitude pruning, the trainable parameters are 85M, excluding S. Our results are averaged from five random seeds.
Pruning Pre-trained Language Models Without Fine-Tuning
teacher models, our method consistently yields significant improvements without auxiliary learning objectives. For 50% remaining weights, SMP-S in MNLI achieves 85.7 accuracy compared to 84.5 with full-model fine-tuning, while it keeps all weights of BERT constant.
Pruning Pre-trained Language Models Without Fine-Tuning
Our method is also parameter efficient. Compared with other first-order methods, we can save half of the trainable parameters by keeping the whole BERT and task-specific head frozen. For new parameters of each task, it is also an important factor affecting the cost of transferring and storing subnetworks. Our method only introduces a binary mask θ M as new parameters for each task at different sparsity levels, while other methods need to save both θ M and the subnetwork. With remaining weights of 50%, 10%, and 3%, we can save 42.5M, 8.5M, and 2.6M parameters respectively compared with other pruning methods. Figure 1 shows more results from 3% remaining weights to 80% by comparing our method with first-order methods: movement pruning and softmovement pruning, and the zero-order pruning method: magnitude pruning. We report the results of our method at 3%, 10%, 30%, 50% and 80% remaining weights. Previous first-order methods such as movement pruning underperform magnitude pruning at remaining weights of more than 25% in MNLI and SQuAD. Even under high sparsity level like 20% remaining weights, magnitude pruning still strongly outperforms both movement pruning and soft-movement pruning in Figure 1  pruning and magnitude pruning, respectively. KD represents the results with knowledge distillation. We report the results of our method on 3%, 10%, 30%, 50%, 70%, and 80% remaining weights. Our method constantly outperforms other methods from low sparsity to high.   (Liang et al., 2021), and the remaining weights and new parameters per task in SuperT are averaged over all tasks. Note all results are from the setting without knowledge distillation for a fair comparison.
Pruning Pre-trained Language Models Without Fine-Tuning
(c). This shows the limitation of current first-order methods that performing ideally only at very high sparsity compared to zero-order pruning methods. However, SMP-L and SMP-S as first-order methods can constantly show better performance than magnitude pruning at low sparsity. For the results without knowledge distillation, SMP-S and SMP-L achieve similar performance of soft-movement pruning with much less remaining weights. Considering to previous LTH in BERT, we find SMP-S can outperform full-model fine-tuning at a certain ratio of remaining weights in Figure 1 (a), (b) and (c), indicating that BERT contains some subnetworks that outperform the original performances without fine-tuning. For the results with knowledge distilla-tion, SMP-S and SMP-L benefit from knowledge distillation at all sparsity levels. After removing even 70% weights from the encoder, our method still strongly outperforms full-model fine-tuning.
Pruning Pre-trained Language Models Without Fine-Tuning
We also validate our method on GLUE and report the results at 80% remaining weights in Table 2. Compared to full-model fine-tuning, our method achieves better performance on two PLMs by only removing 20% parameters in the encoder while keeping the remaining parameters unchanged. Compared to SuperT, which searches 8 different sparsity levels for each task, our method achieves better performance by using the same sparsity levels. In addition, our method also saves more than 98M new parameters per task compared to SuperT.
Pruning Pre-trained Language Models Without Fine-Tuning
Function 80% 10% 3% 80% 10% 3%  Table 3: Influence of different masking functions. We report the results in MNLI and SQuAD with 80%, 10% and 3% remaining weights. N/A means that our method with corresponding masking function fails to converge in our setting. Masking function is to transform S (·) to the binary mask M l (·) of W l (·) . T refers to the thresholding masking function following (Sanh et al., 2020), and τ is the threshold. G and L are global and local masking functions, and S v is the smallest value in the top v% after sorting all S together. S refers to our proposed masking function, and v l (·) is from Eq. 4.
Pruning Pre-trained Language Models Without Fine-Tuning
In this section, we discuss the influence of different masking functions. Table 3 shows the results of different masking functions on our method without knowledge distillation. Contrary to previous pruning methods, the thresholding masking function T fails to converge in our method due to the difficulty in controlling the sparsity during training. For global masking function G, we sort all 85M BERT encoder weights and remain Top v% weights in each training step. Compared to local masking functions L, G takes more than twice the training times due to the computational cost of sorting 85M weights. Although it took the longest to train, it still underperforms L at 10% and 3% remaining weights. Contrary to G, our proposed masking function S outperforms L without additional training time since S directly assigns the remaining weights of each matrix. More results of masking functions S and L are also available in Table 1 and Figure 1. Figure 2 displays the distribution of remaining weights in different layers in MNLI with 10% remaining weights. We find G assigns too many remaining weights for W U and W V , which are four times larger than other matrices. It causes other weight matrices such as W Q to be more sparse than S and L. Following previous studies (Sanh et al., 2020;Mallya and Lazebnik, 2018), we also find that overall sparsity tends to increase with the  Table 3. depth of the layer. However, only W U and W V follow this pattern in all three matrices. Since W U and W V occupy more than 60% of the weight in each layer, it causes the overall distribution of each layer also follows their trend as well.
Pruning Pre-trained Language Models Without Fine-Tuning
To understand the behavior of attention heads, we also display the remaining weights ratio of each head in Figure 3. Each row represents a matrix containing 12 heads. Due to space limitation and the similar distribution between W Q and W K , we only show W Q and W V . Instead of assigning sparsity uniformly to each head, the sparsity of each head is not uniform in three masking functions, with most heads having only below 1% or below remaining weights. Furthermore, three masking Each cell refers to the remaining weights ratio of the corresponding attention head. The darker the color, the higher the ratio of remaining weight. L, G and S in figures refer to the masking functions following Table 3. functions show similar patterns even with different ways of assigning remaining weights. For our masking function S, S can assign more remaining weights to important heads compared to L, and some heads in W Q achieve more than 60% remaining weights at 9th layer. For global masking function G, due to most of remaining weights being assigned to W U and W D , the average remaining weights ratio of W Q and W V in G are only 3.2% and 2.8%, which causes G to underperform other masking functions.
Pruning Pre-trained Language Models Without Fine-Tuning
To validate the effectiveness of our task-specific head initialization method, we compare it with training from scratch.   Table 4 shows the results of SMP-L in MNLI and SQuAD with 80%, 10% and 3% remaining weights. For training from scratch, we randomly initial the head and fine-tune it with the learning rate of 3e-5 following previous pruning methods. Results show our method achieves better performance with task-specific heads frozen.
Pruning Pre-trained Language Models Without Fine-Tuning
Regularization term in training objective is a key factor for our method. We find that our method is hard to converge at high sparsity without regularization term R in Table 5. With the increase of sparsity, the performance gap between with and without R sharply increases. SMP-L without R even fails to converge at 10% and 3% remaining weights in SQuAD.  As analyzed in section 4.3, we find the remaining weights in attention heads are more uniform without R. For example, the standard deviation of remaining weights in each attention head is 3.75 compared to 12.4 in SMP-L with R in MNLI with 10% remaining weights. In other words, without R, it cannot assign more remaining weights to important heads as in Figure 3.
Pruning Pre-trained Language Models Without Fine-Tuning
In this paper, we propose a simple but effective task-specific pruning method called Static Model Pruning (SMP). Considering previous methods, which perform both pruning and fine-tuning to adapt PLMs to downstream tasks, we find finetuning can be redundant since first-order pruning already converges PLMs. Based on this, our method focuses on using first-order pruning to replace finetuning. Without fine-tuning, our method strongly outperforms other first-order methods. Extensive experiments also show that our method achieves state-of-the-art performances at various sparsity. For the lottery ticket hypothesis in BERT, we find it contains sparsity subnetworks that achieve original performance without training them, and these subnetworks at 80% remaining weights even outperform fine-tuned BERT on GLUE.
Pruning Pre-trained Language Models Without Fine-Tuning
Like all unstructured pruning methods, SMP is hard to achieve inference speedup compared to structured pruning methods. Since SMP prunes model without fine-tuning, this also limits the extension of SMP to structured pruning methods. However, we find that most rows of the sparsity matrices in SMP are completely pruned at high sparsity level. This allows us to directly compress the size of matrices, resulting in faster inference. For example, the 3% remaining weights model of MNLI can be compressed to 47.43% of the model actual size (resulting in around 1.37× inference speedup) without retraining or performance loss. By removing rows of matrices that contain less than 10 remaining weights, we can further compress it to 25.19% actual size (1.76× inference speedup) with 0.9 accuracy drop. We expect that a carefully designed loss function during training could result in even smaller actual model size and faster inference speedup, which we leave it in the future.
Pruning Pre-trained Language Models Without Fine-Tuning
We also report our standard deviation of tasks from 5 random runs in Table 6 and 7.   A2. Did you discuss any potential risks of your work? Not applicable. Left blank.
Pruning Pre-trained Language Models Without Fine-Tuning
A3. Do the abstract and introduction summarize the paper's main claims?
Pruning Pre-trained Language Models Without Fine-Tuning
Left blank.
Pruning Pre-trained Language Models Without Fine-Tuning
A4. Have you used AI writing assistants when working on this paper?
Pruning Pre-trained Language Models Without Fine-Tuning
B Did you use or create scientific artifacts?
Pruning Pre-trained Language Models Without Fine-Tuning
B1. Did you cite the creators of artifacts you used? No response.
Pruning Pre-trained Language Models Without Fine-Tuning
B2. Did you discuss the license or terms for use and / or distribution of any artifacts? No response.
Pruning Pre-trained Language Models Without Fine-Tuning
B3. Did you discuss if your use of existing artifact(s) was consistent with their intended use, provided that it was specified? For the artifacts you create, do you specify intended use and whether that is compatible with the original access conditions (in particular, derivatives of data accessed for research purposes should not be used outside of research contexts)? No response.
Pruning Pre-trained Language Models Without Fine-Tuning
B4. Did you discuss the steps taken to check whether the data that was collected / used contains any information that names or uniquely identifies individual people or offensive content, and the steps taken to protect / anonymize it? No response.
Pruning Pre-trained Language Models Without Fine-Tuning
B5. Did you provide documentation of the artifacts, e.g., coverage of domains, languages, and linguistic phenomena, demographic groups represented, etc.? No response.
Pruning Pre-trained Language Models Without Fine-Tuning
B6. Did you report relevant statistics like the number of examples, details of train / test / dev splits, etc. for the data that you used / created? Even for commonly-used benchmark datasets, include the number of examples in train / validation / test splits, as these provide necessary context for a reader to understand experimental results. For example, small differences in accuracy on large test sets may be significant, while on small test sets they may not be.
Pruning Pre-trained Language Models Without Fine-Tuning
No response.
Pruning Pre-trained Language Models Without Fine-Tuning
Left blank.
Pruning Pre-trained Language Models Without Fine-Tuning
C1. Did you report the number of parameters in the models used, the total computational budget (e.g., GPU hours), and computing infrastructure used? Left blank.
Pruning Pre-trained Language Models Without Fine-Tuning
The Responsible NLP Checklist used at ACL 2023 is adopted from NAACL 2022, with the addition of a question on AI writing assistance.