Gradient Checking

The problem

In this section you will write backward passes by hand: code that computes the gradient of a function. A backward pass can be wrong and still look plausible, so before writing any, build the tool that tells you whether one is right. You will use it, or the version in the tests, for every gradient in the rest of the roadmap.

The tool has two parts: a slow but reliable way to estimate a gradient, and a way to compare two gradients.

Part 1: estimating a gradient by nudging

The derivative of $f$ with respect to one entry $x_i$ says how much $f$ changes when $x_i$ changes a tiny bit. So measure it directly: nudge $x_i$ up by a small eps, compute $f$; nudge it down by eps, compute $f$ again; divide the change by the distance between the two points. This is the central difference:

where:

• $\varepsilon$ is eps, the size of the nudge;
• $e_i$ is an array of zeros with a 1 at entry $i$, so $x + \varepsilon e_i$ means "add eps to entry $i$ only, leave the others alone";
• $2\varepsilon$ is the distance between the two nudged points.

Do this for every entry, one at a time, and you get an array of estimates shaped like x.

Example. $f = x_0^2 + 3 x_1$ at x = [1.0, 2.0], with eps = 0.01. The true gradient is $(2 x_0, 3) = (2, 3)$.

• Entry 0: with $x_0 = 1.01$, $f = 7.0201$; with $x_0 = 0.99$, $f = 6.9801$. Estimate: $(7.0201 - 6.9801) / 0.02 = 2$.
• Entry 1: with $x_1 = 2.01$, $f = 7.03$; with $x_1 = 1.99$, $f = 6.97$. Estimate: $(7.03 - 6.97) / 0.02 = 3$.

The result is [2.0, 3.0], and x is back to [1.0, 2.0] at the end.

Why both directions? The one-sided version, $(f(x + \varepsilon e_i) - f(x)) / \varepsilon$, is much less accurate. For $f = x^3$ at $x = 1$ (true derivative $3$) with $\varepsilon = 0.01$, it gives $3.0301$, while the central difference gives $3.0001$.

Part 2: comparing two gradients

Your gradient $a$ and the estimate $b$ will never be exactly equal, so we need to measure how far apart they are. A plain difference is not enough: $0.001$ is a big error if the gradient is $0.002$, and nothing if it is $1000$. The relative error divides by the size of the numbers:

where:

• $|a_i - b_i|$ is the difference at entry $i$, and the top takes the largest one;
• $|a_i| + |b_i|$ is the size of the two numbers at entry $i$, and the bottom takes the largest one;
• if both arrays are all zeros, the bottom is 0, and the answer is defined as 0: no error.

Example.

• $a = (2, 3)$, $b = (2, 3.0003)$: the largest difference is $0.0003$, the largest size $3 + 3.0003 = 6.0003$, so the relative error is about $5 \times 10^{-5}$. Close.
• $a = (2, 3)$, $b = (2, -3)$: the largest difference is $6$, the largest size $6$, so the relative error is $1$. A sign error: a bug.

As a rule of thumb, around $10^{-7}$ or below is a pass and $10^{-2}$ means a bug.

What to implement

• numerical_grad(f, x, eps=1e-5): f takes no arguments and returns a number computed from the array x, which can have any shape. Return an array shaped like x with the central-difference estimate for every entry.
• rel_error(a, b): the relative error between two arrays of the same shape, as a number.

Requirements

• f reads x itself, so change x in place, one entry at a time, and put every entry back to its original value. After the call, x must be exactly unchanged.
• Use the central difference, not the one-sided one: the tests check accuracy closely enough to tell them apart.

Hints

• np.ndindex(x.shape) yields every index of an array of any shape: (0,), (1,), ... for a list, (0, 0), (0, 1), ... for a table. A loop is fine here: gradient checks run on small inputs only.
• Save the original value before nudging and assign it back at the end. Adding eps and subtracting it again does not always give back exactly the same number in floating point.