Section 1
The least squares objective and its gradient
How to use this pageClick the colored symbols to see what they mean. Move each demo before you read the text under it, and commit to a prediction first.
data and unknowns gradient second derivatives and multipliers objective and Lagrangian step sizes and tolerance
Picture three compass bearings taken from three hilltops. They disagree a little, and the best spot has the smallest total disagreement. That is least squares: each row of is one measurement, is its target value, and is the position we choose.
Click any coloured symbol to see what it means.
Predict first. Drag the point to the bottom of the bowl. How long is the arrow there?
The bowl and its downhill arrow
The contours are the level curves of in the plane. Drag the point . The arrow is minus the gradient, and the teal dot is the lowest point. The readout compares the gradient formula with a numerical slope.
current point (drag)lowest pointminus the gradient
The factor one half only tidies the later formulas. The disagreement is half the squared length of the residual , the amount by which the measurements miss their targets.
The contours are ellipses because is quadratic. A long thin ellipse means one direction is far more sensitive than the other: the poor conditioning of Section 4.2.
Click any coloured symbol to see what it means.
The residual says how far each measurement misses. Multiplying by gives the direction to move, and the gradient is zero exactly when .
Going deeper: where the gradient comes from
This derivation is added here and is not printed in the book. Write as one half of . Multiply out to get . The matrix is symmetric, so the gradient of the first term is and the gradient of the middle term is . The last term does not depend on .
Challenge +8 XPDrag the point until it sits on the lowest point (teal). The readout must show a gradient length below 0.25.
Gradient descent on least squares
To solve the problem by gradient descent (Section 4.3), follow the gradient downhill in small steps. The book writes this as Algorithm 4.1. The step size sets how far each step goes, and the tolerance sets when to stop.
Algorithm 4.1: gradient descent for least squaresMinimize with respect to .
- Start from any . Set the step size and the tolerance to small positive numbers.
- While , repeat the update below.
Predict first. The step size is 0.3 and the limit is about 0.82. What happens to the number of steps if you double to 0.6?
Running Algorithm 4.1
path of the pointlength of the gradienttolerance linelowest point
Start with the defaults. On the log chart the gradient length falls in an almost straight line, because each step cuts it by about the same factor. Raise past the limit and the path zigzags, then the gradient grows instead of shrinking.
The gradient is zero at the minimum, so the loop ends once its length falls to or below. The step size has an exact limit. Let be the largest eigenvalue of . The iteration converges when and diverges when is larger.
Going deeper: how the middle row changes the steps
This comparison is added here. Lower the weight of the middle row and the valley narrows. The largest eigenvalue falls, so the limit rises from 0.82 at weight 0.6 to 0.89 at weight 0.1. The smallest eigenvalue falls more, so the steps grow from 57 to 99. The speed is set by the ratio of the largest to the smallest eigenvalue, the condition number of Section 4.2.
Going deeper: why the limit is 2 over the largest eigenvalue
This derivation is added here. Along an eigenvector of with eigenvalue , one step multiplies the error in that direction by . The error shrinks only when , which means . Along the slowest direction the factor is , and that direction sets the number of steps.
Challenge +8 XPSet the step size above the limit printed in the readout. The readout must say that the run cannot converge.
Challenge +8 XPLower the weight of the middle row until gradient descent takes more than 90 steps and still converges.
Newton’s method on a quadratic
Newton’s method (Section 4.3.1) replaces by its second-order Taylor approximation at the current point and jumps to the lowest point of that approximation. Its step uses the Hessian , the matrix of second derivatives, which here is for every .
Click any coloured symbol to see what it means.
The book states the one-step result without printing the update. The update above is added here.
Predict first. Newton’s method on this quadratic, from any start point. How many steps does it need to reach the lowest point?
One Newton step against gradient descent
Drag the start point. Newton’s step jumps straight to the lowest point. Gradient descent takes many small steps along a curved route.
start (drag)Newton: one jumpgradient descent, fixed steplowest point
The readout tests the claim at a nearby point: the true and the quadratic prediction differ only by rounding noise. Newton’s step needs , which means solving the very system we started from, so for many unknowns gradient descent is often cheaper.
The book’s remark is that the quadratic approximation is exact, because the true function is quadratic. One step therefore reaches the global minimum from any start, with no step size to choose.
Going deeper: the quadratic model is exact
This identity is added here. For a quadratic, holds for every step , with no remaining terms. Newton’s method minimizes the right-hand side over , which gives the update above.
Challenge +8 XPDrag the start point to a corner, then press Newton step once. The distance to the lowest point must be below 0.001.
The constrained solution and its multiplier
Keep the same but require a solution of length at most 1, the norm constraint of Section 4.4. Attach a multiplier and form the Lagrangian of Equation 4.14 with one inequality:
Click any coloured symbol to see what it means.
The problem then becomes the minimax of Equation 4.24:
Click any coloured symbol to see what it means.
Predict first. Shrink the target until the unconstrained answer lies inside the circle. What is the multiplier then?
The solutions as the multiplier grows
Each value of gives one point . The curve of these points runs from the unconstrained answer towards the origin. The point where it crosses the circle is the constrained answer.
solutions for each multiplierconstrained answerunconstrained answer
At the point sits at the unconstrained answer. As grows, it slides towards the origin. A small target puts the unconstrained answer inside the circle, so the constraint is inactive and the multiplier stays at 0.
Check the easy case first. If the smallest-norm unconstrained solution lies inside the circle, it is the constrained answer and . Otherwise the answer lies on the circle.
The book states the stationarity condition as Equation 4.25 and solves it as Equation 4.26:
Click any coloured symbol to see what it means.
Click any coloured symbol to see what it means.
Going deeper: the stationarity condition 4.25 and the solution 4.26
This step is added here. The book states 4.25 and 4.26 directly. The gradient of is by Equation 4.22. The gradient of with respect to is . Setting the sum of the two to zero gives Equation 4.25. Solving for gives Equation 4.26, because is invertible for every , and at when the columns of are independent, as in the demos.
Going deeper: why the pseudoinverse is not always unique
This example is added here. Take and . Every point with gives residual , so all of them minimize . The pseudoinverse picks the shortest of them, .
Challenge +8 XPMove the multiplier by hand until the length of the solution is within 0.005 of 1, with the multiplier above zero. The slider steps by 0.005; the jump button does not count.
Finding the multiplier by gradient ascent
How large must be? Equation 4.24 maximizes over , so we climb the Lagrangian in that variable. Its slope with respect to is read straight off Equation 4.23:
Click any coloured symbol to see what it means.
When the length of exceeds 1 the slope is positive, so going uphill means increasing . A larger adds more penalty on , and Equation 4.26 then gives a shorter .
Predict first. At the start the multiplier is 0 and the solution is too long. Which way does the multiplier move?
The book gives the rule in words: increase while the length of exceeds 1, and stop when the length is 1 and the slope is 0. The case of a length below 1 is added here. The slope is then negative, but may not go below 0, so the update below holds it at 0.
The update is added here too, with step size . The book describes the idea but gives no formula:
Click any coloured symbol to see what it means.
Solve for the solution, then adjust the multiplier
solution after each roundlength of the solutionthe length 1 allowedexact answer
Each round solves Equation 4.26 for the current , then moves by the update above. The length of creeps down to 1 and settles at the exact value. A small step needs many rounds, and a large one may overshoot. With the target at its default size the update settles for every step up to about 1.21. Above that, the multiplier bounces and does not settle.
Going deeper: the stability limit of the update
This analysis is added here. Let be the slope of with respect to at the exact answer . Near that answer, one round of the update multiplies the distance from by , so the update settles when . For the default target , and the limit is about 1.21. For the target scaled by 1.2 the limit is about 1.56, and for 1.5 it is about 1.98.
Challenge +8 XPChoose a step size between 0.3 and 0.6, press Run 20 rounds, and the multiplier must match the exact value to within a millionth.
Challenge +8 XPSet the step size above 1.3, press Run 20 rounds, and the length of must still be more than 0.05 away from 1.
What to take away
- Least squares minimizes (Equation 4.21), with gradient (Equation 4.22).
- Gradient descent converges when (Algorithm 4.1), so the largest eigenvalue sets the limit.
- Newton’s method reaches the lowest point in one step, because the quadratic approximation is exact.
- With , use the Lagrangian (Equation 4.23). If the pseudoinverse solution is feasible it is the answer; otherwise use Equation 4.26.
- Find by gradient ascent on the slope (Equation 4.27), and never let it go below 0.
Final quizCheck yourself
Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.
Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 4.5 (pages 96–97), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.