Trying to write Nesterov Optimization - Gradient Descent

Question

Problem: Im unsure if I understood Nesterov Optimization

Im writing about Nesterov Optimization, but the notation im using seems different from the references below. I have done it using some books as guides.

Would someone please clarify?

---

Let $\epsilon$ be the learning rate, $w$ each weight of the neural network, $\alpha$ the momentum and $E$ a loss function and considering the weights and gradients are calcualted as an unidimensional vector, the weight updates is done as below :

$n_0 = 0 $

$n_t = \alpha * n_{t-1} + \epsilon \frac{\partial E}{\partial w_t}$

And the update for each weight done as the formula below:

$\Delta_{w(t)} = \alpha_{n{t-1}} - {1 - \alpha} n_t$

---

QUESTIONS

What exactly is $n$ and $t$ ?

---

References:

https://blogs.princeton.edu/imabandit/2014/03/06/nesterovs-accelerated-gradient-descent-for-smooth-and-strongly-convex-optimization/

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

What's the difference between momentum based gradient descent, and Nesterov's accelerated gradient descent?

http://neuralnetworksanddeeplearning.com/chap2.html

https://brilliant.org/wiki/backpropagation/

Answer 1

I think you might be missing something here. I will use the first link you provided as a guide.

Nesterov's method has two steps: The normal gradient update, and then the "nudge" where we move the update a bit according to the update in the previous time step.

From what you write $n$ should be the change in your weights, i.e. is a vector. $t$ is the iteration number. So it doesn't make sense to initialize it to zero, the momentum is what we initialize to 0. Adapting notation from Bubeck's article, and changing the definition of $n$:

$$ n_0 = 0, n_t = \frac{1 + \sqrt{1+4n_{t-1}^2}}{2}, \alpha_t=\frac{1-n_t}{n_{t+1}} $$

Then the update is done in two steps: First get the regular update according to the gradient, previous weights and learning rate, then apply momentum to it:

$$ y_{t+1} = w_t - \epsilon \frac{\partial E}{\partial w_t}\\ w_{t+1} = (1 - \alpha_t)y_{t+1} + \alpha_t y_t $$