Simulated annealing for deep learning: Why is gradient free statistical learning not in the main stream?

Question

In order to define what deep learning is, the learning portion is often listed with backpropagation as a requirement without alternatives in the main stream software libraries and in the literature. There are not many gradient free optimisations are mentioned in deep learning or in general statistical learning. Similarly, in "classical algorithms" (Nonlinear least squares) involves derivatives [1]. In general, gradient free learning in deep learning or classical algorithms are not in the main stream. One promising alternative is simulated annealing [2, 3], so-called 'nature-inspired optimization'.

Is there any inherent theoretical reason that why gradient free deep learning (statistical learning) is not in the main stream? (Or not preferred?)

Notes

[1] Such as Levenberg–Marquardt

[2] Simulated Annealing Algorithm for Deep Learning (2015)

[3] CoolMomentum: a method for stochastic optimization by Langevin dynamics with simulated annealing (2021) Though this is still not fully gradient-free, but does not require auto-differentiation.

Edit 1 Additional references using Ensemble Kalman Filter, showing a derivative free approach:

• Ensemble Kalman Inversion: A Derivative-Free Technique For Machine Learning Tasks arXiv:1808.03620.
• Ensemble Kalman Filter optimizing Deep Neural Networks: An alternative approach to non-performing Gradient Descent springer (manuscript-pdf)

Edit 2 As far as I gather, Yann LeCun does not consider gradient-free learning as part of deep learning ecosystem. "DL is constructing networks of parameterized functional modules & training them from examples using gradient-based optimization." tweet

Edit 3 Ben Bolker's comment on local geometry definitely deserves to be one of the answers.

Answer 1

Gradient-free learning is in the mainstream very heavily, but not used heavily in deep learning. Methods used for training neural networks that don't involve derivatives are typically called "metaheuristics." In computer science and pattern recognition (which largely originated in electrical engineering), metaheuristics are the go-to for NP-hard problems, such as airline flight scheduling, traffic route planning to optimize fuel consumption by delivery trucks, or the traveling salesman problem (annealing). As an example see swarm-based learning for neural networks or genetic algorithms for training neural networks or use of a metaheuristic for training a convolutional neural network. These are all neural networks which use metaheuristics for learning, and not derivatives.

While metaheuristics encompasses a wide swath of the literature, they're just not strongly associated with deep-learning, as these are different areas of optimization. Look up "solving NP-hard problems with metaheuristics." Last, recall that gradients used for neural networks don't have anything to do with the derivatives of a function that a neural network can be used to minimize (maximize). (This would be called function approximation using a neural network as opposed to classification analysis via neural network.) They're merely derivatives of the error or cross-entropy with respect to connection weight change within the network.

In addition, the derivatives of a function may not be known, or the problem can be too complex for using derivatives. Some of the newer optimization methods involve finite differencing as a replacement for derivatives, since compute times are getting faster, and derivative-free methods are becoming less computationally expensive in the time complexity.

Answer 2

Great question! To put it briefly, "Gradient Free Learning" (i.e. "metaheuristics", as pointed out by @user0123456789) is usually used when the "gradient" (i.e. derivative) of the loss function can not be evaluated. This can occur in instances such as :

• The derivative of the loss function does not exist (e.g. contains "indicator functions", piecewise functions)

• The derivative of the loss function exists, but is very costly to evaluate (e.g. I have heard talks in which gradient free optimization techniques were suggested for various problems involving reinforcement learning)

• Discrete Combinatorics/Optimization problems (this is kind of related to the first point, but imagine trying to optimize functions in which the inputs are a set of discrete objects and the output is a value associated with different inputs - for example: travelling salesman problem, knapsack optimization, scheduling, etc.)

• Gradient Free Optimization Techniques (e.g. Evolutionary Algorithms, Genetic Algorithm, Simulated Annealing, Particle Swarm, etc.) are sometimes preferred for certain types problems such as "games", in which optimal strategies are developed by mutating and combining random strategies according to their performance with respect to some target (e.g. https://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies , https://www.youtube.com/watch?v=OGHA-elMrxI)

The other note that I wanted to add was that in situations where the gradient of the loss function can be evaluated (e.g. classic MLP neural networks), I think there might be some theoretical results that guarantee the probabilistic convergence of Stochastic Gradient Descent (i.e. the opposite of gradient free learning) to a global maximum provided infinite iterations (I could be wrong about this) - with gradient free optimization techniques, as far I know there is no such guarantee (over here, I myself asked a question about the "Schema Theorem", which uses Markov Chains to supposedly guarantee an improvement in results as the number of iterations in the Genetic Algorithm increases https://math.stackexchange.com/questions/4295279/does-the-following-computer-science-optimization-theorem-have-a-proof).

To sum everything up - chances are that if the derivative of your loss function "exists", try using classical gradient based optimization techniques. If the derivative does not exist, consider using Gradient Free based techniques.

For example, over here I asked a question about identifying "clusters" in a dataset such that the "proportion of zeros in all columns for a given cluster" is minimized. As far as I can think, there is no standard "gradient" in this problem, making it an ideal choice for "gradient free optimization techniques": https://or.stackexchange.com/questions/7488/mixed-integer-programming-optimization-using-the-genetic-algorithm

Hope this helps!

Answer 3

The reason we don't use gradient-free methods for training neural nets is simple: gradient-free methods don't work as well as gradient-based methods.

Gradient-based methods converge faster, to better solutions. Gradient-free methods tend to scale poorly (for instance, one of the papers you cite only tests on MNIST, which is a tiny dataset and task; the other tests on CIFAR-10 but is a gradient-based method) and tend to yield inferior results (for instance, one of the papers you cite reports 97% accuracy on MNIST; but state-of-the-art accuracy on MNIST is well over 99%).

In general, when a gradient is available and the loss surface is not too messy, typically gradient-based methods work better than gradient-free methods. Gradient-free methods are useful when it is not easy to compute the gradient or when the loss function is not very smooth.

Answer 4

In my understanding it's a consequence of the high number of variables that neural networks tends to require when tackling interesting problems. For simple tasks gradient-free methods work very well and are quite capable of beating gradient-based methods, as many of them deal with non-convex functions/local optima better than the grad-based methods and that tends to be the biggest issue for low dimensional problems.

However, as the number of dimensions/model variables increases, two things happen:

1. Local optima cease to be optima and become saddles instead. To be, say, a local minimum a zero-gradient point must be a minimum with respect to every dimension. If you have a million of these, it is practically guaranteed that it won't be a minimum in at least one. Modern gradient-based methods deal with saddles reasonably well, so as models scale up the functions become effectively convex for them.
2. A random perturbation of a solution candidate becomes increasingly unlikely to happen to have a direction similar to that of the gradient. That means that in grad-free methods that rely on such perturbations a lot of them will have to be made before the solution candidates move in the direction of the gradient, as opposed to just performing a random walk. Most grad-free methods fall into this category, and accordingly take a performance hit as models scale up.

The exception to that rule are the methods of the evolutionary strategies family. The main idea of these is to accumulate the information about the gradient from multiple perturbations and skew the distribution of subsequent perturbations in a way that makes them more likely to be aligned with the gradient. Those perform reasonably well on deep learning tasks [1]. They require roughly a few times more resources than the amount required by the gradient-based family to do the same job, but offer a superior performance on deceptive problems and improved horizontal scalability. I think the main reason why this approach never attracted mainstream attention is because the amount of parallel hardware required to get to the point where they compare favorably to grad-based is available to very few people in the world. It's been a while, but from what I recall the breakeven point is somewhere in the hundreds of GPUs region.

[1] https://eng.uber.com/deep-neuroevolution/