I'm studying gradient descent methods, in particular Nesterov's methods and others that achieve a better complexity (in terms of access to the gradient oracle) than regular gradient descent. In particular, for a smooth objective, accelerated gradient descent uses $O(1/\sqrt{\epsilon})$ calls to the oracle as opposed to $O(1/\epsilon)$ of regular gradient descent.

I've been reading other methods that accelerate but all of them change the direction of descent. I was wondering if there is some method that always moves following the opposite direction of the gradient and that also only needs $O(1/\sqrt{\epsilon})$ to the gradient oracle.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.