1
$\begingroup$

Currently I am studying logistic regression.

I read online that Gradient Descent is a 1st-order optimisation algorithm, and that Newton's Method is a 2nd order optimisation algorithm.

Does that mean that Gradient Descent cannot be used for multivariate optimisation and that Newton's Method cannot be used for univariate optimisation? Or can Newton's Method be done using a 1st order Taylor polynomial and still be different from Gradient Descent?

These sites are causing me to question:

$\endgroup$
  • 1
    $\begingroup$ You can certainly use both gradient descent and Newton's method for either univariate or multivariate optimization. $\endgroup$ – littleO Nov 27 '19 at 11:36
  • $\begingroup$ This means that gradient descent depends only on the derivative of a function, whereas Newton's method depends on the first and the second derivative. This terminology (1st order/ 2nd order) has nothing to do with univariate or multivariate optimisation. $\endgroup$ – Slup Nov 27 '19 at 11:37
2
$\begingroup$

Like in the comments stated; gradient descent and Newton's method are optimization methods, independently if its univariate or multivariate. Gradient descent only uses the first derivative, which sometimes makes it less efficient in multidimensional problems because Newton's method attracts to saddle points. Newton's method uses the curvature of the function (the second derivative) which lead generally faster to a solution if the second derivative is easy to compute. So they can both be used for multivariate and univariate optimization, but the performance will generally not be similar.

$\endgroup$
  • $\begingroup$ So does that mean that when you use the 1st-order Taylor polynomial it is no longer Newton's method, that it becomes Gradient Descent? $\endgroup$ – Hugh Pearse Nov 27 '19 at 12:03
  • $\begingroup$ in essence, the (directional) second derivative tells us how well we can expect a gradient descent step to perform and uses therefore a second -order Taylor approximation. Gradient descent just moves into the direction of the negative gradient, where the gradient refers to the derivative with respect to a vector. $\endgroup$ – Steven31415 Nov 27 '19 at 12:20
  • $\begingroup$ @HughPearse You are confusing two related but different goals. With Newton's method you solve an equation by using the 1st derivative. When you optimize, however, you are not looking for a zero of a function, but for a zero of its jacobian. You then need one more derivative, and that's the hessian. See Newton's method in optimization. $\endgroup$ – Jean-Claude Arbaut Nov 27 '19 at 12:36
  • $\begingroup$ @Jean-ClaudeArbaut I found this site which shows a Newton's Method on a univariate function using 1st order Taylor polynomial. There is no Hessian or Jacobian until they need to perform multivariate optimisation. Are they using the wrong terminology? $\endgroup$ – Hugh Pearse Nov 27 '19 at 12:49
  • 1
    $\begingroup$ @HughPearse Yes. But to see why you have to consider the Newton-Raphson method to solve a system of nonlinear equations in several variables, using the derivative (i.e. the jacobian matrix). When you apply this method to an optimiztion problem, you are given a function $f$ of several variables, and you look for critical points, so the system do solve is $\frac{\partial f}{\partial x_i}=0$, $i=1\dots n$. Thus when you apply Newton's method to this system of equations, you need the second derivative. $\endgroup$ – Jean-Claude Arbaut Nov 27 '19 at 12:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.