Pruning Randomly Initialized Neural Networks with Iterative Randomization
Year: 2021

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 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. The code is available at https://github.com/dchiji-ntt/iterand.

heading: 1 Introduction
text: 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 over-parameterized DNN has a sparse subnetwork (called a winning ticket) that can achieve almost the same accuracy as the fully-trained entire network when trained independently. If the hypothesis holds for a given network, then we 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-parametrization of DNNs is no longer necessary and their subnetworks alone are sufficient to achieve full accuracy.
Ramanujan et al. [23] went one 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 a subnetwork in a randomly initialized neural network such that it 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 a 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 weight-optimization) with stochastic gradient descent (SGD).
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-optimization at
∗Corresponding author: daiki.chijiwa.mk@hco.ntt.co.jp
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
least in the case of shallow networks. Therefore, the weight-pruning optimization requires more parameters, and thus more memory space, than the weight-optimization 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-optimization in practice.
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 weight-pruning 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 weight-pruning to the same as that for a network fully trained by the weight-optimization up to constant factors, in contrast to the logarithmic factors of the previous results [22, 21]. We also empirically demonstrate that, under a given amount of network parameters, IteRand boosts the accuracy of the weight-pruning optimization in multiple vision experiments.

heading: 2 Background
text: In this section, we review the prior works on pruning randomly initialized neural networks.
Notation and setup. Let d,N ∈ N. Let f(x;θ) be an l-layered ReLU neural network with an input x ∈ Rd and parameters θ = (θi)1≤i≤n ∈ Rn, where each weight θi is randomly sampled from a distributionDparam over R. A subnetwork of f(x;θ) is written as f(x;θ m) where m ∈ {0, 1}n 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(x;θ) by solving the following discrete optimization problem, which we call weight-pruning optimization:
min m∈{0,1}n E (x,y)∼Dlabeled
[ L(f(x;θ m), y) ] , (1)
where Dlabeled is a distribution on a set of labeled data (x, 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-pruning optimization by edge-popup [23] 1 Initialize θ ∼ Dnparam, s ∼ Dnscore; // Dparam and Dscore are distributions over R 2 while k = 0, · · · , N − 1 do 3 Sample a labeled data (x, y) ∼ Dlabeled; 4 m, s← TrainMask(θ, s; (x, y)); // optimize importance scores s and update m 5 end 6 return m,θ;
The TrainMask (Algorithm 2) is the key process in Algorithm 1. It has a latent variable s = (si)1≤i≤n ∈ Rn, where each element si represents an importance score of the corresponding weight θi, and optimizes s instead of directly optimizing the discrete variable m. Given the score s, the corresponding m is computed by the function CalculateMask(s), which returns m = (mi)1≤i≤n defined as follows: mi = 1 if si is top 100(1 − p)% in {si}1≤i≤n, otherwise mi = 0, where p ∈ (0, 1) is a hyperparameter representing a sparsity rate of the pruned network. In the line 3 of Algorithm 2, SGDη,λ,µ(s,g) returns the updated value of s by stochastic gradient descent with a learning rate η, weight decay λ, momentum coefficient µ, and gradient vector g. On the theoretical side, Malach et al. [16] first provided a 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 l-layered network with bounded weight matrices, and g(x) be a randomly initialized 2l-layered neural network. If the width of g(x) is larger than ftarget(x) by the factor of a polynomial term, then there probably exists a subnetwork of g(x) that approximates ftarget(x).
Algorithm 2: Pseudo code of TrainMask 1 Input: θ, s ∈ Rn, (x, y): a labeled data; 2 m← CalculateMask(s); // calculate the mask m with the current scores 3 s← SGDη,λ,µ (s,∇s=mL(f(x;θ s), y)); // update s by the gradient at s = m 4 m← CalculateMask(s); // calculate new mask m with the updated scores 5 return m, s;
By considering a well-trained network as ftarget, Theorem 2.1 indicates that pruning a sufficiently wide g(x) 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 to a logarithmic term. However, Pensia et al. [22] showed that the logarithmic order is unavoidable at least in the case of l = 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 weight-pruning optimization, i.e. the weight-pruning optimization can train only less expressive models than ones trained with the conventional weight-optimization like SGD, under a given amount of memory or network parameters.

heading: 3 Method
text: In this section, we present a 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, it still has a limitation in the expressive power under a fixed amount of memory or network parameters. Our method is designed to overcome this limitation. The main idea is to randomize pruned weights at 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 2. In addition, we assume that each weight θi of the network f(x;θ) can be re-sampled from Dparam at each iteration of the weight-pruning optimization.

heading: 3.1 Algorithm
text: 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 a hyperparameter Kper ∈ N≥1 (line 5). At the k-th iteration, whenever k can be divided by Kper, pruned weights are randomized by Randomize(θ,m) function (line 6). There are multiple possible designs for Randomize(θ,m), which will be discussed in the next subsection.
Algorithm 3: Weight-pruning optimization with iterative randomization (IteRand) 1 Initialize θ ∼ Dparam, s ∼ Dscore; 2 while k = 0, · · · , N − 1 do 3 Sample a labeled data (x, y) ∼ Dlabeled; 4 m, s← TrainMask(θ, s; (x, y)); 5 if k + 1 can be divided by Kper then // this if-block is newly added to Algorithm 1 6 θ ← Randomize(θ,m); // randomize a subset of pruned weights 7 end 8 end 9 return m, θ;
Note that Kper controls how frequently the algorithm randomizes the pruned weights. Indeed the total number of the randomizing operations is bN/Kperc. 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 Kper is too large, the algorithm becomes almost same as the original weight-pruning Algorithm 1, and thus the effect of the randomization disappears. We fix Kper = 300 on CIFAR-10 (about 1 epoch) and Kper = 1000 on ImageNet (about 1/10 epochs) in our experiments (Section 5).

heading: 3.2 Designs of Randomize(θ,m)
text: Here, we discuss how to define Randomize(θ,m) function. There are several possible ways to randomize a subset of the parameters θ.
Naive randomization. For any distribution Dparam, a naive definition of the randomization function (which we call naive randomization) can be given as follows.
Randomize(θ,m)i := { θi, (if mi = 1) θ̃i, (otherwise)
where we denote the i-th component of Randomize(θ,m) ∈ Rn as Randomize(θ,m)i, and each θ̃i ∈ R is a random variable with the distribution Dparam. Also this can be written in another form as
Randomize(θ,m) := θ m+ θ̃ (1−m), (2)
where θ̃ = (θ̃i)1≤i≤n ∈ Rn is a random variable with the distribution Dnparam.
Partial randomization. The naive randomization (Eq. (2)) is likely to be unstable because it 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 as follows (which we call partial randomization):
Randomize(θ,m) := θ m+ ( θ (1− br) + θ̃ br ) (1−m), (3)
where θ̃ ∈ Rn is the same as in Eq. (2), r ∈ [0, 1] is a hyperparameter and br = (br,i)1≤i≤n ∈ {0, 1}n is a binary vector whose each element is sampled from the Bernoulli distribution Bernoulli(r), i.e. br,i = 1 with probability r and br,i = 0 with probability 1− r. 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 r = 0, it never randomizes any weights and thus is equivalent to Algorithm 1.
In Figure 1, we observe that r = 0.1 works well with various network architectures on CIFAR-10, where we use the Kaiming uniform distribution (whose definition will be given in Section 5) for Dparam and Kper = 300.

heading: 4 Theoretical justification
text: In this section, we present a theoretical justification for our iterative randomization approach on the weight-pruning of randomly initialized neural networks.

heading: 4.1 Setup
text: We consider a target neural network f : Rd0 → Rdl of depth l, which is described as follows. f(x) = Flσ(Fl−1σ(· · ·F1(x) · · · )), (4)
where x is a d0-dimensional real vector, σ is the ReLU activation, and Fi is a di × di−1 matrix. Our objective is to approximate the target network f(x) by pruning a randomly initialized neural network g(x), 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(x). Thus, g(x) can be described as
g(x) = G2lσ(G2l−1σ(· · ·G1(x) · · · )), (5)
where Gj is a d̃j × d̃j−1 matrix (j = 1, · · · , 2l) with d̃2i = di. Each element of the matrix Gj is assumed to be drawn from the uniform distribution U [−1, 1]. Since there is a one-to-one correspondence between pruned networks of g(x) and sequences of binary matrices M = {Mj}j=1,··· ,2l with Mj ∈ {0, 1}d̃j×d̃j−1 , every pruned network of g(x) can be described as
gM (x) = (G2l M2l)σ((G2l−1 M2l−1)σ(· · · (G1 M1)(x) · · · )). (6) Under these setups, we recall that the previous works showed that, with high probability, there exists a subnetwork of g(x) that approximates f(x) when the width of g(x) is larger than f(x) by polynomial factors [16] or logarithmic factors [22, 21].

heading: 4.2 Formulation and main results
text: Now we attempt to mathematically formulate our proposed method, IteRand, as an approximation problem. As described in Algorithm 3, the method consists of two steps: optimizing binary variables M = {Mj}j=1,··· ,2l and randomizing pruned weights in g(x). The first step can be formulated as the approximation problem of f(x) by some gM (x) as described above. Corresponding to the second step, we introduce an idealized assumption on g(x) for a given number R ∈ N≥1: each element of the weight matrix Gj can be re-sampled with replacement from the uniform distribution U [−1, 1] up to R− 1 times, for all j = 1, · · · , 2l. (re-sampling assumption for R) Under this re-sampling assumption, we obtain the following theorem.
Theorem 4.1 (Main Theorem) Fix , δ > 0, and we assume that ‖Fi‖Frob ≤ 1. Let R ∈ N, and assume that g(x) satisfies the re-sampling assumption for R. If d̃2i−1 ≥ 2di−1d 64l2d2i−1di 2R2 log( 2ldi−1di δ )e holds for all i = 1, · · · , l, then with probability at least 1− δ, there exist binary matrices M = {Mj}1≤j≤2l such that ‖f(x)− gM (x)‖2 ≤ , for ‖x‖∞ ≤ 1. (7)
In particular, if R is larger than 8ldi−1 √ di log( 2ldi−1di δ ), then d̃2i−1 = 2di−1 is enough.
Theorem 4.1 shows that the iterative randomization is provably helpful to approximate wider networks in the weight-pruning optimization of a random network. In fact, the required width for g(x) in Theorem 4.1 is reduced to even twice as wide as f(x) when the number of re-sampling is sufficiently large, in contrast to the prior results without re-sampling assumption where the required width is logarithmically wider than f(x) [22, 21]. This means that, under a fixed amount of parameters of g(x), we can achieve a higher accuracy by weight-pruning of g(x) with iterative randomization since a wider target network has a higher model capacity.
In the rest of this section we present the core ideas by proving the simplest case (l = d0 = d1 = 1) of the theorem, while the full proof of Theorem 4.1 is given in Appendix A. Note that the full proof is obtained essentially by applying the argument for the simplest case inductively on the widths and depths.

heading: 4.3 Proof ideas for Theorem 4.1
text: Let us consider the case of l = d0 = d1 = 1. Then the target network f(x) can be written as f(x) = wx : R→ R, where w ∈ R, and g(x) can be written as g(x) = vTσ(ux) where u,v ∈ Rd̃1 . Also, subnetworks of g(x) can be written as gm(x) = (v m)Tσ((u m)x) for some m ∈ {0, 1}d̃1 . There are two technical points in our proof. The first point is the following splitting of f(x):
f(x) = wσ(x)− wσ(−x), (8) for any x ∈ R. This splitting is very similar to the one used in the previous works [16, 22, 21]:
f(x) = σ(wx)− σ(−wx). (9)
However, if we use the latter splitting Eq. (9), it turns out that we cannot obtain the lower bound of d̃2i−1 in Theorem 4.1 when d0 > 0. (Here we do not treat this case, but the proof for d0 > 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 , δ ∈ (0, 1), w ∈ [−1, 1], d ∈ N. Let u,v ∼ U [−1, 1]d be uniformly random weights of a 2-layered neural network g(x) := vTσ(u · x). If d ≥ 2d 16 2 log( 2 δ )e holds, then with probability at least 1− δ, ∣∣wx− gm(x)∣∣ ≤ , for all x ∈ R, |x| ≤ 1, (10) where gm(x) := (v m)Tσ(u · x) for some m ∈ {0, 1}d.
Proof (sketch): We assume that d is an even number as d = 2d′ so that we can split an index set {0, · · · , d − 1} of d hidden neurons of g(x) into I = {0, · · · , d′ − 1} and J = {d′, · · · , d− 1}. Then we have the corresponding subnetworks gI(x) and gJ(x) given by gI(x) :=∑ k∈I vkσ(ukx), gJ(x) := ∑ k∈J vkσ(ukx), which satisfy the equation g(x) = gI(x) + gJ(x).
By the splitting Eq. (8), it is enough to consider the probabilities for approximating wσ(x) by a subnetwork of gI(x) and for approximating −wσ(−x) by a subnetwork of gJ(x). Now we have
P ( 6 ∃i ∈ I s.t. |ui − 1| ≤
2 , |vi − w| ≤ 2
) ≤ ( 1− 2
16
)d′ ≤ δ
2 , (11)
P ( 6 ∃j ∈ J s.t. |uj + 1| ≤
2 , |vj + w| ≤ 2
) ≤ ( 1− 2
16
)d′ ≤ δ
2 , (12)
for d′ ≥ 16 2 log ( 2 δ ) , by a standard argument of the uniform distribution and the inequality ex ≥ 1+x for x ≥ 0. By the union bound, with probability at least 1− δ, we have i ∈ I and j ∈ J such that∣∣wσ(x)− viσ(uix)∣∣ ≤ 2 ,∣∣− wσ(−x)− vjσ(ujx)∣∣ ≤ 2 .
Combining these inequalities, we finish the proof.
The second point of our proof is introducing projection maps to leverage the re-sampling assumption, as follows. As in the proof of Lemma 4.2, we assume that d = 2d′ for some d′ ∈ N and let I = {0, · · · , d′ − 1}, J = {d′, · · · , d− 1}. Now we define a projection map
π : Ĩ → I, k 7→ bk/Rc, (13)
where Ĩ := {0, · · · , d′R − 1}, and b·c denotes the floor function. Similarly for J , we can define J̃ := {d′R, · · · , dR− 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 l = d0 = d1 = 1) Fix , δ ∈ (0, 1), w ∈ [−1, 1], d ∈ N. Let u,v ∼ U [−1, 1]d be uniformly random weights of a 2-layered neural network g(x) := vTσ(u · x). Let R ∈ N and we assume that each element of u and v can be re-sampled with replacement up to R− 1 times. If d ≥ 2d 16 2R2 log(
2 δ )e holds, then with probability at least 1− δ,∣∣wx− gm(x)∣∣ ≤ , for all x ∈ R, |x| ≤ 1, (14)
where gm(x) := (v m)Tσ(u · x) for some m ∈ {0, 1}d.
Proof (sketch): Similarly to the proof of Lemma 4.2, we utilize the splitting Eq. (8). We mainly argue on the approximation of wσ(x) since the argument for approximating −wσ(x) is parallel.
By the assumption that each element of u and v can be re-sampled up to R− 1 times, we can replace the probability in Eq. (11) in the proof of Lemma 4.2, using the projection map π : Ĩ → I , by
P ( 6 ∃i1, i2 ∈ Ĩ s.t. π(i1) = π(i2), |ũi1 − 1| ≤
2 , |ṽi2 − w| ≤ 2
) , (15)
where ũ1, · · · , ũd′R, ṽ1, · · · , ṽd′R ∼ U [−1, 1]. Indeed, since we have #{(i1, i2) ∈ Ĩ × Ĩ : π(i1) = π(i2)} = d′R2, (16)
we can evaluate the probability Eq. (15) as Eq.(15) ≤ ( 1− 2
16
)d′R2 ≤ δ
2 , (17) for d′ ≥ 16 2R2 log ( δ 2 ) . 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 −wσ(x) by replacing I with J . The rest of the proof is the same as Lemma 4.2.

heading: 5 Experiments
text: In this section, we perform several experiments to evaluate our proposed method, IteRand (Algorithm 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 a given amount of network parameters. In all experiments, we used the partial randomization with r = 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 small-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× 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] as a 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 1 GPU (NVIDIA GTX 1080 Ti, 11GB) for CIFAR-10 and 2 GPUs (NVIDIA 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 as Section 2, both IteRand and edge-popup requires two distributions: Dparam and Dscore. In our experiments, we consider Kaiming uniform (KU) and signed Kaiming constant (SC) distribution. The KU distribution is the uniform distribution over the interval [− √ 6 cfanin , √ 6 cfanin
] where cfanin is the constant defined for each layer of ReLU neural networks [1][9]. The SC distribution is the uniform distribution over the two-valued set {− √
2 cfanin
, √
2 cfanin }, which is introduced by Ramanujan et al. [23]. We fix Dscore to the KU distribution, and use the KU or SC distribution for Dparam.

heading: 5.1 Varying the network width
text: To demonstrate the parameter efficiency, we introduce a 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 CIFAR-10 using IteRand, edge-popup and SGD, varying the width factor ρ 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 ResNet18 and ResNet34. Our method outperforms the baseline method for various widths. The difference in accuracy is large both when the width is small (ρ ≤ 0.5), and when Dparam is the KU distribution where edge-popup struggles.

heading: 5.2 ImageNet experiments
text: The parameter efficiency of our method is also confirmed on ImageNet (Figure 3a). ImageNet is more difficult than CIFAR-10, and thus more complexity is required for networks to achieve competitive performance. Since our method can increase the network complexity as shown in Section 4, the effect is 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.

heading: 6 Related work
text: Lottery ticket hypothesis Frankle and Carbin [5] originally proposed the lottery ticket hypothesis. Many properties and applications have been studied in subsequent works, such as transferability of winning subnetworks [19], sparsification before training [14, 27, 26] and further ablation studies on the hypothesis [29].
Zhou et al [29] surprisingly showed that only pruning randomly initialized networks without any optimization on their weights can be a training method surprisingly. Ramanujan et al. [23] went
further by proposing an effective pruning algorithm on random networks, called edge-popup, and achieved competitive accuracy compared with standard training algorithms by weight-optimization [24]. Malach et al. [16] mathematically formalized their pruning-only approach as an 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 R 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-based pruning [7], L0 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 a dense-sparse-dense (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 to recover pruned weights by zero-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.

heading: 7 Limitations
text: 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 Dparam is the uniform distribution over the interval [−1, 1]. Thus, generalizing our theorem to other distributions, such as the uniform distribution over binary values {−1, 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 = 1. Whether we can reduce the required width for R > 1 remains an open question.
Also our algorithm (IteRand) and its empirical results have several limitations. (1) Pruning randomlyinitialized 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 is the state-of-the-art 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.

heading: 8 Conclusion
text: 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-pruning can be used instead of the standard weight-optimization within the same memory budget.

heading: Acknowledgement
text: 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.

Review summaries:
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.

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.   The idea and the empirical results are good, however, the theoretical result could be improved significantly.

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}.   The 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.   The empirical experiments demonstrate IteRand achieves better performance than existing weight-pruning optimization methods under the same memory budget.