Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network
Authors: James Diffenderfer
Bhavya Kailkhura
Venue: ICLR 2021 Poster (2021)
Keywords: Binary Neural Networks
Pruning
Lottery Ticket Hypothesis

Abstract: Recently, Frankle & Carbin (2019) demonstrated that randomly-initialized dense networks contain subnetworks that once found can be trained to reach test accuracy comparable to the trained dense network. However, finding these high performing trainable subnetworks is expensive, requiring iterative process of training and pruning weights. In this paper, we propose (and prove) a stronger Multi-Prize Lottery Ticket Hypothesis:

A sufficiently over-parameterized neural network with random weights contains several subnetworks (winning tickets) that (a) have comparable accuracy to a dense target network with learned weights (prize 1), (b) do not require any further training to achieve prize 1 (prize 2), and (c) is robust to extreme forms of quantization (i.e., binary weights and/or activation) (prize 3).

This provides a new paradigm for learning compact yet highly accurate binary neural networks simply by pruning and quantizing randomly weighted full precision neural networks. We also propose an algorithm for finding multi-prize tickets (MPTs) and test it by performing a series of experiments on CIFAR-10 and ImageNet datasets. Empirical results indicate that as models grow deeper and wider, multi-prize tickets start to reach similar (and sometimes even higher) test accuracy compared to their significantly larger and full-precision counterparts that have been weight-trained. Without ever updating the weight values, our MPTs-1/32 not only set new binary weight network state-of-the-art (SOTA) Top-1 accuracy -- 94.8% on CIFAR-10 and 74.03% on ImageNet -- but also outperform their full-precision counterparts by 1.78% and 0.76%, respectively. Further, our MPT-1/1 achieves SOTA Top-1 accuracy (91.9%) for binary neural networks on CIFAR-10. Code and pre-trained models are available at: https://github.com/chrundle/biprop.

Published as a conference paper at ICLR 2021
Multi-Prize Lottery Ticket Hypothesis:
FINDING ACCURATE BINARY NEURAL NETWORKS BY PRUNING A RANDOMLY WEIGHTED NETWORK
James Diffenderfer & Bhavya Kailkhura Center for Applied Scientific Computing Lawrence Livermore National Laboratory Livermore, CA 94550, USA {di ffenderfere, kai maailkhuree khural J
ABSTRACT
Recently, |Frankle & Carbin (2019) demonstrated that randomly-initialized dense networks contain subnetworks that once found can be trained to reach test accu- racy comparable to the trained dense network. However, finding these high per- forming trainable subnetworks is expensive, requiring iterative process of training and pruming weights. In this paper, we propose (and prove) a stronger Multi-Prize Lottery Ticket Hypothesis:
A sufficiently over-parameterize neural network with random weights contains several subnetworks (winning tickets) that (a) have comparable accuracy a dense target network with learned weights (prize 1), (b) do not require any fur- ther training to achieve prize 1 (prize 2). and (c) robust to extreme forms of quantization (i.e., binary weights and/or activation) (prize 3).
This provides a new paradigm for learning compact yet highly accurate binary neural networks simply by pruming and quantizing randomly weighted full pre- cision neural networks. We also propose an algorithm for finding multi-prize CIFAR-10
tickets (MPT's and test it by performing series of experiments and ImageNet datasets. Empirical results indicate that as models grow deeper higher)
and wider, multi-prize tickets start to reach similar (and sometimes test accuracy compared to their significantly larger and full-precision counter- parts that have been weight-trained. Without ever updating the weight values, our MPTs 1/32 not only set new binary weight network state-of-the-an (SOTA) Top-1 accuracy 94.8% on CIFAR-10 10 and 74.03% on ImageNet but also out- perform their full-precision counterparts by 1.78% and 0.76%, respectively. Fur- ther, our MPT-1/1 achieves SOTA Top-1 accuracy (91.9%) for binary neural net- works CIFAR-10. Code and pre-trained models are available at: https: 7/github. com/ www.hcleeeiiuproooo
INTRODUCTION
Deep learning (DL) has made significant breakthroughs in wide range of applications (Goodfel- low et al., (016). These performance improvements can be attributed to the significant growth in the model size and the availability of massive computational resources train such models. Therefore, these gains have come at the cost of large memory consumption, high inference time, and increased power consumption. This not only limits the potential applications where DI. can make an impact but also have some serious consequences, such as, (a) generating huge carbon footprint, and (b) creating roadblocks to the democratization of AI. Note that significant parameter redundancy and a large number of floating-pon point operations are key factors incurring the these costs. Thus, for discard- ing the redundancy from DNNs, one can either (a) Prune: remove non-essential connections from an existing dense network, (b) Quantize: constrain the full-precision (FP) weight and activation values to set of discrete values which allows them to represented using fewer bits. Further, one can exploit the complementary nature of pruning and quantization combine their strengths.

---

Published as a conference paper at ICLR 2021
Memory Savings
Comp. Savings
Configuration
Model
Weights
Params
Accuracy
ImageNet CIFAR-10 10
Dense (32/32)
ResNet18
Learned
1x
1x
11.2 M
33.02%
ProxQuant (1/32)
ResNet56
Learned
32x
~2
0.85
92.3%
MPT (1/32)
ResNet18
Pruned
322
~2x
2.2 M
94.8%
Dense (32/32)
ResNet34
Learned
1x
1x
21.8 M
73 73.27%
Quant-Net Net (1/32)
ResNet50
Learned
~x2
xx2x
72.8%
MPT (1/32)
WRN-50
Pruned
~32
2x
13.7 M
74.03%
Figure I: Multi-Prize Ticket Performance: Multi-prize tickets, obtained only by pruning and binarizing random networks, outperforms trained full precision and SOTA binary weight networks.
Although pruning and quantization are typical approaches used for compressing DNNs (Neill, 2020), it is not clear under what conditions and what extent compression can be achieved with- out sacrificing the accuracy. The most extreme form of quanitization is binarization, where weights and/or activations can only have two possible values, namely - 1()) or +1 (the interest of this paper). In addition to saving memory, binarization results in more power efficient networks with significant computation acceleration since expensive multiply-acee auttiply-accumulate operations (MACs) can be replaced by cheap XNOR and bit-counting operations (Qin et al.) 2020a). In light of these benefits, it is of in- terest question if conditions exists such that a binarized DNN can be pruned achieve accuracy comparable to the dense FP DNN. More importantly, even if these favourable conditions are met then how do we find these extremely compressed (or compact) and highly accurate subnetworks?
Traditional pruning schemes have shown that a pretrained DNN can be pruned without significant loss the performance. Recently, (Frankle & Carbin 2019) made a breakthrough by showing that dense network contain sparse subnetworks that can match the performance of the original network when trained from scratch with weights being reset to their initialization (Lottery Ticket Hypothesis). Although the original approach to find these subnetworks still required training the dense network, some efforts (Wang et al.) 2020b You et al., 2019 Wang et al., 2020a) have been carried out to overcome this limitation. Recently more intriguing phenomenon has been reported dense network with random initialization contains subnetworks that achieve high accuracy. without any further training (Zhou al.
Orseau al., 2020 These trends highlight good progress being made towards efficiently and accurately pruning DNNs.
2019 Ramanujan al. 2020 Malach et al.
In contrast to these positive developments for pruning, results binarizing DNNs have been mostly negative. To the best of our knowledge, post-training schemes have not been successful in binariz- ing pretrained models without retraining. Even with training binary neural networks (BNNs) from scratch (though inefficient), the community has not been able to make BNNs achieve compara- ble results to their full precision counterparts. The main reason being that network structures and weight optimization techniques are predominantly developed for full precision DNNs and may not be suitable for training BNNs. Thus, closing the gap accuracy between the full precision and the binarized version may require paradigm shift. Furthermore, this also makes one wonder if efficiently and accurately binarizing DNNs similar to the recent trends in pruning is ever feasible.
In this paper, we show that randomly initialized dense network contains extremely sparse binary subnetworks that without any weight training (i.c., efficient) have comparable performance to their trained dense and full- precision counterparts (i.c., accurate). Based on this, state our hypothesis:
Multi-Prize Lottery Ticket Hypothesis. A sufficiently over-parameterized neural network with random weights contains several subnetworks (winning tickets) that (a) have comparable ac- curacy to dense target network with learned weights (prize 1), (b) do not require any further training to achieve prize 1 (prize 2), and (c) robust to extreme forms of quantization (i.e., binary weights and/or activation) (prize 3).
Contributions.
First, we propose the multi-prize lottery ticket hypothesis as a new perspective on finding neural networks with drastically reduced memory size, much faster test-time inference and
A detailed discussion related work pruning and quantization is provided in Appendix F
2

---

Published as a conference paper at ICLR 2021
lower power consumption compared to their dense and full- full-precision counterparts. Next, we pro- vide theoretical evidence of the existence of highly accurate binary subnetworks within a randomly weighted DNN (i.e., proving the multi lottery ticket hypothesis). Specifically. we mathemati- cally prove that we can find an e-approximation of a fully-connected ReL.U DNN with width n and depth é using sparse binary-weight DNN of sufficient width. Our proof indicates that this can be accomplished by pruning and binarizing the weights of a randomly weighted neural network that is a factor ((///2 wider and 2 deeper. To the best of our knowledge, this is the first theoretical work proving the existence of highly accurate binary subnetworks within sufficiently overparame- terized randomly initialized neural network. Finally, we provide biprop (binarize-pruus in Algorithm to identify MPTs within randomly weighted DNNs and empirically test our hypoth- esis. This provides a completely new way to learn BNNs without relying on
optimizer)
Results. We explore two variants of multi- prize tickets - one with binary weights (MPT-1/32) and other with binary weights and activation (MPT-1/1) where z/y denotes and y bits to represent weights and activation, respectively. MPTs we find have 60 80% fewer parameters than the original network. We perform series of experiments recognition, namely CIFAR-10 (Krizhessky et al., 2009) and ImageNet (Deng et al., 2009). On CIFAR-10, we test the performance of multi-prize tickets against the trend of making the model deeper and wider. We found that as models grow deeper and wider, both variants of multi-prize tickets start reach similar (and sometimes even higher) test accuracy compared the dense and full precision original network with learned weights. In other words, the performance of multi- prize tickets improves with the amount of redundancy in the original network. We also carry out experiments with ofte-of-theeart (SOTA) architectures an aim to investigate their redundancy. We find that within most randomly weighted SOTA DNNs reside extremely compact (i.e., sparse and binary) subnetworks which are smaller than, but match the performance of trained target dense and full precision networks. Furthermore, with minimal hyperparameter tuning, our MPTs achieve Top-1 accuracy comparable to (or higher than) SOTA BNNs. The performance of MPTs is further improved by allowing the parameters in BatchNorm layer to be learned. Finally, on both CIFAR-10 and ImageNet, MPT-1/32 subnetworks outperform their significantly larger and full-precision counterparts that have been weight-trained.
small and large scale datasets for image
CIFAR-10 10 and ImageNet datasets with
2 MULTI-PRIZE LOTTERY TICKETS: THEORY AND ALGORIHTMM
We first prove the existence of MPTs in an overparameterized randomly weighted DNN. For ease of presentation, we state an informal version of Theorem 2 which can be found in Appendix We then explore two variants of tickets (MPT-1/32 and MPT-1/1) and provide algorithm to find them.
2.1 PROVING THE MULTI- LOTTERY TICKETS HYPOTHESIS
In this section we seek to answer the following question: What is the required amount of over- parameterization such that a randomly weighted neural network can be compressed to a sparse binary subnetwork that approximates a dense trained target network?
Theorem 1. (Informal Statement of Theorem 2 Let E,8 8 > O. For every fully-connected (FC) target network with ReLU activations of depth and width n with bounded weights, a random binary FC network with ReLU activations of depth 2l and width O ((en3/2/e) /E) + En log( (En/)) contains with probability (1 1--)) binary subnetwork that approximates the target network with error at most e.
(W))))), where a (x) ma, x E Rd. w E R ky = d, and E [A. Additionally, consider a FC network with binary weights given by G(z) = B())) (-1,+1)%xx, Kg d, and i E [e]. Our goal is to determine a lower bound on the depth, e", and the widths, (K() such that with probability (1 - 6) the network G(æ)) contains a subnetwork ((x)) satisfying [|G(z) F(x)]| < c, for any E 0 and 5 (0, 1). We first establish lower bounds the width of a network of the form g(x)
Sketch of Proof. Consider a FC ReLU network F(x) = ( a
(B (B(('-)) 11. o (B()))) where B() e
such that with probability
(1 - 8') there exists a subnetwork g(x) of g(æ) s.t. [lğ(z) (WW)) < E', for any e' >> 0 and
8' (0. 1). This process is carried out in detail in Lemmas and 3 in Appendix B We have
3

---

Published as a conference paper at ICLR 2021
now approximated single layer FC real-valued network using subnetwork of a two-layer FC binary network. Hence, we can take E' = 2 and Lemma 1ommaBpprove provides lower bounds on the width of each intermediate layer such that with probability (1 - 5) there exists a subnetwork G(x) of G(z)
satisfying [G(x)) - F & E. This is accomplished in Theorem in Appendix B
To the best of our knowledge this is the first theoretical result proving that sparse binghy-weight DNN that can approximate a real-valued target DNN. As it has been established that real-valued DNNs are universal approximators (Scarselli & Tsoi 1998), our result carries the implication that sparse binary-weight DNNs are also universal approximators. In relation to the first result establish- ing the existence of real-valued subnetworks in a randomly weighted DNN approximating a real- valued target DNN (Malach et al. 2020), the lower bound on the width established in Theorem 2 is better than their lower bound of O (L'n log(En/6)//e).
2.2 FINDING MULTI-PRIZE WINNING TICKETS
Given the existence of multi-prize winning tickets from Theorem 2 a natural question arises- - How should we find them? In this section, answer this question by introducing algorithm for finding multi-prize tickets Specifically, we explore two variants of multi-prize tickets in this paper - 1) MPT-1/32 where weights are quantized to 1-bit with activations being real valued (i.e., 32-bits) and 2) MPT-1/1 where both weights and activations are quantized to 1-bit. We first outline a generic process for identifying MPTs along with some theoretical motivation for our approach.
Given a neural network g(x: W) with weights W E R", we can express a subnetwork of using a binary mask M E {0. 1 jm as g(x; M ④ W). where a denotes the Hadamard product. Hence, a binary subnetwork can be expressed as g ( M & B), where B E {-1, +1)0.. Lemma [ in Ap- pendix B indicates that rescaling the binary weights to {-a, a)} using a gain term a E R is necessary to achieve good performance of the resulting subnetwork. We note that the use of gain terms is com- mon in binary neural networks (Qin et al. [020aa] Martinez et al., 2020 Bulat & Tzimiropoulos 2019) Combining all this allows us to represent a binary subnetwork g(
O B)).
Now we focus on how to update M, B, and a. Suppose (ax; W*) is target network with opti- mized weights n that we wish to approximate. Assuming g (z;:)) is k-Lipschitz continuous yields
lg (I:; (M @ B)) - f(a: W S x @ (W-oBB) -ww-olll
[g((;; M W fax W')
MPT
Rintrization error
Suhnetwoek error
Hence, the MPT error is bounded above by the error of the subnetwork of g with the original weights and the error from binarizing the current subnetwork. This informs our approach for identifying MPTs: 1) Update pruning mask M that reduces the subnetwork eгror (lines 7 9 in Algorithm D. and 2) apply binarization with a gain term that minimizes the binarization error (lines 4 and 10).
We first discuss how to update M. While we could search for M by minimizing the subnetwork error in ( this would require the use of a pretrained target network (i.e., f(æ; W*)). To avoid requiring target network in our method we instead aim to minimize the training loss w.r.t. M in the current binary subnetwork. Directly optimizing over the pruning mask is a combinatorial problem. So to update the pruning mask efficiently we optimize over set of scores S E I corresponding to each randomly initialized weight in the network. In this approach, each component of the randomly initialized weights is assigned pruning score. The pruming scores updated via backpropagation by computing the gradient of the loss function over minibatches with respect to the pruning scores (line 7). Then the magnitude of the scores in absolute value are used identify the P percent of weights in each layer that are least important to the success of the binary subnetwork (line 8). The components of the pruning mask corresponding to these indices are set 0 and the remaining components are set to 1 (line 9). To avoid unintentionally pruning an entire layer of the network, we use pruning mask for each layer that prunes P percent of the weights in that layer. The choice to use pruning scores to update the mask M was due to the fact that it is computationally efficient. The eslbbistabl optimization technique used in a range of applications (Johhi & Boyd 2009 Ramanujan et al. 2020).
use of pruming scores
Although our results are derived under certain assumptions (e.g., fully-connected, ReL. neural network approximated by subnetwork with binary weights), our algorithm is restricted by these assumptions.
4

---

Published as a conference paper at ICLR 2021
Algorithm biprop: Finding multi-prize tickets in randomly weighted neural network
1: Input: Neural network g(;;)) with 1- or 32-bit activations; Network depth &: Layer widths
f:lj=iLLss function L; Training data {(x11, (y())) ) Pruning percentage P.
2: Randomly Initialize FP Parameters: Network weights ( (W 13=13 Pruning scores (SU) j=1-
3: Initialize Layerwise Pruning Masks: (M 1/=1 each to 1.
4: Initialize Binary Subnetwork Weights: {B 1j=1 + (sign(
5: Initialize Layerwise Gain Terms: {a 1 + (1]M & w |
6: for k = to N Nepoche do
7: 5(1) 5(5) Lgg @ B
Update pruning scores at layer j
8:
{T(1)) Sorting of indices (1) s.t. (5
(S
7(+11) Index values |
r())
9: MD - 11022111, (i)
Update pruning mask at layer j
10:
a + |M O ((1l//MMM
Update gain term at layer j
11:
Output: Return Binarized Subnetwork g(æ; (a()( o B
We now consider how update B and By keeping M fixed, we can derive the following closed form expressions that minimize the binarization error in [ B = These closed form expressions indicate that only the gain term needs to be recomputed after each update to M. Hence, B sign( W) throughout our entire approach (line 4). We update a gain term for each layer of the subnetwork in our approach based on the formula for a" (line 10). More details on the derivation of B and a are provided in Appendix C
sign( and a"
|| C | ||1.
Pseudocode for our method biprop (binarize- prune optimizer) is provided in Algorithm [and cross- entropy loss is used in our experiments. Note that the process for identifying MPT-1/32 and MPT-1/1 differs only in computation of the gradient. Next, we explain how these gradients can be computed.
2.2.1 UPDATING PRUNING SCORES FOR BINARY- WEIGHT TICKETS (MPT-1/32)
As an example, for FC network where the state at each layer is defined recursively by U (B(( @ MZ and UG) a B o (U we have ar.
as
aL au()) aM())
We use the straight- estimator (Bengio al. 2013) for aMU
which
as
yields AL =
DL a Bl)) a (U) where OL is computed via backpropagation. auti
asp)
2.2.2 UPDATING PRUNING SCORES FOR BINARY- TICKETS (MPT-1/1)
Note that MPT-1/1 uses the sign activation function. From Section
2.2.1 it immediately follows that 01 via backpropagation requires
0L
0L 80 ( B.g sign ( (U)-"). However, updating a0:!3
(i)
gradient estimator for the sign activation function. To motivate our choice of estimator note that we
can approximate the sign function using a quadratic spline parameterized by some 0:
a1 (z)
: x -t
(x(x)
(2)
(2(2z) (z)
x 0,t)
x x2
In 2 (x) ax² + b,r + q; and suitable values for the coefficients are derived using the following zero- and first-order constraints: (-(=t) = -1, (0) = 0, 92 (2) 0, (2(t) = 1, (-t) (0) = (0). and (t) 0. This yields (z)
(z/t)2 2(z/t) and (2(2) = 2 + ((x/(). As (z approximates sign(r), we can use s((x) our gra- dient estimator. Since (x) (1 + +) and (x(x) = (1 - )) it follows that s((x) =
? (1- (4 1 (0) The choice to approximate sign using a quadratic spline instead of cubic spline results in gradient estimator that be implemented efficiently in PyTorh
5

---

Published as a conference paper at ICLR 2021
torch. cl (2* (1-torch. abs (x) /t) mt,ni..0000 We note that lime-+0 sx(2) sign(z), which suggests that smaller values of t yield more suitable approximations. Our experi- ments use si (a) as the gradient estimator since found it to work well in practice. Finally, note that taking = in our gradient estimator yields the same value as the gradient estimator in (Liu et al. 201 8a), however, our implementation in PyTorch is 6x more memory efficient.
EXPERIMENTAL RESULTS
The primary goal of the experiments in Section 3.1 is empirically verify our Multi-Prize Lot- tery Ticket Hypothesis. As a secondary objective, we would like to determine tunable factors that make randomly-initialized networks amenable to containing readily identifiable Multi-Prize Tickets (MPTs). Thus, we test our hypothesis against the general trend of increasing the model size (depth and width) and monitor the accuracy of the identified MPTs. After verifying our Multi-Pres Prize Lottery Ticket Hypothesis.
consider the performance of MPTs compared to state-of-the-arty in binary neural networks and their dense counterparts on CIFAR-10 and ImageNet datasets in Section 3.2 Building upon edge-popup (Ramanujan et al. 2020 we implement Algorithm 1 to identify MPTs
3.1 WHERE CAN WE EXPECT TO FIND MUL.TI-RRIZE TICKETS?
In this section, we empirically test the effect of overparameterization on the performance of MPTs. We overparameterize networks by making them (a) deeper (Sec. 3.1.1 and (b) wider (Sec. 3.1.2).
Conv-2
Cony-4
Conv-6
Cony-8
40
CIFA-10 Top-1 Accuraty
as
80
75
75
75
20
65
80
60
10
50
60
30
80
50
40
70
Perceetage
Weeights
(Pruncdi
Dence
Weighes)
Figure 2: Effect of Varying Depth and Pruning Rate: Comparing the Top-1 accuracy of small and binary MPTs to a large, full- full-precision, and weight-optimized network on CIFAR-10.
We use VGG (Simonyan & Zisserman, 2014) variants as our network architectures for searching for MPTs. In each randomly weighted network, we find winning tickets MPT-1/32 and MPT-1/1 for different pruning rates using Algorithm I We choose our baselines as dense full-precision models with learned weights. In all experiments, average of Top-1 accuracy with with error bars extending to the lowest and highest Top-1 accuracy. Additional experiment configuration details provided in Appendix A
three independent initializations and report the
3.1.1 Do WINNING TICKETS EXIST IN DEEP NETWORKS?
In this experiment, we empirically test the following hypothesis: As a network grows deeper, the per- formance of multi-prize tickets in the randomly initialized network will approach the performance of the same network with learned weights. We are further interested in exploring the required network depth for our hypothesis to true.
In Figure 2 vary the depth of VGG architectures (d to 8) and compare the Top-1 accuracy of MPTs (at different pruning rates) with weight- trained dense network. We notice that there exist range of pruming rates where the performance of MPTs are very similar, and beyond this range the performance drops quickly. Interestingly, as the network depth increases, more parameters can be pruned without hurting the performance of MPTs. For example, MPT-1/32 can match the per- formance of trained Conv-8 while having only 20% of its parameter count. Interestingly, the
A comparison of MPT-1/32 found using biprop and edgepopup is provided in Appendix which demon- strates that hiprop outperforms edgepopup.

---

Published as a conference paper at ICLR 2021
Conv-4
Conv-8
CIFRR-10 Top-1 Accuracy
90
90
90
225
80
80
75
75
75
70
65-
65
65
0.5
2.0
1.5
2.0
0.3
Width
Weight))
Figure 3: Effect of Varying Width MPT--132: Comparing the Top-1 accuracy of sparse and binary MPT-1/32 to dense, full-precision, and weight-optimized network on CIFAR-10.
performance gap between MPT-1/32 and MPT-1/1 does not change much with depth across differ- ent pruning rates. We further note that the performance of MPTs improve when increasing the depth and both start to approach the performance of the dense model with learned weights. This gain starts to plateau beyond a certain depth, suggesting that the MPTs might be approaching the limit of their achievable accuracy. Surprisingly, MPT- 1/32 performs equally good (or better) than the weight-trained model regardless of having 50 80% lesser parameters and weights being binarized.
3.1.2 Do WINNING TICKETS EXIST IN WIDE NETWORKS?
Conv-4
Cony-6
Conv-8
CIFAR-10 Top-1 Accuracy
90
80
80
80
75
20
65
65
65
0.5
1.0
2,0
0.5
3.0
1.5
2.0
0.5
1.0
2.0
Layer (Prune 93%)
Layer Factor
Layer
MPT-11 (Prune 80%)
+ (huns 60%)
(Leamed Weigtts)
Figure 4: Effect of Varying Width MPT-1/1: Comparing the Top-1 accuracy of sparse and binary MPT-1/1 to dense, full-precision, and weight-optimized network on CIFAR-10.
Similar to the previous experiment, in this experiment, empirically test the following hypothesis: As a network grows wider, the performance of multi-prize prize tickets in the randomly initialized network will approach the performance of the same network with learned weights. We are further interested in exploring the required layer width for our hypothesis to be true.
In Figures 3 annd 4
vary the width of different VGG architectures and compare the Top-1 accuracy of MPT-1/32 and 1PT-1/1 tickets (at different pruning rates) with weight-trained dense network. A width multiplier of value 1 corresponds
the models in Figure 2 Performance of all the models improves when increasing the width and the performance of both MPT-1/32 and MPT-1/1 start to approach the performance of the dense model with learned weights. Although, this gain starts to plateau beyond a certain width. For both MPT-1/32 and MPT-1/1, as the width and depth increase the performance at different pruning rates approach the same value. This observed phenomenon yields more significant gain in the performance for MPTss with higher pruning rates. Similar to the previous experiment, the performance of MPT-1/33 matches (or exceeds) the performance of dense models for a large range of pruning rates. Furthermore, in the high width regime, large number of weights (~ 90%) can be pruned without having a noticeable impact on the performance MPTs. We also notice that the performance gap between MPT- 1/32 and MPT-1/1 decreases significantly with an increase the width which is in sharp contrast with the with the depth experiments where the performance gap between MPT-1/32 and MPT-1/1 appeared to be largely independent of the depth.
7

---

Published as a conference paper at ICLR 2021
Key Takeaways. Our experiments verify Multi-Prizz Lottery Ticket Hypothesis and additionally convey the significance of choosing appropriate network depth and layer width for a given pruning rate. In particular, we find that network with a large width can be pruned more aggressively without sacrificing much accuracy, while the accuracy of a network with smaller widths suffers when pruning large percentage of the weights. Similar patterns hold for the depth of the networks well. The amount of overparametrization needed to approach the performance of dense networks seems to differ for MPT variants- MPT-1/1 requires higher depth and width compared MPT-1/32.
3.2 HOW REDUNDANT ARE STATE-OF-THE--RR DEEP NEURAL NETWORKS?
Having shown that MPTs can perform equally good (or better) than overparameterized networks, this experiment aims to answer: Are sute-offthe-art weight-trained DNNs overparametrized enough that significantly smaller multi-prize tickets can match (or beat) their performance?
Experimental Configuration. Instead of focusing on extremely large DNNs, we experiment with small to moderate size DNNs. Specifically, we analyze the redundancy of following backbone models: (1) VGG-Small and ResNet-18 on CIFAR-IO, and (2) WedeRes and WedeResNet- 50 on ImageNet. As we will show later that even these models are highly redundant, thus, our finding automatically extends to larger models. In this process. we also perform comprehensive comparison of the performance of our multi-prize winning tickets with offte-of-theaarr in binary neural networks (BNNs). Details on the experimental configuration are provided in Appendix
This experiment uses Algorithm | to find MPTs within randomly initialized backbone networks. We compare the Top-1 accuracy and number of non-zero parameters for our MPT-1/32 and MPT- 1/1 tickets with selected baselines in BNNs (Qin et al. (2020a). Results for CIFAR-10 and ImageNet are shown in Tables [ 2 and Tables
respectively. Next to each MPT method we include the percentage of weights pruned in parentheses. Motivated by (Frankle et al., 2020), we also include models in which the BatchNorm parameters are learned when identifying the random subnetwork using biprop, indicated by +BN. A more comprchensive comparison can be found in Appendix D
Method
Model
Top-1
Params
Method
Model
Top-1
Params
BinaryConneet
VGG-Small
91.7
4.6 M
BNN
VGG-Small
89.9
4.6
ProxQuam
ResNet-56
92.3
0.85
XNOR-Net
VGG-Small
'8.88
4.6
DSQ
ResNet-20
90.2
0.27 M
DSQ
VGG-Small
91.77
4.6 M
IR-Net
ResNei-20
90.8
0.27 M
IR-Net
ResNet-18
"9..5
11.2 M
Full- full-Precision
ResNet-
93.02
11.2
fall-Precision
VGG-Small
93.6
4.6
MPT (80)
ResNct-18 18
94.66
2.2 M
MPT (75)
VGG-Small
88.52
1.44 M
MPT (80) +BN
R8
94.8
2.2 M
MPT (75) +BN
VGG-Small
91.9
1.44 M
Table 1: Comparison of MPT-1/32 with
Table 2:
Comparison MPT-1/1 with
trained binary- 1/32 networks on CIFAR-10.
trained binary- 1/1 networks CIFAR-10.
Method
Model
Top-1
Params
Method
Model
Top-1
Params
ABC-Net
ResNet-18
62.8
11.2 M
BNN
AlexNet
27.9
62.3
BWN
ResNet-18
60.8
11.2 M
XNOR Net
AlexNet
44.2
62.3 M
IR-Net
ResNet-34
70.4
21.8 M
ABC-Net
ResNet-34
52.4
21.8 M
Que
ResNet-50
72.8
225.6 M
TR-Net
Res
62.9
2T.8 M
Hull-Precision
ResNer-34 34
73.27
21.8 M
Full- Precision
ResNet- 34
73.27
"2.8 M
MPT (80)
WRN-50
72.67
13.7 M
MPT (60)
WRN-34
45.06
19.3 M
MPT (80) +BN
WRN-50
74.03
13.7 M
MPT (60) +BN
WRN-34
52.07
19.3 M
Table 3: Comparison of MPT-1/32 with
Table 4: Comparison of MPT-1/1 with
trained bi32 networks on ImageNet.
trained binary-1/1 networks on ImageNet.
Our results highlight that SOTA DNN models are extremely redundant. For similar parameter count, binary MPT-1/32 models outperform even full precision models with learned weights. When compared to state-of-the--e BNNss with minimal hyperparameter tuning our multi-prize tick- ets achieve comparable (or higher) Top-1 accuracy. Specifically, our MPT-1/32 outperform trained
8

---

Published as a conference paper at ICLR 2021
binary weight networks CIFAR-10 and ImageNet and our MPT-1/1 outperforms trained binary weight and activation networks on CIFAR-10 10. Further, on CIFAR-10 and ImageNet, MPT-1/32 net- works with significantly reduced parameter counts outperform dense and full precision networks with learned weights. Searches for MPT-1/1 in BNN-specific architectures (Kim et al. 2020 Bulat et al., 2020a) and adopting other commonly used tricks improve model & representation capac- ities (Bulat et al. 2020b;; Yang et al.) 2020 Lin et al.) 2020; 2021) are likely to yield MPT-1/1 networks with improved performance. For example, up to a 7% gain in the MPT-1/1 accuracy was achieved by simply allowing BatchNorm parameters to be updated. Additionally, alternative approaches for updating the pruning mask in biprop could alleviate issues with back- propapropaggting gradients through binary activation networks.
4 DISCUSSION AND IMPLICATIONS
Existing compression approaches (e.g., pruning and binarization) typically rely on some form of weight-training, This paper showed that a sufficiently overparametrized randomly weighted network contains binary subnetworks that achieve high accuracy (comparable to dense and full precision original network with learned weights) without any training. We referred to this finding as the Multi-Prit Prize Lottery Ticket Hypothesis. We also proved the existence of such winning tickets and presented generic procedure to find them. Our comparison with state-of-the-aar neural networks corroborated our hypothesis. With minimal hyperparameter tuning, our binary weight multi-prize tickets outperformed current state-of-the-art in BNNs and proved its practical importance. Our work has several important practical and theoretical implications.
Algorithmic. Our biprop framework enjoys certain advantages over traditional weight- optimization. First, contemporary experience suggests that sparse BNN training from scratch is challenging. Both sparseness and binarization bring their own challenges for mradient-based weight training - getting stuck at bad local minima in the sparse regime, incompatibility of back- propagation due to discontinuity in activation function, etc. Although we used gradient-based ap- proaches in this paper, biprop is flexible to accommodate different class of algorithms that might avoid the pitfalls of gradient- based weight training. Next, in contrast weight-optimizztionn that quires large model size and massive compute resources to achieve high performance, our hypothesis suggests that one achieve similar performance without ever training the large model. Therefore, strategies such as fast ticket search Youu et al.) 2019) or forward ticket selection (Ye et al.] (2020) can be developed to enable more efficient ways of finding-or even Sosigning-MPTT Finally, opposed to weight-optimization biprop by design achieves compact yet accurate models.
Theoretical. MPTs achieve similar performance as the model with learned weights. First, this observation notes the benefit of overparameterrizatin in the neural network learning and reinforces the idea that an important task of gradient descent (and learning in general) may be to effectively compress overparametrized models find multi-prize tickets. Next, our results highlight the expres- sive power of MPTs since we showed that compressed subnetworks can approximate any target neural network who are known to be universal approximators, our MPTs are also universal approxi- mators. Finally, the multi-prize lottery ticket hypothesis also uncovers the generalization properties of DNNs. Generalization theory for DI. is still in its infancy and its not clear what and how DNNs learn Neyshabur al.) 2017). Multi-prize lottery ticket hypothesis may serve as valuable tool for answering such questions as indicates the dependence of generalization on the compressiblity.
Practical. Huge storage and heavy computation requirements of state-of-the-art deep neural net- works inevitably limit their applications in practice. Multi-prize tickets are significantly lighter, faster, and efficient while maintaining performance. This unlocks a range of potential applications DL could be applied to (e.g.. applications with resource-constrained devices such as mobile phones, embedded devices, etc.). Our results also indicate that existing SOTA models might be spending far more compute and power than is needed to achieve certain performance. In other words, SOTA DL models have terrible energy efficiency and significant carbon footprint (Strubell et al. 2019). In this regard, MPT's have the potential to enable environmentally friendly artificial intelligence.

---

Published as a conference paper at ICLR 2021
REFERENCES
Yu Bai, Yu-Xiang Wang, and Edo Liberty. Proxquant: Quantized neural networks via proximal operators. In International Conference on Learning Representations, 2018
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 100..338.3344 3432, 2013.
Adrian Bulat and Georgios Tzimiropoulos. Xnor-net++: Improved binary neural networks. arXiv preprint 13866 2019.
Adrian Bulat, Brais Martinez, and Georgios Tzimiropoulos. Bats: Binary architecture search. arXiv preprint arXiv:2003.0/711 2020a.
Adrian Bulat, Brais Martinez, and Georgios Tzimiropoulos. High-capacity expert binary networks. arXiv preprint arXiv:2010003558. 2020b.
Matthieu Courbariaux, Yoshua Bengio, and lean-Pierre David. Binaryconnect: Training deep neural networks with binary weights during propagations. In Advances neural information processing systems, pp. 3123-3131, 2015.
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El- El-Yaniv, and Yoshua Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to+ or-1. arXiv preprint urXiv:1602.028300 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-24822552 255. lece, 2009.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:// openreview net/ wttpl//wwnee/ffroumiieeeee (dt.ouummmmrrr-rrreee
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. Training batchnorm and only batchnorm:
On the expressive power of random features in cnns, 2020.
Adam Gaier and David Ha. Weight agnostic neural networks. In Advances in Neural Information Processing Systems, pp. 5364-5378, 2019.
Ruihao Gong, Xianglong Liu, Shenghu Jiang, Tianxiang Li, Peng Hu, Jiazhen Lin, Fengwei Yu, and Junjie Yan. Differentiable soft quantization: Bridging full-precision and low-bit neural networks. In Proceedings of the IEEE International Conference Computer Vision, pp. 4852 4861, 2019.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1.
MIT press Cambridge, 2016.
Jiaxin Gu, Ce Li, Baochang Zhang, Jungong Han, Xianbin Cao, Jianzhuang Liu, and David Doer- mann. Projection convolutional neural networks for 1-bit cnns via discrete back propagation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 8344 8351, 2019.
Masafumi Hagiwara. Removal of hidden units and weights for back propagation networks. In Proceedings of 1993 International Conference on Neural Networks (JJCNN-93-Nagoya, Japan), volume pp. 351-354. IEEE, 1993.
Kai Han, Yunhe Wang. Yixing Xu, Chunjing Xu, Enhua Wu, and Chang Xu. Training binary neural networks through learning with noisy supervision. arXiv preprint arXiv:2010.04871, 2020.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00144 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1034-1034, 2015.
10

---

Published as a conference paper at ICLR 2021
Lu Hou, Quanming Yao. and James T Kwok. Loss-aware binarization of deep networks. arXiv preprint arXiv:1611.01660 2016.
Siddharth Joshi and Stephen Boyd. Sensor selection via convex optimization. Trans. Sig. Proc., 57
(2):451-462, February 2009. ISSN 1053-587X, doi: 10.1109//SP:200822007000 URL https: 7/doi. orgg 1109 09/059/922222 2008 2007095
Dahyun Kim, Kunal Pratap Singh, and Jonghyun Choi. Learning architectures for binary networks. In European Conference on Computer Vision, pp. 575-591. Springer. 2020.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXiv: (xXi::/81000234) 2018.
Mingbao Lin, Rongrong Ji, Zihan Xu, Baochang Zhang, Yan Wang, Yongjian Wu, Feiyue Huang, and Chia-Wen Lin. Rotated binary neural network. arXiv preprint arXiv:2009.13055, 2020.
Mingbao Lin, Rongrong Ji, Zihan Xu, Baochang Zhang, Fei Chao, Mingliang Xu, Chia- Wen Lin, and Ling Shao. Siman: Sign-to-magnitude network binarization. arXiv preprint arXiv:2102.0798) 2021.
Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network. In Advances in Neural Information Processing Systems, pp. 345-353, 2017.
Zechun Liu, Baoyuan Wu, Wenhan Luo, Xin Yang. Wei Liu, and Kwang-Ting Cheng. Bi-real net: Enhancing the performance of 1-bit cnns with improved representational capability and advanced training algorithm. In Proceedings of the European conference on computer vision (ECCV), pp- 722-737, 2018a.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint arXiv:1810.05270, 2018b.
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. arXiv preprint arXiv:2002.00585. 2020.
Brais Martinez, Jing Yang, Adrian Bulat, and Georgios Tzimiropoulos. Training binary neural networks with real-to-binary convolutions. arXiv preprint arXiv:2003.11535, 2020.
James O' Neill. An overview of neural network compression. arXiv preprint arXiv:2006.03669, 2020.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances neural information processing systems, pp. 5947-5956,
2017.
Laurent Orseau, Mareus Hutter, and Omar Rivasplata. Logarithmic pruning all you need. Ad- vances in Neural Information Processing Systems, 33, 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papalliopoulos. Optimal lottery tickets via subsetsum: Logarithmic over-parameterization is sufficient, 2020.
Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe. Binary neural networks: A survey. Pattern Recognition, pp. 107281, 2020a.
Haotong Qin, Ruihao Gong, Xianglong Liu, Mingzhu Shen, Ziran Wei, Fengwei Yu, and Jingkuan Song. Forward and backward information retention for accurate binary neural networks. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2250- 2259, 2020b.
11

---

Published as a conference paper at ICLR 2021
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's 's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 11893-11902, 2020.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In European conference on computer vision, pp. 525-542. Springer, 2016.
Franco Scarselli and Ah Chung Tsoi. Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results. Neural Netw. 11(1):15-37, January 1998. ISSN 0893-6080. doi: 10.101 101101///093-608000 60000670007 URL https: wwlddoi..oo. . 10. 10.101169000 00.10066500833-6000
(97) 00097-X
Mingzhu Shen, Xianglong Liu, Ruihao Gong, and Kai Han. Balanced binary neural networks with gated residual. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4197-4201. IEEE, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv 1409. 1556, 09 2014.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. arXiv preprint arXiv:1906.02233 2019.
Chaoqi Wang. Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020a.
Yulong Wang, Xiaolu Zhang, Lingxi Xie, Jun Zhou, Hang Su, Bo Zhang, and Xiaolin Hu. Pruning from scratch. In AAAI, pp. 12273-12280, 2020b.
Andreas S Weigend, David E Rumelhart, and Bernardo A Huberman. Generalization by weight- climination with application to forecasting. In Advances in neural information processing systems, pp. 875-882, 1991.
Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. Discovering neural wirings. In Ad- vances in Neural Information Processing Systems, pp. 2684-2694, 2019.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neu- ral networks for image recognition. In Proceedings of the IEEE International Conference on Computer Vision pp.
1293, 2019.
Zhaohui Yang, Yunhe Wang, Kai Han, Chunjing Xu, Chao Xu, Dacheng Tao, and Chang Xu. Search- ing for low-bit weights in quantized neural networks. arXiv preprint arXiv:2009.0666 2020.
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, and Qiang Liu. Good subnet- works provably exist: Pruning via greedy forward selection. arXiv preprint arXiv:2003.01794 2020.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird bird tickets: Towards more efficient training of deep networks. arXiv preprint arXiv: 1909. 1157,, 2019.
Dongqing Zhang, Jiaolong Yang, Dongqiangzi Ye, and Gang Hua. Le-nets: Learned quantization for highly accurate and compact deep neural networks. In Proceedings of the European conference on computer vision (ECCV), pp. 365-382, 2018.
Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen. Incremental network quantiza- tion: Towards lossless cnns with low-precision weights. arXiv preprint arXiv: 07077700224444 2017.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems, pp. 3597-3607, 2019.
Shuchang Zhou, Yuxin Wa, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-net: Train- ing low bitwidth convolutional neural networks with low bitwidth gradients. arXiv preprint arXiv:1066.00 06/0, 2016.
12

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
The authors would like to thank Shreya Chaganti for her valuable contributions to the biprop open source code development and for her help on training MPT models for the final version of the paper.
This work was performed under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under Contract No. DE-AC52-07NA27444 Lawrence Livermore National Security, LLC. This document was prepared as an account of the work sponsored by an agency of the United States Government. Neither the United States Government nor Lawrence Livermore National Security, LLC, nor any of their employees makes any warranty, expressed implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, process disclosed, or represents that its use would infringe privately owned rights. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation. or favoring by the United States Government or Lawrence Livermore National Security, LLC. The views and opinions of the authors expressed herein do not necessarily state or reflect those of the United States Government or Lawrence Livermore National Security, LLC, and shall not be used for advertising or product endorsement purposes. This work was supported by LLNL Laboratory Directed Research and Development project 20-ER-014 and released with LLNL tracking number LLNL-CONT-815432.
13

---

Published as a conference paper at ICLR 2021
A HYPERPARAMETER CONFIGURATIONS
A.1 HYPERPARAMETERS SECTION 3.1
Experimental Configuration. For MPT-I/32 tickets, the network structure is not modified from the original. For MPT-1/1 tickets, the network structure is modified by moving the max- max-pooling layer directly after the convolution layer and adding a activation function, as is common in many BNN architectures (Rastegan et al. 2016). We choose our baselines as dense full precision models with learned weights. The baselines were obtained by train- ing backbone networks using the Adam optimizer with learning rate of 0.0003 for 100 epochs and with batch size of 60. In each randomly weighted backbone network,
layer before the binary
find winning tickets MPT- 1/32 and MPT-1/1 for different pruning rates using Algorithm [ For both the weight-optimized and MPT networks, the weights are initialized using the Kaiming Normal distribution (He al. 2015). All training routines make use cosine decay learning rate policy.
Method
Model
Optimizer
LR
Momentum
Weight Decay
Batch
Epochs
MPT-1/32 Conv2/4/6/8
SGD
0.9
128
250
MPT-1/1 Conv2/4/6/8
Adam
00.
1e-4
128
250
Table Hyperparameter Configurations for CIFAR- 10 Experiments
A.2 HYPERPARAMETER: FOR SECTION 3.2
In these experiments, the weights are initialized using the Kaiming Normal distribution (He et al., 2013) for all the models except for MPT-1/32 on ImageNet where we use the Signed Constant initialization (Ramanujan et al., 2020) as it yielded slightly better performance. All training routines make use of a cosine decay learning rate policy. For ImageNet training we used a label smoothing value of 0.1 and learning rate warmup length of epochs.
Method
Model
Opt.
LR
Momentum
Weight Decay
Batch
Epochs
MPT-1/32
ResNet-18
SGD
0.1
0.9
5e-4
256
250
MPT-1732 +BN
R
SGD
0.1
0.
50-4
256
250
MPT-171
VGG "GG-Small"
Adam
3.63c-3
17.335
128
600
MPT-1/1 +BN
VGG-Small
Adam
3.63e-3
1e-4
128
600
Table Hyperparameter Configurations for CIFAR- 10 Experiments
Method
Model
Optimizer
LR
Momentum
Weight Decay
Batch
Epochs
MPT- 1/32
WRN-50
SGD
0.256
0.875
3.051757812e-$
MPT-1/32 +BN
WRN-50
SGD
0.256
0.875
3.05175781 2e-5
256
120
MPT-1/1
WRN-34
Adam
2.56e-4
3.05175781 2e-5
256
250
MPT- +BN"
WRN-34
Adam
2.56e-4
3.0517578126-5
256
250
Table 7: Hyperparameter Configurations for ImageNet Experiments
B EXISTENCE OF HINARY-WEIGHT SUBNETWORK APPROXIMATING TARGET NETWORK
In the following analysis, note that we write Bin([-1, (1]((111+11a) m to denote matrices of dimension m whose components are independently sampled from binomial distribution with elements +1) and probability 1/2.
Lemma 1. Let E [d]. E
[- Jo 1
J.).a i [d], and 5, 2 0 be given. Let B {-1,+11ks
be chosen randomly from Bin({-1. 1jxxd) and E {-1,+1}* k be chosen randomly from
14

---

Published as a conference paper at ICLR 2021
-1n If
16
(7)
2
+ 16 16log
(3)
8V8
then with probability at least 1 - there exist masks mn E {0, 13 and M E {0, 1 such that
the function g Rd + R defined by
g(x:) (m u)* a (e(M B)x),
(4)
satisfies
1g(x)) -xxi Se
(5)
for all |0/100 & 1. Furthermore, || = |M 1lo S 24. and maxisisk M S 1.
Proof. If [o] < then taking M = yields the desired result. Suppose that |a| > E. Then there
exists G N such that
GE S |a| s (cs 1)e and Iez |all S
(6)
Hence, it follows that
Jas sign(a));; azzi |ailcqs lall S
where the final inequality follows from (6) and the hypothesis that ||ar|| I 1. Our goal now is to
show that with probability 1 the random initialization of and yield masks and M such that g(x) oj sign(a)).;.
Now fix E [d] and take k' & First, we consider the probability
2'
P(G [M] uj +1 and В sign(a)) <G)
(8)
As and B each sampled from binomial distribution with K' trials, the distribution that the pair (uj. Bj,a) is sampled from is multinomial distribution with four possible events each having
probability of 1/4. Since we only interested the event (u,, B3,a) (+1, sag)(a)) occurring,
instead consider binomial distribution where P((ug. Bja) (+1, sign(a))
and
P((u, B,a) + sign(()) 2. Hence, using Hoeffding's inequality we have that
G
P (Kj E M uy +1 and By,, sign(a)) < <a) S exp
-2k'
(9)
4
k'
2 c
exp
W' +
(10)
exp
W + 2c
(11)
where the final inequality follows since exp() an increasing function and - < 0. From (6) and the fact that (a] < + follows that
(12)
8V8
Combining our hypothesis in with 12 yields that
16
2 )))
1
(
W G
k k
16
log
(13)
16
16 ev/
EVS
Substituting
13
into
11) yields
8
P(Ui E [K] uj +1 and Bj, sigu(a))
< c3) <
(14)
15

---

Published as a conference paper at ICLR 2021
Additionally, it follows from the same argument that
P POKK < <jsk:u = and Bj -iinnn)g) < q) 2
(15)
From 14 and 15 it follows with probability at least 1 - 8 that there exist sets S+ = {i U
and Bj sign(a)) and S_ = {j uj = and B = - sign(a)) satisfying
|S+ = S ei and S+ ns = D. Using these sets, we define the components of the mask mn
and M by
mg {
JE S US otherwise
(16)
and
M3.t 1
j E S+ U.S. and = otherwise
(17)
Using the definition of g(x) in
4) we now have that
g(x)
Σ (Esign(a)x:) Σ (-
(18)
iES,
G. (iign(()) - Go (-esign(a)z;)
(19)
G sign((a)...
(20)
where the final equality follows from the identity ((a) (-a)) for all a E R. This concludes the proof of (5)
Lastly, by our choice of m in 16
M in 17 and 12 it follows that
|
llo = M loo
2c; S 8V8'
(21)
and
max 15J5k
|| - 1,
(22)
which concludes the proof.
The next step is to consider an analogue for Lemma A.2 from (Malach et al. 2020) which we provide in Lemma 2
Lemma 2. Let [d]. w E [- Ve with ||00 s, and E, 0 be given. Let B
{-1, +1]kxd be chosen randomly from 1,n(f11,1) and {-1, +1} be chosen randomly
from
22s 16 + 16log
]
8
(23)
8
then with probability least 1-6 there exist masks mn E {0, 1]th and M 10xd such that the function Rd - R defined by
g(x)= = (m o u) (e(M o B)æ),
(24)
satisfies
1g(x) (w",x)) S e, for all | S 1.
(25)
Furthermore, |mllo ||
2sy/2 and maxisiss M;allo 1.
Proof. Assume & 16v5 16
2g and set = $. Note that
16./ + 16 log
(2x) then the excess neurons can be masked yielding the desired value for k. We
16

---

Published as a conference paper at ICLR 2021
decompose u, m, B. and M into equal size submatrices by defining
u (3)
(R(1i1)++1
uwi] l E (11,+114xx
(26)
770 (1)
(111111)+1
mxd] T E (0, 10,11
(27)
(1
((((-1)+1)dd
B
E {-1, +1]
(28)
beid
(((
M
:
{0. 10.1)
(29)
mysid
for i E [s]. Note that these submatrices satisfy
u (1)
(1)
B(1)
(
a
m
B
M
(30)
(()
B(s)
M
Now let I = {i E [d] : * 0}. By our hypothesis that ||00 11o S it follows that [ S 8.
WLOG, assume that C [s]. Now fix E [s] and define gi : I2d
+ R by
(xx m u )
(5(M()
B B
(31)
By 23 taking e and 8' - yields that k' eVP
16 16 (+) Hence, follows from
Lemma that with probability least there exist ( E f0, 11 and M {0, 1) k such that
(gx(x) - w/ S 6566
(32)
for every æ E gd with | loo I 1, and
2/
m i llo
|M la 88
and
max M(-1)+IsisM
| 1lo I 1.
(33)
By the definition of g(x)) in 24 using
30 yields
g(x) = (m 2 TT (cMM @ B)x)
m (0
(e(M)() 3 B())))
Σ
9: (x))
1=1
(34)
Hence, combining 32 for all i [s], it follows that with probability at least 1 - 8 we have
1g(x)= - (w", x)1 Σ (x)
S
(x)
wool E.
(35)
Finally, it follows from 330p and 33 that
28
m Ilu
||
llo
S
and
max 15
|M 1,
(36)
g
which concludes the proof.
We now state and prove an analogue to Lemma A.5 (Malach et al. 2020) which is the last lemma will need to establish the desired result.
17

---

Published as a conference paper at ICLR 2021
nxd
Lemma 3. Let E [d], W Ve
with || S S, F R R defined by
(((x)) - ( and e > 0
given. Let {-1, +11,+ chosen randomly from
(in 1] kx and U +-1,++1 be chosen randomly from Bin +11xxxx If
16yns nss E
m2ss)
2 ns
+ 16 lolog
(37)
8
then with probability at least 1- 8 there exist masks M E [0,1]&xm and M {0, hxd such that the function G I2d + R defined by
G(x) = (M OUTO (e(M @ B)m)).
(38)
satisfies
[G((x) - F(x))l2 S for all ||0 S 1.
(39)
Furthermore, |M |M I 2nsyns
Proof. Assume = ns
16yns + 16 log (ne and set K' &. Note that if ns
16/08 + 16 (2mg)
then excess neurons can be masked to yield the desired value for k.
As in the proof of Lemma
2 we split U, M, B, and M into submatrices, denoted E +1) xn, B( E [11,+ xd and M E (-1, +1) =
U {-1,+11* "11""='' M
xd
for E [m]. such that
U
MM
M
U-
M
B
and M =
(40)
Uin)
(
B ((n)
MM))
To simplify notation in the following definition, define the vectors m (9)
M (
and a
1/4 Now we define the functions gi
RRd R by
(xxx)= m r
(1))) T
(B(M o )o),
(41)
for each i E [n]. Taking g =
and 8' it follows from 37 that
2 8
Vn
16 16 log 2x As the hypotheses of Lemma 2 are satisfied, with probability least
there exist masks m (1) and (+) with
m (1) lo || < 28 28
28 2s/ ns
(42)
such that
lg. - (W;, x) S E
for all ||0|/00 S 1.
(43)
Vn'
For each i [ni], note that this results in choosing the columns of the mask M by
m (
t=
M
(44)
0
otherwise
Combining this choice with (40 yields
(x(
(M o UTTo (3(M B)x)
(45)
(x)
18

---

Published as a conference paper at ICLR 2021
By the definition of (ax) in 38 follows from 45 that
(x))
G(æ))
(46)
[(g(())))
Combining (43) and (46), we have with probability at least that
[[((x) - F()) (o())(=)) ((w, x))))
(a:(x)) - (W;, (Wi s
(47)
Finally, it follows from 42 and that
2ns 2ns
M lo 1| <
(48)
which concludes the proof.
We now ready prove the main result in Theorem 2
[- vo dxn (W E V vn
nx*
Theorem 2. Let s,,,s E N.
w E
and ( E Vn vn 1 1xn max, W
Assume that for each i E [ we have || S and
W 1lo S s. Define F(x) = F(0) ....... ... (x) where F()()) = o( (i) x) for
i E 1] and (x) w( Fixe, 1).
Let ((1) E {11,+1) be sampled from Bin((-1,+1)xx44 (BO) E {-1,+1]Axm {-1, +-1,+1)bxx be sampled from Bin([-1,-11)) and U()) (11,++1kxxl sampled from Bin((-1, +1](k),)) If
be sampled from (inff-1,11)x*) (Ul0)E=
k 2 ns 328 16
(nnsl
+16log log
(-60)
(49)
then with probability at least - ā there exist binary masks (M Fi=1 and (MO)) for (B Jiz and (U0i), J respectively, such that the function G Rd + R defined by
G(x) (( o...o (x),
(50)
where
(x) a (M (1) o To((( @ )x))
for E [ee [e-1)
(51)
(z) (M ( B)))))
(52)
satisfies
[G(x) F(x)] S s, for all ||0||2-
(53)
Additionally, |M = || 4nsst /ns
Proof. Let i [E 1). Using Lemma with el and 8' 3. with probability least
there exist (i) and (+) such that
( (x) (x) S 28
for all |0 S
(54)
and
M (
l. =
| 11o <
2ns ns
4nst I ns
(55)
The remainder of the proof follows from applying the same argument as in the proof of Theorem A.6 from (Malach et al. 2020).
[]
19

---

Published as a conference paper at ICLR 2021
C MOTIVATION FOR FRAMEWORK TO IDENTIFY MPTs
Suppose that f(æ; W with optimized weights W* is target network that we wish to approx- imate. Let g( W) denote the network in which we want to identify a MPT-1/32 that is an E- O.
approximation of f(: W*), for some
Now assume that g(x; .) is Lipsehitz continuous with constant Ni B E { {-1,+1}m are binary parameters for g, and R is gain term. It follows that
l19 (z; (M @ B)) f(x; W - 1 (x; a(M B) -0;; M @ B)ll
+ 119(2;; M @ W) - f(x: W'll
x|| MM W) a(M @ B)
+ (1l M C W) f(æ; W
(56)
If we take M to be a fixed binary mask, we can minimize the emror of binarizing the subnetwork parameters M O W by solving the optimization problem
min a.B II(M : W) - a 3 B)
(57)
s.t.
R. B (-1
where M, W. and B are stacked into vectors of some length, say n. As the pruning mask M is applied to both W and B, solving problem (57) is equivalent to solving problem (2) in (Rastegari al., 2016) with different dimension. Hence, immediately follows that one closed form solution for B in problem (57) is
B
sign WW)
(58)
Taking the derivative of the cost function in 57 with respect to a and setting it equal zero yields
a(M @ (
B") (M & (M B²) = O.
(59)
Recalling that M E {00.1" and using 588 we have
(M o ( O Σ (M,B)) Σ (iign (i))
= Σ M, = |
(60)
1=1
and
(Mo W)T(MM B*) Σ M&W, sign(W.) = Σ M.|wal JM o W|l.
(61)
Substituting
(60) and 61 into 59 and solving for a yields the closed form solution
|M @ W
(62)
|
Hence, a" and B" minimize the right hand side of (66) and, consequently, reduce the approximation error of the MPT-1/32. So when the binarization error, [I @ W) w7-a((1)
sign (W)) ll. and the subnetwork error, []g[;; M MOW) W) fa; WI are sufficiently small then the binarized subnetwork g (x; a 3 sign W)) serves as a good approximation to the target network.
a(
These closed form expressions for the gain term and the binarized weights are the updates used for the gain term and binary subnetwork weights in biprop after updating the binary pruning mask.
D COMPARISON OF MPTs WITH BINARY NEURAL NETWORK SOTA
Here we provide a more exhaustive comparison of MPT-1/32 and MPT-1/1 on CIFAR-10 and Im- ageNet to SOTA methods BinaryConner (Courbariaux et al.] 2015). BNN (Courbariaux et al.) 2016), DoReFa-Nee (Zhou et al. 2016), LQ-Nets (Zhang et al. 2018), BWN and XNOR-Net (Raste- gari al. 2016), ABC-Net (Lin et al.) 2017). IR-Net (Qin et al. 2020b), LAB (Hou et al. 2016), ProxQuant (aai et al. 2018). DSQ (Gong et al. 2019). and BEG (Shen et al. 2020). Results for CIFAR-10 can be found in Tables and I and results for ImageNet can be found in Tables 10 and II Next to the MPT method we include the percentage of weights pruned and the layer width multiplier
(if larger than 1) in parentheses.
20

---

Published as a conference paper at ICLR 2021
Method
Model
Top-1
Params
BinaryConnect
VGG-Small
91.7
4.6 M
BWN
VGG-Smal
90.1
(4.66 M
DoReFa-Ne Fetet
ResNet-20 20
90.0
0.27 M
LQ-Nets
ResNet-21 20
90.1
0.27 M
LAB
VGG-Small
89.5
4.6 M
ProxQuant
ResNet-36
92.3
0.85 M
DSQ
ResNet-20
90.2
0.27 M
IR-Net
ResNet-20
90.8
0.27 M
Full-Precision
ResNet-18
93.02
11.2 M
MPT-1732 (95)
VGG-Small
91.48
0.23 M
(80)
ResNet-18
94.66
2.2 M
MPT (80) +BN
ResNet-18
94.8
2.2 M
Table 8: Comparison of MPT-1/32 with Trained Binary (1/32) Networks CIFAR-10
Method
Model
Top-1
Params
BNN
VGG-Small
89.9
4.6 M
XNOR-NO
VGG-Small
89.8
4.6 M
DoReFa-Net
ResNet-20
79.3
0.27
BBG
ResNet-20
85.3
"0.27 M
LAB
VGG- Smail
87.7
4.6 M
DSQ
VGG-Small
91.7
IR-Net
ResNet- 18
91.5
4.6 M
Fuil Prie-Precision
VGG Small
93.6
4.6 M
MPT (75, 1.25x)
VGG-Smal
88.49
1.44
MPT (75, 1.25x) +BN
VGG-Small
91.9
1.44 M
Table 9: Comparison of MPT- 1/1 with Trained Binary (1/1) Networks CIFAR-10
Method
Model
Top-1
Params
ABC-Net
ResNet-18
62.8
11.2 M
BWN
ResNei-18
60.8
111.2 M
BWNH
ResNet- 18
64.3
"11.2
PACT
ResNet- 18
65.8
11.2 M
IR-Net
ResNet-34
70.4
21.8 M
Muunization-Networr
ResNet-
66.3
"1i.2
Tmantization-Netwwe Networks
ResNer 50
72.8
255.6
Full-Precision
ResNet-34
73.27
21.8 M
MPT (80)
WRN-50
72.67
13.7
MPT (80)+ +BN
WRN-50
74.03
13.7 M
Table 10: Comparison of MPT-1/32 with Trained Binary (1/32) Networks ImageNet
E COMPARISON EDGEPOPUP FOR MPT-
Note that binarization step of biprop can be avoided while finding MPT- - by initializing (and pruning) our backbone neural network with binary initialization (c.g., edgepopup with Signed Con- stant initialization (Ramanujan et al. 2020)). In this specific instance, biprop boils down to edge- popup with proper scaling. Next, we compare the performance of MPT-1/32 networks identified using these two approaches. Both networks presented below use the same hyperparameter config- urations and are trained for 250 epochs on the CIFAR- dataset. We initialize the networks iden- tified with edgepopup using the Signed Constant initialization as it yielded their best performance. MPT-1/32 networks identified using biprop are initialized using the Kaiming Normal initialization. We plot the average over three experiments for each pruning percentage and bars extending to the minimum and maximum accuracy for each pruning percentage. Additionally, for each network we include the Top-1 accuracy of dense model with learned weights. These plots can be found in
21

---

Published as a conference paper at ICLR 2021
Method
Model
Top-1
Params
BNN
AlexNet
27.9
62.3 M
XNOR-Net
AlexNet
44.2
62.3 M
ABC-Net
ResNet- 18
42.7
11.2 M
ABC-Net
ResNet-34
52.4
21.8 M
TSQ
AlexNet
58.0
62.3 M
WRPN
ResNei-34
60.5
21.8 M
HWGQ
AlexNet
52.7
62.3 M
IR-Net
ResNet-
58.1
11.2 M
IR-Net
ResNet-34
62.9
21.8 M
Full-Precision
ResNei-34 34
73.27
21.8 M
MPT (60)
WRN-34 34
45.06
19.3 M
MPT (60) +BN
WRN-34
52.07
19.3 M
Table 11: Comparison of MPT-1/1 with Trained Binary (1/1) Networks on ImageNet
We find that the performance of MPT-1/33 identified with biprop outperforms networks identified using edgepopup. This highlights the benefit binarization (in conjunction with pruning) as learning strategy.
Figure
Conw-2
Cony-4
Cony-6
Conv-8
90-
90
CIFAR-10 Tep-1 Accuracy
85
80
00
90
75
20
70
35
60
65
70
75
80
05
90
50
55
60
65
70
75
80
05
90
50
55
60
85
70
75 00
05
90
50
55 80 85
70
75
00 05 90
Pecenaage
Percentage
Peroontage (WWett
MPT-1/12 (litrrlted))
Edgepepup (Signed Constant)
++-
Dente (Learreed Weightts)
Figure 5: Comparing biprop and edgepopup: Comparing the Top-1 accuracy of MPT-1/32 to binary weight networks of the same size identified using edgepopup on CIFAR-I0.
F RELATED WORK
F.1 PRUNING
We categorize pruning methods based on whether a model is pruned either after the training or before the training (see (Neill 2020) for comprehensive review).
Post- Training Pruning. The traditional pruning methods leverage three-stage pipeline pre- training (a large model), pruning, and fine-tuning. The main distinction lies among these approaches what type of criteria is used for pruning. One of the most popular approach is the magnitude-based pruning where the weights with the magnitude below a certain threshold are discarded (Hagiwara) 1993). Further, certain penalty term (e.g., 41, la lasso weight regularization) can be used during training to encourage model to learn certain smaller magnitude weights and removing them post- training (Weigend al. 199T). Models can also be pruned by measuring the importance of weights by computing the sensitivity of the loss function when weights are removed and prune those which cause the smallest change the loss (LeCun et 1990).
Pruning Before Training. Thus far, have have discussed methods for pruning pretrained DNNs.
Recently, (Frankle & Carbin 2019 proposed the Lottery Ticket Hypothesis and showed that candomly-initialin neural networks contain sparse subnetworks that can be effectively trained from scratch when reset to their initialization. Further, (Liu et al. 2018b) showed that the training
22

---

Published as a conference paper at ICLR 2021
pverpparameterizee model is often not necessary to obtain efficient final model and network architecture itself is more important than the remaining weights after pruning pretrained networks. These findings has revived interest in finding approaches for searching sparse and trainable subnet- works. For example, (Lee et al.) 2018: Wang et al., 20206 You et al., 2019 Wang et al. 2020a) explored efficient approaches search for these sparse and trainable subnetworks. Along this line of work, a striking finding was reported by (Zhou et al. 20199] Ramanujan et al. 2020) showing that randomly-initiaizzed neural networks contain sparse subnetworks that achieve good performance without any training. (Malach et al., 2020; [Pnssi et al,, 2020) provided theoretical evidences for this phenomenon and showed that one can approximate any target neural network, by pruning a sufficiently wer-paaametterize network of random weights.
F.2 BINARIZATION
Similar to pruning, we categorize binarization methods based on whether a model binarized either after the training or during the training (see (Qin et al. 2020a) for comprehensive review).
Post-Traiee Teainingn Binarization. To the best of our knowledge, none of the post-training schemes have been successful in binarizing pretrained models with or without retraining to achieve reasonable test accuracy. Most existing works (Han et al., 2015 Zhou et al. 2017) are limited to ternary weight quantization.
Training-Aware Binarization. There are several efforts to improve the performance of BNN training. This is a challenging problem as binarization introduces discontinuities which makes dif- ferentiation during backpropogation difficult. Binaryconnect (Courbariaux et al. (2015) established how to train networks with binary weights within the familiar back-propagation paradigm. Bina- ryNet (Courbariaux et al. 2016) further quantize both the weights and the activations to 1-bit values. Unfortunately, these early schemes resulted in a staggering drop in the accuracy compared their full precision counterparts. In an attempt improve the performance, XNOR-Net (Rastegari al.) 2016) proposed to add a real-valued channel-wise scaling factor. Dorefa-Net (Zhou al.. 2016) ex- tends XNOR-Net to accelerate the training process using quantized gradients. ABC-Net (Lin al. 2017) improved the performance by using more weight bases and activation bases at the cost of increase in memory and computation. There have also been efforts in making modifications the network architectures to make them amenable for the binary neural network training. For example, Bireal-Net (Liu al., (018a) added layer-wise identity short-cut, and AutoBNN (Shen et al. 2020) proposed to widen or squeeze the channels in an automatic manner. (Han et al., 2020) proposed learn binarize neurons with noisy supervision. Some efforts also have been carried out to de- signing gradient estimators extending straight-through estimator (STE) (Bengio et al., 2013) for accurate gradient back propagaatpag DSQ (Gong et al. (019) used differentiable soft quantization to have accurate gradients in backward propagation. On the other hand, PCNN Gu et al. (2019) proposed a new discrete back pack-propagation via projection algorithm to build BNNs.
F.3 OTHER RELATED DIRECTIONS
Gaier & Ha 2019) proposed a search method for neural network architectures that can already per- form a task without any explicit weight training, i.e., each weight in the network has the same shared value. Recent work in randomly wired neural networks (Xic et al., 2219)) showed that constructing neural networks with random graph algorithms often outperforms manually engineered architec- ture. As opposed fixed wirings in (Xie al. 2019), /Wortsman al. 2019) learned the network parameters as well as the structure. This show that finding a good architecture is akin to finding a sparse subnetwork of the complete graph.
23


Reviews:
[{"review_id": "lNlT_ly4yr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an innovate method based on lottery ticket hypothesis to prune a BNN (parameters are only -1(0) and +1, it can be viewed as an extreme case of quantization) from a dense NN. It focuses on learning a mask to prune the NN instead of the traditional method (pruning on an already trained network). In addition, not only experiments but theortical proof are given and have a highly brief result.\n\nPro:\nThe way to find the mask iteratively is innovate and has a mathematical support.\nThe result of MPT is amazing because the untrained network can be pruned to a BNN with comparable accrancy of some trained SOTA NN on CIFAR dataset.\nThe experiments show it can be generized to deeper and wider network.\nIt has better accurancy than other BNN methods but network parameters still high.\nCon:\nThe main article spends little word to describe how to find the mask, and it is not a trivial way.\nThe experiments of generization are only done on the very small NN (e.g. Conv2/4/6/8).\n\nClarity: Very low. Pros: The authors try to express in a way that every step of logical connections in this paper can be clearly understood by readers. To reduce complexity, many parts are settled in the appendix. Cons: Many sentences in this paper are quite long and sometimes using nesting clauses, which makes the text to be obscure. Besides, since many parts are moved into the appendix, the whole structure of the main body is kind of empty and shallow. Some summative and conclusive paragraphs are the simple repetition of previous “claims” since the demonstrations are in the appendix. All of these make a lower clarity. \nFinally, I find that this paper has narrower page margins, which means each line can contain more characters. Besides, the header “Under review as a conference paper at …” is missing. These modifications of the submit template may volatile the conference rule and should be considered a cheating behavior. So I give the “very low” score on clarity.\n\nOriginality: Medium. Pros: They apply the Lottery Ticket Hypothesis to quantization/BNN. They give proof of their rationality. Cons: The success essentials of their algorithm “biprop” contains two-part: edge-popup and gradient estimator. Both of them are take-away from other works. I regard this work as a new application of LTH to binary neural networks.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kExE_sjVaEv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a stronger lottery ticket hypothesis in this paper – the multi-prize lottery ticket hypothesis. In particular, the new hypothesis seeks answer to the required amount of over-parameterization for a randomly initialized network to become able to compress to a sparse untrained binary subnetwork with on-par accuracy. The authors prove the existence of such subnetwork and show the bounds on over-parameterization. The paper proposes new methods to get the binary-weight tickets and the binary-activation tickets, where binary-weight tickets are subnetworks with weights as binary, and binary-activation tickets have the activation function in the forward propagation as binary. As binary networks can largely reduce the computational complexity for inference, this work has practical importance especially for applications with constraints for memory and power. The paper has many simulation results to support the theoretical guarantees, and the proposed approach on binary-weight networks has advantages over existing methods.\n\nThe paper has sufficient and novel contributions, both for the theoretical results on binary subnetworks and the empirical evaluations that reveal the efficiency of the algorithm on binary-weight subnetworks, so that I recommend this paper for publication. \n\nHere are some minor concerns.\n\n[a] It would be more convincing if the authors could further highlight the technical novelty of this work for the proof of Theorem 1. Compared with Malach 2020 “Proving the lottery ticket hypothesis: pruning is all you need”, the authors can highlight what key differences are needed for proof of the binary network.\n\n[b] For the comparison of full precision network and the MPT from this paper, it can be useful if the computational complexity is shown, where the complexity for MPT would be for the algorithm to find the mutli-prize tickets in an over-parameterized network.\n\n[c] The MPT 1/1 seems not to perform as well compared to trained binary activation network, which may reduce the quality of paper. It is good that the authors mention future work for MPT 1/1 network to attain state-of-art results of binary activation network.\n\n[d] Some of the references seem to lack information, e.g. Malach 2020, Orseau 2020, both of which do not have the venue or journal names.\n\n[e] A question: for the binary weights subnetworks, what does it mean by 20 million parameters? The weights can only be -1 or 1, so the network has 20 million of -1 or 1, but they do not require any multiplication at the inference stage?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hzs2S6hNoN", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper propose utilizing the existing \"lottery ticket\" result for constructing binary neural networks. This work has some novelty, in the sense that I haven't seen any other papers on untrained binary neural networks. The experimental results looks good.\n\nHowever, I have some concerns on this paper.\n1. This paper, at least the main text, is not self-contained. The writing needs significant improvement. The main contribution of the paper, section 2, is only one-page long. Neither the theory nor the algorithm are well explained in the main text. Moreover, the algorithm relies heavily on the edge-popup algorithm, which is not explained even in the supplementary material. The title is also somewhat too long.\n2. Though the proposed algorithm achieves excellent results in terms of parameter count and accuracy, I think the comparison is somewhat unfair. The subnetwork is sparse, and can be much slower on real hardware. Moreover, pruning from a larger network is known to achieve better result than training a smaller network from scratch, but the baselines does not utilize this.\n3. There lacks any discussion on the real time consumption of the proposed network.\n4. Time consumption of training should also be reported.\n\nPost rebuttal\n====\n\nThanks the authors for clarifying and revising the paper. The updated version does look much clearer to me, so I updated my ratings. \n\nI am still wondering the difference of biprop vs. a classical quantization-aware training for ternary networks. I did read the response to R3. From my understanding it seems that:\n1. biprop doesn't count 0 as a parameter, while TWN does;\n2. biprop prunes a larger network (WRN50), while TWN trains a network of the original size (ResNet-50);\nI am not sure if the superiority of biprop comes from these reasons, instead of LTH itself. biprop still looks more like a QAT algorithm than a LT-finding algorithm in the sence that\n1. it does not train the pruned network after finding the LT as the original LTH paper;\n2. it directly learns the binary weights.\nJust out of curiosity, but I think clarifying these concerns would make the paper stronger.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TBBbtXvdlkk", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work investigated a method of finding a subnetwork of redundant binary networks to gain an overall advantage over pruned or quantized networks.\n\nOne main concern of the reviewer is the similarity between the paper's approach---training a mask over a binary network---and the conventional ternary network.  Are the masked weights analogous to the 0 of the ternary networks, while the unmasked weights are in {-1, 1}? In that case, it's fairer to compare with ternary networks with 0 counted into the total params.\n\nFollowing this analogy, it is also misleading to claim that the network is \"untrained\", as to minimize the loss, any binarized weights can be updated to 0(masked), although indeed the weight update across 0 is forbidden. \n\nThe theory works of this paper are strong and prove that the expressive power of redundant binary(or ternary?) networks can match their denser counterpart.  Still, the question to clarify here is that whether \"subset (lottery ticket) + binary network\" equals to \"ternary network\". \n\nIn general, the paper is well written and the theoretical and experimental works support the authors' claim. The reviewer would recommend accepting the paper on the condition that the authors can address the comparison with the ternary network fairly.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a new theoretical framework that establishes that any network can be approximated by pruning a polynomially larger random binary networks, and also an algorithm for pruning binary nets. The results are important in the general context of the "strong" lottery ticket hypothesis, and are of both theoretical and practical interest. Although some of the ideas and technical contributions can be seen as a combination of prior tools and algorithms, the experimental findings are very novel.  Some further concerns of clarity and novelty were addressed by the authors.
Decision: Accept (Poster)