Stefan M. Wild
Optimal Finite Difference Derivatives of Noisy, Iterative Simulations

Mathematics and Computer Science Division
Argonne National Laboratory
9700 S Cass Ave Bldg 240-1154
Argonne IL 60439
wild@mcs.anl.gov
Jorge Moré

We have developed new mathematical theory and tools for estimating the computational noise that arises in numerical simulations throughout scientific computing [4]. Roundoff errors, discretizations, numerical solutions to systems of equations, and adaptive techniques are among the many sources of computational noise, which can destroy the smoothness of the processes underlying a simulation and complicate optimization, sensitivity analysis, and other applications depending on the simulation output. Our theory is based on a stochastic model but does not assume a specific form (e.g., Gaussian or mean zero) for the distribution of the noise. Our technique is similar to that of Hamming [3] and has been validated empirically on deterministic simulations where the theory does not hold.

In this talk, we use an estimate of the computational noise to address a longstanding problem in derivative estimation: How should finite difference parameters be determined when working with a noisy function?

We have derived optimal finite difference parameters that are easy to compute, depending only on an estimate of the computational noise and a coarse bound on a higher-order derivative (typically requiring just a few additional simulations) [5]. Our estimates, $h_{\rm opt}$ , come with provable approximation bounds for the resulting mean-squared error between the finite difference estimate and the directional derivative of a smooth function,

$$\mathcal{E}(h_{\rm opt}) \leq \gamma \min \limits_{h\leq h_U} \ma... ...thbb{E} \left\{\left(\frac{f(x_0+hp)-f(x_0)}{h}-f'_s(x_0;p) \right)^2 \right\}.$$

An exciting aspect of this work is that we can obtain bounds on the number of correct digits in the noisy derivative estimate. For example, for forward differences, a typical approach is to use a multiple of the square root of the machine's precision. Our numerical experiments show that in many applications our estimate obtains 2-3 more digits of accuracy in the derivative than does the classical approach.

Here we use the symmetric positive definite matrices in the Florida Sparse Matrix collection [2] to define noisy, deterministic quadratics of the form

$$f(x) = \Vert y_{\tau}\Vert _2^2, Ay_{\tau}=x,$$

where $y_{\tau}$ is obtained using an iterative solver with tolerance $\tau$ . We consider Krylov solvers in MATLAB [1], but the numerical results are similar for other solvers.

We use these finite difference estimates to show how computational noise can destroy the accuracy of derived calculations, for example, the computation of derivatives. In some cases, the accuracy of derivative estimates based on function values is many times better than that of finite-precision evaluation of derivatives obtained by hand-coded or automatically differentiated codes. Our experiments also illustrate that the relationship between truncation errors and the computational noise can be surprisingly nonintuitive.