Is it possible to train a neural network without backpropagation?

Question

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?

Answer 1

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.)

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.