[HN Gopher] An illustrated guide to automatic sparse differentia...
___________________________________________________________________
An illustrated guide to automatic sparse differentiation
Author : mariuz
Score : 127 points
Date : 2025-04-29 03:18 UTC (1 days ago)
(HTM) web link (iclr-blogposts.github.io)
(TXT) w3m dump (iclr-blogposts.github.io)
| nathan_douglas wrote:
| Picking my way through this slowly... I'm familiar with autodiff
| but some of these ideas are very new to me. This seems really,
| really exciting though.
| whitten wrote:
| This paper is written by three Europeans who clearly understand
| these mathematical ideas.
|
| Is this type of analysis a part of a particular mathematical
| heritage ?
|
| What would it be called ?
|
| Is this article relevant ? https://medium.com/@lobosi/calculus-
| for-machine-learning-jac...
| ghurtado wrote:
| I quickly realized it was approximately 20,000 ft over my head,
| but I still power through these sort of things to see if
| anything "sticks".
|
| So far, nothing but I'll keep trying ..
| molticrystal wrote:
| Maybe someone else can summarize more accurately or do a better
| job but I'll take a shot:
|
| The Jacobian often appears in the final segment of a three part
| calculus series when exploring chain rules and variable
| transformations. Look up the Jacobian used in converting
| between x,y,z and spherical coordinates r,ph,th and note its
| matrix structure. Skimming your Medium Lobosi article it seems
| it emphasizes this aspect.
|
| The Jacobian also serves another purpose. As stated in the OP's
| article "The Jacobian operator Df:x[?]Df(x) is a linear map
| which provides the best linear approximation of f around a
| given point x."
|
| We like approximations, we can make a speed vs accuracy/memory
| trade off, you only have so much space in a register or memory
| cell, and trying to get more accuracy past a certain point
| takes more memory/computations/time.
|
| The article then notes that many computations involve Jacobians
| with sparse matrices meaning some matrix elements can be
| ignored so we don't have to waste our time on them if handled
| cleverly.
|
| Subsequent sections cover methods to identify and label
| sparsity patterns. The article explains how applying their
| proposed coloring techniques to large matrices common in
| machine learning yields significant efficiency gains.
|
| As far as the mathematical heritage, I don't know the family
| tree, but I suspect it stems from courses blending matrix
| theory linear algebra and algorithms so you'd want the computer
| science version of such math. Functional approximation ties to
| numerical methods though I am uncertain if introductory texts
| cover Jacobians. Check out Newton's method to grasp its
| mechanics and understand how that works then explore its
| Jacobian extension. For the coloring aspect graph theory is
| where to turn. You can learn its basics with minimal
| prerequisites by studying the seven bridges problem or the map
| coloring problem, do the five color version. Many of these
| concepts can be simplified into small programming projects.
| They will not rival Matlab but they will solidify your
| understanding.
| yorwba wrote:
| The blog post mentions in an aside that "The authors of this
| blog post are all developers of the ASD ecosystem in Julia."
| which might be the closest thing to an intellectual school that
| this kind of work is associated with.
| gdalle wrote:
| Blog post author here, happy to answer any questions you may
| have!
|
| The prerequisites for understanding the blog post are an
| undergrad course in calculus and linear algebra, and some graph
| theory. I can look up some accessible resources if you're
| interested :)
| JohnKemeny wrote:
| Does this article exist as a (LaTeX) pdf for printing too?
| funks_ wrote:
| We don't have plans for that, but you could try to convert
| the Markdown source: https://github.com/iclr-
| blogposts/2025/blob/main/_posts/2025...
| gdalle wrote:
| Our Arxiv preprint is a slightly longer read, available in
| PDF form with more precise descriptions:
| https://arxiv.org/abs/2501.17737
| carterschonwald wrote:
| Thx!
|
| It's always fun to see new flavors of AD work. My
| attempts in that direction haven't been the most
| successful
| constantcrying wrote:
| >Is this type of analysis a part of a particular mathematical
| heritage ?
|
| It is a mixture of two very much related areas of mathematics.
| Analysis, called calculus in the US, and numerics.
|
| The ideas behind automatic differentiation arise from the
| question of how to compute the derivative of a function on a
| computer. The "derivative" part is the Analysis part and the
| "on a computer" part is the numerics.
|
| As it turns out writing down the formal definition of the
| derivative and approximating it on a computer has many
| undesirable properties. So alternative approaches, like AD,
| were developed. But AD is much older than the recent Neural
| network trend.
| imtringued wrote:
| The hessian is needed for optimization and this blog post was
| most likely motivated by improving the method used in the
| precursor blog post: https://iclr-
| blogposts.github.io/2024/blog/bench-hvp/
| funks_ wrote:
| Yes, this blog post indeed inspired us to submit ours!
| rdyro wrote:
| A really cool post and a great set of visualizations!
|
| Computing sparse Jacobians can save a lot of compute if there's a
| real lack of dependency between part of the input and the output.
| Discovering this automatically through coloring is very
| appealing.
|
| Another alternative is to implement sparse rules for each
| operation yourself, but that often requires custom autodiff
| implementations which aren't easy to get right, I wrote a small
| toy version of a sparse rules-based autodiff here:
| https://github.com/rdyro/SpAutoDiff.jl
|
| Another example (a much more serious one) is
| https://github.com/microsoft/folx
| gdalle wrote:
| You might also be interested in Spadina for Enzyme. There are
| no Julia bindings yet but I'd be excited if someone made them!
| https://c.wsmoses.com/presentations/weuroad23.pdf
| oulipo wrote:
| Sparsely-related question: is the blog style/css open-source?
| molticrystal wrote:
| It seems to be based off of Al-Folio, MIT licensed
|
| https://github.com/alshedivat/al-folio
| FilosofumRex wrote:
| The classic reference on the subject is "Numerical Linear
| Algebra" by Lloyd Trefethen. Skip to the last chapter on the
| iterative methods for computational aspects. You'll learn a lot
| more and faster with Matlab.
|
| https://davidtabora.wordpress.com/wp-content/uploads/2015/01...
|
| A short overview is chapter 11 in Gilbert Strangs's Intro to
| linear Algebra
| https://math.mit.edu/~gs/linearalgebra/ila5/linearalgebra5_1...
|
| AD comes from a different tradition - dating back to FORTRAN 77
| programers attempt to differentiate non-elementary functions (For
| Loops, procedural functions, Subroutines, etc). Note the hardware
| specs for some nostalgia
| https://www.mcs.anl.gov/research/projects/adifor/
| gwf wrote:
| Not trying to "Schmidhuber" this or anything, but I think my 1999
| NIPS paper gives a cleaner derivation and explanation for working
| on the Jacobian. In it, I derive a Jacobian operator that allows
| you to compute arbitrary products between the Jacobian and any
| vector, with complexity that is comparable to standard backprop.
|
| [*] G.W. Flake & B.A. Pearlmutter, "Differentiating Functions of
| the Jacobian with Respect to the Weights,"
| https://proceedings.neurips.cc/paper_files/paper/1999/file/b...
| goosedragons wrote:
| There is automatic sparse differentiation available in the R
| ecosystem. That's what the RTMB & TMB packages do.
| adgjlsfhk1 wrote:
| That's really impressive! I can't even imagine implimenting
| sparsity tracing in a language as dynamic and hard to compile
| as R.
| goosedragons wrote:
| I think they do sparsity tracing and tape construction in C++
| behind the scenes. RTMB does some wacky thing abusing complex
| values to let you write the function code in R and pass that
| off somehow.
___________________________________________________________________
(page generated 2025-04-30 23:02 UTC)