# Randomly Initialized Subnetworks with Iterative Weight Recycling

Matt Gorbett  Darrell Whitley

###### Abstract

The Multi-Prize Lottery Ticket Hypothesis posits that randomly initialized
neural networks contain several subnetworks that achieve comparable accuracy
to fully trained models of the same architecture. However, current methods
require that the network is sufficiently overparameterized. In this work, we
propose a modification to two state-of-the-art algorithms (Edge-Popup and
Biprop) that finds high-accuracy subnetworks with no additional storage cost
or scaling. The algorithm, Iterative Weight Recycling, identifies subsets of
important weights within a randomly initialized network for intra-layer reuse.
Empirically we show improvements on smaller network architectures and higher
prune rates, finding that model sparsity can be increased through the
”recycling” of existing weights. In addition to Iterative Weight Recycling, we
complement the Multi-Prize Lottery Ticket Hypothesis with a reciprocal
finding: high-accuracy, randomly initialized subnetwork’s produce diverse
masks, despite being generated with the same hyperparameter’s and pruning
strategy. We explore the landscapes of these masks, which show high
variability.

Machine Learning, ICML

##  1 Introduction

The Lottery Ticket Hypothesis (Frankle & Carbin, 2019) demonstrated that
randomly initialized Deep Neural Network’s (DNN’s) contain sparse subnetworks
that, when trained in isolation, achieve comparable accuracy to a fully-
trained dense network of the same structure. The results of the hypothesis
indicate that over-parameterized DNN’s are no longer necessary; instead,
finding ”winning ticket” sparse subnetworks can yield high accuracy models.
The consequences of winning tickets are abundant in practical use: we can
train DNN’s with a decreased computational cost (Morcos et al., 2019)
including memory consumption and inference time, and additionally enable wide-
spread democratization of DNN’s with a low carbon footprint.

Figure 1:  Performance of Iterative Weight Recycling at varying network depth:
We compare the accuracy of our algorithm against Edge-Popup, Biprop, and a
densely trained baseline. We apply our weight recycling algorithm to Biprop
(red) and Edge-Popup (green). We use varying prune rates (x-axis) and varying
network depths (Conv-2 to Conv-8) on VGG-like architectures. We train and
evaluate all algorithms on the CIFAR-10 dataset using the same
hyperparameter’s and training procedure.

Expanding on the Lottery Ticket Hypothesis, Ramanujan et al. (Ramanujan et
al., 2020) reported a remarkable finding: we do not have to train neural
networks at all to find winning tickets. Their algorithm, Edge-Popup,
uncovered sparse subnetworks within randomly initialized DNN’s that achieved
comparable accuracy to fully trained models. This phenomena was mathematically
proven in the Strong Lottery Ticket Hypothesis (Malach et al., 2020).
Practically, this finding showed that gradient-based weight optimization is
not necessary for a neural network to achieve high accuracy. Moreover, it
allows us to overcome difficulties of gradient-based sparsification, such as
getting stuck at local minima and incompatible backpropagation (Diffenderfer &
Kailkhura, 2021). Finally, randomly initialized ”winning ticket” subnetworks
have been shown to be more robust than other pruning methods (Diffenderfer et
al., 2021).

Despite this fascinating discovery, it also marked a key limitation to
existing work: randomly initialized DNN’s require a large number of parameters
in order to achieve high-accuracy. In other words, to reach the same level of
performance as dense networks trained with weight-optimization, randomly
initialized models need more parameters, and hence more memory space.
Subsequent works have relaxed the bounds proposed by the Strong Lottery Ticket
Hypothesis (Pensia et al., 2020; Orseau et al., 2020), showing mathematically
that network width needs to be only logarithmically wider than dense networks.
Chijiwa et. al (Chijiwa et al., 2021) proposed an algorithmic modification to
Edge-Popup, iterative randomization (IteRand), showing that we can reduce the
required network width for weight pruning to the same as a fully trained model
up to constant factors.

In addition to these findings, the Multi-Prize Lottery Ticket Hypothesis
(Diffenderfer & Kailkhura, 2021) showed there are several subnetworks (Multi-
Prize Tickets (MPT’s)) in randomly initialized models that achieve high-
accuracy compared to dense networks. Importantly, the authors translates this
finding into Binary Neural Networks (BNN’s), where they propose a new
algorithm (Biprop) to identify winning tickets in randomly initialized BNN’s.
The implications of this finding allow for extreme compression of large, over-
parameterized models.

In this work, we propose an algorithm to find accurate sparse subnetworks in
randomly initialized DNN’s and BNN’s. Our approach exploits existing weights
in a network layer, identifying subsets of trivial weights and replacing them
with weights influential to a strong subnetwork. We demonstrate our results in
Figure 9, showing improvements on a variety of architectures and prune rates.
Additionally, we provide confirmation for the Multi-Prize Lottery Ticket
Hypothesis, showing evidence that subnetworks generated under tight
hyperparameter control exhibit fundamentally dissimilar structure.

Our contributions are as follows:

  * •

We propose a new algorithm, Iterative Weight Recycling, which improves the
ability to find highly accurate sparse subnetworks within randomly initialized
neural networks. The algorithm is an improvement to both Edge-Popup (for
DNN’s) as well as Biprop (BNN’s). The algorithm identifies $k$ extraneous
weights in a model layer and replaces them with $k$ relevant weight values.

  * •

We examine MPT’s generated under strict hyperparameter control, showing that,
under almost identical conditions, MPT’s display diverse mask structures.
These results indicate that, not only do there exist multiple lottery tickets
within randomly initialized neural networks, but rather an abundance of
lottery tickets.

##  2 Background

In this section, we review current state-of-the-art methods for pruning
randomly initialized and binary randomly initialized neural networks.

Randomly Initialized DNN’s Given a neural network $f(x;\theta)$ with layers
1,…$L$, weight parameters $\theta\in\mathbb{R}^{n}$ randomly sampled from
distribution $\mathcal{D}$ over $\mathbb{R}$, and dataset $x$, we can express
a subnetwork of $f(x;\theta)$ as $f(x;\theta\odot\mathrm{M})$, where
$\mathrm{M}\in\\{0,1\\}^{n}$ is a binary mask and $\odot$ is the Hadamard
product.

Edge-popup (Ramanujan et al., 2020) finds $\mathrm{M}$ within a randomly-
initialized DNN by optimizing weight scoring parameter
$\mathrm{S}\in\mathbb{R}^{n}$ where $\mathrm{S}\sim\mathcal{D}_{score}$.
$\mathrm{S}_{i}$ can be intuitively thought of as an importance score computed
for each weight $\theta_{i}$. The algorithm takes pruning rate hyperparameter
$p\in[0,1]$, and on the forward pass computes $\mathrm{M}$ at $\mathrm{M}_{i}$
as

$\mathrm{M}_{i}=\begin{cases}1&\text{if
$|\mathrm{S}_{i}|\in\\{\tau(i)_{i=1}^{k_{j}}\geq[k_{j}p/100]\\}$}\\\
0&\text{otherwise}\end{cases}$ (1)

where $\tau$ sorts indices $\\{i\\}^{j}_{i=1}\in\mathrm{S}$ such that
$|S_{\tau(i)}|\leq|S_{\tau(i+1)}|$. In other words, masks are computed at each
weight by taking the absolute value of scores for each layer, and setting the
mask to 1 if the absolute score value falls within the top 100*$p$%, otherwise
they set the mask to zero. They use the straight-through estimator (Bengio et
al., 2013) to backpropagrate through the mask and update $\mathrm{S}$ via SGD.

Chijiwa et. al (Chijiwa et al., 2021) improved on the Edge-Popup algorithm
with the IteRand algorithm. They show that by rerandomizing pruned network
weights during training, better subnetworks can be found. They theoretically
prove their results using an approximation theorem indicating rerandomization
operations effectively reduce the required number of parameters needed to
achieve high-accuracy subnetworks.

The IteRand algorithm is mainly driven by two hyperparameters: $K_{per}$ and
re-randomization rate $r$. $K_{per}$ drives the frequency weights will be re-
randomized. The second hyperparameter, $r$, denotes a partial re-randomization
of pruned weights. To achieve the best results, the authors set $r$ to 0.1,
meaning re-randomizing 10% of pruned weights.

Algorithm 1 Edge-Popup with IteRand

1:Require:$\theta\sim\mathcal{D}_{weight},$
$\mathrm{S}\sim\mathcal{D}_{score}$, $p$, $K_{per}$, $r$

2:Input:  Dataset(X,Y)

3:function EdgePopup(S, M, f(x))

4: for each $l\in L$ do

5: if $|s_{i}|\in$ top $k$ $|\mathrm{S}_{l}|$ then $\mathrm{M}_{i}=1$ else
$\mathrm{M}_{i}=0$ end if

6: end for

7: return $\mathrm{S},\mathrm{M}$

8:end function

9:for i=1 …, N-1 do

10: $x,y\leftarrow\textsc{MiniBatch}(X,Y)$

11: $\mathrm{S},\mathrm{M}\leftarrow\textsc{Edge-
Popup}(\mathrm{S},\mathrm{M},f(x))$

12: if $i\mod K_{per}=0$ then

13: $\theta\leftarrow Rerandomize(\theta,\mathrm{M})$

14: end if

15:end for

Randomly-Initialized BNN’s Complementary to the findings reported in the
previous section, Diffenderfer and Kailkhura (Diffenderfer & Kailkhura, 2021)
described a new method for finding high accuracy subnetworks within binary-
weighted models. This finding provides us the ability to store bit size
weights rather than floating-point (32 bit) numbers, leading to substantial
compression of large models. In this section, we summarize the Biprop
algorithm.

We start with a modification of the function described in the previous
section, replacing $\theta\in\mathbb{R}^{n}$ with binary weights
$\mathcal{B}\in\\{-1,1\\}$. The resulting network function becomes
$f(x;\mathcal{B}\odot\mathrm{M})$, with mask $\mathrm{M}$ over binary weights.
Further, Biprop introduces scale parameter $\alpha\in\mathbb{R}$, which
utilizes floating-point weights $\theta$ prior to binarization (Martinez et
al., 2020). The learned parameter rescales binary weights to
$\\{-\alpha,\alpha\\}$, and the resulting network function becomes
$f(x;\alpha(\mathcal{B}\odot\mathrm{M}))$. Parameter $\alpha$ is updated with
$||\mathrm{M}\odot\theta||_{1}/||\mathrm{M}||_{1}$, with $\mathrm{M}$ being
multiplied by $\alpha$ for gradient descent (the straight-through estimator is
still used for backpropagation). During test-time, the learned alpha parameter
simply scales a binarized weight vector. As a result, only bit representations
of the weights are needed at positive mask values ($\pm 1$ where
$\mathrm{M}=1$), substantially reducing memory, storage, and inference costs.

Empirically, Diffenderfer and Kailkhura (Diffenderfer & Kailkhura, 2021) are
able to produce high accuracy binary subnetworks using Biprop on a range of
network architectures, and theoretically prove this result on models with
sufficient over-parameterization. In the subsequent section we show how we can
modify this algorithm, as well as Edge-Popup, with Weight Recycling to achieve
increased performance.

##  3 Iterative Weight Recycling

In this section we detail Iterative Weight Recycling, first summarizing the
methodology behind the approach, and subsequently detailing the experimental
setup and results. Finally we perform empirical analysis on the algorithm,
with results showing that Iterative Weight Recycling emphasizes keeping high
norm weights values similar to the traditional L1 pruning technique.

###  3.1 Method

We consider $f(x;\theta)$ as an $l$-layered neural network with ReLU
activations, dataset $x\in\mathbb{R}^{n}$ with weight parameters
$\theta\sim\mathcal{D}_{weight}$. We freeze $\theta$ and additionally turn off
the bias term for each $l$. Our model is initialized similarly to Edge-Popup
and Biprop: a score pararmeter $\mathrm{S}$ for each $\theta$, where
$\mathrm{S}_{i}$ learns the importance of $\theta_{i}$. Additionally, we set a
pruning rate $p\in[0,1]$. $\mathcal{D}_{weight}$ is initialized using Kaiming
Normal initialization (without scale fan) for Biprop and Signed Constant
Initialization for Edge-Popup. Further, $\mathcal{D}_{score}$ is initialized
with Kaiming Uniform with seed 0, except in Section 4, where we explore
different $\mathrm{S}$ initializations.

Weight recycling works on an iterative basis, similar to IteRand (Chijiwa et
al., 2021). We define two hyperparameters, $K_{per}$ and $r$, where $K_{per}$
is the frequency we change weights, and $r$ is the recycling rate. During the
recycling phase, we compute $k$ as the number of weights we want to change in
a given layer as $j*r$, where $j$ is the size of $\mathrm{S}$ at layer $l$ and
$r\in[0,1]$. We retrieve subsets
$\mathrm{S}^{low}_{l},\mathrm{S}^{high}_{l}\subset\mathrm{S}_{l}$ containing
the lowest absolute $k$ scores and highest absolute $k$ scores at each layer:

$\mathrm{S}^{low}_{l}=\\{\tau(i)^{k}_{i=1}\\}\text{,
}\quad\mathrm{S}^{high}_{l}=\\{\tau(i)^{j}_{i=j-k}\\}$ (2)

where $\tau$ sorts $\\{i\\}^{j}_{i=1}\in\mathrm{S}$ such that
$|S_{\tau(i)}|\leq|S_{\tau(i+1)}|$. Here, $\\{i\\}^{j}_{i=1}$ equates to the
index values associated with set $\\{|S_{\tau}|\\}^{j}_{i=1}$. Next, we
retrieve weight values associated with $\mathrm{S}^{high}_{l}$ and
$\mathrm{S}^{low}_{l}$, with $\\{i,...,k\\}_{S}=\\{i,...,k\\}_{\theta}$ .
Finally, we set $\theta^{low}_{l}$=$\theta^{high}_{l}$. Effectively, the
Iterative Weight Recycling algorithm finds $\mathrm{S}$ values and their
associated index (where $i_{\mathrm{S}}=i_{\theta}$) and retrieves the weight
value associated to the index, for both high and low $\mathrm{S}$ scores. The
algorithm replaces low $\mathrm{S}$ weight values with high $\mathrm{S}$
weight values, discarding of low $\mathrm{S}$ weight values. Algorithm 2
denotes the equation in pseudo-code form.

Algorithm 2 Weight Recycling. Replace line 14 in Algorithm 1 with the
following method

1:function WeightRecycle(S, $\theta$)

2: for each $l\in L$ do $\triangleright$ layer of size j

3: $k\leftarrow j*r$ $\triangleright$ Calculate number of weights to change

4: $\mathrm{S_{l}}^{high}\leftarrow\textit{highest k}\mkern
9.0mu|\mathrm{S}_{l}|$ $\triangleright$ Retrieve indices of top k abs(score)
values

5: $\mathrm{S_{l}}^{low}\leftarrow\textit{lowest k}\mkern
9.0mu|\mathrm{S}_{l}|$ $\triangleright$ Retrieve indices of bottom k
abs(score) values

6:
$\theta_{l}[\mathrm{S_{l}}^{low}]\leftarrow\theta_{l}[\mathrm{S_{l}}^{high}]$$\triangleright$
Replace low $\theta_{l}$ with high $\theta_{l}$

7: end for

8: return $\mathrm{S},\mathrm{M}$

9:end function

Figure 2: Effects of Varying Width at 50% Prune Rate Results of baseline
models (Dense, Biprop, Edge-Popup) and Iterative Weight Recycling models at
varying network widths up to one. Using Iterative Weight Recycling yields
winning tickets with a comparable accuracy to densely trained models at just
50% width factor in all architectures. Error bars are denoted for Iterative
Weight Recycling algorithms.

###  3.2 Experimental Setup

To begin, we use model architectures and datasets similar to the three
previous works. Conv-2 to Conv-8 are VGG-like CNNs (Simonyan & Zisserman,
2015) with depth $d$= 2 to 8 . We additionally use their ”wide” analogues,
which introduces a scale parameter at each layer to influence the specific
width of each layer width $w$=0.1 to 1. Additionally we use ResNets (He et
al., 2015), which utilize skip connections and batch normalization. We test
the models on both CIFAR-10 and ImageNet datasets. Non-affine transformation
is used for all CIFAR-10 experiments, and ResNets use a learned batch
normalization similar to (Diffenderfer & Kailkhura, 2021). We apply similar
pruning rates to previous works $\\{0.2,0.4,0.5,0.6,0.8,0.9\\}$, and
additionally test our method at prune rates above 0.9. In Iterative Weight
Recycling experiments, we use three different initializations, and report the
average accuracy, with error bars denoting the lowest and highest accuracy.

We compare the performance of Iterative Weight Recycling to Edge-Popup,
Biprop, and IteRand algorithms using the same hyperparameters. For each
baseline algorithm, we use the hyperparameters that yielded the best results
in the original papers: Signed Constant initialization for Edge-Popup/IteRand,
and Kaiming Normal with scale fan for Biprop. For our algorithm, we use these
same initialization strategies, except for Biprop with Weight Recycling we did
not use scale fan as this yielded slightly better results. Additionally, for
IteRand we use the same $K_{per}$ and $r$ as the paper: $K_{per}=1$ (once per
epoch), with $r=0.1$. For our algorithm, we choose $K_{per}=10$ and $r=0.2$
for all models. We found that less frequent recycling yielded better results,
hypothesizing that recycling too frequently yielded redundant values.

###  3.3 Results

In this section we test the effects of network overparameterization and prune
rate on subnetwork performance, with the goal of empirically verifying the
Iterative Weight Recycling compared to Edge Popup (Ramanujan et al., 2020),
Biprop (Diffenderfer & Kailkhura, 2021), and IteRand (Chijiwa et al., 2021)
algorithms. We follow previous works and test neural networks with varying
depth and width, and additionally test each algorithm at high prune rates.

Figure 3:  Pruning Algorithm Performance with Limited Parameters We test the
effect of high prune rates on model performance, showing that Weight Recycling
achieves high accuracy compared to IteRand, Edge-Popup, and Biprop. Left:
Accuracies of various VGG architectures with prune rates greater than 80% and
parameter count less than 500k. We include architecture, prune rate, and
original parameters of the model in four of the datapoints. Right: ResNet18
with prune rates greater than 95%. With just under 600k parameters (95% prune
rate), ResNet18 with Iterative Weight Recycling achieves higher accuracy than
a dense baseline model (93.1%).

Varying Depth In Figure 9, we vary the depth of VGG architectures from 2 to 8
and compare the test accuracy at various prune rates. We observe a clear
advantage to using Iterative Weight Recycling: at every prune rate and model
architecture, Iterative Weight Recycling outperforms both Biprop and Edge-
Popup. Additionally, Biprop with Weight Recycling generally outperforms Edge-
Popup with Weight Recycling at higher prune rates. Iterative Weight Recycling
outperforms dense models in each architecture except when 90% of the weights
have been pruned. Notably, we discover that Iterative Weight Recycling is able
to achieve accuracy exceeding the dense model in Conv-2 architectures. This is
the first such observation on a low-depth model – Edge-Popup and Biprop
research reported test accuracy near the dense model, however never clearly
exceeded it. Further, Biprop+Iterative Weight Recycling is able to achieve an
80.23% test accuracy with just 20% of the weights.

Varying Width We also consider network width as a factor to control network
parameterization. Previous showed that as we increase width, our chances of
finding winning tickets increased. Edge-Popup found winning tickets at width
factors greater than 1, while Biprop reported winning tickets around width
factor 1.

In Figure 2, we demonstrate the efficacy of Iterative Weight Recycling on
networks with width factors less than one. Results show that in each
architecture, we can find winning tickets at just 50% width. In practical
terms, in a Conv-4 architecture this equates to just 25% of the parameters
compared to a Conv-4 with width factor 1 (600k vs. 2.4m). Additionally, our
Conv-4 architecture with width factor 0.5 achieved an accuracy of 86.5%
compared to 86.66% for a dense Conv-4 with width factor 1.

Varying Prune Rate In Figure 3, we demonstrate the results of Biprop, Edge-
Popup, IteRand, and Iterative Weight Recycling (Biprop) on DNN’s with prune
rates above 80%. Iterative Weight Recycling shows favorable results with
limited parameter counts. Notably, the algorithm consistently outperformed
IteRand at aggressive prune rates between 80% and 99%. At more modest prune
rates (20%-60%), Weight Recycling was comparable to IteRand, which we
summarize in Section 3.4.

In the ResNet18 architecture (11 million parameters), our algorithm was able
to find winning tickets with just 5% of the random weights. These results are
further evidence that overparameterization helps in the identification of high
performing subnetworks.

Algorithm | Prune % | # Params | Acc.(%)
---|---|---|---
Edge-Popup | 70% | 7.6M | 67.13
Edge-Popup+IteRand | 70% | 7.6M | 69.11
Edge-Popup+IWR | 70% | 7.6M | 69.02
Edge-Popup+IWR | 80% | 5.1M | 68.87
Biprop | 70% | 7.6M | 67.76
Biprop+IteRand | 70% | 7.6M | 43.76
Biprop+IWR | 70% | 7.6M | 69.85
Biprop+IWR | 80% | 5.1M | 68.65
Table 1: ImageNet results on ResNet50: We test various pruning algorithms on
the ImageNet dataset with the ResNet50 architecture. Results show that
Iterative Weight Recycling (bold) achieves similar results to Edge-Popup,
Biprop, and IteRand with 2.5 million less parameters.

ImageNet Results In Table 1, we highlight the results of our algorithm on the
ImageNet dataset. We choose a ResNet50 architecture which contains 25.5
million total parameters. We train each baseline algorithm with a 70% prune
rate, similar to previous papers. Results for IteRand and Edge-Popup were
within 0.1% of the original papers results.

Results show that our algorithm performs well under more aggressive pruning
rates compared to Edge-Popup, IteRand, and Biprop, similar to what we found in
Section 3.3. Specifically, our algorithm performed similar to, or better than,
previous algorithms with 2.5 million less parameters.

###  3.4 Analysis

In this section we provide empirical justification for Iterative Weight
Recycling.

Effect of Random Weights We first perform an ablation study on the effects of
random weights by assessing whether $\mathrm{S}^{low}$ can be replaced by any
subset of weights. Specifically, to justify the reuse of ”important” weights
as identified $\mathrm{S}$, we replace $\mathrm{S}^{high}$ at $l$ with
$\mathrm{S}^{high}_{l}=\\{\tau(i)^{2k}_{i=k+1}\\}$. Effectively, this recycles
weight values deemed to be in the second tier of ”unimportance” as measured by
parameter $\mathrm{S}$.

In our experiments, we train a Conv-6 architecture with both Edge-Popup and
Biprop Weight Recycling algorithms with 3 different initializations to compare
the effectiveness of the approach to the baseline algorithm. We use the same
hyperparameters as the initial experiments, except we use Kaiming Normal
initialization for Edge-Popup.

Biprop accuracy dropped from 90.9%($\pm 0.2$ ) to 89.7%($\pm 0.5$), and Edge-
Popup accuracy dropped from 88.9%($\pm 0.3$ ) to 87.15%($\pm 0.5$). Results of
these experiments indicate a benefit to recycling high importance weights as
opposed to other random weights. Finally, we note that recycling weights is
more computationally efficient than re-randomizing weights.

Norms on Pretrained Models In this section we study the Frobenius norms of
various pruning algorithms. We first train a dense Conv-8 network using a
standard training procedure on the CIFAR-10 dataset, and subsequently apply
Edge-Popup, Biprop, and Iterative Weight Recycling algorithms to prune the
trained model. Frobenius norms of each model layer and algorithm are depicted
in Figure 6, with each algorithm using a 50% prune rate except for the dense
network.

Analyzing the norms of unpruned weights (depicted with a ”+”) compared to
pruned weights (”-”) shows that each algorithm exhibits higher norms in its
unpruned weight mask compared to its pruned weights, except for Iterative
Weight Recycling. Interestingly, even Biprop, which uses floating-point
weights prior to binarization, exhibits higher norms in its unpruned weights.
Iterative Weight Recycling, on the other hand, exhibits similar norms in both
its pruned and unpruned weights.

Figure 4:  Norms across layers. We apply various pruning algorithms to a dense
pretrained Conv-8 architecture, showing that Iterative Weight Recycling
exhibits high norms. ”+” indicates unpruned norms, ”-” pruned norms.

Results of this analysis indicate that high-norm weight values are chosen
naturally in both Edge-Popup and Biprop. We show that Weight Recycling
emphasizes the reuse of high-norm weight values, creating a search space of
good candidates compared to a randomly initialized population.

We show similar results on randomly initialized networks in the Appendix, with
each algorithm choosing high norm weights. IteRand exhibited similar results,
however we excluded these results in Figure 6 for visualization purposes.

Figure 5: Comparing MPT’s: We train multiple models with the same weight
initialization and constrain hyperparameters such as prune rate. The only
hyperparameter we modify is the seed of masking parameter $\mathrm{S}$. Under
these constraints, our results yield diverse masks, confirming that multiple
winning tickets exist in a randomly initialized network. The similarity matrix
(left) highlights the low JI when comparing 15 Edge-Popup models and 15 Biprop
models with the same weight initialization and prune rate (0.5). Despite this,
JI values fall within small ranges, indicating the algorithms converge to a
similar search space. The bottom triangle compares Edge-Popup and the top
triangle Biprop. The layer-by-layer similarity scores (right) summarizes the
mean JI across models layers. In the error bars we denote the min and max
model values for each layer.

Iterative Weight Recycling compared to IteRand Comparing Iterative Weight
Recycling to IteRand yields statistically insignificant improvements in the
Edge-Popup algorithm using Signed Constant initialization. We argue that any
weight randomization works well under this initialization because constant
weight values make recycling less relevant. However, weight recycling performs
as well, if not slightly better than IteRand with less computational cost.
Finally, weight recycling outperforms IteRand at aggressive prune rates, as
depicted in Figure 3.

In addition to these arguments we note several key limitations to IteRand: 1)
Additional storage cost. By iteratively re-randomizing weights, we need to
save additional random seeds and binary masks every $K_{per}$ during training.
In limited compute environments this may become a restraining factor. In the
original work, $K_{per}$ was set to aggressive values: one to ten times per
epoch. 2) Periodically re-randomizing weights creates an artificially over-
parameterized model. If pruned weights are re-initialized with rate $r$ every
$K_{per}$ for $K$ epochs, a network with $n$ weights needs
$n+K{}/K_{per}(n\cdot p\cdot r)$ weight values to achieve high-accuracy.
Iterative Weight Recycling instead shows that relevant weight values exist as
a subset of the original $n$ parameters, and identifies those values for
reuse. 3) In the original paper, IteRand was only tested on Edge-Popup. We
implemented IteRand on the Biprop algorithm and were unable to achieve
successful results on over half a dozen configurations. Table 1 (Biprop)
depicts these results.

##  4 Winning Tickets Galore

The Multi-Prize Lottery Ticket Hypothesis (Diffenderfer & Kailkhura, 2021)
posits that a randomly initialized neural network contains several winning
tickets that achieve accuracy comparable to weight trained models of the same
architecture. In this section, we further assess this hypothesis by asking the
following question: Given a sufficiently overparameterized network, can we
find multiple winning tickets (MPT’s) under strict hyperparameter control?

While MPT’s were shown to be theoretically possible (Diffenderfer & Kailkhura,
2021), empirical results were mostly limited to showing the existence of MPT’s
by varying the prune rate. While this was sufficient evidence for the proof,
we instead seek to evaluate whether winning tickets exhibit differing
structures in a constrained environment. In particular, we restrict
hyperparameters such as prune rate in order to evaluate the heterogeneity of
MPT’s.

We hypothesize that winning tickets, i.e. unique mask structures, exist in
larger quantities than has previously been reported. To exemplify this,
consider the smallest layer of a Conv-6 network (the first layer) containing
1,258 weights. When restricting the search for a mask to a specific prune
rate, say 95%, there are $1,258\choose 63$ possible masks to choose from, an
astronomical number.

Experiments We use the Conv-6 network since it is relatively compact (2.26m
parameters) and also generates winning tickets at multiple prune rates. To
perform hyperparameter control, we initialize each model with an identical
configuration; additionally, we seed each run to a) initialize the same
weights b) execute the same training feed (i.e. batches are identical in both
data and ordering), and c) facilitate consistency across libraries and devices
(e.g.. NumPy/PyTorch, CPU/GPU). We set the torch CUDA backend to
’deterministic’, as is recommended in documentation. Our single hyperparameter
modification is the seed for score parameter $\mathrm{S}$, which we increment
by one for each subsequent model.

We train models using the standard Edge-Popup and Biprop algorithms. At 50%
prune rate, we train 15 models for each algorithm, and at 75% and 90% prune
rates we train 5 models for each algorithm. We note that each pruned model
achieved test accuracy similar to other models of the same algorithm and prune
rate: Edge-Popup at 50% prune rate ($\mu=89.57\%\pm 0.2$), 75% prune rate
($\mu=86.75\%\pm 0.1$), 90% prune rate ($\mu=79.73\%\pm 0.1$). Biprop at 50%
prune rate($\mu=89.7\%\pm 0.2$), 75% prune rate ($\mu=88.56\%\pm 0.2$), 90%
prune rate ($\mu=82.56\%\pm 0.1$). For Biprop, scale parameter $\alpha$ is
converted to one for each mask in order to compute mask equality.

We evaluate the similarity of binary masks using Simple Matching Coefficient
(SMC) (Rand, 1971), and JI (Jaccard, 1912; Tanimoto, 1956). SMC measures the
total percentage of matching masks, whereas JI measures the percentage of
masks equal to one, excluding mutual absence from the denominator
($M_{11}/(M_{01}+M_{10}+M_{11})$.

Alg. | Pruned | SMC | JI
---|---|---|---
Edge-Popup | 50% | 0.51 | 0.25
Edge-Popup | 75% | 0.63 | 0.13
Edge-Popup | 90% | 0.82 | 0.05
Biprop | 50% | 0.58 | 0.29
Biprop | 75% | 0.68 | 0.18
Biprop | 90% | 0.84 | 0.09
Table 2: Mask similarity statistics: Statistics of model combinations with
varying algorithms and prune rates.

Results In Figure 5, we show the heatmap of JI coefficients at 50% prune rate
as well as layer level JI for each algorithm. Results across coefficients,
model layers, and prune rates indicate that masks generated with different
scoring seeds produce contrasting structures. For example, the similarity
matrix in Figure 5 and the summary statistics in Table 2 show all algorithm
combinations yield JI averages less than 0.29, a large difference between
masks in all circumstances. SMC values yielded higher scores (up to 0.84 in
Table 2), but this is expected at higher prune rates as most masks will have
matching zeroes. A telling distinction of uniqueness is the JI at higher prune
rates: at 90% pruning, there is very low commonality between positive masks
chosen for the subnetworks (0.05 and 0.09).

Results also indicate several similarities. Figure 5 compares each model
against 14 others for each algorithm, with JI scores falling within $1/100$ of
a decimal place of each other. We speculate this as being a result of the
algorithm and the prune rate: since each layer is confined to a specific prune
rate, its match rate compared to the same layer in another model will be
constrained by the prune rate. A second similarity can be seen in layerwise
coefficients yielding similar patterns across models. The first layer exhibits
the highest similarity in all cases, indicating the masking structure needed
to learn dataset inputs is important. Middle layers yielded diverse masks,
showing that weights at these layers exhibit more interchangeable utility.
Finally, the last layer generally yielded higher similarity coefficients,
indicating the importance of specific weights for classification.

Practically, this analysis provides several avenues for future research.
First, the existence of MPT’s under hyperparameter control shows evidence that
the total quantity of MPT’s may be large. Understanding this theoretical
quantity may guide us in the search for better models. And second, assessing
the similarities of weights across MPT’s can help us in understanding the
desirable properties inherent to successful subnetworks.

##  5 Related Work

Traditional Network Pruning The effectiveness of sparse neural networks was
first demonstrated by Lecun et. al (LeCun et al., 1989). With the advent of
deep learning, the size and efficiency of ML models quickly became a critical
limitation. Naturally, research aimed at decreasing size (Han et al., 2015;
Hinton et al., 2014), and limiting power and energy consumption (Yang et al.,
2017).

Lottery Ticket Hypothesis The Lottery Ticket Hypothesis found that dense
networks contained randomly-initialized subnetworks that, when trained on
their own, achieved accuracy comparable to the original dense model. However,
the approach required training a dense network in order to identify winning
tickets. Subsequent work identified strategies to prune DNN’s without a
pretrained model using greedy forward selection (Ye et al., 2020), mask
distances (You et al., 2022), flow preservation techniques (Wang et al.,
2019a; Tanaka et al., 2020), and channel importance (Wang et al., 2019b).

Randomized Neural Networks Important to work described in (Ramanujan et al.,
2020; Chijiwa et al., 2021; Malach et al., 2020), randomized neural networks
(Gallicchio & Scardapane, 2020) have also been explored in shallow
architectures. Several applications explore randomization, including random
vector functional links (Needell et al., 2020; Pao et al., 1994; Pao &
Takefuji, 1992), random features for kernel approximations (Le et al., 2013;
Rahimi & Recht, 2007; Hamid et al., ), reservoir computing (Lukoševičius &
Jaeger, 2009), and stochastic configuration networks (Wang & Li, 2017).

Binary Neural Networks BNN’s studied in this paper fall into the class of
quantized neural networks. Like pruning, quantization is a natural approach
for model compression. Common techniques for creating quantized networks
include post-training quantization with retraining (Gysel et al., 2018;
Dettmers, 2016) and quantization-aware training (Gupta et al., 2015). In the
Biprop algorithm proposed in (Diffenderfer & Kailkhura, 2021), quantization-
aware binary neural networks are trained with parameter $\alpha$, which
enables floating-point weights to learn a scale parameter prior to
binarization (Martinez et al., 2020).

##  6 Discussion

In this work, we propose a novel algorithm for finding highly accurate
subnetworks within randomly initialized models. Iterative Weight Recycling is
successful on both DNN’s (Edge-Popup) as well as BNN’s (Biprop). Our results
indicate that smaller networks are able to achieve higher accuracy than
previously thought. Practically, this allows us to create accurate and
compressed models in limited compute environments.

In addition, we show evidence of abundant MPT’s by creating variegated
subnetworks with nearly identical hyperparameters. This provides several
avenues for further investigation: 1) Deriving the theoretical limits on the
total number of MPT’s in a given architecture 2) Exploring the properties of
the unpruned weights to better understand weight optimization, and 3)
Exploring weight pruning in different problem domains such as NLP.

## References

  * Bengio et al. (2013) Bengio, Y., Léonard, N., and Courville, A.  Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation.  _arXiv:1308.3432 [cs]_ , August 2013.  URL http://arxiv.org/abs/1308.3432.  arXiv: 1308.3432.
  * Chijiwa et al. (2021) Chijiwa, D., Yamaguchi, S. y., Ida, Y., Umakoshi, K., and INOUE, T.  Pruning Randomly Initialized Neural Networks with Iterative Randomization.  In _Advances in Neural Information Processing Systems_ , volume 34, pp. 4503–4513. Curran Associates, Inc., 2021.
  * Dettmers (2016) Dettmers, T.  8-Bit Approximations for Parallelism in Deep Learning.  _arXiv:1511.04561 [cs]_ , February 2016.  URL http://arxiv.org/abs/1511.04561.  arXiv: 1511.04561.
  * Diffenderfer & Kailkhura (2021) Diffenderfer, J. and Kailkhura, B.  Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network.  _arXiv:2103.09377 [cs]_ , March 2021.  URL http://arxiv.org/abs/2103.09377.  arXiv: 2103.09377.
  * Diffenderfer et al. (2021) Diffenderfer, J., Bartoldson, B. R., Chaganti, S., Zhang, J., and Kailkhura, B.  A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness.  2021\.
  * Frankle & Carbin (2019) Frankle, J. and Carbin, M.  The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks.  March 2019.  URL http://arxiv.org/abs/1803.03635.  arXiv: 1803.03635.
  * Gallicchio & Scardapane (2020) Gallicchio, C. and Scardapane, S.  Deep Randomized Neural Networks.  In Oneto, L., Navarin, N., Sperduti, A., and Anguita, D. (eds.), _Recent Trends in Learning From Data: Tutorials from the INNS Big Data and Deep Learning Conference (INNSBDDL2019)_ , Studies in Computational Intelligence, pp. 43–68. Springer International Publishing, Cham, 2020.  ISBN 978-3-030-43883-8.  doi: 10.1007/978-3-030-43883-8˙3.  URL https://doi.org/10.1007/978-3-030-43883-8_3.
  * Gupta et al. (2015) Gupta, S., Agrawal, A., Gopalakrishnan, K., and Narayanan, P.  Deep Learning with Limited Numerical Precision.  pp. 10, 2015.
  * Gysel et al. (2018) Gysel, P., Pimentel, J., Motamedi, M., and Ghiasi, S.  Ristretto: A Framework for Empirical Study of Resource-Efficient Inference in Convolutional Neural Networks.  _IEEE Transactions on Neural Networks and Learning Systems_ , 29(11):5784–5789, November 2018.  ISSN 2162-2388.  doi: 10.1109/TNNLS.2018.2808319.  Conference Name: IEEE Transactions on Neural Networks and Learning Systems.
  * (10) Hamid, R., Xiao, Y., Gittens, A., and DeCoste, D.  Compact Random Feature Maps.  pp. 9.
  * Han et al. (2015) Han, S., Pool, J., Tran, J., and Dally, W. J.  Learning both Weights and Connections for Efficient Neural Networks.  October 2015.  URL http://arxiv.org/abs/1506.02626.  arXiv: 1506.02626.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Deep Residual Learning for Image Recognition.  Technical Report arXiv:1512.03385, arXiv, December 2015.  URL http://arxiv.org/abs/1512.03385.  arXiv:1512.03385 [cs] type: article.
  * Hinton et al. (2014) Hinton, G., Vinyals, O., and Dean, J.  Distilling the Knowledge in a Neural Network.  March 2014.  URL http://arxiv.org/abs/1503.02531.  arXiv: 1503.02531.
  * Jaccard (1912) Jaccard, P.  The Distribution of the Flora in the Alpine Zone.1.  _New Phytologist_ , 11(2):37–50, 1912.  ISSN 1469-8137.  doi: 10.1111/j.1469-8137.1912.tb05611.x.  URL https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1469-8137.1912.tb05611.x.  _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1469-8137.1912.tb05611.x.
  * Le et al. (2013) Le, Q., Sarlos, T., and Smola, A.  Fastfood - Computing Hilbert Space Expansions in loglinear time.  In _Proceedings of the 30th International Conference on Machine Learning_ , pp. 244–252. PMLR, May 2013.  URL https://proceedings.mlr.press/v28/le13.html.  ISSN: 1938-7228.
  * LeCun et al. (1989) LeCun, Y., Denker, J., and Solla, S.  Optimal Brain Damage.  In _Advances in Neural Information Processing Systems_ , volume 2. Morgan-Kaufmann, 1989.
  * Lukoševičius & Jaeger (2009) Lukoševičius, M. and Jaeger, H.  Reservoir computing approaches to recurrent neural network training.  _Computer Science Review_ , 3(3):127–149, August 2009.  ISSN 1574-0137.  doi: 10.1016/j.cosrev.2009.03.005.  URL https://www.sciencedirect.com/science/article/pii/S1574013709000173.
  * Malach et al. (2020) Malach, E., Yehudai, G., Shalev-Schwartz, S., and Shamir, O.  Proving the Lottery Ticket Hypothesis: Pruning is All You Need.  In _Proceedings of the 37th International Conference on Machine Learning_ , pp. 6682–6691. PMLR, November 2020.  ISSN: 2640-3498.
  * Martinez et al. (2020) Martinez, B., Yang, J., Bulat, A., and Tzimiropoulos, G.  Training Binary Neural Networks with Real-to-Binary Convolutions.  March 2020.  URL http://arxiv.org/abs/2003.11535.  arXiv: 2003.11535.
  * Morcos et al. (2019) Morcos, A., Yu, H., Paganini, M., and Tian, Y.  One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Needell et al. (2020) Needell, D., Nelson, A. A., Saab, R., and Salanevich, P.  Random Vector Functional Link Networks for Function Approximation on Manifolds.  _arXiv:2007.15776 [cs, math, stat]_ , July 2020.  URL http://arxiv.org/abs/2007.15776.  arXiv: 2007.15776.
  * Orseau et al. (2020) Orseau, L., Hutter, M., and Rivasplata, O.  Logarithmic Pruning is All You Need.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 2925–2934. Curran Associates, Inc., 2020.
  * Pao & Takefuji (1992) Pao, Y.-H. and Takefuji, Y.  Functional-link net computing: theory, system architecture, and functionalities.  _Computer_ , 25(5):76–79, May 1992.  ISSN 1558-0814.  doi: 10.1109/2.144401.  Conference Name: Computer.
  * Pao et al. (1994) Pao, Y.-H., Park, G.-H., and Sobajic, D. J.  Learning and generalization characteristics of the random vector functional-link net.  _Neurocomputing_ , 6(2):163–180, April 1994.  ISSN 0925-2312.
  * Pensia et al. (2020) Pensia, A., Rajput, S., Nagle, A., Vishwakarma, H., and Papailiopoulos, D.  Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 2599–2610. Curran Associates, Inc., 2020.
  * Rahimi & Recht (2007) Rahimi, A. and Recht, B.  Random Features for Large-Scale Kernel Machines.  In _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2007.
  * Ramanujan et al. (2020) Ramanujan, V., Wortsman, M., Kembhavi, A., Farhadi, A., and Rastegari, M.  What’s Hidden in a Randomly Weighted Neural Network?  In _Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Rand (1971) Rand, W. M.  Objective Criteria for the Evaluation of Clustering Methods.  _Journal of the American Statistical Association_ , 66(336):846–850, December 1971.  ISSN 0162-1459.  doi: 10.1080/01621459.1971.10482356.  URL https://www.tandfonline.com/doi/abs/10.1080/01621459.1971.10482356.
  * Simonyan & Zisserman (2015) Simonyan, K. and Zisserman, A.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  Technical Report arXiv:1409.1556, arXiv, April 2015.  URL http://arxiv.org/abs/1409.1556.  arXiv:1409.1556 [cs] type: article.
  * Tanaka et al. (2020) Tanaka, H., Kunin, D., Yamins, D. L., and Ganguli, S.  Pruning neural networks without any data by iteratively conserving synaptic flow.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 6377–6389, 2020.
  * Tanimoto (1956) Tanimoto, T. T.  An elementary mathematical theory of classification and prediction.  pp. 37–50, 1956.
  * Wang et al. (2019a) Wang, C., Zhang, G., and Grosse, R.  Picking Winning Tickets Before Training by Preserving Gradient Flow.  September 2019a.  URL https://openreview.net/forum?id=SkgsACVKPH.
  * Wang & Li (2017) Wang, D. and Li, M.  Stochastic Configuration Networks: Fundamentals and Algorithms.  _IEEE Transactions on Cybernetics_ , 47(10):3466–3479, October 2017.  ISSN 2168-2275.  doi: 10.1109/TCYB.2017.2734043.  Conference Name: IEEE Transactions on Cybernetics.
  * Wang et al. (2019b) Wang, Y., Zhang, X., Xie, L., Zhou, J., Su, H., Zhang, B., and Hu, X.  Pruning from Scratch.  _arXiv:1909.12579 [cs]_ , September 2019b.  URL http://arxiv.org/abs/1909.12579.  arXiv: 1909.12579.
  * Yang et al. (2017) Yang, T.-J., Chen, Y.-H., and Sze, V.  Designing Energy-Efficient Convolutional Neural Networks using Energy-Aware Pruning.  April 2017.  URL http://arxiv.org/abs/1611.05128.  arXiv: 1611.05128.
  * Ye et al. (2020) Ye, M., Gong, C., Nie, L., Zhou, D., Klivans, A., and Liu, Q.  Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pp. 10820–10830. PMLR, November 2020.  URL https://proceedings.mlr.press/v119/ye20b.html.  ISSN: 2640-3498.
  * You et al. (2022) You, H., Li, C., Xu, P., Fu, Y., Wang, Y., Chen, X., Baraniuk, R. G., Wang, Z., and Lin, Y.  Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks.  _arXiv:1909.11957 [cs, stat]_ , February 2022.  URL http://arxiv.org/abs/1909.11957.  arXiv: 1909.11957.

##  Appendix A Analysis: Random Weights

In Figure 6, we analyze the norms of the weights chosen by various subnetwork
identification algorithms. We train each subnetwork identification algorithm
on Kaiming Normal randomly initialized weights with a 50% prune rate.

In Figure 6, we measure the Frobenius norms of each layer for the unpruned
masks (denoted with a ”+”), as well as the norms of weights for the pruned
masks (denoted with a ”-”). Unpruned masks (”+”) are the identified
subnetworks chosen by each algorithm. Results show that for each of the four
algorithms, the weights at positive masks contain higher norms than the
weights of disposed zero masks. Notably, the two highest identified norms,
IteRand and Weight Recycling, perform the strongest. Weight Recycling negative
masks overlap with its positive masks almost identically, and Edge-Popup and
Biprop negative masks overlap almost identically with each other.

This shows evidence that high norm weights are beneficial to a successful
subnetwork in each algorithm, with Iterative Weight Recycling emphasizing the
reuse of these high norm weights across its pruned and unpruned weight masks.

Figure 6:  Frobenius norms across algorithms and model layers for pruned and
unpruned weights. ”+” denotes the learned high-accuracy subnetwork, ”-”
denotes the pruned weights. Each algorithm keeps weights with higher norms,
discarding lower norm weights. Weight Recycling reuses high norm weights to
identify the best subnetwork.

##  Appendix B CIFAR-10 Hyperparameters

For CIFAR-10 experiments, we test each algorithm using Conv-2 to Conv-8
architectures as well as ResNet18. Additionally, we test each algorithm with
layer width parameter $p$ for Conv-2 to Conv-8 algorithms. These architectures
are built using the same codebase as Edge-Popup and IteRand. We refer to the
Edge-Popup GitHub for model definitions:
https://github.com/allenai/hidden-networks/tree/master/models

Baseline models For our baseline models, we train dense models with learned
weights. We use the SGD optimizer initialized with kaiming normal weights,
with a learning rate of 0.01 for 100 epochs with batch size 128. We
additionally use a weight decay of 1e-4 and momentum 0.9. Cosine decay
learning rate policy is used for all models.

Subnetwork algorithms We train Edge-Popup, IteRand, Biprop, and Weight
Recycling with similar hyperparameters. We try to train baseline algorithms
with the same hyperparameters as used in the original papers (ass denoted
below).

All models are are trained with hyperparameters as follows:

  1. 1.

SGD optimizer, learning rate 0.1

  2. 2.

250 Epochs

  3. 3.

Batch Size=128

  4. 4.

Weight Decay=1e-4 for Conv2-Conv8 models, 5e-4 for ResNet

  5. 5.

Cosine decay learning rate policy

  6. 6.

Non-Affine BatchNorm

  7. 7.

Score parameter $\mathrm{S}$ initialized with Kaiming Uniform

Algorithm | Weight Init.
---|---
Edge-Popup | Signed Constant
Edge-Popup+IteRand | Signed Constant
Biprop | Kaiming Normal
Biprop+IteRand | Kaiming Normal
Edge-Popup+Weight Recycle | Signed Constant
Biprop+Weight Recycle | Kaiming Normal
Table 3: Weight initializations used for each experiment.

IteRand with Biprop We try several configurations for Biprop + IteRand,
applying the same code as the original authors from each paper. Configurations
Signed Constant and Unsigned Constant initialization, modified learning rate,
modified rerandomization frequency and rate (we chose parameters identical to
Weight Recycling, 10 and 0.2, respectively), modified score seed, modified
weight seed. In the result tables below, we use the same hyperparameters as
the original paper, using Kaiming Normal initialization for Biprop+IteRand
experiments.

Model Sizes

Prune Rate | Width Factor | Conv2 | Conv4 | Conv6 | Conv8 | ResNet18
---|---|---|---|---|---|---
0 | 1 | 4,300,992 | 2,425,024 | 2,261,184 | 5,275,840 | 11,678,912
0 | 0.1 | 39,761 | 22,505 | 21,630 | 51,614 | -
0 | 0.25 | 269,616 | 152,368 | 142,128 | 330,032 | -
0 | 0.5 | 1,076,320 | 607,328 | 566,368 | 1,319,392 | -
0.2 | 1 | 3,440,794 | 1,940,019 | 1,808,947 | 4,220,672 | 9,343,129.60
0.4 | 1 | 2,580,595 | 1,455,014 | 1,356,710 | 3,165,504 | 7,007,347.20
0.5 | 1 | 2,150,496 | 1,212,512 | 1,130,592 | 2,637,920 | 5,839,456.00
0.6 | 1 | 1,720,397 | 970,010 | 904,474 | 2,110,336 | 4,671,564.80
0.8 | 1 | 860,198 | 485,005 | 452,237 | 1,055,168 | 2,335,782.40
0.9 | 1 | 430,099 | 242,502 | 226,118 | 527,584 | 1,167,891.20
0.95 | 1 | 215,050 | 121,251 | 113,059 | 263,792 | 583,945.60
0.98 | 1 | 86,020 | 48,500 | 45,224 | 105,517 | 233,578.24
0.99 | 1 | 43,010 | 24,250 | 22,612 | 52,758 | 116,789.12
0.5 | 0.1 | 19,881 | 11,253 | 10,815 | 25,807 | -
0.5 | 0.25 | 134,808 | 76,184 | 71,064 | 165,016 | -
0.5 | 0.5 | 538,160 | 303,664 | 283,184 | 659,696 | -

##  Appendix C CIFAR-10 Results

In this section we detail the results across CIFAR10 models. Accuracies for
Weight Recycling experiments are averaged across three runs.

Dense model accuracy’s:

Prune Rate | Width Factor | Conv2 | Conv4 | Conv6 | Conv8 | ResNet18
---|---|---|---|---|---|---
0 | 1 | 79.9 | 87 | 89 | 89.41 | 93.03
0 | 0.1 | 58.5 | 67.26 | 72.48 | 75.06 | -
0 | 0.25 | 72.49 | 81.13 | 83.65 | 84.75 | -
0 | 0.5 | 77.55 | 84.96 | 87.54 | 87.18 | -
Prune Rate | Width Factor | Algorithm | Conv2 | Conv4 | Conv6 | Conv8
---|---|---|---|---|---|---
0.2 | 1 | Biprop | 64.1 | 74.71 | 78.2 | 76.59
IteRand | 56 | 57.9 | 59.6 | 49.84
Weight Recycle | 80.28 | 88.05 | 90.2 | 90.35
0.4 | 1 | Biprop | 78.3 | 85.9 | 88.9 | 89.13
IteRand | 65 | 73.3 | 75 | 75.14
Weight Recycle | 81.2 | 88.8 | 90.8 | 90.93
0.5 | 1 | Biprop | 79.56 | 87.42 | 89.52 | 90.35
IteRand | 65.3 | 74 | 77 | 77.61
Weight Recycle | 81.36 | 88.91 | 90.9 | 91
0.6 | 1 | Biprop | 79.98 | 87.2 | 90.25 | 90.54
IteRand | 65.72 | 74.13 | 76.2 | 78.9
Weight Recycle | 81.36 | 88.64 | 90.6 | 90.85
0.8 | 1 | Biprop | 77.9 | 85.34 | 87.5 | 89.11
IteRand | 58.9 | 67.1 | 71.2 | 76.72
Weight Recycle | 80.23 | 87.75 | 90 | 90.55
0.9 | 1 | Biprop | 70.1 | 79 | 82.38 | 84.84
IteRand | 50 | 54 | 61 | 52
Weight Recycle | 76.9 | 84.3 | 85.5 | 86.4
0.95 | 1 | Biprop | 56.6 | 64.83 | 66.12 | -
IteRand | 38.78 | 45.91 | 49.2 | -
Weight Recycle | 65.11 | 73.5 | 72.11 | -
0.5 | 0.1 | Biprop | 47.2 | 50.4 | 56.9 | 61.2
IteRand | 41 | 42.8 | 43 | 44.3
Weight Recycle | 52.55 | 59.64 | 65 | 69
0.5 | 0.25 | Biprop | 64.55 | 73.23 | 77.84 | 80.4
IteRand | 53 | 57.5 | 60.4 | 62.5
Weight Recycle | 68.8 | 78.51 | 82 | 84.5
0.5 | 0.5 | Biprop | 74.69 | 82.6 | 86.23 | 87.33
IteRand | 60.5 | 67.3 | 70.4 | 70.3
Weight Recycle | 76.7 | 86.5 | 88.43 | 89.67
Table 4: Binary neural networks Biprop, Biprop+IteRand,Biprop+Iterative Weight Recycling results. Weight recycle accuracy averaged across three runs. Best result bolded for each experiment. Notably, Weight Recycling performs best across all algorithms, and is robust to higher prune rates.  Prune Rate | Width Factor | Algorithm | Conv2 | Conv4 | Conv6 | Conv8
---|---|---|---|---|---|---
0.2 | 1 | Edge-Popup | 70.1 | 77.6 | 83 | 84.39
IteRand | 80.7 | 88.4 | 90.58 | 90.99
Weight Recycle | 81.05 | 88.95 | 91.1 | 91.15
0.4 | 1 | Edge-Popup | 78.6 | 86.74 | 89.33 | 90.15
IteRand | 81.3 | 89.2 | 91.1 | 91.55
Weight Recycle | 81.8 | 89.2 | 91.2 | 91.5
0.5 | 1 | Edge-Popup | 79.69 | 86.67 | 89.53 | 90.28
IteRand | 81.83 | 88.37 | 90.74 | 91.11
Weight Recycle | 81.68 | 88.5 | 90.9 | 91.36
0.6 | 1 | Edge-Popup | 79.1 | 86.43 | 89.1 | 90.5
IteRand | 81.75 | 87.66 | 90 | 91.16
Weight Recycle | 81.12 | 88.15 | 90.4 | 90.95
0.8 | 1 | Edge-Popup | 75.15 | 83.28 | 85.4 | 86.9
IteRand | 78.04 | 85.34 | 86.94 | 88.42
Weight Recycle | 79.06 | 85.6 | 87.13 | 88.87
0.9 | 1 | Edge-Popup | 64.05 | 74.42 | 79.57 | 83.6
IteRand | 68.87 | 78.88 | 81.22 | 84.73
Weight Recycle | 70.22 | 79.78 | 83.2 | 86.93
0.95 | 1 | Edge-Popup | 49.4 | 57.61 | 60.63 | 76.7
IteRand | 53.5 | 64.72 | 68.8 | 81.66
Weight Recycle | 55.2 | 65.22 | 68.02 | 81.51
0.5 | 0.1 | Edge-Popup | 48.1 | 50.73 | 57.3 | 63.35
IteRand | 55.2 | 59.3 | 64.5 | 71.56
Weight Recycle | 53.4 | 59.82 | 64.1 | 70
0.5 | 0.25 | Edge-Popup | 72.49 | 73.34 | 78.48 | 81.5
IteRand | 70.5 | 78.91 | 83 | 85.5
Weight Recycle | 70.33 | 78.92 | 83 | 85.5
0.5 | 0.5 | Edge-Popup | 77.55 | 82.08 | 86.24 | 87.92
IteRand | 78 | 85.45 | 88.18 | 87.99
Weight Recycle | 77 | 85.63 | 88.57 | 89.73
Table 5: Randomly Initialized Neural Networks Edge-Popup, Edge-Popup+IteRand,
Edge-Popup+Iterative Weight Recycling results. Weight recycle accuracy
averaged across three runs. Best result bolded for each experiment. Notably,
at prune rates above 80%, weight recycling outperforms all algorithms.  Figure
7: Comparison of Edge-Popup, IteRand, and Weight Recycling using continuous
valued weights with signed constant initialization. In this figure, we vary
the model depth.  Figure 8: Comparison of Edge-Popup, IteRand, and Weight
Recycling using continuous valued weights with signed constant initialization.
In this figure, we vary the model width.

##  Appendix D MPT Analysis

In Section ”Winning Tickets Galore”, we show that an abundance of MPT’s
(winning tickets) exist in randomly initialized neural networks. We analyze
MPT’s in both randomly initialized neural networks using Edge-Popup as well as
binary randomly initialized networks using Biprop. We train 15 Edge-Popup
models and 15 Biprop models with a Conv-6 model at 50% prune rate, and 5
models of each algorithm at both a 75% and 90% prune rate (using Conv-6).

We restrict the hyperparameters of each run to measure the differences of the
generated subnetworks. The only hyperparameter that is changed is the score
parameter seed, which is set to values 0 to 14 for 50% prune rate, and 0 to 4
for 75% and 90% prune rates. The rest of the hyperparameters are defined as
follows:

  1. 1.

SGD optimizer, learning rate 0.1

  2. 2.

Weight decay 1e-4, momentum 0.9

  3. 3.

250 Epochs, Batch size 128

  4. 4.

Batch Size=128

  5. 5.

Weight initialization: Signed constant for Edge-Popup, Kaiming Normal for
Biprop

  6. 6.

All random seeds set to 0: python random library, torch manual seed, torch
cuda manual seed, torch cuda manual seed all

  7. 7.

torch.backends.cudnn.deterministic = True

  8. 8.

torch dataloader: worker_init_fn=np.random.seed(0)

  9. 9.

Weight Seed=0

We measure the SMC and JI of each model combination. The figures below
summarize the SMC and JI for combinations at 50% and 75% prune rate.

Figure 9:  Heatmap of Simple Matching Coefficients of Binary Masks across
models.

Figure 10: Jaccard Index at 75% prune rate.

Figure 11: SMC at 75% prune rate.