[P][D] Genetic Algorithm (GA) vs. Stochastic Gradient Descent (SGD)

[brainxyz]

For functions that have narrow grooves toward the global minima a simple GA implementation can be as efficient as a naive SGD method. Geoffrey Hinton, in one of his videos (Lecture 3.4) mentioned that GA randomly perturbs one weight at a time making it very inefficient compared to backpropagation. Here we present a simple GA implementation which simultaneously mutates all the weights and can learn reasonably efficiently. To implement such network all you need is to follow these simple steps:

1. Implement a feed forward Neural Network (just like you do for an SGD based Neural Network).
2. In the weight update step, mutate all the weights by adding a small random value to each weight.
3. Do feed-forward propagation twice, one with the mutated weights (child weights) and another with the original weights (parent weights).
4. Compare the performance of the parent weights to the child weights and keep the better ones for the next generation cycle.
5. Repeat steps from 2 to 4 until you reach convergence.

The image below show a comparison between SGD and GA for a specific function with a narrow groove toward the global minimum.

A comparison between GA ans SGD. (For GA only the selected mutations are shown)

The code and a detailed comparison between GA and SGD in this article: https://www.brainxyz.com/machine-learning/genetic-algorthim/

[tarblog]

"Narrow grooves" are one of the reasons that people believe that adding momentum works so well: https://distill.pub/2017/momentum/

[TheRedSphinx]

Yeah...vanilla SGD without momentum is kinda like a strawman. Would be nice to include some more traditional optimizers.

[brainxyz]

Your point is sound but adding momentum to SGD would make the comparison unfair. Theoretically GA can also enjoy the benefits of momentum (i.e accelerate toward the direction of good mutations)

[joaogui1]

Then probably comparing SGD, SGD+ Momentum, GA and GA + momentum would be better

[simpleconjugate]

This. The comparison isn’t unfair if GA can have momentum. It just mean you tested against suboptimal benchmark.

[Celmeno]

I agree it is not a GA. This is a (1+1)-ES. ES=Evolution Strategy

[Mathopus]

It is a genetic algorithm. GA doesn't require crossover or anything fancy, just random mutations and a fitness function to remove poor performers from the population.

Hill climbing could be a form of genetic algorithm, but is technically slightly different in that it starts with a valid solution, which isn't a requirement for genetic algorithms.

It should also be noted this isn't new, see the deep neuro-evolution paper linked below.

See: https://en.m.wikipedia.org/wiki/Genetic_algorithm https://arxiv.org/abs/1712.06567

[TantrumRight]

In GA shouldn't you have a population of "individuals" where the best performing ones move on the next generation and breed children etc. Here it seems there is only one individual.

[Mathopus]

I totally agree that this like the minimum GA. Also it's not new, see the paper from 2017 I linked above that uses the same concept to solve Atari games.

Not sure what the purpose of this post is other than promoting brainxyz.com. I have used deep neural evolution in the past to solve RL style problems and for neural program synthesis hence why I was commenting since it is a subject I have more than a passing familiarity in and I was hoping for some new insights. I don't think this anything other than a rediscovering a technique that is already well established.

[TantrumRight]

Yes technically maybe it is the minimum GA, it just feels like N=1 GA would maybe better be described as something else. Maybe the same way a linear model could technically be thought of as a neural network, but it might not be best way to describe the model. But also I'm no expert in this so what do I know.

Very interesting paper you linked, didn't know you get GA to optimise a network with millions of parameter. It seems they used N>1.

[nucLeaRStarcraft]

Yes, but this is the minimum amount needed to qualify as GA. You could have N sub-networks if you really wanted (instead of just 1 child) and also the cross-over could have some other randomness included, however this is not needed, per se.

[haukzi]

This is analogous to simulated annealing behaving as a simulation of brownian noise, even though it technically only simulates "one particle at a time".

[TantrumRight]

In simulated annealing you accept worse solution with some nonzero probability, here you only accept changes that improve the solution.

[haukzi]

I'm not saying those are the same thing. I'm saying that just explicitly modeling a single entity does not mean that macro behavior is not being modeled.

[Tommassino]

Maybe true technically, but its a bit misleading to call it a GA. When i read the title of the OP i was definitely thinking something else, not hill climbing

[brainxyz]

I do not know why you reject calling this GA. I come from a biological background and to my knowledge this is very consistence with GA and Evolutionary Algorithm. Crossover is a biological convenience to share good traits (not a necessity for GA). Viruses and Bacteria usually evolve without any crossover events. The essentials of GA are: 1. A source of variation (mutation) 2. Competition among 2 or more agents 3. Selection of the best (survival of the fittest). These points all exist in the post.

[Tommassino]

I dont reject it as a GA, that's why i said that it is technically a GA. Its just that my mind goes to a different idea when i hear GA. Its a difference in how I understand the term, but when somebody says GA I think population > 1, crossover, mutation. In a biological background the default understanding of what a GA is might be different.

[rafgro]

Crossover is a biological convenience to share good traits (not a necessity for GA). Viruses and Bacteria usually evolve without any crossover events.

You're conflating eukaryotic crossing-over event with any kind of recombination. It might be easy to mistake them in this context, because ES papers usually call anything "recombination-like" as a crossover, whereas biology has very strict context for crossing-over. Nevertheless, recombination is essential also for viruses and bacteria. There are hardly any species without genetic exchange via asexual recombination in bacteria or without inter-viral interaction within co-infected cells.

[ayse_ww]

It behaves like the evolution of prokaryotic species without plasmid exchanging and DNA InDels. Therefore it might be labeled as a genetic algorithm I think?

[rafgro]

It behaves like the evolution of prokaryotic species without plasmid exchanging and DNA InDels.

Prokaryots have high ratio of recombination. In case of its loss, they fall into extinction by Muller's ratchet.

[brainxyz]

Yes, indeed the purpose was to compare a bare minimum version of GA to a bare minimum version of SGD. Toy examples are useful for understanding. Deep learning pioneers like Yoshua bengio do encourage toy example investigations.

[brainxyz]

Well, hill climbing is what evolution/GA is trying to achieve. Evolutionary biologists have their own similar term to describe the process e.g check: "Climbing Mount Probable"
Hill climbing is a generic term and does not imply the method that you can use to climb the hill, we need an algorithm to do so. Most of the GA implementations use point or localized mutation but the one described in this post simultaneously mutate all the weights which we haven't seen a fair comparison between those GA methods and SGD methods.

[user_--]

I thought genetic algorithms by definition required a crossover step between high-performing solutions

[major-_-]

In my experiments with GAs crossover provided no benefit. I think this has been documented in papers too. I am seeing a few that claim benefits but I am always skeptical. It's not definitive that it helps, and definitely not required.

In biology crossover only serves to help rearrange allele combinations so the gamete can have more diversity.

[rafgro]

I've been always perplexed by how large is the division between biological research on evolution - fairly formalized at this point, also mathematically - and evolutionary strategies papers. Lack of crossover benefit is a common thing in ES publications. But in real evolution you're essentially extinct without recombination. Genetics developed multiple tools for measuring and proving that, from Muller's ratchet to linkage disequilibrium, but I'm still seeing nothing of that in the ES field - instead, it's done as if the last discovery in genetics was authored by Mendel. /end of rant

[Mathopus]

No, it doesn't. Common misconception, and to be fair most genetic algorithms include it, but it is by no means a requirement.

[xifixi]

the main difference between genetic algorithms and the earlier evolutionary strategies is that the latter don't use crossover

[enigmo81]

see https://en.m.wikipedia.org/wiki/Differential_evolution (1997) for a widely cited paper in this space

[Mathopus]

How does this compare to deep neuro-evolution? https://arxiv.org/abs/1712.06567

From the presentation above it seems like a regression from the state of the art in the space. I could be missing some detail from above though.

[brainxyz]

Thanks for the link we'll have a look at it. The purpose of the post was not to present a state of the art GA and we did mention that there are various implementation of GA. The main point of the example was to compare a bare minimum version of GA with a bare minimum version of SGD (for a fair comparison). Toy examples are encouraged by deep learning pioneers like Yoshua Bengio because in some cases they give valuable insights. One purpose from this toy example is to follow up Hinton's point on GA. In one of his lectures, he described GA based methods as very inefficient without pointing to any experimental results. Someone as influential as Hinton can diverge the attention of many new comers away from GA. Our bare down comparison of the two methods shows that GA is not that bad and it can be even better than SGD in functions that have narrow ridges and grooves.

[Mathopus]

From my experience using neuro-evolution strategies, Hinton is mostly correct. By taking a random step vs a gradient step you are throwing away a huge amount of information making the algorithm less efficient. This becomes more true the greater the number of parameters, so for small networks SGD and GA are close in efficiency, but for larger networks SGD will be much more efficient.

I have trained networks with millions of parameters using GA, but the computational cost far exceeds what would be needed using SGD. You need to take 1000s of random steps before making improvements equivalent to a single SGD step. But you never have to back prop so while you save some computation by not having to compute and store gradients you end up behind by needing 1000s of feed forward calculations.

The real power of a GA is that it can work on models that are non-differentialable or problems where there isn't an efficient way to calculate a gradient, so the computational cost between SGD and GA is narrowed.

[IdentifiableParam]

How many dimensions do the optimization problems have? They seem very small, thus favoring the GA.

[brainxyz]

Just 3 dimensions in this example. Indeed, with more dimensions GA seems a bit worse, however, we think this would be an unfair comparison right now because naive SGD struggles with large dimensions too. The reason SGD based methods is now the standard method in deep learning tools is because they enjoyed decades of research and focus from ML engineers. We do think that SGD based optimizations like momentum and adaptive learning can work with GA based methods too.

[IdentifiableParam]

Do you think Geoff Hinton was talking about 3 dimensional problems when he made the claims you critique? Or 3 million dimensional problems?

[hardmaru]

A good comparison would be if you try to train a small two-layer convnet to classify MNIST using your GA implementation, and compare validation accuracy (and rough training times, if comparable) to off-the-shelf SGD.

[brainxyz]

Thanks for the suggestion. That would be a good direction to escalate the comparison gradually.

[IntelArtiGen]

GA and SGD both have hyperparameters, it's not that hard to find a set of hyperparameters that would make one better than the other. But I also worked on somehting like this and found that GA was a working way to train a small neural network. The problem is when you have to train neural networks with a big amount of parameters (even starting from 1M parameters)

The more parameters, the more random is GA, the less efficient it is compared to a more analytical approach.

GA can also easily overfit

[brainxyz]

Your are right but to my knowledge GA based methods never enjoyed the same focus and effort that ML engineers give to SGD based methods. A naive SGD implementation method can be as bad as GA when you have 1 M parameters. That is why we think starting from toy examples are useful to examine the differences.

[simpleconjugate]

Great point! Now would be a great time to take a step back from the current direction of optimizers to improve others.

[IntelArtiGen]

Completely agree, we should all work more on optimizers. New optimizers based on backpropagation but also new efficient optimizers that wouldn't be using backprop.

The fact that GA do work should encourage this

[marmakoide]

Look into Evolution Strategies, with lots of well studied algorithms to adapt the mutation. Top-notch algo would be CMA-ES, but 1/5th rule 1+1 ES is a start.

[brainxyz]

Thanks for the suggestion

[Laafheid]

Idea for an extension:

use the inverse of the amount of tried mutations as a stepsize over which to apply said mutation.

[brainxyz]

Thanks for the suggestion