Why does gradient descent zig-zag on an elliptical bowl with condition number 100?

## The model surface Use `f(x, y) = 0.5 * (x^2 + 100 * y^2)`. Its level sets are ellipses stretched ten times further along x than along y, and the second derivatives are 1 along x and 100 along y. The condition number of the problem — here the ratio of the largest curvature to the smallest, written kappa — is 100. This single number predicts almost everything about how gradient descent behaves on the surface. ## Why the two axes fight each other The gradient is `(x, 100 * y)`, so with a constant step size eta the update splits into two independent scalar recursions: ``` x <- (1 - eta) * x y <- (1 - 100 * eta) * y ``` Each one converges only if its multiplier has absolute value below 1. The y recursion demands `eta < 2 / 100 = 0.02`; the x recursion would happily accept anything up to `eta < 2`. A single shared eta must satisfy the stricter constraint, so the steepest direction sets the ceiling and the flattest direction pays for it. Pick `eta = 0.019`, just inside the limit. Then the y multiplier is `1 - 1.9 = -0.9`: y alternates sign each iteration while shrinking by ten percent — that alternation, drawn on the contour plot, is the zig-zag across the narrow valley. Meanwhile the x multiplier is `1 - 0.019 = 0.981`, so the long axis shrinks by under two percent per iteration. Reducing x by a factor of a thousand takes roughly 360 iterations. The picture is a path that rattles rapidly from wall to wall while inching toward the far end. ## The rate in terms of kappa For a quadratic with smallest curvature mu and largest curvature L, the best constant step size is `2 / (L + mu)`, and the distance to the optimum then contracts by a factor `(kappa - 1) / (kappa + 1)` per iteration, where `kappa = L / mu`. With kappa = 100 that is `99 / 101`, about 0.980 per step. Because `(kappa - 1) / (kappa + 1)` is approximately `1 - 2 / kappa`, the number of iterations for a fixed accuracy grows roughly **linearly in kappa**. Ten times more elongation, ten times more iterations. That is the headline result to be able to state. ## Curved valleys make it worse The elliptical bowl is the easy version because the valley floor is a straight line. The classic hard case is the Rosenbrock banana: a long, narrow, *curved* valley. There the direction of the shallow axis rotates as you move, so a fixed step that is safe against the local wall curvature also has to keep re-aiming along a floor that keeps bending. Descent crawls along the banana valley with many tiny zig-zag steps, and the loss curve shows a fast initial drop into the valley followed by an extremely long, nearly flat tail. Seeing that shape should make you suspect conditioning, not a bug. ## What you actually observe Three symptoms travel together: 1. The loss drops sharply for a few iterations and then flattens into a long plateau that is still, on close inspection, decreasing. 2. Some parameter traces oscillate in sign from iteration to iteration while others drift slowly and monotonically. 3. Lowering the learning rate removes the oscillation but makes the plateau even flatter — a strong signal that you are conditioning-limited rather than step-size-limited in the naive sense. ## What helps, and what does not **Shrinking eta does not fix it.** It cures the visible bouncing, but the slow direction was already the bottleneck and now moves even slower. Nothing about the ratio of the two curvatures has changed. **Rescaling the coordinates does.** The condition number is a property of the objective *as parametrised*. If the elongation comes from features measured on wildly different scales — one in units of 1 and another in units of 10,000 — standardising them so each has comparable spread pulls the curvatures toward one another and drops kappa directly. The same goes for reparametrising a variable that enters the loss with a very different sensitivity. This is why input scaling has such an outsized effect on how a first-order method trains: it is not cosmetic, it changes the geometry the algorithm has to traverse. **Reformulating the objective** can help too — for example, centring predictors so that an intercept term does not sit on a wildly different curvature from the slopes. ## The interview point The answer that scores is not just the word oscillation. It is the mechanism: one shared step size must satisfy the steepest curvature, the flattest curvature therefore converges at a rate set by the ratio, the ratio is the condition number, iteration count scales with it, and the leverage is in changing the ratio rather than in changing the step size.