3 ms·

An interesting question is: why are we not seeing fast and scalable GPU implementations of GAs? (I'm not trying to trick you, genuinely cu

An interesting question is: why are we not seeing fast and scalable GPU implementations of GAs? (I'm not trying to trick you, genuinely curious). I think one problem, making GAs as they are understood today (maybe there is a better way), is the freewheeling, unconstrained nature of GA fitness functions. If the ambient fitness function has a lot of data-dependent branching, SIMD will be slow. Moreover GAs have two phases: measuring fitness and mutation/crossing over to produce the next generation. Is the mutation/crossover phase SIMD friendly? Typically, it involves randomness ... In contrast, neural net training is essentially GeMM (General Matrix Multiply) which is an incredibly predictable workload -- almost no data dependent branching. So none of the things that make processors slow and complicated (caches, prefetching, branch prediction, reservation station, scheduler ...) is needed: instead you can just stream the data from main memory directly into the matrix multiplier (tensor core). This means you can use the available transistors (and energy) much more efficiently. As far as I am aware, GAs have not, so far, been reduced to as simple uniform and predictable a workload as GeMM, which I believe is why GAs don't usually get run on a GPU (not to mention more specialised hardware like TPUs). run each machine almost entirely independently. I am not sure how this works with mutation/crossover. Learning happens by 'throwing away' unpromising search avenues (genes). So if different machines do not synchronise their populations, they don't learn from each other. Synchronisation OTOH is very slow.

joefourier 6y ago
Evolution strategies (essentially the same as genetic algorithms) have been successfully applied to GPU-training of neural networks and parallelise very well. Look at various papers on neuro-evolution (e.g. the ones from the now defunct Uber AI Labs). A simple, very inefficient implementation would be: do inference on n randomly initialised neural networks, calculate loss, select the m best performing and copy them to fill all n spots, add gaussian noise to each weight and bias of every individual, repeat. More efficient mutation and selection strategies exist, but the principle is similar and parallelisation on GPUs is trivial and actually easier than current approaches (atomic operations e.g. compare-and-swap can be used to avoid going back to the CPU for selection). I believe the real reason for neuro-evolution's unpopularity is that for most problems, gradient descent is just faster and more efficient. What would be interesting might be to combine both approaches, using evolution strategies on hyperparameter search, although I haven't read the literature on that front.
- GregarianChild 6y ago
  gradient descent is faster and more efficient. Why? Regarding neuro-evolution and hyperparameter, here the question becomes why would the stochastic nature of GAs (and ESs) be particularly better than e.g. brute force search?
  - joefourier 6y ago
    In their basic form, genetic algorithms essentially approximate gradient descent by randomly sampling the search space to find the direction of steepest descent (similar to a finite differences method). If the loss function is differentiable, you are essentially wasting computing resources on calculating paths that are known not to be optimal, hence, why not apply gradient descent directly instead of a slower approximation? Brute force search would be even more inefficient, genetic algorithms at least throw away unpromising directions.

joefourier 6y ago

Evolution strategies (essentially the same as genetic algorithms) have been successfully applied to GPU-training of neural networks and parallelise very well. Look at various papers on neuro-evolution (e.g. the ones from the now defunct Uber AI Labs). A simple, very inefficient implementation would be: do inference on n randomly initialised neural networks, calculate loss, select the m best performing and copy them to fill all n spots, add gaussian noise to each weight and bias of every individual, repeat. More efficient mutation and selection strategies exist, but the principle is similar and parallelisation on GPUs is trivial and actually easier than current approaches (atomic operations e.g. compare-and-swap can be used to avoid going back to the CPU for selection). I believe the real reason for neuro-evolution's unpopularity is that for most problems, gradient descent is just faster and more efficient. What would be interesting might be to combine both approaches, using evolution strategies on hyperparameter search, although I haven't read the literature on that front.

GregarianChild 6y ago
gradient descent is faster and more efficient. Why? Regarding neuro-evolution and hyperparameter, here the question becomes why would the stochastic nature of GAs (and ESs) be particularly better than e.g. brute force search?
- joefourier 6y ago
  In their basic form, genetic algorithms essentially approximate gradient descent by randomly sampling the search space to find the direction of steepest descent (similar to a finite differences method). If the loss function is differentiable, you are essentially wasting computing resources on calculating paths that are known not to be optimal, hence, why not apply gradient descent directly instead of a slower approximation? Brute force search would be even more inefficient, genetic algorithms at least throw away unpromising directions.