Three ways to differentiate

Nine numbers decide what a small network does. Change one and the loss moves, so training needs to know which way each of the nine should move. A modern model has millions of such numbers, and nobody can read the formula that joins them. The chapter's question is practical: how does a computer differentiate a huge formula? This section gives the short answer, by comparing the three routes a computer can take.

The routes are symbolic differentiation, numerical differentiation and automatic differentiation. Symbolic differentiation works on a formula and returns another formula. Numerical differentiation works on values and returns an estimate. !The product program $L=w_1{w}_2\cdots w_n$, with all $n$ partial derivatives priced in elementary multiplications. The formula route needs $n(n-2)$ and the centred numeric route $2n(n-1)$, so both climb with the square of the model; the program route needs $3(n-1)$ and climbs in proportion. At nine weights the counts are 63, 144 and 24; at a million they are $10^{12}$, $2\times 10^{12}$ and $3\times 10^6$. The two upper lines are the ones a large model cannot afford. Status: schematic.

Automatic differentiation works on the program and returns the exact derivative of the trace the program executed — no step is chosen, so no truncation error enters [S:67:261]. It computes that value in floating point, so it carries the rounding error of any other floating-point computation. Bishop calls the result accurate to machine precision, the same claim he makes for symbolic differentiation [S:67:263].

Bishop counts a fourth route, differentiating by hand, and places it first because it was the mainstay for years [S:67:261]. The whole chapter is about replacing that hand work. Each route is exact for a different object, and mixing up the objects is the usual source of trouble.

The formula route is exact for the function it denotes, and the program route is exact for the code that ran. The numeric route is exact for a third object: its centred quotient equals the derivative plus a term of size ${\Delta }^2/6$ times the function's third derivative [S:72:192]. That makes the route exact for every function whose third derivative vanishes — every polynomial of degree at most two, not only the affine ones — and generally inexact otherwise.

Use symbols when you want an expression you can read, simplify or differentiate again, and the expression stays short. Use numbers when you already have a derivative and want to check it. Use a program when the formula is long, the code branches or loops, or there are more parameters than anyone wants to write down.

Worked example. Take the derivative of f(x) = x^3 at x = 2. The formula gives 3x^2 = 12, and two quotients estimate the same slope from values.

A one-sided quotient with step 0.1 gives (2.1^3 - 8)/0.1 = 12.61. A centred quotient gives (2.1^3 - 1.9^3)/0.2 = 12.01. The two estimates miss 12 by 0.61 and 0.01, because each one ran the function at shifted points and divided a small difference.

Three lessons follow from those estimates. The formula route is exact for the function it denotes, and its output can grow far longer than the function it started from [S:67:262]. The numeric route fits any code that computes a value, and its accuracy is limited by subtracting two close numbers [S:67:262]. The program route is exact for the code that ran, because it applies one local rule per operation the code performed [S:66:192]. Exact here means the chain rule is applied rather than approximated; the arithmetic still rounds, so the returned number carries floating-point error of the same order as any other computation of the same length.

The centred quotient is worth writing once. With a step written Δ, it reads

That line says: step a little to each side, subtract the two values, and divide by the width of the whole step.

Two errors pull the numeric route in opposite directions. Shrinking the step reduces the truncation error, the gap between the quotient and the true slope, and raises the round-off error of subtracting two nearly equal values. Bishop calls the result limited accuracy, and the limit belongs to the arithmetic rather than to the function [S:67:262]. A gradient check at a fixed step is therefore evidence, not proof.

The numeric route survives as a check. It uses only the code that computes the value, so it can test an implementation of either other route [S:67:262]. A disagreement means a bug, and agreement to a few digits means the two routes see the same slope.

Symbolic differentiation fails somewhere else. Its output is an expression, and a nested product can make that expression grow much faster than the program that produced it [S:67:262]. This growth is called expression swell, and it is paid in time and memory. The route also needs a closed formula, so a loop, a branch or a procedure call falls outside it [S:67:263].

Automatic differentiation keeps the program as its object. It reads each operation, applies that operation's local derivative, and never builds a derivative expression [S:66:192]. A branch costs what the branch did, and a loop costs what the loop ran. The price is set by the number of operations, not by the length of any formula.

For a model, the count decides. Nine parameters need ten evaluations for a one-sided numeric gradient — the value at the point plus one shifted evaluation per parameter, $P+1$ in general [S:72:196]. A centred gradient needs eighteen, $2P$, because the centred quotient shares no evaluation between parameters. The count rises with the parameters, and a large model has millions of them. Automatic differentiation spreads its cost across the operations instead, and section 18.3 shows one backward pass returning all nine slopes.

The difference matters at scale. A formula for the loss of a deep network fills pages, and its derivative fills more. A program for the same network is a short sequence of familiar operations, and each operation has a derivative a student can write down. Automatic differentiation asks the program for its operations, not the mathematician for a formula [S:67:263]. For a large model, that is the only one of the three routes that stays affordable.

Limitation: Automatic differentiation differentiates the code you wrote, not the function you meant. A branch, a comparison or a library routine can make the two differ, and at a corner the code still returns a number. Section 18.6 takes that cost apart.

The formal statement. Let a program read an input $x$ and write one output, using a finite set of primitive operations. The three routes return three kinds of object.

• Symbolic differentiation returns an expression whose value is $f^{\prime }(x)$ wherever the function $f$ it denotes is differentiable [S:67:262].
• Numerical differentiation returns a quotient of evaluated values, $\hat{g}(x)=(f(x+\Delta )-f(x-\Delta ))/(2\Delta )$, exact for functions whose third derivative vanishes and otherwise carrying a truncation term of order ${\Delta }^2$ [S:67:262].
• Automatic differentiation returns $\partial f_T(x_{T-1})\cdots \partial f_1(x_0)$, the product of the local derivatives of the operations the run performed [S:66:192].

The third object is a number, exact for the trace in the mathematics and rounded in the arithmetic.

The derivation. Expand $f$ in Taylor series about $x$, with three continuous derivatives near $x$. The even terms agree and the odd terms differ in sign, so subtracting leaves

for some $\xi$ between $x-\Delta$ and $x+\Delta$. That line says the centred quotient equals the slope plus a truncation term of size ${\Delta }^2/6$ times the third derivative.

The second error is arithmetic. Each evaluation rounds, so the numerator carries an absolute error of about machine epsilon times $|f|$, and dividing by $2\Delta$ magnifies it. The two terms pull in opposite directions and are smallest where they are equal; that is the whole of "limited accuracy" [S:67:262]. One step is omitted: the bound treats the rounding of the division as negligible and assumes a bound on $|f^{\prime \prime \prime }|$ that a program may not have.

The edge case. Take $f(x)=3x+1$. The centred quotient returns exactly 3 in exact arithmetic. In floating point it returns 3 only when the two evaluations and their difference are themselves exact, which is a condition on $x$ and $\Delta$ together and not on $3\Delta$: with $x=0$ and $\Delta =0.1$ the quotient is $3.0000000000000004$, and with $x=10^8$ and $\Delta =10^{-8}$, where $\Delta$ is below one ulp of $x$, the quotient is $5.96$. Dyadic $x$ and $\Delta$, such as $x=0$ and $\Delta =1/8$, do give exactly 3. The affine function is exact in the algebra of the quotient, not in the arithmetic that evaluates it [S:72:191]. The core named the object: the quotient is exact when the third derivative vanishes. Here it is, and the bound shows why — the truncation term drops out. A route is not inexact in general. It is inexact in proportion to a derivative the quotient cannot see, and an affine function hides all of them. A gradient check on a nearly linear model passes for reasons that do not transfer to the model you train.

What the core hid. The core compared three routes on $f(x)=x^3$ at $x=2$, where the third derivative is the constant 6 and the step was 0.1. Both error terms were small enough that their sizes did not matter, so the comparison taught the ordering of the routes without teaching their constants. The core also said the formula route is exact for the function. That is right for the denoted function and wrong for the code: an exact expression is still evaluated in floating point.

Where the analogy breaks. "Three routes, three objects" suggests three tools you choose between. Two of them compose. You can simplify a program symbolically and then differentiate the simplified program by automatic differentiation, and you can differentiate a graph built for derivatives to obtain a second derivative [S:66:190-191]. The routes are three places to stop in one pipeline, not three disjoint tools.

Original sources. Bishop opens his automatic-differentiation section by counting the routes and placing derivation by hand first, because it was the mainstay for years [S:67:261]. He then separates the numerical, symbolic and programmatic routes by the object each one differentiates [S:67:262]. Blondel and Roulet give the finite-difference family a chapter of its own, with the evaluation count for each variant [S:72:196].

An open question. Which route to use when the program contains an algorithm rather than a formula. A linear solve, an optimisation and a simulation all end in a loop whose trip count depends on the input. Differentiating the unrolled run is exact for that run and costs memory proportional to the iteration count. Treating the answer as an implicit function costs one linear solve, because the implicit function theorem gives conditions under which an implicit relation can be rewritten as a function of the parameter and supplies its derivative [S:72:288]. The field has not settled which is preferable at scale.

What would settle it: matched-cost comparisons on the same tasks, with the inner tolerance held fixed, the gradient checked against a high-precision oracle, and both error and wall-clock reported. A method that wins only on error or only on time has not settled the choice.

A frontier result. Complex-step differentiation. Evaluate $f$ at $x+i\Delta$ and read the imaginary part divided by $\Delta$. The Taylor expansion separates even terms into the real part and odd terms into the imaginary part. No subtraction of two nearly equal values occurs, so the cancellation that dominates the real quotient at small $\Delta$ is gone and the method usually has smaller round-off error [S:72:195]. Round-off does not disappear: the division by $\Delta$ still rounds, and the truncation term is still $O({\Delta }^2)$, so the step must still be chosen rather than made as small as possible. For a directional derivative the complex step costs one complex function call, against two real calls for any of the three finite differences. For a full gradient of $P$ parameters it costs $P$ complex calls, against $P+1$ for one-sided and backward differences and $2P$ for central differences [S:72:196, Table 7.1]. The saving is therefore one call in the directional case and one call against the one-sided gradient; the reason to use it is the round-off, not the count. The requirement is that every primitive in the program is defined on complex numbers.

What to read next. Chapter 7 of Blondel and Roulet for finite differences, the complex step and the complexity table [S:72:196]. Then Chapter 8 for the two modes that replace the quotient entirely [S:72:198]. In Bishop, section 8.2 for the same four-way comparison in the notation of a neural network [S:67:261].