Re:The quest to evolve neural networks through evolutionary ...
by halflings on Monday October 30, 2017 @12:27AM
(#15583085)
I think the premise (neural nets get stuck in local optima) is not trivial, and there has been a lot of research about non-convex optimisation showing that this is not much of an issue. I am not a researcher, but this answer [0] points to this research.
I would also say that there are multiple ways to escape local optima (setting a larger learning rate, multiple random initialisations, ensembling).
https://www.quora.com/How-come-neural-networks-dont-get-stuc...
Re:The quest to evolve neural networks through evolutionary ...
by Turing_Machine on Monday October 30, 2017 @12:33AM
(#15583114)
You say "not much of an issue" but your link says that it's an "open question that is probably being worked on in the community".
Those aren't the same thing at all.
Re:The quest to evolve neural networks through evolutionary ...
by jhj on Monday October 30, 2017 @01:03AM
(#15583188)
Minima/maxima in high-dimensional spaces are not much of an issue; the bigger issue are saddle points.
cf https://arxiv.org/pdf/1406.2572.pdf
This is presuming that the problem has a continuous formulation anyways.
Re:The quest to evolve neural networks through evolutionary ...
by pavelchristof on Monday October 30, 2017 @04:47AM
(#15583727)
Saddle points are not much of an issue too: https://arxiv.org/abs/1710.07406
Re:The quest to evolve neural networks through evolutionary ...
by nilkn on Monday October 30, 2017 @11:34AM
(#15585753)
To add to what others have said, local extrema are actually quite rare for "random" high-dimensional functions. This is suggested by a simple heuristic based on the Hessian matrix. As the dimension increases, it becomes exponentially harder for every eigenvalue to have the same sign (coin flipping experiment). So it stands to reason that saddle points should be far more common, and SGD is actually quite good at overcoming saddle points.
Re:The quest to evolve neural networks through evolutionary ...
by sevensor on Monday October 30, 2017 @09:22AM
(#15584792)
This does not accord with my reading of history. GAs (heavily crossover-based evolution) were failing pretty hard at optimization until the early '90s, when they adopted some good ideas (real coding, better mutation operators) from the (largely mutation-oriented) ES community. If you look at the most effective single-objective evolutionary algorithms today, they're mostly descendents of ES, like DE and CMAES. Honorable mention to the micro-GA as a descendent of the GA lineage, but its effectiveness is largely driven by discontinuous mutation events. The Goldberg-style GA is woefully out of date and not particularly useful.
Well, the really big advantage is that simple gradient descent can get you stuck in local maxima (or minima, depending on how you look at things). Many fitness landscapes are guaranteed to produce suboptimal results if you use gradient descent. By contrast, a sufficiently large random variation will eventually "get out of the local hole"/"get past the local hump".
It doesn't necessarily have anything to do with differentiability; consider the graph of 0.5x+sin(x). A gradient descent technique is going to get stuck on that one right away, while random exploration won't.
Edit to address some stuff that dragontamer brought up below:
A good genetic algorithm is mostly going to produce offspring that are close to the parents (recombination, which de facto is similar to hillclimbing/gradient descent/gradient ascent) but occasionally it's going to try something off that's completely off the chain (mutation). Some of the early work with genetic algorithms focused on mutation, but it soon turned out that recombination was better most of the time. Nonetheless, you still need some mutation, or you run the risk of getting stuck at local extrema.