Newton's Method: Theory and Derivation

First-order methods like gradient descent rely solely on the slope (gradient) of the loss function to determine the update direction. While effective, they can be slow to converge, especially in areas with complex curvature, such as narrow valleys or near plateaus. Second-order methods incorporate information about the function's curvature, aiming for more direct and potentially faster convergence towards a minimum.

Newton's method is the foundational second-order optimization algorithm. Its core idea is to iteratively approximate the objective function $f(x)$ around the current iterate $x_k$ using a simpler function, specifically a quadratic model, and then find the minimum of that model. This minimum serves as the next iterate $x_{k+1}$.

Recall the second-order Taylor expansion of a function $f: \mathbb{R}^n \to \mathbb{R}$ around a point $x_k$:

$$f(x_k + p) \approx f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T \nabla^2 f(x_k) p$$

Here, $p = x - x_k$ is the step we want to take from $x_k$. $\nabla f(x_k)$ is the gradient vector of $f$ at $x_k$, and $\nabla^2 f(x_k)$ is the Hessian matrix of $f$ at $x_k$, containing all second partial derivatives. Let's denote the Hessian at $x_k$ as $H_k = \nabla^2 f(x_k)$.

Newton's method defines a quadratic model $m_k(p)$ of the function $f$ at $x_k + p$:

$$m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T H_k p$$

To find the best step $p$, we seek the value $p_k$ that minimizes this quadratic model $m_k(p)$. Assuming $m_k(p)$ has a unique minimum (which requires the Hessian $H_k$ to be positive definite), we can find it by setting the gradient of $m_k(p)$ with respect to $p$ equal to zero:

$$\nabla_p m_k(p) = \nabla f(x_k) + H_k p = 0$$

Solving this linear system for the step $p$, which we call the Newton step $p_k$, yields:

$$H_k p_k = - \nabla f(x_k)$$

Assuming the Hessian matrix $H_k$ is invertible, we get:

$$p_k = - H_k^{-1} \nabla f(x_k)$$

This $p_k$ represents the direction and magnitude of the step that leads to the minimum of the local quadratic approximation. The Newton's method update rule is then defined as:

$$x_{k+1} = x_k + p_k = x_k - H_k^{-1} \nabla f(x_k)$$

Geometric Interpretation

Compare this to the gradient descent update: $x_{k+1} = x_k - \alpha \nabla f(x_k)$, where $\alpha$ is the learning rate. Gradient descent always moves in the direction of the negative gradient, the direction of steepest local descent. Newton's method modifies this direction by multiplying the negative gradient with the inverse Hessian $H_k^{-1}$.

The Hessian $H_k$ captures the curvature of the function $f$ at $x_k$. Multiplying by its inverse effectively rescales the gradient components based on this curvature. In directions where the curvature is high (function increases sharply), the step size is reduced. In directions where the curvature is low (function is flatter), the step size is increased. This leads the algorithm to take more direct steps towards the minimum, especially in elongated valleys where gradient descent tends to zigzag.

If the objective function $f(x)$ is itself a strictly convex quadratic function, Newton's method will find the exact minimum in a single step from any starting point, because the quadratic model $m_k(p)$ will be identical to $f(x_k+p)$.

Flow diagram illustrating the computation involved in a single step of Newton's method. Note the dependency on computing both the gradient and the Hessian, followed by a matrix inversion.

Convergence Properties

Under specific conditions, Newton's method exhibits very fast local quadratic convergence. This means that once the iterates $x_k$ are sufficiently close to the actual minimum $x^*$, the error decreases quadratically at each step. Formally, if $e_k = \|x_k - x^*\|$, then quadratic convergence implies $\|e_{k+1}\| \le C \|e_k\|^2$ for some constant $C$. This rapid convergence rate is a significant advantage over the typically linear convergence rate ($e_{k+1} \le c e_k$ for $c < 1$) of first-order methods.

However, this desirable convergence relies on several assumptions:

1. The function $f$ must be twice continuously differentiable.
2. The Hessian matrix $H_k$ must be positive definite near the solution $x^*$. If the Hessian is not positive definite, the Newton step $p_k$ might not even be a descent direction (it could point towards a maximum or saddle point).
3. The Hessian must be invertible (non-singular) at each step.
4. The initial point $x_0$ must be sufficiently close to the solution $x^*$. Far from the solution, Newton's method is not guaranteed to converge and can even diverge.

These assumptions, particularly the computational burden of forming and inverting the Hessian ($O(n^3)$ for dense matrices of size $n \times n$) and the requirement for positive definiteness, motivate the development of modifications and alternatives, such as Quasi-Newton methods, which we will discuss next.