@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?

@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.

## Q14 2018

Hi,

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

Thanks

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.

## 1

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?

## 1

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.

## 1

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

## Add comment