9 ms·

I have always seen evolutionary algorithm as a version of gradient descent that throws away the gradient, and instead just goes randomly in all directions until

I have always seen evolutionary algorithm as a version of gradient descent that throws away the gradient, and instead just goes randomly in all directions until it finds something that works (which is extremely wasteful). I suppose this is wrong since people still find these techniques useful, but what are the advantages of these techniques compared to gradient descent? (other than the fact that you don't need your fitness function to be differentiable)

MereInterest 9y ago
Random walks work well in high dimension soaces, where calculating the gradient gets to be very expensive. Depending on your metaparameters, random walk can also try to jump out of a local minimum, where gradient descent only optimizes within the initial local mimimum.
- halflings 9y ago
  Gradient descent can also jump out of a local minimum if the learning rate is large enough, so they're equal in that sense. But it does make sense that a random walk would be more efficient in very high dimensional problems!
- pavelchristof 9y ago
  Absolutely no. Random search does not work in high dimensions because of the "curse of dimensionality" - the number of directions to search grows exponentially with dimension. Gradient descent avoids the problem because it knows the right direction. Evolutionary strategies are doing (natural) gradient descent using an estimate of the gradient. Here's a good article: http://www.inference.vc/evolutionary-strategies-embarrassingly-parallelizable-optimization/ http://www.inference.vc/evolutionary-strategies-embarrassing...
dragontamer 9y ago
I think you confused "evolutionary algorithm" with Simulated Annealing. Because Simulated Annealing is LITERALLY a random walk (biased towards higher values, but its strongly random nonetheless). https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing Simulated Annealing works because it doesn't get stuck in local maximums. Do a simple gradient ascent on this simple 2d plot, and its very, very unlikely to achieve the true global value: https://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Climbing_with_Simulated_Annealing.gif https://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Cli... But if you do Simulated Annealing (aka: random walk), you get to the global maximum much more reliably. Genetic Algorithms have a similar effect as Simulated Annealing because Genetic Algorithms are strongly randomized. But they still "hill climb" explicitly, because its rare for parents to be thrown away if they were superior to the children.
- randomsearch 9y ago
  > Simulated Annealing is LITERALLY a random walk (biased towards higher values, but its strongly random nonetheless). I don't think that's a fair characterisation, and it could be misleading for people new to SA. I'd say SA is a hill-climbing algorithm that has a probability of accepting an inferior move, a probability which shrinks asymptotically over time.
Turing_Machine 9y ago
"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.
randomsearch 9y ago
> I have always seen evolutionary algorithm as a version of gradient descent... which is extremely wasteful Evolutionary algorithms work by sampling a combinatorial solution space, and learning about the interactions between solution components. This is made explicit (and much more elegant) in the definition of EDAs: https://en.wikipedia.org/wiki/Estimation_of_distribution_algorithm https://en.wikipedia.org/wiki/Estimation_of_distribution_alg... By contrast, gradient descent makes the assumption that such interaction effects don't exist or don't matter, which doesn't work for most optimisation problems - you get stuck in local optima.
- eru 9y ago
  Of course you can mix your gradient descent with simulated annealing. But that gets close to evolutionary algorithms.
- rdlecler1 9y ago
  Evolutionary algorithms may also let you evolve the architecture. Think of a fly brain evolving into a human brain using the same genetic toolbox. With learning algorithms your assuming a fixed architecture. Hard to think how we’d get open ended evolutionary AI without evolutionary algorithms. At that point learning algorithms is the context dependent optimization step after neurogenesis.
  - halflings 9y ago
    The terms you are using are too vague, and seem disconnected from the reality of these algorithms. How do evolutionary algorithms let you evolve the architecture? You define a model space, and explore it stochastically (with different evolutionary strategies). The model space you are exploring is linked to a specific architecture. Regardless, there's also efforts in Deep Learning to automatically learn optimal network architectures ("AutoML").
- halflings 9y ago
  Thanks! That link was really helpful. I guess some optimisation methods using a Hessian take those interaction effects into consideration, but they are too expensive and not used in practice. > doesn't work for most optimisation problems - you get stuck in local optima. This bit is not necessarily true. In practice, and given the high dimensionality, it is (apparently) quite hard to get stuck in local optima. [0] [0] 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...
pavelchristof 9y ago
The fact that you don't need your fitness function to be differentiable is a big advantage :) if you had the gradient it would always help to use it. In reinforcement learning: evolutionary algorithms work by applying peturbations in the parameters space, not in the action space. If your problem is sensitive to action-space perturbations (requires consistent strategies) it might not be possible or efficient to use "standard" RL. Evolutionary strategies (ES) are quite competitive in RL, especially paired with some dimensonality reduction technique (unsupervised VAE). Local minima are not really an advantage. ES are nearly local - they sample the space around the current solution to approximate the gradients. They'll get stuck in local minima sometimes too (if there are any). Bayesian optimization is more interesting, as it's actually global.
sevensor 9y ago
One thing I don't see mentioned here is flexibility. You can plug any ugly old thing into an evolutionary algorithm and let it run. Give me a working computational model at breakfast time and I'll have runs going by lunch. Cranky ancient FORTRAN that requires you to write a new input file for every evaluation? No problem. You have to compile the inputs into the model to make it run? Fine. Badly scaled inputs or outputs? EA doesn't care. More than one objective? Great! Population-based search is a natural fit for multiple objective optimization. As long as you're clear on what the decisions and objectives are, and you're able to run the model yourself, layering evolutionary optimization on top is easy.
- maaaats 9y ago
  I think the multiobjective-part is very important. In other algorithms, you often have to specify the solution-space before hand. For instance, when optimizing between lightweight and strength, one would have to beforehand say how to weight those two properties. (f = 100s - 5w for instance). This throws away a whole dimension in your search space. For EAs, you can let it roam free, and select the bests tradeoffs from the pareto-set after the algorithm is done.
  - sevensor 9y ago
    Yes, exactly! And it gets even better. With a good MOEA, you can keep track of your evaluations, do a short run, decide your objectives don't really express your understanding of the problem, and seed your old evaluations into a run with new objectives. This means you can change objectives without repeating computationally expensive model runs.
  - zardo 9y ago
    The IMO, most interesting work in EA is in 'search space illumination', MAPElites, and it's variations are a great example.
    - sevensor 9y ago
      Thanks for pointing this out. I had a look at http://www.evolvingai.org/files/1504.04909v1.pdf http://www.evolvingai.org/files/1504.04909v1.pdf. It's an interesting read, although I'm not sold on the value of feature space exploration. I think it muddies the waters around the problem of balancing optimization with diversity, by lumping decisions and constraints together. What's to stop it from over-sampling regions of the decision space that have a steep gradient in the other features?

MereInterest 9y ago

Random walks work well in high dimension soaces, where calculating the gradient gets to be very expensive. Depending on your metaparameters, random walk can also try to jump out of a local minimum, where gradient descent only optimizes within the initial local mimimum.

halflings 9y ago
Gradient descent can also jump out of a local minimum if the learning rate is large enough, so they're equal in that sense. But it does make sense that a random walk would be more efficient in very high dimensional problems!
pavelchristof 9y ago
Absolutely no. Random search does not work in high dimensions because of the "curse of dimensionality" - the number of directions to search grows exponentially with dimension. Gradient descent avoids the problem because it knows the right direction. Evolutionary strategies are doing (natural) gradient descent using an estimate of the gradient. Here's a good article: http://www.inference.vc/evolutionary-strategies-embarrassingly-parallelizable-optimization/ http://www.inference.vc/evolutionary-strategies-embarrassing...

dragontamer 9y ago

I think you confused "evolutionary algorithm" with Simulated Annealing. Because Simulated Annealing is LITERALLY a random walk (biased towards higher values, but its strongly random nonetheless). https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing Simulated Annealing works because it doesn't get stuck in local maximums. Do a simple gradient ascent on this simple 2d plot, and its very, very unlikely to achieve the true global value: https://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Climbing_with_Simulated_Annealing.gif https://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Cli... But if you do Simulated Annealing (aka: random walk), you get to the global maximum much more reliably. Genetic Algorithms have a similar effect as Simulated Annealing because Genetic Algorithms are strongly randomized. But they still "hill climb" explicitly, because its rare for parents to be thrown away if they were superior to the children.

randomsearch 9y ago
> Simulated Annealing is LITERALLY a random walk (biased towards higher values, but its strongly random nonetheless). I don't think that's a fair characterisation, and it could be misleading for people new to SA. I'd say SA is a hill-climbing algorithm that has a probability of accepting an inferior move, a probability which shrinks asymptotically over time.

Turing_Machine 9y ago

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

randomsearch 9y ago

> I have always seen evolutionary algorithm as a version of gradient descent... which is extremely wasteful Evolutionary algorithms work by sampling a combinatorial solution space, and learning about the interactions between solution components. This is made explicit (and much more elegant) in the definition of EDAs: https://en.wikipedia.org/wiki/Estimation_of_distribution_algorithm https://en.wikipedia.org/wiki/Estimation_of_distribution_alg... By contrast, gradient descent makes the assumption that such interaction effects don't exist or don't matter, which doesn't work for most optimisation problems - you get stuck in local optima.

eru 9y ago
Of course you can mix your gradient descent with simulated annealing. But that gets close to evolutionary algorithms.
rdlecler1 9y ago
Evolutionary algorithms may also let you evolve the architecture. Think of a fly brain evolving into a human brain using the same genetic toolbox. With learning algorithms your assuming a fixed architecture. Hard to think how we’d get open ended evolutionary AI without evolutionary algorithms. At that point learning algorithms is the context dependent optimization step after neurogenesis.
- halflings 9y ago
  The terms you are using are too vague, and seem disconnected from the reality of these algorithms. How do evolutionary algorithms let you evolve the architecture? You define a model space, and explore it stochastically (with different evolutionary strategies). The model space you are exploring is linked to a specific architecture. Regardless, there's also efforts in Deep Learning to automatically learn optimal network architectures ("AutoML").
halflings 9y ago
Thanks! That link was really helpful. I guess some optimisation methods using a Hessian take those interaction effects into consideration, but they are too expensive and not used in practice. > doesn't work for most optimisation problems - you get stuck in local optima. This bit is not necessarily true. In practice, and given the high dimensionality, it is (apparently) quite hard to get stuck in local optima. [0] [0] 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...

pavelchristof 9y ago

The fact that you don't need your fitness function to be differentiable is a big advantage :) if you had the gradient it would always help to use it. In reinforcement learning: evolutionary algorithms work by applying peturbations in the parameters space, not in the action space. If your problem is sensitive to action-space perturbations (requires consistent strategies) it might not be possible or efficient to use "standard" RL. Evolutionary strategies (ES) are quite competitive in RL, especially paired with some dimensonality reduction technique (unsupervised VAE). Local minima are not really an advantage. ES are nearly local - they sample the space around the current solution to approximate the gradients. They'll get stuck in local minima sometimes too (if there are any). Bayesian optimization is more interesting, as it's actually global.

sevensor 9y ago

One thing I don't see mentioned here is flexibility. You can plug any ugly old thing into an evolutionary algorithm and let it run. Give me a working computational model at breakfast time and I'll have runs going by lunch. Cranky ancient FORTRAN that requires you to write a new input file for every evaluation? No problem. You have to compile the inputs into the model to make it run? Fine. Badly scaled inputs or outputs? EA doesn't care. More than one objective? Great! Population-based search is a natural fit for multiple objective optimization. As long as you're clear on what the decisions and objectives are, and you're able to run the model yourself, layering evolutionary optimization on top is easy.

maaaats 9y ago
I think the multiobjective-part is very important. In other algorithms, you often have to specify the solution-space before hand. For instance, when optimizing between lightweight and strength, one would have to beforehand say how to weight those two properties. (f = 100s - 5w for instance). This throws away a whole dimension in your search space. For EAs, you can let it roam free, and select the bests tradeoffs from the pareto-set after the algorithm is done.
- sevensor 9y ago
  Yes, exactly! And it gets even better. With a good MOEA, you can keep track of your evaluations, do a short run, decide your objectives don't really express your understanding of the problem, and seed your old evaluations into a run with new objectives. This means you can change objectives without repeating computationally expensive model runs.
- zardo 9y ago
  The IMO, most interesting work in EA is in 'search space illumination', MAPElites, and it's variations are a great example.
  - sevensor 9y ago
    Thanks for pointing this out. I had a look at http://www.evolvingai.org/files/1504.04909v1.pdf http://www.evolvingai.org/files/1504.04909v1.pdf. It's an interesting read, although I'm not sold on the value of feature space exploration. I think it muddies the waters around the problem of balancing optimization with diversity, by lumping decisions and constraints together. What's to stop it from over-sampling regions of the decision space that have a steep gradient in the other features?