One-Shot Pruning of Recurrent Neural Networks by Jacobian Spectrum Evaluation
Authors: Shunshi Zhang
Bradly C. Stadie
Venue:  (2020)
Keywords: Pruning
RNNs
Sparsity

Abstract:   Recent advances in the sparse neural network literature have made it possible to prune many large feed forward and convolutional networks with only a small quantity of data. Yet, these same techniques often falter when applied to the problem of recovering sparse recurrent networks. These failures are quantitative: when pruned with recent techniques, RNNs typically obtain worse performance than they do under a simple random pruning scheme. The failures are also qualitative: the distribution of active weights in a pruned LSTM or GRU network tend to be concentrated in specific neurons and gates, and not well dispersed across the entire architecture. We seek to rectify both the quantitative and qualitative issues with recurrent network pruning by introducing a new recurrent pruning objective derived from the spectrum of the recurrent Jacobian. Our objective is data efficient (requiring only 64 data points to prune the network), easy to implement, and produces 95 % sparse GRUs that significantly improve on existing baselines. We evaluate on sequential MNIST, Billion Words, and Wikitext. 

Published as a conference paper at ICLR 2020
ONE-SHOT PRUNING OF RECURRENT NEURAL NET- WORKS BY JACOBIAN SPECTRUM EVALUATION
Matthew Shunshi Zhang University of Toronto ma tthew.. zhang@ma i utoronto.ca
Bradly C. Stadie Vector Institute
ABSTRACT
Recent advances in the sparse neural network literature have made it possible prune many large feed forward and convolutional networks with only a small quan- tity of data. Yet, these same techniques often falter when applied to the problem of recovering sparse recurrent networks. These failures are quantitative: when pruned with recent techniques, RNNs typically obtain worse performance than they do under simple random pruning scheme. The failures are also qualitative: the distribution of active weights in a pruned LSTM or GRU network tend to be concentrated in specific neurons and gates, and not well dispersed across the entire architecture. We seek to rectify both the quantitative and qualitative issues with recurrent network pruning by introducing new recurrent pruning objective derived from the spectrum of the recurrent Jacobian. Our objective is data efficient (requir- ing only 64 data points to prune the network), easy implement, and produces 95 % sparse GRUs that significantly improve on existing baselines. We evaluate on sequential MNIST, Billion Words, and Wikitext.
INTRODUCTION
Within the neural network community, network pruning has been something of an evergreen problem. There are several motivations for pruming a neural network. Theoretically, overparameterization is a well known but poorly understood quality of many networks. Pruning algorithms provide a link between overparameterized models appropriately parameterized models. Thus, these algorithms may provide insights into exactly why overparameterized models have so much success. Indeed, recent work has closely linked the efficient utilization of model capacity with generalization results (Arora cct al. 2018). From a more practical perspective, overparameterized networks require more storage capacity and are computationally more expensive than their pruned counterparts. Hence, there is an incentive to use pruned networks rather than fully dense networks during deployment.
For years, many of the most successful network pruming techniques were iterative relying cycle of pruning and retraining weights to induce sparsity in the network. As identified in Lee et al. (2018), these methods usually either enforce sparsity- penalty the weights (Han al. 2015 LeC Cn
let al., 1990), or else prune based on some fitness criteria (Carreira-Perpine Chauvin 1989). Recent advances in pruning literature suggest that such costly cycles of pruning and retraining might not always be necessary. For some problems, there exists a small subnetwork within the original larger network such that training against this smaller network produces comparable performance to training against the original fully dense network. The Lottery Ticket Hypothesis (Frankle Carbin 2019) provides method for recovering these networks, but only after training
& Idelbayev 2018]
is complete. SNIP (Le et al.) 2018) and GraSP (Wang et al. (020) provide a saliency criterion for identifying this small subnetwork using less than 100 data points, no training, and no iterative pruning.
Our present work began by asking the question: "How well do these newly discovered pruning techniques, which optimize network sensitivity objective, work recurrent neural networks?" Although Lee et al. (2018) does evaluate the SNIP pruning criterion on both GRU and LSTM networks, we found these results to be somewhat incomplete. They did not provide comparison to random pruning, and the chosen tasks were not extensive enough to draw definitive conclusions. When compared against random pruning, we found that the SNIP and GraSP pruning objective

---

Published as a conference paper at ICLR 2020
performed similarly or worse than random pruming. This left wondering where those techniques were falling short, and if a better pruning objective could be developed that takes the temporal structure of recurrent networks into account.
In this paper, we propose a new pruning objective for recurrent neural networks. This objective is based recent advances in mean field theory (Gilboa et al., 2019 Chen et al.) (018a), and can be interpreted as forcing the network to preserve weights that propagate information through its temporal depths. Practically, this constraint is imposed by forcing the singular values of the temporal Jacobian with respect to the network weights to be non-degenerate. We provide a discussion about the similarities and differences between our objective and the SNIP and GraSP pruning objectives. It can be shown that these prior objectives fail to ensure that the temporal Jacobian of the recurrent weights well conditioned. Our method is evaluated with a GRU network on sequential MNIST, Wikitext, and Billion Words. At 95% sparsity, our network achieves better results than fully dense networks, randomly pruned networks, SNIP (Lee al. 2018 pruned networks, and GraSP (Wang al. 2020 pruned networks.
PRUNING RECURRENT NETWORKS BY JACOBIAN SPECTRUM EVALUATION
2.1 NOTATION
We denote matrices and vectors by upper- and lower-case bold letters respectively. Vector-valued functions are bolded, whereas scalar valued functions are not. Distributions over variables are with the following script: D.P. We denote the standard lp norm of a vector by I1-Ilp- Let Hey be the (i.i)-th element of matrix, and [-]s the i-th element of vector. i, O, denotes vector of is Os of appropriate length, and use @ denotes a Hadamard product. TA represents the standard indicator function. For vectors, superscripts always used for sequence lengths while subscripts reserved for indexing vector elements.
2.2 PRELIMINARIES
2.2.1 RECURRENT MODELS
Let X x= (x(0)] with each (()) IR.. Similarly, let Ý (y/10) t=11 where each y(t) E R is an associated set of outputs, such that each tuple (X, Y) i.idd D.
Let M(x; 0) TRDD ROO be generic model, parameterized by O E R.N, that maps X onto output sequence. Define a recurrent model as a mapping done through iterative computation, such that each (x))), (9) M(x(*), (t( 0) depends explicitly only on the current input and some latent state of the model, h.
We define a loss over the entire sequence of outputs as the sum of a non-sequential loss function, L, over entire sequence: L(M,X, E (()()), (t)).
We define sparse model as one where the parameters factorize into 0 O with E {0, 1]. binary mask and w E N the free values, typically trained by gradient descent. We define a K K-sparse condition on sparse model M the restriction |ee|o K during the entire training trajectory. A model is optimally K-sparse if it minimizes the expected loss, E.| X, Y)] after training while also being subject K -sparse condition.
2.2.2 MEMORY HORIZON
We introduce the following terms: N is the size of the network hidden state h. and Jr E R RNN is the temporal Jacobian, of the hidden state time + with respect the previous hidden state, (h(11) "
and o( the singular values of said matrix.
To arrive at a one-shot pruning criteria for recurrent neural networks, we consider the impact of the temporal Jacobian both forward- and backward-propagation
2

---

Published as a conference paper at ICLR 2020
(Backpropagation) The formula for backpropagation through time (BPTT), from the loss time can given as:
s-1
Vol(y..ys)
G Chonoo + G oo s-1 + .... GT hh))
II J
V Vnis)
Where G e is the Jacobian of (()) considering only the explicit dependence on 0.
(Forward Propagation)
A single time-step of the network under small perturbations yields the following:
M(x h + e) h ((+1) + J,e
(2)
With additional powers of the Jacobian appearing as we observe the entire sequence.
From Equation it easily be that increasing the normed singular values of each J, will average exponentially increase the gradient signal from later sequence elements, which will expedite convergence by reducing the vanishing gradient problem. From Equation @ a well-conditioned Jacobian would enable the network to preserve separation of distinct input vectors, by preventing the additive perturbation from vanishing or exploding. Prior works in mean-field theory Gilboa et al. (2019); Chen al. (20 provide extensive analysis of similar objective on the performance of a wide range recurrent networks.
we additionally note that
The Froebenius norm of the temporal Jacobian, defined below, is thus key to both forward and backpropagation. Both processes are significantly expedited when the norm is close to
(0)2 0
= N(S 1)
J.1
N(S N(S-1) 1)
Σ
Σ
2.3 PRUNING CRITERIA
Under typical recurrent model initializations, where 0 >~NN(ua +zJ) or similar distribution, with Hig ~ 0, z < 1. Gilboa et al. 2019) has empirically observed that x is < 1, and that the singular values concentrate towards (see Figure 2 for further evidence). Therefore, we hypothesize that the fastest converging and best performing sparse models are those which simply maximize X.
We would like to determine the effect of removing trajectory. However, as we restrict ourselves only to information available at initialization, we approximate the effect of each parameter on the Jacobian by first-order Taylor expansion. This is analogous to the derivations given in Lee et al. (2018): Wang et al. (2020):
parameter the Jacobian during the training
S-1
dn x ||x|ml = S
J.
(4)
a0,
We call dn the sensitivity score parameter O,.
This criterion will not be well-normed across different types of parameters. This is due to numerous factors, including differing activation functions used for each gate, and differing distributions between the input and recurrent state. Consequently, the variance of our objective is not uniform between groups of parameters (see Section 3.3 for empirical confirmation). We compensate for this by dividing our criterion by the expected magnitude of the gradient for each parameter. The normalized sensitivity score becomes:
[xx] 7mml
S
Oh
(t)
dn = [AA] =
En
(5)
a0
where D is either the data distribution approximate distribution (since only trying to estimate the approximate variance of the gradient distribution), and the sequence (h()) is computed
3

---

Published as a conference paper at ICLR 2020
inputs from that distribution. This normalization scheme is similar in motivation the normaliza- tion proposed in Pascanu et al. (2013). and allows us to consider all recurrent models with only one additional computation.
For our pruning objective, we simply take the weights with largest sensitivity scores, as those represent the parameters which most affect the Jacobian objective the initialization. Formally, find the K-th largest sensitivity, dx, and set Cn. LA (d,, dx). Empirically, we find that the sensitivity score remains an effective metric even if the weights are not restricted to a neighborhood where the Taylor expansion is valid (see Figure 2 for details).
This objective simple to compute, requiring only two backward passes using auto-differentiation. Furthermore, we only depend on the Jacobian-vector product, it has memory cost linear in the parameters.
Algorithm Pruning Recurrent Networks
Require:
Parumeters 6, Dataset 2), Approsimate Dataset D), Spursity Level K. Sequence Length S, Number to Sample P, Sequence Horizon
1:
for all I... P do
2: Sample sequence (X. Y) ~ (X, Y) ~
3: for all f = 1.... S
4:
Compute {h with (X, Y), (b()) with (x. Y)
5:
end for
6:
end for
7:
Compute using ) Equation
8:
for all a I... U. do
96 (8-
9: Compute (w)) + J-- 113 =B
Eis
o 18---
10: Compute (x(")) (w) | (
11:
end for
12: Compute [x(
l71 13: d SortDeecendingdd)
Ga + 1(d, dx]. Vn
15:
2.4 COMPARISON TO EXTANT METHODS
There are two recently proposed criteria for pruning at initialization: GraSP (Wang et al. 2020). and (Lee et al. 2018). They given by:
SNIP
GraSP(0) Hg
(6)
SNIP(O) = =00Tg
(7)
where [H]
PC 30,00, 1. a[ are the expected gradient and Hessian respectively.
Both methods rely the gradient of the loss with respect the weights, with SNIP being more dependent on this gradient than GraSP. Thus, the main term of interest is g, which can be decomposed
as:
gt = G. h L
(8)
With Gr the Jacobian of (4) with respect to 0, as defined in Equation
consequence of the smaller singular values of J is that the successive terms of G, tend to vanish over time. Thus, loss-based gradient objectives tend to be biased toward explicit dependency between (1) on 0, thus neglecting long-term dependence between h (4) and h (t-1)
In certain cases, (ex. when the hidden state is small relative to the input) SNIP and GraSP prune many recurrent connections while leaving the input connections largely untouched (see section 3). In contrast, our algorithm considers the matrix explicitly, which mitigates the problem pruning too many recurrent connections.
4

---

Published as a conference paper at ICLR 2020
Architecture
Parameters
Random
Ours
Dense
A
Basic RNN Cell
171k 8.5k
9.51
7.57=0.20
7.08+2.08
+4.39
Standard LSTM
684k + 34.2k
2.17#0.18
1.66:10.16
0.80=0.18
+0.86
Peephole LSTM
1.32M 66.2k
1.80+:0.18
1.24:10.08
0.74
+0.50
GRU
513k + 25.7k
1.50-+0.08
1.46:
0.77+t0.14
+0.69
Table Validation Error % of Various 400 Unit RNN Architectures after 50 Epochs of Training on Seq. MNIST; our method works well across all common recurrent architectures. Sparsity of 95 % was used on all experiments.
3 EVALUATION
For the following experiments, we compute the 2g norm of JÍ using single minibatch of data samples, and using only the last 4 steps of the sequence.
3.1 SEQUENTIAL MNIST BENCHMARK
We first test our method on the sequential MNIST benchmark (Lee et al. 2018), relatively small dataset which contains long term dependencies. We begin by veritying that our algorithm is robust several common recurrent architectures. The results in Table dependent on any specific recurrent neural architecture choice.
that method
Our principal results for the Sequential MNIST benchmark are presented in Table 2 Again, see that our network's performance improves with network size, with the largest gap between our method and others coming when the network grows 1600 units. We observe that SNIP and GraSP are surprisingly effective at small scales with good initialization, but fail when scaled to larger network sizes. Of the baselines, only random pruning is competitive when scaled, fact we found quite interesting. For reference, we also provide results on standard L2 pruning (Reed) 1993) (for which the schedule can found in the appendix) and random pruning. The reader should be careful to note that L2 pruning requires order of magnitude more resources than other methods due to it's prune retrain cycle; it is only considered here as a lower bound for network compression. Furthermore, while GraSP requires computing the Hessian gradient across the entire dataset, this is computationally infeasible in our case and we instead compute it with a single minibatch, for fairness.
Pruning Scheme
100 Units
400 Units
1600 Units
Unnorm. SNiP
88.9=0.1
88.
89.0+E0.1
Norm. SNiP
4.0911.06
1.52:00111
1.10+0.11
Unnorm. GraSP
88.6-10.1
88.7+0.1
88.6+0.11
Norm. GraSP
4.28++0557
1.62:40.24
1.22+:0.14
Random
2.78=0.25
1.50+10.08
1.15+0.12
Ours
3.39
1.46-10.05
1.01-10.05
L2
1.03=0.05
0.71
0.57+0.02
Table 2: Benchmarking of Various Pruning Algorithms on 95% Sparse GRUs on seq. MNIST. SNIP, GraSP and Random pruning are competitive for smaller models, but the results tend diminish as the network size increases. Our method obtains strong results even as the network size is large. Further experimental details can be found in the appendix.
In the preceding section, we postulated that normalization across the objective was necessary for strong performance (see Equation This intuition is confirmed in Table where present both the normalized results (with Glorot Glorot & Bengio (2010) and y normalization) and the unnormalized results (without both). Indeed, we see that this normalization is crucial for recurrent architectures, with unnormalized architectures having all the retained network weights concentrated a single gate. This proved to be prohibitive to training.
Finally, in Table 3) we examine the performance of our algorithm at various sparsity levels. Our algorithm continues to outperform random pruning, high sparsity levels.
5

---

Published as a conference paper at ICLR 2020
Sparsity Level
# of Parame-
Random
Ours
Dense
A
(%)
ters
90
68.4k
1.12=0.16
1.05:+0.08
0.63+0.02
+0.42
95
34.2k
0.08
1.46 1.77:+0.07
0.77+00110
+0.69
98
13.7k
1.82 1.82-0.22 0.22
0.67++0.13
+1.10
Table 3: Sparsity Level vs Validation Error % on 400 Unit GRUs, for seq. MNIST. Our method consistently beats random pruning.
3.2 LINGUISTIC SEQUENCE PREDICTION
We assess our models on sequence prediction benchmarks: 1) WikiText-2 (wiki2). 2) WikiText- 103 (wiki103), expanded version of (1) with 10 times more tokens. 3) A truncated version of the One Billion Words (lb) benchmark (Chelba et al. (013). where only the top 100,000 vocabulary given in the appendix. We report the training and validation perplexities on a random I % sample of the training set in Table
tokens used. The full experiment parameters
Dataset (%)
Random
Ours
Dense
A
wiki2
22.66
20.54
10.479
+10.61
wikil03
49.65
46.65
35.87
+10.78
Trunc. lb
59.17
53.26
38.98
+14.28
# of Parameters
960k
960k
19.2M
Table 4: Training Perplexities of Training Sparse Models Large Language Benchmarks. Our method successfully reduces the perplexity score across all benchmarks, often significantly, however there still large gap the dense performance. Parameters reported only for the recurrent layer as other layers were not pruned during training.
From the results, it is clear that our algorithm succeeds in decreasing perplexity across all language tasks. Despite their varying difficulties, our algorithm speeds up initial convergence on all tasks and maintains an advantage throughout training.
Finally, we perform an ablation experiment on the Penn Treebank Dataset (PTB) with an 800 unit GRU at different sparsity levels. The results are reported in Table
Sparsity
0%
20%
40%
60%
70%
80%
90%
95%
98%
Perplexity
156.16
160.32
165.13
173.51
178.55
184.85
194.79
208. 14
228.22
Parameters
2.88M
2.30M
1.72M
1.15M
864K
576K
288K
144K
57.6K
Table 5: Validation Perplexities of Pruned 800-unit GRU Models on Penn Treebank. For simple comparison we do not finetune these models, or apply any regularization tricks besides early stopping.
The loss from sparsity increases dramatically as the percentage of parameters remaining approaches zero. This trend is similar that reported in Gale et al. (2019) and other prior works. For reference, a dense 200 unit GRU (360k parameters) achieves 196.31 perplexity while a 100 unit GRU (150k parameters) achieves 202.97 perplexity.
3.3 QUALITATIVE ANALYSIS
The success of our algorithm can be partially attributed to effective distributions across hidden units. Whereas many of the other algorithms are overly concentrated in certain gates and biased towards the input weights, our algorithm effectively distributes sparse connections across the entire weight matrix. We discuss the distribution of remaining connections on a 400 unit GRUs in Figure We also give set of sample connections under each algorithm in Figure 3
Finally, we perform an empirical study of the evolution of the Jacobian spectrum to verify our hypothesis recurrency preservation. We show 400-unit GRU trained sequential MNIST, with a dense network, our pruning scheme, and random pruning respectively. It can be observed from Figure after 50000 training steps that Jacobian has both higher mean and much fewer near-zero singular values, which helps to explain our performance and justify the intuition behind our algorithm. The spectra initialization also further confirms that the initial singular values of J are small.

---

Published as a conference paper at ICLR 2020
(a) SNiP. I/R Ratio: 0.205
(b) GraSP. I/R Ratio: 0.124
(c) Ours. I/R Ratio: 0.094
Figure Plot of Remaining Connections by Gate and Type. SNiP and GraSP consistently prune recurrent connections at much higher ratio than input connections. The ratio of remaining input to recurrent (I/R) connections given for each method; the dense ratio is 0.07 for comparison. SNiP and GraSP also exhibit severe imbalance between gates, while imbalance is far milder.
2001
(a) Initialization. Pre- Pre-Pruning
(b) SNiP
(c) Ours
Figure Singular Value Magnitude Histograms after epochs of Training, for 400 Unit GRU on seq. MNIST. Compared to SNiP, our method prevents spectral concentration at O, with mean singular value magnitude of 0.31 to SNiP's 0.18 This helps to explain our relative performance gain.
4 OTHER RELATED WORK
Methods for Pruning Recurrent Networks: Our method is the latest in series of attempts generate sparse RNNs. Perhaps the most well-known algorithm for sparse network pruning is (a[aangg] al. (017a). is modification to magnitude based pruning wherein the pruning threshold evolves according to several hyperparameters that have to be tuned by the user. Kliegl et al. (2017) uses iterative trace norm regularization to prune RNNs used for speech recognition. This effectively reduces the sum of the singular values of the weight matrices. But we found in our experiments that these values were often degenerate near Furthermore, this technique iterative. Narang al. (2017b) uses iterative ground lasso regularization to induce block sparsity in recurrent neural networks. Wen et al. (2017) alters the structure of LSTMs to decrease their memory requirements. Their intrinsic sparse structures make structural assumptions about the sparsity distribution across the network. Dai et al. (0088) uses magnitude based pruning coupled with a special RNN structure
(a) SNIP
(b) GraSP
(c) Ours
Figure 3: Map of remaining connections, with the x-axis indicating the output size (flattened across gates) and the y-axis indicated the input size.Our method significantly more spread out across neurons and gates than the others.
7

---

Published as a conference paper at ICLR 2020
to make RNNs more efficient. The pruning algorithm itself is magnitude based. See et al. (2016) uses iterative pruning and retraining to prune a recurrent model for neural translation. The underlying technique is simple iterative pruning, and the final pruning percentage is only 80%. While fine for their application, we are interested in novel pruning techniques and higher levels of sparsity.
In summation, all the the methods discussed above utilized some variant of L1 L2 pruning to actually sparsify the network. The novel advances are all related to pruning schedules, modifications to recurrent architectures, small transformations of the LI L2 objective.
Other Pruning Techniques: Many extant pruning techniques are applicable to recurrent network architectures, even if these methods were not designed from the ground up to work in the recurrent case. Lee et al. (2018 8) and Wang et al. (2220) both provide a pruning objective that can be used to prune networks before training begins. They are considered extensively in this work. In Frankle & Carbin 2019), it is shown that at initialization networks contain a small sparse set of connections that can achieve similar results to fully dense networks. However, no known method yet exists to recover these sparse networks to the full extent demonstrated in that work. Haan et al. (2015) showed impressive results with magnitude based pruning. Follow up work made further use of magnitude- based pruning techniques CCarreir-Peerpiáán & Idelbayev 2018 Guo et al. 2016); however, these techniques are primarily iterative.
Mcan Replacement Pruming (Evci al. 2018) uses the absolute-valuc of the Taylor expansion of the loss to as a criterion for which units in a network should be pruned. This method can not be used with BatchNorm and achieves results comparable magnitude based pruning. Bayesian methods have recently seen some success in pruning neural networks. (Ullrich et al. (017). which is itself an extension of Nowlan & Hinton (1992), is the standard citation here. In essence, this method works by re-training a network while also fitting the weights to a GMM prior via KL penalty. MMochanov ct al. (2017) another Bayesian pruning technique that learns a dropout rate via variational inference that can subsequently be used to prune the network. Finally, there exists several classical pruning techniques. Ishikawa (1996); Chauvin 1989) enforced sparsity penalties during the training process. LeCun et al. (1990); Hassibi et al. (199) perform Hessian-bases pruning, using the Hessian to get sensitivity metric for the network's weights.
While many of the above methods are effective in general, they do not explicitly consider the specifics of RNNs and sequential prediction.
Other Related Work Several interesting papers have recently taken critical look at the problem of network pruning (Liu et al.] 2018) Crowley et al., 2018). The problem of network compression is closely related to network pruning. It would be impossible to cite all of the relevant papers here, and no good literature survey exists. Some worthwhile references are Gupta et al. (2015); ; Gong et al. (2014); Courbariaux 2ourbaCuuua
et al. (2016); Chen al. (2018b); Howard et al. (201)). Both problems often share a common goal of reducing the size of a network. Some notable papers explicitly consider
the problem of recurrent network compression (Ye et al. 2018 Lobacheva al. 2017] Wang et al.) 2018).
In the context of the above work, our method is not iterative and can be fully completed before training even begins. The tradeoffs in accuracy can be remedied by scaling up the network, since there is no longer need store fully dense weights during training. Furthermore, our objective is specifically adapted to the sequential prediction context in which RNNs are deployed. We are the first pruning algorithm to consider the temporal Jacobian spectrum as a key to generating faster converging and better performance sparse RNNs Our method not only performs better in practice compared to other zero-shot methods, but also yields key insight into the factors behind RNN performance. This may aid the development of new architectures and training schemes for sequential prediction.
5 CLOSING REMARKS
In this work, we presented an effective and cheap single-shot pruning algorithm adapted toward recurrent models. Throughout the work, we continually found the importance of the Jacobian spectrum surprising and interesting. Future work could further examine the relationship between network width, the Jacobian spectrum, and generalization.
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur. and Yi Zhang, Stronger generalization bounds for deep nets a compression approach. ICML, 2018.
Miguel A Curreira-Perpinae and Yerlan Idelbayev. Searming-compresioon algorithms for neural net pruning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3532-8544 2018.
Yves Chauvin. A paoppproon algorithm with optimal use of hidden units. In Advances in neural information processing systems, pp. 519-526, 1989.
Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One billion word benchmark for measuring progress in statistical language modeling. arXiv preprint 1312. 2013.
Minmin Chen, Jeffrey Pennington, and Samuel S Schoenholz. Dynamical isometry and mean field theory of rnns: Gating enables signal propagation in recurrent neural networks. arXiv preprint 1vXiv:/80.005344 2018a
Patrick Chen, Si Si, Yang Li, Ciprian Chelba, and Cho-Jui Hsieh. Groupreduce: Block wise low-rank approximation for neural language model shrinking. In Advances Neural Information Processing Systems, pp. 10988-108 10998, 2018b.
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran EI- Yaniv, and Yoshua Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1. arXiv preprint a60iv 028300 2016.
Elliot J Crowley, Jack Turner, Amos Storkey, and Michael O' O'Boyle. Pruning neural networks: is it time to nip it in the bud? arXiv preprint arXiv:1810.0440 04222, 2018.
Xiaoliang Dai, Hongxu Yin, and Niraj K. Jha. Grow and prune compact, fast, and accurate Istms. arXiv preprint orXiv:/003 1797, 2018.
Utku Evei, Nicolas Le Roux, Pablo Castro, and Leon Bottou. Mean replacement pruning. 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. ICLR, 2019.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574 2019.
Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S Schoenholz, Ed H Chi, and Jeffrey Pennington. Dynamical isometry and mean field theory of Istms and grus. arXiv preprint arXiv:1901.08987, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pp. 249-256, 2010.
Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdev. Compressing deep convolutional networks using vector quantization. arXiv preprint 6rXiv:1412.6115. 2014.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In Advances In Neural Information Processing Systems, pp. 1379-1387, 2016.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International Conference Machine Learning, pp. 1737-1746. 2015.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015.

---

Published as a conference paper at ICLR 2020
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In JEEE international conference on neural networks, pp. 293-299. IEEE, 1993.
Andrew Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv:1104.0440 2017.
Masumi Ishikawa. Structural learning with forgetting. Neural networks, 933):509-51,, 1996.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint /4X2:::412.69990 2014.
Markus Kliegl, Siddharth Goyal, Kexin Zhao, Kavya Srinet, and Mohammad Shoeybi. Trace norm regularization and faster inference for embedded speech recognition mns. arXiv preprint arXiv:/710.09026, 2017.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances neural information processing systems, pp. 598-5598-0 605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXiv:1810.02340. 2018.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell, Rethinking the value of network pruning. arXiv preprint 1rXiv:1810.05270, 2018.
Ekaterina Lobacheva, Nadezhda Chirkova, and Dmitry Vetrov. Bayesian sparsification of recurrent neural networks. arXiv preprint arXiv: 1708000077 2017.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 249222482992 -2077 JMLR. org, 2017.
Croninng-Volumee
Sharan Narang, Erich Elsen, Gregory Diamos, and Shubho Sengupta. Exploring sparsity in recurrent neural networks. arXiv preprint arXiv:1704.05119 2017a
Sharan Narang, Eric Undersander, and Gregory Diamos. Block-sparse recurrent neural networks. arXiv preprint arXiv: 111.//7.....2... 2017b.
Steven Nowlan and Geoffrey Hinton. Simplifying neural networks by soft weight-sharing. Neural computation, 4(4):473-493, 1992.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318, 2013.
Russell Reed. Pruning algorithms-a survey. IEEE transactions on Neural Networks, 4(5):740-747, 1993.
Abigail See, Minh-Thang Luong, and Christopher D Manning. Compression of neural machine translation models via pruning. arXiv preprint arXiv: 09274, 2016.
Karen Ullrich, Edward Meeds, and Max Welling. Soft weight-sharing for neural network compression. arXiv preprint 1tXXiv:702.04000 2017.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. In International Conference on Learning Representations, 2020. URL
htttps://openreviees net www.moorrmiioooo (i-ooummmdd-SSsscccce
Zhisheng Wang, Jun Lin, and Zhongfeng Wang. Hardware-oriented compression of long short-term memory for efficient inference. IEEE Signal Processing Letters, 25(7):984 988, 2018
Wei Wen, Yuxiong He, Samyam Rajbhandari, Minjia Zhang, Wenhan Wang, Fang Liu, Bin Hu, Yiran Chen, and Hai Li. Learning intrinsic sparse structures within long short-term memory. arXiv preprint arXiv: /709, 0700705 2017.
Jinmian Ye, Linnan Wang, Guangxi Li. Di Chen, Shandian Zhe, Xinqi Chu. and Zenglin Xu. Learning compact recurrent neural networks with block-term tensor decomposition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3378-9387, 2018.
10

---

Published as a conference paper at ICLR 2020
APPENDIX A EXPERIMENT HYPERPARAMETERS
Unless otherwise specified, our model consists of a single-layered RNN, followed by appropriately sized softmax layer with sigmoidal activation. The softmax layer is initialized with standard Xavier. We use minibatch size of 64 samples during training, and optimize using the AdaM optimizer (Kingma & Ba, 2014) with a learning rate of le-3, We use an initial hidden state of zeros for all experiments.
For all networks, we only prune the recurrent layer while leaving prior and subsequent layers untouched, since are primarily interested in performance of recurrent layers. We trained all networks with a single Nvidia P100 GPU.
6.1 SEQUENTIAL MNIST
For seq. MNIST, we follow the same process as SNiP, feeding in row-by-row. We used (00, 0.1) for our method, and Glorot initialization for SNiP and GraSP. y is computed from data sampled from a (O0, 0.1) distribution. We use only the activations from the last time step. For L2, the density was annealed according the schedule {0.8, 0.6, 0.4, 0.2, 0.1, 0.05, 0.02, 0.01} every 10k training steps.
6.2 LANGUAGE BENCHMARKS
We 2000-umit LSTMs for all language benchmarks. To reduce the variance of our comparison, we freeze the embedding layer before training. We use sampled sequential cross-entropy loss with 1000 tokens for wikil03 and 1b, and standard cross-entropy for wiki2. We use He initialization for all papers.
Wiki2 was trained for 20k training steps (13 epochs), while wiki103 was trained for 12k training steps, and 1b was trained for 30k training steps.
7 APPENDIX B ADDITIONAL STUDIES
7.1 INITIALIZATIONS
We benchmark the performance of our algorithm against random pruning using 3 additional initializa- tions, seen in Table With high variance, the first-order expansion we use to estimate our objective fails to hold, so we do significantly worse than the random benchmark.
Iniiiaiizatonn Scheme
Ours
Random
Glorot
1.219
1.36
(( 1)
3.30
1.38
umiform((0..1) 0.10
1.73
1.32
Table 6: Benchmarking of validation Error % on Different Initializations, for Sequential MNIST Task with 400 Unit GRU. Our algorithm successfully beats random on well-conditioned normal distributions, but fails on high variance and the uniform distribution.
7.2 RUNTIME
We benchmark the runtimes of SNiP, GraSP and our own algorithm, using only a single batch and time iteration for faimess, in Table 7
APPENDIX C- TRAINING CURVES
We present a sample training curve a 400 unit GRU for sequential MNIST below. As can be seen, random pruning is only competitive algorithm in this instance.
11

---

Published as a conference paper at ICLR 2020
Pruning Scheme
Runtime (sec-
onds)
SNiP
4.718
GraSP
16.406
Ours
4.876
Table 7: Benchmarking of Pruning Algorithm Runtimes; our method is faster than GraSP as the Hessian is larger than the Jacobian, but slower than SNiP for single time instance. It should be noted that our algorithm works best when iterated across several time steps, while GraSP requires iteration across the entire training set, and SNiP requires only single computation.
Canarged
700
Figure 4: Plot of Log Train Loss for 400 Unit GRU, trained Sequential MNIST. GraSP is the worst performing, followed by SNiP and then Random, which is on par with our method. L2 shown lower bound. It is surprising that random is competitive, but it is free from the gate imbalance exhibited by SNiP and GraSP.
Subsequently we present sample training curve in Figure for the lb words experiment, detailed in Table 4 Our algorithm provides significant benefit over random pruning, but still lags behind the dense model.
Dema
5299
19803
10000
30003
4C20
Figure 5: Plot Log Train Perplexity on the dataset, with 2k LSTM network. Our model clearly outperforms random pruning by a significant margin, however more work is needed before we achieve near-dense performance.
12


Reviews:
[{"review_id": "rklCPNPKur", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "OVERALL:\n\nI should first say that this is reasonably far outside my wheelhouse.\nI have never worked on RNNs or pruning.\nI also have no familiarity with the data sets used.\n\nAll these things being said, I can follow the derivations, and the idea\nseems reasonable and well-motivated, and pruning is interesting\nfor both scientific and practical reasons, and this technique seems to help a substantial amount,\nso I'm inclined to vote for acceptance, with the understanding that perhaps better informed reviewers\n will in the future point out something I have missed.\n\nDETAILED NOTES:\n\n> overparameterized networks require more storage capacity and are computationally more expensive than their pruned counterparts\nI'm with you on the storage capacity, but do any of these pruned networks actually run faster than their non-pruned counterparts?\nI thought you had to work really hard to prune to some kind of block-sparse representation to realize any speed gains.\nThis question is not rhetorical - I know very little about this topic.\n\n> Work for the present volume began by asking the question...\nI like this paragraph for motivation, but perhaps 'volume' is slightly overwrought?\n\n> For our pruning objective, we simply take the\nK weights with largest sensitivity scores, as those represent the parameters which most affect the\nJacobian objective near the initialization.\nIs there some notion of redundancy, where certain sets of parameters affect the jacobian in the same way,\nso that all but 1 element of the set could be pruned, or something?\n\nIn line 13 of algorithm 1, why do we need to sort if in the next step we just mask out\neverything with sensitivity less than D tilde k?\n\nMaybe this is a dumb question, but if you're pruning at initialization, why not\njust initialize a smaller network in such a way that you wouldn't choose to prune any of its parameters?\nAm I misunderstanding what you're doing?\n\n\n> In the prequel, we postulated t\nThe prequel?\n\nFig 1 is interesting, but it raises the question of whether you could recover a simpler\nalgorithm by just modifying random pruning so that it evenly distributes 'prunes' across\ngate and Type.\n\nIn fig 2, why are all the singular values less than 1?\nIt's not obvious to me why that should be true, unless you enforce it w/ the initialization.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rkevyhvpYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Although I worked and published on network pruning in the past, I found little overlap between my knowledge and the content of this paper. I feel therefore that I can only provide a very superficial feedback.\n\nThe authors generalize recently-developed network pruning techniques that were developed in he context of feed-forward networks, and do not require iterative pruning-retraining cycles, to RNNs. Since RNNs apply the same matrix on their hidden vector multiple times, approximate closed-form expressions for pruning criteria can be derived analytically. The pruning criterion is based on the spectrum of the Jacobian matrix of the (N+1)-th hidden unit with respect to the N-th one. A closed-form algorithm for pruning is presented, and the method is evaluated on several datasets.\n\nWhile I appreciate the neatness of deriving closed-form analytical expressions for a fast and simple pruning method, I feel that am not in a position to rate the paper. My apologies to the Authors and the Editors.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJxW5p8sOS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nNotes: \n\n  -RNN network pruning has proven to be challenging using the techniques often used with other network types.  \n\n  -One issue is that the performance of an LSTM/GRU can hinge on a few activated gates and can lead to more concentration of influence than would be seen in a feedforward network without parameter sharing between layers.  \n\n  -New objective uses 64 points to prune the network (I assume this is just the size of the minibatch).  \n\n  -Result is a 95% sparse GRU cell.  \n\n  -New idea is based on keeping weights that propagate information through many time steps.  \n\n  -Encourages \"singular values of the temporal jacobian with respect to network weights to be non-degenerate\" (I suppose this means that the gradient flowing through time will contain multiple directions of variation)  \n\n  -Introduction does a good job of introducing the key ideas.  \n\n  -J_t is a temporal jacobian of size N x N (N is number units) at time step t.  \n\n  -Chi is the spectral norm of this temporal jacobian.  I'm a bit confused by this, because my understanding is that the spectral norm is the largest singular value, but equation 3 looks like a sum over singular values, making it more like a frobenius norm?  \n\n  -This jacobian isn't tractable, so paper approximates it using a first-order taylor expansion.  So basically the pruning just amounts to taking parameters with the largest gradient?  \n\n  -Section 2.4 is confusing and seems to come out of nowhere.  Is this suggesting that the technique isn't just pruning but adding a new normalization scheme?  On second reading, this is a normalization scheme effecting which parameters to prune.  The motivation for why the gradients are normalized like this is still confusing.  If you're willing to make a linear assumption, it seems like it's enough to consider the gradient on the parameter multiplied by the magnitude of the parameter to see the overall effect of removing it?  \n\n  -The results look good, but sequential mnist is a bit of a toy task.  I'd also like to see a more fine-grained analysis showing the tradeoff between the number of units removed and the performance.  \n\n  -The paper claims that L2 pruning requires more data, but it's unclear if this really matters since the whole dataset was used to train both methods initially.  \n\n  -On Table 2 the results of the technique don't seem that much better than \"Random\".  \n\n  Review: This paper presented a fast pruning algorithm for RNNs, which uses the norm of the gradient as a guide to pruning.  I'm borderline on this paper.  The idea of using the gradient is good, but the explanation of some aspects like the normalization is confusing and felt random.  Additionally the results, while better than some other pruning techniques on RNNs, don't seem to be that much better than random.  ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on current unanimous reviews, the paper is accepted.
Decision: Accept (Poster)