### Q14 2018

Hi,
I couldn't find any reference about line search in the notes, was the topic covered this year?
Thanks

Top comment

@Anonymous said:
Check lecture 10, slide 10. However, I don't think I understood why the answer is O(dL/eps) and not O(dL/eps^2), since it says on slide 12 that the complexity of random search is d times the complexity of gradient descent on the function class, which is here convex functions. Any clues?

In slide 11 of lecture 10, it assumes f is L-smooth hence for smooth functions with Gradient Descent we have convergence rate of O(1/eps). I guess that's the reason.

Check lecture 10, slide 10. However, I don't think I understood why the answer is O(dL/eps) and not O(dL/eps^2), since it says on slide 12 that the complexity of random search is d times the complexity of gradient descent on the function class, which is here convex functions. Any clues?

Top comment

@Anonymous said:
Check lecture 10, slide 10. However, I don't think I understood why the answer is O(dL/eps) and not O(dL/eps^2), since it says on slide 12 that the complexity of random search is d times the complexity of gradient descent on the function class, which is here convex functions. Any clues?

In slide 11 of lecture 10, it assumes f is L-smooth hence for smooth functions with Gradient Descent we have convergence rate of O(1/eps). I guess that's the reason.

In that case Q14 should indicate the function is smooth as well.