A First Taste of Algorithms · Problem Set 8

Concept & Counterexample

3.1 Claim: “gradient descent finds the minimum of any function if you run it long enough.” Refute three ways with this chapter’s own objects: a landscape where it provably converges to the wrong place; a starting point on the two-valley landscape where it never moves at all (find it exactly — what equation does that point satisfy, and is it a minimum?); and a stride for which it diverges on even the friendliest bowl.

3.2 Claim: “smaller learning rates are always safer, so when in doubt, shrink η.” Half true. State the half that’s true (what catastrophe does shrinking rule out, by the Diamond’s law?) and refute the “always safer” half with a budget argument: with 100 steps allowed on the bowl from x₀ = 2, compare where η = 0.001 and η = 0.25 each end up. Safety from explosion is not safety from failure; name the failure mode the timid stride commits.

3.3 Claim: “nearest neighbor doesn’t really learn — it just memorizes.” Defend both sides with one lab measurement each: the sense in which the claim is exactly right (which score is always perfect, and why is that score therefore worthless?), and the sense in which it’s wrong (which score can nonetheless be genuinely good, and what does that prove transferred?). Conclude with the sentence this chapter would write on the matter.

3.4 Claim: “with squared loss, one wildly wrong example among a thousand barely matters — it’s just one term in an average.” Compute the refutation: examples (1, 1), (2, 2), (3, 3) plus the typo (1, 100). Find the best slope with and without the typo (use 1.3’s gradient set to zero, or argue directly), and report how far one liar dragged the line. Then connect: which of the three honest reasons for squaring from the chapter is also this vulnerability’s cause, and what does the trade-off teach about choosing losses?

3.5 Claim: “the train/test split is bureaucracy — if the model fits all available data well, it has learned the pattern.” Build the counterexample in miniature: invent a learner (nearest neighbor will do) and a dataset where the training score is perfect, the test score is coin-flip, and you can say exactly what the learner actually “learned.” (Hint: label your points by a fair coin and see what perfect memorization of noise looks like under honest examination.)

All 32 chapters of A First Taste of Algorithms · Foundations · All courses