3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Aug 24, 2011 at 19:04
  • 2
    $\begingroup$ Since $f$ is computable using finitely many arithmetic operations, it is (at least piecewise) a polynomial, right? $\endgroup$ Aug 24, 2011 at 19:16
  • $\begingroup$ @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? $\endgroup$ Aug 24, 2011 at 19:21
  • $\begingroup$ 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 $\endgroup$ Aug 24, 2011 at 19:41
  • $\begingroup$ 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 $\endgroup$ Aug 24, 2011 at 19:50

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Aug 26, 2011 at 0:31
  • 2
    $\begingroup$ I don't see how you could expect to do much better, since the output $\nabla f(x)$ has $n$ components. $\endgroup$ Aug 26, 2011 at 6:44
  • $\begingroup$ 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. $\endgroup$ Aug 26, 2011 at 21:20
1
$\begingroup$

With all due respect to Mr. Israel, his answer is incomplete and, I must apologize writing this, misleading. Let $f: \mathbb{R}^n \to \mathbb{R}^m$ so that the Jacobian $f'(x)$ is a $n \times m$ matrix for every $x$. Assume that $f(x)$ takes $T$ arithmetic operations to evaluate. Fix $x \in \mathbb{R}^n$.

Forward AD evaluates $f'(x)$ in $O(1)Tn$ arithmetic operations.

Reverse AD evaluates $f'(x)$ in $O(1)Tm$ arithmetic operations.

In your case, $m=1$ so the reverse mode evaluates $f'(x)$ in $O(1)T$ operations. This reverse mode AD is also known as "backpropagation" in machine learning, and is a key business strategy for several trillion dollar companies.

The $O(1)$ term was estimated by some illustrious mathematician, I apologize I can't find the reference now, but it's something like $O(1)=3$. So it's something like $3T$ arithmetic operations; barely more than what is needed to compute $f(x)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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