Advantages of Evolutionary Algorithms vs. Gradient Based Optimization

Question

When it comes to the Loss Functions of "Real World" Statistical Models (e.g. Neural Networks) - based on the large number of parameters in these loss functions, their complex behaviors and the fact that they are based on non-deterministic variables (i.e. random variables) : I have heard that it is reasonable to believe that many of these loss functions are non-convex and noisy.

I have heard that the desirable properties (e.g. convergence) of gradient based optimization algorithms do not necessarily extend themselves fully to non-convex and non-deterministic (i.e. "noisy") functions. Compounded by the fact that even Quasi-Newton optimization techniques (e.g. such as gradient descent, that do not rely on the evaluating the second derivatives of the loss function) can be quite computationally expensive for such types of loss functions - does this explain the rise in popularity of evolutionary algorithms (e.g. genetic algorithm) and metaheuristics for optimizing loss functions?

My Question: In problems where we actually have a loss function (as opposed to discrete combinatorial optimization problems where we don't have loss functions) - compared to gradient based optimization techniques, do evolutionary algorithms present advantages for the following reasons:

• Optimizing complex and high dimensional loss functions with many model parameters (i.e. the weights in a neural network) make gradient based optimization techniques (e.g. gradient descent) computationally expensive based on the fact that they have to repeatedly evaluate derivatives of the loss function - whereas Evolutionary Algorithms do not require evaluating derivatives of the loss functions, making them more suitable in such circumstances.

• In general, Evolutionary Algorithms offer no theoretical guarantees on convergence whatsoever - they only guarantee improvements in successive iterations. Seeing as we are still uncertain if the desirable properties of gradient based algorithms (e.g. convergence) extend themselves to non-convex and noisy functions - did this fact serve as one of the reasons as to why Evolutionary Algorithms gained popularity in optimizing machine learning models? Why exactly do Evolutionary Algorithms present advantages in optimizing noisy functions?

Can someone please comment on this?

Thanks!

Answer 1

There are many wrong or slightly off assumptions in this question, I will try to work through them.

• Minor point: Neural networks may or may not be statistical models (many of them are not). I would say that you need a likelihood function or at least a generative model of the data for a mathematical/computational model to be called a statistical model. However, it is not hard if you have a loss function to convert it into a likelihood function of some sort (whether it's a meaningful likelihood function - i.e., model of the generative process of the data - it's another point).
• Being non-convex and noisy are two completely different properties that come from different reasons, I'll unpack it below.
• Non-convexity stems from the arbitrary form of the loss functions used by machine learning models (in general: if you cannot prove convexity, you should assume non-convexity). There are trivial reasons for which you can expect non-convexity in neural networks (e.g., symmetries: there are multiple equivalent solutions obtained by permuting the nodes and weights). Even if you break the symmetry, it's likely that there will be local optima. Frankly, non-convexity is not a big deal: most problems are non-convex. Specifically for neural networks, at least for the success stories that we have seen so far, non-convexity seems to be hardly an issue, exactly for the immensely large number of parameters. See for example [1] for some discussion.
• Noisy (stochastic) objectives are not something "reasonable to believe": it's a well-defined property of a loss function, and (generally) very easy to verify. Evaluate your target function twice with the same input parameters, if the output values are different your function is noisy/stochastic.
  • In machine learning, the typical source of stochasticity in the loss is data subsampling. The loss function is rarely ever evaluated on the entire data set, but only on a subset of it in each iteration (called a "batch"). So the loss function evaluated at each iteration differs because it is evaluated on a different (randomly selected) subset of the data. Note that if you evaluated the loss on the entire dataset, there would be no stochasticity (at least, not due to subsampling).
  • Other sources of stochasticity for the loss function are random variables used in the computation of the loss function (for example, common if the computation of the loss involve simulation of some kind).
• Regarding the rest of your question: stochastic gradient optimization (nothing to do with Quasi-Newton optimization) is very much alive and well, and works extremely well (in fact, the entire success story of deep learning is based on it).
• It is true that in the past few years machine learning researchers have started looking into gradient-free methods (such as CMA-ES or evolution strategies) for optimization of the weights of neural networks and found, with some surprise, that these methods work well in some settings with very large number of parameters. The main reason for their success in some scenarios is that these are settings (e.g., some reinforcement learning problems) in which the gradient is extremely noisy or even deceptive (i.e., to reach the optimum you need to go against the gradient for a while). So standard stochastic-gradient methods are fooled. In those cases, gradient-free methods might end up working better (although it is very much problem-dependent) [2].
  • I strongly doubt that derivative-free methods generally converge faster (in wall-clock time) than gradient-based methods. The gradient (when reliable) provides a massive source of information which is absolutely needed in high dimensions. Many gradient-free methods effectively compute a smoothed approximation of the gradient, so their computations do not come for free (you will need many more function evaluations, without gradients, to move around the space effectively). But I am sure you can find scenarios in which it is the case that gradient-free methods perform better in terms of wall-clock time.
• "as opposed to discrete combinatorial optimization problems where we don't have loss functions". I am pretty sure discrete combinatorial optimization problems have loss functions. In fact, I don't even know how you would define an optimization problem without a target/loss/objective function. The loss may be non-differentiable but that's another story.

References

• [1] Li et al. (2017). "Visualizing the Loss Landscape of Neural Nets", https://arxiv.org/abs/1712.09913
• [2] OpenAI Blog post on evolution strategies as a valid alternative for reinforcement learning problems: https://openai.com/blog/evolution-strategies/