Gradients in many dimensions

You stand at the point $(3,2)$ on a hill whose height is $f(x,y)=x^2+3y^2$, and the height under your feet is 21. At that point the slope east is 6 and the slope north is 12: a step of a hundredth of a unit east gains about six hundredths of height, and the same step north gains about twelve hundredths. A full unit east gains 7 and a full unit north 15, not 6 and 12, because the slopes themselves grow as you move. Check the two full steps against the function: at $(4,2)$ the height is $28$ and at $(3,3)$ it is $36$, rises of 7 and 15 from 21. So the steepest ascent is not due north and not due east, but a combination leaning north, and the two slopes at the point say how to combine them.

Each of those two rates is a partial derivative: the rate of change in one coordinate while the others stay fixed [S:27:152]. Collect the partial derivatives in one list and you have the gradient, written ∇f and pronounced grad f, and for this hill the collection is $(2x,6y)$, which at $(3,2)$ is $(6,12)$. !Contours of $x^2+3y^2$, drawn at equal height intervals, with the gradient at four points. Each arrow is perpendicular to the contour it starts on, and the arrows are longer where the contours crowd together. At $(3,2)$ the arrow is $(6,12)$: six units of height per unit east, twelve per unit north, and the steepest climb is the combination. Arrows are drawn at one plot unit per twelve units of gradient. Status: re-simulated from the formula.

!One run of gradient descent from $(3,2)$ with step size 0.3 on the same hill. The $y$ coordinate changes sign at every step, shrinking by 0.8 each time, while $x$ shrinks by 0.4. The path crosses the valley again and again and creeps along its floor, because each step follows the steepest local direction rather than the road to the bottom. Status: re-simulated from the descent rule.

That line says the gradient is the list of one-variable slopes, and the notation with the curly d marks a partial derivative rather than an ordinary one. The gradient answers the question this section asks — which way is uphill — directly: it points in the direction of steepest ascent and is perpendicular to the contour lines, the curves along which the height is constant [S:27:234]. Its length, the square root of the sum of the squares of the entries, is the rate of climb when you step one unit along it. The linear approximation says the change is the inner product of the gradient with the unit step, and that product is largest, and equal to the length, when the step points along the gradient [S:72:39]. Follow a contour line, where the height never changes, and the gradient stays perpendicular to your path.

Compute the two partial derivatives the usual way, treating $y$ as a constant and differentiating $x^2+3y^2$ in $x$, which gives $2x$. Treat $x$ as a constant and differentiate in $y$, which gives $6y$. Neither step needs new machinery, because each is the one-variable derivative from the previous section, run on a function of one letter while the other letter sits still.

A contour line collects the points where the height is a fixed number. For this hill those lines are ellipses, squeezed along the y axis because the y term grows three times faster. The gradient at a point is perpendicular to the contour through that point, and the perpendicular is the shortest route between adjacent contours. That gives a second reading of steepest ascent: it is the direction that crosses the contours fastest.

Worked example. Descend instead of climb. At $(3,2)$ the gradient is $(6,12)$, so the downhill direction is $(-6,-12)$. Take a step of 0.1 times the gradient, which moves you to $(3-0.6,2-1.2)=(2.4,0.8)$.

The height there is 7.68, against 21 at the start. One small step eliminated most of the elevation, because the displacement was scaled by the size of the gradient and the hill is steep at that point.

That is the whole of gradient descent, the optimisation algorithm behind most training in this book. Training is the process of adjusting a model's numbers so that its loss falls, and descent is the move that does the adjusting. Compute the gradient, step a little against it, and repeat, with the step size controlling the magnitude of each displacement and the gradient supplying its direction:

That line says the next position — the bold letter marks a position with several coordinates, and the subscript counts the step — is the current one minus a small multiple of the gradient. The Greek letter alpha is the step size, a positive number chosen in advance, and the algorithm stops when the gradient is small or the budget runs out.

With many inputs the picture does not change, it only gains coordinates. A model may have a million parameters, the numbers it adjusts during training, and its loss, the number that measures how wrong its outputs are, is a function of all of them at once. The gradient then has a million entries, and each entry says how much the loss moves when that one parameter moves. Training follows the same rule: subtract a small multiple of the whole list [S:27:234].

Reading a gradient takes practice. A large entry means the loss is sensitive to that coordinate; an entry near zero means the loss barely notices it, while the sign indicates which way to move and the magnitude indicates what a unit move costs. Two coordinates with very different entries mean the landscape forms an elongated valley, and a single step size cannot suit both.

Limitation. The gradient is local information, and it does not point at the minimum [S:52:164]. In an elongated quadratic valley, steepest descent zigzags across the valley rather than along it. With an exact line search each step is orthogonal to the one before, and with the fixed step size in the figure the path still crosses the floor instead of following it [S:66:284]. At a flat region the entries are near zero and the direction becomes unreliable [S:52:163]; the gradient also depends on how you scale the coordinates, so a change of units alters the direction it reports.

The formal statement. Let $f:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable at $w$. Then there is a linear map $\partial f(w)$ with

$$f(w+v)=f(w)+\partial f(w)[v]+o(\Vert v\Vert ).$$

That line says the change in $f$ is linear in the step, up to an error smaller than the step. The gradient $\nabla f(w)$ is the vector of partial derivatives [S:27:152]. Differentiability makes the directional derivative linear in the direction, so $\partial f(w)[v]=⟨v,\nabla f(w)⟩$ [S:72:37]. This book keeps the column convention: $\nabla f(w)$ is a column and the update is ${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\alpha \nabla f({\mathbf{x}}_k)$. MML writes the gradient as a $1\times n$ row vector, and its update carries a transpose; the two differ only in that bookkeeping [S:27:153]. Among unit vectors $v$, that inner product is largest at $v=\nabla f(w)/\Vert \nabla f(w)\Vert$ [S:72:39]. Three hypotheses do the work: differentiability, the Euclidean inner product, and a nonzero gradient.

The derivation. For a unit $v$, Cauchy-Schwarz gives $⟨v,\nabla f(w)⟩\le \Vert \nabla f(w)\Vert$, with equality exactly when $v$ is a positive multiple of the gradient. No unit direction climbs faster, and the gradient direction attains the bound. The length of the gradient is the rate of climb in that direction.

The edge case. Every partial derivative can exist while $f$ is not differentiable: directional derivatives in every direction do not imply differentiability [S:72:37]. The source's example is $f(x_1,x_2)=x_1^3/(x_1^2+x_2^2)$, which has directional derivatives at the origin and no derivative there. A computation that assembles the partials and calls the result a gradient can therefore report a direction that no theorem covers. The partials can agree with a formula and still fail to describe a tangent plane.

A second edge case: the ruler. Steepest depends on how you measure the step. Under the Euclidean norm the answer is $\nabla f$. Under another norm it is not, and the choice of norm changes the performance of steepest descent [S:44:510]. Under the Fisher information metric the direction becomes $F^{-1}\nabla f$, which is the natural gradient [S:106:46]. L1 used ordinary distance without naming it.

What L1 hid. L1 said the gradient points in the direction of steepest ascent as if the phrase were absolute. It is relative to the inner product. L1's landscape also had two coordinates, where a picture can show the direction. With a million parameters the statement is unchanged and the picture is unavailable.

Where the analogy breaks. The hill analogy treats the surface as fixed and the ruler as given. In training the surface is a loss over parameters, and the metric that measures a step can change with the parameters. The gradient remains the Euclidean steepest direction; it stops being the direction that makes the most progress in the units that matter.

Original sources. The partial derivative, and the gradient as the collection of partials, are Definition 5.5 in MML [S:27:152]. The argument that the gradient is the steepest-ascent direction, by maximizing the inner product over unit vectors, is in Blondel and Roulet [S:72:39]. Gradient descent as an iterative method goes back to Cauchy, 1847 [S:66:201].

An open question. Steepest descent is defined relative to a norm, and the choice of norm changes its performance [S:44:510]. The natural gradient replaces the Euclidean norm by the Fisher information metric and takes a different direction [S:106:46]. For a network with many parameters, forming and inverting that matrix is impractical [S:106:47]. The matrix has one entry per pair of parameters, so storing it alone grows with the square of the model size. What is unsettled is a metric that is cheap enough to use and provably better on a stated class of problems. Evidence that would settle it: an estimator costing about one gradient, with a convergence bound that beats plain descent on a named class, confirmed on problems outside the class used to design it.

A frontier result. Natural policy gradient and trust-region methods use a metric or a constraint to control the size of a step. They improve on plain policy gradient where the plain step stalls [S:106:46]. Trust-region methods constrain the change in the distribution over actions, not the change in the parameter vector, which makes the step scale-free [S:106:47]. The geometry of the step, not only its direction, is the object being designed.

What to read next. Read MML §5.2 for partial derivatives and §7.1 for gradient descent [S:27:152]. Read Blondel and Roulet §2.2 for the steepest-ascent argument [S:72:39]. Read §5.4 of the deep reinforcement learning survey for the natural gradient and its cost [S:106:46]. The last two sources use two different rulers for the same step, which is the point of the section.