5 ms·

Gradients Are the New Intervals

147 points by surprisetalk 1y ago

kragen 1y ago
This is very exciting! It seems like a lot of the interval stuff is bringing to fruition my idle speculations from 6 years ago in https://dercuano.github.io/notes/interval-raymarching.html https://dercuano.github.io/notes/interval-raymarching.html. I'll have to read this carefully to see if it's actually the same approach or a different one that uses the same algebras.
- mkeeter 1y ago
  Interesting post, thanks for the link! You may also enjoy "Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysis", which uses interval arithmetic (ish) to raymarch neural implicit surfaces: https://arxiv.org/abs/2202.02444 https://arxiv.org/abs/2202.02444
  - kragen 1y ago
    That's fantastic, thanks! I didn't know about neural implicit surfaces at all.
fph 1y ago
One of the benefits of intervals is that you can ensure your results are correct irrespective of floating-point errors, if you carefully round all computations in the correct direction. I don't think you can ensure that with gradients though: if f and f' are computed in machine arithmetic, cancellation errors might pile up.
- kragen 1y ago
  It's true; this is a different application of interval arithmetic, not the usual application, which is, as you say, to avoid numerical stability issues. By and large, graphics researchers don't give a shit about numerical stability issues. They're the Ed Woods of numerical computation.
  - sfpotter 1y ago
    The point of interval arithmetic isn't really to deal with numerical stability, per se... it's to make it possible to do rigorous and validated computations on a computer. Numerical stability is a different concept that is somewhat orthogonal. I could carry out a numerically unstable computation using interval arithmetic, but using interval arithmetic wouldn't magically make the computation stable, it would just give you error bounds (which may indeed be quite loose and unhelpful if the algorithm is unstable).
    - kragen 1y ago
      From my point of view, the problem with numerical instability is that your program computes the wrong answer, and, worse, gives you no clue that it's wrong. Interval and other self-validating methods do fix that problem: the answer may not be useful, but at least it's not wrong, and they tell you there has been trouble.
      - sfpotter 1y ago
        Yeah, I'd generally agree with that. One thing to bear in mind, though: there are numerical algorithms which are stable and unimpeachably useful but which are unstable in interval arithmetic owing to the natural interval inclusion behaving poorly. A great example of this is the Clenshaw recursion for evaluating Chebyshev series. It is the method of choice for evaluating a Chebyshev series at a single point, but the corresponding natural interval inclusion is actually unstable itself (the width tends to blow up exponentially fast in the degree of the series, regardless of the coefficients). I tend to view "classical numerical methods" and interval arithmetic as somewhat different camps. There's definitely a significant overlap and they can both profit from each other, but you need to put on a different hat when you're doing each. Sometimes interval arithmetic is just too expensive, in which case you need to select a good, stable numerical algorithm. On the other hand, if you're doing interval arithmetic because you must (you need a certified, correct answer), then you will often need to use a completely different set of algorithms and spend some time fussing over what the most appropriate interval inclusion is. Again, another good example here relates to Chebyshev series. If you want to find all of the roots of an analytic function on an interval, expand it in a Chebyshev series and solve the colleague matrix eigenvalue problem. The result could be subtly wrong due to numerical roundoff, and you'd have a hard time recovering from this position; but this method is undeniably extremely useful. On the other hand, if you want to compute rigorous enclosures of all zeros of that same analytic function, you'd need to develop a suitable interval inclusion for it, and then run some type of interval rootfinding algorithm based on a combination of interval contractors (Krawczyk) and subdivision. Basically, a branch and bound algorithm.
- constantcrying 1y ago
  >I don't think you can ensure that with gradients though: if f and f' are computed in machine arithmetic, cancellation errors might pile up. Yes, you can. You need to do automatic differentiation with interval arithmetic. This gives you a mathematically correct result for the derivative. Always keep in mind with interval arithmetic that (-inf, inf) is also a mathematically correct result. Keeping intervals small is the challenge with interval arithmetic and means that every algorithm not specifically developed for it is likely going to lead to useless results.
  - helltone 1y ago
    I think perhaps this could be done in other ways that don't require interval arithmetic for autodiff, only that the gradient is conservatively computed, in other words carrying the numerical error from f into f'
    - deleted 1y ago
      [deleted]
    - fph 1y ago
      But the only way we know how to make "conservative computations" is via interval arithmetic.
      - helltone 1y ago
        No? Or maybe I'm missing something. If the goal is to be able to bound the computation of f, you can: 1) compute f with interval arithmetic 2) compute f normally and f' with interval arithmetic 3) compute f rounding towards zero, compute f' from f rounded towards infinity, and round f' up (if f positive) or round f' down (if f negative). In all 3 cases you can use what you computed to figure out bounds on f, (1) is direct, the other two need extra work.
  - kragen 1y ago
    This doesn't help if your computation for f is numerically unstable, unless you compute f with interval arithmetic too.
3abiton 1y ago
It started interestingly, but then > This blog post assumes a vague understanding of implicit surface rasterization, and how interval arithmetic is used to both skip regions of space and simplify complex expressions. Can anyone give me a quick rundow of the article?
- meindnoch 1y ago
  Which part do you not understand? An implicit surface is defined by F(x,y,z) = 0. Implicit surfaces can be rendered by checking whether the camera ray going through pixel x,y intersects the surface or not. An axis-aligned bounding box (AABB) in 3D is the product of intervals [x_min, x_max]x[y_min, y_max]x[z_min, z_max]. The interval extension of F(x,y,z) gives you an interval [F_min, F_max] for such an AABB. If [F_min, F_max] doesn't contain 0, then you can discard the whole AABB for rendering purposes, because the surface is guaranteed to be not there. This can speed up rendering substantially.
  - 3abiton 1y ago
    Kudos for replying, that's already quite helpful.
constantcrying 1y ago
>In this case, "the Lipschitz property" means that the gradient of the distance value is bounded This is total nonsense. The point of Lipschitz continuity is that it is more than continuity and less then differentiability. If you assert that it is differentiable the concept looses all meaning. It is specifically interesting because you do not have to assert differentiability.
- porridgeraisin 1y ago
  Yes. I think the author meant that the rate of change is bounded [without the function needing to be differentiable] but used the term "gradient" anyways. I guess you shouldn't use the term "rate of change" either? I guess The Lipschitz property means the function's output doesn't change faster than linearly with input Is precise in that context
  - constantcrying 1y ago
    He even gives the definition for the L=1 Lipschitz condition afterwards. Lipschitz continuity means the differential quotient is globally bounded (where it exists). Differentiability, by definition, means the differential quotient converges at every point. These are somewhat related, but different things.
- kragen 1y ago
  There are functions that are differentiable, but not Lipschitz, e.g. sin(1/x) on (0, ∞)). In this context the Lipschitz property allows you to do things that mere differentiability doesn't, and, in the context of assuming that your function is differentiable, the definition given for the Lipschitz property is correct. It's true that there are also functions that are Lipschitz-continuous but not differentiable, but in this context they aren't interesting.
  - constantcrying 1y ago
    > It's true that there are also functions that are Lipschitz-continuous but not differentiable, but in this context they aren't interesting. They absolutely are, even in the article. E.g. the max function or the 1-norm are non-differentiable, but continuous. There is literally no point in talking about Lipschitz continuity for differentiable functions, because it is equivalent to the derivative being bounded.
yorwba 1y ago
The suggested normalization procedure, even with the ad-hoc fix for gradient discontinuities, doesn't actually ensure that the resulting function is 1-Lipschitz unless the gradient of the gradient magnitude vanishes. The signed-distance functions considered in the article seem to have piecewise constant gradient magnitudes (so are L-Lipschitz, just with L > 1) except for inside the "r", but for less well-behaved functions, higher order derivatives might start to matter.
- kragen 1y ago
  This is a good point!
- meindnoch 1y ago
  Sure, but signed distance fields by definition have a constant gradient magnitude, aren't they? They measure the distance from the surface, which grows linearly in the normal direction. But it is true that general implicit surfaces don't necessarily have constant magnitude gradients. I.e. F(x,y) = x^2 + y^2 - 1 vs. F(x,y) = sqrt(x^2 + y^2) - 1
diabllicseagull 1y ago
I've worked on a patent some years ago about SDF CSG Tree pruning and constant radius filleted blends. Sadly patents don't get the same visibility journals enjoy. https://patentimages.storage.googleapis.com/7a/73/2d/8d2eecadc278b2/US10083264.pdf https://patentimages.storage.googleapis.com/7a/73/2d/8d2eeca...
- marcosdumay 1y ago
  If you are after visibility, you can always do both. Bot any patent will push people away from your work.
- jacobolus 1y ago
  In theory, the purpose of a patent is to encourage sharing inventions so people can build on each-others' work. In practice, the modern purpose of a patent is to claim ownership over ideas and block further innovation so the author can extract rents via the court system; they are typically written to be as vague and inscrutable as possible to help cover a wider range of possible alternative inventions someone else might come up with, with no incentive for clarity. There's generally little reason for someone who isn't a lawyer to read a patent that hasn't expired yet – still a decade away in this case. A paper is usually better: the goal is very explicitly sharing knowledge, and there are peer reviewers and editors whose job is to make sure the writing is clear.
  - mitthrowaway2 1y ago
    One reason for reading patents that haven't expired yet is if you're trying to evaluate an offer from a startup which has patents on their core technology. It can be worth understanding how strong or weak their technology position is.
    - deleted 1y ago
      [deleted]
  - deleted 1y ago
    [deleted]
guyomes 1y ago
A generalisation of this idea is known as Taylor model in 1998 [1]. It might even have been known in 1984 as neighborhood arithmetic [2]. The generalisation works by taking a Taylor expansion of the function up to order n, and then by using a bound for the remainder using bounds on the partial derivatives of order n+1 [3]. [1]: https://www.bmtdynamics.org/cgi-bin/display.pl?name=rdaic https://www.bmtdynamics.org/cgi-bin/display.pl?name=rdaic [2]: https://books.google.fr/books?id=2zDUCQAAQBAJ https://books.google.fr/books?id=2zDUCQAAQBAJ [3]: https://en.wikipedia.org/wiki/Taylor%27s_theorem#Taylor's_theorem_for_multivariate_functions https://en.wikipedia.org/wiki/Taylor%27s_theorem#Taylor's_th...
- sfpotter 1y ago
  Worth pointing out that these ideas were already well known by Moore, the founder of interval arithmetic. Chapter 3 of his monograph "Methods and Applications of Interval Analysis" has the basic ideas worked out. The folks working on the Taylor model were coming from physics where they had some nasty (very ill-conditioned) nonlinear systems that they needed to solve and developed a package called COSY which implements it. My understanding is that the Taylor model is effective in practice, but there might have been some confusion around what it was actually capable of. I believe the Taylor model people claimed that their interval inclusions had better than quadratic excess, but this turned out not to be the case. Other people were able to push past the quadratic limit of the well known interval inclusions using other techniques. There are some recent papers by Hormann and Yap along these lines, although I think the first interval inclusion that is better than quadratic dates back further...
  - yorwba 1y ago
    I assume "recent papers by Hormann and Yap" is a reference to e.g. Range functions of any convergence order and their amortized complexity analysis https://www.inf.usi.ch/hormann//papers/Hormann.2023.RFO.pdf https://www.inf.usi.ch/hormann//papers/Hormann.2023.RFO.pdf ? Cool stuff.
    - sfpotter 1y ago
ajkjk 1y ago
Don't know much about this kind of thing, but it seems like it would be useful, if possible, to store the actual displacement (dx,dy) vector to the surface instead of just its magnitude, the SDF. I can't evaluate the tradeoff of storing an extra value, but it seems like it would make the recursion in the first section a lot easier: when you want to test if a particular box contains the object, if [v+d, v-d] contains 0, you would know a lot more where to look: you need only continue the iteration on subdivisions that are in the correct direction.
sfpotter 1y ago
Cool post. The Lipschitz trick here relies on the assumption that the gradient has magnitude 1 everywhere. Evaluating the SDF in a box and using the Lipschitz property lets you get some quick estimates on the range of the SDF over the box. This is a close cousin of the monotonicity interval inclusion: e.g., if f'([a, b]) > 0, then f([a, b]) is a subset of [f(a), f(b)]. Rounded interval arithmetic makes this rigorous on a computer; you can also do it in multiple dimensions, with higher derivatives, successively tightening inclusions for lower derivatives, etc.

147 points by surprisetalk 1y ago

This is very exciting! It seems like a lot of the interval stuff is bringing to fruition my idle speculations from 6 years ago in https://dercuano.github.io/notes/interval-raymarching.html https://dercuano.github.io/notes/interval-raymarching.html. I'll have to read this carefully to see if it's actually the same approach or a different one that uses the same algebras.

mkeeter 1y ago
Interesting post, thanks for the link! You may also enjoy "Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysis", which uses interval arithmetic (ish) to raymarch neural implicit surfaces: https://arxiv.org/abs/2202.02444 https://arxiv.org/abs/2202.02444
- kragen 1y ago
  That's fantastic, thanks! I didn't know about neural implicit surfaces at all.

fph 1y ago

One of the benefits of intervals is that you can ensure your results are correct irrespective of floating-point errors, if you carefully round all computations in the correct direction. I don't think you can ensure that with gradients though: if f and f' are computed in machine arithmetic, cancellation errors might pile up.

kragen 1y ago
It's true; this is a different application of interval arithmetic, not the usual application, which is, as you say, to avoid numerical stability issues. By and large, graphics researchers don't give a shit about numerical stability issues. They're the Ed Woods of numerical computation.
- sfpotter 1y ago
  The point of interval arithmetic isn't really to deal with numerical stability, per se... it's to make it possible to do rigorous and validated computations on a computer. Numerical stability is a different concept that is somewhat orthogonal. I could carry out a numerically unstable computation using interval arithmetic, but using interval arithmetic wouldn't magically make the computation stable, it would just give you error bounds (which may indeed be quite loose and unhelpful if the algorithm is unstable).
  - kragen 1y ago
    From my point of view, the problem with numerical instability is that your program computes the wrong answer, and, worse, gives you no clue that it's wrong. Interval and other self-validating methods do fix that problem: the answer may not be useful, but at least it's not wrong, and they tell you there has been trouble.
    - sfpotter 1y ago
      Yeah, I'd generally agree with that. One thing to bear in mind, though: there are numerical algorithms which are stable and unimpeachably useful but which are unstable in interval arithmetic owing to the natural interval inclusion behaving poorly. A great example of this is the Clenshaw recursion for evaluating Chebyshev series. It is the method of choice for evaluating a Chebyshev series at a single point, but the corresponding natural interval inclusion is actually unstable itself (the width tends to blow up exponentially fast in the degree of the series, regardless of the coefficients). I tend to view "classical numerical methods" and interval arithmetic as somewhat different camps. There's definitely a significant overlap and they can both profit from each other, but you need to put on a different hat when you're doing each. Sometimes interval arithmetic is just too expensive, in which case you need to select a good, stable numerical algorithm. On the other hand, if you're doing interval arithmetic because you must (you need a certified, correct answer), then you will often need to use a completely different set of algorithms and spend some time fussing over what the most appropriate interval inclusion is. Again, another good example here relates to Chebyshev series. If you want to find all of the roots of an analytic function on an interval, expand it in a Chebyshev series and solve the colleague matrix eigenvalue problem. The result could be subtly wrong due to numerical roundoff, and you'd have a hard time recovering from this position; but this method is undeniably extremely useful. On the other hand, if you want to compute rigorous enclosures of all zeros of that same analytic function, you'd need to develop a suitable interval inclusion for it, and then run some type of interval rootfinding algorithm based on a combination of interval contractors (Krawczyk) and subdivision. Basically, a branch and bound algorithm.
constantcrying 1y ago
>I don't think you can ensure that with gradients though: if f and f' are computed in machine arithmetic, cancellation errors might pile up. Yes, you can. You need to do automatic differentiation with interval arithmetic. This gives you a mathematically correct result for the derivative. Always keep in mind with interval arithmetic that (-inf, inf) is also a mathematically correct result. Keeping intervals small is the challenge with interval arithmetic and means that every algorithm not specifically developed for it is likely going to lead to useless results.
- helltone 1y ago
  I think perhaps this could be done in other ways that don't require interval arithmetic for autodiff, only that the gradient is conservatively computed, in other words carrying the numerical error from f into f'
  - deleted 1y ago
    [deleted]
  - fph 1y ago
    But the only way we know how to make "conservative computations" is via interval arithmetic.
    - helltone 1y ago
      No? Or maybe I'm missing something. If the goal is to be able to bound the computation of f, you can: 1) compute f with interval arithmetic 2) compute f normally and f' with interval arithmetic 3) compute f rounding towards zero, compute f' from f rounded towards infinity, and round f' up (if f positive) or round f' down (if f negative). In all 3 cases you can use what you computed to figure out bounds on f, (1) is direct, the other two need extra work.
- kragen 1y ago
  This doesn't help if your computation for f is numerically unstable, unless you compute f with interval arithmetic too.

3abiton 1y ago

It started interestingly, but then > This blog post assumes a vague understanding of implicit surface rasterization, and how interval arithmetic is used to both skip regions of space and simplify complex expressions. Can anyone give me a quick rundow of the article?

meindnoch 1y ago
Which part do you not understand? An implicit surface is defined by F(x,y,z) = 0. Implicit surfaces can be rendered by checking whether the camera ray going through pixel x,y intersects the surface or not. An axis-aligned bounding box (AABB) in 3D is the product of intervals [x_min, x_max]x[y_min, y_max]x[z_min, z_max]. The interval extension of F(x,y,z) gives you an interval [F_min, F_max] for such an AABB. If [F_min, F_max] doesn't contain 0, then you can discard the whole AABB for rendering purposes, because the surface is guaranteed to be not there. This can speed up rendering substantially.
- 3abiton 1y ago
  Kudos for replying, that's already quite helpful.

constantcrying 1y ago

>In this case, "the Lipschitz property" means that the gradient of the distance value is bounded This is total nonsense. The point of Lipschitz continuity is that it is more than continuity and less then differentiability. If you assert that it is differentiable the concept looses all meaning. It is specifically interesting because you do not have to assert differentiability.

porridgeraisin 1y ago
Yes. I think the author meant that the rate of change is bounded [without the function needing to be differentiable] but used the term "gradient" anyways. I guess you shouldn't use the term "rate of change" either? I guess The Lipschitz property means the function's output doesn't change faster than linearly with input Is precise in that context
- constantcrying 1y ago
  He even gives the definition for the L=1 Lipschitz condition afterwards. Lipschitz continuity means the differential quotient is globally bounded (where it exists). Differentiability, by definition, means the differential quotient converges at every point. These are somewhat related, but different things.
kragen 1y ago
There are functions that are differentiable, but not Lipschitz, e.g. sin(1/x) on (0, ∞)). In this context the Lipschitz property allows you to do things that mere differentiability doesn't, and, in the context of assuming that your function is differentiable, the definition given for the Lipschitz property is correct. It's true that there are also functions that are Lipschitz-continuous but not differentiable, but in this context they aren't interesting.
- constantcrying 1y ago
  > It's true that there are also functions that are Lipschitz-continuous but not differentiable, but in this context they aren't interesting. They absolutely are, even in the article. E.g. the max function or the 1-norm are non-differentiable, but continuous. There is literally no point in talking about Lipschitz continuity for differentiable functions, because it is equivalent to the derivative being bounded.

yorwba 1y ago

The suggested normalization procedure, even with the ad-hoc fix for gradient discontinuities, doesn't actually ensure that the resulting function is 1-Lipschitz unless the gradient of the gradient magnitude vanishes. The signed-distance functions considered in the article seem to have piecewise constant gradient magnitudes (so are L-Lipschitz, just with L > 1) except for inside the "r", but for less well-behaved functions, higher order derivatives might start to matter.

kragen 1y ago
This is a good point!
meindnoch 1y ago
Sure, but signed distance fields by definition have a constant gradient magnitude, aren't they? They measure the distance from the surface, which grows linearly in the normal direction. But it is true that general implicit surfaces don't necessarily have constant magnitude gradients. I.e. F(x,y) = x^2 + y^2 - 1 vs. F(x,y) = sqrt(x^2 + y^2) - 1

diabllicseagull 1y ago

I've worked on a patent some years ago about SDF CSG Tree pruning and constant radius filleted blends. Sadly patents don't get the same visibility journals enjoy. https://patentimages.storage.googleapis.com/7a/73/2d/8d2eecadc278b2/US10083264.pdf https://patentimages.storage.googleapis.com/7a/73/2d/8d2eeca...

marcosdumay 1y ago
If you are after visibility, you can always do both. Bot any patent will push people away from your work.
jacobolus 1y ago
In theory, the purpose of a patent is to encourage sharing inventions so people can build on each-others' work. In practice, the modern purpose of a patent is to claim ownership over ideas and block further innovation so the author can extract rents via the court system; they are typically written to be as vague and inscrutable as possible to help cover a wider range of possible alternative inventions someone else might come up with, with no incentive for clarity. There's generally little reason for someone who isn't a lawyer to read a patent that hasn't expired yet – still a decade away in this case. A paper is usually better: the goal is very explicitly sharing knowledge, and there are peer reviewers and editors whose job is to make sure the writing is clear.
- mitthrowaway2 1y ago
  One reason for reading patents that haven't expired yet is if you're trying to evaluate an offer from a startup which has patents on their core technology. It can be worth understanding how strong or weak their technology position is.
  - deleted 1y ago
    [deleted]
- deleted 1y ago
  [deleted]

guyomes 1y ago

A generalisation of this idea is known as Taylor model in 1998 [1]. It might even have been known in 1984 as neighborhood arithmetic [2]. The generalisation works by taking a Taylor expansion of the function up to order n, and then by using a bound for the remainder using bounds on the partial derivatives of order n+1 [3]. [1]: https://www.bmtdynamics.org/cgi-bin/display.pl?name=rdaic https://www.bmtdynamics.org/cgi-bin/display.pl?name=rdaic [2]: https://books.google.fr/books?id=2zDUCQAAQBAJ https://books.google.fr/books?id=2zDUCQAAQBAJ [3]: https://en.wikipedia.org/wiki/Taylor%27s_theorem#Taylor's_theorem_for_multivariate_functions https://en.wikipedia.org/wiki/Taylor%27s_theorem#Taylor's_th...

sfpotter 1y ago
Worth pointing out that these ideas were already well known by Moore, the founder of interval arithmetic. Chapter 3 of his monograph "Methods and Applications of Interval Analysis" has the basic ideas worked out. The folks working on the Taylor model were coming from physics where they had some nasty (very ill-conditioned) nonlinear systems that they needed to solve and developed a package called COSY which implements it. My understanding is that the Taylor model is effective in practice, but there might have been some confusion around what it was actually capable of. I believe the Taylor model people claimed that their interval inclusions had better than quadratic excess, but this turned out not to be the case. Other people were able to push past the quadratic limit of the well known interval inclusions using other techniques. There are some recent papers by Hormann and Yap along these lines, although I think the first interval inclusion that is better than quadratic dates back further...
- yorwba 1y ago
  I assume "recent papers by Hormann and Yap" is a reference to e.g. Range functions of any convergence order and their amortized complexity analysis https://www.inf.usi.ch/hormann//papers/Hormann.2023.RFO.pdf https://www.inf.usi.ch/hormann//papers/Hormann.2023.RFO.pdf ? Cool stuff.
  - sfpotter 1y ago

ajkjk 1y ago

Don't know much about this kind of thing, but it seems like it would be useful, if possible, to store the actual displacement (dx,dy) vector to the surface instead of just its magnitude, the SDF. I can't evaluate the tradeoff of storing an extra value, but it seems like it would make the recursion in the first section a lot easier: when you want to test if a particular box contains the object, if [v+d, v-d] contains 0, you would know a lot more where to look: you need only continue the iteration on subdivisions that are in the correct direction.

sfpotter 1y ago

Cool post. The Lipschitz trick here relies on the assumption that the gradient has magnitude 1 everywhere. Evaluating the SDF in a box and using the Lipschitz property lets you get some quick estimates on the range of the SDF over the box. This is a close cousin of the monotonicity interval inclusion: e.g., if f'([a, b]) > 0, then f([a, b]) is a subset of [f(a), f(b)]. Rounded interval arithmetic makes this rigorous on a computer; you can also do it in multiple dimensions, with higher derivatives, successively tightening inclusions for lower derivatives, etc.