D-DL4CV-Lec04bc-Nesterov_Momentum

Nesterov Momentum

Strategy

Instead of deciding where to go only based on current situation (compute_gradient(w)), this approach choose to “look ahead” first then decide what momentum I want to impose on the current momentum, i.e., $\nabla f(x_t+\rho v_t)$

Mathematical Expression

$$\begin{array}{rl}{v}_{t+1}& =\rho v_t-\alpha \nabla f(x_t+\rho v_t)\\ x_{t+1}& =x_t+v_{t+1}\end{array}$$

However, we want to update in terms of $x_t$ and $\nabla f(x_t)$, thus by change of variable (${\tilde{x}}_t=x_t+\rho v_t$) and some rearrangement, we have

$$\begin{array}{rl}{v}_{t+1}& =\rho v_t-\alpha \nabla f({\tilde{x}}_t)\\ x_{t+1}& ={\tilde{x}}_t-\rho v_t+(1+\rho )v_{t+1}\\ & ={\tilde{x}}_t+v_{t+1}+\rho (v_{t+1}-v_t)\end{array}$$

Implementation

v = 0
for t in range(num_steps):
	dw = compute_gradient(w)
	old_v = v
	v = rho * v - learning_rate * dw
	w -= rho * old_v - (1 + rho) * v