Newton's Method: Optimization and Convergence

Hello! In our previous lessons, we explored first-order optimization methods like gradient descent and its stochastic variants. These algorithms navigate the loss landscape by following the negative gradient, which provides the direction of steepest descent. While powerful, their convergence can be slow, often only achieving a linear or sub-linear reduction in error with each step.

Today, we will take a significant leap forward by exploring a second-order optimization technique: Newton's method. Instead of just using the slope (the gradient), Newton's method also incorporates information about the curvature of the function (the Hessian matrix). This allows it to build a much more accurate local model of the function, enabling it to take more intelligent steps. Our goal is to derive this powerful method and rigorously compare its astonishingly fast quadratic convergence rate with the linear convergence of gradient descent.

From Linear to Quadratic Approximation

The core idea behind gradient descent is to approximate the objective function $f (θ)$ around the current point $θ_{k}$ with a first-order Taylor expansion (a linear model) and move in the direction that minimizes this local approximation.

Newton's method improves on this by using a second-order Taylor expansion, creating a local quadratic model of the function. This quadratic model captures not only the slope but also the curvature, providing a much richer description of the landscape.

The "Visually Explained" video below offers an excellent intuition for this. It starts with the idea of iterative optimization and first-order methods before beautifully motivating and deriving Newton's method from the idea of minimizing a better, quadratic approximation.

Visually Explained: Newton's Method in Optimization

This video provides a clear, visual derivation of Newton's method for optimization.

First, watch the introduction to iterative optimization, which recaps the idea of gradient-based methods (until the recap). This sets the stage by showing the limitations of a linear approximation. Then, watch the key segment that derives Newton's method by building and minimizing a quadratic approximation. Pay close attention to how the step size is no longer a manually-tuned hyperparameter but is determined by the function's second derivative.

As the video explains, at a point $θ_{k}$ , we can approximate $f (θ)$ with the following quadratic function:

f (θ) \approx f (θ_{k}) + \nabla f (θ_{k})^{T} (θ - θ_{k}) + \frac{1}{2} (θ - θ_{k})^{T} \nabla^{2} f (θ_{k}) (θ - θ_{k})

Here, $\nabla f (θ_{k})$ is the gradient vector and $\nabla^{2} f (θ_{k})$ is the Hessian matrix of second derivatives at $θ_{k}$ .

Instead of taking a small step down the gradient, Newton's method takes a bold leap: it jumps directly to the minimum of this local quadratic model. To find this minimum, we take the gradient of the approximation with respect to $θ$ and set it to zero:

\nabla f (θ_{k}) + \nabla^{2} f (θ_{k}) (θ - θ_{k}) = 0

Solving for $θ$ gives us our next iterate, $θ_{k + 1}$ :

\nabla^{2} f (θ_{k}) (θ_{k + 1} - θ_{k}) = - \nabla f (θ_{k})

θ_{k + 1} = θ_{k} - [\nabla^{2} f (θ_{k})]^{- 1} \nabla f (θ_{k})

This is the update rule for Newton's method. The term $Δ θ_{k} = - [\nabla^{2} f (θ_{k})]^{- 1} \nabla f (θ_{k})$ is called the Newton step.

This diagram shows how Newton's method works for a 1D function F(X). At a point X₀, it constructs a quadratic Taylor series approximation. The next iterate, X₁, is chosen as the exact minimum of this quadratic approximation, which is often much closer to the true minimum of F(X) than a simple gradient step would be.

The following reading provides a concise, formal derivation that mirrors what we've just discussed, and contrasts the resulting step with the gradient descent step.

[PDF] Newton's Method 14.1 Review of previous lecture 14.2 Introduction

This document from Carnegie Mellon University's Convex Optimization course formally presents Newton's method and its interpretation.

Please read section 14.2.2 Newton’s method interpretation. Focus on the two quadratic approximations: one for Newton's method, which uses the true Hessian \nabla^2 f(x), and one for gradient descent, which uses a scaled identity matrix \frac{1}{t}I. This highlights why Newton's method is considered a "finer" approximation.

The Power of Quadratic Convergence

The real magic of Newton's method lies in its convergence rate. While gradient descent crawls towards the minimum with linear convergence, Newton's method, when it gets close, gallops towards it with quadratic convergence.

First, let's formalize these terms.

Lecture 19: Basic Newton's Method

This excerpt from lecture notes at the University of Wisconsin-Madison provides precise definitions for different rates of convergence.

Please read Section 3: Terminology for rates of convergence (the entire section). Pay special attention to the definitions of Q-linear and Q-quadratic convergence and the intuition behind them: linear convergence adds a constant number of correct digits per iteration, while quadratic convergence doubles the number of correct digits per iteration.

A method with quadratic convergence can achieve extremely high precision in just a handful of iterations. Let's see why Newton's method has this remarkable property. The derivation involves a careful Taylor expansion of the error term. The video below provides a very clear, step-by-step walkthrough for the 1D case, which is perfect for building intuition.

Convergence of Newton's Method | Lecture 17 | Numerical Methods for Engineers

This video from Jeffrey Chasnov's "Numerical Methods for Engineers" course provides a rigorous proof of quadratic convergence for Newton's method in 1D. Your mathematical background will make following this derivation straightforward.

Watch the entire video. The core of the proof is from this segment, where the error at step n+1 (\epsilon_{n+1}) is expressed in terms of the error at step n (\epsilon_n). The key is to see how, after a series of Taylor expansions and cancellations, the relationship \epsilon_{n+1} \propto \epsilon_n^2 emerges. The final segment (until the end) summarizes the result and the conditions under which it holds.

As the video masterfully demonstrates, the error at the next step is proportional to the square of the current error:

∣ ϵ_{n + 1} ∣ \approx C ∣ ϵ_{n} ∣^{2}

This result generalizes to the multivariate optimization case. Under certain conditions (namely, that the function is strongly convex and its Hessian is Lipschitz continuous near the optimum), we can prove that:

∥ θ_{k + 1} - θ^{*} ∥ \leq M ∥ θ_{k} - θ^{*} ∥^{2}

where $θ^{*}$ is the optimal solution. This is the hallmark of quadratic convergence. It's important to note that this rapid convergence is a local property—it is only guaranteed once the iterates are sufficiently close to the optimum. Far from the optimum, Newton's method can be unstable, which is why practical implementations often use a "damped" version that incorporates a line search, similar to gradient descent.

Newton's Method vs. Gradient Descent: A Head-to-Head Comparison

We now have two powerful optimization algorithms. Let's summarize their key differences.

This figure provides a stark visual comparison. On the left, Gradient Descent takes many small, perpendicular steps to navigate the elliptical contours. On the right, Newton's method, by accounting for the landscape's curvature, takes much larger and more direct steps, converging in far fewer iterations. The plots on the right show the error decreasing linearly for Gradient Descent (on a log scale) but quadratically for Newton's method.

This visual is powerful, but a detailed breakdown reveals the crucial trade-offs.

Feature	Gradient Descent	Newton's Method
Information Used	First-order (Gradient $\nabla f$ )	Second-order (Gradient $\nabla f$ & Hessian $\nabla^{2} f$ )
Convergence Rate	Linear (locally)	Quadratic (locally)
Iterations to Converge	Many	Very few (typically < 10)
Cost per Iteration	Low: $O (d)$ to compute gradient.	High: $O (d^{2})$ to form Hessian, $O (d^{3})$ to invert it.
Memory per Iteration	Low: $O (d)$ for gradient.	High: $O (d^{2})$ to store Hessian.
Hyperparameters	Requires tuning a learning rate $η$ .	Pure method is step-size free.
Sensitivity	Sensitive to poor conditioning (zigzagging).	Affine invariant; not sensitive to conditioning.

The main takeaway is the trade-off between per-iteration cost and convergence speed. Gradient descent is cheap per step but needs many steps. Newton's method is extremely expensive per step but needs very few.

The following reading elaborates on this comparison.

[PDF] Newton's Method 14.1 Review of previous lecture 14.2 Introduction

This final section from the CMU notes provides a concise, high-level comparison of the computational aspects of Newton's method versus first-order methods.

Please read Section 14.7 Comparison to first order methods (the entire section). This summarizes the computational complexity and memory requirements we've discussed.

Conclusion

In this lesson, we have derived Newton's method as a powerful second-order optimization algorithm that leverages curvature information to achieve quadratic convergence.

Here are the key takeaways:

Derivation: Newton's method is derived by minimizing a second-order (quadratic) Taylor approximation of the objective function at each step. The update rule is $θ_{k + 1} = θ_{k} - [\nabla^{2} f (θ_{k})]^{- 1} \nabla f (θ_{k})$ .
Quadratic Convergence: Near the optimum, the error in Newton's method decreases quadratically ( $ϵ_{k + 1} \propto ϵ_{k}^{2}$ ), meaning the number of correct digits roughly doubles with each iteration. This is significantly faster than the linear convergence of gradient descent ( $ϵ_{k + 1} \propto ϵ_{k}$ ).
The Trade-Off: The price for this incredible speed is a very high computational cost per iteration. Computing and inverting the $d \times d$ Hessian matrix is an $O (d^{3})$ operation, which is infeasible for the high-dimensional problems typical in modern machine learning.

This computational bottleneck is why pure Newton's method is rarely used for training large models. However, its principles are foundational to a family of highly successful quasi-Newton methods (like L-BFGS) that seek to approximate the inverse Hessian cheaply, capturing some of the benefits of quadratic convergence without the prohibitive cost.

So far, our optimization journey has been in the world of unconstrained problems. In our next lesson, we will introduce a fundamental tool for handling constraints: Lagrangian multipliers. This will allow us to formulate and solve a much broader class of optimization problems, leading us to the powerful Karush-Kuhn-Tucker (KKT) conditions.

Recommended resources

From Linear to Quadratic Approximation

The Power of Quadratic Convergence

Newton's Method vs. Gradient Descent: A Head-to-Head Comparison

Conclusion