Rule of thumb for number of bootstrap samples

Question

I wonder if someone knows any general rules of thumb regarding the number of bootstrap samples one should use, based on characteristics of the data (number of observations, etc.) and/or the variables included?

Answer 1

My experience is that statisticians won't take simulations or bootstraps seriously unless the number of iterations exceeds 1,000. Monte Carlo (MC) error is a big issue that's a little under appreciated. For instance, this paper used Niter=50 to demonstrate LASSO as a feature selection tool. My thesis would have taken a lot less time to run had 50 iterations been deemed acceptable! I recommend that you should always inspect the histogram of the bootstrap samples. Their distribution should appear fairly regular. I don't think any plain numerical rule will suffice, and it would be overkill to perform, say, a double-bootstrap to assess MC error.

Suppose you were estimating the mean from a ratio of two independent standard normal random variables, some statistician might recommend bootstrapping it since the integral is difficult to compute. If you have basic probability theory under your belt, you would recognize that this ratio forms a Cauchy random variable with a non-existent mean. Any other leptokurtic distribution would require several additional bootstrap iterations compared to a more regular Gaussian density counterpart. In that case, 1000, 100000, or 10000000 bootstrap samples would be insufficient to estimate that which doesn't exist. The histogram of these bootstraps would continue to look irregular and wrong.

There are a few more wrinkles to that story. In particular, the bootstrap is only really justified when the moments of the data generating probability model exist. That's because you are using the empirical distribution function as a straw man for the actual probability model, and assuming they have the same mean, standard deviation, skewness, 99th percentile, etc.

In short, a bootstrap estimate of a statistic and its standard error is only justified when the histogram of the bootstrapped samples appears regular beyond reasonable doubt and when the bootstrap is justified.

Answer 2

I start by responding to something raised in another answer: why such a strange number as "$599$" (number of bootstrap samples)?

This applies also to Monte Carlo tests (to which bootstrapping is equivalent when the underlying statistic is pivotal), and comes from the following: if the test is to be exact, then, if $\alpha$ is the desired significance level, and $B$ is the number of samples, the following relation must hold:

$$\alpha \cdot (1+B) = \text{integer}$$

Now consider typical significance levels $\alpha_1 = 0.1$ and $\alpha_2 = 0.05$

We have

$$B_1 = \frac {\text{integer}}{0.1} - 1,\;\;\; B_2 = \frac {\text{integer}}{0.05} - 1$$

This "minus one" is what leads to proposed numbers like "$599$", in order to ensure an exact test.

I took the following information from Davidson, R., & MacKinnon, J. G. (2000). Bootstrap tests: How many bootstraps?. Econometric Reviews, 19(1), 55-68. (the working paper version is freely downloadable).

As regards rule of thumb, the authors examine the case of bootstrapping p-values and they suggest that for tests at the $0.05$ the minimum number of samples is about 400 (so $399$) while for a test at the $0.01$ level it is 1500 so ($1499$).

They also propose a pre-testing procedure to determine $B$ endogenously. After simulating their procedure they conclude:

"It is easy to understand why the pretesting procedure works well. When the null hypothesis is true, B can safely be small, because we are not concerned about power at all. Similarly, when the null is false and test power is extremely high, B does not need to be large, because power loss is not a serious issue. However, when the null is false and test power is moderately high, B needs to be large in order to avoid loss of power. The pretesting procedure tends to make B small when it can safely be small and large when it needs to be large."

At the end of the paper they also compare it to another procedure that has been proposed in order to determine $B$ and they find that theirs performs better.

Answer 3

edit:

If you are serious about having enough samples, what you should do is to run your bootstrap procedure with, what you hope are, enough samples a number of times and see how much the bootstrap estimates "jump around". If the repeated estimates does not differ much (where "much" depends on your specific situation) your are most likely fine. Of course you can estimate how much the repeated estimates jump around by calculating the sample SD or similar.

If you want a reference and a rule of thumb Wilcox(2010) writes "599 is recommended for general use." But this should be considered only a guideline or perhaps the minimum number of samples you should consider. If you want to be on the safe side there is no reason (if it is computationally feasible) why you should not generate an order of magnitude more samples.

On a personal note I tend to run 10,000 samples when estimating "for myself" and 100,000 samples when estimating something passed on to others (but this is quick as I work with small datasets).

Reference

Wilcox, R. R. (2010). Fundamentals of modern statistical methods: Substantially improving power and accuracy. Springer.

Answer 4

There are a some situations where you can tell either beforehand or after a few iterations that huge numbers of bootstrap iterations won't help in the end.

• You hopefully have an idea beforehand on the order of magnitude of precision that is required for meaningful interpretation of the results. If you don't maybe it is time to learn a bit more about the problem behind the data analysis. Anyways, after a few iterations you may be able to estimate how many more iterations are needed.

• Obviously, if you have extremely few cases (say, the ethics committee allowed 5 rats) you don't need to think about tens of thousands of iterations. Maybe it would be better to look at all possible draws. And maybe it would be even better to stop and think how certain any kind of conclusion can (not) be based on 5 rats.

• Think about the total uncertainty of the results. In my field, the part of uncertainty that you can measure and reduce by bootstrapping may only be a minor part of the total uncertainty (e.g. due to restrictions in the design of the experiments important sources of variation are often not covered by the experiment - say, we start by experiments on cell lines although the final goal will of course be patients). In this situation it doesn't make sense to run too many iterations -- it anyways won't help the final result and moreover it may indroduce a false sense of certainty.

• A related (though not exactly the same) issue occurs during out-of-bootstrap or cross validation of models: you have two sources of uncertainty: the finite (and in my case usually very small number of independent cases) and the (in)stability of the bootstrapped models. Depending on your set up of the resampling validation, you may have only one of them contributing to the resampling estimate. In that case, you can use an estimate of the other source of variance to judge what certainty you should achieve with the resampling, and when it stops to help the final result.

• Finally, while so far my thoughts were about how to do fewer iterations, here's a practical consideration in favor of doing more:
  In practice my work is not done after the bootstrap is run. The output of the bootstrap needs to be aggregated into summary statistics and/or figures. Results need to be interpreted the paper or report to be written. Much of these can already be done with preliminary results of a few iterations of the bootstrap (if the results are clear, they show already after few iterations, if they are borderline they'll stay borderline). So I often set up the bootstrapping in a way that allows me to pull preliminary results so I can go on working while the computer computes. That way it doesn't bother me much if the bootstrapping takes another few days.

Answer 5

TLDR. 10,000 seems to be a good rule of thumb, e.g. p-values from this large or larger of bootstrap samples will be within 0.01 of the "true p-value" for the method about 95% of the time.

I only consider the percentile bootstrap approach below, which is the most commonly used method (to my knowledge) but also admittedly has weaknesses and shouldn't be used with small samples.

Reframing slightly. It can be useful to compute the uncertainty associated with results from the bootstrap to get a sense for the uncertainty resulting from the use of the bootstrap. Note that this does not address possible weaknesses in the bootstrap (e.g. see the link above), but it does help evaluate if there are "enough" bootstrap samples in a particular application. Generally, the error related to the bootstrap sample size n goes to zero as n goes to infinity, and the question asks, how big should n be for the error associated with small bootstrap sample size to be small?

Bootstrap uncertainty in a p-value. The imprecision in an estimated p-value, say pv_est is the p-value estimated from the bootstrap, is about 2 x sqrt(pv_est * (1 - pv_est) / N), where N is the number of bootstrap samples. This is valid if pv_est * N and (1 - pv_est) * N are both >= 10. If one of these is smaller than 10, then it's less precise but very roughly in the same neighborhood as that estimate.

Bootstrap error in a confidence interval. If using a 95% confidence interval, then look at how variability of the quantiles of the bootstrap distribution near 2.5% and 97.5% by checking the percentiles at (for the 2.5th percentile) 2.5 +/- 2 * 100 * sqrt(0.025 * 0.975 / n). This formula communicates the uncertainty of the lower end of the 95% confidence interval based on the number of bootstrap samples taken. A similar exploration should be done at the top end. If this estimate is somewhat volatile, then be sure to take more bootstrap samples!

Answer 6

Most bootstrapping applications I have seen reported around 2,000 to 100k iterations. In modern practice with adequate software, the salient issues with bootstrap are the statistical ones, more so than time and computing capacity. For novice users with Excel, one could perform only several hundreds before requiring the use of advanced Visual Basic programming. However, R is much simpler to use and makes generation of thousands of bootstrapped values easy and straightforward.

Answer 7

Data-driven theory-backed procedure

If you want a formal treatment of the subject, a good method comes from a pioneering paper by Andrews & Buchinsky (2000, Econometrica): do some small number of bootstrap replications, see how stable or noisy the estimator is, and then, based on some target accuracy measure, increase the number of replications until you are sure that this resampling-related error has reached a certain lower bound with a chosen certainty. Our helper here is the Weak Law of Large Numbers where the asymptotics are in B. To be more specific, B is chosen depending on the user-chosen bound on the relative deviation measure of the Monte-Carlo approximation of the quantity of interest based on B simulations. This quantity can be standard error, p-value, confidence interval, or bias correction. The closeness is the relative deviation $R^*$ of the B-replication bootstrap quantity from the infinite-replication quantity (or, to be more precise, the one that requires $n^n$ replications): $R^* := (\hat\lambda_B - \hat\lambda_\infty)/\hat\lambda_\infty$. The idea is, find such B that the actual relative deviation of the statistic of interest be less than a chosen bound (usually 5%, 10%, 15%) with a specified high probability $1-\tau$ (usually $\tau = 5\%$ or $10\%$). Then,

$$\sqrt{B} \cdot R^* \xrightarrow{d} \mathcal{N}(0, \omega),$$

where $\omega$ can be estimated using a relatively small (usually 200–300) preliminary bootstrap sample that one should be doing in any case.

Here is the general formula for the number of necessary bootstrap replications $B$:

$$ B \ge \omega \cdot (Q_{\mathcal{N}(0, 1)}(1-\tau/2) / r)^2,$$

where r is the maximum allowed relative discrepancy (i.e. accuracy), $1-\tau$ is the probability that this desired relative accuracy bound has been achieved, $Q_{\mathcal{N}(0, 1)}$ is the quantile function of the standard Gaussian distribution, and $\omega$ is the asymptotic variance of $R$*. The only unknown quantity here is $\omega$ that represents the variance due to simulation randomness.

The general 3-step procedure for choosing B is like this:

1. Compute the approximate preliminary number $B_1 := \lceil \omega_1 (Q_{\mathcal{N}(0, 1)}(1-\tau/2) / r)^2 \rceil$, where $\omega_1$ is a very simple theoretical formula from Table III in Andrews & Buchinsky (2000, Econometrica).
2. Using these $B_1$ samples, compute an improved estimate $\hat\omega_{B_1}$ using a formula from Table IV (ibid.).
3. With this $\hat\omega_{B_1}$ compute $B_2 := \lceil\hat\omega_{B_1} (Q_{\mathcal{N}(0, 1)}(1-\tau/2) / r)^2 \rceil$ and take $B_{\mathrm{opt}} := \max(B_1, B_2)$.

If necessary, this procedure can be iterated to improve the estimate of $\omega$, but this 3-step procedure as it is tends to yield already conservative estimates that ensure that the desired accuracy has been achieved. This approach can be vulgarised by taking some fixed $B_1 = 1000$, doing 1000 bootstrap replications in any case, and then, doing steps 2 and 3 to compute $\hat\omega_{B_1}$ and $B_2$.

Example (Table V, ibid.): to compute a bootstrap 95% CI for the linear regression coefficients, in most practical settings, to be 90% sure that the relative CI length discrepancy does not exceed 10%, 700 replications are sufficient in half of the cases, and to be 95% sure, 850 replications. However, requiring a smaller relative error (5%) increases B to 2000 for $\tau=10\%$ and to 2700 for $\tau=5\%$.

This agrees with the formula for B above. If one seeks to reduce the relative discrepancy r, by a factor of k, the optimal B goes up roughly by a factor of $k^2$, whilst increasing the confidence level that the desired closeness is reached merely changes the critical value of the standard normal (1.96 → 2.57 for 95% → 99% confidence).

Concise practical advice

This being said, we should realise that not everyone is a theoretical econometrician with deep bootstrap knowledge, so here is my quick rule of thumb.

1. B >= 1000, otherwise your paper will be rejected with something like ‘We are not in the Pentium-II era’ from Referee 2.
2. Ideally, B >= 10000; try to do it if your computer can handle it.
3. You could check if your B yields the desired probability $1-\tau$ of achieving the desired relative accuracy $r$ for the values thereof that are psychologically comfortable for you (e.g. $r= 5\%$ and $\tau=5\%$).
4. If not, increase B to the value dictated by the A&B 3-stage procedure described above.
5. In general, for any actual accuracy of your bootstrapped quantity, to increase the desired relative accuracy by a factor of k, increase B by a factor of $k^2$.

Happy bootstrapping!