A First Taste of Algorithms · Learning as an Algorithm

The two valleys

On a bowl, greedy-in-continuous-space is provably perfect: one valley, every downhill road leads there. Now tilt the world. The lab’s landscape f(x) = x⁴ − 3x² + x has two valleys — a deep one near x = −1.30 (floor at −3.51) and a shallow one near x = 1.13 (floor at −1.07) — separated by a hilltop near x = 0.17.

Start the descent at x₀ = −0.5: it walks left, settles at −1.30, the true bottom. Start at x₀ = +0.5 — a coin’s width across the hilltop — and it walks right, settles into the shallow valley, and stays there at −1.07, forever, reporting success. Every local test the algorithm can perform says it is finished: the ground is flat, every direction is uphill. It cannot see the better valley two units to the left, because it has never had anything but the ground under its feet.

Figure 8.3 — Two valleys, two destinies: from −0.5 the walk finds the deep floor; from +0.5 it commits into the shallow valley and pronounces itself done. Start decides everything; the walker never knows.

You have seen this exact failure before, and the recognition is the point of the whole book’s architecture. The shallow valley is the grab-the-10 valley. The deep one is the 7 + 7 valley. Gradient descent at +0.5 is Sevenia’s cashier: the locally best move, committed, mortgaging a better future it never priced. Chapter 2 diagnosed the disease; Chapter 4 cured it — price every branch, then choose — and here is the bitter pill: the cure is unavailable. The table method needs listable questions, and a landscape’s points cannot be listed. The notebook that healed Sevenia cannot be opened on a continuum. So modern practice lives with greedy and manages its valleys the way you’d guess once you say it out loud: descend from several random starts and keep the best (Chapter 7’s move — when cleverness is unavailable, honest dice); jitter the steps with noise so shallow valleys can be stumbled out of; and lean on a strange empirical mercy — in the absurdly high-dimensional landscapes of real models, valleys seem to behave differently than our 1-D pictures suggest, in ways that are genuinely, actively, not understood. That last clause is not a textbook hedge. It is the honest edge of the field, and the deep water says more.

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