Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Merits of the paper: 
+ 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. 
+ 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. 
+ RSO is evaluated on classification tasks on MNIST and CIFAR-10 datasets where it achieves competitive accuracies.

Issues of the paper:
- 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.
- 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.
- It would be interesting to see the performance of RSO on ImageNet and/or COCO.

---------------------------------------------------------------------------------------------------------------------
I have read the response, and the rating is not changed.
review_title: Interesting work but with evaluation issues

final_score: rating: 3: Clear rejection
review_content: ##########################################################################

Summary:

Instead 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.

##########################################################################

Reasons for score: 

 
Overall, 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. 

 
##########################################################################Pros: 

STRONG

1. Investigating alternative learning methods for deep architectures is highly relevant. 
 
2. Nice practical implementation details are provided like parallel computation or clever caching.
 
3. 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. 

 
##########################################################################

WEAK
 
1. 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. 
 
2. 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.
 
3. The formal presentation regarding classic an recent results can be improved (see below).
 
##########################################################################

Some 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. 

This 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". 
 
#########################################################################
review_title: Nice work on randomized learning with unclear contribution

final_score: rating: 7: Good paper, accept
review_content: 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).

While 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:

- 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.

- 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.

Edit: score modified after reading the authors' reply.

Edit 2: Regarding the issue of optimization getting stuck in local optima or finding global minima (moved my comment here for visibility):

I 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.

I 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.
review_title: Very simple but potentially very practical idea.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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.

The 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.

The 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. 

I 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.  

Suggestions:
Section 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?
Section 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.
Section 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. 

Section 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.

Section 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.

Section 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


review_title: I enjoyed this paper, and believe it is the seed of something very important. The main result of a viable alternative to backprop may very well be one of the things that pushes AI into the next stage.  My detailed comments are meant to strengthen the paper.  However, the authors answered nearly all of my questions I had while reading.

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