An overview of gradient descent optimization algorithms.

 Gradient descent variants

    在平时的应用过程中共有三种主流的梯度下降算法：batch gradient decent、stochastic gradient decent、mini-batch gradient decent. 其中第一种和第三种首先分别计算每一个样本的损失函数梯度之后对它们求平均作为更新依据。

Challenges

• Choosing a proper learning rate can be difficult. 

• 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. [3] 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

动量（Momentum）

          SGD has trouble navigating ravines, i.e. areas where the surface curves much more steeply in one dimension than in another [4], 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 [5] 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:

        Note: Some implementations exchange the signs in the equations. The momentum term $\gamma$ is usually set to 0.9 or a similar value.

Nesterov accelerated gradient(NAG  改进版动量)

    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) [6] is a way to give our momentum term this kind of prescience. We know that we will use our momentum term $\gamma v_{t-1}$ to move the parameters $\theta$. Computing $\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:

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

Adagrad（自适应学习率，不同参数采用不同学习率）

Adagrad [9] is an algorithm for gradient-based optimization that does just this: It adapts the learning rate to the parameters, performing smaller updates
(i.e. low learning rates) for parameters associated with frequently occurring features, and larger updates (i.e. high learning rates) for parameters associated with infrequent features. For this reason, it is well-suited for dealing with sparse data. Dean et al. [10] 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. [11] 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 ${\theta }_i$ used the same learning rate $\eta$. As Adagrad uses a different learning rate for every parameter ${\theta }_i$ at every time step $t$, we first show Adagrad's per-parameter update, which we then vectorize. For brevity, we use $g_t$ to denote the gradient at time step $t$. $g_{t,i}$ is then the partial derivative of the objective function w.r.t. to the parameter ${\theta }_i$ at time step $t$:

$g_{t,i}={\nabla }_{\theta }J\left({\theta }_{t,i}\right)$.

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

${\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$ for every parameter ${\theta }_i$ based on the past gradients that have been computed for ${\theta }_i$:

${\theta }_{t+1,i}={\theta }_{t,i}-\frac{\eta }{\sqrt{G_{t,ii}+ϵ}}\cdot g_{t,i}$.

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

As $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 a matrix-vector product $\odot$ between $G_t$ and $g_t$:

${\theta }_{t+1}={\theta }_t-\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（Adagrad的改进版）

Adadelta [13] 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$.

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

$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 $\Delta {\theta }_t$:

$\begin{array}{c}\begin{array}{cc}\Delta {\theta }_t& =-\eta \cdot g_{t,i}\\ {\theta }_{t+1}& ={\theta }_t+\Delta {\theta }_t\end{array}\end{array}$

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

$\Delta {\theta }_t=-\frac{\eta }{\sqrt{G_t+ϵ}}\odot g_t$.

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

$\Delta {\theta }_t=-\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:

$\Delta {\theta }_t=-\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[\Delta {\theta }^2{]}_t=\gamma E[\Delta {\theta }^2{]}_{t-1}+(1-\gamma )\Delta {\theta }_t^2$.

The root mean squared error of parameter updates is thus:

$RMS[\Delta \theta {]}_t=\sqrt{E[\Delta {\theta }^2{]}_t+ϵ}$.

Since $RMS[\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[\Delta \theta {]}_{t-1}$ finally yields the Adadelta update rule:

$\begin{array}{c}\begin{array}{cc}\Delta {\theta }_t& =-\frac{RMS[\Delta \theta {]}_{t-1}}{RMS[g{]}_t}{g}_t\\ {\theta }_{t+1}& ={\theta }_t+\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.

RMSprop（Adadelta的简化版，在前几次更新与Adadelta相似）

RMSprop is an unpublished, adaptive learning rate method proposed by Geoff Hinton in Lecture 6e of his Coursera Class.

RMSprop and Adadelta have both been developed independently around the same time stemming from the need to resolve Adagrad's radically diminishing learning rates. RMSprop in fact is identical to the first update vector of Adadelta that we derived above:

$\begin{array}{c}\begin{array}{cc}E[g^2{]}_t& =0.9E[g^2{]}_{t-1}+0.1g_t^2\\ {\theta }_{t+1}& ={\theta }_t-\frac{\eta }{\sqrt{E[g^2{]}_t+ϵ}}{g}_t\end{array}\end{array}$

RMSprop as well divides the learning rate by an exponentially decaying average of squared gradients. Hinton suggests $\gamma$ to be set to 0.9, while a good default value for the learning rate $\eta$ is 0.001.

Adam(动量与Adadelta的结合)

Adaptive Moment Estimation (Adam) [14] is another method that computes adaptive learning rates for each parameter. In addition to storing an exponentially decaying average of past squared gradients $v_t$ like Adadelta and RMSprop, Adam also keeps an exponentially decaying average of past gradients $m_t$, similar to momentum. Whereas momentum can be seen as a ball running down a slope, Adam behaves like a heavy ball with friction, which thus prefers flat minima in the error surface [15]. We compute the decaying averages of past and past squared gradients $m_t$ and $v_t$ respectively as follows:

$\begin{array}{c}\begin{array}{cc}{m}_t& ={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t\\ v_t& ={\beta }_2{v}_{t-1}+(1-{\beta }_2)g_t^2\end{array}\end{array}$

$m_t$ and $v_t$ are estimates of the first moment (the mean) and the second moment (the uncentered variance) of the gradients respectively, hence the name of the method. As $m_t$ and $v_t$ are initialized as vectors of 0's, the authors of Adam observe that they are biased towards zero, especially during the initial time steps, and especially when the decay rates are small (i.e. ${\beta }_1$ and ${\beta }_2$ are close to 1).

They counteract these biases by computing bias-corrected first and second moment estimates:

They then use these to update the parameters just as we have seen in Adadelta and RMSprop, which yields the Adam update rule:

The authors propose default values of 0.9 for ${\beta }_1$, 0.999 for ${\beta }_2$, and ${10}^{-8}$ for $ϵ$. They show empirically that Adam works well in practice and compares favorably to other adaptive learning-method algorithms.

AdaMax

The $v_t$ factor in the Adam update rule scales the gradient inversely proportionally to the ${\ell }_2$ norm of the past gradients (via the $v_{t-1}$ term) and current gradient $|g_t{|}^2$:

$v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)|g_t{|}^2$

We can generalize this update to the ${\ell }_p$ norm. Note that Kingma and Ba also parameterize ${\beta }_2$ as ${\beta }_2^p$:

$v_t={\beta }_2^p{v}_{t-1}+(1-{\beta }_2^p)|g_t{|}^p$

Norms for large $p$ values generally become numerically unstable, which is why ${\ell }_1$ and ${\ell }_2$ norms are most common in practice. However, ${\ell }_{\infty }$ also generally exhibits stable behavior. For this reason, the authors propose AdaMax (Kingma and Ba, 2015) and show that $v_t$ with ${\ell }_{\infty }$ converges to the following more stable value. To avoid confusion with Adam, we use $u_t$ to denote the infinity norm-constrained $v_t$:

$\begin{array}{c}\begin{array}{cc}{u}_t& ={\beta }_2^{\infty }{v}_{t-1}+(1-{\beta }_2^{\infty })|g_t{|}^{\infty }\\ & =max({\beta }_2\cdot v_{t-1},|g_t|)\end{array}\end{array}$

We can now plug this into the Adam update equation by replacing $\sqrt{{\hat{v}}_t}+ϵ$ with $u_t$ to obtain the AdaMax update rule:

${\theta }_{t+1}={\theta }_t-\frac{\eta }{u_t}{\hat{m}}_t$

Note that as $u_t$ relies on the $max$ operation, it is not as suggestible to bias towards zero as $m_t$ and $v_t$ in Adam, which is why we do not need to compute a bias correction for $u_t$. Good default values are again $\eta =0.002$, ${\beta }_1=0.9$, and ${\beta }_2=0.999$.

Nadam

As we have seen before, Adam can be viewed as a combination of RMSprop and momentum: RMSprop contributes the exponentially decaying average of past squared gradients $v_t$, while momentum accounts for the exponentially decaying average of past gradients $m_t$. We have also seen that Nesterov accelerated gradient (NAG) is superior to vanilla momentum.

Nadam (Nesterov-accelerated Adaptive Moment Estimation) [16] thus combines Adam and NAG. In order to incorporate NAG into Adam, we need to modify its momentum term $m_t$.

First, let us recall the momentum update rule using our current notation :

$\begin{array}{c}\begin{array}{cc}{g}_t& ={\nabla }_{{\theta }_t}J\left({\theta }_t\right)\\ m_t& =\gamma m_{t-1}+\eta g_t\\ {\theta }_{t+1}& ={\theta }_t-m_t\end{array}\end{array}$

where $J$ is our objective function, $\gamma$ is the momentum decay term, and $\eta$ is our step size. Expanding the third equation above yields:

${\theta }_{t+1}={\theta }_t-(\gamma m_{t-1}+\eta g_t)$

This demonstrates again that momentum involves taking a step in the direction of the previous momentum vector and a step in the direction of the current gradient.

NAG then allows us to perform a more accurate step in the gradient direction by updating the parameters with the momentum step before computing the gradient. We thus only need to modify the gradient $g_t$ to arrive at NAG:

$\begin{array}{c}\begin{array}{cc}{g}_t& ={\nabla }_{{\theta }_t}J({\theta }_t-\gamma m_{t-1})\\ m_t& =\gamma m_{t-1}+\eta g_t\\ {\theta }_{t+1}& ={\theta }_t-m_t\end{array}\end{array}$

Dozat proposes to modify NAG the following way: Rather than applying the momentum step twice -- one time for updating the gradient $g_t$ and a second time for updating the parameters ${\theta }_{t+1}$ -- we now apply the look-ahead momentum vector directly to update the current parameters:

$\begin{array}{c}\begin{array}{cc}{g}_t& ={\nabla }_{{\theta }_t}J\left({\theta }_t\right)\\ m_t& =\gamma m_{t-1}+\eta g_t\\ {\theta }_{t+1}& ={\theta }_t-(\gamma m_t+\eta g_t)\end{array}\end{array}$

Notice that rather than utilizing the previous momentum vector $m_{t-1}$ as in the equation of the expanded momentum update rule above, we now use the current momentum vector $m_t$ to look ahead. In order to add Nesterov momentum to Adam, we can thus similarly replace the previous momentum vector with the current momentum vector. First, recall that the Adam update rule is the following (note that we do not need to modify ${\hat{v}}_t$):

$\begin{array}{c}\begin{array}{cc}{m}_t& ={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t\\ {\hat{m}}_t& =\frac{m_t}{1-{\beta }_1^t}\\ {\theta }_{t+1}& ={\theta }_t-\frac{\eta }{\sqrt{{\hat{v}}_t}+ϵ}{\hat{m}}_t\end{array}\end{array}$

Expanding the second equation with the definitions of ${\hat{m}}_t$ and $m_t$ in turn gives us:

${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{{\hat{v}}_t}+ϵ}(\frac{{\beta }_1{m}_{t-1}}{1-{\beta }_1^t}+\frac{(1-{\beta }_1)g_t}{1-{\beta }_1^t})$

Note that $\frac{{\beta }_1{m}_{t-1}}{1-{\beta }_1^t}$ is just the bias-corrected estimate of the momentum vector of the previous time step. We can thus replace it with ${\hat{m}}_{t-1}$:

${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{{\hat{v}}_t}+ϵ}({\beta }_1{\hat{m}}_{t-1}+\frac{(1-{\beta }_1)g_t}{1-{\beta }_1^t})$

    Note that for simplicity, we ignore that the denominator is $1-{\beta }_1^t$ and not $1-{\beta }_1^{t-1}$ as we will replace the denominator in the next step anyway. This equation again looks very similar to our expanded momentum update rule above. We can now add Nesterov momentum just as we did previously by simply replacing this bias-corrected estimate of the momentum vector of the previous time step ${\hat{m}}_{t-1}$ with the bias-corrected estimate of the current momentum vector ${\hat{m}}_t$, which gives us the Nadam update rule:

${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{{\hat{v}}_t}+ϵ}({\beta }_1{\hat{m}}_t+\frac{(1-{\beta }_1)g_t}{1-{\beta }_1^t})$