Enhancing Statistical-Computational Balance in Uncertainty Quantification of Bagging: A Cheap Bootstrap Approach
Abstract
Bagging, which refers to the repeated subsampling of data and averaging the resulting outputs, is a common approach to reduce sampling variability of unstable learning and data-driven optimization procedures. However, uncertainty quantification for these bagged estimators, namely to generate confidence intervals for their target quantities, faces challenges in the simultaneous attainment of coverage validity while being computationally affordable. The latter refers to the practical consideration of overall resampling effort which, when using conventional bootstraps for instance, would lead to nested resampling procedures and thus can be multiplicatively large. In this paper, we develop an interval construction approach that is both asymptotically coverage-valid and computationally light in that it does not use much more than the resampling effort in the bagging scheme itself. Our approach builds on the recent so-called cheap bootstrap idea, a method designed to substantially reduce the number of resamples based on an integrative treatment between data noises and Monte Carlo resampling noises, and an in-depth derivation of the algorithmic configurations under which the Monte Carlo error from incomplete bagging is negligible. Our theory shows that our required computation budget is significantly smaller than existing methods in relation to the bag size and number of Monte Carlo subsamples. Numerical experiments in random forests, as well as an optimality bound estimation in stochastic optimization where bagging is useful, show that our proposed intervals achieve reliable coverage with low computation cost.
Related
- From priors to performance: enhancing statistical efficiency with Bayesian dynamic borrowing
- Adaptive Uncertainty Quantification on Simplicial Complexes with Conformalized Simplicial Neural Networks
- Subjective Risk Decomposition: A New View for Uncertainty Quantification
- Bagged Martingale Posteriors: Calibrated Uncertainty Quantification for Predictive Resampling
- Conformal Uncertainty Quantification Guarantees for Neural Operators
BibTeX
@misc{roychowdhury2026enhancing,
title = {{Enhancing Statistical-Computational Balance in Uncertainty Quantification of Bagging: A Cheap Bootstrap Approach}},
author = {Arindam RoyChowdhury and Henry Lam},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16243},
eprint = {2610.16243},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16243},
}
RIS
TY - UNPB
TI - Enhancing Statistical-Computational Balance in Uncertainty Quantification of Bagging: A Cheap Bootstrap Approach
AU - Arindam RoyChowdhury
AU - Henry Lam
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16243
UR - https://arxiv.org/abs/2610.16243
AB - Bagging, which refers to the repeated subsampling of data and averaging the resulting outputs, is a common approach to reduce sampling variability of unstable learning and data-driven optimization procedures. However, uncertainty quantification for these bagged estimators, namely to generate confidence intervals for their target quantities, faces challenges in the simultaneous attainment of coverage validity while being computationally affordable. The latter refers to the practical consideration of overall resampling effort which, when using conventional bootstraps for instance, would lead to nested resampling procedures and thus can be multiplicatively large. In this paper, we develop an interval construction approach that is both asymptotically coverage-valid and computationally light in that it does not use much more than the resampling effort in the bagging scheme itself. Our approach builds on the recent so-called cheap bootstrap idea, a method designed to substantially reduce the number of resamples based on an integrative treatment between data noises and Monte Carlo resampling noises, and an in-depth derivation of the algorithmic configurations under which the Monte Carlo error from incomplete bagging is negligible. Our theory shows that our required computation budget is significantly smaller than existing methods in relation to the bag size and number of Monte Carlo subsamples. Numerical experiments in random forests, as well as an optimality bound estimation in stochastic optimization where bagging is useful, show that our proposed intervals achieve reliable coverage with low computation cost.
ER -