Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?)

share|improve this question
    
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 '11 at 19:04
2  
Since $f$ is computable using finitely many arithmetic operations, it is (at least piecewise) a polynomial, right? –  Emil Jeřábek Aug 24 '11 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 '11 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 '11 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 '11 at 19:50

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
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 '11 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 '11 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 '11 at 21:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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