21
$\begingroup$

In training deep and shallow neural networks, why are gradient methods (e.g. gradient descent, Nesterov, Newton-Raphson) commonly used, as opposed to other metaheuristics?

By metaheuristics I mean methods such as simulated annealing, ant colony optimization, etc., which were developed to avoid getting stuck in a local minima.

$\endgroup$
13
$\begingroup$

Extending @Dikran Marsupial's answer....

Anna Choromanska and her colleagues in Yan LeCunn's group at NYU, address this in their 2014 AISTATS paper "The Loss Surface of Multilayer Nets". Using random matrix theory, along with some experiments, they argue that:

  • For large-size networks, most local minima are equivalent and yield similar performance on a test set.

  • The probability of finding a "bad" (high value) local minimum is non-zero for small-size networks and decreases quickly with networks size.

  • Struggling to find the global minimum on the training set (as opposed to one of the many good local ones) is not useful in practice and may lead to overfitting.

[From page 2 of the paper]

In this view, there's not a great reason to deploy heavy-weight approaches for finding the global minimum. That time would be better spent trying out new network topologies, features, data sets, etc.

That said, lots of people have thought about augmenting or replacing SGD. For fairly small networks (by contemporary standards), these improved metahuristics do seem to do something Mavrovouniotis and Yang (2016) show that ant colony optimization + backprop beats unmodified backprop on several benchmark data sets (albeit not by much). Rere el al. (2015) use simulated annealing to train a CNN and find it initially performs better on the validation set. After 10 epochs, however, only a a very small (and not-tested-for-significance) difference in performance remains. The faster convergence-per-epoch advantage is also offset by a dramatically larger amount of computation time per epoch, so this is not a obvious win for simulated annealing.

It is possible that these heuristics do a better job of initializing the network and once it has been pointed down the right path, any optimizer will do. Sutskever et al. (2013) from Geoff Hinton's group argue something like this in their 2013 ICML paper.

| cite | improve this answer | |
$\endgroup$
17
$\begingroup$

Local minima are not really as great a problem with neural nets as is often suggested. Some of the local minima are due to the symmetry of the network (i.e. you can permute the hidden neurons and leave the function of the network unchanged. All that is necessary is to find a good local minima, rather than the global minima. As it happens aggressively optimising a very flexible model, such as a neural network, is likely to be a recipe for overfitting the data, so using e.g. simulated annealing to find the global minima of the training criterion is likely to give a neural network with worse generalisation performance than one trained by gradient descent that ends up in a local minima. If these heuristic optimisation methods are used, then I would advise including a regularisation term to limit the complexity of the model.

... or alternatively use e.g. a kernel method or a radial basis function model, which is likely to be less trouble.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ if you would have to solve a problem on how to survive on Earth as an organism , a simple amoeba solution would work. I am sure with backprop you could train thousands of different amoebas starting from different random weights. These amoebas would all be local minimas. However if you would use Genetic Algorithm long enough, you could evolve a smart organism like a human being or a dolphin, and that organism would have much higher survival rate than an amoeba. That's the difference between a global minima and a local minima. Is local minima a problem? All depends on what you are after. $\endgroup$ – Nulik Mar 14 at 19:44
  • $\begingroup$ @Nulik no, not really, you would be more likely to end up with an organism that was so highly adapted to its environment that the slightest change in the environmental would result in its extinction (i.e. it would be over-fitted to its environment in the same way a neural net would be over-fitted to its training data using a GA). We don't actually want to find the global minima of an unregularised loss. Human beings are not that highly adapted to the environment in which we evolved - we are not a global optimum, but we can be a good second best more or less anywhere. $\endgroup$ – Dikran Marsupial Mar 16 at 9:29

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.