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

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

> 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]

In almost every optimisation problem I've encountered in practice, you do get stuck in local optima using simple techniques like SGD. Interaction effects are everywhere, and create local optima.

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.

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

Of course you can mix your gradient descent with simulated annealing. But that gets close to evolutionary algorithms.

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.

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

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

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.

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.

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

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.

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.

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.

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.

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.

The IMO, most interesting work in EA is in 'search space illumination', MAPElites, and it's variations are a great example.

Thanks for pointing this out. I had a look at 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?

What's to stop the discovered solutions from being similar? Nothing but the dimensions of interest. If the best solutions with respect to features a, b, and (a&b) are all the same, then it does not seek different solutions.

This may indicate you chose reduntant features though.

Here's an interesting application that provides some motivation. https://arxiv.org/abs/1407.3501

Regarding the similarity of solutions:

If, in a particular region, your model outputs are particularly sensitive to the inputs, that region can be overrepresented in a feature map. What I mean by this is that we cannot effectively choose between the solutions in this region -- the region is small compared to our ability to control inputs. Overrepresenting such a region in a population-based search starves the rest of the problem space of the algorithm's attention.

Thanks for the link, by the way -- this is a particularly interesting application.

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

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

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

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.

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

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!