Rule of thumb for number of bootstrap samples 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?
 A: 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.
A: My experience is that statisticians won't take simulations or bootstraps seriously unless the number of iterations exceeds 1,000. 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.
A: 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.
A: 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.
A: 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. 
A: 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!
