Selfish Sparse RNN Training
Authors: Shiwei Liu
Decebal Constantin Mocanu
Yulong Pei
Mykola Pechenizkiy
Venue:  (2021)
Keywords: dynamic sparse training
sparse neural networks
dynamic sparse RNN training
recurrent neural networks

Abstract: Sparse neural networks have been widely applied to reduce the necessary resource requirements to train and deploy over-parameterized deep neural networks. For inference acceleration, methods that induce sparsity from a pre-trained dense network (dense-to-sparse) work effectively. Recently, dynamic sparse training (DST) has been proposed to train sparse neural networks without pre-training a large and dense network (sparse-to-sparse), so that the training process can also be accelerated. However, previous sparse-to-sparse methods mainly focus on Multilayer Perceptron Networks (MLPs) and Convolutional Neural Networks (CNNs), failing to match the performance of dense-to-sparse methods in Recurrent Neural Networks (RNNs) setting. In this paper, we propose an approach to train sparse RNNs with a fixed parameter count in one single run, without compromising performance. During training, we allow RNN layers to have a non-uniform redistribution across cell weights for a better regularization. Further, we introduce SNT-ASGD, a variant of the averaged stochastic gradient optimizer, which significantly improves the performance of all sparse training methods for RNNs. Using these strategies, we achieve state-of-the-art sparse training results, even better than dense model results, with various types of RNNs on Penn TreeBank and Wikitext-2 datasets.

Under review as a conference paper at ICLR 2021
SELFISH SPARSE RNN TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Sparse neural networks have been widely applied to reduce the necessary resource requirements train and deploy over-parameterized deep neural networks. For inference acceleration, methods that induce sparsity from pre-trained dense net- work (dense-to-sparse) work effectively. Recently, dynamic sparse training (DST) has been proposed to train sparse neural networks without pre-training large and dense network sppare-to-spaaree erated. However, previous sparse-to-sparse methods mainly focus on Multilayer Perceptron Networks (MLPs) and Convolutional Neural Networks (CNNs), failing match the performance of dense-to-sppp to-ssarse methods in Recurrent Neural Net- works (RNNs) sctting. In this paper, we propose an approach to train sparse RNNs with a fixed parameter count in one single run, without compromising performance. During training, we allow RNN layers to have a non-uniform redistribution across cell weights for a better regularization. Further, we introduce SNT-ASGD, variant of the averaged stochastic gradient optimizer, which significantly improves the performance of all sparse training methods for RNNs. Using these strategies, we achieve state-of-the of-the-art art sparse training results, even better than dense model results, with various types of RNNs on Penn TreeBank and Wikitext-2 datasets.
so that the training process can also be accel-
INTRODUCTION
Recurrent neural networks (RNNs) (Elman 1990), with variant of long short-term memory (LSTM) (Hochreiter & Schmidhuber] 1997). have been highly successful in various fields, including language
modeling (Mikolov et al.] 2010), machine translation (Kalchbrenner & Blunsom, 2013), question answering (Hirschman et al. 1999 Wang & Jiang (017)) etc. As a standard task to evaluate models' ability to capture long-range context, language modeling has witnessed great progress RNNs. Mikolov et al. (2010) demonstrated that RNNs perform much better than backoff models for language modeling. After that, various novel RNN architectures such as Recurrent Highway Networks (RHNs) 2017), Pointer Sentinel Mixture Models (Merity et al.] (017)) Neural Cache Model (Yang et al., 2018), ordered neurons LSTM MOOONNSTTE (Shen et al.) (2019). and effective regularization like variational dropout (Gal &
(Zilly et al.
GGrve et al.
2017). Mixture of Softmaxes LAWD-LSTM-MoN
Ghahramani 2016), weight tying (Inan et al., 2017). DropConnect (Merity et al.) 2018 have been
proposed significantly improve the performance of RNNs.
At the same time, as the performance of deep neural networks (DNNs) improves, the resources required to train and deploy deep models are becoming prohibitively large. To tackle this problem, various dense-to-sparse methods have been developed, including but not limited to pruning (LeCun) al. 1990 Han al. 2015), Bayesian methods (Louizos al. 2017aj Molchanov al. (017). distillation Hinton et al. 2013). L1 Regularization (Wen et al. 10)8 and low-rank decomposition
(Jaderberg et al. 2014). Given pre-trained model. these methods work effectively to accelerate the inference. Recently some dynamic sparse training (DST) approaches (Mocanu et al., 2018
Mostafa Wang 2019 Dettmers& Zettlemoyer 2019 Evei et al. 2020) have been proposed to bring efficiency for both, the training phase and the inference phase by dynamically changing the sparse connectivity during training. However, previous approaches are mainly for CNNs. For RNNs, the long-term dependencies and repetitive usage of recurrent cells make them more difficult to be sparsified (Kalchbrenner et al.) 2018; Evci et al. 2020). More importantly, the sfate-of-the-an performance achieved by RNNs on language modehing mainly associated with the optimizer, averaged stochastic gradient descent (ASGD) (Polyak & Juditsky 1992), which is not compatible with the existing DST approaches. The above-mentioned problems heavily limit the performance

---

Under review as a conference paper at ICLR 2021
(1) Weights removal (remove 50% of weights)
(3) Weights growth (arow 90% of weights)
Training epoch with SNT-ASGD
W
W
W
W
W
W
W
W
12 pruned weights
weights
3
3
(2) Cell weight redisinibution
Figure Schematic diagram of the Selfish- W,, Wy. We, W. refer to LSTM cell weights. Colored squares and white squares refer to nonzero weights and zero weights, respectively. Light blue squares are weights to removed and orange squares are weights to be grown.
of the off-the-shelf sparse training methods in the RNN field. For instance, while "The Rigged Lottery" (RigL) achieves state-of-the-en art sparse training results with various CNNs, it fails match the performance of the iterative pruning method in the RNN setting (Evci et al. 2020). In this paper, introduce algorithm train sparse RNNS with fixed number of computational costs throughout training. We abbreviate our sparse RNN training method as Selfish-RNY because our method encourages cell weights to obtain their parameters selfishly. The main contributions of this work are five-fold:
We propose an algorithm to train sparse RNNs from scratch with a fixed number pa- rameters. This advantage constrains the training costs to fraction of the costs needed for training dense model, allowing us to choose suitable sparsity levels for different types of training platforms.
We introduce SNT-ASGD, sparse variant of the non-monotonically triggered averaged stochastic gradient descent optimizer, which overcomes the over-sparsified problem of the original NT-ASGD (Merity et al. 2018) caused by dynamic sparse training.
We demonstrate state-of the sparse training performance with various RNN models, including stacked LSTMs (Zaremba al. 2014). RHNs, ordered neurons LSTM (ON- LSTM) on Penn TreeBank (PTB) dataset (Marcus et al. 1993) and AWD-LSTM-MoS on Wik dataset (Melis al. 2018).
We present an approach to analyze the evolutionary trajectory of the sparse connectivity optimized by dynamic sparse training from the perspective of graph. With this approach, we show that there exist many good structural local optima (sparse sub-networks having equally good performance) in RNNs, which can be found in an efficient and robust manner.
Our analysis shows two surprising phenomena in the setting of RNNs contrary to CNNs: (I) random-based weight growth performs better than gradient-based weight growth, (2) uniform sparse distribution performs better than Erdās-Rényi (ER) sparse initialization. These results highlight the need to choose different sparse training methods for different architectures.
2 RELATED WORK
Dense-to-Sparse. There are a large amount of works operating on a dense network to yield a sparse network. We divide them into three categories based on the training cost in terms of memory and computation.
(1) Iterative Pruning and Retraining. To the best of our knowledge, pruning was first proposed by Janowsky][195) and Mozer & Smolensky (1989) to yield sparse network from pre-trained network. Recently, Han et al. al. (2015) brought it back to people's attention based on the idea of iterative pruning and retraining with modern architectures. Some recent works were proposed to further reduce the number of iterative retraining e.g., Narang et al. 2017); ;; Zhu & Guptal (017)) Frankle Carbin (2019) proposed the Lottery Ticket Hypothesis showing that the sub-networks ("winning tickets") obtained via iterative pruning combined with their "lucky" initialization can outperform the dense networks. Zhou et al. (009)) discovered that the sign of their initialization is the crucial factor that
2

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison of different sparsity inducing approaches. Removal and Growth refer the strategies used for adaptive sparse connectivity. Fixed is possible if the parameter count is fixed throughout training. Backward Sparse means clear sparse backward pass and no need to compute or store any information of the non-existing weights.
Method
Initialization
Removal
Growth
Fixed
Backward Sparse
Iterative Pruning
dense dense
min( [@)
none no
no
ISS
group Lasso
none no
no
SET
Erdös-Rényi
min (0)
random
yes
yes
DSR
uniform
miri (0)
random
yes
yes
SNFS
uniform
meii (0)
momentum
yes no
RigL
Brdös-Rényi-kerne
mirro (0))
gradient
yes
no
Selfish-RNN
uniform
min((0)
random
yes
yes
makes the "winning tickets" work. Our work shows that there exists a much more efficient and robust way to find those "winning ticketts" without any special initialization. The aforementioned methods require at least the same training cost training dense model, sometimes even more, as pre-trained dense model is involved. We compare our method with state-of-the-art pruning method proposed by Zhu & Gupta (2077) in Appendix | With fewer training costs, our method is able to discover sparse networks that can achieve lower test perplexity than iterative pruning.
(2) Learning Sparsity During Training. There are also some works attempting to learn the sparse networks during training. Louizos et al. (2017b) and Wen et al. (0018) are examples that gradually enforce the network weights to zero via Lo and L1 regularization, respectively. Dai al. (2018) proposed a singular value decomposition (SVD) based method to accelerate the training process for L.STMs. [Lu et al. (2020a) proposed Dynamic Sparse Training to discover sparse structure by learning binary masks associated with network weights. However, these methods start with fully dense network, and hence are not memory efficient.
(3) One-Shot Pruning. Some works aim to find sparse neural networks by pruning once prior to the main training phase based on some salience criteria, such as connection sensitivity (Lee et al. 2019), signal propagation, (Lee al. 2020), and gradient signal preservation (Wang et al.) 2020). These techniques can find sparse networks before the standard training, but at least one iteration of dense model needs to be trained to identify the sparse sub-networks, and therefore the pruning process is not applicable to memory-limited scenarios. Additionally, one-shot pruning generally cannot match the performance of dynamic sparse training, especially at extreme sparsity levels (Wang et al. 2020).
Sparse-to-Sparss
Recently, many works have emerged to train intrinsically sparse neural networks from scratch to obtain efficiency both for training and inference.
(1) Static Sparse Training. Mocanu et al. (2016) introduced intrinsically sparse networks by exploring the scale-free free and small-wont world topological properties in Restricted Boltzmann Machines. Later, some works expand static sparse training into CNNs based on expander graphs and show comparable performance (Prabhu et al. 20188 Kepner & Robinett 2019).
(2) Dynamic Sparse Training. Mocanu et al. (20T8) introduced Sparse Evolutionary Training (SET) which initializes a sparse network and dynamically changes the sparse connectivity by a simple mannoeeand-regroow strategy. At the same time, DeepR (Bellec et al.] 2018) trained very sparse networks by sampling the sparse connectivity based on a Bayesian posterior. The iterative configuration updates have been proved to converge to stationary distribution. Mostafa & Wang (2019) introduced Dynamic Sparse Reparameterization (DSR) to train sparse neural networks while dynamically adjusting the sparsity levels of different layers. Sparse Networks from Scratch (SNFS) (Dettmers & Zettlemoyer 2019) improved the sparse training performance by growing free weights according to their momentum. It requires extra computation and memory to update the dense momentum tensor for each iteration. Further, [Evc et al. (2020) introduced RigL which activates weights with the highest magnitude gradients. This approach grows weights expected to receive gradients with high magnitudes, while amortizing a large number of memory requirements and computational cost caused by momentum. Due to the inherent limitations of deep learning software and hardware libraries, all of the above works simulate sparsity using binary mask over weights. More recently, [iu et al. (2020b) proved the potentials of DST by developing for the first time an independent software framework to train very large truly sparse MLPs trained with SET. However, all these works mainly focus on CNNs and MLPs, and they are not designed to match state-of-the-an performance for RNNs.
3

---

Under review as a conference paper at ICLR 2021
We summarize the properties of all approaches compared in this paper in Table | Same with SET, our method can guarantee Backward Sparse, which does not require any extra information from the removed weights. Additionally, discuss the differences among SET, pruning techniques, and our method in Appendix H
3 SPARSE RNN TRAINING
Our sparse RNN training method is illustrated in Figure T with LSTM as a specific case of RNNs. Note that method can be easily applied any other RNN variants. The only difference is the number of cell weights. Before training, we randomly initialize each layer at the same sparsity (the fraction of zero-valued weights), that the training costs are proportional to the dense model the beginning. To explore more sparse structures, while to maintain a fixed sparsity level, we need to optimize the sparse connectivity together with the corresponding weights (a combinatorial optimization problem). We apply dynamic sparse connectivity and SNT-ASGD to handle this combinatorial optimization problem. The pseudocode of the full training procedure of our algorithm is shown in Algorithm
3.1 DYNAMIC SPARSE CONNECTIVITY
We consider uniform sparse initialization, magnitude weight removal, random weight growth, cell weight redistribution together as main components of our dynamic sparse connectivity method, which ensure fixed number of parameters and clear sparse backward pass, as discussed next.
Notation. Given a dataset of samples D = { Ms) } and a network f(;;; 0) parameterized by
0. We train the network to minimize the loss function Di=1 L(s(a,; 0), The basic mechanism of sparse neural networks is to use fraction of parameters to reparameterize the whole network, while preserving the performance as much possible. Hence, sparse neural network can be denoted as (z; 0.) with a sparsity level Uniform Sparse Initialization. First, the network is uniformly initialized with a sparse distribution in which the sparsity level of each layer is the same S. More precisely, the network is initialized by:
liello. where || llo the fn-norm.
[0llo
02 = 0 O M
(1)
where 9 is a dense weight tensor initialized in standard way; M a binary tensor, which nonzero elements are sampled uniformly based on the sparsity S; @ refers to the Hadamard product. Magnitude Weight Removal. For non-RNN layers, we use magnitude weight removal followed by random weight growth to update the sparse connectivity. We remove fraction of weights with the smallest magnitude after each training epoch. This step is performed by changing the binary tensor M, as follows:
M = M - P
(2)
where P is a binary tensor with the same shape as M, which the nonzero elements have the same indices with the top-p magnitude nonzero weights in 6., with || pll Random Weight Growth. To keep fixed parameter count, we randomly grow the same number of weights immediately after weight removal, by:
M M + R
(3)
where R is a binary tensor where the nonzero elements randomly located the position of zero elements of M. We choose random growth to get rid of using any information of the non-existing weights, so that both feedforward and backpropagation are completely sparse. It is more desirable to have such pure sparse structures as it enables the possibility of conceiving in the future specialized hardware accelerators for sparse neural networks. Besides, our analysis of growth methods in Section 4.3 shows that random growth can explore more sparse structural degrees of freedom than gradient growth, which might be crucial to the sparse training.
Cell Weight Redistribution. Our dynamic sparse connectivity differs from previous methods mainly in cell weight redistribution. For RNN layers, the naive approach is to sparsify all cell weight tensors independently at the same sparsity, as shown in Liu et al. (2019) which is straightforward extension of applying SET to RNNs. Essentially, it is more desirable to redistribute new parameters to cell weight tensors dependently, as all cell weight tensors collaborate together to regulate information. Intuitively, we redistribute new parameters in a way that weight tensors containing more large- magnitude weights should have more parameters. Large-magnitude weights indicate that their loss
4

---

Under review as a conference paper at ICLR 2021
gradients large and few oscillations occur. Thus, weight tensors with more large- magg-mag connections should reallocated with more parameters to accelerate training. Concretely, for each RNN layer I, we remove weights dependently given by ascending sort:
Sortp (6),,.., (e(1)
(4)
where 02.,,,,.,0 } are all weight tensors within each cell, and Sort, returns p indices of the smallest-magnitude weights. After weight removal, new parameters are uniformly grown each weight tensor to implement our cell weight redistribution gradually. We also tried other approaches including the mean value of the magnitude of nonzero weights or the mean value the gradient magnitude of nonzero weights, but our approach achieves the best performance, as shown in Appendix We further demonstrate the final sparsity breakdown of cell weights learned by our method in Appendix M and observe that weights of forget gates are consistently sparser than other weights for all models. Note that redistributing parameters across cell weight tensors does not change the FLOP counting, as the sparsity of each layer is not changed. In contrast, the across-layer weight redistribution used by DSR and SNFS affects the sparsity level each layer. As a result, will change the number of floating point operations (FLOPs).
Similar with SNFS, We also decay the removing rate to zero with cosine annealing. We further use Eq. (T) to enforce the sparse structure before the forward pass and after the backward pass, so that the zero-valued weights will not contribute to the loss. And all the newly activated weights are initialized
Number of Weights x104
Algorithm 1: Selfish-RNN algorithm
1: Input: Model weight 0, number of layer L,
sparsity S, removing rate p. training epoch n;
EVT-4662 PO
2: % Sparse Initialization
MT-AGGO
3: for -- 1 to L do
4: Initialize the network with Eq.
40
5: end for
20
6: % Training
for epoch = 1 to n do
8: @NNormal training process
10
70 90
Epoch [#]
150
250
9: 0₂ < SNT-ASGD(B.)
10: for i= L do
Figure The number of weights whose mag- nitude is larger than 0.1 during training for ON-LSTM. The solid lines represent SNT- ASGD and dashed lines represent standard NT-ASGD, ihl, ih2, and ih3 refer to input weights in the first, second and third LSTM layer.
11:
Weight removal with Eq.
12:
Cell weight redistribution with Eq. 4
13:
Weight growth with Eq.
14: end for
15:
--DeeayRemovingRate((y))
16:
end for
3.2 SPARSE Y TRIGGERED ASGD
Non- monmooooooiially Triggered ASGD (NT-ASGD) has been shown to achieve surprising performance with various RNNs (Merity et al. 2018 Yang et al. 2018 Shen et al. 2019). However, it becomes less appealing for sparse RNNs training. Unlike dense networks in which every parameter in the model is updated at each iteration, for sparse networks, the zero-valued weights remain they are not activated. Once these zero-valued weights are activated, the original averaging operation of standard NT-ASGD will immediately bring them close to Thereby, after the averaging operation is triggered, the number of valid weights will decrease sharply as shown in Figure To alleviate this problem, we introduce SNT-ASGD as following:
when
if m; = 0, Vi,
ΣK WhAt (K +++1
(5)
if m; 1, Vi.
where ti; is the value returned by SNT-ASGD for weight wy; Wiet represents the actual value of weight w; at the 4th iteration; m, = if the weight w; exists and m, = 0 means that the weight w; does not exist; T, is the iteration in which the weight w; grows most recently; and K is the total
5

---

Under review as a conference paper at ICLR 2021
number of iterations. We demonstrate the effectiveness of SNT-ASGD in Figure 2 At the beginning. trained with SGD, the number weights with high magnitude increases fast. However, the trend starts to descend significantly once the optimization switches to NT-ASGD at the 80 epoch, whereas the trend of SNT-ASGD continues to rise after a small drop caused by the averaging operation.
To better understand how proposed components, cell weight redistribution and SNT-ASGD, improve the sparse RNN training performance, we further conduct an ablation study Appendix A clear see that both of them lead to significant performance improvement.
EXPERIMENTAL RESULTS
We evaluate Selfish-RNN with various models including stacked LSMMs, RHNs, ON-LSTM on the Penn TreeBank dataset and AWD-LSTM-MoS the WikiText-2 dataset. The performance of Selfish-RNN is compared with state-of-the-a sparse inducing techniques, including Intrinsic
Sparse Structures (ISS) (Wen al. 2018 SET, DSR, SNES, and RigL. ISS is method to explore sparsity inside RNNs by using group Lasso regularization. We choose Adam (Kingma & Ba 2014) optimizer for SET, DSR, SNFS, and RigL. We also evaluate our methods with two state-of-the-ar RNN models, ON-LSTM on PTB and AWD-LSTM-MOS on Wikitext-2, as reported in Appendix D and Appendix respectively.
4.1 STACKED LSTMS
Table 2: Single model perplexity on validation and test sets for the Penn Treebank language modeling task with Stacked LSTMs and RHNs. FLOPs required to train the entire model and test on single sample reported. Methods with superscript indicates reported results in the corresponding papers. "Static-ER" and "Static-uni" are the static sparse network trained from scratch with ER distribution and uniform distribution, respectively. "Small" refers the small-dense network.
Stacked LSTMs
RHN
Models
FLOPs
FLOPs (Test)
Val
Test
FLOPs (Train)
FLOPs (Test)
Val
Test
(Train)
Dense*
1x(3.1e16)
1x(7 (0)))
82.57 74.51
78.57 72.40
1x(6.5e16) 1x
1x(3.3e10)
67.90
65.40
Dense (NT-ASGD)
1x
1x
1x
63.44
61.84
S=0.67
S=0.53
Small (NT-ASGD)
0.33x
0.33x
88.67
86.33
0.47x
0.47x
70.10
Static-ER (SNT-ASGD)
0.33x
0.34x
81.02
79.30
0.47x
0.47x
75.74
73.21
Static-uni (SNT-ASGD)
0.33x
0.33x
80.37
78.61
0.47x
0.47x
74.11
71.83
ISS
0,28x
0,20x
80.70
76.78
0.50x
0.47x
68.10
65.40
SET
0.33x
0.34x
87.30
85.49
0.47x
0.47x
63.66
61.08
DSR
0.38x
0.40x
89.95
88.16
0.47x
0.47x
65.38
63.19
SNFS
0.63x
0.38x
88.31
86.28
0.63x
0.45x
74.02
70.99
RigL
0,33x
0,34x
88.39
85.61
0.47x
0.47x
67.43
64,41
RigL (SNT-ASGD)
0.33x
0.34x
78.31
75.
0.47x
0.47x
64.82
62.47
Selfish-RNN
0.33x
0.33x
73.76
71.65
0.47x
0.47x
62.10
60.35
S=0.62
S=0.68
0.32x
0.23x
78.67
75.53
0.34x
0.32x
70.30
67.70
RigL (SNT-ASGD)
0.38x
0.39x
77.16
74.76
0.32x
0.32x
69.32
66.64
Selfish-RNN
0.38x
0.38x
73.50
71.42
0.32x
0.32x
66.35
64.03
As introduced by Zaremba al. (2014), stacked LSTMs (large) is two-layer LSTM model with
1 1500 hidden units for each LSTM layer. We choose the same sparsity as ISS, 67% and 62%. We empirically found that 0.7 is safe choice for the removing rate of stacked LSTMs. The clip norm is set to 0.25 and all models are trained for 100 epochs.
Results shown in the left side of Table 2 To evaluate sparse training method fairly, also provide a new dense baseline trained with the standard NT-ASGD, achieving lower test perplexity than the widely-used baseline. We also test whether small dense network and static sparse network

---

Under review as a conference paper at ICLR 2021
with the same number of parameters Selfish-RNN can match the performance of Selfish-RNN We train a dense stacked LSTMs with 700 hidden units, named as "Small". In line with the previous studies (Mocanu et al.) 2018 Mostafa & Wang 2019 Evei et al. 2020), both static sparse networks and the small-dense network fail to match the performance of Selfish-NNN. Training a static sparse network from scratch with uniform distribution performs better than the with ER distribution. Trained with Adam, all sparse training techniques fail to match the performance of ISS and dense models. Models trained with SNT-ASGD obtain substantially lower perplexity, and Selfish-RNN achieves the lowest one, even better than the new dense baseline with much fewer training costs.
Table 3: Performance comparison of all DST methods trained with Adam, momentum SGD and SNT-ASGD with stacked LSTMs on PTB.
Models
#Param
FLOPs (Train)
FLOPs (Test)
Val
Test
Dense*
66.0M 66.0M
1x (3.1e16)
1x (7.2e10)
82.57
78.57
Dense (NT-ASGD)
1x
1x
74.51
72.40
S=0.67
DSR (Adam)
21.8M
0.38x
0.40x
89.95
88.16 16
SNFS (Adam)
21.8M
0.63x
0.38x
88.31
86.28
RigL (Adam)
21.8M
0.33x
0.34x
88.39
85.61
SET (Adam)
21.8M
0.33x
0.34x
87.30
85.49
Selfish-RNN RNNN (Adam)
21.8M
0.33x
0.33x
85.70
82.85
SNFS (Momentum SGD)
21.8M
0.61x
0.36x
90.09
87.98
SET (Momentum SGD)
21.8M
0.33x
0.34x
85.73
82.52
Rigl. (Momentum SGD)
21.8M
0.33x
0.34x
84.78
80.81
DSR (Momentum SGD)
21.8M
0.32x
0.32x
82.89
80.09
Selfish-RNN (Momentum SGD)
21.8M
0.33x
0.33x
82.48
79.69
SNES (SNT-ASGI)
21.8M
0.63x
0.40x
82.11
79.50
RigL. (SNT-ASGD)
21.8M
0.33x
0.34x
78.31
75.90
SET (SNT-ASGD)
21.8M
0.33x
0.34x
76.78
74.84
Selfish-RNN (SNT-ASGD)
21.8M
0.33x
0.33x
73.76
71.65
DSR (SNT-ASGD)
21.8M
0.32x
0.32x
72.30
70.76
To understand better the effect of different optimizers on different DST methods, we report the performance all DST methods trained with Adam, momentum SGD, and SNT-ASGD. The learning rate of Adam is set as 0.001. The learning rate of momentum SGD is 2 decreased by factor of 1.33 once the loss fails to decrease and the momentum coefficient is 0.9. The weight decay is set as 1.2e-6 for all optimizers. For SNFS (SNT-ASGD), gradients. as SNT-ASGD does not involve any momentum terms. We use the same hyperparameters for all DST methods. The results shown in Table 3 It is clear that SNT-ASGD brings significant perplexity improvements to all sparse training techniques. This further stands as empirical evidence that SNT-ASGD is crucial improve the sparse training performance in the RNN setting. Moreover, compared with other DST methods, Selfish-RNN is quite robust to the choice of optimizers due to its simple scheme to update sparse connectivity. Advanced strategies such across-layer weight redistribution used in DSR and SNFS, gradient- based weight growth used in RigL and SNFS heavily depend on optimizers. They might work decently for some optimization methods but may not work for others.
replace momentum of weights with their
Additionally, note that different DST methods use different sparse distributions, leading to very different computational costs even with the same sparsity. We also report the approximated training and inference FLOPs for all methods. The FLOP gap between Selfish-RNN and RigL is very small, whereas SNFS requires more FLOPs than our method for both training and inference (see Appendix L for details on how FLOPs are calculated). ISS achieves a lower number FLOPs, since it does not sparsify the embedding layer and therefore, their LSTM layers much more sparse than LSTM layers obtained by other methods. This would cause a fewer number FLOPs as LSTM layers typically require more FL.PPs than other layers.
7

---

Under review as a conference paper at ICLR 2021
4.2 RECURRENT HIGHWAY NETWORKS
Recurrent Highway Networks Zilly et al., 2017) is variant of RNNs allowing RNNs to explore deeper architectures inside the recurrent transition. See Appendix C for experimental settings of RHN. The results are shown in the right side of T Selfish-RNN achieves better performance than the dense model with half FLOOPs. Unlike the large FLOP discrepancy of stacked L.S,Ms, the FLOP gap between different sparse training techniques for RHNs is very small, except SNFS which requires computing dense momentum for each iteration. Additionally, ISS has similar FLOPs with Selfish-RNi for RHN, as it sparsifies the embedding layer as well.
4.3
ANALYZING THE PERFORMANCE OF SELFISH-RN -NNN
Sparse topology GED
0.8
0.8
0.6
Sparse topology
0.6
0.4
0.4
lstml_.
lstml_i
0.2
lstml hh
0.2
tstll .hh
lstm2,
lstm2 jh
0.0
1stm2
0.0
lstm2
100
90
100
Epoch [#]
Epoch [#]
Figure 3: (left) One aanom-iiitializeee sparse network trained with Selfish-RNY RNNN end up with very different sparse connectivity topology. (right) Two aume-nittialized networks trained with different random seeds end up with very different sparse connectivity topologies. ih the input weight tensor comprising four cell weights and hh is the hidden state weight tensor comprising four cell weights.
Analysis of Evolutionary Trajectory of Sparse Connectivity. The fact that Selfish-RNN consis- tently achieves good performance with different runs naturally raises some questions: e.g., are final sparse connectivities obtained by different runs similar or very different? Is the distance between the original sparse connectivity and the final sparse connectivity large or small? To answer these questions, we investigate a method based on graph edit distance (GED) (Sanfeliu & Fu 1983) to measure the topological distance between different sparse connectivities learned by different runs. The distance is scaled between 0 and 1. The smaller the distance is, the more similar the two sparse topologies are (See Appendix 0 for details on how we measure the sparse topological distance).
The results are demonstrated in Figure 3 Figure Heft shows how the topology of one random- initialized network evolves when trained with SeInih-RNNN We compare the topological distance between the sparse connectivity obtained at the 5thh epoch and the sparse connectivities obtained in the following epochs. We can see that the distance gradually increases from 0 to a very high value 0.8, meaning that Selfish-RNN optimizes the initial topology very different one after training. Moreover, Figure r3iri illustrates that the topological distance between two same-initialized networks trained with different seeds after the 4th epoch. We can see that starting from the same sparse topology, they evolve to completely different sparse connectivities. Note that even when leading to completely different sparse connectivities, different runs achieve similarly good performance, which indicates that in the case of RNNs there exist many good local optima in terms of sparse connectivity that can have equally good performance. This phenomenon complements the findings of Liu et al. (2020c) which show that there are numerous sparse sub-networks performing similarly well the context of MI.Ps.
Analysis of Sparse Initialization. We compare two types of sparse initialization, ER distribution and uniform distribution. Uniform distribution namely enforces the sparsity level each layer to be the same as S. ER distribution allocates higher sparsity to larger layers than smaller ones. Note that its variant Erdōs-Ro Frrds-RRéni---ee Rényi-kernnee proposed by Evci et al. (2020) scales back to ER for RNNs, as no kernels involved. The results are shown the Static group Table 2 We can that uniform distribution outperforms ER distribution consistently. Moreover, ER usually causes RNN layers to be less sparse than other layers, resulting in small increase of FLOPs.
8

---

Under review as a conference paper at ICLR 2021
Analysis of Growth Methods. Methods that leverage gradient- weight growth (SNFS and RigL) have shown superiority over the methods using random-based weight growth for CNNs. However, observe different behavior with RNNs. We set up controlled experiment to compare these two methods with SNT-ASGD and momentum SGD. We report the results with various update intervals (the number of iterations between sparse connectivity updates) in Figure growth in most cases. And there is an increased performance gap the update interval increases. Our hypothesis that random growth helps in exploring better the search space, as it naturally considers large number of various sparse connectivities during training. which is crucial the performance of dynamic sparse training. Differently, gradient growth drives the network topology towards some similar local optima for the sparse connectivity as it uses greedy search strategy (highest gradient magnitude) at every topological change. However, benefits provided by high-magnitude gradients might change dynamically afterwards due to complicated interactions between weights. We empirically illustrate hypothesis via the proposed distance measure between sparse connectivities in Appendix K
4 Surprisingly, gradient-based growth performs worse than random-
stacked -LSMM- (random)
85
slacked-LSTMM (gredient)
65
Test Perplexity
(random)
Test Perplexity
80
80
RHNNs (gradient)
75
75
70
70
(random)
stacked-LSTMS (gradient)
RHiss (random)
(gradient)
100
500
1327
100
500
1327
Update Interval (AT)
Update Interval (AT)
Figure 4: Comparison between
growth and gradient-based growth. (Ieft) Models trained with SNT-ASGD. (right) Models trained with momentum SGD.
Analysis of Hyper-parameters. The sparsity S and the initial removing rate p are two hyper- parameters of our method. We show their sensitivity analysis in Appendix F and Appendix G We find that Selfish Stacked LSTMs, RHNs, ON-LSTM, and AWD-LSTM- need around 25%, 40%, 45%, and 40% parameters reach the performance of their dense counterparts, respectively. And our method is quite robust to the choice of the initial removing rate.
5 CONCLUSION
In this paper, we proposed an approach to train sparse RNNs from scratch with fixed parameter count throughout training. Further, we introduced SNT-ASGD, a specially designed sparse optimizer for training sparse RNNs and we showed that it substantially improves the performance of all dynamic sparse training methods in RNNs. We observed that random-based growth achieves lower perplexity than gradient-based based growth in the case of RNNs. Further, we developed an approach to compare two different sparse connectivities from the perspective of graph theory. Using this approach, we found that random-based growth explores better the topological search space for optimal sparse connectivities, whereas gradient-bras growth is prone to drive the network towards similar sparse connectivity patterns. opening the path for better understanding of sparse training.
REFERENCES
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In International Conference on Learning Representations, 2018. URL
net woormoiiduBB https::/opeereviiie wttp:rrrrweeeeettfooooii-------- BBO_C_
Rui Dai, Lefei Li, and Wenjian Yu. Fast training and model compression of gated mns via singular value decomposition. In 2018 International Joint Conference on Neural Networks (IJCNN), pp. 1-7, IEEE, 2018
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv: arXiv:1907.048400 2019.

---

Under review as a conference paper at ICLR 2021
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):179-2 2111 1990.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference Machine Learning, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable
neural networks. In International Conference on Learning Representations, 2019. URL https
//openreview.nen net/ [/operreeeess.neeeefooooooooores -
Yarin Gal and Zoubin Ghahramani. A theoretically grounded application of dropout in recurrent neural networks. Advances in neural information processing systems, pp. 1019-1027, 2016.
Edouard Grave, Armand Joulin, and Nicolas Usunier. Improving neural language models with continuous cache. In International Conference on Learning Representations, 2017. URL
htttps://openreeieew net. forummiddai14211
Scott Gray, Alec Radford, and Diederik P Kingma. Gpu kernels for block-sparse weights. arXiv preprint SCLV:11111002244 3, 2017.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances neural information processing systems, pp. 1135-1143, 2015.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representations, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge neural network. arXiv preprint arXiv:1503 020531, 2015.
Lynette Hirschman, Marc Light, Eric Breck, and John Burger. Deep read: A reading comprehension system. In Proceedings of the 37th annual meeting of the Association for Computational Linguistics, pp. 325-332, 1999.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Hakan Inan, Khashayar Khosravi, and Richard Socher. Tying word vectors and word classifiers: A loss framework for language modeling. In International Conference on Learning Representations, 2017.
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. arXiv preprint arXiv: 1405.3660,.. 2014.
Steven A Janowsky. Pruning versus clipping in neural networks. Physical Review A, 33( 2):6600, 1989.
Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1700-1709, 2013.
Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury. Norman Casagrande, Edward Lockhart, Florian Stimberg, Aaron van den Oord, Sander Dieleman, and Koray Kavukcuoglu. Efficient neural audio synthesis. In International Conference Learning Representations, 2018.
Jeremy Kepner and Ryan Robinett. Radix-net: Structured sparse matrices for deep neural networks. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 268 274. IEFE, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6949 69800, 2014.
Ben Krause, Emmanuel Kahembwe, lain Murray, and Steve Renals. Dynamic evaluation of neural sequence models. In International Conference on Machine Learning, pp. 2766-2775, 2018.
10

---

Under review as a conference paper at ICLR 2021
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr SNIP: SINGLE-SHOT NETWORK
PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference Learning
Representations, 2019. URL http::::: //tp:revie//eeeeeeer net/ forum net/ Bttp://ooummddBB22eeeiee B
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip S. Torr. A signal propagation
perspective for pruning neural networks at initialization. In International Conference on Learning Representations, 2020. URL httpt::://// /ttp:///pppp/eeeeeee///ee/ee/eee
Yixuan Li, Jason Yosinski, Jeff Clune, Hod Lipson, and John E Hoperoft. Convergent learning: Do different neural networks learn the same representations? In Iclr, 2016.
Junjie Liu, Zhe XU, Runbin SHI, Ray C. C. Cheung, and Hayden K.H. So. Dynamic sparse training: Find efficient sparse network from scratch with trainable masked layers. International Conference on Learning Representations, 2020a.
id=SJ]bGGrttDR
Shiwei Liu, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Intrinsically sparse long short- term memory networks. arXiv preprint 1w0iv:/901.090 2019.
Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neurons on commodity hardware. Neural Computing and Applications, pp. 1-16, 2020b.
Shiwei Liu, TT van der Lee, Anil Yaman, Zahra Atashgahi, D Ferrar, Ghada Sokar, Mykola Pech- enizkiy, and DC Mocanu. Topological insights into sparse neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2020c.
Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. In Advances in Neural Information Processing Systems, pp. 3288 0398,, 2017a.
Christos Louizos, Max Welling, and Diederík P Kingma. Learning sparse neural networks through 1.0 regularization. In International Conference on Learning Representations, 2017b.
Rongrong Ma, Jianyu Miao, Lingfeng Niu, and Peng Zhang. Transformed 11 regularization for learning sparse deep neural networks. Neural Networks, 199:286-298, 2019.
Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building large annotated corpus of english: The penn treebank. 1993.
Gábor Melis, Chris Dyer, and Phil Blunsom. On the state of the art of evaluation in neural language models. In International Conference on Learning Representations, 2018. URL https: openreview wwweeeewwwwweeeeeeeeeeeeee http://rrounnnyyyyyyery
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM
language models. In International Conference on Learning Representations, 2018. URL https
//openreview.oo nnt/ font:fforumt id= S1
Tomáš Mikolov, Martin Karafíát, Luká's Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association, 2010.
Decebal Constantin Mocanu, Elena Mocanu, Phuong H. Nguyen, Madeleine Gibescu, and Antonio Liotta. A topological insight into restricted boltzmann machines. Machine Learning, 104(2): 243-270, Sep 2016. ISSN 1573-0565. doi: 10. 1001000/1119944-1-6-555000 URL https::/t/// //op::///or doi Ttg/10.1007. s 0994-016-5570--
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Communications, 911:23383, 2018.

---

Under review as a conference paper at ICLR 2021
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. 2098-2407, JMLR. org, 2017.
Reza Moradi, Reza Berangi, and Behrouz Minaei. Sparsemaps: convolutional networks with sparse feature maps for tiny image classification. Expert Systems with Applications, 119:142-154, 2019.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning. 2019.
Michael C Mozer and Paul Smolensky. Using relevance to reduce network size automatically. Connection Science, 1(1):3-16, 1989.
Sharan Narang, Erich Elsen, Gregory Diamos, and Shubho Sengupta. Exploring sparsity in recurrent neural networks. In International Conference Learning Representations, 2017.
NVIDIA. Nvidia a100 tensor core gpu architecture. Retrieved from:
hwtp::/wwwwwwwwwooooooooooo///ne whitepaper.pdf. 2020.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4))838-88) 855, 1992.
Ameya Prabhu, Girish Varma, and Anoop Namboodiri. Deep expander networks: Efficient deep networks from graph theory. In Proceedings of the European Conference Computer Vision (ECCV), pp. 20-35, 2018.
Alberto Sanfeliu and King-Sun Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3):353-366 1983.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. ICLR, 2014.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference Learning Representations, 2019.
Chaoqi Wang, Guodong Zhang, and Roger Grosse Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020. URL
https: http:///ppeeeeieeve wtt.:eteoooom.dddoe........
Shuohang Wang and Jing Jiang. Machine comprehension using match-lstm and answer pointer. In International Conference Learning Representations, 2017.
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. In International Conference Learning Representations, 2018. URL URthttss: htt.itttt//ppeereviiiii feet/forum?id=rkke..
Jie Yang and Jun Ma. Forwardr neural network training using sparse representation. Expert Systems with Applications, 16:255-264, 2019.
Zhilin Yang. Zihang Dai, Ruslan Salakhutdinov, and William W. Cohen. Breaking the softmax bottle- neck: high-rank RNN language model. International Conference on Learning Representations, 2018. URL httthhttt////eeeet
net. wtw.m/orrmmmmmm d=H.w75G- fow.oormmmm.......s...... C7
Wojeiech Zaremba, llya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. arXiv preprint 1409 2014.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems, pp. 3597-3607, 2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy pruning for model compression. arXiv preprint arXiv: 17100177, 2017.
12

---

Under review as a conference paper at ICLR 2021
Julian Georg Zilly, Rupesh Kumar Srivastava, Jan Koutník, and Jürgen Schmidhuber. Recurrent highway networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 4189-4198. JMLR. org, 2017.
A ABLATION STUDY
To verify if the improvement shown above caused by the cell weight redistribution or the Sparse NT-ASGD, conduct ablation study for all architectures. To avoid distractive factors, all models use the same excluded. We present the validation and testing perplexity for variants of our model without these two contributions, as shown in Table 4 Not surprisingly, removing either of these two novelties degrades the performance. There is a significant degradation in the performance for all models, up to 13 perplexity point, if the optimizer switches to the standard NT-ASGD. This stands as empirical evidence regarding the benefit of SNT-ASGD. Without cell weight redistribution, the testing perplexity also rises. The only exception is RHN whose number of redistributed weights in each layer is only two. This empirically shows that cell weight redistribution is more effective for the models with more cell weights.
with the ones reported in the paper. And the use of finetuming is not
Table 4: Model ablation of test perplexity for Selfish-RNN for stacked LSTMs, RHNs, ON-LSTM on Penn Treebank and AWD-LSTM-MoS on WikiText-2.
Methods
Stacked LSTMs
RHNs
ON-LSTM
AWD-LSTM-MoS
Selfish-RNN
71.65
60.35
55.68
63.05
w/o Cell weight redistribution
72.89
60.26
57.48
65.27
w/o Sparse NT-ASGD
73.74
69.70
69.28
71.65
B COMPARISON OF DIFFERENT CELL WEIGHT REDISTRIBUTION METHODS
In Table 5 we conduct a small experiment to compare different methods of cell weight redistribution with stacked LSTMs, including redistributing based on the mean value of the magnitude of nonzero weights from different cell weights and the mean value of the gradient magnitude of nonzero weights.
Table 5: A small experiment about the comparison among different cell weight redistribution methods. The experiment evaluated with stacked I. LSTMs on Penn Treebank.
Cell weight redistribution
#Param
Validation
Test
Mean of the magnitude of nonzero weights Mean of the gradient magnitude of nonzero weights
21.8M
74.04
72.40
21.8M
74.54
72.31
Ours
21.8M
73.76
71.65
C EXPERIMENTAL DETAILS FOR RHN
Recurrent Highway Networks Zilly et al. 2017) is variant of RNNs allowing RNNs to explore deeper architecture inside the recurrent transition. Instead of stacking recurrent layers directly, RHN stacks multiple highway layers on top of recurrent state transition. Within each highway layer, free weights are redistributed across the input weight and the state weight. The sparsity level is set the same as ISS, 67.7% and 52.8%. Dropout rates are set to be 0.20 for the embedding layer, 0.65 for the input, 0.25 for the hidden units, and 0.65 for the output layer. The model is trained for 500 epochs with learning rate of 15, batch size of 20, and sequence length of 35. At the end of each training epoch, new weights are redistributed across the weights of the H nonlinear transform and the T' gate.
13

---

Under review as a conference paper at ICLR 2021
D EXPERIMENTAL RESULTS WITH ON-LSTM
Table Single model perplexity on validation and test sets for the Penn Treebank language modeling task with ON-LSTM. Methods with "ASGD" are trained with SNT-ASGID. The numbers reported are averaged over five runs.
Table 7: Single model perplexity on vali- dation and test sets for the WikiText-2 lan- guage modeling task with AWD-LSTM- MoS. Baseline AWD-LSTM-MMO ob- tained from Yang et al. (2018). Meth- ods with "ASGD" are trained with SNT-
Models
#Param
Val
Test
ASGD.
Densc1000
25M
58.29 + 0.10
56.17
0.12
Don
25M
56.28 0.19
Models
#Param
Val
Test
SET
11,3M
65.90
63.56
0.14
Dense
35M
66.01
63.33
DSR
11.3M
0.007
SET
15.6M
72.82
69.61
SNFS
11.3M
0.10
6.15
DSR
15.6M
69.95
66.93
RigL
11.3M
62.01 0.05
0.13
SNES
15.6M
79.97
76.18
RigL1000 (ASGD)
11.3M
0.009 0.08
RigL
15.6M
71.36
68.52
RigI-1300 (ASGD)
11.3M
59.10 + 0.05
57.44
RigL (ASGD)
15.6M
68.84
65.18
Selfish-RNNion
11.3M
58.17 + 0.06
56.31 + 0.10
Solfish-RNI
15.6M
65.96
63.05
DalfishRRNN.an
11.3M
57.67 + 0.03
55.82 = 0.11
Proposed by Shen et al. (0199) recently, ON-LSTM can learn the latent tree structure of natural language by learning the order of neurons. For fair comparison, we use exactly the same model nyper-parametery and regularization used in ON-LSTM. We set the sparsity of each layer to 55% and the initial removing rate to 0.5. We train the model for 1000 epochs and rerun SNT-ASGD as a fine-tuning step once at the 500th epoch, dubbed Selfish-RNN 6, SelfishRRNN outperforms the dense model while reducing the model size to 11 11.3M. Without SNT-ASGD, sparse training techniques can not reduce the test perplexity 60. SNT-ASGD is able to improve the performance of Rigl. by perplexity. Moreover, one interesting observation that of the regularizations used in the standard ON-LSTM, DropConnect, is perfectly compatible with our method, although it also drops the hidden-to-hidden weights out randomly during training.
As shown in Table
In our experiments we observe that Selfish-RNN benefits significantly from the second fine-tuning operation. We scale the learning schedule to 1300 epochs with two fine-tuning operations after 500 and 1000 epochs, respectively, dubbed Selfish-RNN 1300- It is interesting that Selfish-RNN 1300 can achieve lower testing perplexity after the second fine-tuning step, whereas the dense model Dense1300 can not even reach again the perplexity that it had before the second fine-tuning. The heuristic explanation here is that our method helps the optimization escape the local optima or local saddle point by optimizing the sparse structure, while for dense models whose energy landscape is fixed, it is very difficult for the optimizer to find its way off the saddle point or the local optima.
E EXPERIMENTAL RESULTS WITH AWD-LSTM-MOS
We also evaluate Selfish-RNY on the WikiText-2 dataset. The model we choose is AWD-LSTM-MOS YYang et al. 2018), which the state-of-the-art RNN-based language model. replaces Softmax with Mixture of Sofimaxes (MoS) to alleviate the Softmax bottleneck issue in modeling natural language. For a fair comparison, we exactly follow the model hyper-parameters and regularization used in WWD-LSTM-MoS. We sparsify all layers with 55% sparsity except for the prior layer its number of parameters is negligible, We train our model for 1000 epochs without finetuning or dynamical evaluation (Krause al. 2018) to simply show the effectiveness of our method. As demonstrated in Table 7 Selfish AWD-LSTM-ME can reach dense performance with 15.6M parameters.
F EFFECT OF SPARSITY
There is a trade-off between the sparsity level S and the test perplexity of SeIfish-RNN. When there too few parameters, the sparse neural network will not have enough capacity to model the data. If the sparsity level is too small, the training acceleration will be small. Here, we analyze this trade-off by varying the sparsity level while keeping the other experimental setup the same, shown in
14

---

Under review as a conference paper at ICLR 2021
85
85
Selfish Stacked LSTMs
Selfish Stacked LSTMs
Seffish RHNs
Seffish RHNs
Test Perplexity
Seffish ON-LSTM
Test perplexits
Seffish ON-LSTM
75
Seffish AWD-LSTTM-NOS
75
Seffish AWD-LSTMM-NOS
70
70
65
65
60
60
0.50
0.60
0.70 Sparsity
0.80
0.90
0.3
0.5 Initial pruning rate
0.7
(a) Performance Sensitivity of Sparsity
(b) Performance Sensitivity of Removing rate
Figure 5: Sensitivity analysis sparsity levels and the initial removing rate for Selfish stacked LSTMs, RHNs, ON-LSTM, and AWD-LSTM-MoS. (a) Test perplexity of all models with various sparsity levels. The initial removing rate of stacked LSTMs is 0.7, the rest is 0.5. The dashed lines represent the performance of dense models. (b) Test perplexity of all models with different initial removing rates. The sparsity level is 67%, 52.8%, 55% and 55% for Selfish stacked LSTMs, RHNs, ON-LSTM, and AWD-LSTM-MOS, respectively.
Figure We find that Selfish Stacked LSTMs, RHNs, ON-LSTM, and AWD-LSTM-MoS need around 25%, 40%, 45%, and 40% parameters to reach the performance of their dense counterparts, respectively. Generally, the performance of sparsified models is decreasing as the sparsity level increases.
G EFFECT OF INITIAL REMOVING RATE
The initial removing rate p determines the number of removed weights at each connectivity update. We study the performance sensitivity of our algorithm to the initial removing rate p by varying E [0.3, 0.5, 0.7]. We set the sparsity level of each model as the one having the best performance in Figure Sa Results are shown in Figure 5b We can clearly see that our method is very robust the choice of the initial removing rate.
H DIFFERENCE AMONG SET, SELFISH- RNN AND ITERATIVE PRUNING METHODS
The topology update strategy of Selfish-RRL RNN differs from SET in several important features. (1) automatically redistribute weights across cell weights for better regularization, (2) we use magnitude- based removal instead of removing fraction of the smallest positive weights and the largest negative weights, (3) we use uniform initialization rather than non-uniform sparse distribution like ER or ERK, it consistently achieves better performance. Additionally, the optimizer proposed in this work. SNT-ASGD, brings substantial perplexity improvement to the sparse RNN training.
Figure illustrates high-level overview from an efficiency perspective of the difference between RNN and iterative pruning techniques (Han et al.) 2016) Zhu & Guptal 2017 Frankle &
Carbin 2019). The conventional pruning and re-training techniques usually involve three steps: (I) pre-traiing a dense model, (2) pruning unimportant weights, and (3) re-training the pruned model to improve performance. The pruning and re-training cycles can be iterated. This iteration is taking place at least once, but it may also take place several times depending on the specific algorithms used. Therefore, the sparse networks obtained via iterative pruning at least involve pre-training a dense model. Different from the aforementioned three-step techniques, FLOPs required by Selfish-RNN is proportional to the density of the model, as it allows us to train a sparse network with a fixed number of parameters throughout training in one single run, without any re- re-training phases. Moreover, the overhead caused by the adaptive sparse connectivity operation is negligible, as is operated only per epoch.
15

---

Under review as a conference paper at ICLR 2021
Begin
Pruning and retraining
Selfish-RNN
PTB Selfish-RNN vs Pruning with stacked LSTMs
105
Train a sparse network
Selfish-RND
FLOP, FLOP, FLOP
Pre-train
End
Test Perplexity
Pruning
95
RigL
Pruno
Retrain
90
Pruna
Retrain
85
FLOP, << FLOP,
<< FLOP N FLOP,
80
N
75
Prune
Rotrain
0.8
0.85
0.9
Sparsity
End
Figure 6: (left) A high-level overview of the difference between Selfish-RNN and the iterative pruning and re-training techniques. Blocks with light blue color represent optional pruning and retraining steps chosen based on specific approaches. (right) Comparison of the single model perplexity test sets Selfish-RNN, RigL and iterative magnitude pruning with stacked LSTMs on PTB.
COMPARISON BETWEEN SELFISH- AND PRUNING
has been shown by Evei et al. (020) that while state-of- tee-hhhrrrr art sparse training method (RigL) achieves promising performance in terms of CNNs, it fails to match the performance of pruning in RNNs. Given the fact that magnitude pruning has become a widely-used and strong baseline also report comparison between Selfish-RNN and iterative magnitude pruning with stacked LSTMs. The pruning baseline here is the Tensorflow Model Pruning library (Zhu Gupta. 2017). The results demonstrated in Figure rright.
for model compression,
We can see that SelfishRRNN exceeds the performance of pruning in most cases. An interesting phenomenon is that, with increased sparsity, we decreased performance gap between Selfish- RNN and pruning. Especially, Selfish-RNN performs worse than pruning when the sparsity level is 95%. This can be attributed to the poor trainability problem of sparse models with extreme sparsity levels. Noted in Lee et al.) (020)) the extreme sparse structure can break dynamical isometry (Saxe) al. 2014) of sparse networks, which degrades the trainability of sparse neural networks. Different from sparse training methods, pruning operates from a dense network and thus, does not have this problem.
J SPARSE TOPOLOGY DISTANCE MEASUREMENT
Our sparse topology distance measurement considers the unit alignment based semi-matching technique introduced by Li et al. (2016) and graph distance measurement based on graph edit distance (GED) (Sanfeliu Ful 1983). More specifically, our measurement includes the following steps:
Step 1: We train two sparse networks with dynamic sparse training on the training dataset and store the sparse topology after each epoch. Let Wi be the set of sparse topologies for the 1-th layer of network i.
Step 2:
Using the saved model, compute the activity output on the test data, Of gaxm where n is the number hidden units and m is the number of samples.
Step 3: We leverage the activity units of each layer to pair-wisely match topologies Wi. We achieve unit matching between pair of networks by finding the unit in one network with the maximum correlation to the one in the other network.
Step 4: After alignment, apply graph edit distance (GED) to measure the similarity between pairwise Wj. Eventually, the distance scaled to lie between 0 and 1. The smaller the distance is, the more similar the two sparse topologies are.
16

---

Under review as a conference paper at ICLR 2021
Here, We choose stacked LSTMs PTB dataset a specific to analyze. Specifically, train two stacked LSTMs for 100 epochs with different random seeds. We choose a relatively small removing rate of 0.1. We start alignment at the 5th epoch to ensure good alignment result, the very beginning of training networks do not learn very well. We then use the matched order of output tensors align the pairwise topologies Wi-
K TOPOLOGICAL DISTANCE OF GROWTH METHODS
In this section, empirically illustrate that gradient growth drives different networks into some sim- ilar connectivity patterns based on the proposed distance measurement between sparse connectivities. The initial removing rates set as 0.1 for all training runs in this section. First, measure the topological distance between two different training runs trained with gradient growth and random growth, respectively, shown in Figure We can see that, starting with very different sparse connectivity topologies, two networks trained with random growth end up at the same distance, whereas the topological distance between networks trained with gradient growth continuously decreasing and this tendency is likely to continue as the training goes on. We further report the distance between two networks with same initialization but different training seeds when trained with gradient growth and random growth, respectively. As shown in Figure [8] the distance between sparse networks discovered by gradient growth is smaller than the distance between sparse networks discovered by random growth. These observations are in line with our hypothesis that gradient growth drives networks into some similar structures, whereas random growth explores more sparse structures spanned over the dense networks.
0.8
0.8
Sparse topology GED
Sparse topology GED
0.6
0.6
Istm1 jh
Isim] jih
0.2
0.2
ssm1 hh
Istm1 hh
istm? jh
Istm2 jh
0.0
1stm2
0.0
Istm2
9 6 8
100
99,0
100
Epoch
Epoch [+)
Figure 7: (left) The topological distance between two different training runs of stacked LSTMs trained with random growth. (right) The topological distance between two different training runs of stacked LSTMs trained with gradient growth.
L FLOPs ANALYSIS OF DIFFERENT APPROACHES
We follow the way of calculating training FLOPs layer by layer based sparsity level s', proposed by Evci et al. (202)). We split the process of training a sparse recurrent neural network into two steps: forward pass and backward pass.
Forward pass In order to calculate the loss of the current models given a batch of input data, the output of each layer is needed be calculated based on linear transformation and non-linear activation function. Within each RNN layer, different cell weights are used to regulate information in sequence using the output of the previous time step and the input of this time step.
Backward pass In order to update weights, during the backward pass, each layer calculates 2 quantities: the gradient of the loss function with respect to the activations of the previous layer and the gradient of the loss function with respect to its weights. Therefore, the computational expense of backward pass is twice that of forward pass. Given that RNN models usually contain an embedding layer from which it is very efficient pick word vector, for models not using weight tying,
17

---

Under review as a conference paper at ICLR 2021
GED
Sparse topology GED
5par topoloog
0.4
0.4
ssmm
Istm ji
0.2
0.2
istml
1stm2 jh
ih
0.0
1stm2
6
100
1
100
Epoch
Epoch
Figure 8: (left) The topologiaal distance between two stacked LSTMs with same initialization but different training seeds trained with random growth. (right) The topological distance between two networks with same initialization but different training seeds trained with gradient growth. ih the input weight tensor comprising four cell weights and hh is the hidden state weight tensor comprising four cell weights.
Table Training FLOPSs analysis of different sparse training approaches. fn refers to the training FLOPs for dense model compute one single prediction in the forward pass and fs refers to the training FLOPs for a sparse model. 4T the number iterations used by RigL to update sparse connectivity. 8 is the sparsity level of the model at iteration
Method
Forward Pass
Backward Pass
Total
Dense
fD fD *
2fD
3fD
ISS
St
2fp 8
3fD 8t
Pruning
fD * fss fs
St.
2fD*
3fD St
SET
2fs
3fs
DSR
2fs
3fs
SNFS
fs
fs + fD
2fs +fD
RigL
fs
(2AT (2A++))fetD
A1sAT+2fs+fo
4T+1
4T+1
Selfish-RNN (ours)
fs
2/s
3fs
only count the computations calculate the gradient of its parameters as the training FLOPs and omit its inference FLOPs. For models using weight tying, both the training FLOPPs and the inference FLOPs are omitted.
Given a specific architecture, we denote fn as dense FLOPs required to finish one training iteration and fs the corresponding sparse FLOPS (ʃs ~ (1 (1-55)) S)) where S is the sparsity level. Thus fs < fD for very sparse networks. Since different sparse training methods cause different sparse distribution, their FLOPs fs are also different from each other. We omit the FLOPs used update the sparse connectivity, as it is only performed once per epoch. Overall, the total FLOPs required for one training update on one single sample are given in Table The training FLOPs of dense-to-sparse methods like, ISS and pruning, are 3fD 8t, where is the sparsity of the model at iteration t. Since dense-to-sparse methods require to train a dense model for a while, their training FLOPs and memory requirement are higher than our method. For methods that allow the sparsity of each layer dynamically changing e.g., DSR and SNFS, we approximate their training FLOPs via their final distribution. their sparse distribution converge to the final distribution in the first few epochs. ER distribution causes a bit more inference FLOPs than uniform distribution because is allocates more weights to the RNN layers than other layers. SNFS requires extra FLOPss calculate dense gradients during the backward pass. Although Rigl. also uses the dense gradients to assist weight growth, only needs calculate dense gradients every AT iterations, thus its averaged FLOPs is given by 4fs4f+ffstf Here, simply omit the extra FLOPs required by gradient-basse growth, is AT+1
negligible compared with the whole training FL.OPs.
18

---

Under review as a conference paper at ICLR 2021
For inference, calculate the inference FLOPs on single sample based the final sparse distribution learned by different methods.
M FINAL CELL WEIGHT SPARSITY BREAKDOWN
We further study the final sparsity level across cell weights learned automatically by our method. We find consistent observation that the weight of forget gates, either the forget gate in the standard LSTM or the master forget gate in ON-LSTMM, tend to be sparser than the weight of other gates, whereas the weight of cell gates and output gates denser than the average, shown in Figure However, there is no big difference between weights in RHN, although the / nonlinear transform weight slightly sparser than the T gate weight most RHN layers. This phenomenon is in line with the Ablation analysis where the cell weight redistribution does not provide performance improvement for RHNs. Cell weight redistribution is more important for models with more regulating weights.
N LIMITATION
The aforementioned training benefits have not been fully explored, as off-the-shelf software and hardware have limited support for sparse operations. The unstructured sparsity is difficult to be efficiently mapped to the existing parallel processors. The results of our paper provide motivation for new types of hardware accelerators and libraries with better support for sparse neural networks. Nevertheless, many recent works have been developed to accelerate sparse neural networks including Gray et al. (201)); Moradi et al. (20T)) Ma et al. (201)); Yang & Ma (2019); Liu al. (2020b). For instance, NVIDIA introduces the A GPU enabling the Fine-Gr Structured Sparsity (VVIDIA 2020). The sparse structure is enforced by allowing two nonzero values in every four-entry vector to reduce memory storage and bandwidth by almost 2x. We do not claim that Selfish-RNN is the best way obtain sparse recurrent neural networks, but simply highlights that is important future research direction to develop more efficient hardware and software to benefit from sparse neural networks.
19

---

Under review as a conference paper at ICLR 2021
Layer sparsity:
0.7
Gate spars
0.6
0.5
0.4
Ingate
Forgetgate
0.2
Cellgate
0.1
Outgate
In Layyrl
ih lalleyer
Ihh Jayer1
hth Jayar2
Stacked LSTM
Layer sparsity: 0.528
0.8
0.7
nanlinear transtorm
0.6
gate
0.5
0.4
0.3
0.2
0.1
W. depett
R depthi
R. depttt
R. Redeph33
R deptth
R depths
R depthé
R. depthh
R. depeth@
R. depttt
R. depth10
Layer sparsity: 0.55
0.8
Cate sparsity
0.5
0.4
Haster ingate
0.3
Porgeigate
0.2
forpebgate
ih layer?
in Jaaeer
hh leyer1
hhh layer2
hh. Jleyerr
ONLSTM
Layer sparsily: 0.55
0.7
Gate sparsity
0.4
Ingate
0.3
Forgetgate
0.2
Cellgatte
Outgate
th layer1
in Jayer2
in layer3
Ihh leyerl
bh layer
hhh laye??
Mo5
Figure 9: Breakdown of the final sparsity level of cell weights for stacked LSTMs, RHNs, ON-LSTM on PTB, RHNs; ih and hh refer to the input weight and the hidden weight in each layer, respectively for the rest models.
on Wikitext-2. W and R represent the weights tensors at each layer for
20


Reviews:
[{"review_id": "x4_uParF5zR", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe authors improve sparse for recurrent neural networks by developing a greedy redistribution rule for gates and adapting the ASGD optimizer for sparse networks. The work provides good results and a rich analysis of their and related methods.\n\nStrong points:\n- very rigorous experimental setup and analysis\n- Solid evidence for many new insights into some sparse training phenomena. The work provides broadens our understanding of sparse training.\n\nWeak points:\n- Some might complain that RNNs are outdated. I see this only as a minor weak point. Indeed, RNNs are not much used anymore, but many of the insights the paper provides are quite universal.\n- The fixed FLOPS only seems to be a by-product of the algorithm and particular network structure but not necessarily an algorithmic contribution. This makes the paper a bit confusing.\n\nRecommendation (short):\nThis is a very solid paper with exemplary experimentation and analysis. It provides many unique insights that are very valuable for anyone who wants to work in the field of sparse training. I recommend accepting this paper.\n\nRecommendation (long):\nI think this paper is one of these papers, which is a very solid all-around. The authors invested quite a bit of time in creating rigorous experimental setups that test hypotheses. In particular, I like the graph analysis of sparse connective between networks. Findings of different initialization schemes and performance of other sparse training methods are precious and make the overall literature on sparse training robust. I can see that this paper may seem a bit boring and less impactful to some reviewers, but good science like this is not about being exciting but about providing rigorous results for a small problem. This paper does exactly that. I think any good conference should encourage good science by accepting papers like this one.\n\nComments for authors:\nSolid work. Here some additional comments and questions.\n- Please feed your paper through a grammar/spellchecker. There are multiple errors which make the paper hard to read in some sections\n- It is not entirely clear why ASGD is needed for good performance. Can you elaborate, please?\n- Do you have any idea how does ER initialization relates to eigenvalues of recurrent matrices? If you can make a connection here, it would be a quite insightful addition to the paper since the top eigenvalue of the recurrent matrix determines the overall long-term behavior of the recurrent matrix and is known to influence behavior.\n- I would drop the fixed FLOPS contribution and focus on the other parts of the paper. You have more than enough contributions, and the space is better devoted to making the other contributions as clear as possible.\n- The cell weight redistribution algorithm description is unclear. A weight cannot have \"more parameters, I think you mean to say gate-neurons with large magnitude weights gain more parameters over time.\n- The sparse topology algorithm: Is the correlation between weights computed overall test set outputs between two networks/weights?\n- Figure 3, unclear. What does Figure 3 (left) show exactly? It is unclear what random initialization means: different sparsity patterns, different weight values, or both? What does the seed do here? Does it affect sparsity pattern, data order, weight values, etc.?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lhMqduuW5XY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In this paper, the authors propose an approach to train sparse recurrent models, and a sparse variant of the NT-ASGD. The proposed method mixes some interesting novel methodologies and achieves interesting empirical results on Penn Treebank and WikiText-2 language modeling tasks. \nIn general, the paper is well written and interesting, but in section 3 many explanations about the rationale behind some architectural choices of the selfish-RNN methodology are only partially explained, and sometimes they are just related to empirical results (e.g. in the cell weight redistribution). To me, a more theoretical explanation would significantly improve the manuscript readability.\nIn section 4 many different approaches were considered. But there are a few points that are not clear. The authors report the results of a “small\" dense network, but no information about this model is reported in the text.\nReading the results reported in table 5 of the appendix, I found it interesting that the performance of the DSR improves significantly by using SNT-ASGD instead of Adam  (it outperforms the Selfish-RNN). This table shows how much the optimizer influences model performance.  Even if the ablation study reported in appendix A highlights the benefits of the SNT-ASGD, the results reported in table 5 show that the impact of this component is even more important than the selfish-RNN. Honestly, I think that is fairer to compare all the methods using the same optimization algorithm, therefore my suggestion is to move this table in the main paper and extend the analysis of these results. \nReading the manuscript it is not clear how the hyper-parameters considered in the experimental campaigns have been chosen. By reading the first part of section 4.1 seems like parameters like the removing rate or the number of epochs are set without performing any validation on them. Even in appendix D, hyper-parameters (e.g. the learning rate, or the batch size) used to test the RHM are just listed. The authors should insert a more extensive explanation about how the hyper-parameters various models/approaches considered in the comparison have been validated. To perform a fair comparison the hyper-parameters of each model should be chosen according to its performance on the validation set.\nIn this regard, it is important also to highlight how the hyper-parameters are chosen because some SOTA models achieved better results. For instance on the Penn Treebank dataset in “On The State Of The Art Of Evaluation In Neural Language Models”, Melis et al. report perplexities on the test set of 59.7.\nexploiting better the research space. The reported results in the paper (and in Appendix L) show the benefits of using this approach, but honestly, to me, it is not clear if it helps in exploring the state space. In general, it is not clear what is the reason why the model benefits from using the random growth approach. Moreover, in “Sparse evolutionary deep learning with over one million artificial neurons on commodity hardware” the gradient guided growth strategy outperforms the other sparse training approaches considered in the paper, even in the RNN case. Therefore a more extended evaluation/discussion of this point is required.\nAnother recently proposed approach that uses sparsity in recurrent models is defined in “Intrinsically Sparse Long Short-Term Memory Networks” by Liu et al. the author should compare this approach with the selfish-LSTM.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-nMGFcluav", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "In this paper, the authors studied the possibility of sparsity exploration in Recurrent Neural Networks (RNNs) training. The main contributions include two parts: (1) Selfish-RNN training algorithm in Section 3.1 (2) SNT-ASGD optimizer in Section 3.2. The key idea of the Selfish-RNN training algorithm is a non-uniform redistribution across cell weights for better regularization. The authors mentioned previous sparse training techniques mainly focus on Multilayer Perceptron Networks (MLPs) and Convolutional Neural Networks (CNNs) rather than RNNs. This claim seems to be doubtful because one-time SVD + fine-tuning usually works very well for most RNN training applications in the industry.\n\nOverall, this paper is carefully written and provides some interesting empirical results. However, due to the lack of some important information, it is hard to evaluate the contribution of this paper.\n\nHere are some of my questions.\n\nSNT-ASGD needs to save the weights w_i,t from iteration Ti to iteration K, will that cost additional memory?\n\nThe authors mentioned that they picked Adam optimizer for SET, DSR, SNFS, and RigL. Is Adam the best optimizer to build a strong baseline? I suspect Adam may not be the best optimizer for each of them.\n\nThe authors need to give more information on the hyper-parameters like the learning rate. The selection of hyper-parameters usually significantly affects the convergence/generalization performance of an RNN model. For example, the way of learning rate decay has a big impact on the performance of training Penn TreeBank dataset.\n\nCan the authors report the training epochs and wall-clock time (e.g. in Table 2)? The sparsity typically makes modern hardware like GPUs perform poorly. That may be a concern. That’s the reason why researchers are studying structure sparsity. For future work, an analysis of computation (flops) to communication (memory access frequency) ratio seems to be necessary.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-hg1W59XWZ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "The paper claims that the previous sparse training methods mainly focus on MLP and CNN, and fail to perform very well in RNNs. Hence, the authors proposed an approach to train sparse RNNs with a fixed FLOPs budget.\nThe proposed technique is based on defining a mask matrix $M$ and refining it during training. It is initialized randomly to have the desired sparsity level $S$. After each training epoch, a fraction $p$ of the weights with the smallest magnitude is removed, i.e., those locations are zeroed in the mask M.\nNext, the same amount of parameters are randomly added to M again. \nMoreover, a variant of the averaged stochastic gradient optimizer (SNT-ASGD) is developed for the training of sparse RNN to account for the effect of weight masks during training.\nThey showed that in practice, the requirements for efficient sparse training of RNNs are different than CNN and MLP.\n\nStrengths:\nBy adding some refinements and tweaks to the existing techniques (masking for sparse training and adapting the NT-ASGD), the authors were able to achieve good performance to train sparse RNNs. The paper has a rather extensive set of simulations and experimental setups to analyze the best setup which yields good sparse training, e.g., comparing uniform vs ER distribution for masks, sensitivity to hyperparameters, ... Moreover, they have considered a fairly diverse set of RNN architectures to evaluate their method.\n\nWeaknesses and questions:\nCompared to the existing methods, the technical novelty of the paper is minor. It can be seen as some tweaks and improvements to the existing ones (although I admit that those changes are essential for the method to work for RNN.). \nWhat is special about the method that makes it specific to RNN? In other words, is it possible to use the same method for sparse training of MLP and CNN?\nA minor issue with the paper is the FLOPS analysis the authors used. Effectively, they use the sparsity of the parameters as a measure of FLOPS, not the actual FLOPS that might depend on the sparsity structure, HW, or software implementation. It would be a good idea to directly mention and use total sparsity, instead of FLOPS which can mislead the readers.\n\nSome parts of the method are not clear enough, e.g., \n1. In the paper, it is stated that \"magnitude weight removal\" is applied to non-RNN layers. Do the authors mean that for the parameters of RNN, this step is skipped?\n2. In \"cell weight redistribution\", it is suggested that the \"magnitude weight removal\" is applied to the whole set of RNN parameters $\\{\\theta_1, \\ldots, \\theta_t\\}$. However, in \"random weight growth\", it is mentioned that the same number of weights is grown immediately after weight removal, i.e., $R$ and $P$ have the same number of 1's. So, does it mean that the number of 1's in mask $M_i$ for each weight $\\theta_i$ ($1\\leq i \\leq t$) remains fixed S during training?\n3. Another aspect of training that is unclear for me is the parameters that are updated. Is $\\theta$ updated during training or only $\\theta_s$ is updated? As a result, if a weight is removed in one epoch and its value at the time of removal was $\\alpha$, and later regrown at another epoch, is its initial value set to 0 or started from its previous value before \"weight removal\", i.e. $\\alpha$?\n4. Did the authors add any regularizer (e.g., $\\ell_1$) to the training loss to improve sparsity in their experiments?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors introduce an approach to train sparse RNNs with a fixed parameter count. During training, they allow RNN layers to have a non-uniform redistribution across cell weights for a better regularization.They also introduce a variant of the averaged stochastic gradient optimizer, which improves the performance of all sparse training methods for RNNs. They achieve state-of-the-art sparse training results on Penn Treebank and Wikitext-2.

The method achieves very good performance on sparse RNNs for challenging tasks. The paper is well written and provides solid analysis with new insights into sparse network models. Most reviewers believe it is a very solid paper.

However, the technical novelty of the paper is limited. It can be seen as some tweaks and improvements of existing techniques, which seem to work very well. Since the number of papers that can be accepted is very limited, and since technical novelty is an essential criterion for published papers at ICLR, I propose rejection.


Decision: Reject