Gradient descent vs. Newton's method -- which one requires more computation? Broadly speaking, when numerically minimizing a d-dimensional objective function:

Gradient descent generally requires more iterations, but each iteration is fast
(we only need to compute 1st derivatives)

Newton's method generally requires fewer iterations, but each iteration is slow
(we need to compute 2nd dervatives too)


My question is: in terms of the total amount of computation required, which one generally ends up being faster -- Newton's method or gradient-descent? Does this depend on $d$? How?
If this is a better question for another site please let me know.
Minor update
If it matters for the sake of comparison, let's assume the function is convex and &quot;typical&quot; (i.e. I'm not going to explicitly choose a function that exhibits the worst-case behavior of either algorithm). I'm just trying to understand what the rule of thumb is regarding the performance of each method.
I think this depends a lot on the structure of the function you are optimizing (duh). In general non-convex cases, both algorithms have the same worst-case complexity for the number of iterations taken to drive the norm of the gradient below some given tolerance. Not sure what this means in terms of actual computation time for instances because the constant factors come into play.

You can look at this paper by Gould et al and references therein for more details.

I think a good thumbrule is - if your problem is convex and you have a reasonably good initial guess, Newton's (or Quasi-Newton) is usually much faster in practice.
In general a function one is trying to find a zero of is given by an explicit formula so the calculation of the derivative is a single-occurrence event and need not to be incorporated into the iteration. For the advantages of Newton's method see http://en.wikipedia.org/wiki/Newton%27s_method