Example where autodiff works but symbolic differentiation will not?

Question

According to the survey paper on autodiff (linked) Autodiff works on inputs that cannot be specified in closed form but can be described by a sequence of code, each component of which is differentiable. Autodiff also works on code that can be symbolically differentiated but in this latter case the benefits are less obvious and more subtle. However, I haven't been able to come up with an example where autodiff works but symbolic diff will not work.

My question is: does there exist a simple example of autodiff with a code input that will not work with symbolic diff?

Note: I realize simple is somewhat arbitrarily defined so let's say in less than 20 lines of code so that the answer isn't too long to read. If 20 lines isn't enough then something like the minimal number of lines in code would work.

Answer 1

It's state-dependent control flow that's an issue.

function f(u)
  z = 0.0
  while z < 10.0
    z += u
    u += z^2
  end
  return u
end

What's the program for computing the derivative? Automatic differentiation would give you:

function f(_u)
  u = (_u,1.0) # seed the input derivative for the jvp in direction of basis e1
  z = (0.0,0.0)
  while z[1] < 10.0
    z += u
    u += (z[1]^2,2z[1]*z[2]) # by d(z^2)/dz = 2z
  end
  return u # first output is the primal, second is the derivative w.r.t. input
end

That's what dual number arithmetic will actually build under the hood. Now what's the symbolic derivative? You need to know what u is to know the full expression, so that's hard. If you know what the input value u was, the computational graph for the second term of the tuple is precisely the derivative w.r.t. the input _u, so if you knew how many times you'd loop, you could have this symbolic expression. With automatic differentiation this is okay because you only ever want values out, so there you go you get values from this program. But this program cannot tangibly give you the LaTeX to paste into your paper for the derivative w.r.t. any possible _u, which is why "it isn't symbolically differentiable".

So the moral of the story is, AD and symbolic differentiation is more the same than different. The way I generated that code is by symbolically taking the derivative of the steps of the program to build the program for the derivative as the second part of the tuple. But having a program that gives you symbolic expressions is not necessarily a satisfying answer to "give me the symbolic derivative".

Answer 2

The paper you linked answers the question. Autodiff (or hand differentiation) can differentiate branched program statements. For example, limiters, entropy fixes branching in flux statements, and the like. It can be rather helpful for min max statements as well. You can see an example below:

 Function(Vn_bar, a_bar, ul, cl, ur, cr)
   lambda1    = abs(Vn_bar-a_bar)
   lambda2    = abs(Vn_bar)
   lambda4    = abs(Vn_bar+a_bar)

   epsdummy   = max(lambda1-(ul-cl), (ur-cr)-lambda1)
   eps1       = max(0, epsdummy)
   epsdummy   = max(lambda2-ul, ur-lambda2)
   eps2       = max(0, epsdummy)
   epsdummy   = max(lambda4-ul-cl, ur+cr-lambda4)
   eps4       = max(0, epsdummy)

   if (lambda1 < eps1) lambda1 = .5_dp*(lambda1**2/eps1+eps1)
   if (lambda2 < eps2) lambda2 = .5_dp*(lambda2**2/eps2+eps2)
   if (lambda4 < eps4) lambda4 = .5_dp*(lambda4**2/eps4+eps4)
   y = sqrt(lambda1**2 + lambda2**2 + lambda4**2)
   do while(y < 10) 
      y = y**2
   end do
   return y

This is an example where we provide 6 inputs that we can differentiate with respect to (Vn_bar, a_bar, ul, cl, ur, cr) and a function y, whose derivative we are taking. You can see that we have many branch statements here, max and min functions and a loop, all dependent on the state itself. AD or hand differentiation can handle this, even though it doesn't have a real symbolic derivative.

Answer 3

An automatic differentiation program could be refactored to output a symbolic representation, instead of a numerical one. Therefore the 2 forms would be equivalent.

Please see the non-accepted answer here: https://stackoverflow.com/a/55607008/104910

Answer 4

AD is symbolic differentiation of each line of a computer code. But more useful since it gives you another computer code, you dont have to recode the derivative yourself.

If you have some exotic function whose derivative is not known to the AD tool you are using, then it cannot give you the answer of course.

If you have an explicit function, then symbolic diff can always be done, but becomes unwieldy/cumbersome/error-prone if you have a complex expression, as others have given example above.

Discontinuous functions will also be differentiated by AD by taking one sided derivative.

For example $f(x) = max(x,0)$ may be implemented in the code as

$$ f(x) = \begin{cases} 0 & x \le 0 \\ x & x > 0 \end{cases} $$

Then the AD will give the derivative as

$$ f'(x) = \begin{cases} 0 & x \le 0 \\ 1 & x > 0 \end{cases} $$

So even if branching is present in a code, there is an underlying symbolic derivative one can write down.

A more complex example is an implicit function $$ F(x,a)=0, \qquad y = G(x) $$ where $F$ is implemented as a computer code. Here you may not be able to write down an explicit formula for $dy/da$ ? Because there is no explicit formula for $x=x(a)$. Even AD cannot give you the derivative here since it does not know the function $x=x(a)$. In practice we get an approximation to $x$ say $x_h$ by applying some Newton method. $$ x_h = F_h^{-1}(a), \qquad y_h = G(x_h) $$ where $F_h^{-1}$ denotes the Newton method. Now AD can work, but there is also a symbolic derivative underlying it, but it is something you would rather not write down yourself.