5 ms·

I have a hard time with the analogy due to how important population dynamics and solution diversity are to evolutionary algorithms. In an EA, each candidate in

I have a hard time with the analogy due to how important population dynamics and solution diversity are to evolutionary algorithms. In an EA, each candidate in the population represents a complete potential solution. As the diversity & size of the population increases, the potential for convergence on high quality solutions also increases. I do not see the same concept in diffusion models.

dawnofdusk 2y ago
>I do not see the same concept in diffusion models. I believe, Population size = noise dimensionality Population diversity = noise magnitude
- amelius 2y ago
  But iiuc, an EA algorithm needs to keep an entire population in memory at once. I don't think this is the case for diffusion models.
  - bob1029 2y ago
    You can maintain a population of arbitrary size when using approaches such as tournament selection. Each worker can pull a subset of the population from another datacenter and run an isolated tournament. You also don't have to run the entire population each iteration. You can keep win-loss statistics and handle final selection/crossover/mutation in a separate thread once enough have accumulated. Put more simply, run it like chess and use things like Elo rating to determine fitness at selection time.
EvoQ 2y ago
I think that evolutionary algorithms, updates are by natural selection, diffusion models, updates by denoising. Perturbations in evolutionary algorithms using mutations, difusion model is done with difusion process. Seems cool!
- flir 2y ago
  > evolutionary algorithms, updates are by natural selection, diffusion models, updates by denoising but are they not both fitness functions? couldn't an EA use something akin to denoising as its fitness function and still be an EA? (genuine question, complete layman here).
wakawaka28 2y ago
I agree with you. I suppose you could simulate having a large population by maintaining a set of snapshots, but it still seems like not the same thing as a classic evolutionary technique. There is no sane way to do things like crossover I guess, unless you can average the weights from multiple snapshots (a strategy that might not work at all IMO). I think I have seen research papers addressing the crossover of neural network optimization and EA, but I think direct optimization techniques have been preferred for managing the actual weights. Manipulating the input data is more along the lines of perturbation methods. If you look hard enough you can probably see whatever you want but it's a stretch. To me, neural network training is a distinct task that draws from many areas of optimization and does not fit neatly under any one umbrella.
- jcgrillo 2y ago
  Admittedly I haven't dug too deep into the references, including the paper the article refers to--and I'm not too well versed in diffusion models either. Those caveats aside, I'm also having trouble making the analogy, and similarly for me the hangup is about crossover. If I recall correctly, what distinguishes evolution from, say, simulated annealing at varying temperatures, is precisely the crossover operator. It's not obvious where crossover is happening here.
  - robotresearcher 2y ago
    Crossover is not a defining or essential part of an EA. Reproduction with variation under selection pressure is the definition. Crossover is one possible mechanism of reproduction with variation. Simple mutation is another.
    - jcgrillo 2y ago
      Fair enough, I'm convinced now.
    - wakawaka28 2y ago
      I would not call back propagation and similar techniques "mutation". It certainly isn't random in the same sense as other random searches like EA. Maybe the exact mechanism of iteration is not that important as long as some aspect of it is random, but it's still a novel interpretation of EA.
nickpsecurity 2y ago
I’ll add to your observation about them being complete solutions. Also, since the author thinks they’re like NN’s, we’ll do a direct comparison where members are a complete solution. Here’s an evolutionary algorithm: 1. A series of NN models with random weights. 2. A way to score how well each NN model works. 3. Iteratively mixing pieces of models with each other based on how well they scored. I didn’t see that in articles about deep learning at all. It was like they were totally, different things. They were so different that I looked into using both GA’s and simulated annealing for optimization of NN’s. I’d say that EA’s and NN-like methods are different and complementary.
upghost 2y ago
I would encourage you to check out the "No Free Lunch" paper[1]. tl;dr the correct approach depends on the problem, there is no approach that is superior to all others. There are a provably infinite number of optimization problems where RANDOM GUESSING is superior to any other algorithm. (Note: I am not claiming support for the methodology in the paper, I just find the application of search/optimization algos is lovely) That being said back before I understood how to program gradient descent I would often use Evolutionary Algorithms such as simulated annealing to optimize NNs! (never claimed it was state of the art, I just wanted to build and optimize some small networks by hand and my calculus was pretty weak at the time) [1]: https://en.m.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.m.wikipedia.org/wiki/No_free_lunch_in_search_and_...

dawnofdusk 2y ago

>I do not see the same concept in diffusion models. I believe, Population size = noise dimensionality Population diversity = noise magnitude

amelius 2y ago
But iiuc, an EA algorithm needs to keep an entire population in memory at once. I don't think this is the case for diffusion models.
- bob1029 2y ago
  You can maintain a population of arbitrary size when using approaches such as tournament selection. Each worker can pull a subset of the population from another datacenter and run an isolated tournament. You also don't have to run the entire population each iteration. You can keep win-loss statistics and handle final selection/crossover/mutation in a separate thread once enough have accumulated. Put more simply, run it like chess and use things like Elo rating to determine fitness at selection time.

EvoQ 2y ago

I think that evolutionary algorithms, updates are by natural selection, diffusion models, updates by denoising. Perturbations in evolutionary algorithms using mutations, difusion model is done with difusion process. Seems cool!

flir 2y ago
> evolutionary algorithms, updates are by natural selection, diffusion models, updates by denoising but are they not both fitness functions? couldn't an EA use something akin to denoising as its fitness function and still be an EA? (genuine question, complete layman here).

wakawaka28 2y ago

I agree with you. I suppose you could simulate having a large population by maintaining a set of snapshots, but it still seems like not the same thing as a classic evolutionary technique. There is no sane way to do things like crossover I guess, unless you can average the weights from multiple snapshots (a strategy that might not work at all IMO). I think I have seen research papers addressing the crossover of neural network optimization and EA, but I think direct optimization techniques have been preferred for managing the actual weights. Manipulating the input data is more along the lines of perturbation methods. If you look hard enough you can probably see whatever you want but it's a stretch. To me, neural network training is a distinct task that draws from many areas of optimization and does not fit neatly under any one umbrella.

jcgrillo 2y ago
Admittedly I haven't dug too deep into the references, including the paper the article refers to--and I'm not too well versed in diffusion models either. Those caveats aside, I'm also having trouble making the analogy, and similarly for me the hangup is about crossover. If I recall correctly, what distinguishes evolution from, say, simulated annealing at varying temperatures, is precisely the crossover operator. It's not obvious where crossover is happening here.
- robotresearcher 2y ago
  Crossover is not a defining or essential part of an EA. Reproduction with variation under selection pressure is the definition. Crossover is one possible mechanism of reproduction with variation. Simple mutation is another.
  - jcgrillo 2y ago
    Fair enough, I'm convinced now.
  - wakawaka28 2y ago
    I would not call back propagation and similar techniques "mutation". It certainly isn't random in the same sense as other random searches like EA. Maybe the exact mechanism of iteration is not that important as long as some aspect of it is random, but it's still a novel interpretation of EA.

nickpsecurity 2y ago

I’ll add to your observation about them being complete solutions. Also, since the author thinks they’re like NN’s, we’ll do a direct comparison where members are a complete solution. Here’s an evolutionary algorithm: 1. A series of NN models with random weights. 2. A way to score how well each NN model works. 3. Iteratively mixing pieces of models with each other based on how well they scored. I didn’t see that in articles about deep learning at all. It was like they were totally, different things. They were so different that I looked into using both GA’s and simulated annealing for optimization of NN’s. I’d say that EA’s and NN-like methods are different and complementary.

upghost 2y ago

I would encourage you to check out the "No Free Lunch" paper[1]. tl;dr the correct approach depends on the problem, there is no approach that is superior to all others. There are a provably infinite number of optimization problems where RANDOM GUESSING is superior to any other algorithm. (Note: I am not claiming support for the methodology in the paper, I just find the application of search/optimization algos is lovely) That being said back before I understood how to program gradient descent I would often use Evolutionary Algorithms such as simulated annealing to optimize NNs! (never claimed it was state of the art, I just wanted to build and optimize some small networks by hand and my calculus was pretty weak at the time) [1]: https://en.m.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.m.wikipedia.org/wiki/No_free_lunch_in_search_and_...