3
$\begingroup$

In my machine learning class, we've discussed two methods for optimization - gradient descent and Newton's method. I had learned Newton's method before in calculus, but always in the context of finding roots of $f(x)=0$.

In retrospect it is obvious that it can just as easily be applied to $f'(x)=0$, but I guess it had never occurred to me before.

When solving $f(x)=0$, Newton's method requires us to use $f'(x)$, so I was always taught that this makes it a "first-order method".

But of course when solving $f'(x)=0$ using Newton's method (which we do in the context of optimization), we must use $f''(x)$. Does this now make it a "second-order method", while gradient descent would be a first-order method?

Or, should Newton's method applied to $f'(x)$ still be considered a first-order optimization method, and gradient descent a "zeroth-order optimization method"?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The order of a method refers to the speed with with it approaches the objective. If you have $x_{n + 1}$ computed from $x_n$, converging to $x^*$, the method is called order $\alpha$ if, approximately when near the objective:

$$\lvert x_{n + 1} - x^* \rvert \approx c \lvert x_n - x^* \rvert^\alpha$$

Newton's root finding method (either on the function or on the derivative, for optimization) is of second order unless the zero is multiple, when it is linear.

$\endgroup$
2
  • 3
    $\begingroup$ Unfortunately the usage of "order" in both senses is not unusual. $\endgroup$
    – Ian
    Commented Oct 9, 2015 at 1:20
  • 1
    $\begingroup$ Essentially then the order of the method corresponds to its Hölder exponent. $\endgroup$
    – Mathews24
    Commented Jun 7, 2020 at 14:53

You must log in to answer this question.

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