Evolutionary Algorithms for Noisy Optimization

Question

• In the field of Machine Learning, we are often tasked with optimizing a "noisy function", as compared to a "deterministic function" in classical optimization problems.

• This means that we have to "reconstruct" the function we want to optimize based on the observed data we have - since data is said to usually come from a semi-random data generating process; as a result, the function we are interested in optimizing is usually said to have a stochastic component.

• This means that had we collected the same data at a different time, it is possible that the data would not be identical to the same data collected at a different point in time - since the function (e.g. Loss Function of a Machine Learning Model) we are interested in optimizing is ultimately based on this data having a random component, (I have heard that) it is important the algorithms we use for optimizing these functions has some inherent ability to be "robust"; meaning that the solution the optimization algorithm returns for this function should (within reason) be similar to the solution for the same function based on slightly different data.

• An optimization algorithm that is not "robust" potentially has the ability to return significantly different solutions to the same objective function based on slight variations in the data, and this of course is of concern.

My Question: In terms of High Dimensional Loss Functions that are Non-Convex and expensive to differentiate, I have heard that Evolutionary Algorithms (e.g. Genetic Algorithms, Simulated Annealing, Differential Evolution, etc.) can display considerable advantages compared to Gradient Based Optimization Algorithms (e.g. Gradient Descent) - this is because repeatedly taking derivatives of functions with many variables is usually a lot more "computationally expensive" compared to the operations typically performed by Evolutionary Algorithms (e.g. crossover, mutation) .

But in the case of "noisy optimization" - do Evolutionary Algorithms present any advantages compared to Gradient Based Optimization Algorithms when considering properties such as the "robustness" of solutions??

Can someone please comment on this?

Thanks!

Answer 1

I have heard that Evolutionary Algorithms (e.g. Genetic Algorithms, Simulated Annealing, Differential Evolution, etc.) can display considerable advantages compared to Gradient Based Optimization Algorithms (e.g. Gradient Descent) - this is because repeatedly taking derivatives of functions with many variables is usually a lot more "computationally expensive" compared to the operations typically performed by Evolutionary Algorithms (e.g. crossover, mutation) .

Evolutionary algorithms proceed by doing random mutation, keeping the best candidates, and mutating them again. This is a slow and noisy process, same as biological evolution that needed millions of years to achieve what it achieved. Gradient descent is more computationally demanding, but by moving along the gradient each step is supposed to go in the "correct direction", hence move faster. If each step is slower, but you need less steps, the you may be faster overall. With evolutionary algorithms you need the computational resources for doing a lot of iterations.

Evolutionary algorithms are used for some tasks like architecture search or reinforcement learning, but not for optimization in general because they would be inefficient. This post summarizes the common disadvantages:

• GA based methods generally require more iterations to reach the minima compared to well-optimized SGD based methods.
• If the mutation rate is high, learning becomes unpredictable and noisy. If the mutation rate is low, learning becomes slow and can stick in local minima.
• Bad performance for high dimensional and complex data patterns (this needs further investigation especially with CNN architecture which we have not investigated here).
• GA is a population-based learning, therefore, we cannot take inspirations from this method to find more about the learning method used by our brains.

This also answers your question about robustness, since the algorithm is completely randomized, the results are not necessary robust in terms of their consistency.