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 )$ :
