GD Iteration Count Bound

Problem

For an L-smooth, mu-strongly convex function, gradient descent contracts the distance to the optimum by (1 - mu/L) per step, so reaching accuracy eps from x0 takes at least log(eps / |x0|) / log(1 - mu / L) steps.

Given L, mu, eps, and x0, return the ceiling of that bound; return 0 when x0 is zero.

Hint

Solve (1 - mu/L)^k * |x0| = eps for k and round up.

Test cases

case 1

in: [10,1,0.001,1]

expected: 66

case 2

in: [4,2,0.000001,5]

expected: 23

case 3

in: [100,1,0.5,1]

expected: 69

Starter codePython

def gd_iteration_count_bound(l, mu, eps, x0):
    # Your code here
    pass

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