Finite-Sample Coverage Errors of the Cheap Bootstrap With Minimal Resampling Effort

The bootstrap is a popular data-driven method to quantify statistical uncertainty, but for modern high-dimensional problems, it could suffer from huge computational costs due to the need to repeatedly generate resamples and refit models. Recent work has shown that it is possible to reduce the resampling effort dramatically, even down to one Monte Carlo replication, for constructing asymptotically valid confidence intervals. We derive finite-sample coverage error bounds for these ``cheap'' bootstrap confidence intervals that shed light on their behaviors for large-scale problems where the curb of resampling effort is important. Our results show that the cheap bootstrap using a small number of resamples has comparable coverages as traditional bootstraps using infinite resamples, even when the dimension grows closely with the sample size. We validate our theoretical results and compare the performances of the cheap bootstrap with other benchmarks via a range of experiments.