4 ms·

For a loop, you can unroll it and define the derivative that way. But you're correct in general that there are programs that have no sensible derivative but aut

For a loop, you can unroll it and define the derivative that way. But you're correct in general that there are programs that have no sensible derivative but automatic differentiation will still compute something. Going beyond AD there is a "differential lambda calculus" [1]. I don't really understand this work. It requires more background in programming languages, logic, and analysis than I have time to learn. My understanding is it allows you to compute more derivatives (e.g. for higher-order functions) and place conditions so only sensible derivatives are computed. There is also "differential linear logic" [2] which has some relation to the differential lambda calculus but it's unclear to me what that relationship is. So in summary I believe: 1. automatic differentiation will compute the correct derivative when such a thing is available, and some nonsense answer otherwise 2. to increase the space of programs for which derivatives can be computed and to rule out other programs you need to look at differential lambda calculus / linear logic. [1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.471.7213&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.471... [2]: https://arxiv.org/abs/1606.01642 https://arxiv.org/abs/1606.01642

improbable22 9y ago
Do you have a simple example of a loop with no sensible derivative? Or rather, of a loop computing something which should have one, but for which AD fails? If your loop is computing something like f(g(...h(x))) i.e. applying functions in sequence, starting with x, then there's no problem -- dual numbers will compute the correct derivative. If the loop is an implementation detail, like I think the poisson distribution p(λ,k) is often computed with a loop up to k... then making λ a dual number still works. Clearly you can't differentiate on k, because it's an integer.
- noelwelsh 9y ago
  I don't have a simple example (and I'm not claiming [some] loops do not have sensible derivatives). This talk from 27mins onwards discusses some of the issues if you're interested in diving in a bit deeper: https://www.youtube.com/watch?v=qhPBfysSYI8 https://www.youtube.com/watch?v=qhPBfysSYI8 I found it pretty heavy going. YMMV.
  - improbable22 9y ago
    Thanks! Will take a look.
mehrdadn 9y ago
> automatic differentiation will compute the correct derivative when such a thing is available, and some nonsense answer otherwise The problem is this is false too. Just modify my example a bit: y = x if x > 0 else x if x < 0 else 0 Here we clearly have y'(0) = 1, yet autodiff would seem to give y'(0) = 0.
- noelwelsh 9y ago
  Good point / example!

improbable22 9y ago

Do you have a simple example of a loop with no sensible derivative? Or rather, of a loop computing something which should have one, but for which AD fails? If your loop is computing something like f(g(...h(x))) i.e. applying functions in sequence, starting with x, then there's no problem -- dual numbers will compute the correct derivative. If the loop is an implementation detail, like I think the poisson distribution p(λ,k) is often computed with a loop up to k... then making λ a dual number still works. Clearly you can't differentiate on k, because it's an integer.

noelwelsh 9y ago
I don't have a simple example (and I'm not claiming [some] loops do not have sensible derivatives). This talk from 27mins onwards discusses some of the issues if you're interested in diving in a bit deeper: https://www.youtube.com/watch?v=qhPBfysSYI8 https://www.youtube.com/watch?v=qhPBfysSYI8 I found it pretty heavy going. YMMV.
- improbable22 9y ago
  Thanks! Will take a look.

mehrdadn 9y ago

> automatic differentiation will compute the correct derivative when such a thing is available, and some nonsense answer otherwise The problem is this is false too. Just modify my example a bit: y = x if x > 0 else x if x < 0 else 0 Here we clearly have y'(0) = 1, yet autodiff would seem to give y'(0) = 0.

noelwelsh 9y ago
Good point / example!