Neural Network Optimization Algorithms

Question

What are some of the popular optimization algorithms used for training neural networks?

Answer 1

Here's a list of popular algorithms used in training neural networks:

• SGD updates parameters in the negative direction of the gradient, learning rate parameter $\epsilon_k$ should be decreased over time, computation time is proportional to mini-batch size $m$: $$ g = \frac{1}{m}\nabla_\theta \sum_i L(f(x^{(i)};\theta), y^{(i)}) \\ \theta = \theta - \epsilon_k \times g $$

• Momentum accumulates exponentially decaying moving average of past gradients and continues to move in their direction, thus step size depends on how large and how aligned the sequence of gradients are, common values of momentum parameter $\alpha$ are 0.5 and 0.9 $$ v = \alpha v - \epsilon \nabla_\theta \big(\frac{1}{m}\sum_i L(f(x^{(i)};\theta), y^{(i)}) \big) \\ \theta = \theta + v $$

• Nesterov Momentum inspired by Nesterov's accelerated gradient method, difference betweent Nesterov and standard momentum is where the gradient is evaluated, with Nesterov's momentum the gradient is evaluated after the current velocity is applied, thus Nesterov's momentum adds a correction factor to the gradient: $$ v = \alpha v - \epsilon \nabla_\theta \big(\frac{1}{m}\sum_i L(f(x^{(i)};\theta + \alpha \times v), y^{(i)}) \big) \\ \theta = \theta + v $$

• AdaGrad adapts the learning rates of all model parameters, learning rate is inversely proportional to the square root of the sum of historical squared values, weights that receive high gradients will have their effective learning rate reduced, while weights that receive small or infrequent updates will have their effective learning rate increased: the net effect is greater progress in the more gently sloped directions of parameter space: $$ g = \frac{1}{m}\nabla_\theta \sum_i L(f(x^{(i)};\theta), y^{(i)}) \\ s = s + g^{T}g \\ \theta = \theta - \epsilon_k \times g / \sqrt{s+eps} $$

• RMSProp modifies AdaGrad by changing the gradient accumulation into an exponentially weighted moving average, it discards history from the extreme past. RMSProp has been shown to be an effective and practical optimization algorithm for deep neural networks.

$$ g = \frac{1}{m}\nabla_\theta \sum_i L(f(x^{(i)};\theta), y^{(i)}) \\ s = \mathrm{decay\_rate}\times s + (1-\mathrm{decay\_rate}) g^{T}g \\ \theta = \theta - \epsilon_k \times g / \sqrt{s+eps} $$

• Adam derives from "adaptive moments", it can be seen as a variant on the combination of RMSProp and momentum, the update looks like RMSProp except that a smooth version of the gradient is used instead of the raw stochastic gradient, the full adam update also includes a bias correction mechanism, recommended values in the paper are $\epsilon = 1e-8$, $\beta_1 = 0.9$, $\beta_2 = 0.999$ $$ g = \frac{1}{m}\nabla_\theta \sum_i L(f(x^{(i)};\theta), y^{(i)}) \\ m = \beta_1 m + (1-\beta_1) g\\ s = \beta_2 v + (1-\beta_2) g^{T}g \\ \theta = \theta - \epsilon_k \times m / \sqrt{s+eps} $$

For more information about the algorithms, I recommend referring to deep learning book by Ian Goodfellow and a neural network course. For a TensorFlow implementation have a look at the following ipython notebook.

Answer 2

On top of the 1st order algos listed out by @VadimSnolyakov, it is perhaps worth mentioning 2nd order gradient methods.

• Second order methods often converge much more quickly, but it can be very expensive to calculate and store the Hessian matrix.
• In general, most people prefer clever first order methods which need only the value of the error function and its gradient with respect to the parameters (source)

2nd order gradient methods include the classical Newtons's method, Broyden-Fletcher-Goldfarb-Shanno (BFGS) and other quasi-Newton methods, where an approximation for the Hessian (or its inverse directly) is built up from changes in the gradient, as it is the case, for example, in Levenberg-Marquardt.

---

Edit 1:

It has been questioned whether the use of second order methods is "popular". Well, in order to settle the dispute we would need to agree on how to define and measure "popularity".

However, we read on the notes of the Stanford CS class CS231n: Convolutional Neural Networks for Visual Recognition

Second order methods

A second, popular group of methods for optimization in context of deep learning is based on Newton’s method (source)

We can not draw on conclusion on our dispute based on this quote but yes, second order methods may be an option, especially if you have shallow NNs (due to the computational burden the Hessian approximation brings).

On top of that, some promising research has already been carried on comparing optimization methodologies when dealing with auto-encoders and in particular sparse auto-encoders:

More significant speed improvements of L-BFGS and CG over SGDs are observed in our experiments with sparse autoencoders. This is because having a larger minibatch makes the optimization problem easier for sparse autoencoders: in this case, the cost of estimating the second-order and conjugate information is small compared to the cost of computing the gradient (source)

In the end, we might regard the extra cost associated to the approximation of the Hessian as an alternative to:

1) the need of pre-training

why does pre-training work and why is it necessary? Some researchers (e.g. Erhan et al., 2010) have investigated this question and proposed various explanations such as a higher prevalence of bad local optima in the learning objectives of deep models. Another explanation is that these objectives exhibit pathological curvature making them nearly impossible for curvature-blind methods like gradient-descent to successfully navigate (source)

• having to tune first-order methods - curvature helps!

One key disadvantage of SGDs is that they require much manual tuning of optimization parameters such as learning rates and convergence criteria. If one does not know the task at hand well, it is very difficult to find a good learning rate or a good convergence criterion. (source)

All this is far for being exhaustive but I hope interesting enough to encourage us to dig deeper. In research, we assist to waves of interest and popularity. We might in fact see a resurgence of interest in second order methods in the upcoming future.

Of particular interest to the use of second-order methods is the relatively recent (or not so recent, depending on your type of work) discovery that saddle points are far more common in high-dimensional space than local minima (see [1406.2572] Identifying and attacking the saddle point problem in high-dimensional non-convex optimization). This is a bit counterintuitive, since local minima are far more ubiquitous in lower-dimensional problems. Purely first-order methods cannot differentiate between saddle points and local minima, and thus for certain problems, SGD can become stuck along paths of slow convergence around saddle points (source)