The learning rate at which descent stops converging

STATEMENT

Find the exact learning rate above which gradient descent diverges on a quadratic, then run descent either side of it. Show that the boundary is not a gradual degradation but a change of sign in an exponent.

GIVEN

A quadratic loss with a diagonal Hessian:

with the optimum at the origin and the starting point $\vec{\theta}_0 = (1, 1)$.

FIND

The stability threshold; the condition number; the error norm after 1, 5, 10, 50 and 100 steps at $\eta \in \{0.01,\ 0.09,\ 0.0990,\ 0.11,\ 0.2\}$; the per-step multiplier in each eigendirection at $\eta = 0.09$ and $\eta = 0.11$; and the optimal rate with its contraction factor.

STRATEGY

Because the Hessian is diagonal the two coordinates never interact, so the iteration is two independent scalar recurrences. Each is multiplied by a fixed number every step, and a geometric sequence converges exactly when that number is below one in magnitude. The whole problem reduces to that comparison.

SOLUTION

Step 1 — the recurrence. Substituting $\nabla\mathcal{L} = \mat{H}\vec{\theta}$ into (I.7.1):

which is (I.7.3). In the eigenbasis — here the coordinate axes — each component is multiplied by $1 - \eta\lambda_i$ every step.

Step 2 — the threshold. A geometric sequence converges when $|1 - \eta\lambda| < 1$, that is $0 < \eta < 2/\lambda$. Every coordinate must converge, so the binding constraint is the largest eigenvalue:

The condition number is $\kappa = 20/0.2 = 100$.

Step 3 — either side of it. Error norms:

Step 4 — why the boundary is sharp. The multipliers:

A two-percent change in $\eta$ moves the steep multiplier from $0.8$ to $1.2$. Both are close to one; the difference is which side. Raised to the hundredth power, $0.8^{100} \approx 2 \times 10^{-10}$ and $1.2^{100} \approx 8 \times 10^{7}$ — seventeen orders of magnitude apart, from a rate difference of two percent.

Note also that the flat direction converges in both rows. Divergence is entirely the steep direction’s doing, and it is invisible in the flat one.

Step 5 — the best a scalar rate can do. Minimising $\max_i |1 - \eta\lambda_i|$ balances the two extremes, giving

which is (I.7.4). At that rate the error shrinks by a factor of a thousand in 346 steps — for a two-dimensional quadratic with an exactly known Hessian. The slowness is not the algorithm being poorly implemented; it is $\kappa = 100$ being charged for.

Check — sanity

The smallest rate is not the safest choice. At $\eta = 0.01$ the error after 100 steps is $0.8186$ — barely moved, and worse than $\eta = 0.09$ by a factor of five. Stability and progress are different requirements, and satisfying the first with room to spare fails the second.

$\eta = 0.0990$ is worse than $\eta = 0.09$ at $t = 100$. $0.1914$ against $0.1626$, even though $0.0990$ is the theoretical optimum. The optimum minimises the asymptotic rate, and at 100 steps the iteration has not reached its asymptote: the larger multiplier in the steep direction is still costing more than the smaller one in the flat direction is saving.

The threshold uses $\lambda_{\max}$ and the rate uses both. Stability is decided by the steepest direction alone; speed is decided by their ratio. Two different eigenvalues answering two different questions, which is why quoting a single “curvature” for a model explains neither.