2Derivatives and Gradients

Optimization is concerned with finding the design point that minimizes (ormaximizes) an objective function. Knowing how the value of a function changes
as its input is varied is useful because it tells us in which direction we can move toimprove on previous points. The change in the value of the function is measured
by the derivative in one dimension and the gradient in multiple dimensions. This
chapter briefly reviews some essential elements from calculus.1

2.1 Derivatives

For a more comprehensive review, see S. J. Colley, Vector Calculus, 4th ed. Pearson, 2011.
1

The derivative f ′ ( x ) of a function f of a single variable x is the rate at which thevalue of f changes at x. It is often visualized, as shown in figure 2.1, using thetangent line to the graph of the function at x. The value of the derivative equals
the slope of the tangent line.

f (x)

x

Figure 2.1. The function f is drawn
in black and the tangent line to f ( x )is drawn in blue. The derivative off at x is the slope of the tangentline.

20 c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

We can use the derivative to provide a linear approximation of the function
near x:f ( x + ∆x ) ≈ f ( x ) + f ′ ( x )∆x(2.1)

The derivative is the ratio between the change in f and the change in x at the
point x:∆ f (x)(2.2)
f ′ (x) =∆xwhich is the change in f ( x ) divided by the change in x as the step becomes
infinitesimally small as illustrated by figure 2.2.

h

h

h

The notation f ′ ( x ) can be attributed to Lagrange. We also use the notation

created by Leibniz,

Figure 2.2. The tangent line is obtained by joining points with sufficiently small step differences.

d f (x)(2.3)
dx
which emphasizes the fact that the derivative is the ratio of the change in f to thechange in x at the point x.
The limit equation defining the derivative can be presented in three different
ways: the forward difference, the central difference, and the backward difference. Eachmethod uses an infinitely small step size h:f ′ (x) ≡f ′ ( x ) ≡ lim
h →0|

f ( x + h/2) − f ( x − h/2)f ( x ) − f ( x − h)f ( x + h) − f ( x )
= lim
= lim
h
h
h
h →0
h →0
{z
} |
{z
} |
{z
}

forward difference

central difference

backward difference

If f can be represented symbolically, symbolic differentiation can often provide
an exact analytic expression for f ′ by applying derivative rules from calculus. The
analytic expression can then be evaluated at any point x. The process is illustrated
in example 2.1.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com(2.4)

2. 2. d e ri va ti ve s i n mu l ti p l e d i me n si on s 21

The implementation details of symbolic differentiation is outside the scopeof this text. Various software packages, such as SymEngine.jl in Julia and
SymPy in Python, provide implementations. Here we use SymEngine.jl tocompute the derivative of x2 + x/2 − sin( x )/x.

Example 2.1. Symbolic differentiation provides analytical derivatives.

julia> using SymEngine
julia> @vars x; # define x as a symbolic variablejulia> f = x^2 + x/2 - sin(x)/x;
julia> diff(f, x)
1/2 + 2*x + sin(x)/x^2 - cos(x)/x2.2

Derivatives in Multiple Dimensions

The gradient is the generalization of the derivative to multivariate functions. It
captures the local slope of the function, allowing us to predict the effect of taking
a small step from a point in any direction. Recall that the derivative is the slopeof the tangent line. The gradient points in the direction of steepest ascent of thetangent hyperplane as shown in figure 2.3. A hyperplane in an n-dimensional
space is the set of points that satisfies
w1 x 1 + · · · + w n x n = b(2.5)

for some vector w and scalar b. A hyperplane has n − 1 dimensions.
The gradient of f at x is written ∇ f (x) and is a vector. Each component of that
vector is the partial derivative2 of f with respect to that component:
h
i
f (x)
∂ f (x)∂ f (x)∇ f (x) = ∂∂x(2.6), ∂x , . . . , ∂xn
2

1

We use the convention that vectors written with commas are column vectors. For
example, we have [ a, b, c] = [ a b c]⊤ . Example 2.2 shows how to compute thegradient of a function at a particular point.
The Hessian of a multivariate function is a matrix containing all of the second
derivatives with respect to the input.3 The second derivatives capture information
about the local curvature of the function.
 2∂2 f (x)∂2 f (x)∂ f (x)···∂x1 ∂xn  ∂x1 ∂x1 ∂x1 ∂x2
..
2∇ f (x) = 
(2.7)

.

 2
∂ f (x)∂2 f (x)∂2 f (x)· · · ∂xn ∂xn∂xn ∂x∂xn ∂x1

Figure 2.3. Each component of thegradient defines a local tangent
line. These tangent lines define thelocal tangent hyperplane. The gradient vector points in the directionof greatest increase.

The partial derivative of a function with respect to a variable isthe derivative assuming all other
input variables are held constant.
It is denoted ∂ f /∂x.

2

The Hessian is symmetric only if
the second derivatives of f are allcontinuous in a neighborhood of
the point at which it is being evaluated:
3

∂2 f
∂2 f
=
∂x1 ∂x2∂x2 ∂x1

2© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

22 c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

Example 2.2. Computing the gradient at a particular point.

Compute the gradient of f (x) = x1 sin( x2 ) + 1 at c = [2, 0].
f (x) = x1 sin( x2 ) + 1


∂f ∂f
∇ f (x) =,= [sin( x2 ), x1 cos( x2 )]∂x1 ∂x2∇ f (c) = [0, 2]

The directional derivative ∇s f (x) of a multivariate function f is the instantaneous
rate of change of f (x) as x is moved with velocity s. The definition is closely related
to the definition of a derivative of a univariate function:4∇s f (x) ≡ lim
h →0|Some texts require that s be aunit vector. See, for example, G. B.
Thomas, Calculus and Analytic Geometry, 9th ed. Addison-Wesley,1968.
4

f (x + hs/2) − f (x − hs/2)
f (x) − f (x − hs)f (x + hs) − f (x)
= lim
= lim
h
h
h
h →0
h →0
{z
} |
{z
} |
{z
}

forward difference

central difference

backward difference

The directional derivative can be computed using the gradient of the function:∇s f (x) = ∇ f (x) ⊤ s(2.9)

Another way to compute the directional derivative ∇s f (x) is to define g(α) ≡f (x + αs) and then compute g′ (0), as illustrated in example 2.3.
The directional derivative is highest in the gradient direction, and it is lowest
in the direction opposite the gradient. This directional dependence arises fromthe dot product in the directional derivative’s definition and from the fact thatthe gradient is a local tangent hyperplane.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com(2.8)

2. 3. n u me ri c a l d i ffe re n ti a ti on 23

We wish to compute the directional derivative of f (x) = x1 x2 at x = [1, 0] inthe direction s = [−1, −1]:
h
i
∂f
∂f
∇ f (x) = ∂x
, ∂x = [ x2 , x1 ]
2
1
" #
h
i −1
= −1
∇s f (x) = ∇ f (x) ⊤ s = 0 1−1

Example 2.3. Computing a directional derivative.

f (α)
α

We can also compute the directional derivative as follows:

1g(α) = f (x + αs) = (1 − α)(−α) = α2 − αg′ (α) = 2α − 1
g ′ (0) = −1

2.3

Numerical Differentiation

The process of estimating derivatives numerically is referred to as numericaldifferentiation. Estimates can be derived in different ways from function evaluations.
This section discusses finite difference methods and the complex step method.5

2.3.1 Finite Difference Methods
As the name implies, finite difference methods compute the difference between twovalues that differ by a finite step size. They approximate the derivative definitions
in equation (2.4) using small differences:f ′ (x) ≈For a more comprehensive treatment of the topics discussed in theremainder of this chapter, see A.
Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation,
2nd ed. SIAM, 2008.
5f ( x + h/2) − f ( x − h/2)f ( x ) − f ( x − h)f ( x + h) − f ( x )
≈
≈
h
h
h
|
{z
} |
{z
} |
{z
}
forward difference

central difference(2.10)

backward difference

Mathematically, the smaller the step size h, the better the derivative estimate.
Practically, values for h that are too small can result in numerical cancellation
errors. This effect is shown later in figure 2.4. Algorithm 2.1 provides implementations for these methods.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

24 c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

diff_forward(f, x; h=sqrt(eps(Float64))) = (f(x+h) - f(x))/h
diff_central(f, x; h=cbrt(eps(Float64))) = (f(x+h/2) - f(x-h/2))/h
diff_backward(f, x; h=sqrt(eps(Float64))) = (f(x) - f(x-h))/h

The finite difference methods can be derived using the Taylor expansion. We
will derive the forward difference derivative estimate, beginning with the Taylor
expansion of f about x:
f ′ (x)f ′′ ( x ) 2
f ′′′ ( x ) 3h+h +h +···
1!
2!
3!
We can rearrange and solve for the first derivative:f ( x + h) = f ( x ) +(2.11)

Algorithm 2.1. Finite difference
methods for estimating the derivative of a function f at x with finite
difference h. The default step sizes
are the square root or cube root of
the machine precision for floating
point values. These step sizes balance machine round-off error withstep size error.
The eps function provides thestep size between 1.0 and the next
larger representable floating-pointvalue.

f ′′′ ( x ) 3
f ′′ ( x ) 2h −h −···(2.12)
2!
3!
f ( x + h) − f ( x )f ′′ ( x )f ′′′ ( x ) 2
f ′ (x) =−h−h −···(2.13)h2!
3!
f ( x + h) − f ( x )(2.14)f ′ (x) ≈h
The forward difference approximates the true derivative for small h withf ′ ( x )h = f ( x + h) − f ( x ) −f ′′ ( x )f ′′′ ( x )error dependent on 2! h + 3! h2 + · · · . This error term is O(h), meaning theforward difference has linear error as h approaches zero.6
The central difference method has an error term of O(h2 ).7 We can derive
this error term using the Taylor expansion. The Taylor expansions about x forf ( x + h/2) and f ( x − h/2) are:  f ′′ ( x ) h 2
f ′′′ ( x ) h 3
h++···(2.15)f ( x + h/2) = f ( x ) + f ′ ( x ) +
2
2!
2
3!
2
 
 
f ′′′ ( x ) h 3
f ′′ ( x ) h 2
h
′
−
+···
(2.16)f ( x − h/2) = f ( x ) − f ( x ) +
2
2!
2
3!
2

Asymptotic notation is covered inappendix C.

6

J. H. Mathews and K. D. Fink, Numerical Methods Using MATLAB,
4th ed. Pearson, 2004.
7

Subtracting these expansions produces:

 3
h
2 ′′′
h
f ( x + h/2) − f ( x − h/2) ≈ 2 f ( x ) + f ( x )
2 3!
2
′

(2.17)We rearrange to obtain:f ′′′ ( x )h2
f ( x + h/2) − f ( x − h/2)−h24which shows that the approximation has quadratic error.
f ′ (x) ≈(2.18)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

2. 3. n u me ri c a l d i ffe re n ti a ti on 25

2.3.2 Complex Step Method
We often run into the problem of needing to choose a step size h small enoughto provide a good approximation but not too small so as to lead to numericalsubtractive cancellation issues. The complex step method bypasses the effect ofsubtractive cancellation by using a single function evaluation. We evaluate thefunction once after taking a step in the imaginary direction.8
The Taylor expansion for an imaginary step is:f ( x + ih) = f ( x ) + ih f ′ ( x ) − h2

f ′′′ ( x )f ′′ ( x )
− ih3
+···
2!
3!

(2.19)Taking only the imaginary component of each side produces a derivative approximation:
f ′′′ ( x )+···3!
f ′′′ ( x )Im( f ( x + ih))
+ h2
−···
⇒ f ′ (x) =h3!
Im( f ( x + ih))
+ O(h2 ) as h → 0=hIm( f ( x + ih)) = h f ′ ( x ) − h3

8
J. R. R. A. Martins, P. Sturdza, andJ. J. Alonso, “The Complex-Step
Derivative Approximation,” ACM
Transactions on Mathematical Software, vol. 29, no. 3, pp. 245–262,
2003. Special care must be taken to
ensure that the implementation off properly supports complex numbers as input.

(2.20)(2.21)(2.22)

An implementation is provided by algorithm 2.2. The real part approximates f ( x )to within O(h2 ) as h → 0:f ′′ ( x )+...
2!
f ′′ ( x )⇒ f ( x ) = Re( f ( x + ih)) + h2−···
2!
Re( f ( x + ih)) = f ( x ) − h2

(2.23)(2.24)

Thus, we can evaluate both f ( x ) and f ′ ( x ) using a single evaluation of f withcomplex arguments. Example 2.4 shows the calculations involved for estimating
the derivative of a function at a particular point. Algorithm 2.2 implements thecomplex step method. Figure 2.4 compares the numerical error of the complex
step method to the forward and central difference methods as the step size isvaried.
diff_complex(f, x; h=1e-20) = imag(f(x + h*im)) / h

Algorithm 2.2. The complex step
method for estimating the derivative of a function f at x with finite
difference h.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

26

c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

Consider f ( x ) = sin( x2 ). The function value at x = π/2 is approximately
0.624266 and the derivative is π cos(π 2 /4) ≈ −2.45425. We can arrive at
this using the complex step method:

Example 2.4. The complex step
method for estimating derivatives.

julia> f = x -> sin(x^2);
julia> v = f(π/2 + 0.001im);julia> real(v) # f(x)0.6242698144866649
julia> imag(v)/0.001 # f'(x)-2.4542516170381785

complexforwardcentralabsolute relative error

103

10−1

10−5

10−9

10−13

Figure 2.4. A comparison of theerror in derivative estimate for thefunction sin( x ) at x = 1/2 as thestep size is varied. The linear errorof the forward difference method
and the quadratic error of the central difference and complex methods can be seen by the constantslopes on the right hand side. The
complex step method avoids thesubtractive cancellation error that
occurs when differencing two function evaluations that are close together.

10−17
10−18

10−15

10−12

10−9

10−6

10−3

100

step size h© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

2. 4 . a u toma ti c d i ffe re n ti a ti on 27

2.4

Automatic Differentiation

This section introduces algorithms for the numeric evaluation of derivatives offunctions specified by a computer program. Key to these automatic differentiation
techniques is the application of the chain rule:dd f dgdf ( g( x )) =( f ◦ g)( x ) =
dx
dx
dg dx

(2.25)A program is composed of elementary operations like addition, subtraction,
multiplication, and division.
Consider the function f ( a, b) = ln( ab + max( a, 2)). If we want to compute thepartial derivative with respect to a at a point, we need to apply the chain rule
several times:9∂f∂=ln( ab + max( a, 2))
∂a
∂a
∂
1
=
( ab + max( a, 2))
ab + max( a, 2) ∂a∂( ab) ∂ max( a, 2)
1+=
ab + max( a, 2) ∂a
∂a

 

1
∂a
∂2
∂b
∂a
=
b +a
+ (2 > a ) + (2 < a )ab + max( a, 2)
∂a
∂a
∂a
∂a
1
=
[b + (2 < a)]ab + max( a, 2)(2.26)

We adopt the convention that
Boolean expressions like (2 < α)
are 1 if true and 0 if false.

9(2.27)(2.28)(2.29)(2.30)

This process can be automated through the use of a computational graph. A
computational graph represents a function where the nodes are operations andthe edges are input-output relations. The leaf nodes of a computational graphare input variables or constants, and terminal nodes are values output by thefunction. A computational graph is shown in figure 2.5.
There are two methods for automatically differentiating f using its computational graph. The forward accumulation method used by dual numbers traverses
the tree from inputs to outputs, whereas reverse accumulation requires a backwards
pass through the graph.

2.4.1 Forward Accumulation
Forward accumulation will automatically differentiate a function using a single forward pass through the function’s computational graph. The method is equivalent© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

28

c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

Figure 2.5. The computationalgraph for ln( ab + max( a, 2)).

b

×

c1

a

+
max

c3

ln

c4

c2

2
to iteratively expanding the chain rule of the inner operation:





df
d f dc4d f dc4 dc3
dc dc
d f dc4 dc3 dc2
=
=
+ 3 1
=
dx
dc4 dxdc4 dc3 dx
dc4 dc3 dc2 dx
dc1 dx(2.31)

To illustrate forward accumulation, we apply it to the example function f ( a, b) =ln( ab + max( a, 2)) to calculate the partial derivative at a = 3, b = 2 with respect
to a.
1. The procedure starts at the graph’s source nodes consisting of the function
inputs and any constant values. For each of these nodes, we note both thevalue and the partial derivative with respect to our target variable, as shownin figure 2.6.10
2. Next we proceed down the tree, one node at a time, choosing as our next node
one whose inputs have already been computed. We can compute the value by
passing through the previous nodes’ values, and we can compute the local
partial derivative with respect to a using both the previous nodes’ values andtheir partial derivatives. The calculations are shown in figure 2.7.

10
For compactness in this figure,
we use dot notation or Newton’s notation for derivatives. For example,
if it is clear that we are taking thederivative with respect to a, we canwrite ∂b/∂a as ḃ.

We end up with the correct result, f (3, 2) = ln 9 and ∂ f /∂a = 1/3. This wasdone using one pass through the computational graph.
This process can be conveniently automated by a computer using a programming language which has overridden each operation to produce both the value
and its derivative. Such pairs are called dual numbers.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

2. 4 . a u toma ti c d i ffe re n ti a ti on 29b=2ḃ = 0a=3ȧ = 1Figure 2.6. The computationalgraph for ln( ab + max( a, 2)) being
set up for forward accumulation
to calculate ∂ f /∂a with a = 3 andb = 2.

b
c1

×
a

c3

+

c4

ln

c2

max
2

b=2
ḃ = 0a=3ȧ = 1c1 = a × b = 6ċ1 = b ȧ + aḃ = 2

b

×

c1

a

+
max

2

c2

c3

c4 = ln c3 = ln 9ċ4 = ċ3 /c3 = 31
ln

Figure 2.7. The computationalgraph for ln( ab + max( a, 2)) after
forward accumulation is applied
to calculate ∂ f /∂a with a = 3 andb = 2.

c4

c3 = c1 + c2 = 9ċ3 = ċ1 + ċ2 = 3

c2 = max ( a, 2) = 3
0 if 2 > aċ2 ==1 ȧ if 2 < a© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

30 c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

Dual numbers can be expressed mathematically by including the abstract
quantity ǫ, where ǫ2 is defined to be 0. Like a complex number, a dual number iswritten a + bǫ where a and b are both real values. We have:( a + bǫ) + (c + dǫ) = ( a + c) + (b + d)ǫ

(2.32)( a + bǫ) × (c + dǫ) = ( ac) + ( ad + bc)ǫ(2.33)

In fact, by passing a dual number into any smooth function f , we get the evaluationand its derivative. We can show this using the Taylor series:∞

f (k) ( a )( x − a)kk!
k =0

(2.34)

f (x) = ∑∞f (k) ( a )( a + bǫ − a)kk!
k =0f ( a + bǫ) = ∑∞f (k) ( a ) bk ǫkk!
k =0(2.35)(2.36)= ∑∞f ( k ) ( a ) b k ( k −2)
ǫ
k!
k =2

= f ( a ) + b f ′ ( a ) ǫ + ǫ2 ∑(2.37)= f ( a) + b f ′ ( a)ǫ

(2.38)

Example 2.5 shows an implementation.

2.4.2 Reverse Accumulation
Forward accumulation requires n passes in order to compute an n-dimensional
gradient. Reverse accumulation11 requires only a single run in order to compute acomplete gradient but requires two passes through the graph: a forward pass during
which necessary intermediate values are computed and a backward pass which
computes the gradient. Reverse accumulation is often preferred over forward
accumulation when gradients are needed, though care must be taken on memoryconstrained systems when the computational graph is very large.12
Like forward accumulation, reverse accumulation will compute the partial
derivative with respect to the chosen target variable but iteratively substitutes theouter function instead:





df
d f dc1 dc3 dc4d f dc4d f dc3 dc4d f dc2+===(2.39)dx
dc4 dxdc3 dc4 dx
dc2 dc3
dc1 dc3 dc4 dx

S. Linnainmaa, “The Representation of the Cumulative Rounding
Error of an Algorithm as a Taylor
Expansion of the Local Rounding
Errors,” M.S. thesis, University of
Helsinki, 1970.

11

Reverse accumulation is central
to the backpropagation algorithm
used to train neural networks. D. E.
Rumelhart, G. E. Hinton, and R. J.
Williams, “Learning Representations by Back-Propagating Errors,”
Nature, vol. 323, pp. 533–536, 1986.
12© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

2. 4 . a u toma ti c d i ffe re n ti a ti on 31

Dual numbers can be implemented by defining a struct Dual that contains
two fields, the value v and the derivative ∂.

Example 2.5. An implementationof dual numbers allows for automatic forward accumulation.

struct Dualv∂
end

We must then implement methods for each of the base operations required.
These methods take in dual numbers and produce new dual numbers usingthat operation’s chain rule logic.
Base.:+(a::Dual, b::Dual) = Dual(a.v + b.v, a.∂ + b.∂)Base.:*(a::Dual, b::Dual) = Dual(a.v * b.v, a.v*b.∂ + b.v*a.∂)Base.log(a::Dual) = Dual(log(a.v), a.∂/a.v)
function Base.max(a::Dual, b::Dual)v = max(a.v, b.v)
∂ = a.v > b.v ? a.∂ : a.v < b.v ? b.∂ : NaN
return Dual(v, ∂)endfunction Base.max(a::Dual, b::Int)v = max(a.v, b)∂ = a.v > b ? a.∂ : a.v < b ? 0 : NaN
return Dual(v, ∂)end

The ForwardDiff.jl package supports an extensive set of mathematicaloperations and additionally provides gradients and Hessians.
julia> using ForwardDiff
julia> a = ForwardDiff.Dual(3,1);
julia> b = ForwardDiff.Dual(2,0);
julia> log(a*b + max(a,2))
Dual{Nothing}(2.1972245773362196,0.3333333333333333)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

32 c ha p te r 2. d e ri va ti ve s a n d g ra d i e n ts

This process is the reverse pass, the evaluation of which requires intermediate
values that are obtained during a forward pass.
Reverse accumulation can be implemented through operation overloading13 in a 13 Operation overloading refers
similar manner to the way dual numbers are used to implement forward accumu- to providing implementations
for common operations such as
lation. Two functions must be implemented for each fundamental operation: a +, −, or = for custom variableforward operation that overloads the operation to store local gradient information types. Overloading is discussed inappendix A.2.5.
during the forward pass and a backward operation that uses the information to 14
Tensorflow is an open source softpropagate the gradient backwards. Packages like Tensorflow14 or Zygote.jl can ware library for numerical compuautomatically construct the computational graph and the associated forward and tation using data flow graphs andis often used for deep learning apbackwards pass operations. Example 2.6 shows how Zygote.jl can be used.
plications. It may be obtained fromThe Zygote.jl package provides automatic differentiation in the form ofreverse-accumulation. Here the gradient function is used to automaticallygenerate the backwards pass through the source code of f to obtain thegradient.

tensorflow.org.

Example 2.6. Automatic differentiation using the Zygote.jl package.
We find that the gradient at [3, 2] is[1/3, 1/3].

julia> import Zygote: gradientjulia> f(a, b) = log(a*b + max(a,2));
julia> gradient(f, 3.0, 2.0)
(0.3333333333333333, 0.3333333333333333)

2.5 Summary• Derivatives are useful in optimization because they provide information about
how to change a given point in order to improve the objective function.
• For multivariate functions, various derivative-based concepts are useful for
directing the search for an optimum, including the gradient, the Hessian, andthe directional derivative.
• One approach to numerical differentiation includes finite difference approximations.
• The complex step method can eliminate the effect of subtractive cancellation
error when taking small steps, resulting in high quality gradient estimates.
• Analytic differentiation methods include forward and reverse accumulationon computational graphs.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

2. 6 . e x e rc i se s 33

2.6 Exercises
Exercise 2.1. Adopt the forward difference method to approximate the Hessianof f (x) using its gradient, ∇ f (x).

Exercise 2.2. What is a drawback of the central difference method over otherfinite difference methods if we already know f (x)?
Exercise 2.3. Compute the gradient of f ( x ) = ln x + e x + 1x for a point x close to
zero. What term dominates in the expression?
Exercise 2.4. Suppose f ( x ) is a real-valued function that is also defined forcomplex inputs. If f (3 + ih) = 2 + 4ih, what is f ′ (3)?

Exercise 2.5. Draw the computational graph for f ( x, y) = sin( x + y2 ). Use thecomputational graph with forward accumulation to compute ∂ f /∂y at ( x, y) =(1, 1). Label the intermediate values and partial derivatives as they are propagatedthrough the graph.
Exercise 2.6. Combine the forward and backward difference methods to obtain adifference method for estimating the second-order derivative of a function f at x
using three function evaluations.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com