# Optimization: Providing gradients by autodifferentiation e.g PyAutoDiff

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)

def g(x):
return f(x)


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

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.

• But i have to do that just once ? Feb 4 '15 at 16:14
• 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). Feb 4 '15 at 16:20
• 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. Feb 4 '15 at 16:21
• Well, you can always try it. Also, as many around here like to point out, try reading Nocedal and Wright. Feb 4 '15 at 16:24
• @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. Feb 4 '15 at 20:07

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.