Gradient descent

Walking downhill

Lesson 4.4.1 found minima by solving $\nabla f = \mathbf{0}$. Usually that equation has no formula, so the computer walks downhill instead. Lesson 4.2.1 showed that $-\nabla f$ is the direction in which $f$ falls fastest.

$\eta$ has the units that make $\eta\nabla f$ a distance in the units of $\mathbf{x}$. Doubling $\eta$ doubles every step.

Take $f(x, y) = x^2 + xy + y^2 - 3x$ of lesson 4.4.1, with minimum $(2, -1)$ and gradient $(2x + y - 3,\ x + 2y)$. From $(0, 1)$ the gradient is $(-2, 2)$. With $\eta = 0.3$ the first step goes to $(0, 1) - 0.3(-2, 2) = (0.6, 0.4)$, where $f = -1.04$.

$f$ falls at every step, towards $-3$. Each distance is 0.7 times the one before; the next section explains that number. After 42 steps, $\lVert\nabla f\rVert$ is below $10^{-6}$.

How large a step?

One variable

Take $f(x) = 2x^2$, with its minimum at 0 and slope $f'(x) = 4x$. One step gives $x - \eta \cdot 4x = (1 - 4\eta)x$: each step multiplies $x$ by the same factor $1 - 4\eta$. From $x_0 = 1$:

A small step creeps towards 0 from one side. At 0.25 one step lands on the minimum.

At 0.45 every step overshoots to the other side but still gets closer. At 0.55 each overshoot is larger than the last: the method diverges.

The steps close in on 0 exactly when the factor lies between $-1$ and 1, that is, when $0 < \eta < 0.5$; past $\eta = 0.25$ they overshoot. The 4 in $1 - 4\eta$ is $f''$, the curvature (lesson 2.4.2). So a curve that bends more allows only a smaller step: the limit is $\eta < 2/f''$.

Several variables: one factor per eigenvector

For a quadratic $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x}$ with minimiser $\mathbf{x}^*$, lesson 4.4.1 gave $\nabla f = A\mathbf{x} - \mathbf{b} = A(\mathbf{x} - \mathbf{x}^*)$. Write $\mathbf{e}_k = \mathbf{x}_k - \mathbf{x}^*$ for the error. Then one step is

Along a unit eigenvector $\mathbf{q}_i$ of $A$, with eigenvalue $\lambda_i$, $(I - \eta A)\mathbf{q}_i = (1 - \eta\lambda_i)\mathbf{q}_i$ (lesson 3.6.1). So the part of the error along each eigenvector is multiplied by its own factor $1 - \eta\lambda_i$ at every step, as in one variable.

For $x^2 + xy + y^2 - 3x$, $A$ has eigenvalue 3 along $(1, 1)$ and 1 along $(1, -1)$ (lesson 3.6.3). So the limit is $\eta < 2/3$. From $(0, 1)$ the error $(-2, 2)$ lies along $(1, -1)$, which is why it shrank by exactly $1 - 0.3 \times 1 = 0.7$ per step.

From $(0, 0)$ the error $(-2, 1)$ has a part along each eigenvector. Steps until $\lVert\nabla f\rVert < 10^{-6}$:

Too small is slow, because the factor along $(1, -1)$ is close to 1. Too large is slow too, because the factor along $(1, 1)$ is close to $-1$, and past $2/3$ it diverges. The best fixed step, $\eta = 2/(\lambda_{\max} + \lambda_{\min}) = 0.5$, makes the two factors the same size.

At $\eta = 0.7$ the part of the error along $(1, 1)$ goes $-0.7071$, 0.7778, $-0.8556$, 0.9412: it grows by 1.1 each step and flips sign. $f$ first falls to $-1.89$, then climbs, reaching $-0.1519$ after seven steps, and goes on rising.

Long narrow valleys

The ratio $\kappa = \lambda_{\max}/\lambda_{\min}$ of a positive definite $A$ is its condition number (lesson 3.3.2). It measures how stretched the bowl is: the level curves are ellipses whose axes have lengths in the ratio $\sqrt{\kappa}$ (lesson 3.7.1). With the best fixed step, the slowest factor is

which is 0.5 for $\kappa = 3$, 0.8182 for $\kappa = 10$, and close to 1 for a large $\kappa$.

Take $f(x, y) = x^2 + 10y^2$, with Hessian $\begin{pmatrix} 2 & 0 \\ 0 & 20 \end{pmatrix}$ and $\kappa = 10$. The limit is $\eta < 2/20 = 0.1$. From $(-4, 1)$:

At $\eta = 0.09$, $y$ flips sign at every step, 1, $-0.8$, 0.64, $-0.512$, while $x$ creeps from $-4$ to $-3.28$, $-2.6896$, $-2.2055$. The path zig-zags across the valley, as in the figure. The steep direction caps the step size, and the gentle direction pays for it.

For the round bowl $x^2 + y^2$, with $\kappa = 1$, the step $\eta = 0.5$ reaches the minimum from any start in one step. Rescaling $y$ by $\sqrt{10}$ would turn $x^2 + 10y^2$ into that bowl. Lesson 4.4.3's Newton's method does such a rescaling automatically.

A curved valley

The function $f(x, y) = (1 - x)^2 + 5(y - x^2)^2$ has a long valley along the curve $y = x^2$, with its minimum at $(1, 1)$. There the Hessian is $\begin{pmatrix} 42 & -20 \\ -20 & 10 \end{pmatrix}$, with eigenvalues 0.3875 and 51.6125, so $\kappa \approx 133$. Near the minimum, a step must stay below $2/51.6125 = 0.0388$.

From $(-1.5, 2.5)$ with $\eta = 0.02$, 1688 steps bring $\lVert\nabla f\rVert$ below $10^{-6}$. After 50 steps the point is still at $(-0.8817, 0.9382)$, crawling round the bend.

With $\eta = 0.04$, just above the limit, the path gets near $(1, 1)$ quickly but never settles. It ends up jumping between two points, 0.0539 and 0.055 from the minimum. With $\eta = 0.05$ the steps blow up within six steps.

The explorer starts on this valley at $(-1.5, 2.5)$ with step size 0.02. Set 50 steps and watch the path zig-zag across the curved floor as it creeps along. Then try 0.04, and 0.05, when the steps grow without limit.

Pick the tilted bowl $x^2 + xy + y^2 - 3x$, move the start to $(0, 0)$, and compare 0.3 with 0.6. The Newton's method switch is for lesson 4.4.3.

When to stop

The steps rarely land exactly on the minimum, so the code needs a rule for when to stop. Three tests are common, and each can mislead.

A small gradient in a flat valley. For a quadratic, the distance to the minimum is at most $\lVert\nabla f\rVert/\lambda_{\min}$. Take $f = x^2 + 0.01y^2$ at $(0, 1)$: $\nabla f = (0, 0.02)$, a small gradient, yet the minimum is 1 away. Scale the tolerance to the problem.

A small step with a small $\eta$. Each step has length $\eta\lVert\nabla f\rVert$. With $\eta = 10^{-4}$ on the bowl $x^2 + xy + y^2 - 3x$, the first step from $(0, 1)$ moves only 0.000283, far from the minimum. A step test then stops at once.

Backtracking: a step size without $\lambda_{\max}$

In practice $\lambda_{\max}$ is unknown and changes from point to point. Backtracking chooses $\eta$ afresh at each step, by trial.

The tangent plane (lesson 4.2.2) says a step $-\eta\nabla f$ lowers $f$ by about $\eta\lVert\nabla f\rVert^2$. Accept the step if $f$ really falls by at least half of that; otherwise halve $\eta$ and try again.

On the curved valley from $(-1.5, 2.5)$, backtracking needs 442 steps, against 1688 with the fixed $\eta = 0.02$. The first accepted step size is $\frac{1}{128}$, and later ones are often $\frac{1}{32}$ or $\frac{1}{64}$. Its 2017 halvings in all each cost one evaluation of $f$, so the saving is real but smaller than the step counts suggest.

Lesson 4.4.3 replaces the fixed direction $-\nabla f$ with Newton's step, which bends towards the minimum in a narrow valley. Practice set 4.4.4 asks you to write the backtracking method.

Common mistakes

1. Too large a step diverges. Past $2/\lambda_{\max}$ the error grows each step; watch that $f$ falls.
2. Too small a step only looks safe. The path creeps, and a step-length test may stop it far from the minimum.
3. The limit comes from the steepest direction. It is $2/\lambda_{\max}$, set by the largest eigenvalue, not by an average curvature.
4. A small gradient is not a small error in a flat valley: $x^2 + 0.01y^2$ has $\lVert\nabla f\rVert = 0.02$ at $(0, 1)$, a distance of 1 from the minimum.
5. A zig-zag is bad scaling, not a bug. It comes from a large condition number; rescale the variables or use Newton's method.
6. Gradient descent stops at any critical point it reaches, including a local minimum that is not global (lesson 4.4.1).
7. Always cap the number of steps, and report when the cap is reached.