large data in R

[Andrew Gelman]

Hi--I assume youall know about this:
http://www.datadr.org
?

[Bob Carpenter]

Looks nice.

The difficulty in applying map-reduce to Stan (what they
call, more descriptive, "divide and recombine"), is
that we don't have any parallelization below the Markov
chain level (unlike the Passage sampler from PRL).
But it would allow us to execute different R functions
on different machines.

It should be really helpful for imputation when you have
many types of missing data and want to impute them
simultaneously. For instance, you could take all 1000 or 2000
predictors from those big election surveys and impute
the missingness all at once.

It should also be really useful for Andrew's "secret weapon"
(build a bunch of separate models for different groups of
data [and display them together]).

This won't make existing R functions any faster --- you need whole
new conceptions of the algorithms that can be shoehorned
into the map-reduce (what they call, more descriptively,
"divide and recombine"). So you won't just be able to run
lmer for a really large N. It will make it very easy
to run something like lmer on many small models. So it'd
be awesome for the "secret weapon" if there were many many
piles of data.

I'm not going to be the first one to say "hree-pay" out loud!

- Bob

[Michael Betancourt]

Bob,

I've always thought that the potential for parallelization is not in HMC itself but in computing the potential and derivatives. Isn't the passage through the expression graph pretty map-reducable?

> --
>
>

[Bob Carpenter]

On 1/5/13 12:58 PM, Michael Betancourt wrote:

> I've always thought that the potential for parallelization is not in HMC itself but in computing the potential and derivatives. Isn't the passage through the expression graph pretty map-reducable?

That's essentially what Passage does with Gibbs
sampling -- looks at the graphical model and
decomposes it.

And it's what I meant by having to define new
algorithms -- we can't just take Stan as is and
do this.

Forward-mode auto-dif would be much easier. For
reverse mode, there's a forward expression building
pass then a backward pass. The computation has to
follow the expression graph. You can't compute
a node on the forward pass until all of its sub-expressions
have been computed. You can't compute a node on
the reverse pass until all of its super-expressions
have been computed. There has been a lot of work
in auto-dif on trying to block out bits of the graph
this way in order to reduce the memory entailed by
reverse mode (the idea's to do a bit of forward mode,
then combine into a single reverse mode step). But
all the algorithms are NP complete and quite hairy.

- Bob

[Andrew Gelman]

Also, I have a big application I want to model (a million data points, lots of predictors) so maybe we will want to do some divide-and-recombine for that. Applications are always a good way to fix ideas.
A

On Jan 5, 2013, at 12:53 PM, Bob Carpenter wrote:

> --
>

[Bob Carpenter]

We should be able to do a million data points and
lots of predictors in a single Stan model, but it
won't be ripping through iterations. It's the next couple
of orders of magnitude that are presently the bottleneck.

It'll be interesting as well to see how RM-HMC works on
some of these bigger problems if there aren't too many
predictors (thousands, or ideally hundreds).

- Bob