1
$\begingroup$

What is the difference (in terms of e.g robustness and speed) between proving a gradient obtained by an AD package (like PyAutoDiff) and let the solver (e.g BSGS) calculate the gradient ? It seems so tempting to do something like:

from autodiff import gradient

def my_costfun(x):
    return f(x)

@gradient
    def g(x):
    return f(x)

Is that really that simple ? What about functions with, lets say 10 parameters ?

$\endgroup$
1
$\begingroup$

If the cost function is complex or has lots of parameters, calculating the gradient with automatic differentiation can grow in cost rapidly. Often exact gradients aren't needed (especially far from the minimum), and so other strategies may be much, much cheaper.

$\endgroup$
8
  • $\begingroup$ But i have to do that just once ? $\endgroup$
    – Moritz
    Feb 4 '15 at 16:14
  • $\begingroup$ You have to evaluate the new, perhaps very complicated and expensive gradient function, many, many times usually. You only have to construct this function once, but the number of operations required to evaluate it may be many, many times more costly than the BFGS update formula (for example). $\endgroup$
    – Bill Barth
    Feb 4 '15 at 16:20
  • $\begingroup$ I guess i have to start reading a book about optimization. It is so simple to just use that stuff, but only for very simple problems. $\endgroup$
    – Moritz
    Feb 4 '15 at 16:21
  • $\begingroup$ Well, you can always try it. Also, as many around here like to point out, try reading Nocedal and Wright. $\endgroup$
    – Bill Barth
    Feb 4 '15 at 16:24
  • $\begingroup$ @BillBarth: Forward mode AD can be expensive; reverse (adjoint) mode AD is usually a small multiple of the cost of a function evaluation (the number usually quoted from theory is 3-5x, but I've seen implementations claiming 10-35x). The difficulty with inexact gradients is that noise (specifically, ill-conditioned function evaluations) can degrade severely the accuracy of the finite difference approximation, and hamper convergence of gradient-based optimization methods. (See Lemma 9.1 of Nocedal and Wright.) Proper application of AD should give accurate gradients, but introduces other issues. $\endgroup$ Feb 4 '15 at 20:07
1
$\begingroup$

Disclaimer: I'm going to talk in generalities about AD packages, not PyAutoDiff.

Finite Differences

Pros:

  • Easy to implement
  • Useful for testing whether analytical gradient routines or AD give the right result
  • If you can reimplement your function to take complex number inputs, there's a trick that will give you nearly exact gradients
  • Non-intrusive
  • Good enough accuracy in many cases

Cons:

  • Can be noisy; ill-conditioned functions can lead to inaccurate finite difference approximations
  • For quasi-Newton methods that use Hessian updates derived from gradients (e.g., BFGS-type methods), noise in gradient is propagated into Hessian.
  • Expensive: for a function of $n$ variables, requires $n$ function evaluations
  • There's a bit of an art to choosing the magnitude of the difference used in the denominator of the quotient
  • Even if sufficiently accurate, the noise can slow convergence of optimization methods.

Automatic Differentiation

Pros:

  • Returns nearly exact gradients
  • Reverse mode is cheap ("3-5x" a function evaluation in theory, but in practice, it's an implementation-dependent multiple bounded above by a constant)
  • Can analyze very complicated functions
  • Avoids potentially time-consuming derivations of gradient functions

Cons:

  • Forward mode is expensive; scales with # of input variables
  • Heinous to implement yourself; you should definitely rely on a library
  • The method is intrusive -- it requires source-code access
  • Source-to-source translation methods can analyze source code automatically, but can return ludicrously obfuscated code; more to the point, these methods frequently cannot differentiate the code they generate, so you're usually limited to derivatives of order 1.
  • Operator overloading approaches require rewriting your code to use the overloaded operators; this process can be time-consuming
$\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.