3
$\begingroup$

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 "typical" (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.

$\endgroup$
4
  • $\begingroup$ What precisely do you mean by total amount of computation? Usually for nonlinear programming algorithms, one compares methods in terms of convergence rates. $\endgroup$
    – wonko
    Commented Aug 12, 2014 at 14:59
  • $\begingroup$ @wonko: It's a pretty clear question -- I mean if I run it on a computer, which one will finish faster (perhaps up to a constant factor)? $\endgroup$
    – user541686
    Commented Aug 12, 2014 at 17:14
  • 1
    $\begingroup$ Newton-type methods will usually win by far, if done properly. A good reference for the state-of-the-art methods for numerical optimization is Nocedal and Wright's book. $\endgroup$
    – Nick Alger
    Commented Jun 12, 2015 at 0:12
  • $\begingroup$ @NickAlger: Thanks for the tip, I'll take a look at the book. $\endgroup$
    – user541686
    Commented Jun 12, 2015 at 18:58

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you sure it doesn't strongly depend on d? Intuitively I would expect Newton to become worse than gradient descent as d increases (since it needs second derivatives), but not sure... (and good point about the structure of the function, I think it's safe to assume it's a typical convex function for the sake of the question) $\endgroup$
    – user541686
    Commented Aug 12, 2014 at 20:57
  • $\begingroup$ You're right in the sense that the actual number of computations would depend on $d$ since obviously you are computing more derivative terms as the dimension increases. But I'm not sure there is a general statement you can make about what the tradeoff looks like between iterations and computations per iteration between the two algorithms. $\endgroup$
    – wonko
    Commented Aug 12, 2014 at 21:39
  • 1
    $\begingroup$ @Mehrdad Surprisingly it tends to be quite the opposite - Newton type methods tend to do way better for large $d$. The reason is that it turns out you don't actually need to compute the full $d$-by-$d$ Hessian to apply it's inverse (or an approximation of its inverse) to a vector. The key methods to look into are "inexact Newton-Krylov" and "L-BFGS". $\endgroup$
    – Nick Alger
    Commented Jun 12, 2015 at 19:49
  • $\begingroup$ @NickAlger: Very interesting, thanks for the pointers! $\endgroup$
    – user541686
    Commented Jun 12, 2015 at 20:01
-1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I meant when this is done numerically -- I'll update the question. $\endgroup$
    – user541686
    Commented Aug 12, 2014 at 10:22
  • $\begingroup$ The OP asks about optimization not equation solving, I guess. $\endgroup$ Commented Aug 12, 2014 at 10:38
  • $\begingroup$ @Claude, I don't see how this could be answered without some kind of information about the regularity of the function. Does this question make sense? $\endgroup$ Commented Aug 12, 2014 at 10:40
  • $\begingroup$ It makes a lot of sense to me. I confess that I implicitly admit the regularity of the function. To me, the main question is : what means "compute the derivatives" ? Are they analytical or numerical ? The problem is very interesting (at least, to me !). Cheers :-) $\endgroup$ Commented Aug 12, 2014 at 10:47
  • $\begingroup$ @Claude, computing the derivative only increases each iteration by a constant factor, whereas if you assume regularity, doesn't Newton's method provide an exponential improvement on other methods? $\endgroup$ Commented Aug 12, 2014 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .