Gradient descent vs. Newton's method: which is more efficient?

Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both gradients and Hessians.

However, gradient descent generally requires many more iterations than Newton's method to converge within the same accuracy.

My question, then, is:

Assuming they both converge, in terms of the number of elementary floating-point operations, which is usually faster: Newton's method or gradient descent? Why?

• More appropriate for scicomp.se. But I think you'll need to be more specific about how you are calculating your Hessian. [Elementary functions](en.wikipedia.org/wiki/… have derivatives that are similar in form (the derivative of an exponential is an exponential) and so calculating the derivative is often almost trivially inexpensive if you save the intermediate results of your original function evaluation. Apr 12 '14 at 12:59
• @WanderingLogic I think the question is ontopic here, but it may profit from migration if no good answer appears in a few days.
– Raphael
Apr 12 '14 at 13:38
• @WanderingLogic: I'm not talking about special cases -- I'm talking about the general case, where the function can only be evaluated numerically, hence you have to take derivatives numerically (say, by evaluating the function at nearby points and finding the slope at a point, or similar for concavity). If there are multiple methods for calculating Hessians even in this setting, then please mention that in the answer because I'm not familiar enough with them to pick a particular one. Apr 12 '14 at 21:06