Algorithms: Gradient Descent and Newton's Method
How we actually minimize: first-order steps, second-order steps, and why conditioning matters.
Leads to: 10.5 runs these solvers on portfolio and regression objectives.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- State the gradient-descent iteration and its convergence rate for strongly convex functions.
- Explain the role of the condition number in first-order convergence speed.
- State Newton's method and its local quadratic convergence.
- Compare gradient descent and Newton's method in cost per step and step count.
- Implement gradient descent on a quadratic and verify convergence to \(Q^{-1}c\).
Key Vocabulary
- Gradient descent
- The iteration \(x_{k+1}=x_k-t\,\nabla f(x_k)\); step downhill along the negative gradient.
- Step size / learning rate
- The scalar \(t\gt 0\); too large diverges, too small crawls; line search adapts it.
- Strong convexity
- There is \(\mu\gt 0\) with \(\nabla^2 f\succeq\mu I\); gives linear convergence.
- Condition number
- For a quadratic, \(\kappa=\lambda_{\max}/\lambda_{\min}\) of the Hessian; large \(\kappa\) means slow zig-zag descent.
- Newton's method
- The iteration \(x_{k+1}=x_k-[\nabla^2 f(x_k)]^{-1}\nabla f(x_k)\); uses curvature.
- Quadratic convergence
- Error squares each step (\(e_{k+1}\approx c\,e_k^2\)) near the optimum; Newton's hallmark.
Intuition & Motivation
Gradient descent
With a fixed step \(t\le1/L\) (where \(L\) is the Lipschitz constant of \(\nabla f\), i.e. \(\nabla^2 f\preceq LI\)), and strong convexity \(\nabla^2 f\succeq\mu I\), the iterates converge linearly:
The ratio \(\kappa=L/\mu\) is the condition number. When \(\kappa\) is large the factor \(1-1/\kappa\) is near 1 and convergence is slow - the classic zig-zag across a stretched bowl. Well-conditioned (\(\kappa\approx1\)) problems converge in a handful of steps.
Newton's method
Newton minimizes the local second-order Taylor model exactly. On a pure quadratic it reaches \(x^\star=Q^{-1}c\) in one step (the model is exact). Near a smooth minimum with \(\nabla^2 f^\star\succ0\), convergence is quadratic: the number of correct digits roughly doubles per iteration. The price is forming and solving \(\nabla^2 f\,\Delta x=-\nabla f\) (cost \(O(n^3)\)) each step.
| Method | Info used | Per-step cost | Steps to converge |
|---|---|---|---|
| Gradient descent | \(\nabla f\) | \(O(n)\) (plus grad) | Many; \(\propto\kappa\log(1/\epsilon)\) |
| Newton | \(\nabla f,\ \nabla^2 f\) | \(O(n^3)\) solve | Few; quadratic locally |
Interactive: watch the zig-zag
- Choosing a step \(t\gt 2/L\); gradient descent then diverges (overshoots the bowl).
- Blaming the algorithm for slow convergence when the real culprit is a large condition number \(\kappa\); precondition or rescale instead.
- Using Newton far from the optimum without safeguards (line search / trust region); the raw step can overshoot or head uphill.
- Inverting the Hessian explicitly. Solve the linear system \(\nabla^2 f\,\Delta x=-\nabla f\) instead.
- Normalize/scale features so \(\kappa\) is small - often the biggest practical speedup for first-order methods.
- Use Newton (or quasi-Newton like BFGS) when \(n\) is moderate and high accuracy is needed; gradient methods when \(n\) is huge.
- Backtracking line search makes both methods robust with almost no tuning.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#39 Integer Right Triangles (2%, tier A) #11 Largest Product in a Grid (5%, tier A) #44 Pentagon Numbers (6%, tier A) #18 Maximum Path Sum I (7%, tier A)
Applied:
#485 Maximum Number of Divisors (19%, tier B) #190 Maximising a Weighted Product (21%, tier B) #183 Maximum Product of Parts (23%, tier B)
Challenge:
#869 Prime Guessing (41%, tier C) #143 Torricelli Triangles (43%, tier C)
73 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
For \(f(x)=\tfrac12 x^\top Q x-c^\top x\) with \(Q=\diag(1,100)\), \(c=(1,1)^\top\): (a) What is \(\kappa\)? (b) With optimal fixed step, what contraction factor does gradient descent achieve? (c) How many Newton steps are needed?
(a) \(\kappa=\lambda_{\max}/\lambda_{\min}=100/1=100\).
(b) Contraction factor \((\kappa-1)/(\kappa+1)=99/101\approx0.980\) - each step cuts the error by only about 2%, so roughly \(\sim\kappa\log(1/\epsilon)\) iterations are needed.
(c) One. The objective is quadratic, so Newton reaches \(x^\star=Q^{-1}c=(1,\,0.01)^\top\) in a single step, independent of \(\kappa\).
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: \(f(x_k)-f^\star\le(1-\mu/L)^k(f(x_0)-f^\star)\) - linear, slower as the condition number \(\kappa=L/\mu\) grows.
A: Newton: uses the Hessian, quadratic local convergence, \(O(n^3)\)/step. Gradient descent: uses only the gradient, linear convergence, cheap per step.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Additional Exercises for Convex Optimization (Boyd & Vandenberghe, 2016) current - Ch. 9 - Ch. 9 exercises: unconstrained minimization, gradient and Newton methods, convergence.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lec. 12-20 - Conditioning and its effect on iterative convergence; linear solves inside Newton steps.