3
$\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$
6
$\begingroup$
  1. It would be a waste of information; the gradient is available, so use it and save time.
  2. There is reason to believe that the local optima are good; see, for example, Choromanska et al. (notes).
  3. Over-optimizing for the training set leads to worse generalization, so sometimes we deliberately don't even try by stopping early. Probably the best free lunch in machine learning.
$\endgroup$
3
$\begingroup$

In a large neural network there can be millions of free parameters, and assessing the current heuristic means evaluating the network for a significant number of training records, assuming supervised or semi-supervised learning.

Gradient-based methods can cope with this amount of parameters in a reasonable time. The gradient can be approximated for all parameters in a single pass through a subset of the training data, and a single step will update all of parameters at once. There is theoretical support showing gradient-based changes to weights should converge to a better solution (caveat being local minima). There is no theoretical result that shows that a set of weights with optimal values for some of its parameters (in some local subset of all the weights) should be better at a task than a set of random weights. This puts search-based methods that look to build good local choices and combine them at a disadvantage in that we really don't know whether they have a chance of working for a specific problem.

Genetic algorithms have successfully been used to train small/medium networks, e.g. NEAT. This works well in small control systems with immediate feedback (although reinforcement learning may be a better choice in many cases), and also commonly seen in a-life simulations. But this approach does not scale up to complex networks, or supervised learning scenarios with large amounts of data. The cost of assessing the GA against the training data for each member of the population, and the size of population/number of assessments required for a search for a genome that might be several megabytes, makes GA for large networks computationally too expensive.

Simulated annealing cannot be used directly to search weights in a standard feed-forward network, since it needs a heuristic calculated (e.g. from a significant portion of training data) for every tiny "move" mode in parameter space - the cost of each move needs to be fast to compute. However, Boltzmann Machine training is closely related to simulated annealing, and Restricted Boltzmann Machines can be used to pre-train deep neural networks, amongst other things, so there are cases where SA is sort-of used.

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