46
$\begingroup$

So momentum based gradient descent works as follows:

$v=self.momentum*m-lr*g$

where $m$ is the previous weight update, and $g$ is the current gradient with respect to the parameters $p$, $lr$ is the learning rate, and $self.momentum$ is a constant.

$p_{new} = p + v = p + self.momentum * m - lr * g$

and Nesterov's accelerated gradient descent works as follows:

$p_{new} = p + self.momentum * v - lr * g$

which is equivalent to:

$p_{new} = p + self.momentum * (self.momentum * m - lr * g ) - lr * g$

or

$p_{new} = p + self.momentum^2 * m - (1 + self.momentum) * lr * g$

source: https://github.com/fchollet/keras/blob/master/keras/optimizers.py

So to me it seems Nesterov's accelerated gradient descent just gives more weight to the lr * g term over the pervious weight change term m (compared to plain old momentum). Is this interpretation correct?

$\endgroup$
  • 7
    $\begingroup$ Would asking you to type in $\LaTeX$ be asking too much? $\endgroup$ – Rodrigo de Azevedo Oct 9 '16 at 7:18
33
$\begingroup$

Arech's answer about Nesterov momentum is correct, but the code essentially does the same thing. So in this regard the Nesterov method does give more weight to the $lr \cdot g$ term, and less weight to the $v$ term.

To illustrate why Keras' implementation is correct, I'll borrow Geoffrey Hinton's example.
enter image description here

Nesterov method takes the "gamble->correction" approach.
$v' = m \cdot v - lr \cdot \nabla(w+m \cdot v)$
$w' = w + v'$
The brown vector is $m \cdot v$ (gamble/jump), the red vector is $-lr \cdot \nabla(w+m \cdot v)$ (correction), and the green vector is $m \cdot v-lr \cdot \nabla(w+m \cdot v)$ (where we should actually move to). $\nabla(\cdot)$ is the gradient function.

The code looks different because it moves by the brown vector instead of the green vector, as the Nesterov method only requires evaluating $\nabla(w+m \cdot v) =: g$ instead of $\nabla(w)$. Therefore in each step we want to

  1. move back to where we were $(1 \rightarrow 0)$
  2. follow the green vector to where we should be $(0 \rightarrow 2)$
  3. make another gamble $(2 \rightarrow 3)$

Keras' code written for short is $p' = p + m \cdot (m \cdot v - lr \cdot g) - lr \cdot g$, and we do some maths

$\begin{align} p' &= p - m \cdot v + m \cdot v + m \cdot (m \cdot v - lr \cdot g) - lr \cdot g\\ &= p - m \cdot v + m \cdot v - lr \cdot g + m \cdot (m \cdot v - lr \cdot g)\\ &= p - m \cdot v + (m \cdot v-lr \cdot g) + m \cdot (m \cdot v-lr \cdot g) \end{align}$

and that's exactly $1 \rightarrow 0 \rightarrow 2 \rightarrow 3$. Actually the original code takes a shorter path $1 \rightarrow 2 \rightarrow 3$.

The actual estimated value (green vector) should be $p - m \cdot v$, which should be close to $p$ when learning converges.

$\endgroup$
12
$\begingroup$

I don't think so.

There's a good description of Nesterov Momentum (aka Nesterov Accelerated Gradient) properties in, for example, Sutskever, Martens et al."On the importance of initialization and momentum in deep learning" 2013.

The main difference is in classical momentum you first correct your velocity and then make a big step according to that velocity (and then repeat), but in Nesterov momentum you first making a step into velocity direction and then make a correction to a velocity vector based on new location (then repeat).

i.e. Classical momentum:

vW(t+1) = momentum.*Vw(t) - scaling .* gradient_F( W(t) )
W(t+1) = W(t) + vW(t+1)

While Nesterov momentum is this:

vW(t+1) = momentum.*Vw(t) - scaling .* gradient_F( W(t) + momentum.*vW(t) )
W(t+1) = W(t) + vW(t+1)

Actually, this makes a huge difference in practice...

$\endgroup$
11
$\begingroup$

It seems to me that the OP's question was already answered, but I would try to give another (hopefully intuitive) explanation about momentum and the difference between Classical Momentum (CM) and Nesterov's Accelerated Gradient (NAG).


tl;dr
Just skip to the image at the end.
NAG_ball's reasoning is another important part, but I am not sure it would be easy to understand without all of the rest.



CM and NAG are both methods for choosing the next vector $\theta$ in parameter space, in order to find a minimum of a function $f(\theta)$.

In other news, lately these two wild sentient balls appeared:
CM_ball NAG_ball

It turns out (according to the observed behavior of the balls, and according to the paper On the importance of initialization and momentum in deep learning, that describes both CM and NAG in section 2) that each ball behaves exactly like one of these methods, and so we would call them "CM_ball" and "NAG_ball":
(NAG_ball is smiling, because he recently watched the end of Lecture 6c - The momentum method, by Geoffrey Hinton with Nitish Srivastava and Kevin Swersky, and thus believes more than ever that his behavior leads to finding a minimum faster.)

Here is how the balls behave:

  • Instead of rolling like normal balls, they jump between points in parameter space.
    Let $\theta_t$ be a ball's $t$-th location in parameter space, and let $v_t$ be the ball's $t$-th jump. Then jumping between points in parameter space can be described by $\theta_t=\theta_{t-1}+v_t$.
  • Not only do they jump instead of roll, but also their jumps are special: Each jump $v_t$ is actually a Double Jump, which is the composition of two jumps:
    • Momentum Jump - a jump that uses the momentum from $v_{t-1}$, the last Double Jump.
      A small fraction of the momentum of $v_{t-1}$ is lost due to friction with the air.
      Let $\mu$ be the fraction of the momentum that is left (the balls are quite aerodynamic, so usually $0.9 \le \mu <1$). Then the Momentum Jump is equal to $\mu v_{t-1}$.
      (In both CM and NAG, $\mu$ is a hyperparameter called "momentum coefficient".)
    • Slope Jump - a jump that reminds me of the result of putting a normal ball on a surface - the ball starts rolling in the direction of the steepest slope downward, while the steeper the slope, the larger the acceleration.
      Similarly, the Slope Jump is in the direction of the steepest slope downward (the direction opposite to the gradient), and the larger the gradient, the further the jump.
      The Slope Jump also depends on $\epsilon$, the level of eagerness of the ball (naturally, $\epsilon>0$): The more eager the ball, the further the Slope Jump would take it.
      (In both CM and NAG, $\epsilon$ is a hyperparameter called "learning rate".)
      Let $g$ be the gradient in the starting location of the Slope Jump. Then the Slope Jump is equal to $-\epsilon g$.
  • So for both balls the Double Jump is equal to:$$v_t=\mu v_{t-1} -\epsilon g$$ The only difference between the balls is the order of the two jumps in the Double Jump.
  • CM_ball didn't think it mattered, so he decided to always start with the Slope Jump.
    Thus, CM_ball's Double Jump is: $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}\right)$$
  • In contrast, NAG_ball thought about it for some time, and then decided to always start with the Momentum Jump.
    Therefore, NAG_ball's Double Jump is: $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}+\mu v_{t-1}\right)$$

    NAG_ball's reasoning

    • Whatever jump comes first, my Momentum Jump would be the same.
      So I should consider the situation as if I have already made my Momentum Jump, and I am about to make my Slope Jump.
    • Now, my Slope Jump is conceptually going to start from here, but I can choose whether to calculate what my Slope Jump would be as if it started before the Momentum Jump, or as if it started here.
    • Thinking about it this way makes it quite clear that the latter is better, as generally, the gradient at some point $\theta$ roughly points you in the direction from $\theta$ to a minimum (with the relatively right magnitude), while the gradient at some other point is less likely to point you in the direction from $\theta$ to a minimum (with the relatively right magnitude).

Finally, yesterday I was fortunate enough to observe each of the balls jumping around in a 1-dimensional parameter space.
I think that looking at their changing positions in the parameter space wouldn't help much with gaining intuition, as this parameter space is a line.
So instead, for each ball I sketched a 2-dimensional graph in which the horizontal axis is $\theta$.
Then I drew $f(\theta)$ using a black brush, and also drew each ball in his $7$ first positions, along with numbers to show the chronological order of the positions.
Lastly, I drew green arrows to show the distance in parameter space (i.e. the horizontal distance in the graph) of each Momentum Jump and Slope Jump.

CM_ball vs NAG_ball example


Appendix 1 - A demonstration of NAG_ball's reasoning

In this mesmerizing gif by Alec Radford, you can see NAG performing arguably better than CM ("Momentum" in the gif).
(The minimum is where the star is, and the curves are contour lines. For an explanation about contour lines and why they are perpendicular to the gradient, see videos 1 and 2 by the legendary 3Blue1Brown.)

NAG better than CM (Momentum)

An analysis of a specific moment demonstrates NAG_ball's reasoning:

CM vs NAG in a specific moment

  • The (long) purple arrow is the momentum sub-step.
  • The transparent red arrow is the gradient sub-step if it starts before the momentum sub-step.
  • The black arrow is the gradient sub-step if it starts after the momentum sub-step.
  • CM would end up in the target of the dark red arrow.
  • NAG would end up in the target of the black arrow.

Appendix 2 - things/terms I made up (for intuition's sake)

  • CM_ball
  • NAG_ball
  • Double Jump
  • Momentum Jump
  • Momentum lost due to friction with the air
  • Slope Jump
  • Eagerness of a ball
  • Me observing the balls yesterday

Appendix 3 - terms I didn't make up

$\endgroup$
  • 1
    $\begingroup$ I find the part from "Here is how the balls behave:..." to " to point you in the direction from θ to a minimum (with the relatively right magnitude)." excellent as an explanation of the difference. $\endgroup$ – Poete Maudit Nov 2 '18 at 16:16
5
$\begingroup$

Added: a Stanford course on neural networks, cs231n, gives yet another form of the steps:

v = mu * v_prev - learning_rate * gradient(x)   # GD + momentum
v_nesterov = v + mu * (v - v_prev)              # keep going, extrapolate
x += v_nesterov

Here v is velocity aka step aka state, and mu is a momentum factor, typically 0.9 or so. (v, x and learning_rate can be very long vectors; with numpy, the code is the same.)

v in the first line is gradient descent with momentum; v_nesterov extrapolates, keeps going. For example, with mu = 0.9,

v_prev  v   --> v_nesterov
---------------
 0  10  -->  19
10   0  -->  -9
10  10  -->  10
10  20  -->  29

The following description has 3 terms:
term 1 alone is plain gradient descent (GD),
1 + 2 give GD + momentum,
1 + 2 + 3 give Nesterov GD.

Nesterov GD is usually described as alternating momentum steps $x_t \to y_t$ and gradient steps $y_t \to x_{t+1}$:

$\qquad y_t = x_t + m (x_t - x_{t-1}) \quad $ -- momentum, predictor
$\qquad x_{t+1} = y_t + h\ g(y_t) \qquad $ -- gradient

where $g_t \equiv - \nabla f(y_t)$ is the negative gradient, and $h$ is stepsize aka learning rate.

Combine these two equations to one in $y_t$ only, the points at which the gradients are evaluated, by plugging the second equation into the first, and rearrange terms:

$\qquad y_{t+1} = y_t$
$\qquad \qquad + \ h \ g_t \qquad \qquad \quad $ -- gradient
$\qquad \qquad + \ m \ (y_t - y_{t-1}) \qquad $ -- step momentum
$\qquad \qquad + \ m \ h \ (g_t - g_{t-1}) \quad $ -- gradient momentum

The last term is the difference between GD with plain momentum, and GD with Nesterov momentum.


One could use separate momentum terms, say $m$ and $m_{grad}$:
$\qquad \qquad + \ m \ (y_t - y_{t-1}) \qquad $ -- step momentum
$\qquad \qquad + \ m_{grad} \ h \ (g_t - g_{t-1}) \quad $ -- gradient momentum

Then $m_{grad} = 0$ gives plain momentum, $m_{grad} = m$ Nesterov.
$m_{grad} > 0 $ amplifies noise (gradients can be very noisy),
$m_{grad} \sim -.1$ is an IIR smoothing filter.

By the way, momentum and stepsize can vary with time, $m_t$ and $h_t$, or per component (ada* coordinate descent), or both -- more methods than test cases.


A plot comparing plain momentum with Nesterov momentum on a simple 2d test case,
$(x / [cond, 1] - 100) + ripple \times sin( \pi x )$ :

enter image description here

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