## Complexity of computing derivatives

Sorry if this is too simple. This is my first question here.

Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point $x$. Can we use that to somehow precisely bound the time that is required to compute $\nabla f$? (Intuitively because of finite difference approximations, we might be able to do this, but is a precise statement available, or am I overlooking something obvious?)

-
I believe the answer is yes, and the bound is given by appropriate applications of the Chain Rule. You might look at algorithms for symbolic computation of the derivative, unless you want a numeric result. Then you can probably get a bound that is roughly exponential in the number of multiplications (or compositions perhaps) used in computing f. Gerhard "Ask Me About System Design" Paseman, 2011.08.24 – Gerhard Paseman Aug 24 2011 at 19:04
Since $f$ is computable using finitely many arithmetic operations, it is (at least piecewise) a polynomial, right? – Emil Jeřábek Aug 24 2011 at 19:16
@Gerhard, is exponential really the best possible? @Emil, good point. Maybe I should generalise to ask for the case when $f(x)$ is numerically approximatable to accuracy $\epsilon$? So if $f$ is essentially a polynomial, then we should be able to compute its gradient in cT operations for some constant $c$, is that true? – onemoreuser Aug 24 2011 at 19:21
I do not know what the bound is in general. I decided that giving a poor bound for a general situation was better, and to wait for "arithmetic operations" to be made explicit before offering improvements. For polynomials there should be better than exponential bounds, PROVIDED you are given a method like Horner's to evaluate the polynomial and the representation allows it. I suggested exponential because the chain rule requires you to compute two derivatives and at least two compositions from a function having a composition. Gerhard "Ask Me About System Design" Paseman, 2011.08.24 – Gerhard Paseman Aug 24 2011 at 19:41
As an illustration, consider (x - 7)^64. In some systems this will take over 60 operations to evaluate, while in others it will take less than 10. If you represent a function as a dataflow diagram with just-in-time evaluation, and use that to derive a similar diagram to represent computing the derivative, I see a potential for exponential blow up. The way in which you perform the T operations is important. Gerhard "Ask Me About Data Flow" Paseman, 2011.08.24 – Gerhard Paseman Aug 24 2011 at 19:50

The complexity is $O(nT)$. Look up "automatic differentiation" in Wikipedia. This is taking your statement about computing $f(x)$ in $T$ arithmetic operations literally: the "arithmetic operations" could include arbitrary powers and elementary functions such as exp, ln, sin, considered as single operations, as long as their derivatives can also be computed with a bounded number of operations. If approximations and errors must be taken into account, that's a whole different story.
 informally, $n$ times slowdown seems to be sufficient because of first-order taylor expansion. but is it really the best one can do? this is bad, I guess but maybe in practice one can get away with much lesser. – onemoreuser Aug 26 2011 at 0:31 I don't see how you could expect to do much better, since the output $\nabla f(x)$ has $n$ components. – Robert Israel Aug 26 2011 at 6:44 Is there a lower bound available? maybe that is the catch. it does not seem to be clear what kind of model of computation we are talking about here. – onemoreuser Aug 26 2011 at 21:20