Gradient descent
The map shows the height f(x, y) of a landscape as coloured bands, like contour lines: pale is low, dark is high, and the star marks the bottom. Tap anywhere to drop a ball, and watch it take steps of the form (x, y) ← (x, y) − η ∇f: each step goes straight downhill, with a length set by the step size η. Slide η. Small steps crawl. Larger steps get there faster, until the path starts to zig-zag across the valley, and a little larger still it leaves the map entirely.
Mission. On the bowl f = x² + 3y², set η = 0.30 and tap a start. It zig-zags but gets there. Now try η = 0.34. Before you do, predict: where exactly is the dividing line between settling and blowing up, and why?
Answer
η = 1/3. The y-gradient is 6y, so each step replaces y by y − 6ηy = (1 − 6η)y. That factor has size below 1 only when η < 1/3; at η = 1/3 it is exactly −1 and y bounces for ever between two values; beyond it |y| grows every step. The x-direction is gentler (factor 1 − 2η) and is still fine at η = 0.34, so the ball runs away up and down, not sideways. The zig-zag begins when 1 − 6η turns negative, at η = 1/6. Extension: the steep bowl x² + 20y² has gradient 40y in y. Predict its threshold (1/20) and test it.
What's going on
The gradient ∇f = (∂f/∂x, ∂f/∂y) points in the direction of steepest ascent, and it is perpendicular to the contour through the point. So walking against the gradient is walking straight downhill, at right angles to the bands. On a round bowl that aims directly at the bottom. On a stretched bowl like x² + 3y² it does not: the steep y-direction dominates the gradient, so the step is mostly vertical even when the bottom is mostly to the side. The path overshoots the valley floor and has to come back, which is the zig-zag.
How large a step is safe depends on the steepest curvature. Along y the bowl x² + 3y² curves like 6 (the second derivative), and a step of size η multiplies the y-error by 1 − 6η. Convergence needs |1 − 6η| < 1, so η < 1/3, a hard wall. The gentle x-direction would happily take η up to 1. The best single η has to respect the steep direction and so crawls along the gentle one. The ratio of steepest to gentlest curvature, 6/2 = 3 here, is called the condition number, and the larger it is the worse plain gradient descent does.
The banana valley is where this bites. Along the floor of the curved valley the landscape is nearly flat (curvature about 0.4 at the minimum), while across it the walls are steep (curvature about 100). Any η that survives the walls, below about 0.02, takes hundreds of steps to creep along the floor to (1, 1). Set max steps to its limit and watch it inch forward. This is the picture to have in mind whenever someone says a machine "learns" by gradient descent: it is this ball, in millions of dimensions, with the same two failure modes.
Sheet: Gradient descent.