Bagging by design (on the suboptimality of bagging)

Bagging (Breiman 1996) and its variants is one of the most popular methods in aggregating classifiers and regressors. Originally, its analysis assumed that the bootstraps are built from an unlimited, independent source of samples, therefore we call this form of bagging ideal-bagging. However in the real world, base predictors are trained on data subsampled from a limited number of training samples and thus they be-have very differently. We analyze the effect of intersections between bootstraps, obtained by subsampling, to train differ-ent base predictors. Most importantly, we provide an alter-native subsampling method called design-bagging based on a new construction of combinatorial designs, and prove it uni-versally better than bagging. Methodologically, we succeed at this level of generality because we compare the prediction accuracy of bagging and design-bagging relative to the accu-racy ideal-bagging. This finds potential applications in more involved bagging-based methods. Our analytical results are backed up by experiments on classification and regression settings