Gradient descent

You stand on a hillside in fog and want to reach the valley floor. You can only feel the slope under your feet, so you take a step downhill, feel again, and step again. Below, a ball does that on a map of a loss, four times, with four step sizes. Before you play it: which run reaches the bottom first?

Walking downhill

The picture is a map seen from above. The two numbers a model adjusts are $\theta_1$ and $\theta_2$, its parameters; on these pages $\theta$ is a parameter, never an angle. I write the pair as $\boldsymbol\theta=(\theta_1,\theta_2)$. The loss $J(\boldsymbol\theta)$ measures how wrong the model is with those parameters, and each ellipse joins the points with one value of the loss. This loss is a bowl, lowest at $(2,1)$.

The slope under the ball is the gradient, from Partial derivatives and the gradient: the arrow of the two slopes,

which points straight uphill. At the start, $(-2,3)$, it is $(-8,20)$. To go down, step the other way. One step is

Here $t$ counts the steps taken, not time, and the bold $\boldsymbol\theta_t$ is where the ball stands after $t$ steps; the plain $\theta_1$ and $\theta_2$ stay its two entries. The positive number $\eta$ (eta) is the learning rate: how far to go per unit of slope. Repeating the step is gradient descent.

Now the answer to the question. The third run, at 0.17, zig-zags across the valley and still reaches the bottom first. The first crawls and is still short after 30 steps, the second glides in, and the fourth swings wider each time and leaves the map. Every run that settles ends on the same cross. The step size changes the path, never the bottom. Drag $\eta$ from 0.01 up and find where a run first leaves the map: 0.21.

One direction first

To see why, take a bowl with one parameter, $J(\theta)=a(\theta-c)^2$ with $a>0$: lowest at $\theta=c$. Its slope is $J'(\theta)=2a(\theta-c)$, and here $\theta_t$ is the one parameter after $t$ steps, so a step gives

Every step multiplies the distance from the bottom by the same factor, $1-2a\eta$. If the factor is between −1 and 1, the distance shrinks to 0. That happens for $0<\eta<1/a$. A negative factor means the step jumps past the bottom to the other side, an overshoot. At $\eta=1/a$ the factor is −1, and the ball bounces between the same two points for ever. Beyond it the factor is below −1, and each swing is larger than the last: the run diverges.

Doubling the loss doubles $a$, so the largest safe learning rate halves. The step size and the steepness of the loss always go together.

Two directions, one step size

The bowl on the map is two one-direction bowls added together: $a=1$ along $\theta_1$ and $a=5$ along $\theta_2$. The gradient’s two entries do not mix, so each step multiplies

Both factors must lie between −1 and 1. Along $\theta_1$ that allows $\eta<1$, along $\theta_2$ only $\eta<0.2$. The more sharply curved direction sets the limit: $\eta<1/a_\text{max}=0.2$, where $a_\text{max}$ is the larger of the two. The run at 0.21 is a little past it: its factor along $\theta_2$ is −1.1, and each swing across the valley is 10 % larger than the last.

No single $\eta$ is perfect in both directions, because the two curvatures differ by a factor of 5. The best I can do is make the two factors equally small: $1-2\eta=-(1-10\eta)$ gives $\eta=1/6$, with factor $2/3$ along $\theta_1$ and $-2/3$ along $\theta_2$. The run at 0.17 is close to that: factors 0.66 and −0.7. Its zig-zag across the valley is the price of shrinking the slow direction fast. The run at 0.08 never zig-zags, but its slow factor, 0.84, leaves it behind.

The step arrow at the start also misses the bottom. The gradient is steep along $\theta_2$, where the bowl is steep, so the step points mostly across the valley rather than along it to the bottom. Steepest down is not straight to the bottom unless the bowl is round or the ball sits on one of its axes.

When to stop

Gradient descent does not know it has arrived. Three stopping rules are common, and programs often use more than one:

• the gradient is small: $\lVert\nabla J\rVert$ falls below a chosen tolerance, since at the bottom of a bowl the gradient is zero;
• the loss has stopped falling: it changes by less than a tolerance between steps;
• a budget: a fixed number of steps, whatever happens.

On a bowl there is one bottom, and every run that settles finds it. A loss with several valleys is different: the bottom a run reaches can depend on where it starts. This page keeps to bowls.

Worked example

Take the map’s bowl with $\eta=0.15$. The factors are $1-2(0.15)=0.7$ along $\theta_1$ and $1-10(0.15)=-0.5$ along $\theta_2$.

Step 0. The ball starts at $(-2,3)$, where $J=4^2+5\cdot2^2=36$ and $\nabla J=(-8,20)$.

Step 1. It moves to $(-2,3)-0.15\,(-8,20)=(-0.8,0)$, where $J=2.8^2+5\cdot1^2=12.84$.

Step 2. There $\nabla J=(-5.6,-10)$, so the ball moves to $(0.04,1.5)$, where $J=1.96^2+5\cdot0.5^2=5.0916$.

Step 3. There $\nabla J=(-3.92,5)$, so it moves to $(0.628,0.75)$, where $J=1.372^2+5\cdot0.25^2=2.1949$.

The factor rule checks every step: $\theta_1-2=-4(0.7)^t$ and $\theta_2-1=2(-0.5)^t$. So $\theta_2$ zig-zags about 1, its distance halving each time, while $\theta_1$ creeps up towards 2.

How many steps? For $\theta_1$ to come within 0.01 of 2, I need $4(0.7)^t<0.01$, that is $0.7^t<0.0025$, so $t>\ln0.0025/\ln0.7=16.8$: 17 steps. By then $\theta_2$ is within 0.0001 of 1.

The angle the step misses by. The first step points along $(8,-20)$; the bottom lies along $(4,-2)$ from the start. The cosine of the angle between them is

so the step points 41.6° (0.727 rad) away from the bottom.

One direction. With $J=(\theta-2)^2$ from $\theta=-1$: at $\eta=0.25$ the points are −1, 0.5, 1.25, 1.625, and the distance halves; at $\eta=1$ they are −1, 5, −1, 5, and the ball bounces; at $\eta=1.25$ they are −1, 6.5, −4.75, 12.125, −13.1875, 24.78, and the distance is multiplied by 1.5 each step with its sign flipping, $\theta_t-2=-3(-1.5)^t$.

Try it yourself. With $\eta=0.1$ on the map’s bowl, the factor along $\theta_2$ is 0: the first step lands on $\theta_2=1$ at once. With $\eta=0.2$ it is −1, and $\theta_2$ bounces between 3 and −1 for ever.

Where you’ll meet this

Fitting models. Nearly every model in this course is fitted by some form of gradient descent, from logistic regression to networks with many layers. The loss is rarely a perfect bowl, but the learning rate behaves as it does here.

Large least-squares problems. When a system is too large to solve by elimination, steepest descent and its relatives walk down the bowl of squared error, one matrix-vector product per step.

Adaptive filters. An echo canceller adjusts its taps a little at every sample, a small step down the bowl of squared error.

Reference card