Slot Machines: Discovering Winning Combinations of Random Weights in Neural Networks
Authors: Maxwell Mbabilla Aladago
Lorenzo Torresani
Venue:  (2021)
Keywords: initialization
optimization

Abstract: In contrast to traditional weight optimization in a continuous space, we demonstrate the existence of effective random networks whose weights are never updated. By selecting a weight among a fixed set of random values for each individual connection, our method uncovers combinations of random weights that match the performance of trained networks of the same capacity. We refer to our networks as ``slot machines'' where each reel (connection) contains a fixed set of symbols (random values). Our backpropagation algorithm ``spins'' the reels to seek ``winning''  combinations, i.e., selections of random weight values that minimize the given loss. Quite surprisingly, we find that allocating just a few random values to each connection (e.g., 8 values per connection) yields highly competitive combinations despite being dramatically more constrained compared to traditionally learned weights. Moreover, finetuning these combinations often improves performance over the trained baselines.  A randomly initialized VGG-19 with 8 values per connection contains a combination that achieves 90% test accuracy on CIFAR-10.  Our method also achieves an impressive performance of 98.1% on MNIST for neural networks containing only random weights. 

Under review as a conference paper at ICLR 2021
SLOT MACHINES: DISCOVERING WINNING COMBINA- TIONS OF RANDOM WEIGHTS IN NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In contrast to traditional weight optimization in a continuous space, we demon- strate the existence of effective random networks whose weights are never up- dated. By selecting a weight among a fixed set of random values for each in- dividual connection, our method uncovers combinations of random weights that match the performance of traditionally- -traine---idd networks of the same capacity. We refer our networks as "slot machines" where each reel (connection) contains a fixed set of symbols (random values). Our backpropagation algorithm "spins" the reels to seek "winning" combinations, i.e., selections of random weight values that minimize the given loss. Quite surprisingly, we find that allocating just few random values to each connection (c.g.. 8 values per connection) yields highly competitive combinations despite being dramatically more constrained compared to traditionally learned weights. Moreover, finetuning these combinations often improves performance over the trained baselines. A randomly initialized VGG- 19 with 8 values per connection contains a combination that achieves 90% test accuracy on CIFAR-10. Our method also achieves an impressive performance of 98.1% on MNIST for neural networks containing only random weights.
INTRODUCTION
Innovations in how deep networks are trained have played an important role in the remarkable suc- cess deep learning has produced in variety of application areas, including image recognition (He) al. 2016), object detection (Ren al. 2015 He et al., 2017), machine translation (Vaswani al,,
2017 and language modeling (Brown et al. 2020). Learning typically involves either optimizing
a network from scratch (Krizhevsky et al. 2012). finetuning a pre-trained model (Yosinski et al.)
2014) or jointly optimizing the architecture and weights (Zoph & Le 2017). Against this predom- inant background, we pose the following question: can à network instantiated with only random weights achieve competitive results compared to the same model using optimized weights?
For a given task, an untrained, randomly initialized network is unlikely to produce good perfor- mance. However, we demonstrate that given sufficient random weight options for each connection, there exist selections of these random weight values that have generalization performance compa- rable to that of a traditionally-trainedd network with the same architecture. More importantly, we introduce a method that can find these high-performing randomly weighted configurations consis- tently and efficiently. Furthermore, we show empirically that small number of random weight options (e.g., 2 8 values per connection) are sufficient to obtain accuracy comparable to that of the traditionally- -araiinnnnll--ttieeeddd trained network. Instead of updating the weights, the algorithm simply selects for each connection a weight value from fixed set of random weights.
We use the analogy of "slot machines" to describe how our method operates. Each reel Slot Machine has a fixed set of symbols. The reels are jointly spinned in an attempt to find winning com- binations. In our context, each connection has a fixed set of random weight values. Our algorithm "spins the reels" in order to find winning combination of symbols, i.e., selects weight value for each connection so as to produce an instantiation of the network that yields strong performance. While in physical Slot Machines the spinning of the reels is governed by fully random process, in our Slot Machines the selection of the weights is guided by a method that optimizes the given loss at each spinning iteration.

---

Under review as a conference paper at ICLR 2021
More formally, we allocate K fixed random weight values to each connection. Our algorithm assigns a quality score to each of these K possible values. In the forward pass a weight value is selected for each connection based on the scores. The scores are then updated in the backward pass via stochastic gradient descent. However, the weights are never changed. By evaluating different combinations of fixed randomly generated values, this extremely simple procedure finds weight configurations that yield high accuracy.
We demonstrate the efficacy of our algorithm through experiments on MNIST and CIFAR-IO.
On MNIST, our randomly weighted Lenet-300-100 (Lecun et al. 1998) obtains a 97.0% 97.0% test set accuracy when using K
options per connection and 98.1% with K 128. On CIFAR- 10 (Krizhevsky) 2009), our six six-layer convolutional network matches the test set performance of the traditionalll-trann trainne network when selecting from K 64 fixed random values each connection.
Finetuning the models obtained by our procedure generally boosts performance over networks with optimized weights albeit at an additional compute cost (see Figure Also, compared to traditional networks, our networks are less memory efficient due to the inclusion of scores. That said, our work casts light on some intriguing phenomena about neural networks:
First, our results suggest performance comparability between selection from multiple ran- dom weights and traditional training by continuous weight optimization. This underscores the effectiveness of strong initializations.
Second, this paper further highlights the enormous expressive capacity of neural networks. Maennel et al. (2020) show that contemporary neural networks are so powerful that they can memorize randomly generated labels. This work builds on that revelation and demonstrates that current networks can model challenging non-linear mappings extremely well even by simple selection from random weights.
This work also connects to recent observations (Malach et al. 2020 Frankle & Carbin 2018) suggesting strong performance can be obtained by utilizing gradient descent to un- cover effective subnetworks.
Finally, we are hopeful that our novel model model- connsisingg in the the introduction of multiple weight options for each edge- will inspire other initialization and optimization strategies.
RELATED WORK
Supermasks and the Strong Lottery Ticket Conjecture. The lottery ticket hypothesis was ar- ticulated in (Frankle & Carbin, 2018) and states that a randomly initialized neural network contains sparse subnetworks which when trained in isolation from scratch can achieve accuracy similar to that of the trained dense network. Inspired by this result, Zhou et al. (201)) present method for identifying subnetworks of randomly initialized neural networks that achieve better than chance performance without training. These subnetworks (named "supermasks") are found by assigning probability value to each connection. These probabilities are used to sample the connections to use and are updated via stochastic gradient descent. Without ever modifying the weights. Zhou et al. 2019) find subnetworks that perform impressively across multiple datasets.
Follow up work by |Ramanujan dense network. On ImageNet (Russakovsky et al. 2009). they find subnetworks within randomly weighted ResNet-50 (Zagoruyko & Komodakis 2016) that match the performance of smaller, trained ResNet-34 (He et al. (2016). Accordingly. they propose the strong lottery ticket conjecture: sufficiently overparameterized, randomly weighted neural network contains subnetwork that performs as well as traditionally-trained network with the same number of parameters, |Ramanujan et al. (0199) adopts a deterministic protocol in their so-called "edge-popup" algorithm for finding supermasks instead of the stochastic algorithm of Zhou al. (2019).
(2019) finds supermasks that match the performance of
These empirical results as well as recent theoretical ones (Malach et al., 2020 Pensia et al. 2020) suggest that pruning randomly initialized network is just good as optimizing the weights, pro- vided a good pruning mechanism is used. Our work corroborates this intriguing phenomenon but differs from these prior methods in a significant aspect. We eliminate pruning completely and in- stead introduce multiple weight values per connection. Thus, rather than selecting connections to define subnetwork, our method selects weights for all connections in network of fixed structure.
2

---

Under review as a conference paper at ICLR 2021
For each edge (i,j), assigned K fixed random weights and K corresponding scores.
Forward: use only one of the K weight options for each edge basc on the learned scores.
Backward: update scores including those that were not used in the forward pass.
Figure I: Our method assigns set of K (K' this illustration) random weight options each connection. During the forward pass, one of the K values is selected for each connection, based on a quality score computed for each weight value. On the backward pass, the quality scores of all weights are updated using a straight-through gradient estimator (Bengio et al. 2013), enabling the network to sample better weights in future passes. Unlike the scores, the weights are never changed.
Although our work has interesting parallels with pruning (as illustrated Figure 9 is different from pruning all connections remain active in every forward pass.
Pruning at Initialization. The lottery ticket hypothesis also inspired several recent work aimed towards pruning (i.e., predicting "winning" tickets) at initialization (Lee et al. 2020 2019 Tanaka et al. 2020 Wang et al. (020). Our work is different in motivation from these methods and those that train only subset of the weights (Hoffer et al. 2018 Rosenfeld & Tsotsos 2019). Our aim is to find neural networks with random weights that match the performance of traditionally-train networks with the same number of parameters.
Weight Agnostic Neural Networks. Gaier & Ha 2019) build neural network architectures with high performance
setting where all the weights have the same shared random value. The op- timization is instead performed over the architecture (Stanley & Mükkkllanen (202).. They show empirically that the network performance indifferent the shared value but defaults to random chance when all the weights assume different random values. Although we do not perform weight training, the weights in this work have different random values. Further, we build our models using fixed architectures.
Low-bit Networks and Quantization Methods. As in binary networks (Courbariaux & Bengio 2016 Rastegari et al. 2016) and network quantization (Hubara et al.) 2017; Wang 2018), the parameters in slot machines are drawn from a finite set. However, whereas the primary objective in quantized networks is mostly compression and computational speedup, the motivation behind slot machines recovering good performance from randomly initialized networks. Accordingly, slot machines use real-valued weights opposed the binary (or integer) weights used by low-bit networks. Furthermore, the weights in low-bit networks are usually optimized directly whereas only associated scores are optimized in slot machines.
Random Decision Trees. Our approach is inspired by the popular use of random subsets of features in the construction of decision trees (Breiman al., 1984). Instead of considering all possible choices of features and all possible splitting tests at each node, random decision trees are built by restricting the selection to small random subsets feature values and splitting hypotheses. We adapt this strategy to the training of neural network by restricting the optimization of each connection over a random subset weight values.
3 SLOT MACHINES: NETWORKS WITH FIXED RANDOM WEIGHT OPTIONS
Our goal is to construct non-sparse neural networks that achieve high accuracy by selecting value from a fixed set completely random weights for each connection. We start by providing an intuition for our method in Section 3.1 before formally defining our algorithm in Section 3.2
3

---

Under review as a conference paper at ICLR 2021
3.1 INTUITION
An untrained, randomly initialized network is unlikely to perform better than random chance. In- terestingly, the impressive advances of Ramanujjn et al. (2019) and Zhou et al. (2019) demonstrate that networks with random weights can in fact do well, if pruned properly. In this work, instead of pruning we explore weight selection from fixed random values as a way to obtain effective net- works. To provide an intuition for method, consider value for each connection, as typically done. If the weights of N are drawn randomly from an ap- propriate distribution D (e.g.. (Glorot Bengio, 2010) (He al. 2015)), there an extremely small but nonzero probability that N obtains good accuracy (say, greater than a threshold r) on the given task. Let q denote this probability. Also consider another untrained network N& that has the same architectural configuration as .N but with K > weight choices per connection. If n is the number of connections in N, then Nx contains within K" different network instantiations that are architecturally identical to N but that differ in weight configuration. If the weights of Nx are sam- pled from DD then the probability that none of the R" networks obtains good accuracy is essentially (1 - x** This probability decays quickly as either K or increases. Our method finds randomly weighted networks that achieve very high accuracy even with small values of K. For instance, a six layer convolutional network with 2 random values per connection obtains 82% test accuracy on CIFAR-10.
untrained network N with weight
But how do we select good network from these K different networks? Brute-force evaluation of all possible configurations is clearly not feasible due to the massive number of different hypotheses. Instead, present an algorithm, shown in Figure that iteratively searches the best combination of connection values for the entire network by optimizing the given loss. To do this, the method learns real-valued quality score for each weight option. These scores are used to select the weight value of each connection during the forward pass. The scores are then updated in the backward pass based on the loss value in order to improve training performance over iterations.
3.2 LEARNING IN SLOTT MACHINES
Here we introduce our algorithm for the case of fully monlecconnected networks but the description extends seamlessly to convolutional networks. A fully-connected neural network is an acyclic graph con- sisting of a stack of L layers [1,... .L] where the 9th layer has ne neurons. The activation l1(z)) of neuron in layer f is given by
Mx)
(e-) w M
(1)
where w:(0) is the weight of the connection between neuron i in layer and neuron j in layer L - 1, represents the input to the network, and is non-linear function. Traditionally, w starts off as a random value drawn from an appropriate distribution before being optimized with respect to a dataset and loss function using gradient descent. In contrast, our method does not ever update the weights. Instead, associates a set of K possible weight options for each connectior and then optimizes the selection of weights to use from these predefined sets for all connections.
Forward Pass. Let [Wij..... Wark P be the set of the K possible weight values for connection (i,j) and let sijk be the "quality score" of value WiJ.k, denoting the preference for this value over the other possible K- - values. We define a selection function o which takes as input the scores (say1....., Sink] } and returns an index between 1 and K. In the forward pass, we set the weight of (1,5) to Wisa- where k- =
8.
In work we set p be either the arg max function (returning the index corresponding to the largest score) or the sampling from a Multinomial distribution defined by (sigi...., 8i5K }. We refer to the former Greedy Selection (GS). We name the latter Probabilistic Sampling (PS) and
For simplicity, we use the same number of weight options K for all connections in a network. For brevity, from now on we omit the superscript denoting the layer.
4

---

Under review as a conference paper at ICLR 2021
860
140
(b)
Itasiceds
Sdaad Wegto
Sdared Wegbo
Rindatty
Sckood Draga
Juadesty
Natwook
Newwor
Natwers
Figure 2: Selecting from only = weight options per connection already dramatically improves accuracy compared to an untrained network that performs at random chance (10%) on both (a) MNIST and (b) CIFAR-10. The first bar in each plot shows the performance of untrained ran- domly initialized network and the second bar shows the results of selecting random weights with GS using K options per connection.
implement it as
p(si). p(ai).....,,8 8i5Kk) ~ Mult
Σk= e
efijk
Ek
eiik
Skml
The empirical comparison between these two selection strategies is given in Section
4.5
We note that, although K values per connection are considered during training (as opposed to the infinite number of possible values of traditional training), only one value per connection is used at test time. The final network is obtained by selecting for each connection the value corresponding to the highest score (for both GS and PS) upon completion of training. Thus, the effective capacity of the network at inference time is the same that of traditionalll-traine network.
Backward Pass. In the backward pass, all the scores are updated with araight-through gradient estimation since has zero gradient almost everywhere. The straight-through gradient estima- tor (Bengio et al. (201)) treats p essentially as the identity function in the backward pass by setting the gradient of the loss with respect to Sigk
UL da(x))
Mx),
(e" W Gj
(3)
Befk
for ht E [1,..., layer E. Given a as the learning rate, and ignoring momentum, we update the scores via stochastic gradient descent
..K K} where L is the objective function. a(x) is the pre-activation of neuron in
Sijk = Sijk aV Bask
(4)
where $ijk is the score after the update. Our experiments demonstrate that this simple algorithm learns to select effective configurations of random weights resulting in impressive results across different datasets and models.
EXPERIMENTS
4.1
EXPERIMENTAL SETUP
The weights of all our networks are sampled uniformly at random from a Glorot Uniform distribu- tion (Glorot& & Bengio, 2010), U(-oz, where a. is the standard deviation of the Glorot Normal distribution. We ignore K, the number of options per connection, when computing the standard deviation since does not affect the network capacity. Like for the weights, we initialize the scores independently from uniform distribution U(y, 7 + Aaz)) where and À are small constants. We use 0.1 for all fully- fully-connected layers and À to when initializing convolutional layers. We always set to O. We use 15% and 10% of the training sets of MNIST and CIFAR- 10, respectively, for validation. We report performance on the separate test set. On MNIST, we experiment with the Lenet-300-100 (Lecun al.) 1998) architecture following the protocol in Frankle & Carbin (2018). We also use the VGG-like architectures used thereof and in Zhou et al. (2019) and Ramanujaa jn et al. (2019). We denote these networks CONV-2, CONV-4. and CONV-6 For completeness, these architectures and their training schedules are provided in Appendix C All our plots show the aver- ages of five different independent trials. Error bars whenever shown the minimum and maximum
5

---

Under review as a conference paper at ICLR 2021
Lenet On MNIST
CONV-2 on CIFAR-10
CONV-4 on CIFAR-10
CONV-6 on CIFAR-10
95
97.6
76
97.0
65.0
150 76
30
50
77
50
50
130
Weggtt
Selected Weigits (05)
Selected Weights (PS)
Figure 3: Comparison with traditional training CIFAR-10 and MNIST. Performance of Slot Machines improves by increasing (here we consider K {2,8, 64, 128}) although the gains after K 8 are small. For CONV-6 (the deepest model considered here), approach using GS achieves accuracy comparable to that obtained with trained weights, while for CONV-2 and CONV- 4 it produces performance only slightly inferior that of the optimized network. Furthermore, as illustrated by the error bars in these plots, the accuracy variances of Slot Machines with GS are much smaller than those of networks traditionally trained by optimizing weights. Accuracies measured on the test set over five different trials using carly stopping on the validation accuracy with a horizon of 30 epochs for all models.
CONV-4 on CIFAR-10
CONV-6 on CIFAR-10
VGG-19 on CIFAR-10
88.5
92.5
86.5
88.0
92.0
Test Accuracy
86.0
87.5
91.5
85.5
87.0
85.0
91.0
86.5
84.5
86.0
90.5
90.0
400
450
500
550
600
650
700
2500
3000
3500
Tern Flops
Tera Flops
Tera Flops
Learned Weights
Selected Weights (GS)
Finetuned Selected Weights (GS)
Figure 4: Finetuning Selected Weights. Finetuning Slot Machines improves test set performance CIFAR-10. For CONV-4 and CONV-6 this results in better accuracy compared to the same networks learned from scratch at comparable training cost (shown on the x axis). All Slot Machines here use K 8 options per edge.
over the trials. A core component of our algorithm is the hyperparameter K which represents the number of options per connection. As such, we conduct experiments with E {2, 64, 128] and analyze the performance K varies. When not otherwise noted, used the Greedy Selection (GS) method. We empirically compare GS to Probabilistic Selection (PS) in 4.5
4.2 SLOT MACHINES VERSUS TRADITIONALLY-
NETWORKS
We compare the networks using random weights selected from our approach with two different base- lines: (1) randomly initialized networks with one weight option per connection, and (2) traditionally- trained networks whose weights are optimized directly. These baselines are off-the-shelf modules from Py Torch (Paszke al. 2019) which we train in the standard way according to the schedules presented in Appendix C
As shown in Figure 2 untrained dense networks perform at chance, if they have only one weight per edge. However, methodologically selecting the parameters from just two random values for each connection greatly enhances performance across different datasets and networks. Even better, as shown in Figure 3 as the number of random weight options per connection increases, the perfor- mance of these networks approaches that of traditionally-trineed networks with the same number of

---

Under review as a conference paper at ICLR 2021
Lenet on MNIST
CONV- on CIFAR-10
CONV-6 on CIFAR-10
the
16
40
20
20
20
40
60
100
125
40
60
80
100
120
20
80
100
95
801
96
Accroay
60
40
30
0.03
0.15
0.2
0.5
0.3
0.2
0.4
0.6
0.5
mide sno (MB)
moddl 5i00 (MBB)
moddl size (MB)
Weight
Global
Figure 5: Sharing random weights: Slot Machines using the same set of K random weights for all connections layer or even in the entire network perform quite well. However, they do not match the performance of Slot Machines that use different sets of weights for different connections. The benefit of sharing weights is that the space needed store these networks is substantially smaller compared to the storage footprint of slot machines with unshared weight We do not include the curves for slot machines with unshared weights the second row because they are disproportionately too large relative to the shown plots. As an example, Lenet model with unshared weights needs 1MB storage.
parameters, despite containing only random values. Malach al. (2020) proved that any "ReLU network of depth e can be approximated by finding weighted-suunetworr. of a random network of depth 2 and sufficient width." Without pruning, our selection method finds within the superset of fixed random weights 6 layer configuration that performs well 6 layer traditionally-train network.
4.3 FINETUNING SLOT MACHINES
Our approach can also be viewed as a strategy to provide better initialization for traditional training. To assess the value of such a scheme, we finetune the networks obtained after training Slot Machines for 100 epochs (see Appendix C for implementation details). Figure 4 summarizes the results in terms of training time (including both selection and finetuning) test accuracy. It can be noted that for the CONV-4 and CONV-6 architectures, finetuned Slot Machines achieve higher accuracy compared to the same models learned from scratch, effectively at additional training cost. For VGG-19, finetuning improves accuracy, but the resulting model still does not match the performance of the model trained from scratch.
To show that the weight selection in Slot Machines does in fact impact performance of finetuned models, finetune from different Slot Machine checkpoints. If the selection is beneficial, then finetuning from later checkpoints will show improved performance. As shown Figure 6 this is indeed the the test set.
finetuning from later Slot Machine checkpoints results in higher performance
4.4 SHARING RANDOM WEIGHTS
Inspired by quantized networks (Courbariaux & Bengio 2016 Rastegari et al.) 2016: Hubara et al.) 2017 Wang et al. 2018), in this experiment consider slot machines under two different settings. The first constrains the connections in a layer to share the same set of random weights. The second
Thhe set of shared values for the weights can be stored in lookup table and thus the selected weight for each connection is compactly represented by low-hit index into the table.

---

Under review as a conference paper at ICLR 2021
MNIST on CIFAR-10
CONV-2 and CONV.4 CIFAR-10
86.0
64.0
8 CChngge of Sclegaa Natarkk Neteok
12.0
16.0
Text Accuracy
8.0
84.5
4.0
84.0
2.0
1.0
83.5
20
60
80
100
Epoch
Selected Network (GS)
Selected Network (PS)
20
40
60
80
100
Slot Machine Checkpoint
CONV.4 Finetueed
CONV66 Finetuned
Weight exploration in Slot Ma- chines. The vertical axis shows (on log scale) the percentage of weights changed af- ter every five epochs as training progresses. It can be seen that, compared to PS, GS is much less exploratory and converges rapidly preferred configuration of weights. On the other hand, due to its probabilistic sam- pling, PS keeps changing the weight selec- tions even in late stages of training.
Figure 7:
Figure 6: Finetuning from different Slot Ma- chine checkpoints. Slot Machine checkpoint shows the number of training epochs used for weight selection before switching to finetuning (performed for 100 epochs). Performance is mea- sured on the test set using early stopping deter- mined by the maximum validation accuracy dur- ing finetuning.
setting is even more restricting by requiring all connections in the network to share the same set of K random weights. Under the first setting, at each layer the weights are drawn from the uniform distribution U(-or,,a)) where og the standard deviation of the Glorot Normal distribution for layer f. When using a single set of weights for the entire network, we sample the weights independently from U(-Ō, a). is the mean of the standard deviations of the per layer Glorot Normal distributions.
Each of the weights is still associated with a score. The slot machine with shared weights is then trained as before. This approach has the potential of compressing the model although the full set of of scores is still needed.
As shown in Figure 5 these models continue to do well when K large enough. However, unlike conventional slot machines, these models do not do well when K is very small, e.g., K = 2. Furthermore, when K < 64, the accuracy exhibits large variance from run to run, as evidenced by the large error bars in the plot. This is understandable, restricted to search in a much smaller space of parameter combinations and thus the probability of finding winning combination is greatly reduced.
the slot machine with shared weights is
4.5 GREEDY SELECTION VERSUS PROBABILISTIC SAMPLING
we consider two different methods for sampling our networks in the forward pass: a greedy selection where the weight corresponding to the highest score is used and stochastic selection which draws from a proper distribution over the weights. We compare the behavior of our networks under these two different protocols.
As detailed in Section 3.2
As seen Figure 3 GS performs better. To fully comprehend the performance differences between these two strategies, it is instructive to look at Figure 7 which reports the percentage of weights changed every epochs by the two strategies. PS keeps changing a large percentage of weights even in late stages of the optimization, due to its probabilistic sampling. Despite the network changing considerably, PS still manages to obtain good accuracy (see Figure indicating that there are poten- tially many good random networks within Slot Machine. However, hypothesized in Ramanujan et al. (2019), the high variability due to stochastic sampling means that the same network is likely never rarely observed more than once in any training run. This makes learning extremely chal- lenging and consequently adversely impacts performance. Conversely, GS is less exploratory and converges fairly quickly stable set of weights.
8

---

Under review as a conference paper at ICLR 2021
CONV-6 on CIFAR-10
Epoch 0
Epoch 50
Epoch 100
16
17.5
14
6
15.0
12
12.5
10
Density
4
10.0
7.5
2
5.0
2.5
0
0.0
0.1
0.0
0.1
0.1
0.0
0.1
0.1
0.0
0.1
Initial Weights
Initial Weights
Initial Weights
conv-layer-I (GS)
conv-layer-2 (GS)
fo-layer-1 (GS)
conv-layer-I (PS)
conv-layer-2 (PS)
fo-layer-1 (PS)
Figure 8: The distributions of the selected weights in the first two convolutional and the first fully- connected layers of CONV-6 on CIFAR-10. 10. Starting from purely uniform distributions, Slot Ma- chines progressively choose large magnitude weights training proceeds. See Appendix[]for plots showing similar behavior in other Slot Machines.
From Figure 3, we can also notice that the accuracy of GS improves or remains stable as the value of K is increased. This is not always the case for PS when K 2 8. We claim this behavior is expected since GS more restricted in terms of the choices it can take. Thus, GS benefits more from large values of K compared to PS.
4.6 DISTRIBUTION OF SELECTED WEIGHTS
Here we look at the distribution of selected weights at different training points order to understand why certain weights are chosen and others not. As shown in Figure both GS and PS tend to prefer weights having large magnitudes as learning progresses. This propensity for large weights might help explain why methods such as magnitude-based based pruning of traditionally-trac trained networks work as well as they do. Unlike the weights, we find that the scores associated to the selected weights form a normal distribution overtime as shown in Figure in the Appendix.
CONCLUSION AND FUTURE WORK
This work shows that neural networks with random weights perform competitively, provided that each connection is given multiple weight options and that good selection strategy is used. We in- troduce simple selection procedure that is remarkably effective and consistent producing strong weight configurations from few random options per connection. We also demonstrate that these selected configurations can be used as starting initializations for finetuning, which often produces accuracy gains over training the network from scratch, at comparable computational cost. Our study suggests that our method tends to naturally select large magnitude weights as training proceeds. Future work will be devoted further analyze what other properties differentiate selected weights from those that are not selected, as knowing such properties may pave the way for more effective initializations for neural networks.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.
Leo Breiman, Jerome Friendman, Charles J. Stone, and R. A Olstein. Classification and regression trees. Wadsworth & Brooks/Cole Advanced Books & Software., Monterey, CA, 1984. ISBN
978-0-412-04841-8.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel fierbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Matthieu Courbariaux and Yoshua Bengio. Binarynet: Training deep neural networks with weights and activations constrained to +1 -1, 2016. URL http://arxiv.orgg/
602.
02:30
Jonathan Frankle and Michael Carbin, The lottery ticket hypothesis: Finding sparse, trainable neural networks, 2018.
Adam Gaier and David Ha. Weight agnostic neural networks, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth Interna- tional Conference Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learming Research, pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
K. He, X. Zhang. S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level perfor- mance on imagenet classification. In 2015 IEEE International Conference on Computer Vision (ICCV), pp. 1026-1034 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, pp. 770-778, 2016.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the International Conference on Computer Vision (ICCV), 2017.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Fix your classifier: the marginal value of training the last weight layer. In ICLR, 2018
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-ia,iv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Jour- nal of Machine Learning Research, 18(1):686968888 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Alex Krizhevsky. Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances Neural Information Processing Systems, volume 25, pp. 1097-105. Curran Associates, Inc., 2012.
Yann Lecun, Le' on Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( 86(11):2278-233 1998.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: Single-shot network pruning based connection sensitivity. In ICLR, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr. A signal propaga- tion perspective for pruning neural networks at initialization. In ICLR, 2020.
10

---

Under review as a conference paper at ICLR 2021
Hartmut Maennel, Ibrahim Alabdulmohsin, Ilya Tolstikhin, Robert J. N. Baldock, Olivier Bousquet, Sylvain Gelly, and Daniel Keysers. What do neural networks learn when trained with random labels?, 2020.
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang. Zach De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Neural Information Processing Systems (NeurIPS), 2019.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subsetsum: Logarithmic over-parameterization is sufficient, 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in a randomly weighted neural network?, 2019.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks, In Computer Vision ECCV2010 pp. 525-542, 2016. URL http:/xxxvvv.... abs/ 1603. 05279
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Neural Information Processing Systems (NIPS), 2015.
Amir Rosenfeld and John K. Tsotsos. Intriguing properties of randomly weighted networks: Gen- eralizing while learning next to nothing. In 2019 16th Conference on Computer and Robot Vision (CRV). pp. 9-16, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet: A Large-Scate Scale Hierarchical Image Database. In CVPR, 2009.
K. O. Stanley and R. Mikkuulaieen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2):99-127, 2002.
Hidenori Tanaka, Daniel Kunin, Daniel L.. K. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 6000-6010, 2017.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In ICLR, 2020.
P. Wang, Q. Hu, Y. Zhang, C. Zhang, Y. Liu, and J. Cheng. Two-step quantization for low-bit neural networks. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4376-4384, 2018. doi: 10. 101110//....2018..000 8.00460.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Neural Information Processing Systems (NIPS), 2014.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks, 2016.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask, 2019.
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In ICLR, 2017. //trvv////xii.ae www.wwwwww..o..aa.aa.aaaaaaaaaaa 01177711171111888111111111111181
11

---

Under review as a conference paper at ICLR 2021
A RELATION TO PRUNING
The models learned by our algorithm could in principle be found by applying pruning bigger network representing the multiple weight options in the form of additional connections. One way to achieve this by introducing additional "dummy" layers after every layer & except the output layer. Each "dummy" layer will have K identity units where с = R2 * Re++1 and ny is the number of neurons layer f. The addition of these layers has the effect of separating out the random values for each connection in our network into distinct connection weights. It is important that the neurons of the "dummyy" layer encode the identity function to ensure that the random values can pass through it unmodified. Finally, in order to obtain the model learned by our system, all connections between a layer and its associated "dummy" layer must be pruned except for the weights which would have been selected by our algorithm shown in Figure 9 This procedure requires allocating bigger network and is clearly more costly compared to our algorithm.
Figure 9: In principle, is possible to obtain our network (left) by pruning bigger network con- structed ad-hoc (right). In this example, our slot machine uses K = 2 options per connection (i,j). The green-colored connections represent the selected weights. The square boxes in the bigger net- work implement identity functions. The circles designate vanilla neurons with non- lineiin activation functions. Red dash lines in our network represent unchosen weights. These lines in the bigger network would correspond to pruned weights.
B EXPERIMENTAL COMPARISON WITH PRIOR PRUNING APPROACHES
Our approach is similar to the pruning technique of Ramanuuja et al. (2019) as their method too does update the weights of the networks after initialization. Furthermore, their strategy selects the weights greedily, as in our GS. However, they use one weight per connection and employ pruning uncover good subnetworks within the random network whereas we use multiple random values edge. Additionally, we do not ever prune any of the connections. We compare the results of our networks this prior work T We also compare with supermasks (Zhou al., 2019). Supermasks employ probability distribution during the selection which makes them reminiscent of our PS models. However, they use a Bernoulli distribution at each weight while PS uses Multinomial distribution at each connection. Also, like Raaaauujan et al. (2019), supermasks have one weight per connection and perform pruning rather than weight selection. Table[[hhow that GS achieves accuracy comparable that of Ramanujan et al. (2019) while PS matches the performance of supermasks. These results suggest an interesting empirical performance equivalency among these related but distinet approaches.
12

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison with Ramanujan et two rows are from the respective papers.
2019 and (Zhou et al.
2019
The results of the first
Method
Lenet
CONV-2
CONV-4
CONV-6
Ramanujan et al.
2019)
77.7
85.8
88.1
SNIP Zhou al.
2019
98.0
66.0
72.5
76.5
Slot Machines (GS)
98.1
77.2
84.6
86.3
Slot Machines (PS)
98.0
67.8
76.7
78.3
Table Architecture specifications of the networks used in our experiments. The Lenet network is trained on MNIST. The CONV-r models are the same VGG-like architectures used in (Frankle & Carbin 2018 Zhou et al. 2019 Ramanujan et al. 2019). All convolutions use x filters and pool denotes max pooling.
Nenwork
Lenet
CONV-2
CONV-4
CONV-6
VGG-19
2x64, pool
2x128, pool
64, 64, pool 128, 128, pool 256, 256, pool
2x256, pool
64, 64, pool 128, 128, pool
4x512, pool
Convolutional Layers
64, 64, pool
4x512, avg-pool
Fully-connected Layers
300,
100, 10
256, 256, 10
256, 256, 10
256, 256, 10
10
Epochs: GS
140
160
140
140
100
C FURTHER IMPLEMENTATION DETAILS
We find that a high learning rate is required when sampling the network probabilisticallyy- be- haviour which was also observed in Zhou et al. (2019). Accordingly, we use learning rate of 25 for all PS models except the six layer convolutional network where we use learning rate of 50. We did not train 19 using probabilistic selection. Also, a slightly lower learning rate helps GS networks when K 2 64. Accordingly, we set a constant learning rate 0.1 for GS models for K E {2 and 0.01 for K E {64, 128]. When optimizing the weights directly from scratch or fine-tuning, we decay the learning rate by factor of 10% at epoch 20 for all models except when training CONV-2 and CONV-4 from scratch where we decay the rate epoch 60. Learned weights and fine-tuned models all use the same initial learning rate of 0.01. All the VGG-19 models use an initial learning rate of 0.1 which is decayed by factor of 10% at epoch 80 and additionally at epoch 120 when directly optimizing the weights from scratch. Finetuning in VGG-19 also starts with an initial learning rate of 0.1 which is reduced by factor of 10 at epoch 20.
Whenever we sample using PS, we train for additional 40 epochs relative to the number of epochs used by the corresponding GS model shown in Table 2 We do this compensate for the slow convergence of PS models as shown in Figure 7 All finetuned models are trained for 100 epochs. When directly optimizing the weights from scratch, we set the number of epochs to be the sum of the number of epochs used for the corresponding selection checkpoint and that of the finetuned model; we then report the test accuracy based on early stopping with a horizon of 30 with respect to the validation accuracy.
We use data augmentation and dropout (with a rate of p = 0.5) when experimenting on CIFAR- 10 (Krizhevsky 2009). All models use batch size of 128 and stochastic gradient descent optimizer with a momentum of 0.9. We do not use weight decay when optimizing slot machines (for both GS and PS ). But do use weigh decay of le 4 for all directly optimized models (training from scratch and finetuning). We use batch normalization in VGG-19 but the affine parameters are never updated throughout training.
13

---

Under review as a conference paper at ICLR 2021
D DISTRIBUTION OF SELECTED WEIGHTS AND SCORES
As discussed in Section 4.6 and shown in Figure g we observe that slot machines tend to choose increasingly large magnitude weights as learning proceeds. In Figures Io II 12 of this appendix, we show similar plots for other models. We reasoned that the observed behavior might be due to the Glorot Uniform distribution from which the weights are sampled. Accordingly, we performed ablations for this where we used Glorot Normal distribution for the weights as opposed to the Glorot Uniform distribution used throughout the paper. As shown in Figure [Oa] the initialization distribution do indeed contribute to observed pattern of preference for large magnitude weights. However, initialization may not he the only reason as the models continue to choose large magnitude weights even when the weights are sampled from Glorot Normal distribution. This is shown more clearly in the third layer of Lenet which has relatively fewer weights compared to the first two layers. We also observed similar behavior in normally distributed convolutional layers.
Different from the weights, notice that the selected scores are distributed normally as shown in Figure [2] The scores in PS move much further away from the initial values compared to those in GS. This is largely due to the large learning rates used in PS models.
E SCORES INITIALIZATION
We initialize the quality scores by sampling from a uniform distribution U(7, + Aaz). ). As shown in Figure [3] observe that our networks sensitive the range of the uniform distribution the scores are drawn from when trained using GS. However, as expected we found them to be insensitive the position of the distribution y. Generally, narrow uniform distributions, e.g., U(0, 0.1), lead to higher test set accuracy compared to wide distributions e.g., U(0, 1). This matches intuition since the network requires relatively little effort to drive a very small score across small range compared to large range. To concretize this intuition, take for example a weight w that gives the minimum loss for connection (i, j). its associated score is initialized poorly to small value, and the range is small, the network will need little effort to push it to the top to be selected. However, if the range large, the network will need much more effort to drive to the top for W. We believe that this sensitivity to the distribution range could be compensated by using higher learning rates for wider distributions of scores and vers.
14

---

Under review as a conference paper at ICLR 2021
Lenet on MNIST
Epoch 0
Epoch 50
Epoch 100
5
Density
3
2
2
Initial Weights
Initial Weights
Initial Weights
(a) Glorot Normal Initialization
Epoch O
Epoch 50
Epoch 100
12
10
10
5
Density
4
4
2
0.2
0.0
0.2
0.25
0.00
0.25
0.25
0.00
0.25
Initial Weights
Initial Weights
Initial Weights
fe-layer-1 (GS)
fe-layer-2 (GS)
fo-layer-3 (GS)
fc-layer-1 (PS)
fc-layer-2 (PS)
fe-layer-3 (PS)
(b) Glort Uniform Initialization
Figure 10: Distribution of selected weights on MNIST. As noted above, both sampling methods tend to choose larger magnitude weights as oppose to small values. This behavior more evident when the values are sampled from Glorot Uniform distribution (bottom) as opposed to Glorot Normal distribution (top). However, layer which has the fewest number of weights of any layer in this work continue to select large magnitude weights even when using normal distribution.
15

---

Under review as a conference paper at ICLR 2021
CONV-2 on CIFAR-10
Epoch 0
Epoch 50
Epoch 100
70
60
50
15
40
Density
40
10
20
20
10
10
0.1
0.0
0.1
0.1
0.0
0.1
0.1
0.0
0.1
Initial Weights
Initial Weights
Initial Weights
CONV-4 on CIFAR-I0
Epoch 0
Epoch 50
Epoch 100
12
10
25
20
Densiy
15
10
0..1
0.0
0.1
0.1
0.0
0.1
0.1
0.0
0.1
Initial Weights
Initial Weights
Initial Weights fe-layer-1 (GS)
conv-layer-I (GS)
conv-layer-2 (GS)
conv-layer- (PS)
conv-layer-2 (PS)
fc-layer-1 (PS)
Figure 11: Distribution of selected weights on CIFAR-10. Similar to the plots shown in Figure g both CONV-2 and CONV-4 CIFAR-10 tend to choose increasingly bigger weights in terms of magnitude as training progresses. Here, we show the distribution the selected networks in the first two convolutional layers and the first fully-connected layer of the above networks but all the layers all slot machines show similar pattern.
16

---

Under review as a conference paper at ICLR 2021
Fully-Connected Layer MNIST
Lenet (GS)
Lenet (PS)
0.14
0.12
0.10
Density
0.08
2
0.06
0.04
0.02
0.00
0.5
0.0
0.5
1.0
-20
-10
0
10
20
Scores
Scores
Epoch 10
Epoch 50
Epoch 100
Distribution of selected scores. Different from the selected weights, the selected scores tend to be normally distributed for both GS and PS. We show only the scores for layer 3 of Lenet because it is the layer with the fewest number of weights. However, the other layers show a similar trend except that the selected scores them have very narrow distributions which makes them uninteresting. Notice that although range U(0, 0.1 o.) where σ₂ is the standard deviation the Glorot Normal distribution, gradient descent is able drive them into the negative region. The scores in PS slot machines move much farther away from the initialization compared to those GS due to the large learning rates used in PS models.
Figure 12:
sample the scores uniformly from the non-negative
17

---

Under review as a conference paper at ICLR 2021
Lenet on MNIST
98
97
Test Accuracy
96
95
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Lambda
Figure 13: Scores Initialization. The models are sensitive to the range of the sampling distribution.
As discussed in Section the initial scores sampled from the uniform distribution U(x AAr The value of does not affect performance, so we always set it to 0. These plots are averages of different random initializations of Lenet MNIST.
18


Reviews:
[{"review_id": "rEl_LNjrzSe", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "### Summary\n\nThe paper investigates a type of neural network in which one of K possible fixed weights is chosen in each neuronal connection. The weights themselves are fixed and random, but the scores that determine which of the weights is chosen are updated through back-propagation using a straight-through estimator. The accuracy and behavior of such networks is studied for small networks on small datasets (MNIST, CIFAR).\n\n### Quality, clarity, originality and significance\n\nThe paper is well-written and easy to follow.\n\nThe main idea seems interesting at first sight and it is well-motivated, but after some consideration of related effects in neural networks, the results do not seem very surprising (see below). I think a deeper exploration of the connection to other phenomena would be necessary to make this paper relevant to the conference, e.g. to weight quantization (to few bits per weight) or to (variational) dropout. The paper seems to not go beyond ad-hoc conclusions of the form that these (peculiar) networks \"perform competitively on challenging datasets\" (which seems to be a bit of an overstatement to me). The authors also claim that the trained networks might be useful for initialization, but to really make this point strongly, a comparison to other practical methods of data-driven initialization on larger datasets with larger architectures might be needed to convince the reader.\n\nWhy do the results not seem surprising to me: It is possible that I misunderstood the algorithm (which we could clarify in the rebuttal period, of course), but in my understanding of the described approach, the straight-through estimation of the scores will lead to preferring the selection of larger (or smaller) weights where standard gradient descent training would lead to larger (or smaller) weights. This is consistent with the distribution of the selected weights as shown in several figures, with the observation that uniform initialization works better than Normal initialization, and with the observation that \"both GS and PS tend to prefer weights having large magnitudes as learning progresses\". It would also account for the observation of the similarity in error rates when the network has a sufficient number of weights to choose from.\n\n* Pros: interesting idea, the paper is well-written\n* Cons: of limited interest to the conference audience I believe; not clear if there is practical relevance or potential to improve scientific understanding\n\n### Detailed/minor comments\n* The main bullet points at the end of the introduction were not fully substantiated in the paper in my opinion: (1) I was not fully convinced of \"a performance equivalence between random initialization and training\", because the slot machines are effectively *trained*. (2)\"demonstrates that current networks can model challenging non-linear mappings extremely well even with random weights\" is not 100% clear because the weights are a *choice* among a set of *initially* random weights, but that choice is a result of training. (3)\"connects to recent observations\". This seems to happen mostly in the two sentences before 4.3 and there connection *and* statement are not entirely convincing to me \"We find a random 6 layer network that performs as well as a 6 layer trained network without any form of pruning.\" Here it seems to me that the slot machine after training is in fact not random, because it was trained, and that training exploited weight-correlations that potentially span multiple layers. The argument could be extended to regular training in the sense that regular training just picks out the random weights among all the random floating point numbers. (This is a bit exaggerated, but I think it shows why the term \"random 6 layer network\" may be an overstatement after training.) \n* Why is K chosen from the set {2, 8, 64, 128} - it seems that some natural values in this sequence are missing or that a more log-uniform spread would be more \"natural\". Maybe there is a specific reason that is not obvious, then it could be mentioned.\n\n### Update after author replies and discussion\nI have updated the review score after reading the authors' reply and revision of the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "mZXe27rVIbN", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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": "##########################################################################\n\nSummary:\n\nThis paper proposes a method to train a neural network by selecting a weight from a set of $K$ randomly generated weights for each edge in the network. Each edge has a different set of random weights. Quality score is assinged to each of $K$ random weights, which determines the weight used in the forward calculation. Instead of optimizing weights directly, the proposed method optimizes the quality scores with the straight-through gradient estimator. Experimental results show that the neural network trained by the proposed method achieves high accuracy compared to random initialization even when $K=2$.\n\n##########################################################################\n\nReasons for score: \n\nOverall, I vote for rejecting. The authors say in Sec. 3 that the goal is to construct non-sparse neural networks with completely random weights that achieve high accuracy. However, the model obtained by the proposed method is no longer a network with completely random weights, because the authors optimize quality scores instead of original weights. It is empirically shown that a neural network can achieve a high accuracy by properly selecting weights from a set of random weights prepared in advance. However, such a result is not so surprising from the viewpoint that the quality scores are optimized.\nAlso, this paper has few practical implications. I would like to see if the network can still achieve a high accuracy when every edge has a common set of $K$ random weights. If this is the case, the proposed method may lead to a network that is efficiently compressed.\n\n\n##########################################################################\n\nMinor concerns:\n\n(p.1) a fixed a set of random weights -> a fixed set of random weights\n\n\n--\n\nRegarding the author responses, I have updated my rating.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jAIYNm12iVn", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary: The work extends an existing algorithm to train a convolutional neural network by selecting a subset of fixed random weights by (1) using multiple random values per weight, (2) using a sampling procedure to select the particular random value for each weight. If these networks are finetuned after random-value selection is performed, they perform close to networks purely trained with SGD on CIFAR-10 and MNIST.\n\nStrong points:\n- Interesting results that extend results on the lottery ticket hypothesis and random weight learning.\n\nWeak points:\n- The paper builds heavily on an existing algorithm, but it does not cite it in the method section.\n- The paper makes many claims and fails to provide evidence for these claims.\n- The work is not clearly motivated. It is unclear why this problem is interesting or the results insightful.\n\nRecommendation (short):\nWhile the results are interesting, the paper is poorly motivated and does not conform to standards of scientific work. I recommend rejecting this work.\n\nRecommendation (long):\nThe method section appears to be independent work, but it is the same as Ramanujan et al., 2019 extended with multinomial sampling. While Ramanujan et al., 2019 are cited, it is not cited in this section. Furthermore, the paper claims that random initialized networks and trained networks perform the same, but it does not lay out evidence or an argument for this. Otherwise, it is unclear why this method is interesting. I recommend rejecting this work.\n\nComments for authors:\n\nI think these are some good initial results that you have, and you can work with that, but right now, the paper has many flaws that need to be ironed out before you make another attempt. I do not think you can get this work accepted in this round and instead should try to learn as much as possible from the discussion for a resubmission.\n\nI think fixing the claim, references, and so forth will be easy. The hard question is, why is your work interesting. Using multiple random values per weight can be seen as some form of quantization\nof weights. Why is your way of doing something similar to quantization more interesting than other forms of quantization? \n\nPlease also consider if it is true that selecting fixed random weights is training or not. Clearly, you are optimizing weights. It does not matter if you do it with SGD, an evolutionary strategy, or your algorithm; in the end, you optimize weights to have particular values. I would say that it should be considered training. But if your method is considered just a different optimization process compared to SGD, why is it interesting? Finding subnetworks, like done in Ramanujan et al., 2019, is interesting because you have smaller trained networks, but you do not have subnetworks.\n\nIt could be interesting if you do (1) a thorough analysis that yields some insights and make this an analysis paper, or (2) try to get better performance by doing both optimizations of weights and selection of weights (but this is very similar to Wortsman et al. 2019).\n\nSome minor things: \n- Equation 3 has an additional W (h(*) already contains the W)\n- Figure 6 has an annotation error; I believe the upper line is supposed to be the PS method\n\n\nRamanujan et al., 2019: What’s Hidden in a Randomly Weighted Neural Network?, https://arxiv.org/abs/1911.13299\nWortsman et al., 2019: Discovering Neural Wirings, https://arxiv.org/abs/1906.00586\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2PjiHeEhDmd", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Update after authors' response**\nI want to thank the authors for their response, and I am happy to see additional results on shared sets of weight values (which allows to easily relate the work to methods for training low-bit-width networks). To further increase impact and significance of the work it would be necessary to really flesh out the advantage of the proposed method over other, similar methods (\"it is not too surprising that the method works, but why would I prefer it over other methods?\"). Nonetheless, the paper presents novel empirical analysis that adds to the body of work on non-standard training of neural networks. To make a clear stance for the reviewer discussion I have therefore increased my score to 7, though I would rate the paper at the lower end of score-7 papers. \n---\n\n**Summary**\nThe paper proposes a novel scheme to obtain well performing neural networks without classical adaptation of weights. Instead, each connection can have one out of K randomly drawn values, and “training” consists of a backpropagation-based procedure to find which value out of the K possible values to select for each weight. The method can be interpreted as finding a high-performing sub-network within a larger network of random weights. However, in contrast to previous methods that literally implement the latter, the proposed method is computationally more efficient. Experiments are performed on a number of neural network architectures on MNIST and CIFAR-10.\n\n---\n**Contributions, Novelty, Impact**\n\n1) Proposal of a novel scheme for finding well-performing networks without explicit training of weights. This is interesting and adds to a growing body of recent work on alternatives to classical training of neural nets (which is insightful for both, developing better training algorithms but also understanding the nature of neural network training). My concern is that the proposed method is conceptually very similar to previously known approaches (pruning a larger network which is also discussed in the paper, but also some methods for training low-bit-weight networks such as [1] and [2]). While the proposed method is an interesting alternative implementation, the advantages compared to the other approaches are fairly limited. Accordingly the potential impact of the work might be somewhat limited as well, I’m afraid.\n\n2) A nice and extensive set of ablations and control experiments, as well as repetitions of experiments to establish statistical significance of the results. The paper, in particular the experimental part is well executed, and the ablations and controls allow for being optimistic about the generality of the findings, which has a positive influence on the potential impact of the work.\n\n3) The paper shows that networks obtained with the proposed scheme can also act as a good initialization for further fine-tuning, leading to very well performing classifiers. This process is also analyzed in terms of overall computational budget (FLOPS) and in 2 of 3 cases shown compares favourably against standard neural network training. In terms of impact this is another nice result to add, but probably not strong enough to replace standard initialization anytime soon.\n\n\n[1] Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1, Courbariaux et al. 2016\n\n[2] XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks, Rastegari et al. 2016\n\n---\n**Score and reasons for score**\nI’m quite torn with this paper - on one hand the method works well, is thoroughly analysed and the paper is very well written and polished (in many respects I would even say this is an exemplary paper). On the other hand the paper suffers from only adding a quite simple variation on existing work. Particularly the work on training low-bit-width networks ([1] and [2] above, as well as later extensions to more than single-bit weights) is conceptually very similar - the forward pass uses constrained weight values but gradient information is accumulated in a real-valued variable. As the appendix notes, the main idea could also be implemented simply via pruning in a larger network (though less computationally efficient). \n\nTo further strengthen the paper it would be good if the paper could answer one (or both) of the following questions: (i) how do the results contribute to understanding weight initialization and the training process, what can the reader learn that wasn’t known already, (ii) what are the concrete advantages of the proposed method over previously proposed alternatives, what does it do better, what shortcomings does it address (is it faster, is training more stable, …)?\n\nI would love to give this paper a very high score because of the great execution and presentation, but the lack of novel insights, or clear methodological advantages makes this hard. I am currently voting for a weak accept (because the paper is very well written and experiments are thorough, if the scoring was based on novelty alone I’m not sure that the paper would clear the bar for a top-tier conference). I am of course happy to reconsider my final verdict in light of the other reviews and authors’ response.\n\n---\n**Strengths**\n1) Great presentation of the work, a very well written paper, and good main results.\n\n2) Experiments are well executed - multiple repetitions, many controls and ablations that one wants to see to improve confidence in the generality of the findings.\n\n\n---\n**Weaknesses**\n1) Little novelty. The proposed algorithm is a nice idea, but it’s not too surprising that it operates essentially on par with a previously proposed pruning method since the algorithm can even be conceptually recast as pruning in a larger network.\n\n2) The writing puts a lot of emphasis and focus on the distinctive features of the method (understandably so given how close it is compared to other methods). But I think it’s also fine to not start off in an almost defensive fashion and simply state that this is another possibility of implementing the same idea but with the following advantages (and disadvantages).\n\n---\n**Correctness**\nReasoning in the paper is sound, experiments are well executed and many control-experiments and ablations are shown.\n\n---\n**Clarity**\nThe paper is very well written, results are nicely presented and related literature is discussed in a useful fashion.\n\n---\n**Improvements (that would make me raise my score) / major issues**\n\n1) The main issue is a lack of novelty. Addressing either (i) how the paper adds new knowledge (in light of the current body of literature) or (ii) stating the precise advantages of the proposed method over alternatives would be crucial. I don’t see an obvious way for (i), but for (ii) a starting point could be to do more detailed comparison against other methods, in particular Ramanujan and see whether the proposed method compares favorably e.g. in terms of training stability of robustness w.r.t. hyper-parameters.\n\n2) Another possibility to add novelty to the paper would be to focus on low-bit-width training, where instead of drawing K values for each weight separately, values are re-used per layer or even across the whole network (typically first and last layers need to be treated differently, i.e. they require more bit-width). Reliable and robust methods to obtain e.g. 2-, 4- or 8-bit networks is a timely and important topic, and the proposed method has potential to contribute to that body of work as well (though it is admittedly a bit of a deviation from the current story and main focus of the paper). I want to add this as a suggestion to the authors (it could work, but it could also severely reduce focus and clarity of the paper), not necessarily as an improvement that I’d expect to see.\n\n---\n**Minor comments**\n\nA) The ICLR header seems to be missing in the PDF file.\n\nB) In the probabilistic version of the method it might be worth experimenting with some “annealing” schedule where the randomness of the method is gradually reduced over training (e.g. via reducing a Gumbel Softmax temperature). Making the magnitude of the scores very large has essentially the same effect but is less controllable since it has to be indirectly influenced via the learning rate. I would expect convergence/test-time performance of the method to benefit from such a schedule and perhaps even help close the gap to “greedy selection”.\n\nC) Is the supplementary material supposed to go into a separate document (did not double-check the submission instructions)?\n\nD) A bit of a nitpick, the phrase that “weights are never updated” might suggest some miraculous phenomenon - I’d rather say there’s a set of weight values, from which one value is probabilistically selected. So if one considers the weight of a particular connection as a random variable (across different forward passes) then the expected value over that random variable changes (smoothly) as training progresses - resembling a standard weight update process quite closely.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The idea behind this paper is to develop a training algorithm that chooses among a fixed set of weights for each true weight in a neural network.  The results are reasonable -- though difficult to quantify as either good or surprising -- performance from the algorithm. A perhaps interesting point is that additional fine-tuning from these found networks can, in some cases, best the accuracy of the original network.

The pros of this paper are that it is a neat original idea. With the exception of the limited scale of the benchmarks (i.e., the selected architectures), the paper is largely well-executed.  The primary shortcoming of the paper, as discussed by the reviewers, is the lack of clarity in its implications. Specifically, it is difficult to position the result as contributing to a practical aim or leading to additional future work.  

Based on the reviews and discussion, my recommendation is Reject. In particular, this paper would be significantly improved by bringing in a strong motivational context and, therefore, additional comparisons.

For example, the context for the work of Ramanujan et al. (2019) is that, perhaps, it is possible to find subnetworks of large initialized networks that will permit more efficient training. In Appendix A, this paper proposes that the technique here could be cast as pruning within a much larger network. Following results from Zhu and Gupta [1] and also Ramanujan et al. (2019), finding a sparse network within a larger network can produce a more accurate network than training a network of equivalent size to the sparse. Therefore, these results could, potentially, be cast and as a more efficient way to perform the techniques of Ramanujan et al. (2019). 

Alternatively, the results that demonstrate that fine-tuning the identified networks improves performance over the standard network could be more robustly evaluated and perhaps cast as either an alternative training technique or leveraged as a technique like warm starting [2].

This is a very interesting and promising direction. It appears that the paper just needs a bit more distillation.

[1] To prune, or not to prune: Exploring the efficacy of pruning for model compression. Michael Zhu and Suyog Gupta. In International Conference on Learning Representations Workshop Track, 2018.

[2] On Warm-Starting Neural Network Training. Jordan T. Ash, Ryan P. Adams. NeurIPS 2020
 

Decision: Reject