Exact Finite-Sample Variance Decomposition of Subagging: A Spectral Filtering Perspective
Authors: Ye Su, Mingrui Ye, Yining Wang, Jipeng Guo, Yong Liu
Organizations: Shenzhen Institutes of Advanced Technology Chinese Academy of Sciences Shenzhen 518055, China · School of Mathematics Renmin University of China Beijing 100872, China · College of Information Science and Technology Beijing University of Chemical Technology Beijing 100029, China · Gaoling School of Artificial Intelligence Renmin University of China Beijing 100872, China
Standard resampling ratios (e.g., α≈0.632) are widely used as default baselines in ensemble learning for three decades. However, how these ratios interact with a base learner's intrinsic functional complexity in finite samples lacks a exact mathematical characterization. We leverage the Hoeffding-ANOVA decomposition to derive the first exact, finite-sample variance decomposition for subagging, applicable to any symmetric base learner without requiring asymptotic limits or smoothness assumptions. We establish that subagging operates as a deterministic low-pass spectral filter: it preserves low-order structural signals while attenuating c-th order interaction variance by a geometric factor approaching αc. This decoupling reveals why default baselines often under-regularize high-capacity interpolators, which instead require smaller α to exponentially suppress spurious high-order noise. To operationalize these insights, we propose a complexity-guided adaptive subsampling algorithm, empirically demonstrating that dynamically calibrating α to the learner's complexity spectrum consistently improves generalization over static baselines.
Figures & tables
Figure 1: Structural shift of the optimal subsampling ratio α∗ across nine evaluated datasets. Blue markers represent the low-complexity regime (shallow trees), clustering near the classical heuristic α≈0.632 (dotted line) to preserve structural signals. Red markers represent the high-complexity regime (unpruned deep trees), demonstrating a systematic shift toward smaller subsampling ratios. This empirical shift corroborates the comparative statics in Theorem 5.5 , highlighting the necessity of stringent geometric filtering for high-capacity interpolators.
Datasets
Metric
Regime 1 (Low-Complexity)
Regime 2 (High-Complexity)
0.632
0.8
CGAS
0.632
0.8
CGAS
yprop_4_1
MSE
0.9672 ∗
0.9686 ∗
0.9670
1.0192 ∗
1.0427 ∗
0.9923
MAE
0.6605
0.6610 ∗
0.6605
0.7851 ∗
0.7936 ∗
0.7745
wine_quality
MSE
0.7231 ∗
0.7276 ∗
0.7221
0.9326 ∗
0.9821 ∗
0.8843
MAE
0.6671 ∗
0.6695 ∗
0.6666
0.7663 ∗
0.7859 ∗
0.7457
superconduct
MSE
0.2881 ∗
0.2908 ∗
0.2876
0.8628 ∗
0.9650 ∗
0.7468
Table 1: Out-of-sample MSE and MAE across various datasets under two distinct functional complexity regimes. The best performance metrics in each regime are highlighted in bold .
Datasets
Metric
Regime 1 (Low-Complexity)
Regime 2 (High-Complexity)
0.632
0.8
CGAS
0.632
0.8
CGAS
yprop_4_1
MSE
0.9649 ∗
0.9660 ∗
0.9647
1.3692 ∗
1.5465 ∗
1.0295
MAE
0.6622 ∗
0.6647 ∗
0.6618
0.9137 ∗
0.9724 ∗
0.7900
wine_quality
MSE
0.6449 ∗
0.6415
0.6420
1.1593 ∗
1,2971 ∗
0.9195
MAE
0.6297 ∗
0.6267
0.6267
0.8543 ∗
0.9031 ∗
0.7608
superconduct
MSE
0.1449 ∗
0.1360 ∗
0.1304
0.9728 ∗
1.0731 ∗
0.7637
Table 2: Out-of-sample MSE and MAE for KNN across various datasets under two distinct functional complexity regimes. The best performance metrics in each regime are highlighted in bold .
Figure 2: Relative error reduction in out-of-sample MSE (left) and MAE (right) achieved by the theoretically calibrated RF∗ (bootstrap with max_samples= α∗ ) over the standard RF baseline (default bootstrap). The grey bars indicate marginal yet strictly non-negative improvements under the low-complexity regime. The red bars highlight substantial and consistent performance gains under the high-complexity regime, empirically validating that restricting the sampling fraction dynamically suppresses high-order interpolation noise even within a standard bootstrap framework.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Symbol
Definition
Domain/Space
1. Sets and Spaces
X,Y
Feature input space and target continuous output space
-
Z
The measurable product space X×Y
-
Dn
The finite training dataset {Z1,…,Zn}
Zn
[n],[k]
The integer index sets {1,2,…,n} and {1,2,…,k}
Z+
(k[n]),(c[n])
The collection of all k -element or c -element subsets drawn from [n]
We study feature bagging through the lens of algorithmic stability. Feature bagging is an ensemble strategy that aggregates base learners trained on randomly subsampled feature subsets, possibly in a data-dependent manner. We introduce feature instability (FI), the feature-axis analogue of instance instability (II), which measures sensitivity to removing a single feature. Smaller values of II or FI correspond to stronger stability, and our experiments show that FI captures generalization-relevant information complementary to II. Within this framework, we analyze feature bagging in both a parametric linear model and a model-free setting inspired by recursive feature subsampling in random forests. In both settings, we establish formal guarantees showing that feature bagging improves the relevant stability relative to its non-bagged counterpart, with larger improvements under more aggressive subsampling. We further show that a modest number of bagging rounds is sufficient to approach the infinite-bagging stability level.
Yuheng Ma, Qiang Sun
School of Statistics, East China Normal University · University of Toronto · MBZUAI
This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the γ-graph dimension characterizes learnability for a broad class of natural aggregation procedures. Furthermore, we prove that an extremely simple aggregation procedure, combining three interpolating hypotheses via the median, is optimal among all these aggregation procedures, and is strictly more powerful than proper learning. Finally, we show that some hypothesis classes are learnable only by aggregating infinitely many hypotheses or by using non-interpolating aggregation rules (which may predict outside the range of their inputs), and any finite interpolating aggregation fails to achieve even trivial performance.
Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu Zou
Department of Computer Science, Aarhus University, Aarhus, Denmark · Department of Statistics, University of Oxford, Oxford, United Kingdom
Is the same data equally useful to every learner? The question is whether the value of a training sample belongs to the sample or arises in its interaction with the learner. We test it with a selection experiment. Under a per-class budget, two kinds of samples compete for the slots: easy samples, which a short training run learns first, and coverage samples, which spread over the class in feature space. Easy samples win at small budgets and coverage samples at large ones, and the budget at which the winner flips, the crossover m0, can be measured. We ask whether m0 is set by the data or by the learner. To separate the two, we freeze the selected subsets and change only the learner that trains on them. On low-resolution ImageNet-100, doubling the width of a ResNet-18 moves the crossover from 57 to 85 samples per class on the same subsets. Enlarging the input grid from 32 to 64 pixels at fixed image information moves it from 85 to 57, and a single stride change reproduces or removes this shift. The grid shift shrinks as width grows. Under the native ImageNet-1k protocol, a 4x range of width moves the boundary by at most a few samples per class. On a Vision Transformer, coverage wins at every measured budget, even with easy subsets that work on the convolutional learner. The budget at which one kind of sample stops being the more useful kind therefore belongs to the learner, and the preferred regime of a selection strategy has to be read against the learner that will use the data.