Differentiation of the Cholesky decomposition

[Aki Vehtari]

I know that differentiation of the Cholesky decomposition was already made faster and use less memory in Stan, but this might be useful at some point (or just nice to read because it provides nice review of many ways to make the omputation)
http://arxiv.org/abs/1602.07527

[Michael Betancourt]

Yeah, but a complete ignorance of Stan. And Iain definitely knows about Stan...

> On Feb 25, 2016, at 11:33, Aki Vehtari <aki.v...@aalto.fi> wrote:
>
> I know that differentiation of the Cholesky decomposition was already made faster and use less memory in Stan, but this might be useful at some point (or just nice to read because it provides nice review of many ways to make the omputation)
> http://arxiv.org/abs/1602.07527
>

> --
> You received this message because you are subscribed to the Google Groups "stan development mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-dev+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Bob Carpenter]

I just took a look at rev/mat/fun/cholesky_decompose.hpp and
it looks pretty good. It's not using any kind of blocking
structure, though, which probably would be a huge speedup in
larger matrices. I don't really know how to implement it,
though --- is it worth reading that paper?

Speeding up a bunch of this stuff in Stan would make a
great project for someone who knew numerical matrix processing.

- Bob

P.S. And for my usual stylistic rant, I really hate using a variable
width font in fixed-width mode for code.

[Andrew Gelman]

In all seriousness, perhaps we could write a 1-page Arxiv article called, Faster Differentiation of the Cholesky Decomposition where we give the Stan code.
People read Arxiv (as you’ve just demonstrated)!
A

> On Feb 25, 2016, at 11:42 AM, Michael Betancourt <betan...@gmail.com> wrote:
>

[Bob Carpenter]

I just glanced at the Murray paper. What he's
doing is the blocking that's critical to shuttling
data to and from memory, which is the bottleneck in
large-scale matrix operations.

There's a discussion of this for basic matrix ops in
our arXiv paper. Stan's algorithm for matrix multiplication
is slower than just autodiffing the Eigen algorithm.
I very very strongly suspect that's the result of the clever
blocking they do in Eigen. Ours uses less memory and
the speed results are pretty close, but the point is that we
could speed up what our algorithm's doing with proper
blocking and get the best of both worlds.

Same for the Cholesky thing.

So I'm not sure what you think we have to add to the discussion
at this point.

- Bob

[Andrew Gelman]

I have no idea what we could add. I was just reacting to the comments by Aki and Mike that Stan is faster and uses less memory than was was done in that paper. If that’s really true, it coudl be worth our making that clear.

[Robert Trangucci]

I think Aki was referring to the fact that we've made autodiffing through the Cholesky faster and less memory-intensive than previous versions of Stan (where we didn't have an explicit reverse-mode implementation).

We've implemented Giles algorithm which he references in the paper.

Rob

[Andrew Gelman]

Ok, then maybe we just should have a blog post pointing to the Murray paper and saying that we implemented the relevant algorithm and it’s fast.
A

[Aki Vehtari]

Yes! Thanks Rob!

And I did not want to imply that potential additional improvements should have top priority. I just wanted to point out this paper for reference if someone at some point has time and we want to get more speed (e.g. with block algorithms).

Aki

[Robert Trangucci]

I think it would be great to look into the blocking algorithm proposed in Murray.

As for the blog post, perhaps it'd be useful to let people know that inference on latent GPs has been sped up/slimmed down, and give a few examples of runtime differences.

Maybe Michael's Seville BDA hierarchical GPs?

Rob

[Dustin Tran]

Not sure how helpful this is, but Matt Johnson implemented Iain Murray’s algorithm just today in autograd. (Or did he implement one of many algorithms? I didn’t look closely)

https://github.com/HIPS/autograd/blob/master/autograd/numpy/linalg.py#L80

Dustin

[Michael Betancourt]

Ugh, all of this self congratulation on Twitter between Murray and the autograd/theano 

with no discussion of Stan is still very disappointing; it’s taking everything I have to not

write a snarky response.  To be clear, Matt and David and the autograd team are all

great, just disappointed that all of this discussion is happening in a Stan-vacuum.  Not

sure what else we have to do to be acknowledged by those communities.

[Robert Trangucci]

How bout: ".@driainmurry Stan - Autodiffing through the Cholesky decomposition since inception"? Too snarky?


Rob

[Michael Betancourt]

“Welcome to 2014 — where have you guys been?”  Okay, I’m blocking

myself from Twitter until tomorrow night.

[Robert Trangucci]

Too late, couldn't resist

Rob

[Ido Rosen]

Sick burn @trangucc

https://twitter.com/Trangucc/status/703284626501009409

hashbrown ImWithStan

On Fri, Feb 26, 2016 at 1:28 PM, Robert Trangucci

[Bob Carpenter]

The O() is great, but the devil's in the memory locality.
That can lend a real factor of 10 or more speedup.

Now if someone wants to profile autograd vs. Stan...

The real trick is that we can avoid having to do a Cholesky
decomposition in most cases (the notable exception being the
GP covariance matrix).

- Bob

[Andrew Gelman]

I recommend writing a polite blog post.