News for hackers. Stuff that matters.
Re:Swift: Google’s Bet on Differentiable Programming by noelwelsh on Thursday April 09, 2020 @07:38AM (#22821566)
Symbolic differentiation is a fairly common exercise but it is inefficient (the size of the derivative grows exponentially in the size of the original expression). "Automatic differentiation" is the term for the class of algorithms usually used in practice, which are more efficient while still being exact (for whatever "exact" means when you're using floating point :-)
Re:Swift: Google’s Bet on Differentiable Programming by thechao on Thursday April 09, 2020 @08:10AM (#22821767)
AD still explodes for “interesting” derivatives: efficiently computing the adjoint of the Jacobian is NP-complete. And, naturally, the Jacobian is what you want when doing machine learning. There’s papers from the mid-90’s discussing the difficulties in adding AD Jacobian operators to programming languages to support neural networks. This article is just rehashing 25 year old problems.
Re:Swift: Google’s Bet on Differentiable Programming by jedbrown on Thursday April 09, 2020 @10:31AM (#22822871)
Correction: Finding the optimal algorithm (minimal number of operations) for computing a Jacobian is NP-complete, but evaluating it in a multiple of the cost of a forward evaluation is standard.

Also, many optimizers that are popular in ML only need gradients (in which case the Jacobian is just the gradient vector). Second order methods are important in applications with ill-conditioning (such as bundle adjustment or large-scale GPR), but they have lots of exploitable structure/sparsity. The situation is not nearly as dire as you suggest.

Re:Swift: Google’s Bet on Differentiable Programming by thechao on Thursday April 09, 2020 @10:51AM (#22823077)
Yep; I was imprecise!
Re:Swift: Google’s Bet on Differentiable Programming by hinkley on Thursday April 09, 2020 @11:08AM (#22823252)
Around 2000 I was accidentally inventing a Bloom filter variant (to this day I don’t know how I missed the Google papers at the time) for doing a large set intersection test between two machines.

Somehow, I ended up with a calculus equation for determining the right number of bits per entry and rounds to do to winnow the lists, for any given pair of machines where machine A found n entries and machine B found m. But I couldn’t solve it. Then I discovered that even though I did poorly at calculus, I still remembered more than anyone else on the team, and then couldn’t find help from any other engineer in the building either.

Eventually I located a QA person who used to TA calculus. She informed me that my equation probably could not be solved by hand. I gave it another day or so and then gave up. If I couldn’t do it by hand I wasn’t going to be able to write a heuristic for it anyway.

For years, this would be the longest period in my programming career where I didn’t touch a computer. I just sat with pen and paper pounding away at it and getting nowhere. And that’s also the last time I knowingly touched calculus at work.

(although you might argue some of my data vis discussions amount to determining whether we show the either the sum or rate of change of a trend line to explain it better. The S curve that shows up so often in project progress charts is just the integral of a normal distribution, after all)

Re:Swift: Google’s Bet on Differentiable Programming by moultano on Thursday April 09, 2020 @10:29AM (#22822851)
The Jacobian is used all the time, but where do you end up needing the adjoint?
Re:Swift: Google’s Bet on Differentiable Programming by nbulka on Friday April 10, 2020 @10:16PM (#22839189)
What's a link to that paper?
Re:Swift: Google’s Bet on Differentiable Programming by kgwgk on Thursday April 09, 2020 @08:42AM (#22821962)
Re:Swift: Google’s Bet on Differentiable Programming by arethuza on Thursday April 09, 2020 @07:46AM (#22821616)
Thanks - I didn't think it was literally doing symbolic differentiation (I don't work in the area so literally had no idea) - but the basic idea that you apply some process to your code to get some other code doesn't sound that surprising to anyone who has used lisp (and I used to write tools in lisp to write numerical engineering simulations - admittedly a long time ago)
Re:Swift: Google’s Bet on Differentiable Programming by steerablesafe on Thursday April 09, 2020 @11:27AM (#22823456)
> the size of the derivative grows exponentially in the size of the original expression.

Only if you treat it as a tree, not a DAG.

edit: Sorry no, it's still linear, even for a tree.

Re:Swift: Google’s Bet on Differentiable Programming by jjgreen on Thursday April 09, 2020 @10:57AM (#22823145)
exp(x) ?