Which way is downhill?

A machine has two knobs, set at 2 and 1, and its error reads 8; the slope there is (4, 8), and each entry says how fast the error rises when one knob turns. Move a tenth of that slope the other way — 0.4 off the first knob and 0.8 off the second — and the error falls to 2.72.

That number is a loss: a single quantity that measures how badly the machine is performing. Improving a machine means reducing its loss, and the chapter's beginner question asks how it accomplishes that reduction one step at a time; the answer begins with a measurement of the local slope. !Contours of $f(x,y)=x^2+4y^2$ near the setting $(2,1)$. The gradient $(4,8)$ points uphill and its negative points downhill; the inner product with $(-1,-1)$ is $-12$, so that arrow descends, while with $(2,-1)$ it is $0$, so that arrow runs along the level set. The dotted line to the minimum $(0,0)$ is not the downhill arrow: the steepest local step does not aim at the bottom. Arrows are scaled to fit the frame; the numbers are inner products of the unscaled vectors. The figure is schematic. Status: schematic.

A gradient assembles the partial derivatives of the loss, one for every knob, so each entry reports how rapidly the loss changes when that particular knob rotates. At the setting (2, 1) on the loss below, the first knob changes the loss at rate 4 and the second at rate 8, so the second parameter matters twice as much there. A list of two rates is also an arrow: the arrow whose two entries are those rates. The gradient indicates the direction of steepest ascent for the Euclidean ruler [S:27:234-234], and its opposite therefore indicates the direction of steepest descent, along which a sufficiently short displacement reduces the loss [S:27:234-235].

For two knobs the loss is a landscape; stand on it, and the slope underfoot supplies one arrow, pointing uphill. Every direction less than a right angle from the downhill arrow also descends, and the test is an inner product. The inner product of two arrows is the sum of the products of their matching entries.

An arrow constitutes a descent direction when the gradient dotted with it is negative [S:44:477-477]; because an inner product measures an angle, the test says the arrow makes an acute angle with the negative gradient [S:63:314-314].

At the start of the example the gradient is (4, 8), and the arrow (−1, −1) scores 4(−1) + 8(−1) = −12 and descends. The arrow (2, −1) scores 4(2) + 8(−1) = 0 and runs along the level set — the set of settings where the loss keeps one fixed value.

The second arrow changes the loss only to second order, by an amount proportional to the square of the step, and it may raise or lower the objective. The first-order information, the gradient's linear prediction, cannot distinguish the two cases. That ambiguity is where curvature enters, curvature being how fast the gradient itself changes, and the next two sections address it.

The hillside comparison breaks in one place: a hillside has two directions and a pair of feet, whereas a model can have a million knobs and no picture at all. What survives is the local test, which costs one pass through the model — one sweep over the data to compute one gradient — rather than a glance at the landscape.

Among arrows of the same length, one is special: a normalized steepest direction is the unit arrow that lowers the linear model most [S:44:489-489]. For the Euclidean ruler the winner is the negative gradient, by Cauchy–Schwarz [S:44:490-490]. Change the ruler and the winner changes. That choice defines the procedure.

Write f for the loss, θ for the setting, ∇f(θ) for its gradient at that setting, η for the step size, and t for the iteration number. The setting at the start of iteration t is θ_t, and the setting after the step is θ_{t+1}. Then

$${\theta }_{t+1}={\theta }_t-\eta \nabla f({\theta }_t).$$

That line says: from the present setting, subtract a multiple η of the gradient; the displacement has length η‖∇f(θ)‖, so it equals η only where the gradient has length one. [F01]

The step size has a name of its own: the learning rate is η, the multiplier on the gradient arrow. This chapter keeps three words apart: direction for the arrow, step size for the multiplier, and displacement for the move that results.

Worked example: take the loss

$$f(x,y)=x^2+4y^2$$

and start at the setting (2, 1). The gradient is (2x, 8y), because the derivative of x² in x is 2x and the derivative of 4y² in y is 8y. At the start it is (4, 8) and the loss is 4 + 4 = 8. Step with η = 0.1: multiply each entry of the gradient by 0.1, obtaining (0.4, 0.8), and subtract it from the setting. The new setting is (1.6, 0.2), and its loss is 2.56 + 0.16 = 2.72.

The two knobs move 0.4 and 0.8, so the displacement has length √(0.4² + 0.8²) = 0.894, not 0.1; the step size is a multiplier on the gradient, not a distance.

The step lowered the loss by 5.28, and a second iteration repeats the arithmetic: the gradient at (1.6, 0.2) is (3.2, 1.6), so the setting moves to (1.28, 0.04) and the loss becomes 1.6384 + 0.0064 = 1.6448. Both updates reduce the objective, though neither reaches the minimiser — the setting where the loss is smallest — which is (0, 0), and nothing in the direction test indicates how many iterations are required.

The idea has a sharp edge. A descent direction promises a decrease only for a multiplier small enough that the first-order term, the linear part of the change, dominates the squared part, and it says nothing about how small that is. At a flat point the gradient is zero, so the test is silent in every direction, including directions that descend, and the next section supplies the missing number: a bound on how large the multiplier may be.

The formal statement. Let $f:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable at $\theta$. The gradient $\nabla f(\theta )$ collects the partial derivatives, one per coordinate. For a vector $\Delta \theta$, the directional derivative of $f$ at $\theta$ along $\Delta \theta$ is the inner product $\nabla f(\theta {)}^{\top }\Delta \theta$. Call $\Delta \theta$ a descent direction at $\theta$ when that inner product is negative [S:44:477-477]. The theorem reads: if $\nabla f(\theta {)}^{\top }\Delta \theta <0$, then $f(\theta +\eta \Delta \theta )<f(\theta )$ for every positive $\eta$ below some threshold. The one hypothesis is differentiability at $\theta$. The loss need not be convex, smooth or bounded below.

The derivation. Differentiability at $\theta$ means

$$f(\theta +\eta \Delta \theta )=f(\theta )+\eta \nabla f(\theta {)}^{\top }\Delta \theta +o(\eta ).$$

The display says that a step changes the loss by the directional derivative times the step length, plus a remainder that vanishes faster than the step. Subtract $f(\theta )$, divide by $\eta$, and let $\eta$ shrink to zero. The quotient tends to the directional derivative, and a quantity with a negative limit is negative for all small enough $\eta$. That is the whole proof. The little-$o$ remainder is the definition of the derivative, so no step is omitted.

The steepest choice follows from the same inner product. Let $u$ be a unit vector and $\phi$ the angle between $u$ and the gradient. Then

$$\nabla f(\theta {)}^{\top }u=\Vert \nabla f(\theta )\Vert \Vert u\Vert \cos \phi .$$

The display says that, among arrows of length one, the score depends on the angle alone. It is smallest at $\cos \phi =-1$, so $u=-\nabla f(\theta )/\Vert \nabla f(\theta )\Vert$ wins with value $-\Vert \nabla f(\theta )\Vert$. Cauchy–Schwarz gives the same bound, with equality exactly when the two vectors are parallel.

The edge case. Steepest needs a ruler. Boyd and Vandenberghe define the steepest direction with respect to any norm, as the unit vector in that norm that lowers the linear model most [S:44:489-489]. Change the ruler and the arrow changes. Under the quadratic norm $\Vert z{\Vert }_P=(z^{\top }Pz{)}^{1/2}$ the steepest step is $-P^{-1}\nabla f(\theta )$ rather than $-\nabla f(\theta )$ [S:44:490-490]. The core names the Euclidean ruler; change it and the arrow changes. That is not a technicality: choosing $P$ is choosing a preconditioner, and section 17.4 shows how much the choice can matter.

What the core hid. The core wrote that a small multiplier lowers the loss and left "small" unquantified. The theorem gives existence, not a size. The threshold depends on the curvature and on the direction, and the first-order test cannot estimate it. At $(2,1)$ on $x^2+4y^2$ the multiplier of $0.1$ works because the curvature is mild there. A sharper loss can turn the same multiplier into an overshoot, which is what section 17.3 quantifies.

Where the analogy breaks. A hillside arrives with a ruler, because distance is measured in the plane, and the picture assumes that this is the only ruler there is. A loss comes with no ruler, and the norm changes the steepest arrow, as the quadratic norm shows. The picture also suggests that a flat spot is safe ground. At a saddle the gradient is zero, the test is silent, and the loss still falls along the directions of negative curvature.

Original sources. The iteration is Cauchy's. Prince dates gradient descent to Cauchy in 1847 and stochastic gradient descent to Robbins and Monro in 1951 [S:74:105-105]. Bubeck opens his chapter with the same attribution and writes the update in the form this chapter uses [S:43:35-35]. The descent-direction test appears as a definition in Boyd and Vandenberghe [S:44:477-477] and in Murphy [S:63:314-314], and both agree with the inner-product form in the core.

An open question. The field has settled that the negative gradient is the steepest direction for a fixed ruler. It has not settled which ruler to use. The steepest direction is defined relative to a norm, and a quadratic norm turns it into $-P^{-1}\nabla f$ [S:44:490-490]. The dual norm also sets the length of the unnormalized steepest step, so the choice of ruler changes both the arrow and its length. The question then becomes how to build $P$. Bach calls the search for a good change of variables the main principle behind preconditioning [S:77:139-140]. Evidence that would settle a proposed $P$: a fixed set of problems, the condition number measured before and after the change, and a wall-clock count to a fixed accuracy that includes the cost of building $P$.

A frontier result. AdaGrad builds the ruler from the run itself. It replaces the missing diagonal of the Hessian with the accumulated squared gradient, one scale per coordinate [S:69:561-561], and its effective step falls like $t^{-1/2}$ on each coordinate [S:69:562-562]. The method needs no estimate of $L$ and no matrix of second derivatives, so its cost per step stays linear in the number of knobs.

What to read next. Read Bubeck's chapter 3 for the dimension-free argument [S:43:35-35], Boyd and Vandenberghe section 9.4 for steepest descent under an arbitrary norm [S:44:489-489], and Bach section 5.2.5 for preconditioning as a change of variables [S:77:139-140]. Then read the AdaGrad section of Dive into Deep Learning for the per-coordinate version [S:69:562-562].