1
$\begingroup$

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.

$\endgroup$

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.