Ensemble linear interpolators: The role of ensembling
This work addresses the problem of unstable generalization in overparameterized models for machine learning researchers, offering a theoretical analysis of ensembling as a stabilization technique, though it is incremental in extending known bagging methods to linear interpolators.
The paper tackles the instability of interpolators, such as the minimum L2 norm least squares estimator, which can have unbounded test errors with noisy data, and shows that bagging linear interpolators stabilizes them, leading to bounded out-of-sample prediction risk. It introduces a multiplier-bootstrap-based bagged estimator, revealing that bagging acts as implicit regularization to mitigate variance, unlike sketching which only modifies aspect ratios and thresholds.
Interpolators are unstable. For example, the mininum $\ell_2$ norm least square interpolator exhibits unbounded test errors when dealing with noisy data. In this paper, we study how ensemble stabilizes and thus improves the generalization performance, measured by the out-of-sample prediction risk, of an individual interpolator. We focus on bagged linear interpolators, as bagging is a popular randomization-based ensemble method that can be implemented in parallel. We introduce the multiplier-bootstrap-based bagged least square estimator, which can then be formulated as an average of the sketched least square estimators. The proposed multiplier bootstrap encompasses the classical bootstrap with replacement as a special case, along with a more intriguing variant which we call the Bernoulli bootstrap. Focusing on the proportional regime where the sample size scales proportionally with the feature dimensionality, we investigate the out-of-sample prediction risks of the sketched and bagged least square estimators in both underparametrized and overparameterized regimes. Our results reveal the statistical roles of sketching and bagging. In particular, sketching modifies the aspect ratio and shifts the interpolation threshold of the minimum $\ell_2$ norm estimator. However, the risk of the sketched estimator continues to be unbounded around the interpolation threshold due to excessive variance. In stark contrast, bagging effectively mitigates this variance, leading to a bounded limiting out-of-sample prediction risk. To further understand this stability improvement property, we establish that bagging acts as a form of implicit regularization, substantiated by the equivalence of the bagged estimator with its explicitly regularized counterpart. We also discuss several extensions.