alan-turing-institute / alan-turing-institute/PosteriorBootstrap

Speed up the sampling

Open
#47 0 comments 0 reactions 1 assignee Claimed by @mm3509 View on GitHub
to-do
Dominant language
R
Stars
4
Forks
3
Avg merge
5h 18m
Merged PRs (30d)
1

Description

The code took several hours on a single processor on my mac laptop and had yet to finish. The current code on #58 is a bit faster than the version of February 14th (commit e6e548f), the first time I was able to reproduce the figure. For example, the current code in #58 with a `concentration = 500`, `n_bootstrap = 1000`, and posterior samples from Rstan variational Bayes, the `anpl()` function takes 92 seconds:

```
[1] "Timing of the lap:"
[1] 91.52413
```

while the code from e6e548f with `prior_sample_size = 500`, `n_samp = 1000`, and posterior samples also from Rstan variational Bayes, the `mdp_logit_mvn_stickbreaking` function takes 94 seconds:

```
[1] "Timing of the lap:"
[1] 94.39698
```

It needs to be faster for CRAN, as CRAN runs the code in the vignettes too. #20 does not help because CRAN runs on one or two processors only.

Commit 0fde804 added code to skip some parts on the vignette on CRAN. It still runs on Travis. Commit fca24da added a progress bar that kept the build alive and passed the tests on Travis.

The long running time seems to be a feature of the algorithm rather than our implementation. The length of the stick breaks is two orders of magnitude larger than the concentration:

```
> length(stick_breaking(1))
[1] 100
> length(stick_breaking(1e3))
[1] 100000
> length(stick_breaking(2e4))
[1] 1000000
```

Each new draw of the algorithm is the result of a `glm.fit` with logistic regression. Logistic regression does not have a closed form, so each draw is the result of some numerical optimisation like gradient descent. The data for the logistic regression is the original data (1,000 observations) augmented by a number of synthetic observations equal ot the length of the stick breaks.

Therefore, when the concentration is `1` (where the length of stick-break is `100`), each draw is a logistic regression on `1,100` observations; when it is `1e3` (where the length of the stick-break is `100,000`), each draw is a regression on 101,000 observations; and when it is `2e4`(where the length of the stick break is `1,000,000`), each draw is a regression on 1,001,000 observations.

Line profiling shows that most of the time is spent on running the logistic regression with `stats::glm.fit()`, so it will be quite hard to improve the running time.

I don't see how we can speed up the code anywhere near the requirement of a thousand logistic regressions each on 1 million observations to fit under 10 minutes (in case we don't keep the Travis build alive with the "hack" in commit fca24da).

I would be fine for closing this issue, but in my view it calls into question the purpose of the package: Rstan can provide the required number of samples from an exact or variational Bayesian regression in a few seconds. @jemrobinson and @sllll, what do you think?

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.