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