3 ms·

"what are the advantages of these techniques compared to gradient descent?" Well, the really big advantage is that simple gradient descent can get you stuck in

"what are the advantages of these techniques compared to gradient descent?" 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.

halflings 9y ago
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-stuck-in-poor-local-optima-Why-are-there-so-many-high-quality-local-optima https://www.quora.com/How-come-neural-networks-dont-get-stuc...
- Turing_Machine 9y ago
  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.
jhj 9y ago
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 https://arxiv.org/pdf/1406.2572.pdf This is presuming that the problem has a continuous formulation anyways.
- pavelchristof 9y ago
  Saddle points are not much of an issue too: https://arxiv.org/abs/1710.07406 https://arxiv.org/abs/1710.07406
sevensor 9y ago
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.
nilkn 9y ago
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.

halflings 9y ago

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-stuck-in-poor-local-optima-Why-are-there-so-many-high-quality-local-optima https://www.quora.com/How-come-neural-networks-dont-get-stuc...

Turing_Machine 9y ago
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.

jhj 9y ago

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 https://arxiv.org/pdf/1406.2572.pdf This is presuming that the problem has a continuous formulation anyways.

pavelchristof 9y ago
Saddle points are not much of an issue too: https://arxiv.org/abs/1710.07406 https://arxiv.org/abs/1710.07406

sevensor 9y ago

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.

nilkn 9y ago

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.