• 0. Linear operator
  • 1. Gradient of a function
  • 2. Jacobian of a function
  • 3. Key matrix derivatives
  • 4. Function is a DAG
  • 5. Autodiff on a DAG
  • 6. VJP and JVP
  • 7. Hessian of a function
unitgridOpacitycanvasColororiginXoriginY

Gradient of a function

  • 0. What is a gradient?
    • 0.1 Gradient is perpendicular to the tangent plane
  • 1. Gradient and the inner product
    • 1.1 Frobenius inner product and Frobenius norm
  • 2. Some useful identities
    • 2.1 Trace of a matrix
    • 2.2 Kronecker product
  • 3. Examples
    • 3.1 f(A)=∥A∥Ff(A) = \|A\|_Ff(A)=∥A∥F​
    • 3.2 f(A)=xTAyf(A) = x^TAyf(A)=xTAy
    • 3.3 f(A)=det⁡(A)f(A) = \det(A)f(A)=det(A)

We start with functions whose output is a scalar. The gradient is defined only for scalar-valued functions; for vector-valued functions, it generalizes to the Jacobian.


0. What is a gradient?

Consider a scalar-valued function f(x⏟∈Rn)=y⏟∈Rf(\underbrace{x}_{\in R^n}) = \underbrace{y}_{\in R}f(∈Rnx​​)=∈Ry​​. Then a small change in output given a small change in input can be expressed as an inner product with the change in input dxdxdx:

Lf[dx]⏞scalar=⟨ ?⏞∈Rn ,dx⟩=⟨ ∇f⏟grad(f) ,dx⟩\begin{aligned} \overbrace{L_f[dx]}^{\text{scalar}} &= \langle \ \overbrace{?}^{\in R^n} \ , dx \rangle \\ &= \textcolor{#b45309}{\langle \ \underbrace{\nabla f}_{grad(f)} \ , dx \rangle} \end{aligned}Lf​[dx]​scalar​​=⟨ ?∈Rn ,dx⟩=⟨ grad(f)∇f​​ ,dx⟩​

This is because Lf[dx]L_f[dx]Lf​[dx] is a linear function of dxdxdx and its output is a scalar. Note that this becomes possible only because the output is a scalar. ∇f\nabla f∇f is the gradient of fff. It is a vector with the same dimension as the input vector xxx.

Conceptually, the gradient of a scalar-valued function is a vector whose components are the partial derivatives of the function with respect to each of the coordinates of the input vector.

⟨[∂f/∂x1∂f/∂x2⋮∂f/∂xn]⏟∇f,[dx1dx2⋮dxn]⏟dx⟩=df\langle \underbrace{\textcolor{#b45309}{\begin{bmatrix} \partial f / \partial x_1 \\ \partial f / \partial x_2 \\ \vdots \\ \partial f / \partial x_n \end{bmatrix}}}_{\textcolor{#b45309}{\nabla f}}, \underbrace{\begin{bmatrix} dx_1 \\ dx_2 \\ \vdots \\ dx_n \end{bmatrix}}_{dx} \rangle = df⟨∇f​∂f/∂x1​∂f/∂x2​⋮∂f/∂xn​​​​​,dx​dx1​dx2​⋮dxn​​​​​⟩=df

0.1 Gradient is perpendicular to the tangent plane

In the above expression, setting df=0df = 0df=0 gives us ⟨∇f,dx⟩=0\langle \nabla f, dx \rangle = 0⟨∇f,dx⟩=0. Since the output does not change, the vector dxdxdx lies in the tangent plane of the function fff at the point xxx. The gradient ∇f\nabla f∇f is perpendicular to the tangent plane.

For example, consider f(x)=∥x∥f(x) = \|x\|f(x)=∥x∥. Writing f(x)=xTxf(x) = \sqrt{x^Tx}f(x)=xTx​ and using d(xTx)=2xTdxd(x^Tx) = 2x^Tdxd(xTx)=2xTdx, we get df=xTdx∥x∥=⟨x/∥x∥⏟∇f,dx⟩df = \frac{x^Tdx}{\|x\|} = \langle \underbrace{\textcolor{#b45309}{x/\|x\|}}_{\textcolor{#b45309}{\nabla f}}, dx \rangledf=∥x∥xTdx​=⟨∇fx/∥x∥​​,dx⟩. So the gradient of the norm is simply the unit vector in the direction of xxx.

Given a function R2→RR^2 \to RR2→R, one can draw its gradient at each point as a vector field, where each vector represents the gradient at that point:

pie.clear()
p0 = pie.point(0, 0, out='p0', hidden=True)
p = pie.point(3, 2, out='p')
dist = pie.distance(p, p0, out='dist')
  • Vector field of f(x)=∥x∥f(x) = \|x\|f(x)=∥x∥.
import math

AMBER = '#b45309'
# The gradient x / ||x|| of f(x) = ||x|| at each grid point (except the origin),
# drawn as an arrow of length 0.8 starting at that point
LENGTH = 0.8
tails = [(gx, gy) for gx in range(-6, 7) for gy in range(-5, 6) if (gx, gy) != (0, 0)]
dxs = [LENGTH * gx / math.hypot(gx, gy) for gx, gy in tails]
dys = [LENGTH * gy / math.hypot(gx, gy) for gx, gy in tails]
pie.la_vec2d(dxs, dys, [float(gx) for gx, gy in tails], [float(gy) for gx, gy in tails], out='vf', stroke=AMBER)

Note how the gradient at each point is a unit vector that points in the same direction as the input point.

px = pie.lift(lambda q: q[0], pie.Scalar)(p)
py = pie.lift(lambda q: q[1], pie.Scalar)(p)
pie.la_vec2d(px, py, out='vp')
pie.circle(p0, dist, out='circ')

Since rotation does not change the magnitude of the vector, all these gradients are normal to the circle passing through this point.


1. Gradient and the inner product

The idea of inner product between two vectors can be extended to matrices. This allows us to use matrix identities to compute the gradient of a scalar-valued function. The inner product of two matrices AAA and BBB (of the same shape) is the sum of their elementwise products. It is also known as the Frobenius inner product and denoted by ⟨A,B⟩F\langle A, B \rangle_F⟨A,B⟩F​.


1.1 Frobenius inner product and Frobenius norm

The trace of a square matrix MMM, denoted by tr(M)\text{tr}(M)tr(M), is the sum of its diagonal elements. It is connected to the Frobenius inner product like so:

⟨ A,B⏟m,n ⟩F=tr(ATB⏟n,n)=tr(BTA⏟n,n)\langle \ \underbrace{A,B}_{m,n} \ \rangle_F = \text{tr}(\underbrace{A^TB}_{n,n}) = \text{tr}(\underbrace{B^TA}_{n,n})⟨ m,nA,B​​ ⟩F​=tr(n,nATB​​)=tr(n,nBTA​​)

One can also extend the idea of the norm of a vector to the norm of a matrix. The Frobenius norm of a matrix AAA, denoted by ∥A∥F\|A\|_F∥A∥F​, is the square root of the Frobenius inner product of AAA with itself.

∥A∥F=⟨A,A⟩F=tr(ATA)\|A\|_F = \sqrt{\langle A,A \rangle_F} = \sqrt{\text{tr}(A^TA)}∥A∥F​=⟨A,A⟩F​​=tr(ATA)​

2. Some useful identities

It is helpful to remember some identities that are useful in computing the gradient of a scalar-valued function.


2.1 Trace of a matrix

  • Linear: tr(pA+qB)=p tr(A)+q tr(B)\text{tr}(pA + qB) = p\,\text{tr}(A) + q\,\text{tr}(B)tr(pA+qB)=ptr(A)+qtr(B)
  • Invariant under transposition: tr(A)=tr(AT)\text{tr}(A) = \text{tr}(A^T)tr(A)=tr(AT)
  • Commutative: tr(AB)=tr(BA)\text{tr}(AB) = \text{tr}(BA)tr(AB)=tr(BA)
  • Invariant under circular shifts: tr(ABC)=tr(CAB)=tr(BCA)\text{tr}(ABC) = \text{tr}(CAB) = \text{tr}(BCA)tr(ABC)=tr(CAB)=tr(BCA)
  • Invariant under similarity: tr(P−1AP)=tr(A)\text{tr}(P^{-1}AP) = \text{tr}(A)tr(P−1AP)=tr(A)
  • And finally: d(tr(A))=tr(dA)d(\text{tr}(A)) = \text{tr}(dA)d(tr(A))=tr(dA)

2.2 Kronecker product

More details can be found in this article. Two key properties of the Kronecker product that will come in handy are:

  • vec( C⏟c1,c2M⏞c2,b2BT⏟b2,b1 )=(B⊗C)⏟b1c1,b2c2vec(M)⏞b2c2vec(\ \underbrace{C}_{c_1,c_2} \overbrace{M}^{c_2,b_2} \underbrace{B^T}_{b_2,b_1} \ ) = \underbrace{(B \otimes C)}_{b_1c_1,b_2c_2} \overbrace{vec(M)}^{b_2c_2}vec( c1​,c2​C​​Mc2​,b2​b2​,b1​BT​​ )=b1​c1​,b2​c2​(B⊗C)​​vec(M)​b2​c2​​
  • tr(A⊗B)=tr(A) tr(B)\text{tr}(A \otimes B) = \text{tr}(A)\,\text{tr}(B)tr(A⊗B)=tr(A)tr(B)

3. Examples

Note that all the functions below are scalar valued.


3.1 f(A)=∥A∥Ff(A) = \|A\|_Ff(A)=∥A∥F​

The function can be rewritten as f=∥A∥F=tr(ATA)f = \|A\|_F = \sqrt{\text{tr}(A^TA)}f=∥A∥F​=tr(ATA)​. Then:

df=f(A+dA)−f(A)=12∥A∥ d(tr(ATA))=12∥A∥ tr(d(ATA))=12∥A∥ tr(ATdA+dATA)=12∥A∥ tr(ATdA+ATdA)=12∥A∥ tr(2ATdA)=1∥A∥ tr(ATdA)=⟨A∥A∥⏟∇f,dA⟩\begin{aligned} df &= f(A+dA) - f(A) \\ &= \frac{1}{2\|A\|}\,d(\text{tr}(A^TA)) \\ &= \frac{1}{2\|A\|}\,\text{tr}(d(A^TA)) \\ &= \frac{1}{2\|A\|}\,\text{tr}(A^TdA + dA^TA) \\ &= \frac{1}{2\|A\|}\,\text{tr}(A^TdA + A^TdA) \\ &= \frac{1}{2\|A\|}\,\text{tr}(2A^TdA) \\ &= \frac{1}{\|A\|}\,\text{tr}(A^TdA) \\ &= \langle \underbrace{\textcolor{#b45309}{\frac{A}{\|A\|}}}_{\textcolor{#b45309}{\nabla f}}, dA \rangle \end{aligned}df​=f(A+dA)−f(A)=2∥A∥1​d(tr(ATA))=2∥A∥1​tr(d(ATA))=2∥A∥1​tr(ATdA+dATA)=2∥A∥1​tr(ATdA+ATdA)=2∥A∥1​tr(2ATdA)=∥A∥1​tr(ATdA)=⟨∇f∥A∥A​​​,dA⟩​

3.2 f(A)=xTAyf(A) = x^TAyf(A)=xTAy

Here we use the trick that the trace of a scalar is the scalar itself. Hence tr(c)=c,c∈R\text{tr}(c) = c, c \in Rtr(c)=c,c∈R.

df=f(A+dA)−f(A)=xT dA y=tr(xT dA y)=tr(yxT dA)=tr((xyT)T dA)=⟨xyT⏟∇f,dA⟩\begin{aligned} df &= f(A+dA) - f(A) \\ &= x^T\,dA\,y \\ &= \text{tr}(x^T\,dA\,y) \\ &= \text{tr}(yx^T\,dA) \\ &= \text{tr}((xy^T)^T\,dA) \\ &= \langle \underbrace{\textcolor{#b45309}{xy^T}}_{\textcolor{#b45309}{\nabla f}}, dA \rangle \end{aligned}df​=f(A+dA)−f(A)=xTdAy=tr(xTdAy)=tr(yxTdA)=tr((xyT)TdA)=⟨∇fxyT​​,dA⟩​

Note that using the Kronecker identity of the bilinear form, we could also write:

df=xT dA y=⟨x⊗y⏟vec(∇f),vec(dA)⟩df = x^T\,dA\,y = \langle \underbrace{\textcolor{#b45309}{x\otimes y}}_{\textcolor{#b45309}{\text{vec}(\nabla f)}}, \text{vec}(dA) \rangledf=xTdAy=⟨vec(∇f)x⊗y​​,vec(dA)⟩

Indeed one can verify that vec(xyT)=x⊗y\text{vec}(xy^T) = x\otimes yvec(xyT)=x⊗y.


3.3 f(A)=det⁡(A)f(A) = \det(A)f(A)=det(A)

Assume that A−1A^{-1}A−1 exists. First we establish that d(det⁡(I+dX))=tr(dX)d(\det(I + dX)) = \text{tr}(dX)d(det(I+dX))=tr(dX) for a small perturbation dXdXdX.

det⁡(I+dX)=∏i(1+dXii)+(higher order terms)=1+∑idXii+(higher order terms)=1+∑idXii=1+tr(dX)=det⁡(I)+tr(dX)\begin{aligned} \det(I + dX) &= \prod_i(1 + dX_{ii}) + \text{(higher order terms)} \\ &= 1 + \sum_i dX_{ii} + \text{(higher order terms)} \\ &= 1 + \sum_i dX_{ii} \\ &= 1 + \text{tr}(dX) \\ &= \det(I) + \text{tr}(dX) \end{aligned}det(I+dX)​=i∏​(1+dXii​)+(higher order terms)=1+i∑​dXii​+(higher order terms)=1+i∑​dXii​=1+tr(dX)=det(I)+tr(dX)​

Next we perturb the matrix AAA by a small amount dAdAdA and rewrite it as A+dA=A(I+A−1dA)A+dA = A(I + A^{-1}dA)A+dA=A(I+A−1dA).

d(det⁡(A+dA))=d(det⁡(A) det⁡(I+A−1dA))=det⁡(A) d(det⁡(I+A−1dA))=det⁡(A) tr(A−1dA)=tr(det⁡(A)A−1dA)=tr(det⁡(A)A−1⏟=CAT dA)=⟨CA⏟∇f,dA⟩\begin{aligned} d(\det(A + dA)) &= d(\det(A)\,\det(I + A^{-1}dA)) \\ &= \det(A)\,d(\det(I + A^{-1}dA)) \\ &= \det(A)\,\text{tr}(A^{-1}dA) \\ &= \text{tr}(\det(A)A^{-1}dA) \\ &= \text{tr}(\underbrace{\det(A)A^{-1}}_{= C_A^T}\,dA) \\ &= \langle \underbrace{\textcolor{#b45309}{C_A}}_{\textcolor{#b45309}{\nabla f}}, dA \rangle \end{aligned}d(det(A+dA))​=d(det(A)det(I+A−1dA))=det(A)d(det(I+A−1dA))=det(A)tr(A−1dA)=tr(det(A)A−1dA)=tr(=CAT​det(A)A−1​​dA)=⟨∇fCA​​​,dA⟩​

Here CAC_ACA​ is the cofactor matrix of AAA. Thus, the gradient of determinant of a matrix is its cofactor matrix.

Next we will generalize the idea of a gradient to functions whose output is a vector.


← Linear operator · Jacobian of a function →