89
$\begingroup$

Many neural network books and tutorials spend a lot of time on the backpropagation algorithm, which is essentially a tool to compute the gradient.

Let's assume we are building a model with ~10K parameters / weights. Is it possible to run the optimization using some gradient free optimization algorithms?

I think computing the numerical gradient would be too slow, but how about other methods such as Nelder-Mead, Simulated Annealing or a Genetic Algorithm?

All the algorithms would suffer from local minima, why obsessed with gradient?

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of In neural nets, why use gradient methods rather than other metaheuristics? $\endgroup$ – Franck Dernoncourt Sep 20 '16 at 3:29
  • 6
    $\begingroup$ @FranckDernoncourt I interpreted the other question as "why not use global optimization techniques to train neural networks?", whereas this one is more "why not use derivative-free optimzers ...". $\endgroup$ – GeoMatt22 Sep 20 '16 at 4:16
  • 6
    $\begingroup$ With 3 upvoted answers, this does not seem too broad to be answerable to me. $\endgroup$ – gung Sep 20 '16 at 12:26
  • 5
    $\begingroup$ Yeah, you don't have to worry much about Nelder-Mead getting stuck at a local minimum, because you'll be lucky if it gets anywhere useful. $\endgroup$ – Mark L. Stone Sep 23 '16 at 23:54
  • 1
    $\begingroup$ BTW, ultra L-BFGS, give that a whirl. it might be good, but it's so obscure probably no one has even tried it on neural networks. See equation 2.9 on p. 12 (you need to read the preceding few pages to understand the formula, though) of maths.dundee.ac.uk/nasc/na-reports/NA149_RF.pdf (not called ultra BFGS in the paper), which then would need to get into an "L" (limited memory) version to be ultra L-BFGS, rather than ultra BFGS. The non-L version is laid out in the paper. Ultra BFGS is basically a souped-up ("hot rod") BFGS - can be faster, but might be a little wilder. $\endgroup$ – Mark L. Stone Sep 24 '16 at 0:00
77
$\begingroup$

The first two algorithms you mention (Nelder-Mead and Simulated Annealing) are generally considered pretty much obsolete in optimization circles, as there are much better alternatives which are both more reliable and less costly. Genetic algorithms covers a wide range, and some of these can be reasonable.

However, in the broader class of derivative-free optimization (DFO) algorithms, there are many which are significantly better than these "classics", as this has been an active area of research in recent decades. So, might some of these newer approaches be reasonable for deep learning?

A relatively recent paper comparing the state of the art is the following:

Rios, L. M., & Sahinidis, N. V. (2013) Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization.

This is a nice paper which has many interesting insights into recent techniques. For example, the results clearly show that the best local optimizers are all "model-based", using different forms of sequential quadratic programming (SQP).

However, as noted in their abstract "We find that the ability of all these solvers to obtain good solutions diminishes with increasing problem size." To give an idea of the numbers, for all problems the solvers were given a budget of 2500 function evaluations, and problem sizes were a maximum of ~300 parameters to optimize. Beyond O[10] parameters, very few of these optimizers performed very well, and even the best ones showed a noticable decay in performance as problem size was increased.

So for very high dimensional problems, DFO algorithms just are not competitive with derivative based ones. To give some perspective, PDE (partial differential equation)-based optimization is another area with very high dimensional problems (e.g. several parameter for each cell of a large 3D finite element grid). In this realm, the "adjoint method" is one of the most used methods. This is also a gradient-descent optimizer based on automatic differentiation of a forward model code.

The closest to a high-dimensional DFO optimizer is perhaps the Ensemble Kalman Filter, used for assimilating data into complex PDE simulations, e.g. weather models. Interestingly, this is essentially an SQP approach, but with a Bayesian-Gaussian interpretation (so the quadratic model is positive definite, i.e. no saddle points). But I do not think that the number of parameters or observations in these applications is comparable to what is seen in deep learning.

Side note (local minima): From the little I have read on deep learning, I think the consensus is that it is saddle points rather than local minima, which are most problematic for high dimensional NN-parameter spaces.

For example, the recent review in Nature says "Recent theoretical and empirical results strongly suggest that local minima are not a serious issue in general. Instead, the landscape is packed with a combinatorially large number of saddle points where the gradient is zero, and the surface curves up in most dimensions and curves down in the remainder."

A related concern is about local vs. global optimization (for example this question pointed out in the comments). While I do not do deep learning, in my experience overfitting is definitely a valid concern. In my opinion, global optimization methods are most suited for engineering design problems that do not strongly depend on "natural" data. In data assimilation problems, any current global minima could easily change upon addition of new data (caveat: My experience is concentrated in geoscience problems, where data is generally "sparse" relative to model capacity).

An interesting perspective is perhaps

O. Bousquet & L. Bottou (2008) The tradeoffs of large scale learning. NIPS.

which provides semi-theoretical arguments on why and when approximate optimization may be preferable in practice.

End note (meta-optimization): While gradient based techniques seem likely to be dominant for training networks, there may be a role for DFO in associated meta-optimization tasks.

One example would be hyper-parameter tuning. (Interestingly, the successful model-based DFO optimizers from Rios & Sahinidis could be seen as essentially solving a sequence of design-of-experiments/response-surface problems.)

Another example might be designing architectures, in terms of the set-up of layers (e.g. number, type, sequence, nodes/layer). In this discrete-optimization context genetic-style algorithms may be more appropriate. Note that here I am thinking of the case where connectivity is determined implicitly by these factors (e.g. fully-connected layers, convolutional layers, etc.). In other words the $\mathrm{O}[N^2]$ connectivity is $not$ meta-optimized explicitly. (The connection strength would fall under training, where e.g. sparsity could be promoted by $L_1$ regularization and/or ReLU activations ... these choices could be meta-optimized however.)

$\endgroup$
  • 1
    $\begingroup$ The 'review' you quote is from the major proponents of neural nets; I would question the claim about local minima - a well known theoretical criticism of NNs is precisely that any complex model cannot be optimised by gradient descent because it will get stuck in local minima. It is not clear whether it is only the successes of nns that can be solved with backdrop and you do not hear about the failures. $\endgroup$ – seanv507 Sep 20 '16 at 6:30
  • 2
    $\begingroup$ @GeoMatt22 Contrastive divergence is a special approximation to the gradient of a special class of models, which RBMs fall under. It should be noted that RBMs are probabilistic models which imply a certain kind of distribution, for which the gradient of the maximum likelihood estimate is intractable. Neural networks are computational models, which can be used without any probabilistic starting point, e.g. via optimising a hinge loss. Long story short, CD is not a general mean to optimise neural networks. $\endgroup$ – bayerj Sep 21 '16 at 9:06
  • 2
    $\begingroup$ @seanv507 While the claim has been made by the major proponents, there are peer reviewed articles from machine learning's top conferences which evaluate those claims rigorously, e.g. arxiv.org/abs/1406.2572. By now, that claim is widely accepted in the wider ML community, mostly due to its superior theoretical arguments and empirical evidence. I don't think an ad hominem argument is adequate here. $\endgroup$ – bayerj Sep 21 '16 at 9:13
  • 1
    $\begingroup$ I agree that DL theory is lacking. Still you have to acknowledge that articles like this one are advancing that. If you feel that the article is stating wrong results and the conclusions (such as "local minima are less of a problem than saddle points") are invalid, you have to do better than stating yet another ad hominem attack, this time aimed at the ML community as a whole. $\endgroup$ – bayerj Sep 21 '16 at 10:58
  • 1
    $\begingroup$ Recent work shows that with random initialization, gradient descent converges to a local minimum (rather than a saddle point). Paper here: arxiv.org/abs/1602.04915 and blog post here: offconvex.org/2016/03/24/saddles-again On the other hand, there's a (less) recent hypothesis that in large neural networks, the local minima are about as good as the global, discussed here: stats.stackexchange.com/questions/203288/… $\endgroup$ – DavidR Sep 21 '16 at 22:11
12
$\begingroup$

There are all sorts of local search algorithms you could use, backpropagation has just proved to be the most efficient for more complex tasks in general; there are circumstances where other local searches are better.

You could use random-start hill climbing on a neural network to find an ok solution quickly, but it wouldn't be feasible to find a near optimal solution.

Wikipedia (I know, not the greatest source, but still) says

For problems where finding the precise global optimum is less important than finding an acceptable local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent.

source

As for genetic algorithms, I would see Backpropagation vs Genetic Algorithm for Neural Network training

The main case I would make for backprop is that it is very widely used and has had a lot of great improvements. These images really show some of the incredible advancements to vanilla backpropagation.

I wouldn't think of backprop as one algorithm, but a class of algorithms.

I'd also like to add that for neural networks, 10k parameters is small beans. Another search would work great, but on a deep network with millions of parameters, it's hardly practical.

$\endgroup$
12
$\begingroup$

Well, the original neural networks, before the backpropagation revolution in the 70s, were "trained" by hand. :)

That being said:

There is a "school" of machine learning called extreme learning machine that does not use backpropagation.

What they do do is to create a neural network with many, many, many nodes --with random weights-- and then train the last layer using minimum squares (like a linear regression). They then either prune the neural network afterwards or they apply regularization in the last step (like lasso) to avoid overfitting. I have seen this applied to neural networks with a single hidden layer only. There is no training, so it's super fast. I did some tests and surprisingly, these neural networks "trained" this way are quite accurate.

Most people, at least the ones I work with, treat this machine learning "school" with derision and they are an outcast group with their own conferences and so on, but I actually think it's kind of ingenuous.


One other point: within backpropagation, there are alternatives that are seldom mentioned like resilient backproagation, which are implemented in R in the neuralnet package, which only use the magnitude of the derivative. The algorithm is made of if-else conditions instead of linear algebra. They have some advantages over traditional backpropagation, namely you do not need to normalize your data because they do not suffer from the vanishing gradient problem.

$\endgroup$
  • $\begingroup$ Cab you do (most or all of) the spiel in your 4th paragraph, and then use the result as the starting point for a derivative based optimization to "fine tune" it. $\endgroup$ – Mark L. Stone Sep 23 '16 at 23:51
  • 1
    $\begingroup$ @MarkL.Stone I don't know anyone who has done backpropagation by first applying a linear regression to the latter layer. It sounds interesting though. $\endgroup$ – Ricardo Cruz Sep 26 '16 at 11:27
  • 1
    $\begingroup$ As far as I know, the controversy around ELMs is mostly due to ethical aspects, not implementation. Schmidt et al had already touched the subject in 1992, with their Feedforward Network with random weights. $\endgroup$ – Firebug May 22 '17 at 17:55
3
$\begingroup$

You can use pretty much any numerical optimization algorithm to optimize weights of a neural network. You can also use mixed continous-discrete optimization algorithms to optimize not only weights, but layout itself (number of layers, number of neurons in each layer, even type of the neuron). However there's no optimization algorithm that do not suffer from "curse of dimensionality" and local optimas in some manner

$\endgroup$
3
$\begingroup$

You can also use another network to advise how the parameters should be updated.

There is the Decoupled Neural Interfaces (DNI) from Google Deepmind. Instead of using backpropagation, it uses another set of neural networks to predict how to update the parameters, which allows for parallel and asynchronous parameter update.

The paper shows that DNI increases the training speed and model capacity of RNNs, and gives comparable results for both RNNs and FFNNs on various tasks.


The paper also listed and compared many other non-backpropagation methods

Our synthetic gradient model is most analogous to a value function which is used for gradient ascent [2] or a value function used for bootstrapping. Most other works that aim to remove backpropagation do so with the goal of performing biologically plausible credit assignment, but this doesn’t eliminate update locking between layers. E.g. target propagation [3, 15] removes the reliance on passing gradients between layers, by instead generating target activations which should be fitted to. However these targets must still be generated sequentially, propagating backwards through the network and layers are therefore still update- and backwardslocked. Other algorithms remove the backwards locking by allowing loss or rewards to be broadcast directly to each layer – e.g. REINFORCE [21] (considering all activations are actions), Kickback 1, and Policy Gradient Coagent Networks [20] – but still remain update locked since they require rewards to be generated by an output (or a global critic). While Real-Time Recurrent Learning [22] or approximations such as [17] may seem a promising way to remove update locking, these methods require maintaining the full (or approximate) gradient of the current state with respect to the parameters. This is inherently not scalable and also requires the optimiser to have global knowledge of the network state. In contrast, by framing the interaction between layers as a local communication problem with DNI, we remove the need for global knowledge of the learning system. Other works such as [4, 19] allow training of layers in parallel without backpropagation, but in practice are not scalable to more complex and generic network architectures.

$\endgroup$
2
$\begingroup$

As long as this is a community question , I thought I would add another response. "Back Propagation" is simply the gradient descent algorithm. It involves using only the first derivative of the function for which one is trying to find the local minima or maxima. There is another method called Newton's method or Newton-Raphson which involves calculating the Hessian and so uses second derivatives. It can succeed in instances in which gradient descent fails. I am told by others more knowledgeable than me, and yes this is a second hand appeal to authority, that it is not used in neural nets because calculating all the second derivatives is too costly in terms of computation.

$\endgroup$

protected by Community Nov 13 '16 at 13:48

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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