7
$\begingroup$

Neural Networks are usually trained using a gradient based learning algorithm, such as the back propagation algorithm or some variant of it, but can you use global optimization algorithms, such as the Genetic Algorithm, Nelder-Mead Polytope Algorithm, and Particle Swarm Optimisation to train the network?

Since training a neural network all boils down to minimizing a multi-variable cost function, I would assume that it should be easy to do this using a global optimization method, but I have tried to do it myself and I'm getting very bad results.

The GA algorithm reduces my cost function from around 250 (when it is input with random synaptic weights), to only around 170. The Nelder-Mead Algorithm would apparently take years, and I have not yet tried PSO as there is no inbuilt MATLAB function for it.

So is it just accepted that gradient based algorithms are the most suitable for training a Neural Network? If so can someone please point me towards a source of this information? This will be very helpful as I could reference the source in my project to explain why I gave up trying to use global optimization methods to train the network.

Thanks!

$\endgroup$
  • $\begingroup$ Why do you call GA global optimization algorithm since it doesn't necessarily find global optimum? $\endgroup$ – n0p Oct 19 '16 at 13:28
  • $\begingroup$ @n0p Because it tries to find a global optimum? "Global optimization is distinguished from local optimization by its focus on finding the maximum or minimum over all input values, as opposed to finding local minima or maxima." $\endgroup$ – endolith Dec 3 '18 at 3:29
6
$\begingroup$

Reading your question, I understand that you think that "global optimization methods" always give the global optimum whatever the function you are working on. This idea is very wrong. First of all, some of these algorithm indeed give a global optimum, but in practice for most functions they don't... And don't forget about the no free lunch theorem.

Some classes of functions are easy to optimize (convex functions for example), but most of the time, and especially for neural network training criterion, you have : non linearity - non convexity (even though for simple network this is not the case)... These are pretty nasty functions to optimize (mostly because of the pathological curvatures they have). So Why gradient ? Because you have good properties for the first order methods, especially they are scalable. Why not higher order ? Newton method can't be applied because you have too much parameters and because of this you can't hope to effectively inverse the Hessian matrix.

So there are a lot of variants around which are based on second order method, but only rely on first order computations : hessian free optimization, Nesterov gradient, momentum method etc...

So yes, first order methods and approximate second order are the best we can do for now, because everything else doesn't work very well.

I suggest for further detail : "Learning deep architectures for AI" from Y. Bengio. The book : "Neural networks : tricks of the trade" and Ilya Sutskever phd thesis.

$\endgroup$
  • $\begingroup$ scale here is very important. Back propagation can be paralleled massively (indeed, if the number of variable is large it is close to embarrassingly parallel) in a way that GA isn't. $\endgroup$ – user603 May 16 '14 at 23:35
  • 2
    $\begingroup$ For all practical purposes, the no free lunch theorem is irrelevant to the real world. See en.m.wikipedia.org/wiki/…. $\endgroup$ – user76284 Nov 21 '17 at 18:29
  • $\begingroup$ @user76284 Multistart is embarrassingly parallel :D $\endgroup$ – endolith Dec 3 '18 at 3:13
1
$\begingroup$

I had a similar question myself and tried reasoning out the advantage of gradient descent than GA with a slightly different perspective than an intensive mathematical analysis like above -

One of the best use-case of "Neural nets" is that they have an inherent advantage of learning from hierarchies. And this is true for MLPs, ConvNets or RNNs. This feature of neural nets enable us to do "Transfer learning" wherein we just plugin the trained weights from any layer in a trained network (vgg16 inception etc.,).

The slow process of "back-propagation and gradient descent" in my opinion, helps the network, during training, to learn such optimal hierarchies and underlying patterns. This in-turn makes the underlying layers do feature extraction and enables us to apply transfer learning as needed. I relate this entire process to an "organic learning process" just like the way we humans typically learn.

Now, assuming we arrive at the optimal weight coefficients using GA or (some other technique), we are interfering with the organic learning process and the optimal learning hierarchies may get disturbed in the process leading to an over-fitting on the trained data with high variance on unseen data.

$\endgroup$
  • $\begingroup$ But isn't that what validation data is for? To stop before overfitting? $\endgroup$ – endolith Dec 3 '18 at 3:25
1
$\begingroup$

There have been two publications recently providing compelling results using gradient-free optimization for Reinforcement Learning: "Simple random search provides a competitive approach to reinforcement learning" and "Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning". I implemented both methods for a simulated robotics task and am seeing very good results especially with Random Search, which confirms the good scores the author of the paper observed. GA isn't performing as well, also confirming the observation of the authors seeing it perform astoundingly well in Atari games and much worse in simulated Robotics environments.

Anyway, it's 2018 and it's looking like gradient-free optimization methods have a bright future.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.