14
$\begingroup$

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.

$\endgroup$
11
  • 11
    $\begingroup$ Because the gradients are often easy to compute (as in backpropagation) and a highly effective tool for describing local geometry? $\endgroup$
    – Ben Bolker
    Jan 5 at 0:14
  • 5
    $\begingroup$ I asked this when I was a PhD student (~10 years ago) and the direct answer I got was: "it is too wasteful and the dimensions too high" (it was a conference and I asked the speaker). I would point that that there is something that "approximates" this: extreme learning machines but I know nobody using ELM in practice aside as a baseline. $\endgroup$
    – usεr11852
    Jan 5 at 1:04
  • 6
    $\begingroup$ Gradient free learning is very deeply connected with the Lottery ticket hypothesis. Current understanding is that very large and deep networks, at initialization, actually have a high random chance to contain a sub-network that actually does (or is close to) what you want, and gradient descent merely decreases all other unneeded parameters and fine-tunes this sub-network. This might be one of the explanations to the Deep double descent phenomenon. $\endgroup$
    – Bloc97
    Jan 5 at 4:21
  • 3
    $\begingroup$ Maybe I got sidetracked, but my main point is that gradient-free learning is alive and well in deep learning, it's just not being used as the main method of training, as gradient descent is much more computationally efficient. In the future, LTH/template methods might be used to find at initialization, a very good approximation of your function and then you would use gradient descent to tweak the network slightly for best performance. $\endgroup$
    – Bloc97
    Jan 5 at 4:33
  • 2
    $\begingroup$ In my cynical opinion, gradient descent has just become the de facto strategy; it's not a silver bullet. RNNs experienced exploding/vanishing gradient so we devised LSTMs. The same problems were experienced with longer sequences, hence we developed encoder/decoder networks with attention mechanisms, which paved the way for transformers. We keep changing the architectures to mitigate some noteworthy issues with the gradient approach. But the architecture improvements do tend to improve performance; so interest in alternative methods flounders. Talk about being stuck in a local optima! $\endgroup$
    – jbuddy_13
    Jan 6 at 17:24

4 Answers 4

15
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ For other's awareness, NP-hard problems often involve combinatorics and (mixed) integer programming. As such, the functions aren't smooth, continuous, and differentiable. So, gradient descent isn't an option, unless you use a deep reinforcement learning approach, which is likely more firepower than these problems typically require for viable solution. $\endgroup$
    – jbuddy_13
    Jan 6 at 17:08
11
$\begingroup$

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!

$\endgroup$
1
  • 4
    $\begingroup$ Note of caution regarding “existance of gradients” here: There are cases where the gradient mathematically speaking exists but is utterly infeasible to compute, cases where it exists but is very noisy in practice an cannot be used for optimisation, and vice versa cases where it strictly speaking doesn't exist, but just ignoring this technicality and doing the algebra as if it did exist turns out to be in some approximate sense ok and gives perfectly ok results in the end. $\endgroup$ Jan 5 at 15:38
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Agreed. They are slower. But to be fair to cited paper, they indeed shown that given the same setting, architecture and dataset, simulated-annealing reach to a comparable performance. $\endgroup$
    – msuzen
    Jan 5 at 23:27
  • 1
    $\begingroup$ @MehmetSüzen, I don't believe they show that at all. They show 97% accuracy on MNIST with their method, but state-of-the-art with gradient-based training achieves well over 99% accuracy. 97% is very poor performance on MNIST, so a scheme that achieves 97% on MNIST doesn't seem promising. (I realize that their experiments with gradient-based training didn't achieve 99% accuracy either, but I am suspicious that that indicates some shortcoming in their experiments.) $\endgroup$
    – D.W.
    Jan 5 at 23:56
  • 3
    $\begingroup$ You might notice that they provide very few details on their experiments with standard training. They just say they use CNN, but they don't say anything about how they train it (initialization of weights? optimization algorithm? learning rate? number of epochs? other hyperparameters?). Also, they are using a poor architecture (e.g., tanh activation instead of ReLu; tanh is known to be much worse), so no indication what would happen with a modern deep learning architecture. Basically, I don't think that paper makes a very good case for gradient-free training. $\endgroup$
    – D.W.
    Jan 6 at 0:04
4
$\begingroup$

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/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.