Speeding up bootstrap computations: a vectorized implementation for statistics based on sample moments

Elias Chaibub NetoarXiv 2014 · DOI · arXiv

Abstract

In this note we propose a vectorized implementation of the non-parametric bootstrap for statistics based on sample moments. Basically, we adopt the multinomial sampling formulation of the non-parametric bootstrap, and compute bootstrap replications of sample moment statistics by simply weighting the observed data according to multinomial counts, instead of evaluating the statistic on a re-sampled version of the observed data. Using this formulation we can generate a matrix of bootstrap weights and compute the entire vector of bootstrap replications with a few matrix multiplications. Vectorization is particularly important for matrix-oriented programming languages such as R, where matrix/vector calculations tend to be faster than scalar operations implemented in a loop. We illustrate the gain in computational speed achieved by the vectorized implementation in real and simulated data sets, when bootstrapping Pearson's sample correlation coefficient.

Introduction

The non-parametric bootstrap is a fundamental tool in statistics used to estimate the uncertainty of a sample statistic. However, it is computationally expensive, traditionally requiring "re-sampling with replacement" over thousands of iterations. In programming languages like R or Matlab, standard "for-loops" are notoriously slow due to interpreter overhead. While these languages are optimized for matrix operations, the standard bootstrap approach is difficult to vectorize because each iteration typically generates a new version of the dataset. This paper introduces a mathematical framework to perform all bootstrap iterations simultaneously by reframing the problem.

Methodology

The proposed method shifts the perspective from re-sampling data to weighting data.

Multinomial Formulation

Instead of picking $N$ data points with replacement, we can view the bootstrap as assigning weights to each original data point. These weights follow a multinomial distribution. For example, if a data point is selected twice in a bootstrap sample, its weight is $2/N$; if it is not selected, its weight is $0$.

Vectorization via Matrix Multiplication

Rather than generating weights one iteration at a time, we generate a massive $N \times B$ matrix of weights ($W^*$) all at once, where $B$ is the number of bootstrap replicates. For statistics based on sample moments (like means, variances, or correlations), the entire vector of $B$ bootstrap replicates can be calculated using a single matrix multiplication: $\hat{\theta}^* = \mathbf{x}^t W^*$. This approach leverages highly optimized Linear Algebra libraries (BLAS) that power R and Matlab, bypassing the overhead of loop logic.

Empirical Results

The method was evaluated using the Law School dataset (LSAT scores and GPAs). For a small sample size of $N=15$, the vectorized approach demonstrated a dramatic performance advantage.

Performance comparison on Law School data (N=15) showing time ratios and distributional consistency.

As shown in Figure 2, the vectorized multinomial sampling was roughly 50 times faster than the standard loop-based approach. For a larger dataset of $N=82$, the speedup remained significant at approximately 8 times faster. Crucially, the density plots confirm that the vectorized method produces results identical to traditional re-sampling.

Scaling and Memory Considerations

While vectorization offers substantial speedups, it introduces a memory-speed trade-off. Storing a matrix of size $N \times B$ can be taxing on RAM. For example, if $N=1,000$ and $B=1,000,000$, the weight matrix requires several gigabytes of memory.

Scaling of computational efficiency across different sample sizes and bootstrap iterations (B).

Simulation results (Figure 4) indicate that the advantage of vectorization is most pronounced for "small $N$, large $B$" scenarios. As the sample size $N$ increases, the log time ratio decreases toward zero, suggesting that the overhead of managing massive matrices eventually offsets the benefits of vectorization. For very large sample sizes, traditional loops may eventually become more efficient due to lower memory pressure.

Conclusion

By reframing the bootstrap as a multinomial weighting problem, researchers can achieve massive speedups in matrix-oriented languages. This vectorized implementation is particularly effective for statistics based on sample moments, providing a highly efficient alternative to traditional re-sampling loops when memory constraints allow.

Summary updated

Abstract

In this note we propose a vectorized implementation of the non-parametric bootstrap for statistics based on sample moments. Basically, we adopt the multinomial sampling formulation of the non-parametric bootstrap, and compute bootstrap replications of sample moment statistics by simply weighting the observed data according to multinomial counts, instead of evaluating the statistic on a re-sampled version of the observed data. Using this formulation we can generate a matrix of bootstrap weights and compute the entire vector of bootstrap replications with a few matrix multiplications. Vectorization is particularly important for matrix-oriented programming languages such as R, where matrix/vector calculations tend to be faster than scalar operations implemented in a loop. We illustrate the gain in computational speed achieved by the vectorized implementation in real and simulated data sets, when bootstrapping Pearson's sample correlation coefficient.
BibTeX
@misc{neto2014speeding,
  author = {Elias Chaibub Neto},
  title = {{Speeding up bootstrap computations: a vectorized implementation for statistics based on sample moments}},
  year = {2014},
  eprint = {1412.1735},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.1735},
}
Figure