Numerical Gradient Computation: Background & Strategy

Background Knowledge

Derivatives and Rates of Change

The derivative of a function $f$ at a point $x$ represents the instantaneous rate of change—how much the function's output changes relative to small changes in the input. Mathematically, the derivative is defined as the limit:

$f'(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}$

However, in practice, we cannot compute limits exactly on computers. Instead, we use finite difference approximations, which estimate the derivative by evaluating the function at nearby points separated by a small step size $h$. The central difference formula you've been given is one such approximation and is more accurate than simpler forward or backward difference methods because it balances errors on both sides of the point.

Why Numerical Gradients Matter

In optimization and machine learning, gradient-based methods are essential for finding optimal solutions. When analytical gradients are difficult or impossible to compute—such as with complex neural networks or black-box functions—numerical gradient estimation becomes invaluable. The ability to approximate gradients numerically allows us to apply powerful optimization algorithms like gradient descent to a much broader class of problems.

Accuracy and Step Size Selection

The accuracy of your numerical gradient depends critically on choosing an appropriate step size $h$. If $h$ is too large, the approximation becomes crude and inaccurate. If $h$ is too small, you encounter floating-point precision errors where the numerator becomes dominated by rounding errors. The central difference method typically requires $h$ in the range of $10^{-4}$ to $10^{-5}$ for good results with standard floating-point arithmetic, though this varies depending on the function and precision available.

Algorithm/Approach

The central difference formula provides a straightforward algorithmic pattern:

1. Choose a step size $h$ (typically a small value like $10^{-5}$)
2. Evaluate the function at two nearby points: $f(x + h)$ and $f(x - h)$
3. Apply the formula: compute $\frac{f(x + h) - f(x - h)}{2h}$
4. Return the result as your numerical gradient estimate

This approach is general and works for any differentiable function where you can evaluate $f$ at arbitrary points.

Step-by-Step Strategy

Step 1: Understand Your Inputs

• You'll receive a function $f$ (either as a callable or defined implicitly)
• You'll receive a point $x$ where you need to compute the gradient
• You may need to choose or be given a step size $h$

Step 2: Compute Function Values

• Calculate $f(x + h)$ by evaluating the function at the point shifted right by $h$
• Calculate $f(x - h)$ by evaluating the function at the point shifted left by $h$

Step 3: Apply the Central Difference Formula

• Compute the difference: $f(x + h) - f(x - h)$
• Divide by $2h$ to get your gradient approximation

Step 4: Handle Edge Cases

• Consider whether $x$ is a scalar or a vector (for multivariable functions, you may need to compute partial derivatives)
• If working with vectors, you typically compute the gradient for each dimension separately

Step 5: Validate Your Result

• Test with functions where you know the analytical derivative (e.g., $f(x) = x^2$ has $f'(x) = 2x$)
• Compare your numerical result to the analytical result to verify correctness

Common Pitfalls

Step Size Selection

• Choosing $h$ too large leads to poor approximation accuracy
• Choosing $h$ too small introduces floating-point rounding errors
• There's a "sweet spot" that requires some experimentation; $10^{-5}$ is often a good starting point

Floating-Point Precision

• When $h$ is extremely small, subtracting two nearly equal numbers ($f(x+h)$ and $f(x-h)$) can lose precision
• This is called catastrophic cancellation and becomes problematic below certain thresholds

Multivariable Functions

• For functions with multiple inputs, remember that you're computing partial derivatives
• Each component of the gradient requires separate evaluation with perturbations in that dimension only

Function Evaluation Costs

• Numerical gradients require at least two function evaluations per gradient component
• For high-dimensional problems, this can become computationally expensive compared to analytical gradients

Off-by-One Errors in Indexing

• If implementing for vector inputs, ensure you're perturbing the correct dimension
• Be careful with array indexing when computing partial derivatives

Time & Space Complexity

Time Complexity: $O(n)$ where $n$ is the dimensionality of the input

• For a scalar input: $O(1)$ (two function evaluations)
• For an $n$-dimensional input: $O(n)$ (you need $2n$ function evaluations to compute all partial derivatives—two evaluations per dimension)

Space Complexity: $O(1)$ for scalar inputs, $O(n)$ for vector inputs

• You need to store the gradient vector if computing for multivariable functions
• The algorithm itself requires only a constant amount of additional memory beyond storing inputs and outputs