[tomsmeding]

Context: I'm writing an autodiff algorithm, and that's the thing I want to test.

> one strategy to consider would be to build the error bound computation as a function into your math operations

That's autodiff! :D The error (change) in a function's output given an error (change) in its input is the definition of its derivative.

So I guess I can use my autodiff algorithm to compute the error bounds for testing my autodiff algorithm! ... Uhm.

Actually, though, I want _one_ error bound, not one that varies per run. But I guess you can do the same thing symbolically: you just end up with

1. a slightly-too-optimistic bound because you will (for practicality) discard higher-order e terms;

2. a conservative bound because you'll be pessimistic in the face of control flow, array sizes, etc. where the precise operations performed depend on the input.

I guess this symbolic approach works until you have unbounded sequential loops (which pessimistically have unbounded error, because it may accumulate indefinitely). Or perhaps it breaks down already with arbitrary-size arrays; what is rhe error bound on `lambda x. sum([x]*n)`, assuming n is unknown? (Using python syntax as "universal syntax".)

> then you can query the error from a parse tree of different math ops, or something like that.

If there is no dynamic control flow nor variable-size data structures etc. in that parse tree, I suspect they do kind of what I hand-wavingly described above.

It's not perfect enough that I'm going to implement this approach immediately (variable-size arrays are kind of core to what I want to do). But perhaps there's some trick I can pull out of this. Thanks for the ideas!

[dahart]

> That's autodiff! :D The error (change) in a function's output given an error (change) in its input is the definition of its derivative

Ah but the error of your autodiff math isn’t the same thing as the error of the function you’re autodiffing! And the math error isn’t even a derivative. Specifically, the absolute value handling of rounding error analysis will cause the error bounds to diverge from being proportional to the function and/or derivative values.

I assume your unknown sum sizes are eventually finite… otherwise you won’t get an answer? Evaluating the rounding error will just take the same time as evaluating your sum. Long sums, btw, are bad for precision. Typically people try to sort them or compute them in hierarchical/ butterfly reduce fashion, or use other tricks.

[tomsmeding]

> Specifically, the absolute value handling of rounding error analysis will cause the error bounds to diverge from being proportional to the function and/or derivative values.

Oh, I see! Not quite autodiff then, indeed.

> Long sums, btw, are bad for precision. Typically people try to sort them or compute them in hierarchical/ butterfly reduce fashion, or use other tricks.

Typical parallel reduction algorithms do precisely this, but for different reasons (parallelisation). I guess I'd have to compute a partially symbolic expression for the error bound depending on the array size, and hope that I'm not going to change the parallel reduction algorithm without changing the error bounds in tests.

It's possible, but finicky. I see why people slap simple relative bounds on things and call it a day. :)

[dahart]

There’s probably a way to get a stable conservative error bound for a parallel sum reduction that’s non-deterministic.

Here’s the PBR book’s chapter on error analysis. It’s way easier to implement error bound tracking than it is to come up with symbolic bounds, and it’s way better than having nothing or even a guess pulled out of thin air. It’s probably worth trying, just to see what happens, it might be surprising. Plus if you implement the error bounds, you may find very interesting and/or enlightening ways to visualize them.

https://pbr-book.org/4ed/Shapes/Managing_Rounding_Error#

[tomsmeding]

Thanks a lot for the insights!