Interactive tutorial on Newton's method

This learning module has many interactive demos. It is easier to work with them on a larger screen. Bookmark and revisit if you are currently on a small screen device.

\(\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\asterisk}{\ast} \newcommand{\sup}{\text{sup}} \newcommand{\inf}{\text{inf}} \newcommand{\min}{\text{min}\;} \newcommand{\max}{\text{max}\;} \newcommand{\maxunder}[1]{\underset{#1}{\max}} \newcommand{\minunder}[1]{\underset{#1}{\min}} \newcommand{\real}{\mathbb{R}} \newcommand{\natural}{\mathbb{N}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\irrational}{\mathbb{I}} \newcommand{\complex}{\mathbb{C}} \newcommand{\cardinality}[1]{|#1|} \newcommand{\vec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\star}[1]{#1^*} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\indicator}[1]{\mathcal{I}(#1)} \renewcommand{\BigO}[1]{\mathcal{O}(#1)} \renewcommand{\BigOsymbol}{\mathcal{O}} \renewcommand{\smallo}[1]{\mathcal{o}(#1)} \renewcommand{\smallosymbol}[1]{\mathcal{o}} \newcommand{\set}[1]{\mathbb{#1}} \newcommand{\complement}[1]{#1^c} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\setdiff}{\setminus} \newcommand{\setsymmdiff}{\oplus} \newcommand{\dash}[1]{#1^{'}} \newcommand{\permutation}[2]{{}_{#1} \mathrm{ P }_{#2}} \newcommand{\combination}[2]{{}_{#1} \mathrm{ C }_{#2}} \newcommand{\prob}[1]{P(#1)} \newcommand{\pmf}[1]{P(#1)} \newcommand{\pdf}[1]{p(#1)} \newcommand{\cdf}[1]{F(#1)} \newcommand{\expect}[2]{E_{#1}\left[#2\right]} \newcommand{\entropy}[1]{\mathcal{H}\left[#1\right]} \newcommand{\expe}[1]{\mathrm{e}^{#1}} \newcommand{\textexp}[1]{\text{exp}\left(#1\right)} \def\independent{\perp\!\!\!\perp} \def\notindependent{\not\!\independent} \newcommand{\yhat}{\hat{y}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vk}{\vec{k}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vmu}{\vec{\mu}} \newcommand{\vsigma}{\vec{\sigma}} \newcommand{\vphi}{\vec{\phi}} \newcommand{\vtau}{\vec{\tau}} \newcommand{\vtheta}{\vec{\theta}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mH}{\mat{H}} \newcommand{\mK}{\mat{K}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mI}{\mat{I}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\mat{\Sigma}} \newcommand{\mTheta}{\mat{\theta}} \newcommand{\setsymb}[1]{#1} \newcommand{\sA}{\setsymb{A}} \newcommand{\sB}{\setsymb{B}} \newcommand{\sC}{\setsymb{C}} \newcommand{\sO}{\setsymb{O}} \newcommand{\sP}{\setsymb{P}} \newcommand{\sQ}{\setsymb{Q}} \newcommand{\sH}{\setsymb{H}} \newcommand{\sX}{\setsymb{X}} \newcommand{\sY}{\setsymb{Y}} \newcommand{\norm}[2]{||{#1}||_{#2}} \newcommand{\infnorm}[1]{\norm{#1}{\infty}} \newcommand{\fillinblank}{\text{ }\underline{\text{ ? }}\text{ }} \newcommand{\lbrace}{\left\{} \newcommand{\rbrace}{\right\}} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\seq}[1]{\left( #1 \right)} \newcommand{\ndim}{N} \newcommand{\ndimsmall}{n} \newcommand{\dataset}{\mathbb{D}} \newcommand{\ndata}{D} \newcommand{\ndatasmall}{d} \newcommand{\labeledset}{\mathbb{L}} \newcommand{\nlabeled}{L} \newcommand{\nlabeledsmall}{l} \newcommand{\unlabeledset}{\mathbb{U}} \newcommand{\nunlabeled}{U} \newcommand{\nunlabeledsmall}{u} \newcommand{\nclass}{M} \newcommand{\nclasssmall}{m} \newcommand{\loss}{\mathcal{L}} \newcommand{\sign}{\text{sign}} \newcommand{\Gauss}{\mathcal{N}} \newcommand{\hadamard}{\circ} \newcommand{\doh}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dox}[1]{\doh{#1}{x}} \newcommand{\doy}[1]{\doh{#1}{y}} \newcommand{\doxx}[1]{\doh{#1}{x^2}} \newcommand{\doyy}[1]{\doh{#1}{y^2}} \newcommand{\doxy}[1]{\frac{\partial #1}{\partial x \partial y}} \newcommand{\doyx}[1]{\frac{\partial #1}{\partial y \partial x}} \newcommand{\qed}{\tag*{$\blacksquare$}}\)

        Newton's method
        Optimization
      

Newton's method is an approach for unconstrained optimization.

In this article, we will motivate the formulation of this approach and provide interactive demos over multiple univariate and multivariate functions to show it in action.

Prerequisites

To understand this article, we recommend familiarity with the concepts in

Follow the above links to first get acquainted with the corresponding concepts.

Problem statement

In this article, we will consider an objective function $ f : \real^\ndim \to \real $ that we wish to minimize. We express the unconstrained optimization problem as,

\begin{aligned} \min_{\vx} \text{ }& f(\vx) \\ \end{aligned}

Newton's method is an iterative approach. Starting from an arbitrary point, we will progressively discover points with lower function values till we converge to a point with minimum function value.

The next few sections will outline the strategy used by Newton's method to discover the next point $ \va + \vp $, from the current point $ \va $ on its journey to the optimal solution.

Taylor's theorem and optimization: A recap

Owing to the Taylor's Theorem, for a twice differentiable function $ f: \real^\ndim \to \ndim $, the value of the function at a point $\va+\vp $ can be written in terms of the function value at a point $ \va $ as follows.

\begin{equation} f(\va+\vp) = f(\va) + \nabla_{\va}^T \vp + \frac{1}{2} \vp^T \mH_{\va} \vp \label{eqn:second-order-taylor-approx} \end{equation}

Here, $ \nabla_{\va} $ and $ \mH_{\va} $ denote the gradient and Hessian of the function, evaluated at the point $ \va $.

To choose the next point $ \va + \vp $, we need to discover a suitable value of $ \vp $. Since $ \va $ is already known (the current point), this is a function in $ \vp $. At its local minimizer, $ \star{\vp} $, the gradient with respect to $ \vp $ will be zero.

\begin{aligned} \doh{f(\va + \star{\vp})}{\vp} = 0 \\\\ \label{eqn:first-order-condition-on-p} \end{aligned}

Thus, we now have a system of equations to solve for the value of $ \vp $ to choose our next point $ \va + \vp $.

Newton's method

The Newton's method arrives at the next iterate $ \va + \vp $ from the current iterate $ \va $ by solving the above equation.

$$\begin{aligned} & \frac{\partial f(\va + \star{\vp})}{\partial \vp} = 0 \\ \implies & \frac{\partial}{\partial \vp} \left( f(\va) + \nabla_{\va}^T \vp + \frac{1}{2} \vp^T \mH_{\va} \vp \right) = 0 \\ \implies & \nabla_{\va} + \mH_{\va} \vp = 0 \\ \implies & \vp = -\inv{\mH_{\va}} \nabla_{\va} \\ \end{aligned} $$

Thus, Newton's method proceeds as follows:

Start from a suitable point $ \va = \va_0 $
Apply the following update to $ \va $ till a local minimizer has been reached: $ \va \leftarrow \va - \mH_{\va}^{-1} \nabla_{\va} $.

Quite straightforward!

Newton's method demo: $ \min x^2 $

Let's see Newton's method in action with a simple univariate function $ f(x) = x^2 $, where $ x \in \real $.

Note that the function has a global minimum at $ x = 0 $. The goal of the Newton's method is to discover this point of least function value, starting at any arbitrary point.

In this accompanying demo, change the starting point by dragging the orange circle and see the trajectory of Newton's method towards the global minimum.

Newton's method analysis: $ \min x^2 $

No matter where you start for this convex quadratic objective function, Newton's method finds the minimum in exactly 1 step.

In fact, this is a property worth noting: Newton's method always finds the minimum of a convex quadratic objective function in exactly one step. And why not? The second-order Taylor series expansion perfectly models the function and Newton's method finds the exact minimum of that second-order model in each step.

So, let's go beyond quadratic and beyond convex.

Newton's method demo: $ \min x^4 - 8x^2 $

Let's see Newton's method on a nonconvex function with multiple minima and a single maximum.

$$ f(x) = x^4 - 8x^2 $$

Newton's method analysis: $ \min x^4 - 8x^2 $

This is clearly a nonconvex objective fuction with two minima and one local maximum, the bump in the middle.

First, note that the Newton's method, without any restrictions on its movement, does not discriminate between the minimum and the maximum. It just gets to a nearby stationary point. So, if you start very close to the bump in the center, you will land at the local maximum.

Second, note that the iterates jump around before they reach a stationary point, unlike our previous example, a consequence of the objective function being nonconvex.

Also worth nothing is that starting near a particular local minimum does not guarantee that the algorithm will converge to that local minimum. It may actually go over the bump and land up in another local minimum altogether.

Newton's method demo: Rosenbrock's function

Of course, Newton's method can be applied to multivariate functions.

We have introduced Rosenbrock's function in the module on Calculus.

$$ \min_{x,y} (1-x)^2 + 100 (y-x^2)^2 $$

The global minimum of the function lies at $ x = 1, y = 1 $.

Note that unless you start close enough to the minimum, the Newton's method may not find it within 10 iterations. This is a well-known shortcoming of the Newton's method. Iterations should begin with a point that is likely close to the minimum.

Newton's method demo: Himmelblau's function

So far, our function had only a single minimum. Such functions, albeit easy to understand, are rare in machine learning. Let us study a function with multiple minima. We have introduced Himmelblau's function in the module on Calculus.

$$ f(x,y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2 $$

Himmelblau's function is nonconvex with 4 minima (marked in green) and 1 local maximum (marked in blue).

As expected, Newton's method seeks out one of these stationary points. It does not necessarily reach the closest stationary point.

Challenge of the Hessian

Newton's method seems quite straightforward.

But! What if the function is not twice differentiable? Or what if the Hessian is computationally infeasible.

In these cases, we cannot calculate $ \mH_{\vx} $ , let alone it's inverse, $ \inv{\mH_{\vx}} $.

In such scenarios, we use alternative approaches such as

approximate the Hessian using quasi-Newton methods such as BFGS
ignore the Hessian term altogether using gradient descent

Where to next?

Expand your knowledge of optimization approaches with our detailed interactive articles on this subject.

To brush up on calculus, explore our articles on topics in calculus and multivariate calculus. Or start with strong mathematical foundations.

Already an optimization expert? Check out comprehensive courses on machine learning or deep learning.

Please support us

Help us create more engaging and effective content and keep it free of paywalls and advertisements!

Please donate

Subscribe for article updates

Stay up to date with new material for free.

Newton's method

Optimization

Prerequisites

Problem statement

Taylor's theorem and optimization: A recap

Newton's method

Newton's method demo: \( \min x^2 \)

Newton's method analysis: \( \min x^2 \)

Newton's method demo: \( \min x^4 - 8x^2 \)

Newton's method analysis: \( \min x^4 - 8x^2 \)

Newton's method demo: Rosenbrock's function

Newton's method demo: Himmelblau's function

Challenge of the Hessian

Where to next?

Please support us

Subscribe for article updates