The Slowest Direction Sets the Pace

Fit a quadratic curve to a hundred points with gradient descent. Nothing exotic: the design matrix has columns $1$, $t$ and $t^2$ for $t$ evenly spaced on $[0, 1]$, the loss is squared error, the step size is the best constant one for this problem, and the run stops when the loss is within $10^{-6}$ of its minimum, relative to where it started.

It takes 1742 steps.

Now centre and scale the two non-constant columns. Same data, same fit, same minimum. 147 steps.

Now replace the three columns with an orthonormal basis for the same span, which a QR factorisation produces in one call. 1 step.

All three land on the same answer. The residual sums of squares agree to ten decimal places at $0.1936196358$, and the fitted values agree to $1.8 \times 10^{-15}$, because the three bases span the same space and least squares does not care which one you hand it. The optimiser does.

A. Where the ratio comes from

For a quadratic loss with Hessian $H$, everything is set by two eigenvalues: the largest, $L$, and the smallest, $m$.

$L$ limits the step size. Take a step larger than $2/L$ along the steepest eigenvector and the iterate overshoots to somewhere worse than it started; the run diverges.

$m$ limits the progress. Along the flattest eigenvector the gradient is small, so a step of the allowed size moves you very little.

You are forced to a step size set by the steepest direction and then have to cross the flattest one with it. With the optimal constant step size $\alpha = 2 / (L + m)$, the error falls by a factor of

$$\frac{\kappa - 1}{\kappa + 1}, \qquad \kappa = \frac{L}{m},$$

per step, so the number of steps to a fixed accuracy is proportional to $\kappa$, the condition number. Nothing about how deep the bowl is appears anywhere. A loss can be enormous and easy, or tiny and hard.

For a clean check, take a two-dimensional quadratic with eigenvalues 1 and 100. The formula predicts $\lceil \log 10^{-6} / \log(99/101) \rceil = 691$ steps to bring the distance to the optimum down by a factor of $10^{-6}$. Running it takes 691. (Count on the loss instead and you get half of that, because the loss is the distance squared. The rate describes the distance.)

B. The three bases, measured

The conditioning of the three designs above, and what each costs:

The first row is not a pathological design. It is the obvious way to write a quadratic fit, on a tidy interval, with no outliers and no collinearity worth the name. The columns $1$, $t$ and $t^2$ simply point in similar directions on $[0,1]$: all three are positive and increasing across most of the range, so the Hessian is far from a multiple of the identity.

The last row is the limiting case worth holding on to. When $\kappa = 1$ the allowed step size is exactly right for every direction at once, and gradient descent with $\alpha = 1/L$ reaches the minimum of a quadratic in a single step. All the iteration in the first row is the optimiser working around a choice of coordinates.

C. What momentum buys, and what it does not

Heavy-ball momentum adds the previous update to the current one. On a quadratic, tuned optimally, its asymptotic rate is

$$\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1},$$

which replaces $\kappa$ by $\sqrt{\kappa}$ in the step count. On the $\kappa = 100$ problem above that predicts 69 steps against gradient descent's 691, and a run measures 93 - slower than the asymptotic bound because the bound describes the tail rather than the transient, but still a factor of 7.43 on the same problem under the same stopping rule.

The figure opens at a condition number of 23.841. Drag it to 100 and plain gradient descent needs 691 steps, as above, while momentum needs 90 from the figure's starting point against 93 from the one used here: step counts depend on where a run starts, and convergence rates do not.

The square root is the whole benefit, and it is worth being precise about what that means. Momentum does not fix conditioning; it takes the cost from $\kappa$ to $\sqrt{\kappa}$. On $\kappa = 10^4$ that is the difference between hopeless and slow, not between slow and fast. It also introduces a second hyperparameter whose optimal value depends on $\kappa$, which you do not know.

Rescaling, where it is available, is strictly better: it changes $\kappa$ itself, costs one pass over the data, and has no tuning.

D. Why this is everywhere

Once you are looking for the ratio rather than the depth, a lot of standard practice stops looking like folklore.

• Standardising inputs is conditioning work. Rewriting one feature from kilometres into millimetres multiplies its column by $10^6$ and its entry in $X^{\top}X$ by $10^{12}$, and that factor lands directly in $\kappa$.
• Adaptive methods such as RMSProp and Adam maintain a per-coordinate step size, which is a diagonal preconditioner: an attempt to equalise the eigenvalues cheaply, using only the information a diagonal can carry.
• Normalisation layers keep activations on a comparable scale as the network trains, which keeps the Hessian from drifting into a bad ratio part way through a run.
• Residual connections shorten the path a gradient takes, which keeps the spread of curvature across depth from compounding.

None of these makes the loss smaller. They all make the same loss cheaper to descend, which is a different thing and, on the evidence of the table above, often the larger factor by far.