43
$\begingroup$

Gradient Descent has a problem of getting stuck in Local Minima. We need to run gradient descent exponential times in order to find global minima.

Can anybody tell me about any alternatives of gradient descent as applied in neural network learning, along with their pros and cons.

$\endgroup$
37
$\begingroup$

This is more a problem to do with the function being minimized than the method used, if finding the true global minimum is important, then use a method such a simulated annealing. This will be able to find the global minimum, but may take a very long time to do so.

In the case of neural nets, local minima are not necessarily that much of a problem. Some of the local minima are due to the fact that you can get a functionally identical model by permuting the hidden layer units, or negating the inputs and output weights of the network etc. Also if the local minima is only slightly non-optimal, then the difference in performance will be minimal and so it won't really matter. Lastly, and this is an important point, the key problem in fitting a neural network is over-fitting, so aggressively searching for the global minima of the cost function is likely to result in overfitting and a model that performs poorly.

Adding a regularisation term, e.g. weight decay, can help to smooth out the cost function, which can reduce the problem of local minima a little, and is something I would recommend anyway as a means of avoiding overfitting.

The best method however of avoiding local minima in neural networks is to use a Gaussian Process model (or a Radial Basis Function neural network), which have fewer problems with local minima.

$\endgroup$
  • 8
    $\begingroup$ Very true. The problem of not finding the global minimum is overrated. $\endgroup$ – bayerj May 9 '14 at 10:28
  • 1
    $\begingroup$ Overfitting happens when you use many parameters in a model (typical NN use case), it is not related to local minima - at least not in obvious ways. You can get stuck in a bad local minimum even with a small NN, i.e. with very few free parameters. $\endgroup$ – carlosayam Jun 13 '17 at 22:48
  • $\begingroup$ @carlosayam regularisation helps avoid overfitting in overparameterised models (note there is a distinction) by preventing the loss on the training sample from being over-optimised. To some extent the minima (global and local) are caused by that set of parameter values exploiting the meaningless sampling variation in the training sample, which reduces generalisation performance. Searching for the global minima is essentially guaranteeing that exploitation will take place. $\endgroup$ – Dikran Marsupial Jun 15 '17 at 8:27
  • $\begingroup$ @DikranMarsupial, you can have many local minima, even with a single model parameter. It depends on the shape of the loss function. Contrived but simple example: $L(\omega)=(x_{(1)} - \omega)^2 + (x_{(2)} - \omega)^2$, where $x_{(1)}, x_{(2)}$ are nearest and 2-nd nearest neighbours to $\omega$. It is easy to see there is a local minimum between every two consecutive points, i.e. the more data the more local minima! The global is attained between the closest points in the dataset. This is extreme, I know, but I've seen similar behaviour solving change-point problems. $\endgroup$ – carlosayam Jun 17 '17 at 0:20
  • $\begingroup$ @carlosayam of course, however we are talking about neural networks, the most significant problem with which tends to be overfitting of an overparameterised model, so aggressively searching for a global minima is likely to make this problem worse. $\endgroup$ – Dikran Marsupial Jun 19 '17 at 9:00
23
$\begingroup$

Gradient descent is an optimization algorithm.

There are many optimization algorithms that operate on a fixed number of real values that are correlated (non-separable). We can divide them roughly in 2 categories: gradient-based optimizers and derivative-free optimizers. Usually you want to use the gradient to optimize neural networks in a supervised setting because that is significantly faster than derivative-free optimization. There are numerous gradient-based optimization algorithms that have been used to optimize neural networks:

  • Stochastic Gradient Descent (SGD), minibatch SGD, ...: You don't have to evaluate the gradient for the whole training set but only for one sample or a minibatch of samples, this is usually much faster than batch gradient descent. Minibatches have been used to smooth the gradient and parallelize the forward and backpropagation. The advantage over many other algorithms is that each iteration is in O(n) (n is the number of weights in your NN). SGD usually does not get stuck in local minima (!) because it is stochastic.
  • Nonlinear Conjugate Gradient: seems to be very successful in regression, O(n), requires the batch gradient (hence, might not be the best choice for huge datasets)
  • L-BFGS: seems to be very successful in classification, uses Hessian approximation, requires the batch gradient
  • Levenberg-Marquardt Algorithm (LMA): This is actually the best optimization algorithm that I know. It has the disadvantage that its complexity is roughly O(n^3). Don't use it for large networks!

And there have been many other algorithms proposed for optimization of neural networks, you could google for Hessian-free optimization or v-SGD (there are many types of SGD with adaptive learning rates, see e.g. here).

Optimization for NNs is not a solved problem! In my experiences the biggest challenge is not to find a good local minimum. However, the challenges are to get out of very flat regions, deal with ill-conditioned error functions etc. That is the reason why LMA and other algorithms that use approximations of the Hessian usually work so well in practice and people try to develop stochastic versions that use second order information with low complexity. However, often a very well tuned parameter set for minibatch SGD is better than any complex optimization algorithm.

Usually you don't want to find a global optimum. Because that usually requires overfitting the training data.

$\endgroup$
15
$\begingroup$

An interesting alternative to gradient descent is the population-based training algorithms such as the evolutionary algorithms (EA) and the particle swarm optimisation (PSO). The basic idea behind population-based approaches is that a population of candidate solutions (NN weight vectors) is created, and the candidate solutions iteratively explore the search space, exchanging information, and eventually converging on a minima. Because many starting points (candidate solutions) are used, the chances of converging on the global minima are significantly increased. PSO and EA have been shown to perform very competitively, often (albeit not always) outperforming gradient descent on complex NN training problems.

$\endgroup$
  • $\begingroup$ +1 Worth bearing in mind though that aggressively optimizing the training criterion is likely to lead to over-fitting, unless steps are taken to prevent it, so I would avoid PSO and EA unless the training criterion includes some form of regularisation or other complexity based penalty. $\endgroup$ – Dikran Marsupial May 12 '14 at 11:52
  • 5
    $\begingroup$ @anna-earwen , could you please provide some references where PSO performs competitively compared to SGD? $\endgroup$ – emrea Jun 14 '17 at 8:46
7
$\begingroup$

I know this thread is quite old and others have done a great job to explain concepts like local minima, overfitting etc. However, as OP was looking for an alternative solution, I will try to contribute one and hope it will inspire more interesting ideas.

The idea is to replace every weight w to w + t, where t is a random number following Gaussian distribution. The final output of the network is then the average output over all possible values of t. This can be done analytically. You can then optimize the problem either with gradient descent or LMA or other optimization methods. Once the optimization is done, you have two options. One option is to reduce the sigma in the Gaussian distribution and do the optimization again and again until sigma reaches to 0, then you will have a better local minimum (but potentially it could cause overfitting). Another option is keep using the one with the random number in its weights, it usually has better generalization property.

The first approach is an optimization trick (I call it as convolutional tunneling, as it use convolution over the parameters to change the target function), it smooth out the surface of the cost function landscape and get rid of some of the local minima, thus make it easier to find global minimum (or better local minimum).

The second approach is related to noise injection (on weights). Notice that this is done analytically, meaning that the final result is one single network, instead of multiple networks.

The followings are example outputs for two-spirals problem. The network architecture is the same for all three of them: there is only one hidden layer of 30 nodes, and the output layer is linear. The optimization algorithm used is LMA. The left image is for vanilla setting; the middle is using the first approach (namely repeatedly reducing sigma towards 0); the third is using sigma = 2.

Result of two-spirals problem by three approaches

You can see that the vanilla solution is the worst, the convolutional tunneling does a better job, and the noise injection (with convolutional tunneling) is the best (in terms of generalization property).

Both convolutional tunneling and the analytical way of noise injection are my original ideas. Maybe they are the alternative someone might be interested. The details can be found in my paper Combining Infinity Number Of Neural Networks Into One. Warning: I am not a professional academic writer and the paper is not peer reviewed. If you have questions about the approaches I mentioned, please leave a comment.

$\endgroup$
1
$\begingroup$

Extreme Learning Machines Essentially they are a neural network where the weights connecting the inputs to the hidden nodes are assigned randomly and never updated. The weights between the hidden nodes and the outputs are learned in a single step by solving a linear equation (matrix inverse).

$\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.