Nesterov Accelerated Descent

Problem

Minimize f(x) = x^2 with Nesterov accelerated gradient descent.

Start with x = start and velocity v = 0. For n_iters iterations compute the lookahead point look = x + mu * v, evaluate grad = 2 * look, update v = mu * v - lr * grad, then set x = x + v. Return the final value of x.

Hint

The gradient is evaluated at x + mu * v, not at x.

Test cases

case 1

in: [10,0.01,0.9,2000]

expected: 2.5781211955037704e-54

case 2

in: [5,0.1,0.5,50]

expected: -7.314645506403761e-10

case 3

in: [0,0.1,0.9,100]

expected: 0

case 4

in: [-3,0.05,0.8,100]

expected: -1.4750562658798427e-8

Starter codePython

def nesterov_descent(start, lr, mu, n_iters):
    # Minimize f(x) = x ** 2
    # Your code here
    pass

4 test cases · run your code against them in the editor