Ensemble linear interpolators: The role of ensembling
Mingqi Wu Qiang Sun
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.