Pruning Randomly Initialized Neural Networks with Iterative Randomization
Authors: Daiki Chijiwa
Shin'ya Yamaguchi
Yasutoshi Ida
Kenji Umakoshi
Tomohiro INOUE
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: lottery ticket hypothesis
approximation theorem
neural network pruning

Abstract: Pruning the weights of randomly initialized neural networks plays an important role in the context of lottery ticket hypothesis. Ramanujan et al. (2020) empirically showed that only pruning the weights can achieve remarkable performance instead of optimizing the weight values. However, to achieve the same level of performance as the weight optimization, the pruning approach requires more parameters in the networks before pruning and thus more memory space. To overcome this parameter inefficiency, we introduce a novel framework to prune randomly initialized neural networks with iteratively randomizing weight values (IteRand). Theoretically, we prove an approximation theorem in our framework, which indicates that the randomizing operations are provably effective to reduce the required number of the parameters. We also empirically demonstrate the parameter efficiency in multiple experiments on CIFAR-10 and ImageNet.

Pruning Randomly Initialized Neural Networks with Iterative Randomization
Daiki Chijiwa
Shin'y 'a Yamaguchi"
Yasutoshi Ida*
Kenji Umakoshi
Tomohiro Inoue
NTT Computer and Data Science Laboratories, NTT Corporation NTT Social Informatics Laboratories, NTT Corporation
Abstract
Pruning the weights of randomly initialized neural networks plays an important role in the context of lottery ticket hypothesis. Ramanujan et al. [23] empirically showed that only pruning the weights can achieve remarkable performance instead optimizing the weight values. However, to achieve the same level of performance the weight optimization, the pruning approach requires more parameters in the networks before pruning and thus more memory space. To overcome this parameter inefficiency, introduce novel framework to prune randomly initialized neural networks with iteratively randomizing weight values (IteRand). Theoretically, we prove approximation theorem in framework, which indicates that the randomizing operations are provably effective to reduce the required number of the parameters. We also empirically demonstrate the parameter efficiency in multiple experiments on CIFAR-10 and ImageNet. The code available at https:/ htt//gitttt github. comm/chhijinnttiteeeeeeeeeeeeeee
Introduction
The lottery ticket hypothesis, which was originally proposed by Frankle and Carbin [5], has been an important topic in the research of deep neural networks (DNNs). The hypothesis claims that an werr-parameterized DNN has a sparse subnetwork (called winning ticket) that can achieve almost the same accuracy as the fully-trained entire network when trained independently. If the hypothesis holds for given network, then can reduce the computational cost by using the sparse subnetwork instead of the entire network while maintaining the accuracy [14, 19]. In addition to the practical benefit, the hypothesis also suggests that the over-pane paraaatraaattiiooonn of DNNs no longer necessary and their subnetworks alone are sufficient to achieve full accuracy.
step further. They proposed and empirically demonstrated a conjecture related to the above hypothesis, called the strong lottery ticket hypothesis, which informally states that there exists subnetwork in randomly initialized neural network such that already achieves almost the same accuracy as a fully trained network, without any optimization of the weights of the network. A remarkable consequence of this hypothesis is that neural networks could be trained by solving a discrete optimization problem. That is, we may train randomly initialized neural network by finding an optimal subnetwork (which we call weight-pruning optimization), instead of optimizing the network weights continuously (which we call (right-opptmizzatoo) with stochastic gradient descent (SGD).
Ramanujan al. [23]
However, the weight-pruning optimization requires a problematic amount of parameters in the random network before pruning. Pensia et al. [22] theoretically showed that the required network width for the weight-pruning optimization needs to be logarithmically wider than the weight-optimizzaioon at
CCoresponding author: daiki chi wwwhco. wtt.shh....ttt......o... nt...
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

least in the case of shallow networks. Therefore, the parameters, and thus more memory space, than the weight-optimizztion to achieve the same accuracy. In other words, under a given memory constraint, the weight-pruning optimization can have lower final accuracy than the weight-optimizztioon practice.
optimization requires more
In this paper, we propose a novel optimization method for neural networks called weight-pruning with iterative randomization (IteRand), which extends the weight-pruning optimization to overcome the parameter inefficiency. The key idea is to virtually increase the network width by randomizing pruned weights at each iteration of the prightgg optimization, without any additional memory consumption. Indeed, we theoretically show that the required network width can be reduced by the randomizing operations. More precisely, our theoretical result indicates that, if the number of randomizing operations is large enough, we can reduce the required network width for prruhigg to the same as that for network fully trained by the weight-optimization up to constant factors, in contrast to the logarithmic factors of the previous results [22, 21J. We also empirically demonstrate that, under given amount of network parameters, IteRand boosts the accuracy of the weight- optimization in multiple vision experiments.
2 Background
In this section, we review the prior works on pruning randomly initialized neural networks.
Notation and setup. Let d, N E N. Let (a; 0) be an I-layered ReLU neural network with an input x E IR and parameters 0 (0,) E R", where each weight 0, is randomly sampled from distribution D pparam over R. A subnetwork of fa;; 0) is written fa; 0 @ m) where E {0, 1)" is a binary mask and "@" represents an element-wise multiplication.
Ramanujan et al. [23] empirically observed that we can train the randomly initialized neural network f(: 0) by solving the following discrete optimization problem, which we call weight-pruning optimization:
min m (x.g)=Diabcled
[[f(2; m)
where Dlabeled is a distribution on a set of labeled data (æ,, y) and L is a loss function. To solve this optimization problem, Ramanujan et al. [23] proposed an optimization algorithm, called edge-popup (Algorithm 1).
Algorithm 1: Weight- prahnig optimization by edge-popup [23]
Initialize 0 ~ DD param:
D Di
// D param and Dacore are distributions over
while k ===00 O.... N do
3
Sample labeled data (æ, y) ~ Diabeled;
m, + TrainMask(O,, s; (x, v)); // optimize importance scores and update m
end
6
return m, A:
The TrainMask (Algorithm 2) is the key process in Algorithm 1. (s:)ssiz E R"," where each element s; represents an importance score of the corresponding weight 0, and optimizes s instead of directly optimizing the discrete variable m. Given the score s, the corresponding m is computed by the function Calculated (t) which returns m = (m.).sisn defined as follows: my = if s; is top 100(1 - p)% in {shisssm otherwise m, = 0, where p E (0, 1) is a hyperparameter representing a sparsity rate of the pruned network. In the line 3 of Algorithm 2, ,, (s, g) returns the updated value of s by stochastic gradient descent with learning rate 7), weight decay X, momentum coefficient (4, and gradient vector g.
It has a latent variable
On the theoretical side, Malach et al. [16] first provided mathematical justification of the above empirical observation. They formulated it as an approximation theorem with some assumptions on the network width as follows.
Theorem 2.1 (informal statement of Theorem 2.1 in [16]) Let Ftarget (x) be an I-layered network with bounded weight matrices, and g(x)) be randomly initialized 21-layered neural network. If the width of g(x) larger than Fearger (x)) by the factor of a polynomial term, then there probably exists subnetwork of g(x) that approximates frarget (z).
2

---

Algorithm 2: Pscudo code of TrainMask
Input: 0. E Ik" (Ir, y): laheled data;
// calculate the mask with the current scores s f y, (s. C(fe; ( 08), // update s by the gradient at 8 = m m <- CalculateMask(s);
m <- CalculateMask(s)
// calculate new mask with the updated scores
5 return m,
By considering a well-trained network as Starget. Theorem 2.1 indicates that pruning sufficiently wide g(z) may reveal a subnetwork which achieves good test accuracy as ftarget. in principle.
In the follow-up works [22, 21], the assumption on the network width was improved by reducing the factor of the required width logarithmic term. However, Pensia al. [22] showed that the logarithmic order is unavoidable at least in the case of I = 1. While their results imply the optimality of the logarithmic bound, it also means that we cannot further relax the assumption on the network width as long as we work in the same setting. This indicates a limitation of the pright-pruning optimization, i.e. the weight-pruning optimization can train only less expressive models than ones trained with the conventional weight-optimizzatio like SGD, under a given amount of memory or network parameters.
Method
In this section, present novel method called weight-pruning with iterative randomization (IteRand) for randomly initialized neural networks.
As discussed in Section 2, although the original weight-pruning optimization (Algorithm 1) can achieve good accuracy, still has limitation the expressive power under fixed amount of memory network parameters. Our method is designed to overcome this limitation. The main idea to randomize pruned weights each iteration of the weight-pruning optimization. As we prove in Section 4, this reduces the required size of an entire network to be pruned.
We use the same notation and setup as Section In addition, assume that each weight 0; of the network fir; 0) can be re-sampled from 2 param at each iteration of the weight- optimization.
3.1 Algorithm
Algorithm 3 describes our proposed method, IteRand, which extends Algorithm 1. The differences from Algorithm 1 are lines 5-7 in Algorithm 3. IteRand has hyperparameter K Kper E N> (line 5). At the k-th iteration, whenever l can be divided by K Kpers pruned weights are randomized by Randomi (e m) function (line 6). There are multiple possible designs for Randomize(0 m). which will be discussed in the next subsection.
Algorithm 3: Weight- pruning optimization with iterative randomization (IteRand)
Initialize 0 ~ SDrDDpp Param. S Dscore;
2 while 0. ... N do
Sample labeled data (xr, v) Diabeled
m, 4- TrainMask O,, s; (x. y));
if k + can be divided by K Kpee then // this if-block is newly added to Algorithm 1 // randomize a subset of pruned weights
<- Randomized (0, m);
end
end
return m, 0:
Note that Kpor controls how frequently the algorithm randomizes the pruned weights. Indeed the total number of the randomizing operations is W/KperJ. If Kper is too small, the algorithm is likely to be unstable because it may randomize even the important weights before their scores are well-optimized, and also the overhead of the randomizing operations cannot be ignored. In contrast,

---

if per is too large, the algorithm becomes almost same as the original weight-pruning Algorithm and thus the effect of the randomization disappears. We fix Ker 300 on CIFAR-10 (about 1 epoch) and K per 1000 on ImageNet (about 1/10 epochs) in our experiments (Section 5).
3.2 Designs of Randomize m)
Here, we discuss how to define Randomize((. m) function. There are several possible ways to randomize subset of the parameters 0.
Naive randomization. For any distribution D Paramm naive definition of the randomization func- tion (which we call naive randomization) can be given as follows.
0,, (if m; =
Randomize(O..o m):
8, (otherwise)
where we denote the i-th component of Randomize(P m) E IR" as Randomize m)j, and each 0, E IR is random variable with the distribution 2 param Also this can be written in another form as
Randomize m) 0 m (1 m),
where 0- =0+:)siisn 1n is random variable with the distribution D Paramm
Partial randomization. The naive randomization (Eq. (2)) is likely to be unstable because entirely replaces all pruned weights with random values every Kper iteration. To increase the stability, we modify the definition of the naive randomization as it replaces a randomly chosen subset of the pruned weights follows (which call partial randomization):
Randomize O m) == 0 o m + (0 (1 b,.) + ④ b, @
(1
m),
(3)
where O E R is the same in Eq. (2), r 0, is a hyperparameter and b, = (br,))sisn E {0, is a binary vector whose each element is sampled from the Bernoulli distribution Bernoullirr). i.e. b,, 1 with probability and b, with probability r.
Val Accs on CIFAR-10
The partial randomization replaces randomly chosen 100r% of all pruned weights with random values. Note that, when r = 1, the partial randomization is equivalent to the naive randomization (Eq. (2)). In contrast, when 0, never randomizes any weights and thus equivalent to Algorithm 1.
88
Conv6
ResNet18
ResNet34
0-0.0
r=0.01
r=0.1
1=1.0
Figure 1: Analysis on r. We com-
In Figure 1, we observe that r 0.1 works well with various network architectures on CIFAR-10, where we use Kaiming uniform distribution (whose definition will be given in Section 5) for D param and Kper 300.
pare partial randomizations with {0.0, 0.01, 0.1, 1.0) applied to CNNs. The y-axis is the validation accuracy on CUFAR-10. r 0.1 achieves better mean accuracy for every CNNs.
4 Theoretical justification
In this section, we present theoretical justification for our iterative randomization approach on the weight-pruning of randomly initialized neural networks.
4.1
Setup
We consider target neural network
RRdo Rd: of depth I, which described as follows.
fx) = ((
(4)
where æ is do-dimensional real vector, is the ReLU activation, and F; is de d matrix. Our objective is to approximate the target network fxx by pruning randomly initialized neural network g(z), which tends to be larger than the target network.

---

Similar to the previous works [16, 22], we assume that g(x) is twice as deep as the target network f(z). Thus, g(x) can be described as
g -
(5)
where Gj is a d, dj-1 matrix (j 1.... 2/) with d2: d, Each element of the matrix Gj is assumed to be drawn from the uniform distribution UI-1, 1.. Since there a one-to-one correspon- dence between pruned networks of (xx) and sequences of binary matrices M (=,))=,,.... ,2 with M, E 10,1,,,x0 xd; 1, every pruned network of g(z) can be described as
(x) (G2r @ M21 ( @ M2-1)o((--. (G, @ M))()...)))
(6)
Under these setups, we recall that the previous works showed that, with high probability, there exists a subnetwork of gz)) that approximates f f(x) when the width of g(x) is larger than f(x) by polynomial factors [16] or logarithmic factors [22, 21].
4.2 Formulation and main results
Now we attempt to mathematically formulate our proposed method, IteRand, as an approximation problem. As described in Algorithm the method consists of two steps: optimizing binary variables M = {M,]j=ı,.. 21 and randomizing pruned weights in g(z). The first step can be formulated as the approximation problem of f (z) by some gas (a:) as described above. Corresponding to the second step, we introduce an idealized assumption on g(x) for given number R E N>1: each element of the weight matrix Gj can be re- sampled with replacement from the uniform distribution UI-1, 1] up to R - 1 times, for all 1, 21. (re-sampling assumption for R)
Under this re-sampling assumption, we obtain the following theorem.
Theorem 4.1 (Main Theorem) Fix ō > O, and we assume that Fil| S 1. Let R E N, and assume that g(x)) satisfies the re-sampling assumption for R.
1ddh >) holds for all i = =1,".. , then with probability at least If dz 2 2d 64l2 d2 log( 3 {Mj} [Mjhisss2 such that
2²R²
1 6, there exist binary matrices M
[l - (x)]l2 S e, for || S 1.
In particular, if R is larger than 8id,-1 de log( 2id, then d2i-1 = 2d is enough.
Theorem 4.1 shows that the iterative randomization is provably helpful approximate wider networks in the weight-pruning optimization of a random network. In fact, the required width for g(r) in Theorem 4.1 is reduced to even twice as wide as fxx when the number of re-sampling sufficiently large, in contrast to the prior results without re-sampling assumption where the required width is logarithmically wider than f=) [22, 21J. This means that, under a fixed amount of parameters of g(ær), we can achieve a higher accuracy by weight-pruning of g(x) with iterative randomization since wider target network has a higher model capacity.
In the rest of this section we present the core ideas by proving the simplest case (1 do = d1 = 1) of the theorem, while the full proof of Theorem 4.1 is given in Appendix A. Note that the full proof obtained essentially by applying the argument for the simplest case inductively on the widths and depths.
4.3 Proof ideas for Theorem 4.1
Let us consider the case of do = di = 1. Then the target network fxx can be written as f(x) wxr R + I. where E R, and g(x) can be written as g(x) = v (uz) where u, E R Also, subnetworks of g(z) can be written as 9m(x) = (v@m)" ( m))z for some m E {0, 1j There are two technical points in our proof. The first point is the following splitting of f(r):
f(x) wa(x) (-xx),
(8)
for any x E R. This splitting is very similar to the one used in the previous works [16, 22, 21]:
f(x) (wx) - wz)).
(9)
5

---

However, if we use the latter splitting Eq. (9), it turns out that we cannot obtain the lower bound of d in Theorem 4.1 when do > 0. (Here we do not treat this case, but the proof for do > 0 is given in Appendix A.) Thus we need to use our splitting Eq. (8) instead.
Using Eq. (8), we can give another proof of the following approximation result without iterative randomization, which was already shown in the previous work [16].
Lemma 4.2 Fix e, E (0,1), w E [-1,1], N. Let u. ~ U[-1, 1 be uniformly random weights of 2 2-layered neural network g(x) v'o(u 2). If d 2 2 log( holds, then with probability at least 8,
w - 9m( S e, for all a E R. |o| <
(10)
where 9m (x) = (v O m) (u 2) for some m E [0,
Proof (sketch): We assume that d is an even number as d 2d' so that we can split an
index set (0..... d - I} of d hidden neurons of g(x) into I = {0, ... .....'''' d' 1} and J = (d' "dd....., 1}. Then we have the corresponding subnetworks gr(x)) and g g)(x)) given by gr(x) = Eker Uno (ugx). ( (x) Σker U.. which satisfy the equation g(x) = gr(x) + gr(().
By the splitting Eq. (8), it is enough to consider the probabilities for approximating wo by a subnetwork of gr (x) and for approximating - (wo-=)) by subnetwork of g) Now we have
d'
TP ( Ai E 7 s.t. | - 1| &
c m - w| S c 1
8
S
(11)
2'
2
16
2
d'
P (Aj lug + 11 S 6 2 M0 + w|
S 6 2
(12)
16
2
for d' 2 22 log (2)) by standard argument of the uniform distribution and the inequality e 2 1+
for x 2 0. By the union bound, with probability at least 1 5, we have E I and such that
(x) v.o S
1-wa(- (-x) uyo (u;zo) S 2
Combining these inequalities, we finish the proof.
The second point of our proof is introducing projection maps leverage the re-sampling assumption, as follows. As in the proof of Lemma 4.2, we assume that d 2d' for some d' E N and let
I= (0, ......... 1), {d' d 1). Now we define projection map
T + [k/R],
(13)
where 7 = (0, ... d'R 1}. and denotes the floor function. Similarly for J, we can define J: (d' dR 12-1] 1} and the corresponding projection map. Using these projection maps, we can extend Lemma 4.2 to the one with the re-sampling assumption, which is the special case of Theorem 4.1:
Proposition 4.3 (Theorem 4.1 with 1 do d1 = Fix e, (0, 1), E [-1,1], N. Let u, ~ U[11, 1]d be uniformly random weights of a 2-layered neural network g(z) := vT ol z). Let R. E N and we assume that each element of u and v can be re-sam re-sampled with replacement up to R - times. If d > 2[ ア log(
( holds, then with probability at least 1 - 8.
wr - [m(()] S for all æ E R. 1
(14)
where 9m (m)()) = (v c m) (u x)) for some m E 10.
Proof (sketch): Similarly to the proof of Lemma 4.2, we utilize the splitting Eq. (8). We mainly argue on the approximation of wo(x) since the argument for approximating (w) is parallel.

---

By the assumption that each element of u and v can be re-sampled up to R - times, we can replace the probability in Eq. (11) in the proof of Lemma 4.2, using the projection map x : 1, by
é s.t. ((i) - (12), [ūا - 1 S 2 Ti2- - w| - E 2 P (i is E s.t.
(15)
2
where U1,' Ue -1. oon ~ U[- Indeed. since we have
#1 i2) E [ x I (i1) x = d
(16)
we can evaluate the probability Eq. (15) as
2 d'R²
5
Eq. (15) <
(17)
16
2'
for d'
2k log (1) Eq. (17) can play the same role as Eq. (11) in the proof of Lemma 4.2.
Parallel argument can be applied for the approximation of -wwr((x) by replacing / with J. The rest of the proof the same as Lemma 4.2.
5 Experiments
In this section, we perform several experiments to evaluate our proposed method, IteRand (Algo- rithm 3). Our main aim is to empirically verify the parameter efficiency of IteRand, compared with edge-popup [23] (Algorithm 1) on which IteRand is based. Specifically, we demonstrate that IteRand can achieve better accuracy than edge-popup under given amount of network parameters. In all experiments, we used the partial randomization with 0.1 (Eq. (3)) for Randomize in Algorithm 3.
Setup. We used two vision datasets: CIFAR-10 [12] and ImageNet [25]. CIFAR- 10 is a scall-scale dataset of 32 32 images with 10 class labels. It has 50k images for training and 10k for testing. We randomly split the 50k training images into 45k for actual training and 5k for validation. ImageNet is a dataset of 224 x 224 images with 1000 class labels. It has the train set of 1.28 million images and the validation set of 50k images. We randomly split the training images into 99 : 1, and used the former for actual training and the latter for validating models. When testing models, we used the validation set of ImageNet (which we refer to as the test set). For network architectures, we used multiple convolutional neural networks (CNNs): Conv6 [5] shallow network and ResNets [10] as deep networks. Conv6 is a 6-layered VGG-like CNN, which is also used in the prior work [23]. ResNets are more practical CNNs with skip connections and batch normalization layers. Following the settings in Ramanujan et al. [23], we used non-affine batch normalization layers, which are layers that only normalize their inputs and do not apply any affine transform, when training ResNets with edge-popup and IteRand. All of our experiments were performed with GPU (NVIDIA GTX 1080 Ti, 1 1GB) for CIFAR-10 and 2 GPUs (NVIDIA v V100, 16GB) for ImageNet. The details of the network architectures and hyperparameters for training are given in Appendix B.
Parameter distributions. With the same notation Section 2, both IteRand and edge-popup requires two distributions: Dparam and Ducore. In our experiments, we consider Kaiming uniform (KU) and signed Kaiming constant (SC) distribution. The KU distribution is the uniform distribution
over the interval |- Ctanin
where Clanin is the constant defined for each layer of ReLU neural networks [1][9]. The SC distribution is the uniform distribution over the wao-valued set
6
6
Cfanin
2 which is introduced by Ramanujan al. [23]. We fix Dscore to the KU
Cranin
Cramin
distribution, and use the KU or SC distribution for D Dparam-
5.1 Varying the network width
To demonstrate the parameter efficiency, we introduce hyperparameter of the width factor for Conv6, ResNet18 and ResNet34. The details of this modification are given in Appendix B. We train and test these networks on -0 using IteRand, edge-popup and SGD, varying the width factor p in (0.25, 0.5, 1.0, 2.0) for each network (Figure 2). In the experiments for IteRand and edge-popup, we used the sparsity rate of p 0.5 for Conv6 and p = 0.6 for ResNer18 8 and ResNet34. Our method outperforms the baseline method for various widths. The difference in accuracy large both when the width is small (p < 0.5), and when D param is the KU distribution where adge-popup struggles.
7

---

Conv6
ResNet18
ResNet34
95.0
94
92
90.0
75
85.0
88
70
86
65
0.25
0.50
1.00
2.00
0.25
0.50
1.00
2.00
0.25
0.50
1.00
2.00
ItcRand (SC)
IteRand (KU)
popup (SC)
popup (KU)
SGD
Figure 2: We train and evaluate three CNNs (Conv6, ResNet18 and ResNet34) with various widths on CIFAR-10. The x-axis is the width factor & and the y-axis is the aceuracy the test set. We plot the mean + standard deviation over three runs for each experiment. KU/SC in the legend represents the distribution used for D param.
ImageNet
ResNet50
74
Train Accuracy
60
ResNett01
ResNet34
Nasterto
1op-1 Test Accuracy
RessNetbe
ResNer18
20
IteRand (SC)
edge-popup (SC)
60
20
100
ResNer50
Vel. Accuracy
ResNe34
IteRand (SC)
40
IteRand (SC)
papup (SC)
ResNe:34
SGD
20
edge-popup (SC)
67
10
12
14
20
0
20
40
60
60
100
* Parameters (14
Epochs
(a) Network Size Test Accuracy.
(b) Training Curves.
Figure 3: We compare IteRand with edge-pope popup on ImageNet. We used fixed = 0.7 for the sparsity rate (Section 2) following Ramanujan al. [23]. Figure (a) shows parameter-accurage tradeoff curves on the test set. In Figure (b), we plot the train/val accuracy of ResNet50 during optimization. IteRand outperforms edge-popup from early epochs.
5.2 ImageNet experiments
The parameter efficiency of our method is also confirmed on ImageNet (Figure 3a). ImageNet is more diffieult than CIFAR-10, 10, and thus more complexity required for networks achieve competitive performance. Since our method can increase the network complexity as shown in Section 4, the effect significant in ImageNet especially when the complexity is limited such as ResNet34.
In addition to the parameter efficiency, we also observe the effect of iterative randomization on the behavior of optimization process, by plotting training curves (Figure 3b). Surprisingly, IteRand achieves significantly better performance than edge-popup at the early stage of the optimization, which indicates that the iterative randomization accelerates the optimization process especially when the number of iterations is limited.
Related work
Lottery ticket hypothesis Frankle and Carbin [5] originally proposed the lottery ticket hypothesis. Many properties and applications have been studied in subsequent works, such transferability of winning subnetworks [19], sparsification before training [14, 27, 26] and further ablation studies on the hypothesis [29].
Zhou al [29] surprisingly showed that only pruning randomly initialized networks without any optimization their weights can be training method surprisingly. Ramanujan et al. [23] went

---

further by proposing an effective pruning algorithm on random networks, called edge-popin wolge--ppppp...m and achieved competitive accuracy compared with standard training algorithms by veight-optimization [24]. Malach et al. [16] mathematically formalized their pruning-only approach as approximation problem for a target network and proved it with lower bound condition on the width of random networks to be pruned. Subsequent works [22, 21] successfully relaxed the lower bound to the logarithmic factor wider than the width of a target network. Our work can be seen as an extension of their works to allow re-sampling of the weights of the random networks for finite It times, and we showed that the logarithmic factor can be reduced to a constant one when R is large enough. (See Section 4.)
Neural network pruning and regrowth Studies of finding sparse structures of neural networks date back to the late 1980s [8, 13]. There are many approaches to sparsify networks, such as magnitude-basee pruning [7]. Lo regularization [15] and variational dropout [18]. Although these methods only focus on pruning unnecessary weights from the networks, there are several studies on re-adding new weights during sparsification [11] to maintain the model complexity of the sparse networks. Han et al. [6] proposed
caanse-spase--eeee (DSD) training algorithm consisting of three stages: dense training, pruning, and recovering the pruned weights as zeros followed by dense training. Mocanu et al. [17] proposed sparse evolutionary training (SET), which repeats pruning and regrowth with random values at the end of each training epoch. Pruning algorithms proposed in other works [2, 20, 4] are designed recover pruned weights by gero-initialization instead of random values, so that the recovered weights do not affect the outputs of the networks. While these methods are similar to our iterative randomization method in terms of the re-adding processes, all of them use weight-optimization to train networks including re-added weights, in contrast to our pruning-only approach.
7 Limitations
There are several limitations in our theoretical results. (1) Theorem 4.1 indicates only the existence of subnetworks that approximate a given neural network, not whether our method works well empirically. (2) The theorem focused on the case when the parameter distribution D paramm is the uniform distribution over the interval [-1, 1]. Thus, generalizing our theorem other distributions, such as the uniform distribution over binary values 1 [3], is left for future work. (3) The required width given in the theorem may not be optimal. Indeed, prior work [22] showed that we can reduce the polynomial factors in the required width to logarithmic ones in the case when the number of re-sampling operations R = Whether we can reduce the required width for open question.
remains an
Also our algorithm (IteRand) and its empirical results have several limitations. (1) Pruning randomly- initialized networks without any randomization can reduce the storage cost by saving only a single random seed and the binary mask representing the optimal subnetwork. However, if we save the network pruned with IteRand in the same way, it requires more storage cost: R random seeds and R binary masks, where R is the number of re-samplings. (2) Although our method can be applied with any score-based pruning algorithms (e.g. Zhou et al [29] and Wang et al [28]), we evaluated our method only combined with edge-popup [23], which the state-of-the-arr algorithm for pruning random networks. Since our theoretical results do not depend on any pruning algorithms, we expect that our method can be effectively combined with better pruning algorithms that emerge in the future. (3) We performed experiments mainly on the tasks of image classification. An intriguing question is how effectively our method works on other tasks such as language understanding, audio recognition, and deep reinforcement learning with various network architectures.
8 Conclusion
In this paper, we proposed a novel framework of iterative randomization (IteRand) for pruning randomly initialized neural networks. IteRand can virtually increase the network widths without any additional memory consumption, by randomizing pruned weights of the networks iteratively during the pruning procedure. We verified its parameter efficiency both theoretically and empirically.
Our results indicate that the weight-pruning of random networks may become a practical approach to train the networks when we apply the randomizing operations enough times. This opens up the

---

possibility that the weight-pruningg can be used instead of the standard weight-optimizztion within the same memory budget.
Acknowledgement
The authors thank Kyosuke Nishida and Hengjin Tang for valuable discussions in the early phase of our study. We also thank Osamu Saisho for helpful comments on the manuscript. We appreciate CCI team in NTT for building and maintaining their computational cluster on which most of our experiments were computed.
References
[1] torch.nn.init PyTorch 1.8.1 documentation. init, html. Accessed: 2021-10-21.
[2] Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. International Conference on Learning Representations, 2018.
[3] James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning a randomly weighted network. In International Conference Learning Representations, 2021.
[4] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pages 2943 2952.. PMLR, 2020.
[5] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
[6] Song Han, Jeff Pool, Sharan Narang. Huizi Mao, Enhao Gong, Shijian Tang, Erich Elsen, Peter Vajda, Manohar Paluri, John Tran, al. Dsd: Dense-sparse-dense training for deep neural networks. International Conference on Learning Representations, 2017.
[7] Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights and connections for efficient neural networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume Volume 1, pages 1135-1433, 2015.
[8] Stephen Hanson and Lorien Pratt. Comparing biases for minimal network construction with back-propagation. Advances in Neural Information Processing Systems, 1:177-185, 1988.
[9] Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision (ICCV), pages 1026-1034. IEEE Computer Society, 2015.
[10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778. IEEE Computer Society, 2016.
[11] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. arXiv preprint arXiv:2102.0055. 2021.
[12] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[13] Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, pages 598-605, 1990.
[14] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2018.
10

---

[15]
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1 10 regularization. In International Conference on Learning Representations, 2018.
[16] Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning. pages 6682-6699 6691. PMLR, 2020.
[17] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibeseu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1-1,, 2018.
[18] Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In International Conference on Machine Learning, pages 2498-2507. PMLR, 2017.
[19] Ari Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[20] Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference Machine Learning, pages 4646-4655 PMLR, 2019.
[21] Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2925-2934, Curran Associates, Inc., 2020.
[22] Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic wer-parameterization is sufficient. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2599-2610. Curran Associates, Inc., 2020.
[23] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in randomly weighted neural network? In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1 11890-11899, IEEE Computer Society, 2020.
[24] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back propagarpgg errors. Nature, 323(6088):533-523) 1986.
[25] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg. and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (UCV), 1 115(3):211-25 1-252, 2015.
[26] Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In H. Larochelle, M. Ranzato, R. Had- sell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6377-6389. Curran Associates, Inc., 2020.
[27] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
[28] Yulong Wang, Xiaolu Zhang, Lingxi Xie, Jun Zhou, Hang Su, Bo Zhang, and Xiaolin Hu. Prun- ing from scratch. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 12273-12288 2020.
[29] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.


Reviews:
[{"review_id": "u-dSyzeh8Mv", "reviewer": "Reviewer_HPM9", "summary": "This paper proposes a memory-efficient approach for \\textit{weight-pruning optimization}, which suffers from a much larger memory cost than standard \\textit{weight optimization}. \n\nThe proposed approach, weight-pruning with iterative randomization (IteRand), decreases the required network width by introducing pruned weights randomization at each iteration. The author theoretically shows that, with sufficient randomizing operations, the width can be reduced to constant factors of that of a standard network trained by weight-optimization. \n\nThe empirical experiments demonstrate IteRand achieves better performance than existing weight-pruning optimization methods under the same memory budget. ", "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": "**Reason to accept**\n- The paper is well-organized and finely written.\n- The limitations of the existing works are thoroughly discussed and the paper is clearly motivated.\n- The authors both theoretically prove and empirically verify that IteRand can effectively reduce memory consumption and increase the complexity of the network.\n\n**Reason to reject & Questions**\n- Section 5.1&5.2: The gain of IteRand seems to decreases as the network size scales up (ResNet34 > ResNet50 > ResNet101 in Figure 3(a), and the same phenomenon in Figure 2.). I wonder how IteRand performs in settings where the memory constraint is an actual consideration (e.g., when training a model with hundreds of million parameters). \n- How much is the additional computational cost of IteRand over edge-popup? \n- I wonder if the authors can show some empirical results on 1) given the same size of $f(x)$, what is the width required for $g(x)$ for IteRand and for EdgePop to achieve the same performance? This may help understand the percentage of memory that is actually saved. 2) the performance under different $p$s to verify the consistency of the improvement.\n\nDisclaimer: I am not an expert in theoretical proofs. All my evaluation assumes the correctness of Theorem 4.1 and is subject to change if the proof turns out to be erroneous.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2h"}, "extra_text": {}}, {"review_id": "tZ6UIK3iUVx", "reviewer": "Reviewer_GSGE", "summary": "This paper proposes utilizing the existing \"lottery ticket\" result with the re-initialization method. This work has some novelty since doing re-initialization is not studied in other papers.\n\n", "questions": "", "limitations": "", "rating": 6, "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": "Questions: (1) The performance is actually no better than the previous method, for eg. ResNet18 on Cifar10 as compared to https://openreview.net/pdf?id=U_mat0b9iv. As a result, the performance gain by IteRand as compared to edge-popup is not clear. (2) For Theorem 4.1, the value of R is chosen unrealistically. Even for l=10, d=1000, R needs to be at least 10k/\\epsilon. (3) The technical difficulty is not clear to me as compared to previous proofs. This should be emphasized. (4) What happens if the method is applied to NLP problems?\n\n-----------------------After rebuttal----------------------------\nThe authors resolved my concern so that I increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}, {"review_id": "rJlSL3ReYux", "reviewer": "Reviewer_x4sx", "summary": "The paper proposes a new technique to reduce the network width required for pruning based algorithms. In particular, instead of starting from a wider network and then pruning weights to train the network, the paper proposes that pruned neurons can be resampled with random weights. Hence, instead of having extra weights in the form of extra width from the beginning, the new technique brings in new weights every time some of the existing weights are pruned. The motivation behind this is to reduce the memory footprint of the network before the pruning. \n\nThe idea and the empirical results are good, however, the theoretical result could be improved significantly.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The new idea that pruned weights can be resampled seems very intuitive and effective. The empirical results suggest that this indeed outperforms existing pruning techniques. However, the authors should provide more empirical evidence like actual training time, comparison with state-of-the-art (SGD+pruning) techniques like the lottery ticket hypothesis, and the actual number of times weights were resampled.\n\nThe theoretical result does not provide a strong support for the technique. In particular, even though the result is purely existential, the requirement on the number of re-samplings, $R$, is huge. It is proportional to the network depth and width. This seems to suggest that the procedure might not be efficient (in terms of computational time) for training large networks, since each resampling would need at least one complete iteration. \n\nThe paper is well written and easy to understand.\n\nOverall, the proposed technique is novel and can improve the state-of-the-art in pruning techniques.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Please compare your results with techniques that use both SGD and pruning iteratively. Even though (SGD+pruning) might outperform purely pruning based techniques, like the one proposed in this paper, it is still a necessary evaluation that should be included in the paper.\n2. Please provide the comparisons for the actual training time (in seconds) for different techniques.\n3. Please provide details on the number of re-samplings that happened during the training.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "8UhlMNB2S1p", "reviewer": "Reviewer_5mau", "summary": "This work proposes an improved method to find a performative subnetwork within a randomly weighted neural network. In contrast to prior work, a fraction of unused weights are periodically reset. This is a novel idea with empirical improvements and theoretical justification.", "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": "Overall the paper is clear to follow and enjoyable to read. The method is interesting, well motivated, and there are empirical gains. A few suggestions which could improve quality:\n\n1) Additional empirical results would strengthen the paper's message. For instance, this work is introducing two new hyperparameters (r and K_per), though there is only an ablation on one of these parameters. How did the authors choose K_per? Moreover, edge-popup could be added to Figure 3 -- it does seem as though this work performs better.\n\n2) There are a couple points where clarity in limitations could be improved. For instance, is IteRand just has an SC initialization but is no longer SC by the end of training. This is a shortcoming as weights can no longer be encoded with in binary. Moreover, with edge-popup or Zhou et al., a single random seed can be stored which generates all the weights, it seems this is no longer the case with IteRand.\n\nMinor comments:\n- Line 32-33 I believe Pensia et al. show that their theoretical result holds with log overaparam and not that this is required emperically.\n\n-- Added --\n\nI acknowledge the response and have raised my score to 7", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors adequately addressed the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new algorithm for learning by pruning. In the original work by Ramanujan et al. the random weights of a network could be pruned away so that the resulting network could achieve arbitrary accuracy for a given task, at the cost of slight overparameterization. The authors in the current paper show that the performance of such learning by pruning schemes can be improved by further rerandomizing the weights at consequent pruning iterations. This results in a reduced overaparemeterization to achieve the same accuracy compared to past results. The results are novel, and interesting with regards to the related literature. The reviewers have posted several points that the work can be improved, and all are addressed/can be addressed by the final version of the paper. 
Decision: Accept (Spotlight)