6
$\begingroup$

Can anyone point me to methods for varying $h$ in gradient estimation for noisy numerical optimization? Some programs have the user give a fixed $h$, which is used for forward-difference or central-difference gradient estimates the whole time, from initial roughly-linear slopes to roughly-quadratic valleys near a minimum. Surely there are adaptive methods that beat fixed $h$?

I'm looking for a simple method that's been used in practice, not theory.

Added 23 April: a couple of factors that make this interesting:

  • noise, scale of roughness, is difficult. Imagine hiking in rough country, wanting to get up high, but using only local gradients. There are obstructions — noise — at scales of millimeters, meters, kilometers; what's a good $h$ to measure roughness, not for its own sake, but to get up higher ?

  • say that each evaluation of f(x) costs \$1, so a gradient estimate in 10d costs \$10 or (centered) \$20. If you have only \$100 to spend, how could you tradeoff accuracy for money ? For example, instead of \$100 for 10 accurate gradients at 10 points, one could spend \$10 at x$_0$, then update only the biggest gradient component at x$1 \dots $ x${10}$, then \$10 again ... too many possiblities.

$\endgroup$
4
$\begingroup$

You are not as free in choosing step size $h$ as you maybe think. If the accuracy with which you can compute your function is $a$, then the proposed step size is $h = a^{1/2}$ for the forward difference formula and $h = a^{1/3}$ for the central difference formula.

So if the accuracy (e.g., internal functions) is 1e-15 then $h$ should be not much smaller than 1e-7 or 1e-5. The reason is that for very small step sizes the truncation and roundoff errors "step in" and the result will get more inexact. If a larger step size is chosen, one will get less accuracy than is available (like "money left on the table").

Changing step sizes according to how much the function is "bending" are not promising and have to my knowledge not been considered. The error terms of the computation itself forbid that.

Reference: Any textbook on numerical analysis that has a chapter on numerical differentiation.

Hint: If your function is analytical and the programming language allows complex arithmetics, the complex step derivation approach might be possible where you get almost the same accuracy for the numerical derivatives as for the function computation itself.

Update: I forgot to say that if you apply Romberg's method to compute the derivative, as some numerical programs do, it will (try to) settle down with an optimal step size by itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.