Nesterov Accelerated Gradient

Gradient descent with momentum

The issue discussed above can be solved by including the previous gradients in our calculation. The intuition behind this is if we are repeatedly asked to go in a particular direction, we can take bigger steps towards that direction. 

The weighted average of all the previous gradients is added to our equation, and it acts as momentum to our step. 

Source: link

We can understand gradient descent with momentum from the above image. As we start to descend, the momentum increases, and even at gentle slopes where the gradient is minimal, the actual movement is large due to the added momentum.

But this added momentum causes a different type of problem. We actually cross the minimum point and have to take a U-turn to get to the minimum point. Momentum-based gradient descent oscillates around the minimum point, and we have to take a lot of U-turns to reach the desired point. Despite these oscillations, momentum-based gradient descent is faster than conventional gradient descent.

To reduce these oscillations, we can use Nesterov Accelerated Gradient. 

Nesterov Accelerated Gradient (NAG)

NAG resolves this problem by adding a look ahead term in our equation. The intuition behind NAG can be summarized as ‘look before you leap’. Let us try to understand this through an example.

Source: Link

As can see, in the momentum-based gradient, the steps become larger and larger due to the accumulated momentum, and then we overshoot at the 4th step. We then have to take steps in the opposite direction to reach the minimum point. 

However, the update in NAG happens in two steps. First, a partial step to reach the look-ahead point, and then the final update. We calculate the gradient at the look-ahead point and then use it to calculate the final update. If the gradient at the look-ahead point is negative, our final update will be smaller than that of a regular momentum-based gradient. Like in the above example, the updates of NAG are similar to that of the momentum-based gradient for the first three steps because the gradient at that point and the look-ahead point are positive. But at step 4, the gradient of the look-ahead point is negative.

In NAG, the first partial update 4a will be used to go to the look-ahead point and then the gradient will be calculated at that point without updating the parameters. Since the gradient at step 4b is negative, the overall update will be smaller than the momentum-based gradient descent. 

We can see in the above example that the momentum-based gradient descent takes six steps to reach the minimum point, while NAG takes only five steps.

This looking ahead helps NAG to converge to the minimum points in fewer steps and reduce the chances of overshooting.

How NAG actually works?

We saw how NAG solves the problem of overshooting by ‘looking ahead’. Let us see how this is calculated and the actual math behind it.

Update rule for gradient descent:
 w_t+1 = w_t − η∇wt
In this equation, the weight (W) is updated in each iteration. η is the learning rate, and ∇wt is the gradient. 

Update rule for momentum-based gradient descent:
In this, momentum is added to the conventional gradient descent equation. The update equation is
w_t+1 = w_t − update_t

update_t is calculated by:
update_t  = γ · update_t−1 + η∇w_t

Source: link

This is how the gradient of all the previous updates is added to the current update.

Update rule for NAG:
w_t+1 = w_t − update_t
While calculating the update_t, We will include the look ahead gradient (∇w_{look_ahead}).
update_t = γ · update_t−1 + η∇w_{look_ahead}

∇w_{look_ahead} is calculated by:
w_{look_ahead} = w_t − γ · update_t−1

This look-ahead gradient will be used in our update and will prevent overshooting.

FAQs

1. What is the range of momentum?
   Momentum is ranged from 0 to 1. 
    
2. Does gradient descent always converge to the minimum point of our function?
   Gradient descent is used to find the minimum points of our function. However, these points may not necessarily be the global minimum of our function.
    
3. Can we always use gradient descent?
   No, we can only use gradient descent when our cost function is differentiable at all points.

Key takeaways

We started this article by looking at Gradient descent and how it is used to reach the minimum point of our cost function. We also saw its drawback and how it is mitigated by using momentum. Finally, we talked about Nesterov Accelerated Gradient and how it improves the gradient descent with momentum. We also looked at the in-depth functioning of these algorithms. To dive deeper into the realm of Machine learning, check out our machine learning course at coding ninjas.