Preporato

Numerical gradient by central differences

Easy10 min11 hidden tests

A search team wrote a custom ranking loss and wants to see its slopes before they trust any backprop code. Write numerical_gradient(f, x, h) that estimates the gradient of a scalar function f at the point x. For each coordinate, nudge only that coordinate up by h and down by h, and divide the change in f by 2 * h. This is the central difference.

Drag the point, change h

slope ≈ (f(x+h) − f(x−h)) / 2h
True slopeCentral differenceOne-sided

True slope 3x² = 3. Central difference 3.01, off by 0.01. One-sided 3.31, off by 0.31. Halve h and the central error drops about 4 times; the one-sided error only about halves.

x 1, h 0.1. True slope 3, central 3.01, one-sided 3.31.

Examples

The slopes of x0 squared plus 3 x1 at (2, 1) are 4 and 3

numerical_gradient(lambda v: v[0] ** 2 + 3 * v[1], [2.0, 1.0], 1e-5)

returns [4, 3]

With a large h, a cubic's estimate is off by h squared: 3.01 and 12.01

numerical_gradient(lambda v: np.sum(v ** 3), [1.0, -2.0], 0.1)

returns [3.01, 12.01]

Requirements

  • f takes a 1-D float array and returns a float. x is a list or 1-D array of n numbers, and h is a small positive float with a default of 1e-5.
  • Return a 1-D NumPy float array of length n. Entry i is (f(x + h * e_i) - f(x - h * e_i)) / (2 * h), where e_i is 1 at position i and 0 everywhere else.
  • Move one coordinate at a time, and leave the caller's x unchanged.
The idea behind it

A gradient is a list of slopes: entry i says how fast a function grows when input i grows a little and every other input stays put. Backpropagation computes it exactly, but it is easy to get wrong when you write it by hand. A finite difference estimates the same slope from the function alone. The forward difference (f(x + h) - f(x)) / h has an error that shrinks in step with h. The central difference (f(x + h) - f(x - h)) / (2h) looks on both sides, and its error shrinks with h squared, so it is far more accurate for the same h. On a quadratic it is exact. It costs two calls to f per input, which is too slow for training a large model and just right for checking one. Frameworks ship it for this reason: PyTorch's gradcheck compares backprop against these estimates.

pythonCtrl+Enter runs
import numpy as np

def numerical_gradient(f, x, h=1e-5):
"""Central-difference estimate of the gradient of f at x.

f: function from a 1-D float array to a float
x: list or 1-D array of n numbers, the point to look at
h: half the gap between the two points per coordinate, a small positive float
Returns a 1-D float array of n slopes, one per coordinate.
"""
raise NotImplementedError

Stuck? Reveal one rung at a time

Worked solution

Give it a real try first. Then read the solution and why each line is there.