7
$\begingroup$

Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary operation in a computer program, but I am not sure to get how this applies to every computer program.

To quote from this wikipedia page:

every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations

.. which I totally agree with. However, it sounds then that the number $m$ of variables newly produced from any $n$ initial input is fixed and can be determined from static code analysis. But this is not straightforward to me since constructs like:

if x_1 > x_2:                         # branching
    perform 4 elementary operations
else:
    perform 84 elementary operations
endif

and:

while x_1 < x_2:                      # looping
    perform 2 elementary operations
endwhile

do exist in so-called « complicated » computer programs. This make the number (and the type) of elementary operations not straightforward to compute in advance. And I even suspect it is impossible to gess that in general, right?

Does AD support such branching and looping programs?
Are there extensions of AD adapted to programs that are not just intricate closed-form expressions?
How does AD deal with Turing-completeness?

Improve this question
$\endgroup$
1
  • $\begingroup$ Judging from the examples, automatic differentiation supports general control structures as long as they only depend on fixed hyperparameters. In other words, your program should be equivalent to a sequence of fixed arithmetic operations, and then automatic differentiation works. $\endgroup$ – Yuval Filmus Feb 21 '17 at 18:23
10
$\begingroup$

AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be calculated (or variables depending on them). Here is an example:

if x = 3 then 9 else x * x

At close inspection you will recognize that the above is really just an inefficient way of implementing $x*x$. If you evaluate this program at $x = 3$, then the result is the constant $9$. But the derivative of constants is zero, which is obviously not the right answer, which should be $6$.

The reason is that AD will typically only look at the executed branch of your program. It is perfectly ok to have branches on conditions that don't involve numbers, or conditions involving number variables not part of the computational graph for derivative calculations. It's also ok to look at fixed properties of derivative values (e.g. the dimension of a vector). But as soon as you "look" at the contents of a variable that depends on one of the inputs to determine what calculation to perform next, you will "break the chain". AD does basically just that: apply the chain rule.

Users of AD should view programs as "configuring" a fixed computational graph. If running the program with different inputs for which derivatives are requested gives you different computational graphs, AD may not always give the correct result.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ So, if I understand well, branches and loops should should not depend on the content of variables.. To me, this can be reformulated as: "the program should be closed form".. or "the program could be rewritten with no loops" or "the program terminates in a known number of steps", am I right? This is quite a restricted subset of "every computer program", is it not? $\endgroup$ – iago-lito 'considering leaving Feb 22 '17 at 9:34
  • 1
    $\begingroup$ Obviously, one can only calculate derivatives of a program that terminates. You do not need to know the number of steps beforehand. No matter how long it runs, eventually you will have a computational trace of everything that happened. AD (reverse-mode) looks only at the trace of operations that affect derivatives, inferring a computational graph from it. You can then interpret the graph backwards using the chain rule to obtain gradients. The important requirement is that the graph must remain the same even if you changed the value of arguments for which you want to calculate gradients. $\endgroup$ – Markus Mottl Feb 23 '17 at 14:54
  • $\begingroup$ So, there is nothing to do for derivable functions for which I can write a program that both terminates in all cases but whose graph is still not the same when I change the arguments, right? For instance: take a smooth function $f : \mathbb{R}^2 \rightarrow \mathbb{R}$ for which each point is the result of a limit or an integration operation. Then if I write an adaptive iterative program P(a, b) that approximates $f(a,\ b)$ with a control flow which depends on the given value of (a, b) (for adaptive precision or efficiency, say), P cannot be analysed with AD, right? $\endgroup$ – iago-lito 'considering leaving Feb 23 '17 at 15:40
  • 1
    $\begingroup$ Lets assume you have an iterative optimization algorithm that checks a value for convergence. That's a problem, because if you pass arguments that are already optimal, there will be only one iteration of the algorithm, i.e. a small computational graph. In order to "fix" the graph in a meaningful way, you could pass an iteration limit rather than a convergence criterion. In my experience most algorithms can be rewritten such that AD will do the right thing. It's certainly not the case that you can throw AD at any program that wasn't written with AD in mind and always expect sound results. $\endgroup$ – Markus Mottl Feb 24 '17 at 16:22
  • $\begingroup$ Okaay! :D So this is how I understand it: if your program (should it be adaptive) does terminate in all cases, then there exist a finite upper bound to the number of steps it'll perform. So you may refactor it so that it performs exactly this many steps and follow the same graph, no matter the data given as an input.. should you fill up the graph with dummy operations in this purpose. Too bad we cannot enjoy the adaptiveness computational gain then.. but I think I've got it. Cheers :) $\endgroup$ – iago-lito 'considering leaving Feb 24 '17 at 16:32
5
$\begingroup$

If you want the derivative everywhere, automatic differentiation can't handle branches and loops. If you are satisfied with getting the derivative "almost everywhere", automatic differentiation might be fine for some programs with (some kinds of) branches. For some kinds of optimization, this is sometimes good enough.

Automatic differentiation can support at least some branches and if-statements, but with the caveat that it might fail (or the derivative might fail to exist) at the "boundary" of the conditional statements.

Consider your case where we branch if x_1 > x_2, and suppose we are calculating the derivative with respect to x_1 at a particular point (x_1, x_2). Then if the branch is true at that point, we calculate the derivative of the true-branch with respect to x_1. If the branch is false at that point, we calculate the derivative of the false-branch with respect to x_1. (If x_1 == x_2, we might have a discontinuity and the derivative might not be defined.)

Why does this work? Consider the function

$$f(x) = \begin{cases} g(x) &\text{if $x>c$}\\ h(x) &\text{otherwise} \end{cases}$$

Then its derivative is

$$f'(x) = \begin{cases} g'(x) &\text{if $x>c$}\\ h'(x) &\text{otherwise} \end{cases}$$

with a possible discontinuity at $x=c$.

For conditionals with an equality comparison, things might fail at the value where equality holds (at the boundary value). For conditionals with $\le$ or $<$ or $\ge$ or $>$, things might fail at the boundary/threshold value, but it works elsewhere, I think.

Looping is harder, I think.

Markus Mottl's answer is better than mine; see his answer for explanation of why branches and loops are problematic for automatic differentiation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Okay for "almost everywhere". This limitation sure sounds natural: AD will obviously fail to compute derivative where there is no derivative, who would blame that ;) I'll have a look at Markus Mottl's answer. $\endgroup$ – iago-lito 'considering leaving Feb 22 '17 at 8:45
  • 1
    $\begingroup$ @iago-lito, yes, but the limitation is a bit worse than that: it might also fail to compute the correct derivative at the boundary/threshold points, even if a derivative does exist (i.e., a derivative might exist, but it might output the wrong value). That is a bit less desirable. $\endgroup$ – D.W.♦ Feb 22 '17 at 16:45
  • $\begingroup$ That is a bit less desirable indeed. :\ $\endgroup$ – iago-lito 'considering leaving Feb 22 '17 at 16:47

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.