RSO: A Gradient Free Sampling Based Approach For Training Deep Neural Networks
Authors: Rohun Tripathi
Bharat Singh
Venue:  (2021)

Abstract: We propose RSO (random search optimization), a gradient free, sampling based approach for training deep neural networks. To this end, RSO adds a perturbation to a weight in a deep neural network and tests if it reduces the loss on a mini-batch. If this reduces the loss, the weight is updated, otherwise the existing weight is retained. Surprisingly, we find that repeating this process a few times for each weight is sufficient to train a deep neural network. The number of weight updates for RSO is an order of magnitude lesser when compared to backpropagation with SGD. RSO can make aggressive weight updates in each step as there is no concept of learning rate. The weight update step for individual layers is also not coupled with the magnitude of the loss. RSO is evaluated on classification tasks on MNIST and CIFAR-10 datasets with deep neural networks of 6 to 10 layers where it achieves an accuracy of 99.1% and 81.8% respectively. We also find that after updating the weights just 5 times, the algorithm obtains a classification accuracy of 98% on MNIST.

Under review as a conference paper at ICLR 2021
RSO: A GRADIENT FREE SAMPLING BASED AP- PROACH FOR TRAINING DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose RSO (random search optimization), gradient free, sampling based approach for training deep neural networks. To this end, RSO adds a perturba- tion a weight in a deep neural network and tests if reduces the loss on a mini-batch. If this reduces the loss, the weight is updated, otherwise the existing weight is retained. Surprisingly, we find that repeating this process a few times for each weight is sufficient train deep neural network. The number of weight updates for RSO is an order of magnitude lesser when compared to backpropaga- tion with SGD. RSO can make aggressive weight updates in each step as there is no concept of learning rate. The weight update step for individual layers also not coupled with the magnitude of the loss. RSO is evaluated on classification tasks on MNIST and CIFAR-10 datasets with deep neural networks of 6 to 10 lay- ers where it achieves an accuracy of 99.1 % and 81.8% respectively. We also find that after updating the weights just 5 times, the algorithm obtains classification accuracy of 98% on MNIST.
INTRODUCTION
Deep neural networks solve variety of problems using multiple layers progressively extract higher level features from the raw input. The commonly adopted method to train deep neural net- works backpropagation (Rumelhart et al. (1985) and it has been around for the past 35 years. Backpropagation assumes that the function is differentiable and leverages the partial derivative w.r.t the weight wy for minimizing the function fx, w) as follows,
Wi+1 = V f(z w)ww;
where is the learning rate. Also, the method is efficient as makes a single functional estimate to update all the weights of the network. As in, the partial derivative for some weight wj. where j / would change once w; is updated, still this change is not factored into the weight update rule for wy- Moreover, may not even be optimal for all weights move in the same direction as obtained from the gradients in the previous layer. Although deep neural networks are non-convex (and the weight update rule measures approximate gradients), this update rule works surprisingly well in practice.
To explain the above observation, recent literature (Du et al. (2019) Li & Liang 2018) argues that because the network is over-paranenn perrpaarametrized the initial set weights are very close the final solution and even a little bit of nudging using gradient descent around the initialization point leads to a very good solution. We take this argument to another extreme instead of using gradient based optimizers which provide strong direction and magnitude signals for updating the weights; we explore the region around the initialization point by sampling weight changes to minimize the objective function. Formally, our weight update rule is
{ W/ we + Aws,
f(a, <= f(z, wi + Aw;) f(x, > [(, wi + Aw;)
W++1
where Aw; is the weight change hypothesis. Here, we explicitly test the region around the initial set of weights by computing the function and update weight if it minimizes the loss, Fig. 1

---

Under review as a conference paper at ICLR 2021
x' = Xp Ax
f(x)
f(x)
X
X
x' = Xo AX
x' X 77 AX Vf(x)
Figure 1: Gradient descent vs sampling. In gradient descent we estimate the gradient at a given point and take small step in the opposite direction direction of the gradient. In contrast, for sampling based methods we explicitly compute the function at different points and then chose the point where the function is minimum.
Surprisingly, our experiments demonstrate that the above update rule requires fewer weight updates compared to backpropagation to find good minimizers for deep neural networks, strongly suggesting that just exploring regions around randomly initialized networks is sufficient, even without explicit gradient computation. We evaluate this weight update scheme (called RSO; random search optimiza- tion) on classification datasets like MNIST and CIFAR-10 10 with deep convolutional neural networks (6-10 layers) and obtain competitive accuracy numbers. For example, RSO obtains 99. 1% accuracy on MNIST and 81 81.8% accuracy on CIFAR-10 using just the random search optimization algorithm. We do not use any other optimizers for optimizing the final classification layer.
Although RSO is computationally expensive (because it requires updates which are linear in the number of network parameters), our hope that as we develop better intuition about structural properties of deep neural networks, we will be able to accelerate RSO (using Hebbian principles, Gabor filters, depth-wise convolutions). the number of trainable parameters are reduced drastically (Frankle et al.] (2200), search based methods could be viable alternative to back-propagation Furthermore, since architectural innovations which have happened over the past decade use back- propagation by default, a different optimization algorithm could potentially lead to a different class of architectures, because minimizers of an objective function via different greedy optimizers could potentially be different.
2 RELATED WORK
Multiple optimization techniques have been proposed for training deep neural networks. When gra- dient based methods were believed to get stuck local minima with random initialization, layer wise training was popular for optimizing deep neural networks (Hinton et al. (200)); Bengii et al. (2007)) using contrastive methods (Hinton (2002)). (2002). In a similar spirit, recent work, Greedy InfoMax by Löwe et al. (2019) maximizes mutual information between adjacent layers instead of training network end to end. Taylor et al. (2016) finds the weights of each layer independently by solving sequence of optimization problems which can be solved globally in closed form. Weight pertur- bation (Werfel et al. (2004)) based methods have been used for approximate gradients estimation in situations where gradient estimation is expensive. However, these training methods do not general- ize to deep neural networks which have more than 2-3 layers and its not shown that the performance increases as we make the network deeper. Hence, back propagation with SGD or other gradient based optimizers (Duchi et al. (201T): Sutskever et al. (2013); Kingma & Ba (014)) are commonly used for optimizing deep neural networks.
Recently, multiple works have proposed that because these networks are heavily over- parametrized, the initial set of random filters is already close to the final solution and gradient based optimizers only nudge the parameters to obtain the final solution (Du et al. (2019); Li & Liang (2018), ). For example, only training batch-norm parameters and keeping the random filters fixed can obtain very good results with heavily parametrized very deep neural networks (> 800 layers) as shown in Frankle al. (2020). It was also shown that networks can be trained by just masking out some weights without modifying the original set of weights by Ramanujan al. (2020) although one can argue that
2

---

Under review as a conference paper at ICLR 2021
X,
a1
Q:
Q1
X2
42
42
42
42
02
Wia
Wj E Wir
Old
Xn
W1
Wa
and
Onp-1
We
anp
Figure 2: Notation for variables in the network architecture are shown this figure.
masking is very powerful operator and can be used to represent exponential number of output spaces. The network pruning literature covers more on optimizing subsets of an over-parametrized randomly initialized neural network (Frankle & Carbin (2019); [i et al. (2017)). Our method, RSO, is also based on the hypothesis that the initial set of weights is close to the final solution. Here we show that gradient based optimizers may not even be necessary for training deep networks and when starting from randomly initialized weights, even search based algorithms can be a feasible option.
Recently, search based algorithms have gained traction the deep learning community. Since the design space of network architectures is huge, search based techniques are used to explore the placement of different neural modules to find better design spaces which lead to better accuracy ( (Zoph & Le (2016); Liu et al. (2018)). This is done at a block level and each network is still trained with gradient descent. Similar to NAS based methods, weight agnostic neural networks (WANN) (Gaier & Ha (2019)) also searches for architectures, but uses fixed set of weight values 2- +0.5, +1, +2]. WANN operates at a much finer granularity as compared to NAS based methods while searching for connections between neurons and does not gradient descent for optimization. Algorithms like Deep Neuroevolution by/Such et al. (2017) and evolution strategies (ES) by (Salimans al. (2117) are search based optimization algorithms which have been used for training neural networks for reinforcement learning. ES is comprehensively reviewed by [eeyer & Schwefel (2004). Both Deep Neuroevolution and [Salimans al. (2077) create multiple replicas (children) of an initial neural network by adding small perturbations to all the weight parameters and then update the parameters by either selecting the best candidate or by performing a weighted average based on the reward. Both the methods update all the parameters of the network in each update. The problem with changing all the weights is that updating all the parameters of the network at once leads to random directions which are unlikely to contain a direction which will minimize the objective function and slows down learning (results shown in Section 4.5). Also, these methods were only trained on networks with 2-3 hidden layers, which is fairly shallow when compared to modern deep architectures.
3 APPROACH
Consider deep neural network with D layers, where the weights of a layer d with na neurons is represented by Wa {wi, Wz... Wna }. For an input activation Ad-1 {01, ag....0n--1 }, Wa generates an activation Aq {a1, an, J. see Fig Each weight tensor w Wa generates an activation a; E Ad, where can be a scalar or a tensor depending on whether the layer is fully connected, convolutional, recurrent, batch-norm etc. The objective of the training process is to find the best set of weights W, which minimize loss function F(X, W) given some input data X and labels L.
To this end, we initialize the weights of the network with Gaussian distribution NO 22/ like He et al. 2015).. The input data is also normalized to have zero mean and unit standard deviation. Once the weights of all layers are initialized, we compute the standard deviation da of all elements in the weight tensor Wa. In the weight update step for a weight wi E wi,, Aw; is sampled from (1 da). We call this AW, which is zero for all weights of the network but for wj, where
2//weyy |way D)
3

---

Under review as a conference paper at ICLR 2021
Algorithm Random Search Optimization
Input :X,.CCCWW {W1, V2.....b. where Wa (W1, w2.. Ways Wn.
for
c 10 C do d = D
Output:W
10
while d do
X X-EX =(x)
11
for wj E win where wi E Wa do
12
x, ~ X, N,L;AW, + VU, oa); W argminiFFa,,,, F ,
for Wa W do
AW,
for wy wig where Wi, E Wa do
14
m + NO,, / /2/lwaal)
4
15
end
end
16
d d-1
0a (Wa)
end
end
18 end
19 return W
j E ia. For a randomly sampled mini-batch (x,1) E X, L. we compute the loss Fiz, I; W) for W, W + AW, and W 3. If adding subtracting AW, reduces F, W is updated, otherwise the original weight is retained. This process is repeated for all the weights in the network, i.e. to update all the weights of the network once, Ff needs be computed three times the number of weight parameters in the network, 3/W We first update the weights of the layer closest to the labels and then sequentially move closer the input. This is typically faster than optimizing the other way, but both methods lead to good results. This algorithm is described in Algorithm 1.
In Algorithm 1, in line 12, we sample change in weights from Gaussian distribution whose standard deviation is the same as the standard deviation of the layer. This is to ensure that the change in weights is within small range. The Gaussian sampling can also be replaced with other distributions like uniform sampling from (-2aa. 20xa) or just sampling values from a template like (-oa, O, oa) and these would also be effective in practice. The opposite direction of randomly sampled weight is also tested because often it leads to better hypothesis when one direction does not decrease the loss. However, in quite a few cases (close to 10% as per our experiments), not changing the weight at all is better. Note that there is concept of learning rate in this algorithm. We also do not normalize the loss if the batch size increases or decreases as the weight update step is independent of the magnitude of the loss.
There is widespread belief in the literature that randomly initialized deep neural networks are already close to the final solution (Du et al. (2019); & Liang (018)). Hence, regions using bounded step sizes (N (0, a.)) in a single dimension. We chose to update one weight time instead of sampling all the weights of the network as this would require sampling an exponential number of samples to estimate their joint distribution. RSO will be significantly faster even if prior knowledge about the distribution of the weights of individual neurons used.
this prior and explore
EXPERIMENTS
We demonstrate the effectiveness of RSO on image classification tasks by reporting the accuracy on the MNIST (Lecun et al. (1998)) and the CIFAR-10 (Krizhessky (2009) data sets. MNIST consists of 60k training images and 10k testing images of handwritten single digits and CIFAR-10 consists of 50k training images and 10k testing images for 10 different classes of images.
4.1 MNIST
We use a standard convolution neural network (CNN) with convolution layers followed by one fully connected layer as the baseline network for MNIST. All convolution layers use 3 x 3 filter and generate an output with 16 filters channels. Each convolution layer is followed by a Batch Norm layer and then a ReLU operator. Every second convolution layer is followed by 2 x average pool operator. The final convolution layer's 's output is pooled globally and the pooled features are input to fully connected layer that maps to the 10 target output classes. The feature output is mapped to probability values using a softmax layer and cross entropy loss is used as the objective function when choosing between network states. For RSO, we train the networks for 50 cycles described
4

---

Under review as a conference paper at ICLR 2021
Random Search (ours)
Backpropagation (SGD)
WANN Gaier & Ha (2019)
Accuracy 99.12
99.27
94.2
Accuracy of RSO on the MNIST data set compared with back propagation and WANN. The CNN architecture used for RSO and SGD is described i.1.
Table I:
in Section 3 and in each cycle the weights in each layer are optimized once. We sample random 5000 samples in a batch per weight for computing the loss during training. The order of updates within each layer discussed in Section 4.3 After optimizing convolution layer d, we update the parameters of it's batch norm layer using search based optimization as well.
For layer d at cycle c, we sample weight updates from Gaussian with mean 0 and standard de- viation o. At the first cycle, this standard deviation is set to the standard deviation of the layer at initialization dd- We linearly anneal the standard deviation of the Gaussian such that at the final cycle C, of = = /10. RSO is robust to the choice of the initial value of the standard deviation. On varying the initial value from 0. o. to 100g, the minimum accuracy on MNIST is within 0.15 of the maximum accuracy. In Table T we compare the performance of RSO with training using back- propagation (with SGD) and with the training based approach described in Gaier & Ha (2019). The network is able to achieve near state-of of-te-of-the-ar accuracy of 99.12% using random search alone to optimize all the weights in the network.
4.2 SAMPLING MULTIPLE WEIGHTS VERSUS SINGLE WFIGHT
We compare different strategies each with different set of weights that are perturbed at each update step to empirically demonstrate the effectiveness of updating the weights one at time (Algorithm 1). The default strategy is to sample a single weight per update step and cycle through the layers and through each weight within each layer. A second possible strategy is to optimize all the weights in a layer jointly at each update step and then cycle through the layers. The third strategy to sample all the weights in whole network at every update step. For layer-level and network-level sampling, we obtain optimal results when the weight changes for a layer d with weight tensor Wa sampled from (0, oa/10), where da is the standard deviation of all elements in Wa after Wa is initialized for the first time. We optimize each of the networks for 500K steps for each of the three strategies and report performance
MNIST in Figure For the baseline network described in Section 4.1] 500K steps translate to about 42 cycles when using the single weight update strategy. Updating single weight obtains much better and faster results compared to layer level random sampling which, in turn, is faster compared to a network-leve random sampling. When we test on harder data sets like CIFAR-10, the network-level and layer-level strategies do not even show promising initial accuracies when compared to the single weight sampling strategy. The network level sampling strategy is close to how genetic algorithms function, however, changing the entire network is significantly slower and less accurate that RSO. Note that our experiments are done with neural networks with 6-10 layers.
4.3 ORDER OF OPTIMIZATION WITHIN LAYER
When individually optimizing all the weights in layer Wa, RSO needs order for optimizing each of the weights, Wj E Wig, where na is the number of neurons and Wa = {Wi, W2.., Wiay ..Wn.) na is the number of output channels in convolution layer and each neuron has Lxk x weights. where L the number of input channels and k is the filter size. By default, we first optimize the set of weights that affect each output neuron Wia E Wa and optimize the next set and so on till the last neuron. Similarly, in a fully connected layer we first optimize weights for one output neuron Wi, E Wa and then move to the next a fixed manner. These orders do not change across optimization cycles. This ordering strategy obtains 99.06% accuracy on MNIST. To verify the robustness to the optimization order, we inverted the optimization order for both convolution and fully connected layers. In the inverted order, we first optimize the set of weights that interact with one input channel L; E L and then move to the next set of weights and so on. Inverting the order of optimization leads to a performance of 99.12% on the MNIST data set. The final performance for the two runs is almost identical and demonstrates the robustness of the optimization algorithm to a given optimization order in layer.
5

---

Under review as a conference paper at ICLR 2021
100K Steps
200K Steps
300K Steps
400K Steps
500K Steps
600K Steps
Network
88.7
91.81
91.89
92.71
93.01
94.49
Layer 94.85
95.77
96.95
97.24
97.25
97.53
Weight 98.24
98.78
98.94
99.0
99.08
99.12
Table 2: Accuracy of RSO the MNIST data set reported at different stages of training while sampling at different levels at the network level, at the layer level and at the weight level. The final performance and the rate of convergence when sampling at the weight level is significantly better than other strategies.
Stage
convl
conv2
conv3
conv4
Accuracy
D
3 x 3,32
3 x 3, 32
56.30%
Depth-5
3 x 3, 16
3 x 3, 16
3 x 3,32
3 x 3,32
68.48%
Depth-10 10
3 x 3, 16
(3 x 3, 16)
(3 x 3, 32)
(3 3, 32)
x
81.80%
Table 3: Accuracy of RSO with architectures of varying depth on CIFAR-I0. 10. The (+) brackets represent a basic residual block (He et al. (2016) which contains two convolution layers per block and a skip connection across the block, Each convolution layer represented as the filter size and the number of output filters. The conv2 and conv3 stages are followed by a 2 x 2 average pooling layer. The accuracy increases as the depth increases which demonstrates the ability of random search optimization to learn well with deeper architectures.
4.4 CIFAR-10
On CIFAR-10, show the ability of RSO to leverage the capacity of reasonably deep convolution networks and show that performance improves with an increase in network depth. We present results on architectures with 2, 4 and 9 convolution layers followed by one fully connected layer. The CNN architectures are denoted by Depth-l, where l is the number of convolution layers plus 1 and the details of the architectures are reported in Table 3 Each convolution layer is followed by a Batch Norm layer and a ReLU activation. The final convolution layer output is pooled globally and the pooled features are input to fully connected layer that maps to the 10 target output classes. For RSO, we train the networks for 500 cycles and in each cycle the weights in each layer are optimized once as described in Sectior3 To optimize each weight we use a random batch of 5000 samples. The performance of RSO improves significantly with increase in depth. This clearly demonstrates that RSO is able to leverage the improvements which come by increasing depth and is not restricted to working with only shallow networks. A comparison for different depth counts is shown in Table
3
To compare with SGD, we find the hyper-parameten for the best performance of the Depth-10 architecture by running grid search over batch size from 100 to 20K and learning rate from 0.01 to 5. In RSO, we anneal the standard deviation of the sampling distribution, use weight decay and do not use any data augmentation. For SGD we use a weight decay of 0.0001, momentum at 0.9, no data augmentation and step down the learning rate by a factor of 10 twice. The top performance on CIFAR- 10 using the Depth- 10 network was 82.94%.
4.5 COMPARISON OF TOTAL WEIGHT UPDATES
RSO samples each weight once per cycle and weight may or may not be updated. For C cycles, the maximum number of times all weights are updated is C. Baok-propag based SGD updates each weight in the network at each iteration. For a learning schedule with E epochs and B batches per epoch, the total number of iterations is E x B. On the left in Figure we report the accuracy versus the number of times all the weights are updated for RSO and SGD on the MNIST data set. For SGD, we ran grid search as described in Section 4.4 to find hyper-parameter that require the minimum steps reach 2 99.12% accuracy because that is the accuracy of RSO in 50 cycles. We found that using a batch size of 5000, a learning rate of 0.5 and a linear warm-up for the first epochs achieves 99.12% in less than 600 steps.

---

Under review as a conference paper at ICLR 2021
80
80-
00
94
Accuracy
60
50-
60-
60
30-
20
20
10
20
40
50
100
200
300
400
500
50
100
150
200
250
300
10
350
700 1059
1400
1750
Iterations
Iteraions
Iterations
Iterations
Figure 3: Accuracy versus the number times all the weights are updated for RSO and SGD on the MNIST and on the CIFAR-10 data set. The results demonstrate that the number of times all the weights need to be updated RSO typically much smaller than the corresponding number in SGD. Note that since the weight update step for RSO is linear in the number of parameters of the network, each weight update step is significantly more expensive. For example, on MNIST, SGD takes 10 seconds per epoch while RSO takes 12 minutes. On CIFARIO, RSO takes 52 minutes per epoch while SGD) takes 29 seconds.
MNIST Parallel vs Sequential updates
CIFAR Parallel vs Sequential updates
99
80
98
70
Accurac)
97
Accuracy
60
50
40
Sequential updates
Sequential updates
Layer weights update parallel
Layer weights update parallel
Neurons update parallel
Neurons update paralle!
20
0.3 Updates (1e6)
0.5
0.0
2.0
Updates (1e7)
(a)
(b)
Figure 4: Sequential updates versus updating all the weights in convolution layers in parallel or updating the neurons in parallel. Sequential updates perform the best for both data sets. The parallel update scheme enables using distributed learning techniques to reduce wall-clock time to reach convergence for MNIST. For CIFAR-10 10, the gap between sequential and parallel may be closed by running the parallel setup longer learning schedule using distributed learning hardware.
On the right in Figure we report the accuracy on the Depth-10 network (Table at different stages of learning on CIFAR- 10 for RSO and SGD. We apply grid search find optimal hyper-parameters for SGD such that the result is > 81.8%, which is the accuracy of RSO on the Depth-10 network after 300 cycles. The optimal settings use a batch size of 3000, a learning rate 4.0, momentum at 0.9 and linear warm-up for the first 5 epochs to achieve an accuracy of 81.98% in a total of 1700 iterations. The results on number iterations demonstrate that the number of times weights updated in RSO, C. is typically much smaller than the corresponding number in SGD, E x for both MNIST and CIFAR- 10. Further, RSO reaches 98.0% on MNIST after updating all the weights just 5 times, which indicates that the initial set of random weights is already close the final solution and needs small changes to reach high accuracy.
4.6 UPDATING WEIGHTS PARALLEL
RSO is computationally expensive and sequential in its default update strategy, section The sequential strategy ensures that the up to date state the rest of the network is used when sampling single weight in each update step. In contrast, the update for each weight during iteration in the commonly used backpropagation algorithm is calculated using gradients that are based on a single state of the network. In backpropagation. the use of an older state of the network empirically proves to be a good approximation to find the weight update for multiple weights. As shown section 4.2 updating single weight at each step leads to better convergence with RSO compared updating

---

Under review as a conference paper at ICLR 2021
weights jointly the layer and network level. If we can search for updates by optimizing one weight at a time and use an older state of the network, we would have an embarrassingly parallel optimization strategy that can then leverage distributed computing to significantly reduce the run time of the algorithm.
We found that the biggest computational bottleneck was presented by convolution layers and ac- cordingly experimented with two levels of parallel search specifically for convolution layers. The first approach was to search each of the weights in layer w/ E Wigr Wa {wi, w2.., Wigs ] in parallel. The search for the new estimate for each weight uses the state of the network before the optimization started for layer d. The second approach we tried was search for weights of each output neuron Wia in parallel. We spawn different threads per neuron and within each thread we update the weights for the assigned neuron sequentially. Finally we merge the weights for all neu- rons in the layer. Results on the MNIST data set are shown on the left and results on the CIFAR-I6 10 data set are shown on the right in Figure + Regarding the rate of convergence, sequential updates outperform both layer-level parallel and updating the neurons in parallel. However, both parallel approaches converge almost as well as sequential search at the end of 50 cycles on MNIST. For the CIFAR- 10 data set, the sequential update strategy seems out perform the parallel search strategies by a significant margin over a learning schedule of 500 cycles. However, given the embarrassingly parallel nature of both parallel search strategies, this limitation may be overcome by running the experiment on a longer learning schedule using distributed learning hardware to possibly close this gap. This a hypothesis which will have be tested experimentally in a distributed setting.
4.7 CACHING NETWORK ACTIVATION
Throughout this paper, we have described neural networks with D convolution layers and fully connected layer. The number of weight parameters [W] = nD x 10+ Σ9 ny x ia x ka x ka, where nd: la and &y are the number of output filters, number of input filters and filter size respectively, for convolution layer d E D. The FLOPs of a forward pass for a batch size of 1 is F = np x 10 + Στ X ia X ka X ka X X sd. where sæ is the input activation size at layer d. Updating all the parameters the network once using a batch size 1 requires [W] x F FLOPs, which leads to a computationally demanding algorithm.
To reduce the computational demands for optimizing a layer d, we cache the network activations from the layer d before optimizing layer d. This enables to start the forward pass from the layer by sampling a random batch from these activations. The FLOPs for a forward pass starting at convolution layer d reduce to Fa = nD X 10 + Ed nhd X ia x kis x ka X 8d X 8a- The cost of caching the activations of layer d - for the complete training set is negligible if computed at batch size large enough that the number of forward iterations La << [Wa = na X ia X ka X kgg The FLOPs for training the parameters once using this caching techniques is Σ 3 [Wal x Fa. This caching strategy leads to an amortized reduction in FLOPs by 3.0 for the MNIST network described
in 4.1 and by 3.5 for the Depth-10 network in Table
CONCLUSION AND FUTURE WORK
RSO is our first effective attempt to train reasonably deep neural networks (2 10 layers) with search based techniques. A fairly naive sampling technique was proposed in this paper for training the neural network. Yet, as can be seen from the experiments, RSO converges an order of magnitude faster compared back-propagation when we compare the number of weight updates. However, RSO computes the function for each weight update, so its training time scales linearly with the number of parameters in the neural network. we can reduce the number of parameters, RSO will train faster.
Another direction for speeding up training would be to use effective priors on the joint distribution of weights and sampling using techniques like Blocked Gibbs sampling. While sampling at the layer and network level lead to a drop in performance for RSO, a future direction to identify highey-correlated and coupled blocks of weights in the network (like Hebbian priors) that can be sampled jointly to reduce computational costs similar to blocked Gibbs. The north star would be a neural network which consists of fixed set of basis functions that need small set of parameters to
8

---

Under review as a conference paper at ICLR 2021
modulate the responses. If construct and train such networks with search based methods, would significantly improve our understanding of deep networks.
REFERENCES
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In Advances in neural information processing systems, pp. 153-160, 2007.
H. Beyer and H. Schwefel. Evolution strategies comprehensive introduction. Natural Computing, 1:3-52, 2004.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. ICLR, 2019.
John Duchi, Elad Hazan, Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(Jul):2211-2159 2011.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. ICLR, 2019.
Jonathan Frankle, David Schwah, and Ari S Morcos. Training batchnorm and only hatchnorm: On the expressive power of random features in cnns, arXiv preprint 20Xiv:2003.0015: 2020.
Adam Gaier and David Ha. Weight agnostic neural networks. In Advances in Neural Information Processing Systems, pp.
2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. Proceedings of the IEEE international conference on com- puter vision, pp. 1026 1034, 2015.
Geoffrey Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 1478):177 2002.
Geoffrey E Hinton, Simon Osindero, and Yee-Whye Teh. A fast learning algorithm for deep belief nets. Neural compatation, 18(7))1527-1554, 2006.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
1rX1v:1412.69980 2014.
Alex Krizhevsky, Learning multiple layers of features from tiny images. Tech Report, 2009.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedingy of the IEEE, 1998.
Hao Li. Asim Kadav, Igor Durdanovie, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. ICLR, 2017.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances Neural Information Processing Systems, pp. 8157-8166, 2018.
Hanxiao Liu, Karen Simonyan, Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.099 09055, 2018.
Sindy Löwe, Peter O'Connor, and Bastiaan Veeling. Putting an end to end-to-end: Gradient-isolated learning of representations. In Advances in Neural Information Processing Systems, pp. 3033-3045, 2019.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in a randomly weighted neural network? CVPR, 2020.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning internal representations by emror propagation. Technical report, California Univ San Diego La Jolla Inst for Cognitive Science, 1985.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Tlya Sutskever. Evolution strategies scalable alternative reinforcement learning. arXiv preprint arviv 1703,03808, 2017.

---

Under review as a conference paper at ICLR 2021
Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Deep neurocvolution: Genetic algorithms are competitive alternative for training deep neural networks for reinforeement learning. arXiv preprint arXiv:1712.0656) 2017.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On importance initialization and momentum deep learning. International conference on machine learning, pp. 1139-1147, 2013.
Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, and Tom Goldstein. Training neural networks without gradients: A scalable admm approach. In International conference on machine learning.
27222723333 2731, 2016.
Justin Werfel, Xiaohui Xie, and H. Scung. Learning curves for stochastic gradient descent in lincar feedfor- ward networks. In Advances in Neural Information Processing Systems 16, 2004.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint arX1v:161..0157, 2016.
10


Reviews:
[{"review_id": "zEHO0tN7p8A", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes an RSO (random search optimization) method for training deep neural networks. This method is gradient-free and based on the Markov Chain Monte Carlo search. In particular, it adds a perturbation to weight in a deep neural network and tests if it reduces the loss on a mini-batch: the weight is updated if this reduces the loss, and retained otherwise. \n\nMerits of the paper: \n+ This paper shows that repeating the RSO process a few times for each weight is sufficient to train a deep neural network. As a result, the number of weight updates is an order of magnitude lesser when compared to backpropagation with SGD. \n+ It can make aggressive weight updates in each step as there is no concept of learning rate. The weight update step for individual layers is also not coupled with the magnitude of the loss. \n+ RSO is evaluated on classification tasks on MNIST and CIFAR-10 datasets where it achieves competitive accuracies.\n\nIssues of the paper:\n- One potential issue is that the method is only evaluated on relatively small networks. I wonder how it works for larger networks such as ResNet-50 and ResNet-101.\n- The current figures only show the comparison in terms of training iterations. I would like to see the comparison in terms of training time, ie accuracy-time curve.\n- It would be interesting to see the performance of RSO on ImageNet and/or COCO.\n\n---------------------------------------------------------------------------------------------------------------------\nI have read the response, and the rating is not changed.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fd3MZaa30FR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nInstead of back-propagation, the authors consider a randomized search heuristic to train the parameters of neural networks. The proposed work is based on the hypothesis that the initial set of neural network weights is close to the final solution. The authors identify the problem that existing randomized search methods update all the parameters of the network in each update. Thus the proposed method updates only a single weight per iteration. Experimental results on MNIST and CIFAR10 show that the proposed method delivers competitive results.\n\n##########################################################################\n\nReasons for score: \n\n \nOverall, I vote for rejecting. Indeed, investigating alternative learning methods for deep architectures is highly relevant. My major concern is about the novelty of the paper and formal presentation (see cons below). I do not expect that the authors can address my concern in the rebuttal period. \n\n \n##########################################################################Pros: \n\nSTRONG\n\n1. Investigating alternative learning methods for deep architectures is highly relevant. \n \n2. Nice practical implementation details are provided like parallel computation or clever caching.\n \n3. This paper provides experiments on well-known benchmark data sets. The results suggest that randomized search heuristics can work well for training the weights of deep neural networks. \n\n \n##########################################################################\n\nWEAK\n \n1. Highly relevant theoretical work in this field is not referenced or discussed, e.g., Nesterov's \"Efficiency of coordinate descent methods on huge-scale optimization problems\" or work on randomized search in general, like \"Evolution strategies - A comprehensive introduction\" by Hans-Georg Beyer and Hans-Paul Schwefel. \n \n2. The novelty is unclear to me. Maybe the presentation is sub-optimal, but I do not see any novel methodology here or insight. To make this more clear: it is well known that randomized search heuristics work very well on a wide variety of optimization problems (both, combinatorial and numerical). The real open question in this field is to *prove* under which conditions these methods will work, and under which conditions these methods will not work. What is the expected number of objective function evaluations? What is the probability that a solutions that is epsilon-close to a \"good\" solution is found in polynomial time? For me, answering any of these questions would make the paper at hand acceptable.\n \n3. The formal presentation regarding classic an recent results can be improved (see below).\n \n##########################################################################\n\nSome statements are unfortunate: e.g., on page 2, the authors state \"the research community has started questioning the commonly assumed hypothesis if gradient based optimizers get stuck in local minima.\". However, this is far from being a \"commonly assumed hypothesis\". It is a matter of fact from numerical optimization that gradient based optimizers *will*for*sure* get stuck in local minima. The \"assumption\" is, that these local minima are bad solutions. The authors must be careful with such statements, since many researchers spent decades to reveal insights into numerical optimization which shall not be ignored by today's scientists. \n\nThis impreciseness in statements appears for recent works as well: On page 3, the authors state that \"weight agnostic neural networks (WANN) also searches for architectures, but keeps the set of weights fixed.\". This is, however, not correct. WANNs evaluate the expected performance of a model over various parameters which are shared by all connections. Computing the expectation over multiple parameters is far from keeping weights \"fixed\". \n \n#########################################################################", "extra_scores": {}, "extra_text": {}}, {"review_id": "NOLh7XxvuHA", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discusses a possible method for training a deep neural network without using backpropagation.  Backpropagation has been very successful in minimizing output errors for both supervised and unsupervised methods and has stood up to challenges from other methods.  The motivation for finding suitable replacements or approximations is to reduce the computational complexity of training neural networks.  This can take the form of reducing the size of the NN required to accomplish a task or simply train an NN with a smaller number of operations. I believe this is a very important new topic to find viable alternatives to backprop.  These kinds of methods have advantages on better-utilizing memory bandwidth, making cheaper hardware more relevant to the training side of NNs.\n\nThe authors do a good job of giving background by citing node perturbation methods, lottery ticket hypothesis, and genetic methods.  They all appear to be pointing to an underlying concept that random initializations in overparameterized networks already have embedded, sparse representations.\n\nThe main result of the paper is that a small number of sequential weight updates using the authors' proposed algorithm rivals the performance of an established method like backpropagation.  The proposed algorithm is simply to perturb weights from a randomly initialized neural network and keep the perturbation if it reduces the loss on a minibatch. This relies on an assumption that a randomly initialized network is close to a final solution. \n\nI really enjoyed this paper. Nearly every question I asked myself while reading it was answered in a subsequent section.  As pointed out, this is the first step at a new concept.  As with any good paper, this paper begets a lot more questions than it completely answers.  \n\nSuggestions:\nSection 3: what is the motivation for using a Gaussian distribution to initialize weights?  Not that I see anything wrong with that, but is there some reason this might be better or worse than other initializations?\nSection 3: “We first update the weights of the layer closest…”.  This could be an area of additional research as to where to update first.  If we look at neuroscience, we see that layers closer to inputs seems to learn first, so might be good to include some discussion on that here.\nSection 4: These are good networks to start with, but I would like to see larger networks that are more relevant to problems today….transformers being trained to useful levels using this method could be a huge and important step. \n\nSection 4.1: It could strengthen the paper to include some analysis on the number of MAC operations required and the number of reads/writes to memory for SGD vs RSO.  This could be useful in this paper, or a subsequent one.\n\nSection 4.2: Some theory likely needs to be developed here.  It would good to add some discussion about the tradeoffs between these options. I believe this is more for future work.\n\nSection 4.5: If the RSO algorithm is more amenable to parallelism, that could be an important advantage.  Some discussion of that vs SGD could also build a stronger case.ZS\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JYuw83ZSc1L", "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": "In this paper, rather than training a DNN using SGD, the proposed idea is to perturb the weights of the network and accept the perturbation if it improves the performance. This naive idea seems to perform almost as well as SGD, and \"an order of magnitude faster\" (see below).\n\nWhile I commend the authors for bringing up the fact that such training is possible (which can be very practical in RAM bound settings). There are at least two things that I would like to see fixed:\n\n- Markov Chain Monte Carlo is mentioned in the abstract and never discussed again. Though the method certainly resembles MCMC to some degree, either you make this connection explicit and say under which probabilistic model this approach corresponds to MCMC, and potentially connect the values sampled over time with a posterior density, or eliminate the references to MCMC. As of now, you simply mention it but it begs a question more than answers anything.\n\n- Why would it be meaningful to compare SGD and RSO in terms of \"cycles\", given that cycles have vastly different computational costs for SGD and RSO? In fact, a comparison in terms of cycles would be useful, but using the same update schedule for SGD that you use for RSO (which of course would make SGD, the competing approach, take a higher computational cost per cycle). Right now you are stating that RSO is an order of magnitude faster... when measured in a unit (cycles) that is much more costly for RSO. That statement is meaningless. So a) show a fair comparison, for instance accuracy vs. compute time, using a state-of-the-art, GPU-optimized version of SGD (and also of RSO). b)  Given that a) is done, it would also be useful to show the current version of  accuracy vs. cycle time if you consider the two potential versions of SGD cycles: parallel updates and sequential updates. That might make RSO not seem as good compared with SGD but would be much more useful to judge when RSO is to be preferred to SGD.\n\nEdit: score modified after reading the authors' reply.\n\nEdit 2: Regarding the issue of optimization getting stuck in local optima or finding global minima (moved my comment here for visibility):\n\nI thank the authors for their flexibility on this issue, but I'd like to weigh in on this saying that from my perspective those statements were actually accurate and useful, and should be kept in the paper as they existed originally. They are properly backed up by citations, unlike the comment of \"getting stuck for sure in a local optimum\", which is very much dependent on the optimization problem. I am willing to follow up with the other reviewers, should they consider I am mistaken.\n\nI have also increased my score after reading the author's response, and I agree that the final decision should not depend on this specific issue. If the paper is accepted, I'd like it to include the original statement, which can be very informative for some readers.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a variant derivative-free optimization algorithm, that belongs to the family of Evolution Strategies (ES) and zero-order optimization algorithms, to train deep neural networks. The proposed Random Search Optimization (RSO) perturbs the weights via additive Gaussian noise and updates the weights only when the perturbations improve the training objective function. Unlike the existing ES and black-box optimization algorithms that perturb all the weights at once, RSO perturbs and updates the weights in a coordinate descent fashion. RSO adds noise to only a subset of the weights sequentially, layer-by-layer, and neuron-by-neuron. The empirical experiments demonstrated RSO can achieve comparable performance when training small convolutional neural networks on MNIST and CIFAR-10. 

The paper contains some interesting ideas. However, there are some major concerns in the current submission:

1) Novelty: there is a wealth of literature in optimization neural networks via derivative-free methods. The proposed algorithm belongs to Evolution Strategies and other zero-order methods, (Rechenberg & Eigen, (1973); Schmidhuber et al., (2007); Salimans et al., (2017). Unforunately, among all the rich prior works on related algorithms, only Salimans et al. (2017) is merely mentioned in the related works. Furthermore, the experiments only compared against SGD rather than any other zero-order optimization algorithms. 

Many ideas in Algorithm 1 was proposed in the prior ES literature:

- Evaluate the weights using a pair of noise, -\deltaW and +\deltaW in Alg1 Line13-14 is known as antithetic sampling Geweke (1988), also known as mirrored sampling Brockhoff et al. (2010) in the ES literature.

- Update the weights by considering whether the objective function has improved or not was proposed in Wierstra et al. (2014) that is known as fitness shaping.

Given the current submission, it is difficult to discern the contribution of the proposed method when compared to the prior works. In addition, the convergence analysis of the zero-order optimization was studied in Duchi et. al. (2015) that includes the special coordinate descent version closely related to the proposed algorithm.

2) Experiments: 

- Although the experiments showcase the performance of sequential RSO, the x-axis in Figure 4 only reported the iterations after updating the entire network. The true computational cost of the proposed RSO is the #forwardpass x #parameters, that is much more costly than the paper currently acknowledges. Also, RSO requires drawing 5000 random samples and perform forward-passes on all 5000 samples for every single weight update. It will be a great addition to include the #multiplications and computation complexity of RSO and the baseline algorithms. 

- More importantly, the paper only compared RSO with SGD in all the experiments. It will significantly strengthen the current paper by including some of the existing ES algorithms. 


In summary, the basic idea is interesting, but the current paper is not for publication and will need further development and non-trivial modification. 


Decision: Reject