RSO: A Gradient Free Sampling Based Approach For Training Deep Neural
  Networks
  We propose RSO (random search optimization), a gradient free Markov Chain
Monte Carlo search 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.
