Gradient descent

The slope and the derivative

To measure the slope of a curve $L(w)$ at a point, you move the weight by a small amount $\varepsilon$ and divide the change in the error by that move:

The derivative $L'(w)$ is the value that ratio approaches as $\varepsilon$ gets smaller and smaller. That is why $L(w+\varepsilon)\approx L(w)+\varepsilon\,L'(w)$: the derivative says how to scale a small change in the weight to get the change in the error, and it is the slope of the tangent line at that point (Goodfellow et al., 2016, §4.3).

In the lesson, $L(w)=\tfrac12(w-3)^2+1$, so $L'(w)=w-3$. At $w=-1$, with $\varepsilon=0.1$ the error goes from 9 to 8.605 and the ratio is $-0.395/0.1=-3.95$; with $\varepsilon=0.01$, $-3.995$; in the limit, $-4$. On this curve the ratio is exactly $(w-3)+\varepsilon/2$. At weight 6 the derivative is $+3$, and at 3, the bottom, it is $0$.

A word on names: in lesson 3, the weight $w$ was the slope of the model’s line. Here the slope is a different one: that of the error curve with respect to the weight. And in practice nobody probes with an $\varepsilon$: the derivative is computed with exact formulas and, in a deep network, with backpropagation (lesson 8).

The update rule

With one weight, gradient descent repeats

where $\eta>0$ is the learning rate. Since $L(w-\varepsilon\,\text{sign}(L'(w)))$ is less than $L(w)$ for small enough $\varepsilon$, moving in small steps with the opposite sign of the derivative brings the error down (Goodfellow et al., 2016, §4.3). In the lesson, with $\eta=0.5$: $-1 \to 1 \to 2 \to 2.5 \to 2.75 \to \dots$ The distance to the bottom halves at every step, and the steps (2, 1, 0.5, 0.25, …) shorten on their own because the slope flattens.

With many weights, $\mathbf{w}=(w_1,\dots,w_n)$, each partial derivative $\partial L/\partial w_i$ measures how the error changes when only $w_i$ increases, and the gradient is the vector that contains them all:

The gradient points uphill because, among all directions of length 1, it is the one that makes $L$ grow fastest; that is why we subtract it (Goodfellow et al., 2016, §4.3).

The method is credited to Cauchy, who presented it at the 18 October 1847 session of the Paris Academy of Sciences to solve systems of equations: he replaced the system with a single equation, the sum of the squares set to zero, and made that function go down step by step. He set the step size by solving an equation in one variable or by taking a “sufficiently small” value (Cauchy, 1847; Lemaréchal, 2012).

Why there is a threshold for the rate

For a one-variable quadratic error, $L(w)=\tfrac{h}{2}(w-w^*)^2 + c$ with curvature $h>0$, the gradient is $h\,(w-w^*)$ and the distance to the bottom is multiplied by a constant factor at each step:

• if $0<\eta h<1$, the weight approaches the bottom without crossing it;
• if $\eta h=1$, it reaches the bottom in one jump;
• if $1<\eta h<2$, it crosses at every step but converges (it oscillates);
• if $\eta h=2$, it bounces between two points at the same distance from the bottom, without getting closer;
• if $\eta h>2$, the distance grows at every step: it diverges.

This is the classic analysis of LeCun et al. (1998, §5.1): the optimal one-variable rate is $1/h$, and it diverges if the rate exceeds twice the optimal one. In the lesson $h=1$. The four rates in the scene are a slow case (0.05: after 12 steps it is still 2.16 from the bottom, which was 4 away), one that oscillates (1.7: it crosses the bottom at every step but gets closer), one that diverges (2.05: each jump lands farther away and the error goes from 9 to 12.82 in 4 steps), and a good one (0.8: within 0.03 of the bottom in 3 steps). The interactive turn asks you to get within 0.08 of the bottom in ten steps or fewer without crossing it: rates from 0.33 to 1 do it.

A very small rate is not entirely harmless in a real network: besides being slow, it can leave training stuck at a high error, an effect that would not happen with a convex function and that is poorly understood (Goodfellow et al., 2016, §11.4.1).

Several dimensions: conditioning

In several dimensions the curvature is the Hessian matrix $H$. For a quadratic, $\mathbf{w}_{t+1}-\mathbf{w}^*=(I-\eta H)(\mathbf{w}_t-\mathbf{w}^*)$: along each eigendirection the distance is multiplied by $1-\eta\lambda_i$. Convergence needs $\eta<2/\lambda_{\max}(H)$ (LeCun et al., 1998), but progress along the flattest direction depends on $\lambda_{\min}$. With a large condition number $\kappa=\lambda_{\max}/\lambda_{\min}$, the error falls slowly and the path zigzags, as in the figure. With the best fixed rate ($\eta = 2/(\lambda_{\max}+\lambda_{\min})$) the distance to the bottom shrinks by a factor of $(\kappa-1)/(\kappa+1)$ per step (Goh, 2017).

In the figure, $\lambda_{\min}=1$ and $\lambda_{\max}=7$ ($\kappa=7$), and $\eta=0.2$: along the flat direction the distance is multiplied by $0.8$ at every step, and along the steep one by $-0.4$ (it switches sides: the zigzag). The best fixed rate would be $0.25$, with factor $0.75$. At the starting point, $(-1, 0)$, the two slopes are $-6.24$ and $7.80$: the gradient $(-6.24,\ 7.80)$ points up and to the left, uphill, and the path heads down and to the right.

Real landscapes

The curves in the lesson are toys: $L(w)=\tfrac12(w-3)^2+1$, the two-weight bowl with curvatures 1 and 7, and $R(w)=0.08w^4-0.6w^2+0.25w+2$, with two valleys whose minimum errors are 0.38 and 1.35. The error of a real network is not convex: it has local minima, plateaus, and saddle points (zero gradient, but it goes down in one direction and up in another). In large networks it is now suspected that most local minima have an error close to the best one, and that plateaus and saddle points get in the way more than bad minima do (Goodfellow et al., 2016, §8.2; Dauphin et al., 2014). The starting point matters: it can decide whether training converges, at what cost, and with what ability to generalize (Goodfellow et al., 2016, §8.4), and changing only the random seed can give very different results, as when fine-tuning BERT (Dodge et al., 2020).

In code

def descent(slope, w0, eta, steps):
    w = w0
    history = [w]
    for _ in range(steps):
        w = w - eta * slope(w)   # new weight = current weight − rate × slope
        history.append(w)
    return history

# error L(w) = 0.5 * (w - 3)**2 + 1  ->  slope (derivative): w - 3
print(descent(lambda w: w - 3, w0=-1.0, eta=0.5, steps=5))
# [-1.0, 1.0, 2.0, 2.5, 2.75, 2.875]

What comes next

In real models the gradient is computed on a subset of the data (stochastic gradient descent; Bottou et al., 2018) and optimizers such as Adam are used (Kingma and Ba, 2015); both appear in lesson 9. This is how GPT-3 (175 billion weights) was trained: with Adam, batches of up to 3.2 million tokens and, for the large model, a learning rate of $6\times 10^{-5}$ with warm-up and gradual decay (Brown et al., 2020, table 2.1 and appendix B). The efficient computation of $\nabla L$ in deep networks is backpropagation (lesson 8).