9
$\begingroup$

Is it pointless to use gradient based optimization algorithms if you can only provide a numerical gradient? If not, why provide a numerical gradient in the first place if it is trivial to perform finite differentiation for the optimization library itself?

[EDIT]

  • Just to clarify, my question indeed is in a more general sense than a specific application. Although my field of application happens to be likelihood optimization under various statistical frameworks.

  • My issue with automatic differentiation is that there always seems to be a catch. Either the AD library can't propagate to external library calls (like BLAS) or you have to rework your workflow so drastically that it makes it a pain to deal with... especially if you're working with type sensitive languages. My gripes with AD are a separate issue altogether. But I want to believe!

  • I guess I need to better formulate my question but I'm doing a poor job of it. If have an option to either use a derivative-free optimization algorithm or a derivative based optimization algorithm with the caveat that I can only give it a numerical gradient, which one on average will be superior?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Are you trying to ask why would one provide an analytical gradient instead of just computing an approximate one using finite differences? $\endgroup$ – spektr Jul 19 '16 at 3:29
  • 1
    $\begingroup$ My question is, stated another way, suppose your equations are way too involved for you to compute analytical gradients, can gradient dependent optimization algorithms still be superior to ones that do not require gradients at all? $\endgroup$ – professor bigglesworth Jul 19 '16 at 3:38
  • $\begingroup$ That is a different question that the one you posed above. You might be able to compute numerical derivatives by other means, e.g., finite elements. $\endgroup$ – nicoguaro♦ Jul 19 '16 at 20:24
  • 1
    $\begingroup$ @nicoguaro Yes, in the context of optimization with partial differential equations, that is certainly the case (and, this being one of my research areas, that was my first thought as well). But the question doesn't mention anything in that direction (and is more useful in this generality. I think). $\endgroup$ – Christian Clason Jul 19 '16 at 21:37
  • 1
    $\begingroup$ Also, even in that case, it's a reasonable question: What if your (system of) PDE(s) is so complicated that you can't derive an adjoint equation to be numerically solved to obtain the gradient? (These things can get quite nasty, especially if non-standard boundary conditions are involved.) $\endgroup$ – Christian Clason Jul 19 '16 at 21:43
10
$\begingroup$

To complement Brian's excellent answer, let me give a bit of (editorial) background. Derivative-free optimization methods are defined as methods that only make use of function evaluations, and are basically all variations of "sample the admissible set more or less systematically and save the best function value" -- that's all you can do given the information. These methods can be roughly subdivided in

  1. Stochastic methods, where the selection of samples is fundamentally random (meaning that randomness is a crucial component; there can be other, deterministic components). These methods are often motivated by physical or biological processes and have corresponding names like "simulated annealing", "genetic algorithms", or "particle swarm/firefly/anthill method". There is rarely any convergence theory beyond "if you try long enough, you will hit all points (including the minimizer) with probability $1$" (whether that will happen -- with any probability -- before the heat death of the universe is another matter...) As a mathematician, I would consider these methods as a last resort: If you don't know anything about your function, this is all you can do, and you might get lucky.

  2. Deterministic methods, where the selection of samples is not random, i.e., based purely on previous function evaluations. The most famous example is probably the Nelder--Mead simplex method; others are generating set search methods. It is important to realize that this can only work if there is any (exploitable) relation between the value of the function at different points -- i.e., some smoothness of the function. In fact, the convergence theory for, e.g., the Nelder--Mead method is based on constructing a non-uniform finite-difference approximation of the gradient based on the function values at the vertices of the simplex and showing that it convergences to both the exact gradient and zero as the simplex contracts to a point. (The variant based on a standard finite-difference approximation is called compass search.)

  3. Model-based methods, where the function values are used to build a local model of the function (e.g., by interpolation), which is then minimized using standard (gradient-/Hessian-based) methods. Since a finite difference approximation is equivalent to the exact derivative of a polynomial interpolant, the classical "numerical gradient" approach falls into this class as well.

As you can see, the boundaries between these classes are fluid, and often just a matter of interpretation. But the moral should be clear: Make sure you use all available information about the function you're minimizing. To quote Cornelius Lanczos:

A lack of information cannot be remedied by any mathematical trickery.

After all, if you don't know anything about your function, it might as well be completely random, and minimizing a random value is a fool's errand...

|cite|improve this answer
$\endgroup$
17
$\begingroup$

If your objective is smooth, then using finite difference approximations to the derivative is often more effective than using a derivative free optimization algorithm. If you have code that computes the derivatives exactly then it is normally best to use that code rather than to use finite difference approximations.

Although some optimization libraries will compute finite difference approximations for you automatically using heuristics to determine the step size parameters, it can be better to use your own routines to compute the finite difference approximations either because you have better knowledge of the appropriate step sizes or because of special structure in the function that your code can exploit.

Another option that is often worth while is to use automatic differentiation techniques to produce a subroutine that computes the analytical derivatives from the source code for computing the objective function itself.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ +1 for automatic differentiation. This is often much better than either an a-priori symbolic expression for the gradient or a finite-difference approximation. $\endgroup$ – leftaroundabout Jul 19 '16 at 9:19
  • $\begingroup$ I would also recommend using automatic differentiation. For fortran, try tapenade from INRIA Sophia-Antipolis, which is based on source transformation. For C/C++, there is more choice like adol-c, adept, sacado (part of Trilinos). All of these are based on operator overloading and easier to use, though not very efficient for very large problems. $\endgroup$ – cpraveen Jul 19 '16 at 14:10
  • $\begingroup$ There are also some circumstances in which automatic differentiation (AD) may be difficult to apply, but complex step differentiation, which can sometimes amount to almost the same thing as AD (other than being able to compute an entire gradient at once by the reverse mode of AD) may be applicable and relatively easy to apply. $\endgroup$ – Mark L. Stone Jul 19 '16 at 23:39
  • $\begingroup$ In response to the revised question: If your objective is smooth (there's no point in using a derivative based optimization algorithm if it is not) and if the number of variables is reasonably small (doing finite difference derivatives doesn't work in PDE constrained optimization), then most likely you'll be better off using a derivative based optimization method with finite difference approximations rather than using a DFO technique. $\endgroup$ – Brian Borchers Jul 20 '16 at 3:51
4
$\begingroup$

Your question asks about gradient-based optimizers, so I think Brian was right on. I would only share, since I am currently struggling with that myself, some of the issues.

The problems with finite difference are 1) performance, because you have to re-evaluate the function again for each dimension, and 2) it can be tricky to choose a good step size. If the step is too large, the assumption of linearity of the function may not hold. If the step is too small, it may run into the noise in the function itself, because derivatives amplify noise. The latter can be a real problem if the function involves solving differential equations. If it is possible to calculate the gradients analytically, or using sensitivity equations, it will certainly be more accurate and maybe faster.

There's another approach that you can try if you haven't invested too much time already in the software, and that is to run it with complex arithmetic. It's called complex step differentiation. The basic idea is when you evaluate the function, if you want its gradient with respect to parameter X, you set the imaginary part of X to a very small number eps. After you do the calculation, the imaginary part of the function's value, divided by eps, is the gradient with respect to X. When you want the gradient with respect to Y, you have to do it all again, of course. What's interesting about it is that eps can be made very small. The reason it works is that the normal rules of differential calculus are precisely mirrored in the rules of complex arithmetic.

That said, I regard it as not a panacea, because it's not always easy to do a complicated function in complex arithmetic, it's not worth it if the gradient can be calculated analytically, and in the case of differential equations it's exactly equivalent to sensitivity equations, which I'm doing as necessary.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think one of the main benefits is the fact that you aren't doing any subtractions in this complex finite difference formula. When I read a paper a while ago talking about derivations for this method, that was one of the points they seemed to validate experimentally compared to other finite difference formulas. This difference allowed smaller step sizes to be chosen before round-off errors became a problem. $\endgroup$ – spektr Jul 20 '16 at 19:21
  • $\begingroup$ @choward: Right. That's what's pretty about it. I was skeptical though. Some of my colleagues seemed to think it was a magic bullet. I suspected it was equivalent to sensitivity equations, and one of my co-workers, an applied mathematician, proved it. $\endgroup$ – Mike Dunlavey Jul 21 '16 at 0:04
  • $\begingroup$ That's cool about the sensitivity equation. This is an interesting approach but it certainly can have its implementation trade offs. Assuming you want to use it, you have to define complex versions of your functions and then do the additional complex variable algebra/computations, which does make each function evaluation longer. It's one of those things you'd have to figure out if the slower function evaluation is worth the added derivative accuracy. $\endgroup$ – spektr Jul 21 '16 at 0:19
  • $\begingroup$ @choward: That's the conclusion I came to, plus we usually optimize a vector, which means repetitive evaluation. Of course, the alternative is that sensitivity equations can be tricky to derive. I use symbolic differentiation, and they're still tricky. The whole subject is a bit of a mine field. $\endgroup$ – Mike Dunlavey Jul 21 '16 at 12:48

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.