1.33 Newton's method and second-order optimization: study notes

Learn AI by Story

The idea in one sentence

Newton's method fits a parabola to the loss using the slope and the curvature at your current point and jumps straight to the parabola's lowest point (new x = old x minus first derivative divided by second derivative), which is perfect on a true parabola and doubles the correct digits per step near a smooth minimum, but costs far too much when there are millions of parameters.

The story from the video

Kabir is tired of tiny gradient steps. He wonders: if he knew the shape of the valley, not just the slope, could he jump straight to the bottom? He fits a parabola to the valley at his feet and leaps to its lowest point. On the true parabola (x minus 3) squared, starting at 10, the slope is 14 and the curvature is 2, so 10 minus 14/2 = 3: the exact bottom in one jump. On the real curve e to the x minus 2x the parabola at 0 bottoms out at 1, then the next jump lands at 0.736, and the errors fall 0.31, 0.043, 0.0009, 4 in ten million. The catch is cost: with many inputs the curvature is a Hessian matrix, and for a million weights that is about four terabytes.

(Story and numbers are illustrative toy examples that you can verify by hand or in a few lines of code.)

Key definitions

Term	Precise definition	Plain English
Newton's method (for optimization)	Iteration x_new = x_old minus H inverse times gradient, where H is the Hessian of f at x_old (in 1-D: x minus f' divided by f'')	Fit a bowl to where you stand, jump to its bottom
Newton-Raphson (root finding)	Iteration x_new = x minus g(x) divided by g'(x), which seeks a point where g(x) = 0	The same formula, used to find where a curve crosses zero
Newton for optimization vs root finding	Optimization Newton is root-finding Newton applied to g = f' (the gradient), whose root is a stationary point	To minimize f, find where the slope is zero
Hessian	The square matrix of all second partial derivatives of f (roadmap 1.25)	The curvature in every direction and every pair of directions
Positive definite	A symmetric matrix H with v-transpose H v above zero for every nonzero vector v; equivalently all eigenvalues above zero	The surface curves upward in every direction: a true bowl
Quadratic model	The second-order Taylor approximation f(x) + g times step + half of step times H times step (roadmap 1.26)	The parabola (or bowl) Newton fits and then minimizes
Quadratic convergence	The new error is about a constant times the old error squared	The number of correct digits roughly doubles each step
Damped Newton	Newton direction times a step length t between 0 and 1, chosen by backtracking line search	Take a cautious fraction of the jump, and only accept it if the loss really drops
Levenberg-Marquardt / regularized Newton	Replace H by H plus alpha times the identity before inverting	Add a safety cushion so the bowl is guaranteed to curve upward; large alpha behaves like small gradient steps
Quasi-Newton method	A method that builds an approximation of the Hessian (or its inverse) from successive gradients instead of computing it	A cheap, learned guess at the curvature
BFGS	A quasi-Newton method that updates an approximate inverse Hessian with low-rank corrections	The classic way to learn curvature as you go
L-BFGS	Limited-memory BFGS: keeps only the last few step and gradient-change vectors rather than a matrix	BFGS on a diet, usable with many parameters
Gauss-Newton (go deeper)	For least-squares losses, approximates the Hessian with J-transpose J, using only first derivatives (J is the Jacobian of the residuals)	Newton for curve fitting, with the hard part dropped
Fisher information / natural gradient (go deeper)	The expected outer product of the gradient of the log-likelihood; used as a curvature matrix that measures change in predicted probabilities	A curvature matrix tailored to probability models
Affine invariance	If you rescale or shear the variables by an invertible linear map (plus a shift), Newton's iterates transform the same way	Newton does not care how you scale the axes
Saddle point	A stationary point where the gradient is zero but curvature is positive in some directions and negative in others	A mountain pass: a minimum one way, a maximum the other
Negative curvature	A direction along which the second derivative is below zero	The surface bends downward there

Step-by-step explanation

Step 1: the local parabola. Near the current point x, the function looks like q(s) = f(x) + f'(x) s + half of f''(x) s squared, where s is the step. This is the second-order Taylor approximation (roadmap 1.26).

Step 2: find its bottom. The parabola's slope in s is f'(x) + f''(x) s. Setting it to zero gives s = minus f'(x) divided by f''(x). So the new point is x minus f'(x)/f''(x). Compare this with gradient descent, x minus eta f'(x): Newton replaces the hand-tuned step size by 1 over the curvature, which is exactly the best step size from 1.32. There is no eta to tune.

Step 3: repeat. At the new point, fit a fresh parabola and jump again.

Step 4: why it is perfect on a parabola. If f is itself a parabola, the model q is exact, so its minimum is the true minimum, reached in one jump. For (x minus 3) squared at x = 10: f' = 2(x minus 3) = 14, f'' = 2, new x = 10 minus 14/2 = 3.

Step 5: why it is fast on a curve. Near a smooth minimum with positive curvature, any function is almost a parabola, so the parabola's bottom is very close to the true bottom, and the error left after a jump is of the order of the old error squared. Small numbers squared are very small, so the digits double.

Step 6: many variables. With many inputs, the slope becomes the gradient vector and the curvature becomes the Hessian matrix H. The step is minus H inverse times the gradient (in practice you solve the linear system H s = minus g instead of forming the inverse). On a stretched canyon this is a single step, because H inverse exactly undoes the stretching.

Step 7: the catch. Computing H needs second derivatives, storing it needs n squared numbers, and solving needs about n cubed operations. Also H must be positive definite for the jump to head downhill; at a saddle point or in a region of negative curvature Newton may head uphill or toward a maximum.

Everything the video skipped

Root-finding Newton versus optimization Newton. The formula x minus f/f' was first a method for finding where a function equals zero (Newton-Raphson). To minimize f we want f' = 0, so we apply the same recipe to f', which brings in f''. Same idea, one derivative higher.

Affine invariance. Gradient descent's behaviour changes if you stretch an axis (the condition number changes, 1.32). Newton's does not: if you replace x by A x with A invertible, the Newton iterates correspond exactly. That is why the canyon with curvatures 1 and 10 costs Newton the same single step as a round bowl. (CMU 10-725 Lecture 14 notes discuss this.)

Pure phase and damped phase. Far from the minimum, the quadratic model can be a poor guide, and a full Newton jump can even increase the loss. The textbook fix, described in the CMU Lecture 14 notes, is damped Newton: shrink the jump by backtracking until the loss drops enough. The analysis then has two phases: a damped phase where each step makes guaranteed but modest progress, then a pure phase near the optimum with full steps and quadratic convergence.

Regularization (Levenberg-Marquardt). Goodfellow, Bengio and Courville (sec. 8.6.1) describe adding a constant alpha to the diagonal: use H plus alpha I. If H has a negative eigenvalue, a large enough alpha makes the matrix positive definite; with a very large alpha the step becomes a tiny gradient step. The same book notes that Newton can be attracted to saddle points, and that in high dimensions saddle points are much more common than local minima for many random functions.

Quasi-Newton methods. Instead of computing H, BFGS keeps an approximation of the inverse Hessian and refines it with low-rank updates using how the gradient changed between steps. L-BFGS keeps only a handful of recent vectors, so memory is proportional to n rather than n squared. Scikit-learn's LogisticRegression uses lbfgs as its default solver (changed from liblinear in version 0.22).

Go deeper: Gauss-Newton and Fisher. For least-squares problems the Hessian is approximately J-transpose J, which needs only first derivatives. For probabilistic models, the Fisher information plays a similar role and leads to natural-gradient ideas. These approximate curvature cheaply for specific kinds of loss. (Standard background; not covered in the video.)

Why deep learning mostly does not use full Newton. Beyond the cost, mini-batch noise makes curvature estimates unreliable, and the Hessians of neural networks are indefinite. Practical training uses first-order methods, sometimes with diagonal curvature scaling, while second-order ideas appear in approximations and in smaller models.

Limits of the quadratic convergence claim. It needs the minimum to have positive curvature and the start to be close enough. If the curvature at the minimum is zero, convergence slows (see worked example 3).

Memory and cost. The CMU notes quote per-iteration cost of about n cubed for Newton versus n for gradient descent, and n squared memory for the Hessian. A million parameters: n squared = 10 to the 12 entries, 4 bytes each in float32 = 4 terabytes. The dense solve costs of the order n cubed = 10 to the 18 operations.

Connections on the roadmap.

1.25 Jacobian and Hessian: the Hessian is the heart of this lesson.
1.26 Taylor approximation: the second-order Taylor model is what Newton minimizes.
1.31 Convexity: for a convex function the Hessian is positive semi-definite, so the quadratic model never curves downward.
1.32 Gradient descent convergence: 1/curvature is the best step size; Newton automatically picks it, and in all directions at once.
Later optimization modules: quasi-Newton methods, trust regions and natural gradients extend these ideas.

Worked example 1: one jump on a parabola

f(x) = (x minus 3) squared, start x = 10.

f'(10) = 2(10 minus 3) = 14.
f'' = 2 (a constant).
Newton: 10 minus 14/2 = 3.
At 3: f' = 0, so the next jump is 3 minus 0/2 = 3. Done.

Gradient descent with eta = 0.05 on the same curve has curvature 2 too, so it multiplies the distance to 3 by 1 minus 2 times 0.05 = 0.9 each step: the distance shrinks from 7 to 7 times 0.9^10 = 2.44 after ten steps. Newton took one step.

Worked example 2: e to the x minus 2x from 0

f(x) = e^x minus 2x. f'(x) = e^x minus 2, f''(x) = e^x (always positive, so f is convex). The minimum is where e^x = 2, so x = ln 2 = 0.693147.

Newton step: x_new = x minus (e^x minus 2)/e^x.

Step	x	Error from ln 2
0	0	0.693
1	1	0.307
2	0.735759	0.0426
3	0.694042	0.000895
4	0.6931476	4.0e-7
5	0.69314718056	8e-14

First jump check: at 0, f' = 1 minus 2 = -1, f'' = 1, so x_new = 0 minus (-1)/1 = 1. The local parabola there is q(x) = 1 minus x plus x squared over 2, with bottom at x = 1 and q = 0.5. The true function there is f(1) = e minus 2 = 0.718, higher than the model said, because the real curve bends up faster than a parabola. Second jump: f'(1) = e minus 2 = 0.718, f''(1) = e = 2.718, so x = 1 minus 0.718/2.718 = 0.7358. Function values: f(0.7358) = 0.6156 and f(ln 2) = 0.6137. Notice the error pattern: 0.31, 0.043, 0.0009, 4e-7, 8e-14. Each is roughly a constant times the square of the one before: quadratic convergence.

Honest comparison: gradient descent with eta = 0.5 on this same function also converges fast (error 0.193, 0.0175, 0.00015, 1.2e-8), because 0.5 is close to 1 over f''(ln 2) = 0.5. So this example shows Newton's speed, not a weakness of gradient descent; the value of Newton is that it finds the right step itself.

Worked example 3: when Newton is not magic

(a) A flat bottom: f(x) = x to the 4. f' = 4x cubed, f'' = 12 x squared. Newton: x minus 4x cubed / (12 x squared) = x minus x/3 = (2/3) x. From 1: 1, 0.667, 0.444, 0.296. Only linear convergence with factor 2/3, because the curvature at the minimum is zero and the parabola model is a poor fit.

(b) Negative curvature: f(x) = minus x squared (a hill). From x = 2: f' = -4, f'' = -2, so Newton gives 2 minus (-4)/(-2) = 0. It jumps to the top of the hill, a maximum. The method seeks a stationary point, not necessarily a minimum, which is why positive definiteness or damping matters.

(c) A stretched canyon in two variables: f(x, y) = half of (x squared plus 10 y squared) from (10, 10). Gradient = (10, 100), Hessian = diag(1, 10), H inverse times gradient = (10, 10), so the new point is (10 minus 10, 10 minus 10) = (0, 0): the exact bottom in one step. Gradient descent with eta = 0.1 needs 66 steps to shrink x by a factor of 1000 (see 1.32).

Comparison tables

Feature	Gradient descent	Newton's method
Information used	gradient	gradient and Hessian
Step size	tuned eta	none (1/curvature built in)
Perfect on a quadratic	only if eta = 1/c in every direction	always, one step
Rate near a nice minimum	linear	quadratic
Cost per step	about n	about n cubed
Memory	n	n squared
Sensitive to scaling	yes (condition number)	no (affine invariant)
Behaviour at saddle points	moves away slowly	may be attracted or move uphill

Method	Curvature used	Cost and memory	Typical use
Newton	exact Hessian	n cubed, n squared	small, smooth problems
Damped Newton	exact Hessian with line search	same	safer Newton
Levenberg-Marquardt	H plus alpha I	same	nonlinear least squares, regularizing
BFGS	learned inverse Hessian	n squared	medium problems
L-BFGS	few stored vectors	about n times the vectors kept	large smooth problems, default logistic regression solver
Gauss-Newton	J-transpose J	cheaper than full Hessian	curve fitting

Common mistakes and myths

"Newton always converges in one step." Only on a quadratic. On e to the x minus 2x it took five steps to reach 8e-14.
"Newton is always faster than gradient descent." Per step yes, per second not necessarily: each step costs about n cubed.
"Newton finds minima." It finds stationary points; at negative curvature it can head to a maximum or saddle.
"Quadratic convergence is guaranteed from anywhere." It is a local property near the minimum; far away you need damping.
"The Hessian inverse is formed explicitly." In practice a linear system is solved, or the inverse is approximated.
"Newton needs a learning rate." The pure method has none; damped versions have a step length found by line search.
"Quasi-Newton is first-order so it is as weak as gradient descent." It uses gradients only, but it learns curvature from them and is usually much faster.
Mixing up the two Newtons: root-finding uses f over f', optimization uses f' over f''.

Real-life uses

Logistic regression and generalized linear models: Newton-type and L-BFGS solvers are standard; scikit-learn defaults to lbfgs.
Statistics: fitting models by maximum likelihood often uses Newton-like iterations.
Engineering design and control: smooth, low-dimensional problems where a few expensive steps beat thousands of cheap ones.
Nonlinear least squares and curve fitting: Gauss-Newton and Levenberg-Marquardt.
Calculators and numerical libraries: root-finding by Newton-Raphson.

Self-check questions

What is the Newton update in one dimension? Answer: x minus f'(x) divided by f''(x).
What model does it minimize? Answer: the second-order Taylor parabola at the current point.
For (x minus 3) squared from 10, what is the first jump? Answer: 10 minus 14/2 = 3, exactly the minimum.
For e to the x minus 2x, where is the minimum? Answer: x = ln 2 = 0.693147.
What is the first Newton iterate from 0? Answer: 1, since f'(0) = -1 and f''(0) = 1.
What does quadratic convergence mean in practice? Answer: correct digits roughly double each step (errors 0.043, 0.0009, 4e-7, 8e-14).
How big is the Hessian of a million-weight network? Answer: 10 to the 12 entries, about 4 terabytes in float32.
Why add alpha times the identity to the Hessian? Answer: to make the matrix positive definite and tame steps near saddle points (Levenberg-Marquardt).
Why is Newton affine invariant? Answer: the Hessian inverse cancels any linear rescaling of the variables, so a stretched canyon costs one step.
What does L-BFGS do? Answer: builds a cheap curvature estimate from a few recent steps and gradient changes, avoiding the n squared matrix.

Key takeaways

Newton divides slope by curvature: gradient descent with the ideal step size chosen automatically.
One jump on a parabola, digit-doubling near a smooth minimum.
In many variables the cost (n cubed, n squared memory) is the price.
Damping and regularization handle bad curvature; quasi-Newton methods like L-BFGS make it affordable.

Go deeper: D2L 12.3.3 (Newton's Method, Convergence Analysis); Goodfellow et al. 8.6 on Newton and BFGS; CMU Lecture 14 on damped Newton.

Next roadmap ID: 1.34 Joint, marginal and independent events.

Sources and further reading

Zhang, Lipton, Li, Smola, Dive into Deep Learning, sec. 12.3 "Gradient Descent", 12.3.3.1 Newton's Method and 12.3.3.2 Convergence Analysis. https://d2l.ai/chapter_optimization/gd.html
Goodfellow, Bengio, Courville, Deep Learning, ch. 4 "Numerical Computation", 4.3 Gradient-Based Optimization (Newton's method, Hessian). https://www.deeplearningbook.org/contents/numerical.html
Goodfellow, Bengio, Courville, Deep Learning, ch. 8 "Optimization for Training Deep Models", 8.2.3 saddle points, 8.6.1 Newton's Method, 8.6.3 BFGS. https://www.deeplearningbook.org/contents/optimization.html
CMU 10-725 Convex Optimization (Fall 2016), Lecture 14 "Newton's Method" scribe notes. https://www.stat.cmu.edu/~ryantibs/convexopt-F16/scribes/newton-scribed.pdf
scikit-learn documentation, LogisticRegression (solver 'lbfgs' default). https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html

Accuracy note: the numbers are verified in Python; Gauss-Newton, Fisher information and the deep-learning remarks are standard background, not drawn from the sources above.

Search This Blog

Learn AI by Story

Newton's method and second-order optimization: study notes