A critical flaw of standard Newton's Method emerges when optimizing nonconvex functions. The algorithm's update rule involves dividing by the Hessian matrix (or the second derivative in one dimension). If the objective function exhibits negative curvature—meaning the second derivative is negative, as seen in functions like $$f(x) = x \cos(cx)$$—the update step can inadvertently move the parameters in a direction that increases the function's value, rather than minimizing it.

Claude

Newton's Method is a second-order optimization algorithm that relies on the second-order Taylor expansion of a multivariate function $$f(\mathbf{x})$$. By taking the expansion $$f(\mathbf{x} + \boldsymbol{\epsilon}) = f(\mathbf{x}) + \boldsymbol{\epsilon}^	op 
abla f(\mathbf{x}) + \frac{1}{2} \boldsymbol{\epsilon}^	op \mathbf{H} \boldsymbol{\epsilon} + \mathcal{O}(\|\boldsymbol{\epsilon}\|^3)$$, where $$\mathbf{H} = 
abla^2 f(\mathbf{x})$$ is the Hessian matrix, and setting the derivative with respect to the update step $$\boldsymbol{\epsilon}$$ to zero ($$
abla f(\mathbf{x}) + \mathbf{H} \boldsymbol{\epsilon} = 0$$), the algorithm derives the optimal update step as $$\boldsymbol{\epsilon} = -\mathbf{H}^{-1} 
abla f(\mathbf{x})$$. This approach requires computing and inverting the Hessian matrix to directly jump toward the function's minimum.

Newton's Method

Dive into Deep Learning

- Broyden-Fletcher-Goldfarb-Shanno algorithm attempts to bring some of the advantages of Newton's method without the computational burden, referred to as Quasi-Newton Methods.
- A limitation of Newton’s method is that it requires the calculation of the inverse of the Hessian matrix. This is a computationally expensive operation and may not be stable depending on the properties of the objective function.
- Quasi-Newton methods are second-order optimization algorithms that approximate the inverse of the Hessian matrix using the gradient, meaning that the Hessian and its inverse do not need to be available or calculated precisely for each step of the algorithm.

BFGS Optimization Algorithm

When applied to a simple quadratic function, such as $$f(x) = \frac{1}{2} x^2$$, Newton's Method can converge to the global minimum perfectly in a single step. For this function, the gradient is $$
abla f(x) = x$$ and the Hessian is $$\mathbf{H} = 1$$. The update step $$\epsilon = -\mathbf{H}^{-1} 
abla f(x)$$ yields $$\epsilon = -x$$. Because the second-order Taylor expansion is mathematically exact for any quadratic function, no further adjustments or iterative steps are needed to reach the minimum.

Newton's Method on a Quadratic Function

For a convex objective function, such as the hyperbolic cosine function $$f(x) = \cosh(cx)$$, Newton's Method efficiently navigates the optimization landscape. Because the function's curvature is consistently positive, the algorithm typically reaches the global minimum in only a few iterations, demonstrating the effectiveness of second-order optimization on well-behaved surfaces.

Newton's Method on a Convex Function

Newton's Method on a Nonconvex Function

To mitigate the risk of divergence or moving in the wrong direction on nonconvex surfaces, the standard Newton's Method update can be modified by incorporating a learning rate, $$\eta$$. By taking a fraction of the full calculated step, the algorithm retains the benefits of second-order information—being cautious in regions of high curvature and taking longer steps in flatter regions—while significantly increasing optimization stability.

Learn Before

Related