Deriving the threshold and the optimal rate

STATEMENT

Derive, from the update rule alone, the exact condition under which gradient descent converges on a quadratic, the learning rate that converges fastest, and the rate it achieves. The numbers of I.7.B01 should fall out as one instance.

GIVEN

$\mathcal{L}(\vec{\theta}) = \tfrac{1}{2}(\vec{\theta} - \vec{\theta}^*)^{\mathsf{T}}\mat{H}(\vec{\theta} - \vec{\theta}^*)$ with $\mat{H}$ symmetric positive definite, eigenvalues $0 < \lambda_{\min} = \lambda_1 \le \dots \le \lambda_n = \lambda_{\max}$.

FIND

The error recurrence; the condition on $\eta$ for convergence; the $\eta$ minimising the worst-case per-step contraction; and that contraction in terms of $\kappa = \lambda_{\max}/\lambda_{\min}$.

STRATEGY

Change coordinates so the problem falls apart. $\mat{H}$ is symmetric, so it has an orthonormal eigenbasis; written in that basis the update decouples into $n$ independent scalar recurrences, and a scalar geometric sequence is something whose convergence can simply be read off.

SOLUTION

Step 1 — the error recurrence. The gradient is $\nabla\mathcal{L} = \mat{H}(\vec{\theta} - \vec{\theta}^*)$. Writing $\vec{e}_t = \vec{\theta}_t - \vec{\theta}^*$ and substituting into (I.7.1):

so after $t$ steps $\vec{e}_t = (\mat{I} - \eta\mat{H})^t \vec{e}_0$. The whole trajectory is one matrix raised to a power.

Step 2 — decouple. $\mat{H} = \mat{Q}\Lambda\mat{Q}^{\mathsf{T}}$ with $\mat{Q}$ orthogonal. Since $\mat{I} - \eta\mat{H} = \mat{Q}(\mat{I} - \eta\Lambda)\mat{Q}^{\mathsf{T}}$ and $\mat{Q}^{\mathsf{T}}\mat{Q} = \mat{I}$, powers pass straight through:

In the rotated coordinates $\tilde{\vec{e}} = \mat{Q}^{\mathsf{T}}\vec{e}$ the recurrence is $n$ separate scalar ones:

The directions do not interact. This is why one badly served direction cannot be rescued by another going well.

Step 3 — convergence. $(1 - \eta\lambda_i)^t \to 0$ exactly when $|1 - \eta\lambda_i| < 1$, that is $0 < \eta < 2/\lambda_i$. Every direction must converge, so the smallest of those bounds binds:

The condition is necessary as well as sufficient — above it the component along $\vec{q}_{\max}$ grows geometrically, and no other direction can offset that.

Step 4 — the fastest rate. Asymptotically the slowest-decaying component dominates, so the quantity to minimise is

Each $|1 - \eta\lambda_i|$ is a V-shaped function of $\eta$ with its minimum at $1/\lambda_i$. The maximum over $i$ is attained at one of the two extreme eigenvalues: for small $\eta$ by $1 - \eta\lambda_{\min}$, which decreases, and for large $\eta$ by $\eta\lambda_{\max} - 1$, which increases. The minimum of the maximum is where they cross:

Step 5 — the rate. Substituting back:

which is (I.7.4). Dividing through by $\lambda_{\min}$ is what turns two eigenvalues into one ratio: only the shape of the problem matters, not its scale.

Step 6 — check against I.7.B01. With $\lambda = (20, 0.2)$: $\eta^* = 2/20.2 = 0.0990099$ and $\rho = 99/101 = 0.980198$, matching the measured values exactly.

Check — sanity

$\kappa = 1$ gives $\rho = 0$. A perfectly conditioned quadratic is solved in a single step, and the formula says so: $\eta^* = 1/\lambda$ lands exactly on the optimum. Any correct derivation must reproduce this.

$\kappa \to \infty$ gives $\rho \to 1$. Progress per step vanishes as the problem stiffens, which is the behaviour to expect and the reason the ratio rather than either eigenvalue is the quantity of interest.

$\eta^*$ lies strictly inside the stability interval. $2/(\lambda_{\max} + \lambda_{\min}) < 2/\lambda_{\max}$ since $\lambda_{\min} > 0$. The optimum is never on the boundary, which is worth knowing: a rate tuned to the edge of stability is not the fast one.