Back to the on-screen lesson ·
Minimising the quadratic model, quadratic convergence near the answer, and the matrix solve that pays for it.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to take a Newton step by hand, write the Hessian of a small function, and explain why Newton finishes a quadratic in one step from anywhere. You will also be able to state what quadratic convergence claims and where it applies, say what each iteration costs in terms of the number of variables, and explain why a pure Newton step needs a line search or trust region around it on any problem that is not convex.
Gradient descent, which uses slope alone, and its zig-zag on a stretched valley. The zig-zag came from ignoring curvature: the method has no idea one direction is a hundred times steeper than another. Newton's method is what happens when curvature is used, and the change is dramatic in both directions — far fewer iterations, far more work per iteration.
Gradient descent implicitly uses the first-order model $f(x + d) \approx f(x) + \nabla f^\top d$, which has no minimum — hence the need for a step size to stop it running away. Newton uses the second-order model
$$m(d) = f(x) + \nabla f(x)^\top d + \tfrac12 d^\top \nabla^2 f(x)\, d,$$
which does have a minimum when the Hessian is positive definite. Setting $\nabla m = 0$:
$$\nabla^2 f(x)\, d = -\nabla f(x), \qquad x_{k+1} = x_k + d.$$
In one variable this is $x - f'(x)/f''(x)$: slope divided by curvature.
What it buys. Near a minimum where the Hessian is positive definite, convergence is quadratic — the number of correct digits roughly doubles each iteration. Six iterations can take you from one correct digit to thirty. Gradient descent, in the same place, is linear: a fixed fraction of the error removed per step.
What it costs. Each iteration needs the Hessian ($n^2$ second derivatives) and a linear solve ($\sim n^3$ operations). For $n = 10$ that is nothing. For $n = 10^6$ it is impossible — the Hessian alone would be $10^{12}$ numbers. The whole design space of unit 3 is this trade, and lesson 17 is the compromise.
What can go wrong. The Newton direction is a descent direction only when $\nabla^2 f \succ 0$. Far from a minimum on a non-convex problem it can point uphill or at a saddle, and a pure Newton step has no safeguard. In practice it is always wrapped in a line search or a trust region — lesson 15's job.
Another way: picture
A curve with a parabola drawn tangent to it at the current point, matching both its slope and its bend. Newton jumps to the bottom of the parabola. Where the curve really is parabola-like the jump is superb; where it is not, the parabola's bottom can be somewhere the curve is higher than where you started.
Another way: steps
One Newton iteration:
Take $f(x) = ax^2 + bx + c$ with $a > 0$. Then $f' = 2ax + b$ and $f'' = 2a$, so
$$x_{k+1} = x_k - \frac{2a x_k + b}{2a} = x_k - x_k - \frac{b}{2a} = -\frac{b}{2a}.$$
The starting point cancels completely. One step lands exactly on the minimiser, from anywhere on the line.
That is not luck. Newton minimises the second-order Taylor model, and for a quadratic that model is the function, remainder and all — there is nothing left over. Every non-quadratic function is being treated as though it were this one, and the accuracy of the step is exactly the accuracy of that pretence. Near a minimum, where the remainder is third-order and small, the pretence is excellent and convergence is quadratic; far away it can be worthless.
Inverting the Hessian. Solving the system is cheaper and numerically better. Writing $d = -H^{-1}g$ on paper is fine; computing $H^{-1}$ in code is not.
No safeguard. Pure Newton diverges readily from a bad start. The full step $t = 1$ should be tried first — it is right near the solution — and a line search should be free to reject it.
An indefinite Hessian. Away from a minimum the direction can ascend. Modified-Newton methods add a multiple of the identity until the Hessian is positive definite, which quietly interpolates towards gradient descent.
Using it at scale. At $n = 10^6$ there is no Hessian and no solve. That is not a failure of the method, it is its price, and lesson 17 is what to do instead.
"Doubles the correct digits each iteration" is a local result: it holds once the iterates are close enough that the quadratic model is accurate and the Hessian is positive definite. It says nothing about getting there. A Newton run on a hard problem can spend most of its iterations wandering, behaving no better than gradient descent, and then finish in three or four iterations once it enters the good region. This is why the practical question is never "is Newton faster" but "how much does each iteration cost, and how many will be spent outside the region where the promise applies" — and the second half of that question is what a line search or trust region is managing.
$f(x) = x^2 + 100y^2$ from $(1,1)$. Gradient descent with a stable step size needs hundreds of iterations, zig-zagging across the valley.
Slope alone: the condition number bites.
The Hessian is diagonal with entries $2$ and $200$. Newton solves $2d_1 = -2$ and $200 d_2 = -200$, giving $d = (-1, -1)$.
Curvature included: each direction scaled by its own.
One step lands at $(0,0)$: the minimum. The condition number vanished from the problem because the Hessian solve rescaled each direction by its own curvature — which is exactly what lesson 14's change of units did by hand, done automatically and at every iteration.
Newton is automatic rescaling.
$f(x) = \sqrt{1 + x^2}$, which is convex and flattens out to a straight line at large $|x|$. From $x = 10$, $f' \approx 0.995$ and $f'' \approx 0.001$.
Nearly straight, so almost no curvature.
The Newton step is $-f'/f'' \approx -1000$, landing near $x = -990$ — vastly past the minimum at $0$, on the other side and no better off.
A tiny curvature makes an enormous step.
The direction was right; the length was absurd, because a nearly-straight function has a nearly-flat model whose minimum is nearly at infinity. A backtracking line search rejects the full step, halves until progress is real, and the run proceeds — which is why lesson 15 comes before this one rather than after.
The safeguard is not optional.
$f'(x) = 3x^2 - 2$, so $f'(2) = 10$. $f''(x) = 6x$, so $f''(2) = 12$.
Slope and curvature at the point.
Step: $2 - 10/12 = 2 - 5/6 = 7/6 \approx 1.167$.
Check it descends: $f(2) = 4$ and $f(7/6) \approx 1.59 - 2.33 = -0.74$. A large improvement. But notice the Hessian $6x$ is negative for $x < 0$ — start this run at $x = -2$ and the direction points the wrong way, towards the local maximum. The method has no way to tell, and the function has no minimum at all.
Match each part of a safeguarded Newton iteration to the job it does.
| Measures the current first-order slope | Finds the minimiser of the local quadratic model | Makes the model's proposed direction a descent direction | Chooses a step length that decreases the real objective | |
|---|---|---|---|---|
| Compute the gradient | ||||
| Solve $H d=-g$ | ||||
| Check or modify an indefinite Hessian | ||||
| Run a line search along $d$ |
Apply one Newton step to $3x^2 + 12x$ from $x = 5$. Where does it land?
Answer:
How many Newton steps does $5x^2 + -20x$ need from $x = 40$ to reach its minimum exactly?
Answer:
Why does Newton's method finish a quadratic in one step, from any starting point?
| Exactly the original function | Zero | Lands at the true minimiser | Only an approximation, so iteration continues | |
|---|---|---|---|---|
| Second-order Taylor model of a quadratic | ||||
| All derivatives beyond second order | ||||
| Newton's jump to the model minimiser | ||||
| Second-order model of a non-quadratic |
Write the Hessian of $f(x,y) = 6x^2 + xy + 7y^2$.
This task has no paper form; do it on a device.
Far from the minimum, a pure Newton step on a non-convex objective increases the objective. What went wrong?
| Makes the Newton direction a descent direction | Can produce an uphill or saddle-seeking direction | Rejects or shortens a proposed objective-increasing step | Limits the step to a locally reliable model region | |
|---|---|---|---|---|
| Positive-definite Hessian | ||||
| Indefinite Hessian away from a minimum | ||||
| Line search | ||||
| Trust region |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
How many Newton steps does $2x^2 + -8x$ need from $x = -7$ to reach its minimum exactly?
Answer:
You can take a Newton step, write a Hessian, and say what Newton costs and promises. Next: the same curvature information without the Hessian.
9. Your turn: one Newton step on $f(x) = x^3 - 2x$ from $x = 2$, step 3