1
$\begingroup$

I am troubled with why isn't the Newton's method used for backpropagation, instead, or in addition to Gradient Descent more widely.

I have seen this same question, and the widely accepted answer claims

Newton's method, a root finding algorithm, maximizes a function using knowledge of its second derivative

I went and looked - According to Newton's Method from wikipedia,

Geometrically, (x1, 0) is the intersection of the x-axis and the tangent of the graph of f at (x0, f (x0)). The process is repeated until a sufficiently accurate value is reached

I really don't get where and why the second derivative should ever be calculated.

I also saw this similar question, and the accepted answer in short was:

the reason is that the cost functions mentioned might not have any zeroes at all, in which case Newton's method will fail to find the minima

This seems very similar to a similar problem of vanishing gradients in gradient descent, and probably would have about the same solutions, and still doesn't explain why the second derivative is required.

Please explain why is the calculation of the second derivative needed in order to calculate the Newton's method for back-propagation

$\endgroup$
  • $\begingroup$ Short answer is that you should be using newton's method to find roots of a derivative of a function en.wikipedia.org/wiki/Newton%27s_method_in_optimization# $\endgroup$ – ExabytE Nov 9 '18 at 15:43
  • 3
    $\begingroup$ It's definitional; Newton's method uses second derivatives. If you don't use second derivatives, it's not Newton's method. That was the innovation of Newton's method - using the second derivatives to accelerate convergence for many problems. $\endgroup$ – jbowman Nov 9 '18 at 16:02
3
$\begingroup$

My guess at your confusion:

Newton's method is often used to solve two different (but related) problems:

  1. Find $x$ such that $f(x) = 0$
  2. Find $x$ to minimize $g(x)$

A connection between the two problems:

A necessary condition for an optimum for problem (2) is that $g'(x) = 0$. Let $f(x) = g'(x)$. If the first order condition $g'(x) = 0$ is also a sufficient condition for an optimum (eg. $g$ is convex), then (1) and (2) are the same problem.

The update step for problem (1) is: $$ x_{t+1} = x_{t} - \frac{f(x_{t})}{f'(x_{t})}$$ The update step for problem (2) is: $$ x_{t+1} = x_{t} - \frac{g'(x_{t})}{g''(x_{t})}$$

If $f = g'$ then:

  • Taking the 2nd order Taylor expansion, approximating $g$ as a quadratic function $\hat{g}(x_{t+1}) = g(x_t) + g'(x_t)(x_{t+1} - x_t) + \frac{1}{2}g''(x_t)(x_{t+1} - x_t)^2$ and choosing $x_{t+1}$ to minimize $\hat{g}$

is the same problem as

  • approximating $f$ as a linear function $\hat{f}(x_{t+1}) = f(x_t) + f'(x_t)(x_{t+1} - x_t)$ and finding the $x_{t+1}$ where $\hat{f}$ crosses $0$.
$\endgroup$
1
$\begingroup$

Answering your titular question is direct: Newton's method of optimization is defined by its use of the second derivative, full stop.

You might be interested in a bottom-to-top explanation of how different methods of optimization compare. A comprehensive description review can be found in "First-order and second-order variants of the gradient descent: a unified framework". Thomas Pierrot, Nicholas Perrin, Olivier Siguad. https://arxiv.org/abs/1810.08102

$\endgroup$

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.