[Extract] ummary of gradient decent optimizers

Extract from
http://ruder.io/optimizing-gradient-descent/

Target
Gradient descent is a way to minimize an objective function J(θ)$J(\theta )$ parameterized by a model's parameters θ∈ℝd$\theta \in {\mathbb{R}}^d$ by updating the parameters in the opposite direction of the gradient of the objective function ∇θJ(θ)${\mathrm{\nabla }}_{\theta }J(\theta )$ w.r.t. to the parameters. The learning rate η$\eta$determines the size of the steps we take to reach a (local) minimum. In other words, we follow the direction of the slope of the surface created by the objective function downhill until we reach a valley. 

Gradient descent variants

There are three variants of gradient descent, which differ in how much data we use to compute the gradient of the objective function. Depending on the amount of data, we make a trade-off between the accuracy of the parameter update and the time it takes to perform an update.

Batch gradient descent

Vanilla gradient descent, aka batch gradient descent, computes the gradient of the cost function w.r.t. to the parameters θ$\theta$ for the entire training dataset:

θ=θ−η⋅∇θJ(θ)$\theta =\theta -\eta \cdot {\mathrm{\nabla }}_{\theta }J(\theta )$.

As we need to calculate the gradients for the whole dataset to perform just one update, batch gradient descent can be very slow and is intractable for datasets that don't fit in memory. Batch gradient descent also doesn't allow us to update our model online, i.e. with new examples on-the-fly.

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad




Batch gradient descent is guaranteed to converge to the global minimum for convex error surfaces and to a local minimum for non-convex surfaces.

Stochastic gradient descent

Stochastic gradient descent (SGD) in contrast performs a parameter update for each training example x(i)$x^{(i)}$ and label y(i)$y^{(i)}$:

θ=θ−η⋅∇θJ(θ;x(i);y(i))$\theta =\theta -\eta \cdot {\mathrm{\nabla }}_{\theta }J(\theta ;x^{(i)};y^{(i)})$.

Batch gradient descent performs redundant computations for large datasets, as it recomputes gradients for similar examples before each parameter update. SGD does away with this redundancy by performing one update at a time. It is therefore usually much faster and can also be used to learn online.

SGD performs frequent updates with a high variance that cause the objective function to fluctuate heavily as in Image 1.

Image 1: SGD fluctuation (Source: Wikipedia)

However, it has been shown that when we slowly decrease the learning rate, SGD shows the same convergence behaviour as batch gradient descent, almost certainly converging to a local or the global minimum for non-convex and convex optimization respectively. 

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

Mini-batch gradient descent

Mini-batch gradient descent finally takes the best of both worlds and performs an update for every mini-batch of n$n$ training examples:

θ=θ−η⋅∇θJ(θ;x(i:i+n);y(i:i+n))$\theta =\theta -\eta \cdot {\mathrm{\nabla }}_{\theta }J(\theta ;x^{(i:i+n)};y^{(i:i+n)})$.

This way, it a) reduces the variance of the parameter updates, which can lead to more stable convergence; and b) can make use of highly optimized matrix optimizations common to state-of-the-art deep learning libraries that make computing the gradient w.r.t. a mini-batch very efficient. Common mini-batch sizes range between 50 and 256, but can vary for different applications. Mini-batch gradient descent is typically the algorithm of choice when training a neural network and the term SGD usually is employed also when mini-batches are used. 

In code, instead of iterating over examples, we now iterate over mini-batches of size 50:

for i in range(nb_epochs):
  np.random.shuffle(data)
  for batch in get_batches(data, batch_size=50):
    params_grad = evaluate_gradient(loss_function, batch, params)
    params = params - learning_rate * params_grad

Challenges

Vanilla mini-batch gradient descent, however, does not guarantee good convergence, but offers a few challenges that need to be addressed:

• Choosing a proper learning rate can be difficult. A learning rate that is too small leads to painfully slow convergence, while a learning rate that is too large can hinder convergence and cause the loss function to fluctuate around the minimum or even to diverge.
• Learning rate schedules [11] try to adjust the learning rate during training by e.g. annealing, i.e. reducing the learning rate according to a pre-defined schedule or when the change in objective between epochs falls below a threshold. These schedules and thresholds, however, have to be defined in advance and are thus unable to adapt to a dataset's characteristics [10].
• Additionally, the same learning rate applies to all parameter updates. If our data is sparse and our features have very different frequencies, we might not want to update all of them to the same extent, but perform a larger update for rarely occurring features.
• Another key challenge of minimizing highly non-convex error functions common for neural networks is avoiding getting trapped in their numerous suboptimal local minima. Dauphin et al. [19] argue that the difficulty arises in fact not from local minima but from saddle points, i.e. points where one dimension slopes up and another slopes down. These saddle points are usually surrounded by a plateau of the same error, which makes it notoriously hard for SGD to escape, as the gradient is close to zero in all dimensions.

Gradient descent optimization algorithms

In the following, we will outline some algorithms that are widely used by the deep learning community to deal with the aforementioned challenges. 

Momentum

SGD has trouble navigating ravines, i.e. areas where the surface curves much more steeply in one dimension than in another [1], which are common around local optima. In these scenarios, SGD oscillates across the slopes of the ravine while only making hesitant progress along the bottom towards the local optimum as in Image 2.

Image 2: SGD without momentum

Image 3: SGD with momentum

Momentum [2] is a method that helps accelerate SGD in the relevant direction and dampens oscillations (衰减振荡) as can be seen in Image 3. It does this by adding a fraction 

γ$\gamma$ of the update vector of the past time step to the current update vector:

vtθ=γvt−1+η∇θJ(θ)=θ−vt

Essentially, when using momentum, we push a ball down a hill. The ball accumulates momentum as it rolls downhill, becoming faster and faster on the way (until it reaches its terminal velocity if there is air resistance, i.e. γ<1$\gamma <1$). The same thing happens to our parameter updates: The momentum term increases for dimensions whose gradients point in the same directions and reduces updates for dimensions whose gradients change directions. As a result, we gain faster convergence and reduced oscillation.

Nesterov accelerated gradient

However, a ball that rolls down a hill, blindly following the slope, is highly unsatisfactory. We'd like to have a smarter ball, a ball that has a notion of where it is going so that it knows to slow down before the hill slopes up again.

Nesterov accelerated gradient (NAG) [7] is a way to give our momentum term this kind of prescience. We know that we will use our momentum term γvt−1$\gamma v_{t-1}$ to move the parameters θ$\theta$. Computing θ−γvt−1$\theta -\gamma v_{t-1}$ thus gives us an approximation of the next position of the parameters (the gradient is missing for the full update), a rough idea where our parameters are going to be. We can now effectively look ahead by calculating the gradient not w.r.t. to our current parameters θ$\theta$ but w.r.t. the approximate future position of our parameters:

vtθ=γvt−1+η∇θJ(θ−γvt−1)=θ−vt$\begin{array}{r}\begin{array}{rl}{v}_t& =\gamma v_{t-1}+\eta {\mathrm{\nabla }}_{\theta }J(\theta -\gamma v_{t-1})\\ \theta & =\theta -v_t\end{array}\end{array}$

Again, we set the momentum term γ$\gamma$ to a value of around 0.9. While Momentum first computes the current gradient (small blue vector in Image 4) and then takes a big jump in the direction of the updated accumulated gradient (big blue vector), NAG first makes a big jump in the direction of the previous accumulated gradient (brown vector), measures the gradient and then makes a correction (red vector), which results in the complete NAG update (green vector). This anticipatory update prevents us from going too fast and results in increased responsiveness, which has significantly increased the performance of RNNs on a number of tasks [8].

Image 4: Nesterov update (Source: G. Hinton's lecture 6c)

Refer to here for another explanation about the intuitions behind NAG, while Ilya Sutskever gives a more detailed overview in his PhD thesis [9].

Now that we are able to adapt our updates to the slope of our error function and speed up SGD in turn, we would also like to adapt our updates to each individual parameter to perform larger or smaller updates depending on their importance.

Adagrad

Adagrad [3] is an algorithm for gradient-based optimization that does just this: It adapts the learning rate to the parameters, performing larger updates for infrequent and smaller updates for frequent parameters. For this reason, it is well-suited for dealing with sparse data. Dean et al. [4] have found that Adagrad greatly improved the robustness of SGD and used it for training large-scale neural nets at Google, which -- among other things -- learned to recognize cats in Youtube videos. Moreover, Pennington et al. [5] used Adagrad to train GloVe word embeddings, as infrequent words require much larger updates than frequent ones.

Previously, we performed an update for all parameters θ$\theta$ at once as every parameter θi${\theta }_i$ used the same learning rate η$\eta$. As Adagrad uses a different learning rate for every parameter θi${\theta }_i$ at every time step t$t$, we first show Adagrad's per-parameter update, which we then vectorize. For brevity, we set gt,i$g_{t,i}$ to be the gradient of the objective function w.r.t. to the parameter θi${\theta }_i$ at time step t$t$:

gt,i=∇θJ(θi)$g_{t,i}={\mathrm{\nabla }}_{\theta }J({\theta }_i)$.

The SGD update for every parameter θi${\theta }_i$ at each time step t$t$ then becomes:

θt+1,i=θt,i−η⋅gt,i${\theta }_{t+1,i}={\theta }_{t,i}-\eta \cdot g_{t,i}$.

In its update rule, Adagrad modifies the general learning rate η$\eta$ at each time step t$t$ for every parameter θi${\theta }_i$ based on the past gradients that have been computed for θi${\theta }_i$:

θt+1,i=θt,i−ηGt,ii+ϵ‾‾‾‾‾‾‾‾√⋅gt,i${\theta }_{t+1,i}={\theta }_{t,i}-{\displaystyle \frac{\eta }{\sqrt{G_{t,ii}+ϵ}}}\cdot g_{t,i}$.

Gt∈ℝd×d$G_t\in {\mathbb{R}}^{d\times d}$ here is a diagonal matrix where each diagonal element i,i$i,i$ is the sum of the squares of the gradients w.r.t. θi${\theta }_i$ up to time step t$t$[25], while ϵ$ϵ$ is a smoothing term that avoids division by zero (usually on the order of 1e−8$1e-8$). Interestingly, without the square root operation, the algorithm performs much worse.

As Gt$G_t$ contains the sum of the squares of the past gradients w.r.t. to all parameters θ$\theta$ along its diagonal, we can now vectorize our implementation by performing an element-wise matrix-vector multiplication ⊙$\odot$ between Gt$G_t$ and gt$g_t$:

θt+1=θt−ηGt+ϵ‾‾‾‾‾‾√⊙gt${\theta }_{t+1}={\theta }_t-{\displaystyle \frac{\eta }{\sqrt{G_t+ϵ}}}\odot g_t$.

One of Adagrad's main benefits is that it eliminates the need to manually tune the learning rate. Most implementations use a default value of 0.01 and leave it at that.

Adagrad's main weakness is its accumulation of the squared gradients in the denominator: Since every added term is positive, the accumulated sum keeps growing during training. This in turn causes the learning rate to shrink and eventually become infinitesimally small, at which point the algorithm is no longer able to acquire additional knowledge. The following algorithms aim to resolve this flaw.

Adadelta

Adadelta [6] is an extension of Adagrad that seeks to reduce its aggressive, monotonically decreasing learning rate. Instead of accumulating all past squared gradients, Adadelta restricts the window of accumulated past gradients to some fixed size w$w$.

Instead of inefficiently storing w$w$ previous squared gradients, the sum of gradients is recursively defined as a decaying average of all past squared gradients. The running average E[g2]t$E[g^2{]}_t$ at time step t$t$ then depends (as a fraction γ$\gamma$ similarly to the Momentum term) only on the previous average and the current gradient:

E[g2]t=γE[g2]t−1+(1−γ)g2t$E[g^2{]}_t=\gamma E[g^2{]}_{t-1}+(1-\gamma )g_t^2$.

We set γ$\gamma$ to a similar value as the momentum term, around 0.9. For clarity, we now rewrite our vanilla SGD update in terms of the parameter update vector Δθt$\mathrm{\Delta }{\theta }_t$:

Δθtθt+1=−η⋅gt,i=θt+Δθt$\begin{array}{r}\begin{array}{rl}\mathrm{\Delta }{\theta }_t& =-\eta \cdot g_{t,i}\\ {\theta }_{t+1}& ={\theta }_t+\mathrm{\Delta }{\theta }_t\end{array}\end{array}$

The parameter update vector of Adagrad that we derived previously thus takes the form:

Δθt=−ηGt+ϵ‾‾‾‾‾‾√⊙gt$\mathrm{\Delta }{\theta }_t=-{\displaystyle \frac{\eta }{\sqrt{G_t+ϵ}}}\odot g_t$.

We now simply replace the diagonal matrix Gt$G_t$ with the decaying average over past squared gradients E[g2]t$E[g^2{]}_t$:

Δθt=−ηE[g2]t+ϵ‾‾‾‾‾‾‾‾‾‾√gt$\mathrm{\Delta }{\theta }_t=-{\displaystyle \frac{\eta }{\sqrt{E[g^2{]}_t+ϵ}}}{g}_t$.

As the denominator is just the root mean squared (RMS) error criterion of the gradient, we can replace it with the criterion short-hand:

Δθt=−ηRMS[g]tgt$\mathrm{\Delta }{\theta }_t=-{\displaystyle \frac{\eta }{RMS[g{]}_t}}{g}_t$.

The authors note that the units in this update (as well as in SGD, Momentum, or Adagrad) do not match, i.e. the update should have the same hypothetical units as the parameter. To realize this, they first define another exponentially decaying average, this time not of squared gradients but of squared parameter updates:

E[Δθ2]t=γE[Δθ2]t−1+(1−γ)Δθ2t$E[\mathrm{\Delta }{\theta }^2{]}_t=\gamma E[\mathrm{\Delta }{\theta }^2{]}_{t-1}+(1-\gamma )\mathrm{\Delta }{\theta }_t^2$.

The root mean squared error of parameter updates is thus:

RMS[Δθ]t=E[Δθ2]t+ϵ‾‾‾‾‾‾‾‾‾‾‾√$RMS[\mathrm{\Delta }\theta {]}_t=\sqrt{E[\mathrm{\Delta }{\theta }^2{]}_t+ϵ}$.

Since RMS[Δθ]t$RMS[\mathrm{\Delta }\theta {]}_t$ is unknown, we approximate it with the RMS of parameter updates until the previous time step. Replacing the learning rate η$\eta$ in the previous update rule with RMS[Δθ]t−1$RMS[\mathrm{\Delta }\theta {]}_{t-1}$ finally yields the Adadelta update rule:

Δθtθt+1=−RMS[Δθ]t−1RMS[g]tgt=θt+Δθt$\begin{array}{r}\begin{array}{rl}\mathrm{\Delta }{\theta }_t& =-{\displaystyle \frac{RMS[\mathrm{\Delta }\theta {]}_{t-1}}{RMS[g{]}_t}}{g}_t\\ {\theta }_{t+1}& ={\theta }_t+\mathrm{\Delta }{\theta }_t\end{array}\end{array}$

With Adadelta, we do not even need to set a default learning rate, as it has been eliminated from the update rule.

Visualization of algorithms

The following two animations (Image credit: Alec Radford) provide some intuitions towards the optimization behaviour of the presented optimization algorithms. Also have a look here for a description of the same images by Karpathy and another concise overview of the algorithms discussed.

In Image 5, we see their behaviour on the contours of a loss surface (the Beale function) over time. Note that Adagrad, Adadelta, and RMSprop almost immediately head off in the right direction and converge similarly fast, while Momentum and NAG are led off-track, evoking the image of a ball rolling down the hill. NAG, however, is quickly able to correct its course due to its increased responsiveness by looking ahead and heads to the minimum.

Image 6 shows the behaviour of the algorithms at a saddle point, i.e. a point where one dimension has a positive slope, while the other dimension has a negative slope, which pose a difficulty for SGD as we mentioned before. Notice here that SGD, Momentum, and NAG find it difficulty to break symmetry, although the two latter eventually manage to escape the saddle point, while Adagrad, RMSprop, and Adadelta quickly head down the negative slope.

Image 5: SGD optimization on loss surface contours

Image 6: SGD optimization on saddle point

As we can see, the adaptive learning-rate methods, i.e. Adagrad, Adadelta, RMSprop, and Adam are most suitable and provide the best convergence for these scenarios.

Which optimizer to use?

So, which optimizer should you now use? If your input data is sparse, then you likely achieve the best results using one of the adaptive learning-rate methods. An additional benefit is that you won't need to tune the learning rate but likely achieve the best results with the default value.

In summary, RMSprop is an extension of Adagrad that deals with its radically diminishing learning rates. It is identical to Adadelta, except that Adadelta uses the RMS of parameter updates in the numinator update rule. Adam, finally, adds bias-correction and momentum to RMSprop. Insofar, RMSprop, Adadelta, and Adam are very similar algorithms that do well in similar circumstances. Kingma et al. [15] show that its bias-correction helps Adam slightly outperform RMSprop towards the end of optimization as gradients become sparser. Insofar, Adam might be the best overall choice.

Interestingly, many recent papers use vanilla SGD without momentum and a simple learning rate annealing schedule. As has been shown, SGD usually achieves to find a minimum, but it might take significantly longer than with some of the optimizers, is much more reliant on a robust initialization and annealing schedule, and may get stuck in saddle points rather than local minima. Consequently, if you care about fast convergence and train a deep or complex neural network, you should choose one of the adaptive learning rate methods.

Additional strategies for optimizing SGD

Finally, we introduce additional strategies that can be used alongside any of the previously mentioned algorithms to further improve the performance of SGD. For a great overview of some other common tricks, refer to [22].

Shuffling and Curriculum Learning

Generally, we want to avoid providing the training examples in a meaningful order to our model as this may bias the optimization algorithm. Consequently, it is often a good idea to shuffle the training data after every epoch.

On the other hand, for some cases where we aim to solve progressively harder problems, supplying the training examples in a meaningful order may actually lead to improved performance and better convergence. The method for establishing this meaningful order is called Curriculum Learning [16].

Zaremba and Sutskever [17] were only able to train LSTMs to evaluate simple programs using Curriculum Learning and show that a combined or mixed strategy is better than the naive one, which sorts examples by increasing difficulty.

Batch normalization

To facilitate learning, we typically normalize the initial values of our parameters by initializing them with zero mean and unit variance. As training progresses and we update parameters to different extents, we lose this normalization, which slows down training and amplifies changes as the network becomes deeper.

Batch normalization [18] reestablishes these normalizations for every mini-batch and changes are back-propagated through the operation as well. By making normalization part of the model architecture, we are able to use higher learning rates and pay less attention to the initialization parameters. Batch normalization additionally acts as a regularizer, reducing (and sometimes even eliminating) the need for Dropout.

Early stopping

According to Geoff Hinton: "Early stopping (is) beautiful free lunch" (NIPS 2015 Tutorial slides, slide 63). You should thus always monitor error on a validation set during training and stop (with some patience) if your validation error does not improve enough.

Gradient noise

Neelakantan et al. [21] add noise that follows a Gaussian distribution N(0,σ2t)$N(0,{\sigma }_t^2)$ to each gradient update:

gt,i=gt,i+N(0,σ2t)$g_{t,i}=g_{t,i}+N(0,{\sigma }_t^2)$.

They anneal the variance according to the following schedule:

σ2t=η(1+t)γ${\sigma }_t^2={\displaystyle \frac{\eta }{(1+t{)}^{\gamma }}}$.

They show that adding this noise makes networks more robust to poor initialization and helps training particularly deep and complex networks. They suspect that the added noise gives the model more chances to escape and find new local minima, which are more frequent for deeper models.