For gradient descent on f(x) = x^2, which learning rates converge and which diverge?

## The exact dynamics on a quadratic Quadratics are the right place to reason about step size because the iteration has a closed form. For `f(x) = x^2` the derivative is `f'(x) = 2x`, and the gradient descent update is ``` x_new = x - eta * 2 * x = (1 - 2 * eta) * x ``` Every step multiplies the iterate by the same constant `r = 1 - 2 * eta`, so after k steps `x_k = r^k * x_0`. Convergence to the minimum at zero happens exactly when `|r| < 1`, which rearranges to `0 < eta < 1`. ## The five regimes Starting from `x_0 = 1`: - **eta = 0.1** gives r = 0.8. The iterates 0.8, 0.64, 0.512 shrink monotonically and never change sign. Safe but slow. - **eta = 0.5** gives r = 0. The single step lands exactly on the minimum. On a quadratic, the ideal step is `1 / curvature`. - **eta = 0.9** gives r = -0.8. The iterates -0.8, 0.64, -0.512 overshoot the minimum every step but land closer each time. Converging, visibly oscillating. - **eta = 1.0** gives r = -1. The iterate flips between 1 and -1 forever. The loss never changes; the method is exactly on the stability boundary. - **eta = 1.1** gives r = -1.2. The iterates -1.2, 1.44, -1.728 alternate sign and grow geometrically. After twenty steps the magnitude is roughly 38, and in a real training loop this shows up as a loss that explodes to infinity or to a non-finite value within a handful of iterations. ## The general threshold The number 1 is not special — it comes from the curvature of `x^2`. Write the second derivative as L (here `f'' = 2`). Then the contraction factor is `1 - eta * L`, and the condition `|1 - eta * L| < 1` becomes ``` 0 < eta < 2 / L ``` which for L = 2 gives `eta < 1`. Two consequences worth stating in an interview. First, the stability limit is set by the largest curvature anywhere the iterates travel, not by the average one. Second, for a function whose gradient is L-Lipschitz (curvature bounded by L), the standard descent inequality gives, for a step of length eta, ``` f(x - eta * g) <= f(x) - eta * (1 - eta * L / 2) * ||g||^2 ``` so any `eta < 2 / L` guarantees the objective actually decreases at every step, and `eta = 1 / L` is the usual safe default because it maximises that guaranteed decrease. ## Reading it off a loss curve This theory translates directly into diagnosis: - Loss blowing up to a huge or non-finite value in a few steps: eta is above the threshold. Cut it by an order of magnitude, not by ten percent. - Loss falling but bouncing up and down between consecutive steps: eta is inside the range but past `1 / L`, the overshooting regime. Often still fine, sometimes worth halving. - Loss falling smoothly but painfully slowly, with the curve nearly a straight line: eta is far below the threshold and you are wasting iterations. - Loss flat from the start: either eta is minuscule or the gradient is effectively zero at the initial point. ## Tuning in practice Because the safe range depends on a curvature you usually do not know, the practical recipe is a coarse geometric ladder — try step sizes separated by factors of three or ten, run a small number of iterations of each, keep the largest one that does not blow up, then back off by a factor of two or three for margin. Note that this threshold is not a property of your problem alone: it moves if you rescale the objective (multiplying the loss by 10 multiplies every gradient by 10 and divides the safe eta by 10) or rescale the inputs, so a learning rate copied from another setup carries no guarantee. ## The trap in the question The common wrong instinct is that a smaller step size is always safer and a larger one always faster, so the trade-off is smooth. The quadratic shows it is not: behaviour changes qualitatively at `1 / L` (overshoot begins) and again at `2 / L` (divergence begins). Between those two points the method still converges while visibly oscillating, and exactly at `2 / L` it neither converges nor diverges. Being able to name those two thresholds, and derive them from a two-line calculation, is what separates a memorised answer from an understood one.